1、第10章信道编码 10.1 引言引言 10.2 信道编码的基本概念信道编码的基本概念 10.3 常用检错码常用检错码 10.4 线性分组码线性分组码 10.5 循环码循环码 10.6 卷积码卷积码 10.7 交织码与级联码交织码与级联码 10.8 m序列序列 本章小结本章小结 习题习题 第第10章信道编码章信道编码第10章信道编码 10.1 引引 言言数字信号在信道的传输过程中，由于实际信道的传输特性不理想以及存在噪声及干扰，在接收端往往会产生误码。为了提高数字通信的可靠性，可合理设计系统的发送和接收滤波器，采用均衡技术，消除数字系统中码间干扰的影响，还可选择合适的调制解调技术，增加发射机功率
2、，采用先进的天线技术等。若数字系统的误码仍不能满足要求，则可以采用信道编码技术，进一步降低误码率。采用信道编码技术的数字通信系统如图10.1.1所示。第10章信道编码 图10.1.1 采用信道编码技术的数字通信系统第10章信道编码 信道编码是按一定的规律给信息增加冗余度，使不带规律的原始数字信息变换为具有一定规律的数字信息。信道译码则是利用这些规律性来鉴别是否发生错误，进而纠正错误。具体地说，信道编码就是在发送端被传输的信息码元序列中，以一定的编码规则附加一些监督码元，接收端利用该规则进行译码，译码的结果可以发现错误或纠正错误。信道编码是用增加数码，利用冗余来提高抗干扰能力的。亦是以降低信息传
3、输速率为代价来减少错误的，或者说是用削弱有效性来增强其可靠性的。第10章信道编码 信道编码不同于信源编码。信源编码是为提高数字信号有效性而采取的一种编码技术，其宗旨是尽可能压缩冗余度。它可降低数码率，压缩传输频带。而信道编码的目的在于提高数字通信的可靠性。需要强调的是：信源编码减少了冗余度，而信道编码增加了冗余度，但这两种冗余度是不同的。信源编码减少的冗余度是随机的、无规律的，即使不减少它，它也不能用来检错或纠错；信道编码增加的冗余度则是特定的、有规律的、有用的，可用它来检错和纠错。本章主要介绍常用的信道编码技术，主要内容有常用检错码、常用纠错码的编码和译码原理，最后还将介绍m序列及其应用。第
4、10章信道编码 10.2 信道编码的基本概念信道编码的基本概念10.2.1 信道编码的检错、纠错原理信道编码的检错、纠错原理信道编码的基本思想是在被传输信息中附加一些冗余码元，我们称这些冗余码元为监督码元。监督码元和信息码元有一定的关系(规律)，接收端利用监督码元和信息码元的这种关系加以校验，以检测和纠正错误。这种纠、检错能力是用编码的冗余度换取的。设发送端发送A和B两个消息，要表示A、B两种消息只需要一位编码，即用“1”表示A，用“0”表示B。这种编码无冗余度，效率最高，但同时它也无抗干扰能力。若在传输过程中发生误码，即“1”错成“0”或“0”错成“1”，收端无法判断收到的码元是否发生错误，
5、因为“1”和“0”都是发送端可能发送的码元，所以这种编码方法无纠、检错能力。第10章信道编码 若增加一位监督码元，增加的监督码元与信息码元相同，即用“11”表示消息A，用“00”表示信息B。如传输过程中发生1位错误，则“11”、“00”变成“10”或“01”。此时接收端能发现这种错误，因为发送端不可能发送“01”或“10”。但它不能纠错，因为“11”和“00”出现1位错误时都可变成“10”或“01”。所以，当接收端收到“10”或“01”时，它无法确定发送端发送的是“11”还是“00”。第10章信道编码 若增加二位监督码元，监督码元仍和信息码元相同，即用“111”表示消息A，用“000”表示消息
6、B。则若传输过程中出现1位错误，可以纠正。如发送端发送“111”，传输中出现1位错误，使得接收端收到“110”。此时显然能发现这个错误，因为发送端只可能发送“111”或“000”。再根据“110”与“111”及“000”的相似程度，将“110”翻译为“111”，这时“110”中的1位错误得到了纠正。如果“111”在传输过程中出现2位错误，接收端收到“100”、“010”或“001”。因为它们即不代表消息A，也不代表消息B，所以接收端能发现出了错误，但无法纠正这2位错误。如果硬要纠错，会将“100”、“010”或“001”翻译成“000”，显然纠错没有成功。第10章信道编码 10.2.2 码长、
7、码重、码距和编码效率码长、码重、码距和编码效率原始数字信息是分组传输的，以二进制编码为例，每k个二进制位为一组，称为信息组，经信道编码后转换为每n个二进制位为一组的码字(也称为码组)，码字中的二进制位称为码元。码字中监督码元数为n-k。一个码字中码元的个数称为码字的长度，简称为码长，通常用n表示。如码字“11011”，码长n=5。码字中“1”码元的数目称为码字的重量，简称为码重，通常用W表示。如码字“11011”，码重W=4。第10章信道编码 两个等长码字之间对应码元不同的数目称为这两个码字的汉明距离，简称为码距，通常用d表示。如码字“11011”和“00101”之间有四个对应码元不同，故码距
8、d=4。由于两个码字模2相加，对应码元不同的位必为1，对应码元相同的位必为0，所以两个码字模2相加得到的新码组的重量就是这两个码字之间的距离。如：1101100101=11110，11110的码重为4，与上述所得到的码距相同。码字集合中两两码字之间距离的最小值称为码的最小距离，通常用d0表示，它决定了一个码的纠、检错能力，因此是极重要的参数。第10章信道编码 信息码元数与码长之比定义为编码效率，通常用表示，的表达式为 (10-2-1)编码效率是衡量码性能的又一个重要参数。编码效果越高，传信率越高，但此时纠、检错能力要降低，当=1时就没有纠、检错能力了。nk第10章信道编码 10.2.3 最小码
9、距最小码距d0与码的纠、检错能力之间的关系与码的纠、检错能力之间的关系最小码距d0决定了码的纠、检错能力。它们之间的关系如下：(1)检测e个错误，则要求最小码距为d0e+1 (10-2-2)(2)纠正t个错误，则要求最小码距为d02t+1(10-2-3)(3)纠正t个错误的同时检测e(et)个错误，则要求最小码距为d0t+e+1(10-2-4)第10章信道编码 下面举例说明给定码距时，如何根据式(10-2-2)、(10-2-3)及(10-2-4)来确定码的纠、检错能力。仍以发送端发送A、B两种消息为例，信源编码用“1”表示消息A，用“0”表示消息B。信道编码器每收到一个“1”，输出一个码字“1
10、111”；每收到一个“0”，输出一个码字“0000”。显然，每个码字中一个码元是信息，另三个码元是监督元，这个码共有两个码字，这两个码字间的距离就是码的最小距离，所以这个码的最小码距d0=4。第10章信道编码 当此码只用于检错目的时，那么根据式(10-2-2)，d03+1，所以此码最多可检测出3个错误。如“1111”中发生3位错误变成“0001”、“0010”、“0100”、或“1000”，由于发送码字中无这四个码字，所以接收端能发现错误。但它无法发现大于3个的错误，如发生4个错误时，发送“1111”时会收到“0000”，由于“0000”也是可能发送的码字，接收端收到“0000”时认为没有错误
11、，发送的是消息B。第10章信道编码 当此码只用于纠错时，那么根据式(10-2-3)，d021+1，所以此码只能纠正1位错误。如发送端发送“1111”，传输中发生一位错误，错成“1110”、“1101”、“1011”或“0111”，由于这些码字与“1111”的距离小，接收端将它们还原为“1111”，这样，接收码字中的1位错误得到纠正。如果传输过程中发生2位错误，如“1111”错成“1100”，接收端只知道有错，但无法知道是“1111”错成“1100”还是“0000”错成“1100”，所以无法纠正错误。第10章信道编码 当此码用于同时进行纠错和检错的系统时，根据式(10-2-4)，d01+2+1，
12、所以此码纠1位错误的同时能检测2位错误。若此码中发生1位错误，如“1111”错成“1110”，接收端将纠正成“1111”，这1位错误得到纠正。若码中发生2位错误，如“1111”错成“1100”，接收端能发现错误，但无法纠正。若码中发生3位错误，如“1111”错成“0001”，由于系统有纠错功能，因此这种情况发生时，系统认为“0001”中有1位错误，将“0001”自动纠成“0000”，所以系统无法发现3位错误。可见，码距为4的码用于纠错的同时检错，发现不了3位错误，与只用于检错这种情况是不一样的，这一点请读者仔细体会。第10章信道编码 10.2.4 信道编码的分类信道编码的分类信道编码有许多分类
13、方法。(1)根据信息码元和附加的监督码元之间的关系可以分为线性码和非线性码。若监督码元与信息码元之间的关系可用线性方程来表示，即监督码元是信息码元的线性组合，则称为线性码。反之，若两者不存在线性关系，则称为非线性码。(2)根据上述关系涉及的范围来分，可分为分组码及卷积码。分组码的各码元仅与本组的信息码元有关；卷积码中的码元不仅与本组信息码元有关，而且还与前面若干组的信息码元有关，因此卷积码又称为连环码。线性分组码中，把具有循环移位特性的码称为循环码，否则称为非循环码。(3)根据码字中信息码元在编码前后是否相同可分为系统码和非系统码。编码前后信息码元保持原样不变的称为系统码，反之称为非系统码。第
14、10章信道编码(4)根据码的用途可分为检错码和纠错码。以检测(发现)错误为目的的码称为检错码。以纠正错误为目的的码称为纠错码。纠错码一定能检错，但检错码不一定能纠错。通常将纠、检错码统称为纠错码。(5)根据纠(检)错误的类型可分为纠(检)随机错误码、纠(检)突发错误码和既能纠(检)随机错误同时又能纠(检)突发错误码。(6)根据码元取值的进制可分为二进制码和多进制码。本章仅介绍二进制码。第10章信道编码 10.2.5 差错控制方式差错控制方式常用的差错控制方式主要有三种：前向纠错(FEC)、检错重发(ARQ)和混合纠错(HEC)。它们所对应的差错控制系统如图10.2.1所示。第10章信道编码 图
15、10.2.1 三种主要的差错控制方式第10章信道编码 前向纠错记作FEC，又称自动纠错。在这种系统中，发端发送纠错码，收端译码器自动发现并纠正错误。ARQ的特点是不需要反向信道，实时性好，ARQ适合于要求实时传输信号的系统，但编码、译码电路相对较复杂。检错重发记作ARQ，又叫自动请求重发。在这种系统中，发端发送检错码，通过正向信道送到收端，收端译码器检测收到的码字中有无错误。如果接收码字中无错误，则向发送端发送确认信号ACK，告诉发送端此码字已正确接收；如果收到的码字中有错误，收端不向发送端发送确认信号ACK，发送端等待一段时间后再次发送此码字，一直到正确接收为止。ARQ的特点是需要反向信道，
16、编、译码设备简单。ARQ适合于不要求实时传输但要求误码率很低的数据传输系统。第10章信道编码 混合纠错记作HEC，是FEC与ARQ的混合。发端发送纠、检错码(纠错的同时检错)，通过正向信道送到收端，收端对错误能纠正的就自动纠正，纠正不了时就等待发送端重发。HEC同时具有FEC的高传输效率，ARQ的低误码率及编码、译码设备简单等优点。但HEC需要反向信道，实时性差，所以不适合于实时传输信号。第10章信道编码 10.3 常用检错码常用检错码10.3.1 奇偶监督码奇偶监督码奇偶监督码是一种最简单也是最基本的检错码，又称为奇偶校验码。其编码方法是把信息码元先分组，然后在每组的最后加1位监督码元，使该
17、码字中“1”的数目为奇数或偶数，奇数时称为奇监督码，偶数时称为偶监督码。信息码元长度为3时的奇监督码和偶监督码如表10-3-1所示。第10章信道编码 第10章信道编码 奇偶监督码的译码也很简单。译码器检查接收码字中“1”的个数是否符合编码时的规律。如奇监督码，接收码字中“1”的个数为奇数，如果“1”的个数符合编码时的规律，则译码器认为接收码字没有错误；如“1”的个数为偶数，不符合编码时的规律，则译码器认为接收码字中有错误。不难看出，这种奇偶监督码只能发现单个和奇数个错误，而不能检测出偶数个错误，因此它的检错能力不高。但是由于该码的编、译码方法简单，而且在很多实际系统中，码字中发生单个错误的可能
18、性比发生多个错误的可能性大得多，所以奇偶监督码得到广泛应用。第10章信道编码 10.3.2 行列奇偶监督码行列奇偶监督码行列奇偶监督码又称二维奇偶监督码或矩阵码。编码时首先将信息排成一个矩阵，然后对每一行、每一列分别进行奇或偶监督编码。编码完成后可以逐行传输，也可以逐列传输。译码时分别检查各行、各列的奇偶监督关系，判断是否有错。一个行列监督码字的例子如下所示：监督码元(奇监督)11 0 0 1 00 1 0 1 0 10 0 0 0 1 01 1 1 1 1 0监督码元(奇监督)1 0 0 1 0 0第10章信道编码 行列监督码字的右下角这个码元可以对行进行监督，也可以对列进行监督，甚至可以对
19、整个码字进行监督，本例中此码元对列进行奇监督。行列监督码具有较强的检测随机错误的能力，能发现1、2、3及其它奇数个错误，也能发现大部分偶数个错误，但分布在矩形的四个项点上的偶数个错误无法发现。这种码还能发现长度不大于行数或列数的突发错误。这种码也能纠正单个错误或仅在一行中的奇数个错误，因为这些错误的位置是可以由行、列监督而确定的。第10章信道编码 10.3.3 恒比码恒比码恒比码又称为等重码或等比码。这种码的码字中“1”和“0”的位数保持恒定的比例。由于每个码字的长度是相同的，若“1”、“0”恒比，则码字必等重。这种码在收端进行检测时，只要检测码字中“1”的个数是否与规定的相同，就可判别有无错
20、误。我们国家邮电部门采用的五单位数字保护电码，是一种“1”、“0”个数之比为3 2的恒比码。此码有10个码字，恰好可用来表示10个阿拉伯数字，如表10-3-2所示。第10章信道编码 第10章信道编码 10.4 线性分组码线性分组码10.4.1 线性分组码的特点线性分组码的特点既是线性码又是分组码的码称为线性分组码。由码的分类我们知道，监督码元仅与本组信息码元有关的码称为分组码，监督码元与信息码元之间的关系可以用线性方程表示的码称为线性码。所以，在线性分组码中，一个码字中的监督码元只与本码字中的信息码元有关，而且这种关系可以用线性方程来表示。如(7，3)分组码，码字长度为7，一个码字内信息码元数
21、为3，监督码元数为4。码字用A=a6a5a4a3a2a1a0表示，前三位表示信息码元，后四位表示监督码元，监督码元与信息码元之间的关系可用如下方程组表示：第10章信道编码 4505614562463aaaaaaaaaaaaa(10-4-1)第10章信道编码 显然，当三位信息码元a6a5a4给定时，根据式(10-4-1)即可计算出四位监督码元a3a2a1a0，然后由这7位构成一个码字输出。所以编码器的工作就是根据收到的信息码元，按编码规则计算监督码元，然后将由信息码元和监督码元构成的码字输出。由编码规则(10-4-1)得到的(7，3)线性分组码的全部码字列于表10-4-1中。读者可根据式(10-
22、4-1)自行计算监督码元加以验证。需要说明的是，式(10-4-1)中的“+”是模2加，以后不再另行说明。第10章信道编码 线性分组码有一个重要特点：封闭性。利用这一特点可方便地求出线性分组码的最小码距，进而可确定线性分组码的纠、检错能力。线性分组码的封闭性是指：码字集中任意两个码字对应位模2加后，得到的码字仍然是该码字集中的一个码字。如表10-4-1中，码字“0011101”和码字“1110100”对应位模2加得“1101001”，“1101001”是表10-4-1中的6号码字。由于两个码字模2加所得的码字的重量等于这两个码字的距离，故(n,k)线性分组码中两个码字之间的码距一定等于该分组码中
23、某一非全0码字的重量。因此，线性分组码的最小码距必等于码字集中非全0码字的最小重量。线性分组码中一定有全0码字，设全0码字为A0，则线性分组码(n,k)的最小码距为d0=Wmin(Ai)Ai(n,k),i0 (10-4-2)第10章信道编码 第10章信道编码 一个码字集的最小码距决定了这个码的纠、检错能力，线性分组码的封闭性给码距的求解带来了便利。利用式(10-4-2)可方便地求出上述(7，3)分组码的码距，具体方法是：全0码字除外，求出余下7个码字的重量，因为7个码字的重量都等于4，所以最小重量等于4，最小码距d0=4。此(7，3)分组码用于检错，最多能检3个错误，用于纠错，则最多能纠1个错
24、误。对线性分组有了一般性了解后，下面我们系统讨论线性分组码的编码、译码方法。第10章信道编码 10.4.2 线性分组码的编码线性分组码的编码下面我们仍以上述(7，3)线性分组码为例，用矩阵理论来讨论线性分组码的编码过程，并得到两个重要的矩阵：生成矩阵G和监督矩阵H。式(10-4-1)所示监督方程组可改写为(10-4-3)00000451562456346aaaaaaaaaaaaa第10章信道编码 写成矩阵形式有简记为 (10-4-4)或(10-4-5)0000 10001100100011001011100011010123456aaaaaaaTTAH00THA第10章信道编码 其中，AT是码
25、字A的转置，0T是0=0 0 0 0的转置，HT是H的转置，H为 (10-4-6)式(10-4-6)称为此(7,3)分组码的监督矩阵。(n,k)线性分组码的监督矩阵H由r行n列组成，且这r行是线性无关的。系统码的监督矩阵可写成如下形式H=PIr1000110010001100101110001101H第10章信道编码 这样的监督矩阵称为典型监督矩阵。其中Ir为rr的单位矩阵。P是rk的矩阵。对式(10-4-6)有1000010000100001 110011111101rIP第10章信道编码 若信息码元已知，可通过以下矩阵运算求监督元：(10-4-7)或由信息码元和监督码元即可构成码字A=a6
26、a5a4a3 a2a1a0。读者可根据这种方法求出此(7，3)码的全部码字，并与表10-4-1所列码字进行比较。4560123aaaPaaaa TPaaaaaaa4560123第10章信道编码 还可以用生成矩阵来求码字。系统码(n,k)的生成矩阵为G=IkPT(10-4-8)G称为典型生成矩阵。其中，Ik是kk的单位矩阵。显然，生成矩阵G可以由监督矩阵H确定。因此，与式(10-4-6)相对应的生成矩阵为(10-4-9)101110011100100111001G第10章信道编码 当信息给定时，由生成矩阵求码字的方法是A=MG (10-4-10)其中，M为信息矩阵。如M=0 0 1时，通过生成矩
27、阵G生成的码字为改变信息矩阵M可求出(7，3)码的全部码字，它们与表10-4-1所列码字完全一样。1011100101110011100100111001001A第10章信道编码 例例10.4.1 汉明码是一种高效率的纠单个错误的线性分组码。其特点是最小码距d0=3，码长n与监督码元个数r满足关系式n=2r-1(10-4-11)其中，r3。所以有(7，4)、(15，11)、(31，26)等汉明码。设(7，4)汉明码的3个监督码元与4个信息码元之间的关系如下(10-4-12)试求(7，4)汉明码的全部码字。000034613562456aaaaaaaaaaaa第10章信道编码 解解 我们用式(1
28、0-4-10)来求码字。首先求出(7，4)汉明码的典型生成矩阵G。由式(10-4-12)给定的监督关系求出监督矩阵如下所以3100110101010110010111PIH110110110111P第10章信道编码 根据式(10-4-8)得到典型生成矩阵G为根据式(10-4-10)，当信息矩阵M=0 0 0 0时，码字为1101000101010001100101110001G000000011010001010100011001011100010000第10章信道编码 当信息矩阵M=0 0 0 1时，码字为按此方法求出(7，4)汉明码的所有16个码字并列于表10-4-2中。110100011
29、010001010100011001011100011000第10章信道编码 第10章信道编码 根据表10-4-2，除全“0”码字以外，重量最轻的码字的重量为3，所以(7，4)汉明码的最小码距d0=3。(7，4)汉明码能纠1位错误，能检2位错误。例例10.4.2 重复码是最简单的一类线性分组码。具体地说，重复码是将1位信息编码成n位都相同的码字，用(n,1)表示。由于这类码字中只有1位信息，所有总共只有2个码字，一个是全“0”码字，另一个是全“1”码字。如(5，1)重复码的两个码字为：“00000”和“11111”。试求出(5，1)重复码的监督矩阵H和生成矩阵G。第10章信道编码 解解 (5，
30、1)重复码的码字长度为5，其中1位信息码元，4位监督码元，4位监督码元都与信息码元相同，所以监督关系(方程组)如下(10-4-13)40414243aaaaaaaa第10章信道编码 改写式(10-4-13)所示的监督方程组得(10-4-14)000004142434aaaaaaaa第10章信道编码 将式(10-4-14)用矩阵表示为00001000101001001010001101234aaaaa第10章信道编码 所以，(5，1)重复码的监督矩阵为其中410001010010010100011PIH1111P第10章信道编码 因为典型生成矩阵G为G=PTIk所以(5，1)重复码的典型生成矩阵
31、为 111111IPIPGTkT第10章信道编码 例例10.4.3 奇、偶监督码是另一类简单的线性分组码，用(n,n-1)表示，长度为n的码字中信息码元为n-1个，只有1位监督码元。求长度为4的偶监督码的监督矩阵H和生成矩阵G。解解 设长度为4的偶监督码的码字为A=a3a2a1a0，其中前3位表示信息码元，最后1位表示监督码元。由于偶监督码要求码字中“1”的码元数为偶数，即各码元模2加为0，所以(4，3)偶监督码中监督码元与信息码元满足如下关系00123aaaa第10章信道编码 此方程用矩阵表示为所以监督矩阵为H=1 1 1 1=PI1其中P=1 1 1 0 11110123aaaa第10章信
32、道编码 得典型生成矩阵为利用生成矩阵G及式(10-4-10)可求出全部8个码字，所求得码字与表10-3-1中所列的偶监督码码字完全相同，读者可自行加以验证。1100101010013TPIG第10章信道编码 10.4.3 线性分组码的译码线性分组码的译码设发送端发送码字A=an-1an-2a1a0，此码字在传输中可能由于干扰引入错误，故接收码字一般说来与A不一定相同。设接收码字B=bn-1bn-2b1b0，则发送码字和接收码字之差为B-A=E，或写成B=A+E。E是码字A在传输中产生的错码矩阵，E=en-1en-2e1e0。如果A在传输过程中第i位发生错误，则ei=1，反之，则ei=0。例如，
33、若发送码字A=1001110，接收码字B=1001100，则错码矩阵E=0000010。错码矩阵通常称为错误图样。第10章信道编码 译码器的任务就是判别接收码字B中是否有错，如果有错，则设法确定错误位置并加以纠正，以恢复发送码字A。由式(10-4-5)可知，码字A与监督矩阵H有如下约束关系AHT=0当B=A时，有BHT=00为1行r列的全“0”矩阵。第10章信道编码 当BA时，说明传输过程中发生了错误，此时令矩阵S=BHT=EHT (10-4-15)称S为伴随式，伴随式S是个1行r列的矩阵，r是线性分组码中监督码元的个数。由上面的分析可知，当接收码字无错误时，S=0；当接收码字有错误时，S0。
34、又由式(10-4-15)可知，S与错误图样有对应关系，与发送码字无关。故S能确定传输中是否发生了错误及错误的位置。0)(TTTTTHEHEHAHEAHB第10章信道编码 下面以上一节中所列举的(7，3)码为例，具体说明线性分组码的译码过程。(1)首先根据式(10-4-15)求出错误图样E与伴随式S之间的关系，并把它保存在译码器中。由(7，3)线性分组码编码一节可知，此码最小码距d0=4，能纠正码字中任意一位错误，码长为7的码字中错1位的情况有7种，即码字中错1位的错误图样有7种，如码字第一位发生错误，错误图样为E=1000000第10章信道编码 由式(10-4-15)求得伴随式为由上式可看出，
35、伴随式S6等于HT中的第一行。1110100001000010000110111110011110000006THES第10章信道编码 如码字在传输过程中第二位发生错误，错误图样为E=0 1 0 0 0 0 0则伴随式为即伴随式S5等于HT中的第二行。0111100001000010000110111110011101000005THES第10章信道编码 由此可求出错1位的7种错误图样所对应的伴随式，它们刚好对应HT中的7行。错误图样与伴随式之间的对应关系如表10-4-3所示。第10章信道编码 第10章信道编码(2)当译码器工作时，首先计算接收码字B的伴随式S，然后查表10-4-3得错误图样E
36、。如接收码字为B=1100111，用式(10-4-15)求出其伴随式为根据此伴随式，查表10-4-3得错误图样E=1000000，可知接收码字B中第一位有错误。0111010000100001000011011111001111100111THBS第10章信道编码(3)最后用错误图样纠正接收码字中的错误。根据接收码字B及错误图样E即可得到发送码字A，方法是A=B+E=1 1 0 0 1 1 1+1 0 0 0 0 0 0=0100111如果此(7，3)分组码用于检错，码距d0=4的(7，3)分组码最多能检3位错误。检错译码的方法是：计算接收码字的伴随式S，如果S=0，译码器认为接收码字中没有错
37、误；如果S0，则译码器认为接收码字中有错误，译码器会以某种方式将此信息反馈给发送端，发送端将重发此码字。第10章信道编码 最后还要指出，若接收码字中错误位数超过1时，S也有可能正好与发生1位错误时的某个伴随式相同，这样，经纠错后反而“越纠越错”。如发送码字A=0100111，传输过程中发生3位错误，设错误图样E=0000111，此时接收码字B=0100000。根据上述所介绍的纠错译码方法，计算出此接收码字的伴随式S=0111，查表10-4-3得错误图样E=0100000，译码器认为第二位发生了错误，将第二位纠正，得纠正后的码字为0000000。由此可见，本来接收码字中有3位错误，但通过纠错译码
38、后，错误不但没有减少反而增加了1位，这就所谓的“越纠越错”。第10章信道编码 在传输过程中，也会发生发送码字的某几位发生错误后成为另一发送码字的情况，这种情况收端也无法检测，这种错误我们称之为不可检测的错误。从统计观点来看，这种情况出现的概率很小。如发送码字A=0100111，传输过程中发生4位错误变成B=0111010，计算其伴随式发现S=0，译码器认为没错。事实上，接收到的B是另一个发送码字。不管是这种情况还是上述的“越纠越错”，发生原因都是因为码字中的错误个数超出了码的纠错能力。所以在设计信道编码方案时，应充分考虑信道发生错误的情况。第10章信道编码 例例10.4.4 (例10.4.1续
39、)(7，4)汉明码的译码。解解例10.4.1中(7，4)汉明码的监督矩阵为由例10.4.1已知，(7，4)汉明码的码距d0=3，能纠正1个错误。码长为7的码字错1位的错误图样有7种，利用式(10-4-15)可求出这7种错误图样所对应的伴随式。对应关系如表10-4-4所示。100110101010110010111H第10章信道编码 第10章信道编码 由表10-4-4可知，HT中的每一行都是一个伴随式。由于(7，4)汉明码中监督码元的个数为3，所以伴随式是个1行3列的矩阵。三位二进制不同的组合共有8种，除全“0”组合外还有7种，这7种组合刚好与错1位的7种错误图样一一对应。所以，码长为7的码字中
40、至少加入3位监督码元才能纠单个错误。(7，4)汉明码在7位码字中只有3位监督码元，因此，(7，4)码是一种纠单个错误的高效的线性分组码。第10章信道编码 7种错误图样与7个伴随式之间的关系只要一一对应就不会影响码的纠、检错能力。所以，我们也可改变表10-4-4的对应关系，进而得到不同于例10.4.1中的HT，即得到不同于例10.4.1中(7，4)汉明码的监督关系。如改变表10-4-4中的对应关系得到100010001111110011101TH第10章信道编码 所以，监督矩阵为100110101011100011011H第10章信道编码 由 ,得到另一个(7，4)汉明码的监督关系方程组为000
41、0123456aaaaaaaH000034613452356aaaaaaaaaaaa第10章信道编码 按此方法还可构造出不同的(7，4)汉明码的监督关系。我们知道，监督关系不同，码字集中的码字也会不同，但按这种方法构造的所有(7，4)汉明码具有相同的性能，即编码效率相同，纠、检错能力相同。第10章信道编码 例例10.4.5 试验证(5，1)重复码最多能纠2位错误。解解 最多能纠2位错误的码必须能纠任意位置上的单个错误及任意位置上的2个错误。长度为5的码字发生单个错误的错误图样有种，分别是515C00001 0001000100 01000 1000054321EEEEE第10章信道编码 任意错
42、2位的错误图样有种，它们是1024525C0001100101 00110 0100101010 01100 1000110010 10100 110001514131211109876EEEEEEEEEE第10章信道编码 由例10.4.2 可知(5,1)重复码的监督矩阵为10001010010010100011H第10章信道编码 根据式(10-4-15)求出这15个错误图样所对应的伴随式，并将它们列于表10-4-5中。由表10-4-5可看到，每个错误图样对应不同的伴随式，所以当码字中错1位或2位时，根据伴随式即可确定错误图样，以此可纠正码字中的1位或2位错误。由该表还可看出，伴随式由4位二进
43、制组成，除全“0”外的所有4位二进制组合全在表10-4-5中了，如果码字中发生3位或4位错误，其伴随式一定是该表中的一个，译码器会按单个错误或2个错来纠错，导致“越纠越错”；如果码字中发生5位错误，如码字11111错成了00000，此时伴随式为0000，译码器无法发现此错误。所以，(5，1)重复码最多能纠2位错误。第10章信道编码 第10章信道编码 10.5 循循 环环 码码10.5.1 循环码的特点循环码的特点若线性分组码的任一码字循环移位所得的码字仍在该码字集中，则此线性分组码称为循环码。很明显，(n,1)重复码是一个循环码。表10-5-1中的(7，3)码及表10-5-2中的(6，3)码也
44、都是循环码，其循环特性分别如图10.5.1所示。循环圈上的数字为码字的序号。由图10.5.1可见，同一循环圈上的各码字重量是相等的。全“0”、全“1”码字分别自成循环圈。循环码的循环圈数目大于等于2。第10章信道编码 第10章信道编码 第10章信道编码 在讨论循环码时，常用代数多项式来表示循环码的码字，这种多项式称为码多项式。对于(n,k)循环码的码字，其码多项式的一般形式为 (10-5-1)码字中各位码元的数值是其码多项式中相应各项的系数值(0或1)。码字A=1001110的码多项式012211.)(axaxaxaxAnnnnxxxxxA236)(第10章信道编码 10.5.2 循环码的编码
45、循环码的编码循环码完全由其码字长度n及生成多项式g(x)所决定。循环码中，除全“0”码字外，次数最低的码字多项式称为生成多项式。如(7，3)循环码中，生成多项式为g(x)=x4+x3+x2+1 (码字0011101的码多项式)。可以证明，(n,k)循环码的生成多项式g(x)具有如下三个特性：(1)g(x)是xn+1的一个因子。(2)g(x)是r=n-k次多项式。(3)g(x)的常数项为1。第10章信道编码 为了寻找生成多项式，首先应对xn+1进行因式分解，并选择满足上述(2)、(3)两个特点的因式或因式的乘积。如寻找(7，3)循环码，首先对x7+1进行因式分解，有x7+1=(x+1)(x3+x
46、+1)(x3+x2+1)x+1和x3+x+1乘积为x4+x3+x2+1，此乘积可作为(7，3)循环码的生成多项式，因为它满足生成多项式的三个条件，所以(7，3)循环码的一个生成多项式为g(x)=x4+x3+x2+1此生成多项式可生成表10-5-1中所列的循环码。显然，x+1和x3+x2+1的乘积x4+x2+x+1也满足上述生成多项式的三个条件，所以x4+x2+x+1是(7，3)循环码的另一个生成多项式。第10章信道编码 用多项式来表示生成矩阵的各行，则生成矩阵可写成 (10-5-2)()(.)()()(21xgxxgxgxxgxxGkk第10章信道编码 例如表10-5-1中(7，3)循环码，n
47、=7，k=3，r=4，其生成多项式及生成矩阵分别为1)(234xxxxg1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG第10章信道编码 即(10-5-3)101110001011100010111G第10章信道编码 有了生成多项式及生成矩阵后，就可求出循环码的所有码字了。求循环码码字的方法有三种：(1)循环码的码字多项式都是生成多项式g(x)的倍式，设信息矩阵为M=mk-1 mk-2 m1 m0则(n,k)循环码的所有码字由下式生成A(x)=M(x)g(x)(10-5-4)其中，M(x)=mk-1xk-1+mk-2xk-2+m1x+m0为信息多项式。按此方法
48、可产生循环码的所有码字，但这种方法产生的码不是系统码。如信息M=110，则信息多项式为M(x)=x2+x第10章信道编码 设生成多项式为g(x)=x4+x3+x2+1由式(10-5-4)可得码字多项式为A(x)=(x2+x)(x4+x3+x2+1)=x6+x3+x2+x所以码字为1001110，显然它不是系统码的码字。第10章信道编码(2)用生成多项式也可产生系统码的码字，系统循环码的码多项式可表示为A(x)=xn-kM(x)+xn-kM(x)(10-5-5)其中，前一部分代表信息码元组，后一部分用 表示，是xn-kM(x)被g(x)除得的余式，它代表监督码元组。如(7，3)循环码，设信息M=
49、110，则M(x)=x2+xxn-kM(x)=x4M(x)=x6+x5第10章信道编码 当g(x)=x4+x3+x2+1时，求得余式为xn-kM(x)=x4M(x)=x6+x5=x3+1根据式(10-5-5)得码多项式为A(x)=x6+x5+x3+1此码多项式对应的码字为“1101001”，是系统码的码字，前三位是信息码元，后四位是监督码元。第10章信道编码 根据式(10-5-5)，利用多项式除法电路求xn-kM(x)除以g(x)的余式，即可产生(n,k)系统循环码。g(x)=x4+x3+x2+1时，(7，3)循环码的编码器如图10.5.2所示。第10章信道编码 图10.5.2 (7，3)循环
50、码编码器第10章信道编码 D0D1D2D3是四级移位寄存器，反馈线的连接与g(x)的非0系数相对应。编码时，首先将四级移存器清零。三位信息码元输入时，门1断开，门2接通，直接输出信息元。第3个移位脉冲后，D0D1D2D3中数据为除法余数，就是输入信息的监督码元。第47次移位时，门2断开，门1接通，输出监督元。当一个码字输出完毕就将移位寄存器清零，等待下一组信息输入后重新编码。设输入的信息码元为110，图10.5.2中各器件及端点状态变化情况如表10-5-3所示。该编码器输入不同信息组时的码字如表10-5-1所示。第10章信道编码 第10章信道编码(3)由于循环码也是线性分组码，所以前面介绍过的
