通信原理精品课件第10章信道编码.ppt

10.1 引言 10.2 信道编码的基本概念 10.3 常用检错码 10.4 线性分组码 10.5 循环码 10.6 卷积码 10.7 交织码与级联码 10.8 m序列 本章小结 习题,第10章 信道编码,10.1 引 言 数字信号在信道的传输过程中，由于实际信道的传输特性不理想以及存在噪声及干扰，在接收端往往会产生误码。为了提高数字通信的可靠性，可合理设计系统的发送和接收滤波器，采用均衡技术，消除数字系统中码间干扰的影响，还可选择合适的调制解调技术，增加发射机功率，采用先进的天线技术等。若数字系统的误码仍不能满足要求，则可以采用信道编码技术，进一步降低误码率。采用信道编码技术的数字通信系统如图10.1.1所示。,图10.1.1 采用信道编码技术的数字通信系统,信道编码是按一定的规律给信息增加冗余度，使不带规律的原始数字信息变换为具有一定规律的数字信息。信道译码则是利用这些规律性来鉴别是否发生错误，进而纠正错误。具体地说，信道编码就是在发送端被传输的信息码元序列中，以一定的编码规则附加一些监督码元，接收端利用该规则进行译码，译码的结果可以发现错误或纠正错误。 信道编码是用增加数码，利用冗余来提高抗干扰能力的。亦是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强其可靠性的。,信道编码不同于信源编码。信源编码是为提高数字信号有效性而采取的一种编码技术，其宗旨是尽可能压缩冗余度。它可降低数码率，压缩传输频带。而信道编码的目的在于提高数字通信的可靠性。需要强调的是：信源编码减少了冗余度，而信道编码增加了冗余度，但这两种冗余度是不同的。信源编码减少的冗余度是随机的、无规律的，即使不减少它，它也不能用来检错或纠错；信道编码增加的冗余度则是特定的、有规律的、有用的，可用它来检错和纠错。 本章主要介绍常用的信道编码技术，主要内容有常用检错码、常用纠错码的编码和译码原理，最后还将介绍m序列及其应用。,10.2 信道编码的基本概念 10.2.1 信道编码的检错、纠错原理 信道编码的基本思想是在被传输信息中附加一些冗余码元，我们称这些冗余码元为监督码元。监督码元和信息码元有一定的关系(规律)，接收端利用监督码元和信息码元的这种关系加以校验，以检测和纠正错误。这种纠、检错能力是用编码的冗余度换取的。 设发送端发送A和B两个消息，要表示A、B两种消息只需要一位编码，即用“1”表示A，用“0”表示B。这种编码无冗余度，效率最高，但同时它也无抗干扰能力。若在传输过程中发生误码，即“1”错成“0”或“0”错成“1”，收端无法判断收到的码元是否发生错误，因为“1”和“0”都是发送端可能发送的码元，所以这种编码方法无纠、检错能力。,若增加一位监督码元，增加的监督码元与信息码元相同，即用“11”表示消息A，用“00”表示信息B。如传输过程中发生1位错误，则“11”、“00”变成“10”或“01”。此时接收端能发现这种错误，因为发送端不可能发送“01”或“10”。但它不能纠错，因为“11”和“00”出现1位错误时都可变成“10”或“01”。所以，当接收端收到“10”或“01”时，它无法确定发送端发送的是“11”还是“00”。,若增加二位监督码元，监督码元仍和信息码元相同，即用“111”表示消息A，用“000”表示消息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.2.2 码长、码重、码距和编码效率 原始数字信息是分组传输的，以二进制编码为例，每k个二进制位为一组，称为信息组，经信道编码后转换为每n个二进制位为一组的码字(也称为码组)，码字中的二进制位称为码元。码字中监督码元数为n-k。一个码字中码元的个数称为码字的长度，简称为码长，通常用n表示。如码字“11011”， 码长n=5。码字中“1”码元的数目称为码字的重量，简称为码重，通常用W表示。如码字“11011”， 码重W=4。,两个等长码字之间对应码元不同的数目称为这两个码字的汉明距离，简称为码距，通常用d表示。如码字“11011”和“00101”之间有四个对应码元不同，故码距d=4。由于两个码字模2相加，对应码元不同的位必为1，对应码元相同的位必为0，所以两个码字模2相加得到的新码组的重量就是这两个码字之间的距离。如： 1101100101=11110，11110的码重为4，与上述所得到的码距相同。 码字集合中两两码字之间距离的最小值称为码的最小距离，通常用d0表示，它决定了一个码的纠、检错能力，因此是极重要的参数。,信息码元数与码长之比定义为编码效率，通常用表示， 的表达式为 (10-2-1) 编码效率是衡量码性能的又一个重要参数。编码效果越高，传信率越高，但此时纠、检错能力要降低，当=1时就没有纠、检错能力了。,10.2.3 最小码距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-2-2)、(10-2-3)及(10-2-4)来确定码的纠、检错能力。仍以发送端发送A、B两种消息为例，信源编码用“1”表示消息A，用“0”表示消息B。信道编码器每收到一个“1”，输出一个码字“1111”； 每收到一个“0”，输出一个码字“0000”。显然，每个码字中一个码元是信息，另三个码元是监督元，这个码共有两个码字，这两个码字间的距离就是码的最小距离，所以这个码的最小码距d0=4。,当此码只用于检错目的时，那么根据式(10-2-2)， d03+1，所以此码最多可检测出3个错误。如“1111”中发生3位错误变成“0001”、“0010”、“0100”、或“1000”，由于发送码字中无这四个码字，所以接收端能发现错误。但它无法发现大于3个的错误，如发生4个错误时，发送“1111”时会收到“0000”，由于“0000”也是可能发送的码字，接收端收到“0000”时认为没有错误，发送的是消息B。,当此码只用于纠错时，那么根据式(10-2-3)， d021+1，所以此码只能纠正1位错误。如发送端发送“1111”，传输中发生一位错误，错成“1110”、“1101”、“1011”或“0111”，由于这些码字与“1111”的距离小，接收端将它们还原为“1111”，这样，接收码字中的1位错误得到纠正。如果传输过程中发生2位错误，如“1111”错成“1100”，接收端只知道有错，但无法知道是“1111”错成“1100”还是“0000”错成“1100”，所以无法纠正错误。,当此码用于同时进行纠错和检错的系统时，根据式 (10-2-4)， d01+2+1，所以此码纠1位错误的同时能检测2位错误。若此码中发生1位错误，如“1111”错成“1110”，接收端将纠正成“1111”，这1位错误得到纠正。若码中发生2位错误，如“1111”错成“1100”，接收端能发现错误，但无法纠正。若码 中发生3位错误，如“1111”错成“0001”，由于系统有纠错功能，因此这种情况发生时，系统认为“0001”中有1位错误，将“0001”自动纠成“0000”，所以系统无法发现3位错误。可见，码距为4的码用于纠错的同时检错，发现不了3位错误，与只用于检错这种情况是不一样的，这一点请读者仔细体会。,10.2.4 信道编码的分类 信道编码有许多分类方法。 (1) 根据信息码元和附加的监督码元之间的关系可以分为线性码和非线性码。若监督码元与信息码元之间的关系可用线性方程来表示，即监督码元是信息码元的线性组合，则称为线性码。反之，若两者不存在线性关系，则称为非线性码。 (2) 根据上述关系涉及的范围来分，可分为分组码及卷积码。分组码的各码元仅与本组的信息码元有关；卷积码中的码元不仅与本组信息码元有关，而且还与前面若干组的信息码元有关，因此卷积码又称为连环码。线性分组码中，把具有循环移位特性的码称为循环码，否则称为非循环码。 (3) 根据码字中信息码元在编码前后是否相同可分为系统码和非系统码。编码前后信息码元保持原样不变的称为系统码，反之称为非系统码。,(4) 根据码的用途可分为检错码和纠错码。以检测(发现)错误为目的的码称为检错码。以纠正错误为目的的码称为纠错码。纠错码一定能检错，但检错码不一定能纠错。通常将纠、检错码统称为纠错码。 (5) 根据纠(检)错误的类型可分为纠(检)随机错误码、纠(检)突发错误码和既能纠(检)随机错误同时又能纠(检)突发错误码。 (6) 根据码元取值的进制可分为二进制码和多进制码。本章仅介绍二进制码。,10.2.5 差错控制方式 常用的差错控制方式主要有三种：前向纠错(FEC)、检错重发(ARQ)和混合纠错(HEC)。它们所对应的差错控制系统如图10.2.1所示。,图10.2.1 三种主要的差错控制方式,前向纠错记作FEC，又称自动纠错。在这种系统中，发端发送纠错码，收端译码器自动发现并纠正错误。ARQ的特点是不需要反向信道，实时性好，ARQ适合于要求实时传输信号的系统，但编码、译码电路相对较复杂。 检错重发记作ARQ，又叫自动请求重发。在这种系统中，发端发送检错码，通过正向信道送到收端，收端译码器检测收到的码字中有无错误。如果接收码字中无错误，则向发送端发送确认信号ACK，告诉发送端此码字已正确接收； 如果收到的码字中有错误，收端不向发送端发送确认信号ACK，发送端等待一段时间后再次发送此码字，一直到正确接收为止。ARQ的特点是需要反向信道，编、译码设备简单。ARQ适合于不要求实时传输但要求误码率很低的数据传输系统。,混合纠错记作HEC，是FEC与ARQ的混合。发端发送纠、检错码(纠错的同时检错)，通过正向信道送到收端，收端对错误能纠正的就自动纠正，纠正不了时就等待发送端重发。HEC同时具有FEC的高传输效率，ARQ的低误码率及编码、译码设备简单等优点。但HEC需要反向信道，实时性差，所以不适合于实时传输信号。,10.3 常用检错码 10.3.1 奇偶监督码 奇偶监督码是一种最简单也是最基本的检错码，又称为奇偶校验码。其编码方法是把信息码元先分组，然后在每组的最后加1位监督码元，使该码字中“1”的数目为奇数或偶数，奇数时称为奇监督码，偶数时称为偶监督码。信息码元长度为3时的奇监督码和偶监督码如表10-3-1所示。,奇偶监督码的译码也很简单。译码器检查接收码字中“1”的个数是否符合编码时的规律。如奇监督码，接收码字中“1”的个数为奇数，如果“1”的个数符合编码时的规律，则译码器认为接收码字没有错误； 如“1”的个数为偶数，不符合编码时的规律，则译码器认为接收码字中有错误。 不难看出，这种奇偶监督码只能发现单个和奇数个错误，而不能检测出偶数个错误，因此它的检错能力不高。但是由于该码的编、译码方法简单，而且在很多实际系统中，码字中发生单个错误的可能性比发生多个错误的可能性大得多，所以奇偶监督码得到广泛应用。,10.3.2 行列奇偶监督码 行列奇偶监督码又称二维奇偶监督码或矩阵码。编码时首先将信息排成一个矩阵，然后对每一行、每一列分别进行奇或偶监督编码。编码完成后可以逐行传输，也可以逐列传输。译码时分别检查各行、各列的奇偶监督关系，判断是否有错。一个行列监督码字的例子如下所示： 监督码元(奇监督) 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 监督码元(奇监督) 1 0 0 1 0 0,行列监督码字的右下角这个码元可以对行进行监督，也可以对列进行监督，甚至可以对整个码字进行监督，本例中此码元对列进行奇监督。 行列监督码具有较强的检测随机错误的能力，能发现1、2、3及其它奇数个错误，也能发现大部分偶数个错误，但分布在矩形的四个项点上的偶数个错误无法发现。 这种码还能发现长度不大于行数或列数的突发错误。这种码也能纠正单个错误或仅在一行中的奇数个错误，因为这些错误的位置是可以由行、列监督而确定的。,10.3.3 恒比码 恒比码又称为等重码或等比码。这种码的码字中“1”和“0”的位数保持恒定的比例。由于每个码字的长度是相同的，若“1”、“0”恒比，则码字必等重。这种码在收端进行检测时，只要检测码字中“1”的个数是否与规定的相同，就可判别有无错误。 我们国家邮电部门采用的五单位数字保护电码，是一种“1”、“0”个数之比为32的恒比码。此码有10个码字，恰好可用来表示10个阿拉伯数字，如表10-3-2所示。,10.4 线性分组码 10.4.1 线性分组码的特点 既是线性码又是分组码的码称为线性分组码。由码的分类我们知道，监督码元仅与本组信息码元有关的码称为分组码，监督码元与信息码元之间的关系可以用线性方程表示的码称为线性码。所以，在线性分组码中，一个码字中的监督码元只与本码字中的信息码元有关，而且这种关系可以用线性方程来表示。如(7，3)分组码，码字长度为7，一个码字内信息码元数为3，监督码元数为4。码字用A=a6a5a4a3a2a1a0表示，前三位表示信息码元，后四位表示监督码元，监督码元与信息码元之间的关系可用如下方程组表示：,(10-4-1),显然，当三位信息码元a6a5a4给定时，根据式(10-4-1)即可计算出四位监督码元a3a2a1a0，然后由这7位构成一个码字输出。所以编码器的工作就是根据收到的信息码元，按编码规则计算监督码元，然后将由信息码元和监督码元构成的码字输出。由编码规则(10-4-1)得到的(7，3)线性分组码的全部码字列于表10-4-1中。读者可根据式(10-4-1)自行计算监督码元加以验证。需要说明的是，式(10-4-1)中的“+”是模2加，以后不再另行说明。,线性分组码有一个重要特点：封闭性。利用这一特点可方便地求出线性分组码的最小码距，进而可确定线性分组码的纠、检错能力。 线性分组码的封闭性是指：码字集中任意两个码字对应位模2加后，得到的码字仍然是该码字集中的一个码字。如表10-4-1中，码字“0011101”和码字“1110100”对应位模2加得“1101001”，“1101001”是表10-4-1中的6号码字。由于两个码字模2加所得的码字的重量等于这两个码字的距离，故(n, k)线性分组码中两个码字之间的码距一定等于该分组码中某一非全0码字的重量。因此，线性分组码的最小码距必等于码字集中非全0码字的最小重量。线性分组码中一定有全0码字，设全0码字为A0，则线性分组码(n, k) 的最小码距为 d0=Wmin(Ai) Ai(n, k), i0 (10-4-2),一个码字集的最小码距决定了这个码的纠、检错能力，线性分组码的封闭性给码距的求解带来了便利。利用式(10-4-2)可方便地求出上述(7，3)分组码的码距，具体方法是：全0码字除外，求出余下7个码字的重量，因为7个码字的重量都等于4，所以最小重量等于4，最小码距d0=4。此(7，3)分组码用于检错，最多能检3个错误，用于纠错，则最多能纠1个错误。 对线性分组有了一般性了解后，下面我们系统讨论线性分组码的编码、译码方法。,10.4.2 线性分组码的编码 下面我们仍以上述(7，3)线性分组码为例，用矩阵理论来讨论线性分组码的编码过程，并得到两个重要的矩阵：生成矩阵G和监督矩阵H。 式(10-4-1)所示监督方程组可改写为 (10-4-3),写成矩阵形式有 简记为 (10-4-4) 或 (10-4-5),其中，AT是码字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=PIr,这样的监督矩阵称为典型监督矩阵。其中Ir为rr的单位矩阵。 P是rk的矩阵。对式(10-4-6)有,若信息码元已知，可通过以下矩阵运算求监督元： (10-4-7) 或 由信息码元和监督码元即可构成码字A=a6a5a4a3 a2a1a0。读者可根据这种方法求出此(7，3)码的全部码字，并与表10-4-1所列码字进行比较。,还可以用生成矩阵来求码字。系统码(n, k)的生成矩阵为 G=IkPT (10-4-8) G称为典型生成矩阵。其中，Ik是kk的单位矩阵。显然，生成矩阵G可以由监督矩阵H确定。因此，与式(10-4-6)相对应的生成矩阵为 (10-4-9),当信息给定时，由生成矩阵求码字的方法是 A=MG (10-4-10) 其中，M为信息矩阵。如M=0 0 1时，通过生成矩阵G生成的码字为 改变信息矩阵M可求出(7，3)码的全部码字，它们与表10-4-1所列码字完全一样。,例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)汉明码的全部码字。,解 我们用式(10-4-10)来求码字。首先求出(7，4)汉明码的典型生成矩阵G。 由式(10-4-12)给定的监督关系求出监督矩阵如下 所以,根据式(10-4-8)得到典型生成矩阵G为 根据式(10-4-10)，当信息矩阵M=0 0 0 0时，码字为,当信息矩阵M=0 0 0 1时，码字为 按此方法求出(7，4)汉明码的所有16个码字并列于表10-4-2中。,根据表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。,解 (5，1)重复码的码字长度为5，其中1位信息码元，4位监督码元，4位监督码元都与信息码元相同，所以监督关系(方程组)如下 (10-4-13),改写式(10-4-13)所示的监督方程组得 (10-4-14),将式(10-4-14)用矩阵表示为,所以，(5，1)重复码的监督矩阵为 其中,因为典型生成矩阵G为 G=PTIk 所以(5，1)重复码的典型生成矩阵为,例10.4.3 奇、偶监督码是另一类简单的线性分组码，用(n, n-1)表示，长度为n的码字中信息码元为n-1个，只有1位监督码元。求长度为4的偶监督码的监督矩阵H和生成矩阵G。 解 设长度为4的偶监督码的码字为A=a3a2a1a0，其中前3位表示信息码元，最后1位表示监督码元。由于偶监督码要求码字中“1”的码元数为偶数，即各码元模2加为0，所以(4，3)偶监督码中监督码元与信息码元满足如下关系 ,此方程用矩阵表示为 所以监督矩阵为 H=1 1 1 1=PI1 其中 P=1 1 1,得典型生成矩阵为 利用生成矩阵G及式(10-4-10)可求出全部8个码字，所求得码字与表10-3-1中所列的偶监督码码字完全相同，读者可自行加以验证。,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。例如，若发送码字A=1001110，接收码字 B=1001100，则错码矩阵E=0000010。错码矩阵通常称为错误图样。,译码器的任务就是判别接收码字B中是否有错，如果有错，则设法确定错误位置并加以纠正，以恢复发送码字A。 由式(10-4-5)可知，码字A与监督矩阵H有如下约束关系 AHT=0 当B=A时，有 BHT=0 0为1行r列的全“0”矩阵。,当BA时，说明传输过程中发生了错误，此时 令矩阵 S=BHT=EHT (10-4-15) 称S为伴随式，伴随式S是个1行r列的矩阵， r是线性分组码中监督码元的个数。由上面的分析可知，当接收码字无错误时，S=0；当接收码字有错误时，S0。又由式(10-4-15)可知， S与错误图样有对应关系，与发送码字无关。故S能确定传输中是否发生了错误及错误的位置。,下面以上一节中所列举的(7，3)码为例，具体说明线性分组码的译码过程。 (1) 首先根据式(10-4-15)求出错误图样E与伴随式S之间的关系，并把它保存在译码器中。由(7，3)线性分组码编码一节可知，此码最小码距d0=4，能纠正码字中任意一位错误，码长为7的码字中错1位的情况有7种，即码字中错1位的错误图样有7种，如码字第一位发生错误，错误图样为 E=1000000,由式(10-4-15)求得伴随式为 由上式可看出，伴随式S6等于HT中的第一行。,如码字在传输过程中第二位发生错误，错误图样为 E=0 1 0 0 0 0 0 则伴随式为 即伴随式S5等于HT中的第二行。,由此可求出错1位的7种错误图样所对应的伴随式，它们刚好对应HT中的7行。错误图样与伴随式之间的对应关系如表10-4-3所示。,(2) 当译码器工作时，首先计算接收码字B的伴随式S，然后查表10-4-3得错误图样E。 如接收码字为B=1100111，用式(10-4-15)求出其伴随式为 根据此伴随式，查表10-4-3得错误图样E=1000000，可知接收码字B中第一位有错误。,(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，译码器认为接收码字中没有错误；如果S0，则译码器认为接收码字中有错误，译码器会以某种方式将此信息反馈给发送端，发送端将重发此码字。,最后还要指出，若接收码字中错误位数超过1时， S也有可能正好与发生1位错误时的某个伴随式相同，这样，经纠错后反而“越纠越错”。如发送码字A=0100111，传输过程中发生3位错误，设错误图样E=0000111，此时接收码字B=0100000。根据上述所介绍的纠错译码方法，计算出此接收码字的伴随式S=0111，查表10-4-3得错误图样E=0100000，译码器认为第二位发生了错误，将第二位纠正，得纠正后的码字为0000000。由此可见，本来接收码字中有3位错误，但通过纠错译码后，错误不但没有减少反而增加了1位，这就所谓的“越纠越错”。,在传输过程中，也会发生发送码字的某几位发生错误后成为另一发送码字的情况，这种情况收端也无法检测，这种错误我们称之为不可检测的错误。从统计观点来看，这种情况出现的概率很小。如发送码字A=0100111，传输过程中发生4位错误变成B=0111010，计算其伴随式发现S=0，译码器认为没错。事实上，接收到的B是另一个发送码字。不管是这种情况还是上述的“越纠越错”，发生原因都是因为码字中的错误个数超出了码的纠错能力。所以在设计信道编码方案时，应充分考虑信道发生错误的情况。,例10.4.4 (例10.4.1续)(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所示。,由表10-4-4可知， HT中的每一行都是一个伴随式。由于(7，4)汉明码中监督码元的个数为3，所以伴随式是个1行3列的矩阵。三位二进制不同的组合共有8种，除全“0”组合外还有7种，这7种组合刚好与错1位的7种错误图样一一对应。所以，码长为7的码字中至少加入3位监督码元才能纠单个错误。(7，4)汉明码在7位码字中只有3位监督码元，因此，(7，4)码是一种纠单个错误的高效的线性分组码。,7种错误图样与7个伴随式之间的关系只要一一对应就不会影响码的纠、检错能力。所以，我们也可改变表10-4-4的对应关系，进而得到不同于例10.4.1中的HT，即得到不同于例10.4.1中(7，4)汉明码的监督关系。如改变表10-4-4中的对应关系得到,所以，监督矩阵为,由 ,得到另一个(7，4)汉明码的监督关系方程组为,按此方法还可构造出不同的(7，4)汉明码的监督关系。我们知道，监督关系不同，码字集中的码字也会不同，但按这种方法构造的所有(7，4)汉明码具有相同的性能，即编码效率相同，纠、检错能力相同。,任意错2位的错误图样有 种，它们是,由例10.4.2 可知(5,1)重复码的监督矩阵为,根据式(10-4-15)求出这15个错误图样所对应的伴随式，并将它们列于表10-4-5中。 由表10-4-5可看到，每个错误图样对应不同的伴随式，所以当码字中错1位或2位时，根据伴随式即可确定错误图样，以此可纠正码字中的1位或2位错误。由该表还可看出，伴随式由4位二进制组成，除全“0”外的所有4位二进制组合全在表10-4-5中了，如果码字中发生3位或4位错误，其伴随式一定是该表中的一个，译码器会按单个错误或2个错来纠错，导致“越纠越错”；如果码字中发生5位错误，如码字11111错成了00000，此时伴随式为0000，译码器无法发现此错误。所以，(5，1)重复码最多能纠2位错误。,10.5 循 环 码 10.5.1 循环码的特点 若线性分组码的任一码字循环移位所得的码字仍在该码字集中，则此线性分组码称为循环码。很明显， (n, 1)重复码是一个循环码。表10-5-1中的(7，3)码及表10-5-2中的(6，3)码也都是循环码，其循环特性分别如图10.5.1所示。循环圈上的数字为码字的序号。由图10.5.1可见，同一循环圈上的各码字重量是相等的。全“0”、全“1”码字分别自成循环圈。循环码的循环圈数目大于等于2。,在讨论循环码时，常用代数多项式来表示循环码的码字，这种多项式称为码多项式。 对于(n, k)循环码的码字，其码多项式的一般形式为 (10-5-1) 码字中各位码元的数值是其码多项式中相应各项的系数值(0或1)。码字A=1001110的码多项式,10.5.2 循环码的编码 循环码完全由其码字长度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。,为了寻找生成多项式，首先应对xn+1进行因式分解，并选择满足上述(2)、(3)两个特点的因式或因式的乘积。如寻找(7，3)循环码，首先对x7+1进行因式分解，有 x7+1=(x+1)(x3+x+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-5-2) ,例如表10-5-1中(7，3)循环码， n=7， k=3， r=4，其生成多项式及生成矩阵分别为,即 (10-5-3),有了生成多项式及生成矩阵后，就可求出循环码的所有码字了。求循环码码字的方法有三种： (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为信息多项式。按此方法可产生循环码的所有码字，但这种方法产生的码不是系统码。如信息M=110，则信息多项式为 M(x)=x2+x,设生成多项式为 g(x)=x4+x3+x2+1 由式(10-5-4)可得码字多项式为 A(x)=(x2+x)(x4+x3+x2+1)=x6+x3+x2+x 所以码字为1001110，显然它不是系统码的码字。,(2) 用生成多项式也可产生系统码的码字，系统循环码的码多项式可表示为 A(x)=xn-kM(x)+xn-kM(x) (10-5-5) 其中，前一部分代表信息码元组，后一部分用 表示，是xn-kM(x)被g(x)除得的余式，它代表监督码元组。 如(7，3)循环码，设信息M=110，则 M(x)=x2+x xn-kM(x)=x4M(x)=x6+x5,当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-5-5)，利用多项式除法电路求xn-kM(x)除以g(x)的余式，即可产生(n, k)系统循环码。g(x)=x4+x3+x2+1时，(7，3)循环码的编码器如图10.5.2所示。,图10.5.2 (7，3)循环码编码器,D0D1D2D3是四级移位寄存器，反馈线的连接与g(x)的非0系数相对应。编码时，首先将四级移存器清零。三位信息码元输入时，门1断开，门2接通，直接输出信息元。第3个移位脉冲后，D0D1D2D3中数据为除法余数，就是输入信息的监督码元。第47次移位时，门2断开，门1接通，输出监督元。当一个码字输出完毕就将移位寄存器清零，等待下一组信息输入后重新编码。设输入的信息码元为110，图10.5.2中各器件及端点状态变化情况如表10-5-3所示。该编码器输入不同信息组时的码字如表10-5-1所示。,(3) 由于循环码也是线性分组码，所以前面介绍过的线性分组码的编码方法同样适用于循环码。由式 (10-5-3)所示的生成矩阵即可生成循环码的码字，方法如下 A=MG (10-5-6) 其中，M是信息矩阵。由于式(10-5-3)所示的生成矩阵不是典型生成矩阵，所以由式(10-5-6)生成的码字不是系统码的码字。要想用生成矩阵生成系统码的码字，生成矩阵必须为典型生成矩阵。将非典型生成矩阵中的行进行一些线性变换，即可得到典型生成矩阵。如将式(10-5-3)所示矩阵中第二行加到第一行(对应位模2加)，得生成矩阵 (10-5-7),再将式(10-5-7)中的第三行加到第二行，得典型生成矩阵为 (10-5-8) 其中 (10-5-9) 将式(10-5-8)所示的典型生成矩阵代入式(10-5-6)，即可求得循环码的系统码字，改变式(10-5-6)中的信息矩阵可求得(7，3)循环码的所有码字。这个工作请读者完成，并把所得码字与表10-5-1所示码字进行比较。,由式(10-5-9)可得循环码的监督矩阵H为 有了监督矩阵，就可用线性分组码的译码方法对循环码进行译码。所以，完全可以用前面介绍的线性分组码的编译码方法对循环码进行编码和译码，但这种方法没有利用循环码的循环移位特性。,10.5.3 循环码的译码 由式(10-5-4)可知，发送码字多项式A(x)是生成多项式g(x)的倍式，换句话说，生成多项式g(x) 能整除发送码字多项式A(x)。如果码字经信道传输后不发生错误，则接收码字多项式B(x)也是生成多项式g(x)的倍式，但如果码字在传输过程中发生错误，则接收码字多项式不再是生成多项式g(x)的倍式，即此时g(x)不能整除接收码字多项式。所以，定义伴随多项式S(x)为 S(x)=B(x) (10-5-10) 即S(x)是接收码字多项式B(x)除以g(x)后的余式，是不大于r-1次的多项式。,接收码字多项式B(x)可表示为发送码字多项式A(x)与差错多项式e(x)(错误图样所对应的多项式) 之和，即 B(x)=A(x)+e(x) (10-5-11) 将式(10-5-11)代到式(10-5-10)中，得 S(x)=A(x)+e(x)=e(x) (10-5-12) 由式(10-5-12)可发现，伴随多项式只与差错多项式有关。所以，循环码的译码过程也可归纳为如下三个步骤： (1) 根据式(10-5-12)计算出可纠错误图样多项式e(x)的伴随式S(x)，将e(x)与S(x)的对应关系列成译码表；,(2) 当收到一个码字B(x)后，利用式(10-5-10)求出伴随式S(x)，对照译码表找到e(x)； (3) 利用式(10-5-11)求出发送码字A(x)，即A(x)=B(x)-e(x)。 例如(7，3)循环码， g(x)=x4+x3+x2+1，码距d0=4，能纠1位错误，所以可纠错误图样多项式有7种，根据式(10-5-12)求出它们所对应伴随多项式，如表10-5-4所示。,如接收码字为B=0101010，则其码字多项式为B(x)=x5+x3+x，利用式(10-5-10)求出伴随式S(x)=x3+x2+1，查表10-5-4，可知第三位(从左起)有错误。 循环码的这种译码方法与线性分组码的译码方法在原理上是相同的。根据此原理构成的循环码译码器如图10.5.3所示。图中伴随式计算电路对接收到的码多项式计算出相应的伴随式。错误图样识别器有r个输入端，通过这r个输入端输入伴随式多项式，根据伴随式多项式找到错误图样。缓存器用于存储n位接收码字。模2运算电路用于纠正错误。当伴随式为0时，模2运算电路中来自错误图样识别电路的输入端为0，输出接收码字。当伴随式不为0时，识别电路在相应的错误码元时刻输出为1，它使缓存器输出取反，这样就纠正了错误。,图10.5.3 一种循环码译码器原理图,图10.5.3所示译码器与前面介绍的线性分组码译码器的不同之处在于：在循环码译码器中，接收码字的伴随式计算可用循环移位寄存器来实现，这个循环移位寄存器的连线与生成多项式有关，由循环移位寄存器构成的伴随式计算电路不但简单而且运算快速。,10.6 卷 积 码 10.6.1 卷积码编码 卷积码与前面介绍的线性分组码不同。在线性分组码(n, k)中，每个码字的n个码元只与本码字中的k个信息码元有关，或者说，各码字中的监督码元只对本码字中的信息码元起监督作用。卷积码则不同，每个(n, k)码字(通常称其为子码，码字长度较短)内的n个码元不仅与该码字内的信息码元有关，而且还与前面m个码字内的信息码元有关。或者说，各子码内的监督码元不仅对本子码起监督作用，而且对前面m个子码内的信息码元也起监督作用。所以，卷积码常用(n, k, m)表示。通常称m为编码存储，它反映了输入信息码元在编码器中需要存储的时间长短；称N=m+1为编码约束度，它是相互约束的码字个数；称nN为编码约束长度，它是相互约束的码元个数。卷积码也有系统码和非系统码之分，如果子码是系统码，则称此卷积码为系统卷积码，反之，则称为非系统卷积码。,图10.6.1是(2，1，2)卷积码的编码电路。此电路由二级移位寄存器、两个模2加法器，及开关电路组成。编码前，各寄存器清0，信息码元按a1，a2，a3，aj-2，aj-1，aj，的顺序输入编码器。每输入一个信息码元aj，开关K依次接到aj1、 aj2各端点一次，输出一个子码aj1aj2。 子码中的两个码元与输入信息码元间的关系为 (10-6-1) 由此可见，第j个子码中的两个码元不仅与本子码信息码元aj有关，而且还与前面两个子码中的信息码元aj-1、 aj-2有关。因此，卷积码的编码存储m=2，约束度N=m+1=3，约束长度nN=6。,图10.6.1 (2，1，2)卷积码编码电路,例10.6.1 在图10.6.1所示的(2，1，2)卷积码编码电路中，当输入信息10011时，求输出码字序列。 解 在计算第j个子码时的移存寄存器的内容aj-1aj-2称为现状态(简称为现态)，编码工作时初始状态为00(清0)，第j个子码的信息进入移位寄存器后的状态称为次态。当输入信息及现态已知时，利用式(10-6-1)即可求出此输入信息所对应的码字。输入信息、输出码字、每个时刻的现态及次态均列于表10-6-1中。,10.6.2 卷积码的图形描述 卷积码编码器的工作过程常用三种等效的图形来描述，这三种图形分别是：状态图、码树图和格状图。下面以图10.6.1所示的(2，1，2)卷积编码器为例，简要介绍这三种图形。 1. 状态图 图10.6.1所示的编码电路是个典型的米勒型(Mealy)时序逻辑电路。共有四个不同的状态：aj-1aj-2=00，10，01，11，为方便起见，这四个状态分别用a、 b、 c和d来表示。在每一个状态下都有0、1两种输入。根据式(10-6-1)，我们可求出每种状态下每种输入时的输出码字及相应的次态，见表10-6-2。,表10-6-2的图形表示就是(2，1，2)卷积编码器的状态图，见图10.6.2所示。图中，用带箭头的线表示输入信息后状态的转移，实线表示输入信息为“0”，虚线表示输入信息为“1”，线旁的二位二进制数表示输出的码字。 此状态图完全反映了图10.6.1所示编码器的工作原理。有了状态图，我们可以很方便地确定任何输入信息序列时所对应的输出码字序列。如输入信息序列为10011，求输出码字序列的方法是：从初始状态a开始沿着状态图中的有向线走，输入为“1”时走虚线，输入为“0”时走实线，所经路径上的11、10、11、11、01序列即为输入10011时所对应的码字序列。,图10.6.2 (2，1，2)卷积编码器的状态图,2. 码树图 图10.6.1所示(2，1，2)编码器的工作原理也可用图10.6.3所示的图形来表示，此图形称为(2，1，2)卷积码的码树图。它描述了编码器在工作过程中可能产生的各种序列。最左边为起点，初始状态为a。从每个状态出发有两条支路(因为每个码字中只有1位信息)，上支路表示输入为“0”，下支路表示输入为“1”。每个支路上的二位二进数是相应的输出码字。由图可知，当信息序列给定时，沿着码树图上的支路很容易确定相应的输出码序列。如输入信息为10011时，从码树图可得输出码字序列为11、10、11、11、01，与前面从状态图上得到的码字序列完全相同。,3. 格状图 图10.6.4是图10.6.3所示码树图的另一种形式，称为(2，1，2)卷积码的格状图。在码树图中，从第三级开始出现全部四个状态，第三级以后四个状态重复出现，使图形变得越来越大。在格状图中，把码树图中具有相同状态的节点合并在一起，使图形变得较为紧凑；码树中的上支路(即输入信息为 “0”)用实线表示，下支路(即输入信息为“1”)用虚线表示；支路上标注的二进制数据为输出码字；自上而下的4行节点分别表示a、 b、 c、 d四种状态。从第三级节点开始，图形开始重复。当输入信息序列给定时，从a开始的路径跟着就确定了，相应的输出码字序列也就确定了。如输入信息序为10011时，对应格状图的路径为a b c a b d，则相应的输出码字序列为11、10、11、11、01。,图10.6.3 (2，1，2)卷积码的码树图,图10.6.4 (2，1，2)卷积码的格状图,10.6.3 卷积码的维特比译码 卷积码的译码分代数译码和概率译码两类。代数译码由于没有充分利用卷积码的特点，目前很少应用。维特比译码和序列译码都属于概率译码。维特比译码方法适用于约束长度不太大的卷积码的译码，当约束长度较大时，采用序列译码能大大降低运算量，但其性能要比维特比译码差些。维特比译码方法在通信领域有着广泛的应用，市场上已有实现维特比译码的超大规模集成电路。,维特比译码是一种最大似然译码。其基本思想是：将已经接收到的码字序列与所有可能的发送序列进行比较，选择其中码距最小的一个序列作为发送序列(即译码后的输出序列)。具体的译码方法是： (1) 在格状图上，计算从起始状态(j=0时刻)开始，到达j=m时刻的每个状态的所有可能路径上的码字序列与接收到的头m个码字之间的码距，保存这些路径及码距。 (2) 从j=m到j=m+1共有2k2m条路径(状态数为2m个，每个状态往下走各有2k个分支)，计算每个分支上的码字与相应时间段内接收码字间的码距，分别与前面保留路径的码距相加，得到2k2m个路径的累计码距，对到达j=m+1时刻各状态的路径进行比较，每个状态保留一条具有最小码距的路径及相应的码距值。,(3) 按(2)的方法继续下去，直到比较完所有接收码字。 (4) 全部接收码字比较完后，剩下2m个路径(每个状态剩下一条路径)，选择最小码距的路径，此路径上的发送码字序列即是译码后的输出序列。,例10.6.2 以上述(2，1，2)编码器为例，设发送码字序列为0000000000，经信道传输后有错误，接收码字序列为0100010000。显然，接收码字序列中有两个错误。现对此接收序列进行维特比译码，求译码后的输出序列。,解 由于(2，1，2)编码器的编码存储m=2，应用译码方法中的步骤(1)， 应