黑龙江省专业技术人员继续教育知识更新培训专业课程函授学习材料

1、黑龙江省专业技术人员继续教育知识更新培训通信工程专业2011年函授学习材料信道编码理论主讲教师：哈尔滨工业大学 王刚 教授摘 要在通信系统中，能够提供对多媒体(包括话音、图像和数据等)业务的支持已成为二十一世纪通信系统发展的必然趋势。然而它的实现势必要解决两大问题，其一是为了充分利用有限的信道带宽对信源进行高效的压缩即信源编码问题；其二是对压缩后的信息进行错误保护以抗击信道或网络所带来的误码或数据丢失即信道编码问题。本课程重点研究纠错编码原理，即信道编码问题。课程将重点从构造性的观点来研究信道编、译码, 以实现信道与通信系统在可靠性指标下的优化, 因此,首先是工程上的可构造性, 其次才是性能指

2、标的优化。基于这一思路, 首先讨论信道编、译码的基本概念和分类; 其次讨论两类主要信道编、译码, 即分组码与非分组的卷积码, 最后简要介绍其他类型编码：Turbo码和LDPC码。虽然信道编码内容很丰富, 但本课程在选材上将不追求信道编码本身的数学体系和严格的分析方法, 而是选择在已有理论结果的基础上以工程应用为主线, 从实例入手的简单、直观方法, 重点强调概念与方法, 力求通俗易懂。本课程研究信道编码的基本概念、Shannon第二编码定理、线性分组码、循环码以及Turbo码和LDPC码的原理。课程的研究内容对于理解通信系统中实现通信可靠性的方法具有重要意义。不要删除行尾的分节符，此行不会被打印

3、目 录摘 要I第1章 信道编码的基本概念11.1 信道编码定理11.2 信道编码的基本概念21.3 信道编码方法41.4 简单的信道编码5第2章 线性分组码102.1 线性分组码的定义102.2 基本监督矩阵(Parity check matrix)112.3 生成矩阵(Generator matrix)142.4 校验子与译码(Syndrome Matrix and Decoding)172.5 分组码的纠检错能力212.6 标准阵与校验子译码242.7 分组码的其它概念27第3章 循环码333.1 循环码的描述333.2 循环码的编码方法363.3 校验子与循环码的译码原理403.4 循环

4、码的编码电路433.5 循环码的译码453.5.1 梅吉特(Meggit)译码器463.5.2 捕错译码513.5.3 大数逻辑译码56第4章 Turbo码和LDPC码664.1 Turbo码664.2 LDPC码67参考文献72千万不要删除行尾的分节符，此行不会被打印。在目录上点右键“更新域”，然后“更新整个目录”。打印前，不要忘记把上面“Abstract”这一行后加一空行第1章 信道编码的基本概念1.1 信道编码定理联合信源信道编码已被证明是一种行之有效的解决上述问题的编码技术。该技术将信源与信道编码结合在一起考虑，比将最优的信源编码方案与最优的信道编码方案相级联的传统方法更加有效。联合信

5、源信道编码方面的研究在国外已经得到广泛的重视，而在国内还处于起步阶段，许多问题有待进一步深入的研究。定理：有噪声信道编码定理（Shannon第二编码定理）如一个离散有噪声信道有n个输入符号，m个输出符号，信道容量为C。当信道的熵速率RC时，只要码长足够长，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小，pe=。当RC时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小。 编码定理的证明比较复杂，用超球空间几何方法。 这个定理是一个存在定理，指出错误率趋于0的编码方法是存在的。 定理表明，在错误率趋于0的同时，还可以使R趋于C，这是具有理论

6、指导意义的。这个定理的证明思想为：以二元编码为例：1.2 信道编码的基本概念码字空间：如果原始信源空间有M个码字，对其进行q元等长码的信道编码，码长为N，信道码字空间的所有码字为qN个，编码器将在这qN个可用码字中选择M个码字分别代表原始信源中的M个码字，信道编码码字空间的这M个码字称为“许用码字”，而另外的qN-M个码字称为“禁用码字”。为了实现纠错编码，一定有qNM。这M个许用码字也称为一个码组，或称为码字集合。汉明距离：(Hamming distance)在一个码组（码字集合）中，任意两个等长码字之间，如果有d个相对应的码元不同，则称d为这两个码字的汉明距离。例如：和为码组X中的两个不同

