信息论课件chap检错与纠错方式和能力

华侨大学通信工程 ： : 上次上次码重最小距离错误图样定理4.4.1若纠错码的最小距离为dmin，那么如下三个结的任何一个结论独立成若要发现e个独立差错，则要求最dmine1；若要纠正t个独立差dmin2t③若要求发现e个同时又纠正t个独立差错dminet1(et)3 信息 监督表示：（n,k）分组码。n：分组长度k/n：编码效率分类：线性码：信息位与校验位之间为线非线性码：信息与校验位之间不 性关4r个

n=r+ ：信息元个r：校验元个编码是在信道输入端2n个n长的二元序列中找一组2k个码字，使码字的r(=n-k)个校验元与其k个信息元之间满足一定译码常采用最大似然译码准则( ：最小汉明距离译码准则)最大似然准则(ML)：若P{Y|xk}是所有P{Y|xi}中最大的一个，则判断端发的是 [例4.2.1]设将信源 输出的二进制序列进行分组，分长度为k=1，相应的码字表Mcn这样的码字共有两个:“1”和“0”现将M进行变换，变换规

因此，形成的纠错码具有以下形C 由于m1只取“0”或“l”，所以C的全体码字只有两个长为n的全“0”或全“l”即经过上述变换，得到了(n,1)重复码6[例4.2.2]设信源 输出的信息序列为M其中mi(1ik)是二进制数

