1、2022-12-221信息论基础第4章 抗干扰二元编码韩宇辉22022-12-22第4章 抗干扰二元编码4.1 抗干扰二元编码的基本概念抗干扰二元编码的基本概念4.2 检错码检错码4.3 用于单向信道的简单纠错码用于单向信道的简单纠错码4.4 纠一位错误的汉明码纠一位错误的汉明码4.5 循环码循环码4.6 纠正独立错误的卷积码纠正独立错误的卷积码4.7 纠正突发错误的编码纠正突发错误的编码4.8 有限域的基本知识有限域的基本知识2022-12-2234.1 抗干扰二元编码的基本概念42022-12-224.1.1 抗干扰编码的基本思想 00 01 10 110 00 01 11 1奇校验奇校验
2、抗干扰编码的基本思想：抗干扰编码的基本思想：利用剩余的增加来换取可靠性的提高利用剩余的增加来换取可靠性的提高信息元信息元监督元监督元许用码字：许用码字：系统实际使用的码字。系统实际使用的码字。001,010,100,111禁用码字：禁用码字：系统中不使用的码字。系统中不使用的码字。000,011,101,11052022-12-224.1.2 几个定义 码距（汉明距离）码距（汉明距离）W=x1 x2 xn xi 0,1W=x1x2xn xi 0,1 最小码距（最小汉明距离）最小码距（最小汉明距离）一个码组（码字）集合中，两码字间的最小距离一个码组（码字）集合中，两码字间的最小距离dmin称为该
3、码字集合的最小距离，简称称为该码字集合的最小距离，简称最小码距最小码距。码重（汉明重量）码重（汉明重量）码组中所含码元码组中所含码元“1”的数量，称为该码组的重量，的数量，称为该码组的重量，简称简称码重码重。1(,)0W Wniiidxxdn62022-12-224.1.3 最小码距与纠检错能力的关系1.1.译码准则译码准则 p(yj/xi)X Y X:x1,x2,xn Y:y1,y2,ymP(Y/X):p(yj/xi);i=1,2,n;j=1,2,m这时定义一个收到这时定义一个收到yj后判定为后判定为xi的单值函数，的单值函数，即：即：F(yj)=xi (i=1,2,n;j=1,2,m)；这
4、个函数称为这个函数称为译码函数译码函数。它构成一个译码函数组，。它构成一个译码函数组，这些函数的值组成了这些函数的值组成了译码准则译码准则。对于有对于有n个输入，个输入，m个输出的信道来说，可以有个输出的信道来说，可以有nm个不同的译码准则。个不同的译码准则。72022-12-222.2.最小码距译码准则最小码距译码准则若若 d(x*j,yj)d(xi,yj)(对一切的对一切的i)，则，则F(yj)=x*j(j=1,2,m，x*j X)3.3.最小码距与纠检错能力的关系最小码距与纠检错能力的关系【例【例】X：0000000,1111111，dmin=7检错能力：检错能力：发送码字：发送码字：接
5、收码字：接收码字：判断结果：判断结果：纠错能力：纠错能力：发送码字：发送码字：接收码字：接收码字：译码结果：译码结果：00000000000000 00000000000000 10000000000000 11000000000000 11100001111111 11110001111111 11111001111111 11111101111111 11111110000000最多可以发现最多可以发现6位错误位错误0000000传输正确传输正确 最多可以纠正最多可以纠正3位错误位错误1000000传输错误传输错误 1100000传输错误传输错误 1110000传输错误传输错误 11110
6、00传输错误传输错误 1111100传输错误传输错误 1111110传输错误传输错误 1111111传输正确传输正确 82022-12-22纠错纠错同时同时检错的能力检错的能力纠正纠正1位错误：位错误：发送码字：发送码字：接收码字：接收码字：判断结果：判断结果：译码结果：译码结果：纠正纠正2位错误：位错误：发送码字：发送码字：接收码字：接收码字：判断结果：判断结果：译码结果：译码结果：0000000000000010000001100000111000011110001111100111111011111110000000最多可以同时发现最多可以同时发现5位错误位错误0000000传输正确传输
7、正确 1000000传输错误传输错误 1100000传输错误传输错误 1110000传输错误传输错误 1111000传输错误传输错误 1111100传输错误传输错误 1111110传输错误传输错误 1111111传输正确传输正确 最多可以同时发现最多可以同时发现4位错误位错误0000000 0000000 不进行译码不进行译码不进行译码不进行译码不进行译码不进行译码不进行译码不进行译码1111111 1111111 传输正确传输正确 传输错误传输错误 传输错误传输错误 传输错误传输错误 传输错误传输错误 传输错误传输错误 传输错误传输错误 传输正确传输正确 0000000 0000000 00
8、00000 不进行译码不进行译码 不进行译码不进行译码1111111 1111111 1111111 92022-12-22若发现若发现e个错误，则要求个错误，则要求 dmine+1;若纠正若纠正t个错误，则要求个错误，则要求 dmin2t+1;若纠正若纠正t个错误，个错误，同时同时发现发现e个错误，个错误，则要求则要求dmint+e+1（te）102022-12-224.1.4 抗干扰编码的基本原理1.1.原理：原理：dmin与纠检错能力的关系与纠检错能力的关系2.2.实现方法：实现方法：信息元信息元+监督元监督元3.3.代数编码：代数编码：信息元与监督元是按一定的代数关系信息元与监督元是按
9、一定的代数关系互相制约的。互相制约的。(1)(1)分组码（块码）分组码（块码）k信息位长度信息位长度 n码长码长 r=n-k监督位长度监督位长度特点：特点：无记忆性无记忆性(n,k)分组码的分组码的码率码率（编码效率）：（编码效率）：=R/C=H(A)/Hmax(A)=k/n逻辑网络逻辑网络12k12n.112022-12-22 分组码按其结构可以分为系统码和非系统码。如分组码按其结构可以分为系统码和非系统码。如果在一个分组码码字中，信息元安排在前果在一个分组码码字中，信息元安排在前k位，而位，而监督元安排在后监督元安排在后n-k=r位，则称其为位，则称其为系统码系统码，否则，否则就称为就称为
10、非系统码非系统码。(2)(2)卷积码（连环码）卷积码（连环码）m=m+1编码器的约束长度编码器的约束长度 或编码约束长度或编码约束长度 n=n0m卷积码的约束长度卷积码的约束长度 特点：特点：有记忆性有记忆性，输出不仅与当时的输入有关，还，输出不仅与当时的输入有关，还与前与前m个单位时间的输入有关。个单位时间的输入有关。(n0,k0,m)卷积码的码率（编码效率）：卷积码的码率（编码效率）：=k0/n0时序网络时序网络12k012n0.122022-12-224.4.抗干扰编码的分类抗干扰编码的分类(1)(1)用途：用途：检错码和纠错码检错码和纠错码(2)(2)干扰的性质：干扰的性质：纠正独立错
11、误的编码和纠正突发错误的编码纠正独立错误的编码和纠正突发错误的编码p 独立错误独立错误也称为也称为随机错误随机错误，是由随机噪声引起，是由随机噪声引起的，其特点是各码元发生错误与否是互相独立的，的，其特点是各码元发生错误与否是互相独立的，因而一般不会成片地出现错误。因而一般不会成片地出现错误。p 突发错误突发错误是由突发噪声（脉冲噪声、深衰落、接是由突发噪声（脉冲噪声、深衰落、接触不良引起噪声等）引起的，其特点是各码元是触不良引起噪声等）引起的，其特点是各码元是否发生错误存在某种相关性。通常称突发错误持否发生错误存在某种相关性。通常称突发错误持续时间内的码元数目为续时间内的码元数目为突发长度突
12、发长度。(3)(3)对信息的处理方式：对信息的处理方式：分组码和卷积码分组码和卷积码(4)(4)约束关系：约束关系：线性码和非线性码线性码和非线性码(5)(5)信息元的位置：信息元的位置：系统码和非系统码系统码和非系统码132022-12-225.5.差错控制系统的分类差错控制系统的分类(1)ARQ(Automatic Repeat reQuest)自动反馈重传自动反馈重传 采用检错码，接收端收到码字后判断在传输中有采用检错码，接收端收到码字后判断在传输中有无错误产生，并通过反馈信道把检测结果告诉发无错误产生，并通过反馈信道把检测结果告诉发送端。发端把收端认为有错的消息再次传送，直送端。发端把
13、收端认为有错的消息再次传送，直到收端认为正确为止。到收端认为正确为止。优点：优点：译码设备简单，由于同一种码的检错能力比译码设备简单，由于同一种码的检错能力比纠错能力要高得多，因而整个系统能获得极低的纠错能力要高得多，因而整个系统能获得极低的误码率。误码率。缺点：缺点：应用应用ARQ方式方式必须有一条从收端至发端的反必须有一条从收端至发端的反馈信道，只适用于点对点的方式，并要求收、发馈信道，只适用于点对点的方式，并要求收、发两端必须互相配合，其控制电路比较复杂，实时两端必须互相配合，其控制电路比较复杂，实时性也较差。性也较差。142022-12-22(2)FEC(Forward Error C
14、orrection)前向纠错前向纠错 采用纠错码，接收端收到码字后，自动地纠正传采用纠错码，接收端收到码字后，自动地纠正传输中的错误。输中的错误。优点：优点：不需要反馈信道，既适用于点对点的方式，不需要反馈信道，既适用于点对点的方式，也适用于点对多点的方式，实时性较好，控制电也适用于点对多点的方式，实时性较好，控制电路也比较简单。路也比较简单。缺点：缺点：译码设备较复杂，编码效率较低。译码设备较复杂，编码效率较低。(3)HFC(Hybrid Error Correction)混合纠错混合纠错 是前两种方式的结合。发端发送的码既能检错、是前两种方式的结合。发端发送的码既能检错、又有一定的纠错能力
15、。收端译码时若发现错误个又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。通过反馈信道告知发方重发。2022-12-22154.2 检错码162022-12-22一致监督检错码一致监督检错码也叫也叫一致监督校验码一致监督校验码或或奇偶校验码奇偶校验码。1.1.原理：原理：信息元（信息元（k位）：位）：x1，x2，xk监督元（监督元（1位）：位）：xn=xk+1偶校验：偶校验：奇校验：奇校验：4.2.1 一致监督
16、检错码1(mod2)kniixx11kniixx172022-12-22/22221(1)niiniuneeipCpp(1)/22221(1)niiniuneeipCpp246.ppp1ep 22222(1)nuneenepC ppC p2.2.漏检概率漏检概率 奇偶校验码只能发现码字中的奇数个错误，不能奇偶校验码只能发现码字中的奇数个错误，不能发现偶数个错误。发现偶数个错误。n为偶数：为偶数：n为奇数：为奇数：若若 ，则，则182022-12-22 定比码定比码也称也称恒比码恒比码、等重码等重码或或范范德伦码德伦码，每个码字，每个码字中中“1”与与“0”的比例是固定的，的比例是固定的，“1”
17、的个数也是固的个数也是固定的。定的。1.1.五三定比码五三定比码 五三定比码每个码字的码长为五三定比码每个码字的码长为5，含有，含有3个个“1”和和2个个“0”的码字作为许用码字。的码字作为许用码字。(1)许用码字数目：许用码字数目：禁用码字数目：禁用码字数目：4.2.2 定比码355 4 3101 2 3C 535232 1022C192022-12-2226uepp234246(1)3(1)ueeeeppppppp1ep (2)漏检概率漏检概率 若若“1”错成错成“0”的数目正好等于的数目正好等于“0”错成错成“1”的的数目，则五三定比码不能发现这类错误。数目，则五三定比码不能发现这类错误
18、。一个码字中有一个码字中有2位错误，且其中位错误，且其中1位位“1”错成错成“0”，1位位“0”错成错成“1”的概率为的概率为 一个码字中有一个码字中有4位错误，且其中位错误，且其中2位位“1”错成错成“0”，2位位“0”错成错成“1”的概率为的概率为 因此，漏检概率为因此，漏检概率为 当当 时，时，12123232(1)(1)6(1)eeeeeepC ppC pppp22224432(1)3(1)eeeeepC pp C ppp202022-12-22(3)编码效率编码效率 =R/C=H/Hmax=log10/log3266%2.2.七三定比码七三定比码 七三定比码每个码字的码长为七三定比码
19、每个码字的码长为7，含有，含有3个个“1”和和4个个“0”的码字作为许用码字。的码字作为许用码字。(1)许用码字数目：许用码字数目：禁用码字数目：禁用码字数目：(2)编码效率编码效率 =R/C=H/Hmax=log35/log12872%377 6 5351 2 3C 73721283593C212022-12-22(3)漏检概率漏检概率 一个码字中有一个码字中有2位错误，且其中位错误，且其中1位位“1”错成错成“0”，1位位“0”错成错成“1”的概率为的概率为 一个码字中有一个码字中有4位错误，且其中位错误，且其中2位位“1”错成错成“0”，2位位“0”错成错成“1”的概率为的概率为 一个码
20、字中有一个码字中有6位错误，且其中位错误，且其中3位位“1”错成错成“0”，3位位“0”错成错成“1”的概率为的概率为因此，漏检概率为因此，漏检概率为 当当 时，时，121325234(1)(1)12(1)eeeeeepC ppC pppp2222243434(1)(1)18(1)eeeeeepC pp C pppp33336634(1)4(1)eeeeepC p C pppp2543624612(1)18(1)4(1)ueeeeeepppppppppp1ep 212uepp2022-12-22224.3 用于单向信道的简单纠错码232022-12-22编码效率：编码效率：=1/n(1)逐位重
21、复：逐位重复：用于纠正随机错误。用于纠正随机错误。(2)逐段重复：逐段重复：还可用于纠正突发错误。还可用于纠正突发错误。例如，例如，1 0 1 1 0 1 0 0逐位重复，三重码：逐位重复，三重码：111 000 111 111 000 111 000 000逐段重复，四位一段，三重码：逐段重复，四位一段，三重码：1011 1011 1011 0100 0100 01004.3.1 简单重复码将信息重复多次，只要正确传输的次数多于传错的将信息重复多次，只要正确传输的次数多于传错的次数，则可以将错误纠正过来。重复次数次数，则可以将错误纠正过来。重复次数n通常为通常为奇数。奇数。2022-12-2
22、2244.4 纠一位错误的汉明码252022-12-221.1.线性分组码的定义线性分组码的定义若分组码的监督元与信息元之间是一种线性约束关若分组码的监督元与信息元之间是一种线性约束关系，则称其为系，则称其为线性分组码线性分组码。(n,k)线性分组码的码率：线性分组码的码率：=k/n许用码字数目：许用码字数目：2k禁用码字数目：禁用码字数目：2n-2k系统码：系统码：x1 x2 xk xk+1 xk+2 xn信息元信息元监督元监督元262022-12-22111122110 kkka xa xa xx211222220 kkka xa xaxx 11220 rrrkkna xa xa xx2.
23、2.线性分组码的监督矩阵线性分组码的监督矩阵线性分组码监督元与信息元之间的线性关系可以用线性分组码监督元与信息元之间的线性关系可以用二元域上的线性方程组描述。二元域上的线性方程组描述。整理得：整理得：11111221 kkkxa xa xa x22112222 kkkxa xa xax 1122 nrrrkkxa xa xa x0,11,2,;1,2,)(ijair jk272022-12-22111122110 kkka xa xa xx211222220 kkka xa xaxx 11220 rrrkkna xa xa xx将方程组用矩阵方程来表示，可得将方程组用矩阵方程来表示，可得 11
24、1211212222121101kkrrrknaaaxaaaxaaax监督矩阵监督矩阵HH CT=0码字向量码字向量 C=x1 x2 xn 282022-12-22111212122212111kkrrrkaaaaaaHaaark子阵子阵Prr单位阵单位阵Ir111212122212111kkrrrkaaaaHaaaaa111212122212111kkrrrkaaaaHaaaaar=n-k行：行：r个监督元，个监督元，r个监督方程个监督方程n列：列：n个码元之间的监督关系个码元之间的监督关系(n,k)系统系统线性分组码监督矩阵形式线性分组码监督矩阵形式:(典型监督矩阵典型监督矩阵或或标准监督
25、矩阵标准监督矩阵)H=P Ir292022-12-22111 11221 kkkxa xa xa x221 12222 kkkxa xa xa x 1 122 nrrrkkxa xa xa x11 xx22 xx kkxx121112121222112212111kkkkkkrrrnkxxaaaaaaxaxxaxxxxa111212122212121122111kkrrrkkknkkxxxxxxxxxaaaaaaaaa121211112122122212111kkkkkknrrrkxxxxxxaaaxaaaxxaaa3.线性分组码的生成矩阵线性分组码的生成矩阵302022-12-22TTTAB
26、CACB 1121112222121212111rrnkkkrkaaaaaaxxxxxxaaa码字码字C信息码组信息码组m生成矩阵生成矩阵G由于对于矩阵由于对于矩阵A，B，C有有因此因此C=mG312022-12-22G=Ik PT 112111222212111rrkkrkaaaaaaGaaa(n,k)系统系统线性分组码生成矩阵形式线性分组码生成矩阵形式:(典型生成矩阵典型生成矩阵或或标准生成矩阵标准生成矩阵)子阵子阵PTkk单位阵单位阵Ikk行行n列列322022-12-22【例】已知线性分组码的生成矩阵【例】已知线性分组码的生成矩阵G，写出信息码，写出信息码组组m1=1 0 0 0，m2
27、=0 1 0 0，m3=0 0 1 0，m4=0 0 0 1，m5=1 1 0 0，m6=1 1 1 0，m7=1 1 1 1 对应的各个码字。对应的各个码字。C1=m1 G=1 0 0 0 G=1 0 0 0 0 1 1 C2=m2 G=0 1 0 0 G=0 1 0 0 1 0 1 C3=m3 G=0 0 1 0 G=0 0 1 0 1 1 0 C4=m4 G=0 0 0 1 G=0 0 0 1 1 1 1 1000011001011000011110100101G 0100101001011000011111000011G 0010110100001101001010001111G 10
28、00011010010100101100001111G 1000011010010100101100001111G解：解：332022-12-22 1000011010010100101100001111G 0010110000111100001101001101G 1000011010010100101100001111G 1000011010010100101100001111G C5=m5 G=1 1 0 0 G=1 1 0 0 1 1 0 C6=m6 G=1 1 1 0 G=1 1 1 0 0 0 0 C7=m7 G=1 1 1 1 G=1 1 1 1 1 1 1(n,k)线性分组码的
29、线性分组码的2k个码字构成二元个码字构成二元n重矢量空间重矢量空间中的一个中的一个k维子空间。维子空间。(n,k)线性分组码的生成矩阵由线性分组码的生成矩阵由k个线性无关的码字个线性无关的码字矢量组成，构成矢量组成，构成k维子空间的一个基底，其线性组维子空间的一个基底，其线性组合可以生成所有的码字。合可以生成所有的码字。342022-12-22011110010110101101001H 1000011010010100101100001111G【例】已知线性分组码的监督矩阵为【例】已知线性分组码的监督矩阵为判断其码长和信息位长度，并写出其生成矩阵判断其码长和信息位长度，并写出其生成矩阵G。解
30、：解：r=3，n=7，k=4 H=P I3 G=I4 PT011110111101P352022-12-22 ,ECRRCECRE 12nRxxx 112212 nnnECRxxxxxxeee 12nCxxx4.4.线性分组码的译码线性分组码的译码(1)(1)错误图样错误图样发送码字发送码字：接收码字：接收码字：错误图样错误图样：ei=1表明相应位表明相应位有错有错，ei=0表明相应位表明相应位无错无错。362022-12-22 RCE TSHCE TTHCHE TSHE(2)(2)校验矩阵校验矩阵n定义定义S=HRT为为校验矩阵校验矩阵，也称为，也称为校验子校验子或或伴伴随式随式。p若若S=
31、0，表明收到的码字为许用码字，译码器，表明收到的码字为许用码字，译码器认认为为接收码字无错误。接收码字无错误。p若若S0，表明收到的码字为禁用码字，可以判定，表明收到的码字为禁用码字，可以判定接收码字接收码字一定一定有错误。有错误。n由于由于 因此因此校验子与发送码字无关，而仅与错误图样有关。校验子与发送码字无关，而仅与错误图样有关。372022-12-22011110010110101101001H(3)(3)校验子与译码校验子与译码【例】【例】(7,4)线性分组码的监督矩阵为线性分组码的监督矩阵为(1)无错无错 E=0 0 0 0 0 0 0(2)错一位错一位 E=1 0 0 0 0 0
32、0 E=0 1 0 0 0 0 0 E=0 0 1 0 0 0 0 S=HET=0 0 0TS=HET=0 1 1TS=HET=1 0 1TS=HET=1 1 0T382022-12-22若校验子为若校验子为0，认为收到的码字没有错误；，认为收到的码字没有错误；若校验子恰好等于若校验子恰好等于H的第的第i列，认为接收码字的第列，认为接收码字的第i位发生了错误。位发生了错误。线性分组码可以纠正线性分组码可以纠正1位错误需满足的条件：位错误需满足的条件：H的各个列不同且不含有全的各个列不同且不含有全0列；列；2r-1n。392022-12-225.5.汉明码汉明码(1)(1)汉明码的定义汉明码的定
33、义对于任意正整数对于任意正整数r3，存在有下列参数的线性分组码：，存在有下列参数的线性分组码：码长：码长：n 2r-1信息位：信息位：k=n-r监督位：监督位：r=n-k最小码距：最小码距：dmin=3 这种码称为这种码称为汉明码汉明码。若。若n=2r-1称为称为狭义汉明码狭义汉明码或或完备汉明码完备汉明码；若；若n 2r-1称为称为广义汉明码广义汉明码。(2)(2)汉明码汉明码H矩阵的构造矩阵的构造 将将2r-1非全非全0的的r维列向量作为维列向量作为H的各列。的各列。402022-12-22【例】构造【例】构造(7,4)汉明码的监督矩阵。汉明码的监督矩阵。解：解：n=7，k=4，r=n-k
34、=3。由于由于n=2r-1，故为狭义汉明码。，故为狭义汉明码。将将7个非全个非全0的的3维列向量作为维列向量作为H的各列即可。的各列即可。或或011110010110101101001H000111101100111010101H系统码系统码非系统码非系统码412022-12-22(3)(3)汉明码的错误译码概率汉明码的错误译码概率 狭义汉明码狭义汉明码 狭义汉明码可以纠正一位错误，因此其错误译码概狭义汉明码可以纠正一位错误，因此其错误译码概率为：率为：由于当由于当 时，有时，有因此当因此当 时，有时，有所以所以110111(1)(1)nnEeneePpppC pp ()()()f xxf x
35、fxx0 x 1(1)1(1)nEeeePnpnpnp 2(1)EePn np1ep(1)1,neepnp 1(1)1(1)neepnp 422022-12-22 广义汉明码广义汉明码 广义汉明码可以纠正一位错误，还可以纠正部分广义汉明码可以纠正一位错误，还可以纠正部分2位位及及2位以上的错误，因此其错误译码概率：位以上的错误，因此其错误译码概率：比如，比如，(6,3)广义汉明码的监督矩阵为广义汉明码的监督矩阵为错错2位时：若第位时：若第1位和第位和第6位错，或者第位错，或者第2位和第位和第5位错，或位错，或者第者第3位和第位和第4位错，校验子均为位错，校验子均为1 1 1T。因此，不妨。因此
36、，不妨规定当校验子为规定当校验子为1 1 1T时，译作第时，译作第1位和第位和第6位错。此位错。此时，该广义汉明对于第时，该广义汉明对于第1位和第位和第6位错这种错两位的情位错这种错两位的情况也可以纠正。况也可以纠正。000111011001101010H110111(1)(1)nnEeneePpppC pp 432022-12-22(4)(4)增余汉明码增余汉明码n在汉明码的基础上，再增加一位监督元，使汉明在汉明码的基础上，再增加一位监督元，使汉明码的最小码距码的最小码距dmin=4，可以在纠一位错的同时检，可以在纠一位错的同时检两位错，这种线性分组码称为两位错，这种线性分组码称为增余汉明码
37、增余汉明码。n增加的监督元通常取为原汉明码所有码元的模增加的监督元通常取为原汉明码所有码元的模2和，也就是说增余汉明码的和，也就是说增余汉明码的H矩阵是在原汉明矩阵是在原汉明码码H矩阵的最右侧加上一个全矩阵的最右侧加上一个全0列，再在下面加列，再在下面加上一个全为上一个全为1的行。的行。442022-12-22(7,4)汉明码汉明码(8,4)增余汉明码增余汉明码nH矩阵的各个列不同，且任何两列之和不同于另矩阵的各个列不同，且任何两列之和不同于另一列，因此可以纠一列，因此可以纠1位错的同时检出位错的同时检出2位错。位错。n增余汉明码的构成方法不唯一。增余汉明码的构成方法不唯一。011110010
38、110101101001H000011110010110101101001H 1 1 1 1 1 1 1 1000 1 1 1 0 0 0 0 12022-12-22454.5 循环码462022-12-221.1.循环码的定义循环码的定义具有循环移位自闭性的线性分组码称为具有循环移位自闭性的线性分组码称为循环码循环码。所。所谓谓循环移位自闭性循环移位自闭性是指码字集合中的任何一个码是指码字集合中的任何一个码字的循环移位也是该码字集合中的一个码字。字的循环移位也是该码字集合中的一个码字。若若 C(0)=cn-1,cn-2,c1,c0C(C为许用码字集合为许用码字集合)，则则 C(1)=cn-2
39、,cn-3,c0,cn-1C。0000000001110101001110111010循环码循环码1001110101001111010011110100循环码循环码000001010011信息码信息码100101110111信息码信息码(7,3)系统循环码系统循环码472022-12-222.2.循环码的多项式描述循环码的多项式描述n一个一个(n,k)循环码的码字循环码的码字c=cn-1,cn-2,c1,c0可可以用一个二元域上的以用一个二元域上的n-1次多项式表示：次多项式表示：c(x)=cn-1xn-1+cn-2xn-2+c1x+c0 ci 0,1 这个多项式称为这个多项式称为码字多项式
40、码字多项式或或码多项式码多项式。n码字矢量的向左循环移位一次可以用码字矢量的向左循环移位一次可以用x乘上乘上C(x)后后取模取模xn-1(或或xn+1)来表示。来表示。模模xn-1相当于相当于xn-1=0，即，即xn=1 xc(x)=x(cn-1xn-1+cn-2xn-2+c1x+c0)=cn-1xn+cn-2xn-1+c1x2+c0 x =cn-2xn-1+c1x2+c0 x+cn-1 (模模xn-1)482022-12-2211021010()()()()krrkrrrrgggxg xgggxg xG xgggg x3.3.循环码的生成多项式循环码的生成多项式定义：定义：(n,k)循环码中
41、，次数最低的非循环码中，次数最低的非0码多项式是唯码多项式是唯一的，其次数为一的，其次数为r=n-k次。该多项式称为循环码的次。该多项式称为循环码的生成多项式生成多项式。g(x)=grxr+gr-1xr-1+g1x+g0 （gr=g0=1）ng(x),xg(x),x2g(x),xk-1g(x)为为k个线性无关的码个线性无关的码字，可以作为该循环码生成矩阵的字，可以作为该循环码生成矩阵的k行。行。492022-12-2211021010()()()()krrkrrrrgggxg xgggxg xG xgggg xn信息码组信息码组m=mk-1,mk-2,m0 对应的码多项式为：对应的码多项式为：
42、c(x)=mk-1,mk-2,m0 G(x)=mk-1xk-1g(x)+mk-2xk-2g(x)+m0g(x)=m(x)g(x)结论：结论：所有循环码的码多项式都是其所有循环码的码多项式都是其生成多项式生成多项式g(x)的的倍式；反之，任何次数不大于倍式；反之，任何次数不大于n-1次的多项式也一次的多项式也一定是码多项式。定是码多项式。502022-12-224.4.循环码的编码循环码的编码(1)(1)非系统循环码非系统循环码c(x)=m(x)g(x)【例】已知【例】已知(7,4)循环码的生成多项式为循环码的生成多项式为g(x)=x3+x+1，求信息码组求信息码组0 1 0 1对应的循环码码字
43、。对应的循环码码字。解：解：m(x)=x2+1 c(x)=m(x)g(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1 =x5+x2+x+1 C=0 1 0 0 1 1 1512022-12-22()()()n kc xxm xr x(2)(2)系统循环码系统循环码n信息多项式信息多项式m(x)=mk-1xk-1+mk-2xk-2+m0所对所对应的系统循环码的码多项式应的系统循环码的码多项式c(x)应满足如下条件：应满足如下条件：c(x)的次数不大于的次数不大于n-1次，即可以表示次，即可以表示c(x)=cn-1xn-1+cn-2xn-2+c1x+c0；c(x)为为g(x)的
44、倍式；的倍式；cn-1=mk-1，cn-2=mk-2，cn-k=m0。n系统循环码编码步骤：系统循环码编码步骤：(r(x)次数次数n-k-1)()n kxm x()()()()()n kxm xr xq xg xg x522022-12-22()()()c xg x q x由于由于因此因此可见，可见，c(x)为为g(x)的倍式，条件的倍式，条件满足。满足。()()()()()n kxm xr xq xg xg x()()()()n kxm xg x q xr x()()()()()()()n kc xxm xr xg x q xr xr x532022-12-22【例】【例】(7,4)循环码循
45、环码g(x)=x3+x+1，求，求m=1010的系统循的系统循环码码字。环码码字。解：解：m(x)=x3+x xn-km(x)=x3(x3+x)=x6+x4 C(x)=xn-km(x)+r(x)=x6+x4+x+1；C=1010 011x3x6 +x4+x3 x3 除式除式x6 +x4x3+x+1+1x3+x+1x+1被除式被除式商式商式余式余式643()()1n kxm xxxg xxx33111xxxx 542022-12-22(3)(3)如何确定如何确定g(x)?定理定理1 1：(n,k)循环码的生成多项式循环码的生成多项式g(x)是是xn-1的因式。的因式。定理定理2 2：若若g(x)
46、是一个是一个n-k次多项式，且为次多项式，且为xn-1的因式，的因式，则则g(x)一定可以生成一个一定可以生成一个(n,k)循环码。循环码。例如，例如，x7-1=(x+1)(x3+x2+1)(x3+x+1)(7,6)循环码：循环码：g(x)=(x+1)(7,4)循环码：循环码：g(x)=x3+x2+1 或或 g(x)=x3+x+1(7,3)循环码：循环码：g(x)=(x+1)(x3+x2+1)或或 g(x)=(x+1)(x3+x+1)(7,1)循环码：循环码：g(x)=(x3+x2+1)(x3+x+1)结论：结论：xn-1的诸因式决定了所有码长为的诸因式决定了所有码长为n的循环码。的循环码。5
47、52022-12-225.5.循环码的译码循环码的译码发送码字多项式：发送码字多项式：c(x)=cn-1xn-1+cn-2xn-2+c1x+c0错误图样多项式：错误图样多项式：e(x)=en-1xn-1+en-2xn-2+e1x+e0接收码字多项式：接收码字多项式：c(x)=cn-1xn-1+cn-2xn-2+c1x+c0 c(x)=c(x)+e(x)校验子多项式：校验子多项式：s(x)c(x)e(x)模模g(x)s(x)=sr-1xr-1+sr-2xr-2+s0 r-1次多项式次多项式p 若若s(x)=0，表明收到的码字为许用码字，译码器，表明收到的码字为许用码字，译码器认为认为接接收码字无
48、错误。收码字无错误。p 若若s(x)0，表明收到的码字为禁用码字，可以判定接收，表明收到的码字为禁用码字，可以判定接收码字码字一定一定有错误。有错误。562022-12-22【例】【例】(7,4)循环码循环码g(x)=x3+x+1，求接收码字不错或，求接收码字不错或只错一位时的校验子多项式。只错一位时的校验子多项式。e(x)s(x)s2,s1,s00000011001xx010 x2x2100 x3x+1011x4x2+x110 x5x2+x+1111x6x2+1101572022-12-22这个表给出了接收码字不出错或只错一位时校验子这个表给出了接收码字不出错或只错一位时校验子多项式和校验子
49、矢量的结果。根据这个表可以进行多项式和校验子矢量的结果。根据这个表可以进行译码。译码。例如，例如，发送码字多项式为发送码字多项式为 c(x)=x4+x2+x 接收码字多项式为接收码字多项式为c(x)=x4+x3+x2+x g(x)=x3+x+1 校验子多项式为：校验子多项式为：s(x)c(x)模模g(x)=x+1 查表可知查表可知 e(x)=x3 因此因此 c(x)=c(x)+e(x)=x4+x2+x 发送码字为发送码字为 0010110582022-12-226.6.截短循环码截短循环码n通常通常xn-1只能分解出不多的几个因式，因此使得给只能分解出不多的几个因式，因此使得给定长度为定长度为
50、n的循环码的数量往往很少。为了克服这的循环码的数量往往很少。为了克服这个缺点，出现了截短循环码。个缺点，出现了截短循环码。n对于一个对于一个(n,k)循环码，若取所有前循环码，若取所有前i个信息元均为个信息元均为0的码字构成一个子集的码字构成一个子集(0ik)，其监督位长度不变，其监督位长度不变，信息位长度减少至信息位长度减少至k-i位，则得到一个位，则得到一个(n-i,k-i)码，码，称为称为截短循环码截短循环码或或缩短循环码缩短循环码。n截短循环码是原循环码的子集，因此它的最小码截短循环码是原循环码的子集，因此它的最小码距保证了它的纠错能力不会低于原来的距保证了它的纠错能力不会低于原来的(