7、码字，X为一个长度为N的二元码组，其中：=a1,a2,aN ai0,1=b1,b2,bN bi0,1则与的汉明距离为： d=0表明为全同码，d=N表明为全异码，如果用模2加法的概念，有 最小码距：在一个码字集合中，任何两个码字之间的汉明距离组成一个元素集合，D(,),这个集合中的最小值称为这个码字集合的最小汉明距离，简称最小码距，记为：dmin。dmin=mind(,) ,X 例如：码字重量（汉明重量）(Hamming weight)在二元编码的码字集合中，码字中“1”码元的个数称为这个码字的重量。记为：W()。利用码字重量的概念，汉明距离可以表示为：d(,)=W()分组码最小码距与纠检错能力

8、的关系：一个分组码的最小码距为dmin，则其纠检错能力为：若发现e个错误，则要求dmine+1;若纠正t个错误，则要求dmin2t+1;若纠正t个错误，同时发现e个错误，则要求dmint+e+1; te;例如：dmin=1; 无纠检错能力； dmin=2; 检一位错dmin=3; 纠一位错（或检两位错）dmin=4; 纠一位，同时检两位；dmin=5; 纠二位错（或检4位错）dmin=6; 纠二位，同时检3位；(t=2,e=3)dmin=7; 纠三位错（或检两位错）dmin=8; 纠三位，同时检4位；(t=3,e=4 0 1 2 3 t=1 1 2 e=2 dmin=31.3 信道编码方法 纠

9、错编码：根据一定的纠检错要求，对原始码字进行某种变换，使其具有具有纠检错能力，这种变换称为抗干扰编码。 实现方法：信息位+监督位=纠检错编码。 信道编码的分类：纠错码/检错码前向纠错方式(FEC-forward error correction)反馈重传方式(ARQ-automatic repeat request)混合纠错方式(HEC-hybrid error correction)在FEC中又可分为：分组码(block code/group code)卷积码(convolutional code)在分组码中常见的码包括：Hamming CodeCyclic CodeBCH CodeGola

10、y CodeReed-Solommon CodeReed-Muller CodeTurbo码LDPC码1.4 简单的信道编码1.奇偶校验码也称为一致监督检错码，是一种检错分组码。检错原理：当信息码字位二元序列，码字长度位k，共有2k个码字，可以在信息码字后面加上一位监督元，构成长度位n=k+1的检错码，X=x1,x2,xk,xk+1= x1,x2,xn对于偶校验码：监督元为对于奇校验码，监督元为：偶校验码中有偶数个1，奇校验码中有奇数个1；奇偶校验码的最小码距为dmin=2 ;可检一位错；可用码字=2n；许用码字=2k，禁用码字=2n-2k漏检概率检错码不能发现错误码字的概率称为漏检概率。奇偶

11、校验码不能发现偶数个码元错误，根据最小码距分析至少检一位错，实际上可以检出所有奇数个错。假设信道误码率为pe，码字漏检概率为Pu，有： n为偶数； n为奇数；其中n为码字长度，有：当信道误码率很小时，pe1; Pu=Cn2pe2。漏检概率不仅与信道误码率有关，而且还与码字长度有关，实际上它是一个误字率的概念，应当配合ARQ系统使用，可以看到系统可靠性是很高的。编码效率：； 实际上可知：编码效率与信道传输效率是同一个概念：认为信源符号为等概率条件。根据奇偶校验码的原理，还有一些改进方法：水平奇偶校验码，垂直奇偶校验码，群计数码等，2. 定比码（等重码，范德伦码）五三定比码与七三定比码定比码为一种

12、简单检错码。五三定比码（五单位码）用于国内电报系统，码长为5，其中1的个数为3。这种码的许用码字为：代表国内电报系统中的数字09。七三定比码（七单位码）用于国际电报系统，码长为7，其中1的个数为3。这种码的许用码字为：代表26个英文字母和一些符号。漏检概率：五三定比码和七三定比码的dmin=2，至少可以检一位错，实际上定比码可以检出所有奇数位错码，及一些偶数位错码。定比码的漏检为：偶数位错误，且一半1错为0，一半0错为1；Pu=P2+P4+P2=P10.P01=C31pe(1-pe)3-1.C21pe(1-pe)2-1P4=C22C32pe4(1-pe)5-4编码效率：3. 重复码检错码只能发

13、现错误，必须利用ARQ系统才能实现抗干扰，它要求有反向信道，而前向纠错码的最大优点就是不需要反向信道，并且实时性高。重复码是一种最简单的纠错码。在实际系统重有较广泛的应用。一个例子：一个BSC信道，输入为X=0，1，且为等概分布，信道模型为：0 p=1-pe=0.99 0 pe=0.01 pe=0.011 p=1-pe=0.99 1按最大似然译码准则为：F(0)=0; F(1)=1;在信道误码率为pe=10-2条件下，其错误译码概率为：Pemin=(1/n)(pe+pe)=(1/2)(0.01+0.01)=10-2可以看到这时系统误码率就等于信道误码率，这里没有采用任何信道编码。编译码方法重复

14、码的编码方法为，将0编为000，1编为111。这时的可用码字为23=8；分别为：X1=000 X2=001 X3=010 X4=100X5=011 X6=110 X7=101 X8=111而许用码字为000和111，相当于信道输入为X1=000，X2=111，而信道输出端为：Y1=000；Y2=001；Y3=010；Y4=100Y5=011；Y6=110；Y7=101；Y8=111这时的信道转移矩阵为：P=Y1Y2Y3Y4Y5Y6Y7Y8X1p13p12pp12pp12pp1p2p1p2p1p2p3X2p3p1p2p1p2p1p2p12pp12pp12pp13这时如果按最大似然法则译码，将为：

15、F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111错误译码概率为：Pemin=(1/2) p3+ p2p1+ p2p1+ p2p1+ p2p1+ p2p1+ p2p1+ p3= 3p2p1+ p3 310-4可见简单重复码可以将错误译码概率下降两个数量级。这是三次重传大数判别的方法；可以看出如果是五次重复码，误码率还要降低。注：从这里的译码方法可以看到：最大似然译码准则实际上是一种最小汉明距离的译码准则。为了判别比较，一般重复码都采用奇数次重复，然后按大数判决。编码效率三次重复码的编码效率为：相当于k=1,n=3 ; =k/

16、n=1/3;同样可知：五次重复码=k/n=1/5;第2章 线性分组码纠错编码(FEC)主要分为分组码和卷积码两大类，这一章主要介绍分组码中的汉明码。2.1 线性分组码的定义分组码是一种代数编码，它的基本关系一个码字包括独立的信息元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数关系为线性的则称为线性分组码。分组码的编码器的模型为：Encoder m= (mk,mk-1,m0) C=(cn-1,cn-2,c0) m为编码器的输入，称为信息码元（信息位），它由k位码元组成。C为编码器的输出，称为码字矢量，它由n位码元组成，其中有k位信息元，r=n-k位监督元。对于二元编码来说，k位信息码

17、元共有2k个不同组合，根据编码器为一一对应关系，输出的码字矢量也应当有2k种码字。对于长度为n的二元序列来(n-重)说，共有2n个可能的码字矢量，编码器只是在这2n个可能码矢中选择2k个码字，被选中的2k个n-重称为许用码字，其余的2n-2k个码字称为禁用码字，称这2k个码字矢量的集合为(n,k)分组码。信息元 监督元线性分组码定义：长度为n，有2k个码字的分组码，当且仅当这2k个码字是GF(2)上n维矢量空间（所有n重）的一个k维子空间时，称为(n,k)线性分组码，简称(n,k)码。 二元分组码为线性分组码的充要条件为两个码字的模二加也是一个码字。 由于k维子空间是在模2加法下运算的，构成了

18、一个加法交换群（阿贝尔群），所以线性分组码也称为群码。 线性分组码的一个重要参数为码率(Code rate)：R=k/n; 它实际上也就是编码效率或传输效率。 如果(n,k)码位信息位没有变化，与信息码元排列相同，并且与监督位分开，称为系统码，否则称为非系统码。2.2 基本监督矩阵(Parity check matrix)线性分组码可以用GF(2)上的矢量空间的矩阵和GF(2)上多项式来描述，对于汉明码这一类分组码用矩阵描述更为方便。汉明码定义：对于任意正整数r3，存在有下列参数的线性分组码，码长：n=2r-1信息位：k=2r-1-r=n-r监督位：r=n-k最小码距：dmin=3这种码称为狭

19、义汉明码，也称为完备汉明码。这种码的码字矢量为：C=cn-1,cn-2,c1,c0如果对于系统码，其前k位为信息位，后r位位监督位。信息位=mk-1,mk-2,m0=cn-1,cn-2,cn-k监督位=cn-k-1,c1,c0由于线性分组码的监督元与信息元之间的线性关系，可以用二元域上的线性方程组描述。记为：cn-k-1=h1,n-1cn-1+h1,n-2cn-2+h1,n-kcn-kcn-k-2=h2,n-1cn-1+h2,n-2cn-2+h2,n-kcn-kc0=hr,n-1cn-1+hr,n-2cn-2+hr,n-kcn-k 在二元域上，hij:0,1整理这个方程组可得：h1,n-1h1

20、,n-2h1,n-k100cn-1=0h2,n-1h2,n-2h2,n-k010cn-2hr,n-1hr,n-2hr,n-k001c0记为：HCT=0CT为C的转置，称矩阵H为分组码的基本监督矩阵（一致校验矩阵，一致监督矩阵）。可见系统码的基本监督矩阵为：H=P IrP=h1,n-1h1,n-2h1,n-kh2,n-1h2,n-2h2,n-khr,n-1hr,n-2hr,n-kIr=100010001P为rk矩阵，Ir为rr单位阵。举例：(7,4)系统汉明码，n=7, k=4, r=3C=c6,c5,c4,c3,c2,c1,c0；其中c6,c5,c4,c3为信息位，c2,c1,c0为监督位。H

21、=011110010110101101001由HCT=0可知：监督方程为：c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c3根据这个方程组可以进行编码。例如信息码元m=1011，则有c2=c5+c4+c3=0+1+1=0c1=c6+c4+c3=1+1+1=1c0=c6+c5+c3=1+0+1=0则汉明码字C=。2.3 生成矩阵(Generator matrix)（1）生成矩阵的基本形式：由上面(7,4)汉明码的例子；可以将基本监督方程扩展写为：c6=c6c5=c5c4=c4c3=c3c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c3用矩阵表示：c6,c5,c4,

22、c3,c2,c1,c0=c6,c5,c4,c3.1000011010010100101100001111c6,c5,c4,c3,c2,c1,c0=m3,m2,m1,m0.1000011010010100101100001111可以写为：C=m3,m2,m1,m0.G 汉明码字=信息码字生成矩阵G称为(7,4)汉明码的生成矩阵。例如：m=1100, C=1100G=可以看出：(n,k)码的生成矩阵的基本形式为：G=g1,n-1g1,n-2g1,1g1,0g2,n-1g2,n-2g2,1g2,0gk,n-1gk,n-2gk,1gk,0同样，利用生成矩阵的编码关系为C=mG而系统(n,k)码的生成矩

23、阵的基本形式应当为G=100g1,n-k-1g1,0010g2,n-k-1g2,00001gk,n-k-1gk,0这种系统码的生成矩阵也称为典型生成矩阵，其基本形式为；G=Ik,Q，Q为kr矩阵，Ik为kk单位阵。（2）系统码基本监督矩阵与典型生成矩阵的关系：从生成矩阵与码字矢量的关系可以看出：G矩阵的每一行都是一个码字矢量，分别对应信息码字100,01000001的分组码的码字。由于每一行都是码字，把每一行作为一个码字矢量，都应当满足监督矩阵所规定的监督关系，即应当有：HGT=0，同时有：GHT=0称H与G为正交矩阵，由P Ir Ik QT=0 P+QT=0 P=QT Q = P T P矩阵

24、与Q矩阵互为转置矩阵。对于系统码，已知监督矩阵H就可以确定典型生成矩阵G，反之，已知生成矩阵也就可以确定监督矩阵。（3）生成矩阵的一般性质：根据线性分组码的定义，(n,k)线性分组码C是二元n重矢量空间中的一个k维子空间，因此，在码字C的集合中（2k个码元的码组中），可以找到k个线性独立的码字，g1,g2,gk; 使C中的所有码字都是这k个码字的线性组合。g1=g1,n-1,g1,n-2,g1,0g2=g2,n-1,g2,n-2,g2,0gk=gk,n-1,gk,n-2,gk,0C=mn-1g1+mn-2g2+mn-kgk其中系数就是信息码字矢量的元素：mn-1,mn-2mn-k=mk-1,m

25、k-2m0 根据线性矢量空间的知识，这k个码字矢量就可以张成（生成）这个k维子空间，将这k个矢量组成的矩阵就是(n,k)分组码的生成矩阵。所以生成矩阵是一个k行n列的矩阵。 确定(n,k)码的生成矩阵的问题实际上就是确定n-重矢量空间中k维子空间的k个线性无关的码字矢量的问题。也就是寻找基底的问题。 (n,k)码的n-重矢量空间中的一个k维子空间的基底可以有多个，因此可以有不同的生成矩阵G，但都产生相同的码组。 (n,k)码的n-重矢量空间中可以有多个k维子空间，产生不同的码组。（4）非系统汉明码：可以证明非系统汉明码的一致监督矩阵可以用一种简单方法得到。例如：(7,4)非系统汉明码的H为00

26、01111H=01100111010101其每一例都是二进制数的1，2，3 。利用HCT=0的基本关系，可以得到非系统形式的汉明码。通过H矩阵的列换位，可以将H变为系统码的形式。2.4 校验子与译码(Syndrome Matrix and Decoding)设发送码字为：C=(cn-1,cn-2,c0)；由于信道干扰产生差错，反映到接收码字上可以用一个二元矢量E表示，称为错误图样(error patterns)，E=(en-1,en-2,e0)其中：ei=1表明相应位有错，ei=0表明相应位无错。这时接收码字可以表示为，R=C+E=(cn-1+en-1,cn-2+en-2,c0+e0)译码器的

27、作用就是从接收码字R中得到发送码字的估计值，或者说从接收码字中确定错误图样E，然后由C=R-E得到发送码字的估计值，如果估计正确则译码正确，否则译码错误。定义S为校验子（伴随式）：S=RHT=CHT+EHT=EHT 或ST=HRT=HCT+HET=HET (本教材的表示方法)S=sr,sr-1,s1= sn-k,sn-k-1,s1可以看出：如果校验子矢量S0，接收码字一定有错误，如果校验子矢量S=0，译码器认为接收码字无错误。下面通过例子说明校验子的作用。(7,4)汉明码的基本监督矩阵H为已知，H=011110010110101101001由其得到的汉明码字如下表：00000000 00001

28、000100 10110001000 01111001100 11000010001 11101010101 01010011001 10011011101 00100100010 11001100110 01110101010 10111101110 00000110011 00101110111 10010111011 01011111111 111假如接收码字为R=可以看到：ST=HRT=0这时表明无差错；如果接收码字有一位差错，R=；即错误图样E=；接收码字的第三位错。这时校验子矢量为：ST=0=101111001110110100111010011001相当于：ST=0=001111

29、001110110100111010010000可见这时校验子ST不为0，译码器认为有错，且正好等于H的第三列，表明接收码字的第三位码元错了。这时判断发送码字位，译码正确。如果接收码字由两位差错，R=；即错误图样E=；接收码字的第三、四位错。这时校验子矢量为：ST=0=001111001010110101011010010100可见这时，校验子矢量不为0，但是如果这时接收机按原来的译码方法，将认为第7位出错。但如果接收机设计为检错系统，当校验子不为0，就认为有错。因为(7,4)汉明码的最小码距为3，其纠错检错能力是正确的。注意：这里告诉我们一个问题，纠错码的选用要小心，要根据信道条件来确定，如

30、果信道较差，而使用的纠错码能力不够，可能使译码错误反而增加，不仅错误的码元没有纠正，原来正确的码元还被错误的改变。错上加错。这种纠检错能力是由码组的最小码距决定的。可以验证：下面的(7,3)线性分组码的最小码距为4，可以纠一位错，同时检两位错，其基本监督矩阵为：H=10110001110100110000001100012.5 分组码的纠检错能力已知(n,k)分组码的最小码距，就可以知道其纠检错能力，例如，当最小码距为4时，可以纠一位错，同时检两位错，也可以用于检三位错，这与上一章介绍的结论是一样的。这里将进一步介绍有关性质。定理1：任一个(n,k)线性分组码，若要纠正t位错误，其充要条件是一

31、致监督矩阵H中的任何2t个列向量线性无关。或者说：若使一个(n,k)线性分组码的最小码距为d，其一致监督矩阵H中的任何d-1个列向量线性无关。或者说：若使一个(n,k)线性分组码的最小码距d，等于一致监督矩阵H中和为0的最小列数。推理1：改变一致监督矩阵的列的位置，不会影响列的相关性，也就不会影响其最小码距。但可能产生不同的码组，其纠错检错能力是相同的。根据这个推理，非系统汉明码的一致监督矩阵，经过列换位，可以得到系统汉明码的一致监督矩阵。例如：(7,4)非系统汉明码的监督矩阵位，0001111H=01100111010101将其进行列换位，可以得到：1101100H=111001001110

32、01由于前面4列的位置可以任意放置，编出的码字可以不同，但纠错能力是相同的。推理2：(n,k)线性分组码的最小码距dmin的最大值为n-k+1=r+1。 dminr+1这说明，要想提高纠检错能力，只能增加监督元的位数。例如：1100H=10101001这个监督矩阵的最小码距位dmin=4，因为，它由d-1=3个列向量线性无关，任何两个列或三个列相加都不为0。这时最小码距达到其最大值。实际上这是一个n=4, k=1, r=3的简单重复码，0 00001 1111它可以纠一位，同时检两位，或检4位。定理2：线性分组码的最小码距等于非0码字的最小码重。分组码的检错能力： 最小码距为dmin的分组码，

33、能检出所有dmin-1位或更少位错误的错误图样。 它不能检测出所有的dmin位错误，但可以检出一些（大部分）dmin位或更多位的码元错误。 事实上，(n,k)码能检出长度为n的2n-2k个错误图样。因为为禁用码字的个数，收到禁用码字就等于检出错码。令一个(n,k)线性分组码，Ai为码组中重量为i的码字的个数，码字集合（码组）的重量分布为A0,A1,An。这时码字在误码率（转移概率）为pe的BSC信道上的漏检概率为：其中pei(1-pe)n-i为错误图样(en,en-1,e1)中出现i个1，n-i个0的概率，Ai为此错误图样分布正好错成许用码字的数量。也就是错误图样等于许用码字的可能性就是漏检概

34、率。例如：(7,4)汉明码的重量分布为：A0=1,A1=A2=0,A3=A4=7,A5=A6=0,A7=1。Pu=7p3(1-p)4+7p4(1-p)3+p7 （根据公式A0一项没用，所以只有三项）当pe=10-2时，漏检概率为710-6。可见其实际检错能力远远高于最低检错能力。如果按照最小码距与检错能力的分析，其漏检概率为：但是对于短码可以这样计算，对于长码，这样计算是很困难的。分组码的纠错能力：当(n,k)分组码的最小码距为d=2t+1，它可以纠正t个或更少的错误。但实际上，纠错能力为t的分组码还可以纠正一些t+1位或更多位错误的错误图样（在后面的译码原理分析中可以看出），但较难精确计算，

35、其错误译码概率的上限为：2.6 标准阵与校验子译码(n,k)分组码的译码步骤为： 由接收码字R计算校验子ST=HRT。 若S=0，则译码器认为接收码字没错，否则有错，并由S计算错误图样E。 由错误图样进行译码，估计发送的码字C=R-E=R+E(模2减法等于加法)。其中最困难的是第二步，确定错误图样，即错误定位。这里介绍一个基本的译码方法，标准阵译码，即查表法译码。(n,k)分组码的2k个码字，是n维矢量空间Vn中的一个k维子空间，它在GF(2)上是一个子群。利用分元陪集的方法，可以利用该子空间的所有2k元素，生成n为空间中的所有2n个元素。产生的方法如图。码字(子群)陪集首C0C1C2C2k-

36、1禁用码字E1C1+ E1C2+ E1C2k-1+ E1E2C1+ E2C2+ E2C2k-1+ E2E2r-1C1+ E2r-1C2+ E2r-1C2k-1+ E2r-1 将2k个码字放在表中的第一行(第一陪集)，该子群的加法单位元C0=(000)放在第一列，作为第一个陪集的陪集首。 在所有禁用码字中，挑出一个汉明重量最小的作为第二行的第一列，作为第二个陪集的陪集首。将第一行的相应元素与其陪集首相加，构成第二个陪集。 依次进行，构成第2r个陪集。这个表称为标准译码表，简称标准阵。译码器按以下规则进行：收到码字R必然在这个表中，如果落在表中某一列，译码器就译成第一行的相应码字，由此可以看出：译

37、码表的第一列(陪集首)相当于错误图样，如果实际错误图样完全包含在表中的第一列中，译码器就不会产生错误译码，否则就可能产生错误译码。因此问题的关键是如何选择译码表的陪集首。我们知道，在随机信道中，错一个码元的概率大于错两个码元的概率，错两个码元的概率会大于错三个码元的概率。错误图样的汉明重量越小，其产生的可能性越大，应用译码表正确译码的可能性越大，错误译码概率越小。所以在设计译码表是应选择重量最轻的禁用码字作为陪集首。这一译码设计满足最小汉明距离译码准则，可以证明在BSC信道条件下，最小汉明距离译码等价于最大似然译码。例题：设一个(5,2)线性分组码，该码的最小汉明距离为dmin=3，可以纠正一

38、个码元的错误。其一致监督矩阵为：H=111001001011001其码字为C=(c4,c3,c2,c1,c0)，其信息元为(c4,c3)，监督元为(c2,c1,c0)。编码后得到的四个码字分别为：C0=(00000)C1=(01101)C2=(10111)C4=(11010)这时的标准译码表为许用码字00000011011011111010禁用码字10000111010011101010010000010111111100100010001001100111111000010011111010111000000010110010110110110001101110101001100100110

39、010111000111100例如接收码字R=(10101)，则由译码表可知，按最大似然译码准则译码器输出为(10111),在译码表中的第一列中可以看到，在禁用码字部分，前五行为只错一位的错误图样，即汉明重量为最小(dmin=1)的码字矢量。但由这五个汉明距离最小的码矢作为陪集首，并没有构成全部n维空间的码字矢量，所以这个译码表又选择了两个汉明距离较小的禁用码字作为陪集首。所以按这种译码表译码，不仅可以纠正所有单个错误，而且可以纠正两种类型的两位错误。可以得到错误译码概率为：PE=1-5pe(1-pe)4-2pe2(1-pe)3利用标准译码表，需要把2n个码字矢量存在译码器中，译码器的复杂性会

40、随n指数增加。当n较大时，这种方法不可能实现。解决的方法之一，错误图样与校验子矢量有一一对应的关系，根据这种关系，可以将译码表简化。例如(5,2)线性码的简化译码表为错误图样0000010000010000010000010000010001100110校验子000111101100010001011110当接收码字R=(10101)时，可以计算出校验子S=(010)，查表的错误图样的估计值为E=(00010)，由C=R+E可得译码器输出为C=(10111)。当n-k=r较小时(小于30)这种利用校验子表的方法是简单实用的方法。但n进一步大时查表方法就不太实用了，需要找到更简化的译码方法，或者

41、是具有简单译码方法的编码方法。2.7 分组码的其它概念（1）完备译码：从上面介绍的译码方法可以看出，汉明码的译码器接收到一个错误码字（禁用码字）后是利用比较这个错误码字与所有许用码字之间的汉明距离来实现译码的。判断与这个错误码字汉明距离最小的许用码字为发送码字。这种方法称为最小汉明距离译码。定义：(n,k)线性分组码的所有2n-k=2r个校验子（伴随式），在译码过程中都用来纠正所有t=(d-1)/2个随机错误，及大部分大于t个码元错误，则称这种译码方法为完备译码，否则称为非完备译码。如果译码器对于每个接收码字，都必须明确判决发送的对应码字，称为完备译码。相应的译码器称为完备译码器。例如：(3,

42、1)重复码译码，可以实现完备译码。如果译码器对于一些接收码字作出译码判决，而对于另外一些接收码字不能明确作出译码判决，称为不完备译码。例如：(4,1)重复码，当一个码字错两位时，译码器不能明确判决，无论怎样判决都会是很大的错判概率，只能是不完备译码。（2）限定距离译码：如果一个(n,k)线性分组码，能纠正t小于等于(d-1)/2个码元错误。在译码时只纠正tt个码元错误，而当错误码元个数大于t时，译码器只检出错误而不纠正错误。这种译码方法称为限定距离译码。例如当一个线性分组码的最小码距为5时，可以纠两位错误，如果译码器只纠1位错，而大于1位错时都检出，不纠正。就是限定距离译码。（3）汉明码H矩阵

43、的构造：汉明码是1950年由汉明提出的一种纠单个错误的线性分组码。它具有性能好，实现简单的特点，但相比之下纠错能力不是太强。在计算机内部及外存数据传输系统中较多应用。上面我们都是已知汉明码的基本监督矩阵或生成矩阵来分析编码和译码过程，那么，如何确定基本监督矩阵呢？我们看：根据已经给出的，可以经过数学工具证明的性质： 纠1位错误的码组，其最小码距至少为3； 若使最小码距为3，所构成的监督矩阵H中至少为任意两列线性无关，当然这也就意味着没有全0列，且每一列均不相同，也就是任何两列相加不等于0。分析：任何一个(n,k)线性分组码有2r=2n-k个监督元（校验位），对于2进制情况下，这r个监督元可以构

44、成2r个互不相同的r重列向量，其中有1个全0列向量，有2r-1个非全0列向量。那么，如果用这2r-1个非全0列向量作为H矩阵的全部列，此时的H矩阵就可以保证至少任何两列线性无关，就可以得到一个纠1位错的线性分组码，这个码就是汉明码。例如：前面介绍的(7,4)汉明码，可以用这种方法得到其监督矩阵H。由于列的排列可以不同（有一个定理支持），所以编出的汉明码可能不同，但纠错能力是一样的。可以是系统码，也可以是非系统码。但应当指出，根据汉明码的定义，狭义汉明码的监督位为正整数r3，码长和信息位长度分别为n=2r-1和k=n-r。码长必须为奇数，信息位是受到限制的。因此人们通过进一步研究，发现了一些由汉

45、明码引出的线性分组码，它们不属于狭义汉明码，但有时也称为汉明码，可以理解为广义汉明码。例如(7,3)汉明码，不是狭义汉明码，因为这时r=4，如果按照狭义汉明码的定义，码长应当为n=2r-1=15。（4）对偶码：从线性空间的零化空间的概念可以知道，如果一个矢量空间的有两个子空间，其中一个子空间的每一个矢量都与另一个子空间的每一个矢量正交，则称这两个子空间互为正交空间，或互为零化空间，也叫作对偶空间。由线性分组码的一致监督矩阵H和生成矩阵G的基本定义可知，生成矩阵的每一个行向量均为一个码字，因此有HGT=0，这说明H与G互为零化空间，而且分别为n维线性空间Vn的r维和k维子空间。如果H和G分别是码

46、字C的监督矩阵和生成矩阵，则将HD=G作为监督矩阵， GD=H作为生成矩阵，则可以产生一个(n,n-k)线性分组码CD，称C和CD互为对偶码。例如：(7,4)分组码的对偶码为一种(7,3)分组码。如果一种码的对偶码是它本身，则称此码为自对偶码。例如(2,1)重复码就是自对偶码。（5）缩短码：在实际使用中，为了得到希望的码长和信息位长度，有时将(n,k)汉明码的信息位减少若干个(i)码元，这时构成一种(n-i,k-i)分组码，这种码称为原码的缩短码。例如：(7,4)汉明码的缩短码为(6,3)码，其一致监督矩阵由原来的H将第一列去掉而得到。HS=111100011010101001（6）增余汉明码

47、：在汉明码的基础上，再增加一位监督元，它取为所有码元的模2加，这样使汉明码的最小码距dmin=4，可以在纠一位错的同时检两位错，这种线性分组码称为增余汉明码，也称为扩展汉明码。（其它线性分组码同样有扩展码。）例如：由(7,4)汉明码可以构成(8,4)增余汉明码，其一致监督矩阵为：1111000HS=011010010100101111111可以验证这种(8,4)增余汉明码可以纠一位错同时检两位错。（7）完备码：任何一个二元(n,k)线性分组码，有2k个码字，2n-k=2r个校验子矢量。若要纠正所有小于等于t个错误，就必须有大于等于t+1个校验子矢量与之对应。分别指出无错和哪t位错。即校验子的个

48、数必须满足：这个关系式称为汉明界。它是构造纠正t位错的(n,k)码的必要条件。如果一个(n,k)线性分组码使汉明界的等号成立，校验子的个数与所有可纠正的错误图样数正好相等，说明校验位得到了充分的利用，这种码称为完备码。（对于汉明码来说即称为狭义汉明码，否则称为广义汉明码）完备码的标准阵译码表中，能将重量小于等于t的所有错误图样选作陪集首，而且不用大于t的禁用码字作为陪集首。完备码是较少的，可以证明：狭义汉明码是完备码，(23,12)Golay码是完备码。如果译码表中除了使用重量小于等于t的所有错误图样选作陪集首外，还使用了一些重量等于t+1的错误图样作为陪集首，称为准完备码，这种码字是比较多的。如果将一个(n,k)分组码的全部纠错能力都用于纠错，称为完备译码。如果只用一部分用于纠错，另一部分用于检错或不使用，则称为非完备译码。第3章 循环码循环码是线性分组码的最重要的一类码，它的结构完全建立在有限域多项式的基础上。它具有两个基本特点：一是编码电路与译码电路非常简单，易于实现；二是其代数性质好编码译码分析方便，有一些好的译码方法。3.1 循环码的描述循环码定义：一个(n,k)线性分组码C，如果码组中的一个码字的循环移位也是这个码组中的一个码字，则称C为循环码。C(0)=cn-1,cn-2,c1,c0 CC(1)=cn-2,cn-3,c0,cn