m2m1)信道 输出的码字为C c2c1)，其中ci(1in,nk)也是二进制数。若从M到 c 由于从M到 的变换是一种线性变换，所以全体C的集构成了一种(n,n-1)线性分组本例变换后码字集合中每一个码字的 cnc1(m1m2 mk)c1因为假设了码为二进制码，上述码元的和是模2和 7[例 (7,3)分组码。按以下的规则(校验方程)可得到四校验

c3c2c1

c5

c4m3 ccmm c2m3c mm3

m1是信息码元，方程中的加运算为模2由方程得到(7,3)分组码的八个码八个信源序列与八个码字的对应关系列于表4.2.1中8 00000000000010011101010010011101101110101001001110101101001111011010011111110100 c c4m3 cmm c2m3c m 9对于线性分组码有一个非常重要的结论：一个(n,k)组码中非零码字的最小重量等于该码的最小距离dmin 因 性分组码的讨论中就有了生成矩阵和一致校验矩阵的概念生成4.2.的(7300100001001011110101110 c5c4m3

c7c6c5c4c3c2c1m3m2m1cm c2m3

Cccm

称矩阵G为线性分组合，而3个信息码元构成的信息位只有88可见，在本例中，线性分组码的码书是选取了128合之中的8种（合法码字）3的７３因素是生成矩阵生成规则 G 1 。4.2.3pp1,n0100p1,k2,k01k,kpk,np2,n1 1

G

定义4.2.2若信息组以不变的形式，在码字的任意k现，则该码称为系统码。否则，称为非目前常用的有两种形式的

GIk一种是把信息组排在码字(cn ,c2,c1)的最左边k位,cn,cnk式(4.2.另一种是把信息组安置在码字(cn ,c2,c1)的最右边k位,c,1 1

GP

kG

能够产生系统码的生成矩阵为典型矩阵(或称标准统型阵不具有元和特别如果生成矩阵G为非的，可经过行初等变换变成标一致校验从前面的讨论我们知道，编码问题就是在给定的dmin下如何利用已知的k个信息码元求得r=n-k个 c7 c5

c4c7

c7c5c4cccc m

c

cc cmm

c

cc

m3 m

c70110001100110101000111000C

06

HCT 0c5 c 0

4

or c c 1 c2 HCT CHT该式表明C中各码元是满足由矩阵H所确定的r个线性方程的解C是码书C中的一个码字，由C的全体就构成反之，若某码元序列满足由H所确定的r个线性方程，则该元序列一定是码书C中的一 由于(n,k)码的 字均按H所确定的规则求出，故H为一致校验矩阵一致校验矩阵H有如下特点①Ｈ矩阵的每一行代表一个线性方程的系数，它对应 元的线性方程②Ｈ矩阵每一列代表此码元与哪几个校验方③由该Ｈ矩阵得到的(n,k)分组码的 字C都满足由矩阵的行所确(n,k)码需有r 元，故需有r个独立的线性方程因此，H矩阵必须有r行，且各行之间线性无⑤生成矩阵G中的每一行及其线性组合都是(n,k)码中的个码字，故

c7cc7c5c4

06

1HGT1

cccc

c 100011100 1000111000 GHT c

04 1c3 ccc

c

2 HQIr式中Q是一个rk阶矩阵。我们称这种形式的H矩阵为典型矩阵(或标准阵)，同样，采型矩阵形式的H矩阵更

Ik HGT

QIr

QIrPT

Q Q PH0H01100110101000111000Q

Gk|11G01000110111111010线性分组码的[例4.2.4]设二元码字为Cc7c6c5c4c3c2c1码的一致校验矩阵H 0 0 H1 1

0T

c4c7 cc c

c4c7 cc c

按照该线性方程组，可直接画出(7,3)线性分组码的行编码电路和(a)并行编码电 (b)串行编码电例4.2.5（P85）考虑一个(7,4)分组线性码，其生成00000010100110101100101GG00对于信息序

画出该(7,4)分组线性码 原理图

R ，检验它是否为 对偶码和缩矩阵H(n,k)码的一致校验矩阵看成是(n,r)码的生成则称这两种码互为对偶码[例4.2.6]求例4.2.3(7,3)码的G矩阵就是(7,3)码的H矩阵，将其化成标准形式后即可(7,3)(7,4)码，如表所示。011000110000010110100行初等变 1001110001(7,4 010111100000101 在有些情况下，如果对某一给定长度的信息码元找不适码长的码，则可将某一(n,k)码缩短以满足要 000000000001001111010010011011011100100100110101101001110110101111111010信息码码 000000010111101011111100缩短码的G矩阵和H矩阵也可由原(n,k)码的G和H推导而。i,ki,i行和前i列即可，而H7,36,2H

G

H6,2 1 对偶码和对偶码和缩短码的纠错能力与原码的纠错性能线性分组码的CECE R 1)RCriciRHC CHTEHRHC CHTEHT T则认为R有错 定义4.2.3设(n,k)码的一致校验矩阵为H，R是发送码字为时的接收序列，则 SRHTEH为接收序列R的伴随式或校正子

EE

SSHHhh2,1nhh1rhrhSHETnhh 1n1 enhenhnen1hn1若S0那么计算伴随式S得到的结果必为“0”，此时的错误不能发现，也无法纠正，因而这样的错误图样称为不可检错图样SSTeh e [例4.2.7]计算例4.2.3所述(7,3)码接收R1 解：(7,3)码的一致校验矩阵为H

01101100110101000111000(7,3)00R1

接收端

0 0

STHRT 0

0 当接收R2 )时，接收端 根据接收序列计算

0 0 STHRT 0 0 1 1由于S0，所以 判定接收序列R2码，即发送码字应为( )。

0 0 STHRT 1 0 1 1S0与H实现伴随式计算的电路：如前所述的(7,3)码，设接收序列(7654321

r06

rr

4s s4sr

STHRT

05

r5r33

04

rr s

r

rr

2

1图4.2.3线性分由前可知，线性分组码的纠错能力t和码字的最小距离dmin 进一步研究dmin和码字结构的关系。定的，知H矩阵，该码的结构也就知道了，实际上所谓校验就是利用H矩阵去鉴别接收矢量R的结构。那么从研究码的纠错能力角度来看dmin与H有什么关系呢？定理 (n,k)线性分组码最小码距等于dmin的充要条件H矩阵中任何dmin1列线性无定理4.1.2是构造任何类型线性分组码的基础。由定理可出以下三个结论为了构造最小距离dmine1(可检测e个错误)或dmin2t1(中任意dmin1列线性无关。列H无全“”任一线性分组码的最小距离(或最小重量dmin均满足dminnkdminnk1的线性分组码称为极大最小距离码。在同样的n,k之下，由于dmin最大，因此纠错能力更强，所以设计这种码，是编码理论中人们感的一个课题。根据定理4.2.1，我们可以由H码的纠错、检错能力在已知信息位k的条件下，如何去确定校验位r=n-k的位数t若C是(n,k)二元码，当巳知k时，要使C能纠正t个错t必须有不少于r个校验位，且r

2r1

CnC。汉明 汉明码有许多很好的性质，它可以用一种简洁的方法进行译1明码参对于任意正整数m>=3，存在具有下列参数的汉码长：n=2m-信息位数：k=2m-m-校验位数：r=n-最小码（：m=3，n=7，k=4

（7,4）汉明（15,11）汉明22以最