第10章信道编码 10.1 引言引言 10.2 信道编码的根本概念信道编码的根本概念 10.3 常用检错码常用检错码 10.4 线性分组码线性分组码 10.5 循环码循环码 10.6 卷积码卷积码 10.7 交错码与级联码交错码与级联码 10.8 m序列序列 本章小结本章小结 习题习题 第第10章信道编码章信道编码第10章信道编码 10.1 引引 言言数字信号在信道的传输过程中，由于实数字信号在信道的传输过程中，由于实践信道的传输特性不理想以及存在噪声及干践信道的传输特性不理想以及存在噪声及干扰，在接纳端往往会产生误码。为了提高数扰，在接纳端往往会产生误码。为了提高数字通讯的可靠性，可合理设计系统的发送和字通讯的可靠性，可合理设计系统的发送和接纳滤波器，采用平衡技术，消除数字系统接纳滤波器，采用平衡技术，消除数字系统中码间干扰的影响，还可选择适宜的调制解中码间干扰的影响，还可选择适宜的调制解调技术，添加发射机功率，采用先进的天线调技术，添加发射机功率，采用先进的天线技术等。假设数字系统的误码仍不能满足要技术等。假设数字系统的误码仍不能满足要求，那么可以采用信道编码技术，进一步降求，那么可以采用信道编码技术，进一步降低误码率。采用信道编码技术的数字通讯系低误码率。采用信道编码技术的数字通讯系统如图统如图10.1.1所示。所示。第10章信道编码 图10.1.1 采用信道编码技术的数字通讯系统第10章信道编码 信道编码是按一定的规律给信息添加冗余度，使不带规律的原始数字信息变换为具有一定规律的数字信息。信道译码那么是利用这些规律性来鉴别能否发生错误，进而纠正错误。详细地说，信道编码就是在发送端被传输的信息码元序列中，以一定的编码规那么附加一些监视码元，接纳端利用该规那么进展译码，译码的结果可以发现错误或纠正错误。信道编码是用添加数码，利用冗余来提高抗干扰才干的。亦是以降低信息传输速率为代价来减少错误的，或者说是用减弱有效性来加强其可靠性的。第10章信道编码 信道编码不同于信源编码。信源编码是为提高数字信号有效性而采取的一种编码技术，其目的是尽能够紧缩冗余度。它可降低数码率，紧缩传输频带。而信道编码的目的在于提高数字通讯的可靠性。需求强调的是：信源编码减少了冗余度，而信道编码添加了冗余度，但这两种冗余度是不同的。信源编码减少的冗余度是随机的、无规律的，即使不减少它，它也不能用来检错或纠错；信道编码添加的冗余度那么是特定的、有规律的、有用的，可用它来检错和纠错。本章主要引见常用的信道编码技术，主要内容有常用检错码、常用纠错码的编码和译码原理，最后还将引见m序列及其运用。第10章信道编码 10.2 信道信道编码的根本概念的根本概念10.2.1 信道信道编码的的检错、纠错原理原理信道信道编码的根本思想是在被的根本思想是在被传输信息中附信息中附加一些冗余加一些冗余码元，我元，我们称称这些冗余些冗余码元元为监视码元。元。监视码元和信息元和信息码元有一定的关系元有一定的关系(规律律)，接，接纳端利用端利用监视码元和信息元和信息码元的元的这种关系种关系加以校加以校验，以，以检测和和纠正正错误。这种种纠、检错才干是用才干是用编码的冗余度的冗余度换取的。取的。设发送端送端发送送A和和B两个音两个音讯，要表示，要表示A、B两种音两种音讯只需求一位只需求一位编码，即用，即用“1表示表示A，用用“0表示表示B。这种种编码无冗余度，效率最高，无冗余度，效率最高，但同但同时它也无抗干它也无抗干扰才干。假才干。假设在在传输过程中程中发生生误码，即，即“1错成成“0或或“0错成成“1，收端无法判收端无法判别收到的收到的码元能否元能否发生生错误，由于，由于“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表示音讯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 码长、码重、重、码距和距和编码效率效率原始数字信息是分原始数字信息是分组传输的，以二的，以二进制制编码为例，每例，每k个个二二进制位制位为一一组，称，称为信息信息组，经信道信道编码后后转换为每每n个二个二进制位制位为一一组的的码字字(也称也称为码组)，码字中的二字中的二进制位称制位称为码元。元。码字中字中监视码元数元数为n-k。一个。一个码字中字中码元的个数称元的个数称为码字的字的长度，度，简称称为码长，通常用，通常用n表示。如表示。如码字字“11011， 码长n=5。码字中字中“1码元的数目称元的数目称为码字的分量，字的分量，简称称为码重，重，通常用通常用W表示。如表示。如码字字“11011， 码重重W=4。第10章信道编码 两个等长码字之间对应码元不同的数目称为这两个码字的汉明间隔，简称为码距，通常用d表示。如码字“11011和“00101之间有四个对应码元不同，故码距d=4。由于两个码字模2相加，对应码元不同的位必为1，对应码元一样的位必为0，所以两个码字模2相加得到的新码组的分量就是这两个码字之间的间隔。如： 1101100101=11110，11110的码重为4，与上述所得到的码距一样。码字集合中两两码字之间间隔的最小值称为码的最小间隔，通常用d0表示，它决议了一个码的纠、检错才干，因此是极重要的参数。第10章信道编码 信息码元数与码长之比定义为编码效率，通常用表示， 的表达式为 (10-2-1)编码效率是衡量码性能的又一个重要参数。编码效果越高，传信率越高，但此时纠、检错才干要降低，当=1时就没有纠、检错才干了。第10章信道编码 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章信道编码 下面举例阐明给定码距时，如何根据式(10-2-2)、(10-2-3)及(10-2-4)来确定码的纠、检错才干。仍以发送端发送A、B两种音讯为例，信源编码用“1表示音讯A，用“0表示音讯B。信道编码器每收到一个“1，输出一个码字“1111； 每收到一个“0，输出一个码字“0000。显然，每个码字中一个码元是信息，另三个码元是监视元，这个码共有两个码字，这两个码字间的间隔就是码的最小间隔，所以这个码的最小码距d0=4。第10章信道编码 当此码只用于检错目的时，那么根据式(10-2-2)， d03+1，所以此码最多可检测出3个错误。如“1111中发生3位错误变成“0001、“0010、“0100、或“1000，由于发送码字中无这四个码字，所以接纳端能发现错误。但它无法发现大于3个的错误，如发生4个错误时，发送“1111时会收到“0000，由于“0000也是能够发送的码字，接纳端收到“0000时以为没有错误，发送的是音讯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，所以此码纠1位错误的同时能检测2位错误。假设此码中发生1位错误，如“1111错成“1110，接纳端将纠正成“1111，这1位错误得到纠正。假设码中发生2位错误，如“1111错成“1100，接纳端能发现错误，但无法纠正。假设码中发生3位错误，如“1111错成“0001，由于系统有纠错功能，因此这种情况发生时，系统以为“0001中有1位错误，将“0001自动纠成“0000，所以系统无法发现3位错误。可见，码距为4的码用于纠错的同时检错，发现不了3位错误，与只用于检错这种情况是不一样的，这一点请读者仔细领会。第10章信道编码 10.2.4 信道编码的分类信道编码的分类信道编码有许多分类方法。信道编码有许多分类方法。(1) 根据信息码元和附加的监视码元之间的关系可以分为根据信息码元和附加的监视码元之间的关系可以分为线性码和非线性码。假设监视码元与信息码元之间的关系可用线性码和非线性码。假设监视码元与信息码元之间的关系可用线性方程来表示，即监视码元是信息码元的线性组合，那么称线性方程来表示，即监视码元是信息码元的线性组合，那么称为线性码。反之，假设两者不存在线性关系，那么称为非线性为线性码。反之，假设两者不存在线性关系，那么称为非线性码。码。(2) 根据上述关系涉及的范围来分，可分为分组码及卷积根据上述关系涉及的范围来分，可分为分组码及卷积码。分组码的各码元仅与本组的信息码元有关；卷积码中的码码。分组码的各码元仅与本组的信息码元有关；卷积码中的码元不仅与本组信息码元有关，而且还与前面假设干组的信息码元不仅与本组信息码元有关，而且还与前面假设干组的信息码元有关，因此卷积码又称为连环码。线性分组码中，把具有循元有关，因此卷积码又称为连环码。线性分组码中，把具有循环移位特性的码称为循环码，否那么称为非循环码。环移位特性的码称为循环码，否那么称为非循环码。(3) 根据码字中信息码元在编码前后能否一样可分为系统根据码字中信息码元在编码前后能否一样可分为系统码和非系统码。编码前后信息码元坚持原样不变的称为系统码，码和非系统码。编码前后信息码元坚持原样不变的称为系统码，反之称为非系统码。反之称为非系统码。第10章信道编码 (4) 根据码的用途可分为检错码和纠错码。以检测(发现)错误为目的的码称为检错码。以纠正错误为目的的码称为纠错码。纠错码一定能检错，但检错码不一定能纠错。通常将纠、检错码统称为纠错码。(5) 根据纠(检)错误的类型可分为纠(检)随机错误码、纠(检)突发错误码和既能纠(检)随机错误同时又能纠(检)突发错误码。(6) 根据码元取值的进制可分为二进制码和多进制码。本章仅引见二进制码。第10章信道编码 10.2.5 过失控制方式过失控制方式常用的过失控制方式主要有三种：前向纠错常用的过失控制方式主要有三种：前向纠错(FEC)、检错、检错重发重发(ARQ)和混合纠错和混合纠错(HEC)。它们所对应的过失控制系统如。它们所对应的过失控制系统如图图10.2.1所示。所示。第10章信道编码 图10.2.1 三种主要的过失控制方式第10章信道编码 前向纠错记作FEC，又称自动纠错。在这种系统中，发端发送纠错码，收端译码器自动发现并纠正错误。ARQ的特点是不需求反向信道，实时性好，ARQ适宜于要务虚时传输信号的系统，但编码、译码电路相对较复杂。检错重发记作ARQ，又叫自动恳求重发。在这种系统中，发端发送检错码，经过正向信道送到收端，收端译码器检测收到的码字中有无错误。假设接纳码字中无错误，那么向发送端发送确认信号ACK，通知发送端此码字已正确接纳； 假设收到的码字中有错误，收端不向发送端发送确认信号ACK，发送端等待一段时间后再次发送此码字，不断到正确接纳为止。ARQ的特点是需求反向信道，编、译码设备简单。ARQ适宜于不要务虚时传输但要求误码率很低的数据传输系统。第10章信道编码 混合纠错记作HEC，是FEC与ARQ的混合。发端发送纠、检错码(纠错的同时检错)，经过正向信道送到收端，收端对错误能纠正的就自动纠正，纠正不了时就等待发送端重发。HEC同时具有FEC的高传输效率，ARQ的低误码率及编码、译码设备简单等优点。但HEC需求反向信道，实时性差，所以不适宜于实时传输信号。第10章信道编码 10.3 常用常用检错码10.3.1 奇偶奇偶监视码奇偶奇偶监视码是一种最是一种最简单也是最根本的也是最根本的检错码，又称，又称为奇偶校奇偶校验码。其。其编码方法是把信方法是把信息息码元先分元先分组，然后在每，然后在每组的最后加的最后加1位位监视码元，使元，使该码字中字中“1的数目的数目为奇数或偶数，奇数或偶数，奇数奇数时称称为奇奇监视码，偶数，偶数时称称为偶偶监视码。信息信息码元元长度度为3时的奇的奇监视码和偶和偶监视码如如表表10-3-1所示。所示。第10章信道编码 第10章信道编码 奇偶监视码的译码也很简单。译码器检查接纳码字中“1的个数能否符合编码时的规律。如奇监视码，接纳码字中“1的个数为奇数，假设“1的个数符合编码时的规律，那么译码器以为接纳码字没有错误； 如“1的个数为偶数，不符合编码时的规律，那么译码器以为接纳码字中有错误。不难看出，这种奇偶监视码只能发现单个和奇数个错误，而不能检测出偶数个错误，因此它的检错才干不高。但是由于该码的编、译码方法简单，而且在很多实践系统中，码字中发生单个错误的能够性比发生多个错误的能够性大得多，所以奇偶监视码得到广泛运用。第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章信道编码 行列监视码字的右下角这个码元可以对行进展监视，也可以对列进展监视，甚至可以对整个码字进展监视，本例中此码元对列进展奇监视。行列监视码具有较强的检测随机错误的才干，能发现1、2、3及其它奇数个错误，也能发现大部分偶数个错误，但分布在矩形的四个项点上的偶数个错误无法发现。这种码还能发现长度不大于行数或列数的突发错误。这种码也能纠正单个错误或仅在一行中的奇数个错误，由于这些错误的位置是可以由行、列监视而确定的。第10章信道编码 10.3.3 恒比恒比码恒比恒比码又称又称为等重等重码或等比或等比码。这种种码的的码字中字中“1和和“0的位数的位数坚持恒定的比例。由于每个持恒定的比例。由于每个码字的字的长度是一度是一样的，的，假假设“1、“0恒比，那么恒比，那么码字必等重。字必等重。这种种码在收端在收端进展展检测时，只需，只需检测码字中字中“1的个数能否与的个数能否与规定的一定的一样，就，就可判可判别有无有无错误。我我们国家国家邮电部部门采用的五采用的五单位数字位数字维护电码，是一种，是一种“1、“0个数之比个数之比为3 2的恒比的恒比码。此。此码有有10个个码字，恰好字，恰好可用来表示可用来表示10个阿拉伯数字，如表个阿拉伯数字，如表10-3-2所示。所示。第10章信道编码 第10章信道编码 10.4 线性分组码线性分组码10.4.1 线性分组码的特点线性分组码的特点既是线性码又是分组码的码称为线性分组既是线性码又是分组码的码称为线性分组码。由码的分类我们知道，监视码元仅与本组码。由码的分类我们知道，监视码元仅与本组信息码元有关的码称为分组码，监视码元与信信息码元有关的码称为分组码，监视码元与信息码元之间的关系可以用线性方程表示的码称息码元之间的关系可以用线性方程表示的码称为线性码。所以，在线性分组码中，一个码字为线性码。所以，在线性分组码中，一个码字中的监视码元只与本码字中的信息码元有关，中的监视码元只与本码字中的信息码元有关，而且这种关系可以用线性方程来表示。如而且这种关系可以用线性方程来表示。如(7，3)分组码，码字长度为分组码，码字长度为7，一个码字内信息码元，一个码字内信息码元数为数为3，监视码元数为，监视码元数为4。码字用。码字用A=a6a5a4a3a2a1a0表示，前三位表示信息表示，前三位表示信息码元，后四位表示监视码元，监视码元与信息码元，后四位表示监视码元，监视码元与信息码元之间的关系可用如下方程组表示：码元之间的关系可用如下方程组表示：第10章信道编码 (10-4-1)第10章信道编码 显然，当三位信息码元a6a5a4给定时，根据式(10-4-1)即可计算出四位监视码元a3a2a1a0，然后由这7位构成一个码字输出。所以编码器的任务就是根据收到的信息码元，按编码规那么计算监视码元，然后将由信息码元和监视码元构成的码字输出。由编码规那么(10-4-1)得到的(7，3)线性分组码的全部码字列于表10-4-1中。读者可根据式(10-4-1)自行计算监视码元加以验证。需求阐明的是，式(10-4-1)中的“+是模2加，以后不再另行阐明。第10章信道编码 线性分组码有一个重要特点：封锁性。利用这一特点可方便地求出线性分组码的最小码距，进而可确定线性分组码的纠、检错才干。线性分组码的封锁性是指：码字集中恣意两个码字对应位模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章信道编码 第10章信道编码 一个码字集的最小码距决议了这个码的纠、检错才干，线性分组码的封锁性给码距的求解带来了便利。利用式(10-4-2)可方便地求出上述(7，3)分组码的码距，详细方法是：全0码字除外，求出余下7个码字的分量，由于7个码字的分量都等于4，所以最小分量等于4，最小码距d0=4。此(7，3)分组码用于检错，最多能检3个错误，用于纠错，那么最多能纠1个错误。对线性分组有了普通性了解后，下面我们系统讨论线性分组码的编码、译码方法。第10章信道编码 10.4.2 线性分组码的编码线性分组码的编码下面我们仍以上述下面我们仍以上述(7，3)线性分组码为例，用矩阵实际来线性分组码为例，用矩阵实际来讨论线性分组码的编码过程，并得到两个重要的矩阵：生成矩讨论线性分组码的编码过程，并得到两个重要的矩阵：生成矩阵阵G和监视矩阵和监视矩阵H。式式(10-4-1)所示监视方程组可改写为所示监视方程组可改写为(10-4-3)第10章信道编码 写成矩阵方式有简记为 (10-4-4)或(10-4-5)第10章信道编码 其中，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第10章信道编码 这样的监视矩阵称为典型监视矩阵。其中Ir为rr的单位矩阵。 P是rk的矩阵。对式(10-4-6)有第10章信道编码 假设信息码元知，可经过以下矩阵运算求监视元： (10-4-7)或由信息码元和监视码元即可构成码字A=a6a5a4a3 a2a1a0。读者可根据这种方法求出此(7，3)码的全部码字，并与表10-4-1所列码字进展比较。第10章信道编码 还可以用生成矩阵来求码字。系统码(n, k)的生成矩阵为G=IkPT(10-4-8)G称为典型生成矩阵。其中，Ik是kk的单位矩阵。显然，生成矩阵G可以由监视矩阵H确定。因此，与式(10-4-6)相对应的生成矩阵为(10-4-9)第10章信道编码 当信息给定时，由生成矩阵求码字的方法是A=MG (10-4-10)其中，M为信息矩阵。如M=0 0 1时，经过生成矩阵G生成的码字为改动信息矩阵M可求出(7，3)码的全部码字，它们与表10-4-1所列码字完全一样。第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)汉明码的全部码字。第10章信道编码 解 我们用式(10-4-10)来求码字。首先求出(7，4)汉明码的典型生成矩阵G。由式(10-4-12)给定的监视关系求出监视矩阵如下所以第10章信道编码 根据式(10-4-8)得到典型生成矩阵G为根据式(10-4-10)，当信息矩阵M=0 0 0 0时，码字为第10章信道编码 当信息矩阵M=0 0 0 1时，码字为按此方法求出(7，4)汉明码的一切16个码字并列于表10-4-2中。第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，1)反复码的码字长度为5，其中1位信息码元，4位监视码元，4位监视码元都与信息码元一样，所以监视关系(方程组)如下(10-4-13) 第10章信道编码 改写式(10-4-13)所示的监视方程组得(10-4-14)第10章信道编码 将式(10-4-14)用矩阵表示为第10章信道编码 所以，(5，1)反复码的监视矩阵为其中第10章信道编码 由于典型生成矩阵G为G=PTIk所以(5，1)反复码的典型生成矩阵为第10章信道编码 例10.4.3 奇、偶监视码是另一类简单的线性分组码，用(n, n-1)表示，长度为n的码字中信息码元为n-1个，只需1位监视码元。求长度为4的偶监视码的监视矩阵H和生成矩阵G。解 设长度为4的偶监视码的码字为A=a3a2a1a0，其中前3位表示信息码元，最后1位表示监视码元。由于偶监视码要求码字中“1的码元数为偶数，即各码元模2加为0，所以(4，3)偶监视码中监视码元与信息码元满足如下关系第10章信道编码 此方程用矩阵表示为所以监视矩阵为H=1 1 1 1=PI1其中P=1 1 1第10章信道编码 得典型生成矩阵为利用生成矩阵G及式(10-4-10)可求出全部8个码字，所求得码字与表10-3-1中所列的偶监视码码字完全一样，读者可自行加以验证。第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。例如，假。例如，假设发送送码字字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。又由式(10-4-15)可知， S与错误图样有对应关系，与发送码字无关。故S能确定传输中能否发生了错误及错误的位置。第10章信道编码 下面以上一节中所列举的(7，3)码为例，详细阐明线性分组码的译码过程。(1) 首先根据式(10-4-15)求出错误图样E与伴随式S之间的关系，并把它保管在译码器中。由(7，3)线性分组码编码一节可知，此码最小码距d0=4，能纠正码字中恣意一位错误，码长为7的码字中错1位的情况有7种，即码字中错1位的错误图样有7种，如码字第一位发生错误，错误图样为E=1000000第10章信道编码 由式(10-4-15)求得伴随式为由上式可看出，伴随式S6等于HT中的第一行。第10章信道编码 如码字在传输过程中第二位发生错误，错误图样为E=0 1 0 0 0 0 0那么伴随式为即伴随式S5等于HT中的第二行。第10章信道编码 由此可求出错1位的7种错误图样所对应的伴随式，它们刚好对应HT中的7行。错误图样与伴随式之间的对应关系如表10-4-3所示。第10章信道编码 第10章信道编码 (2) 当译码器任务时，首先计算接纳码字B的伴随式S，然后查表10-4-3得错误图样E。如接纳码字为B=1100111，用式(10-4-15)求出其伴随式为根据此伴随式，查表10-4-3得错误图样E=1000000，可知接纳码字B中第一位有错误。 第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，译码器以为接纳码字中没有错误；假设S0，那么译码器以为接纳码字中有错误，译码器会以某种方式将此信息反响给发送端，发送端将重发此码字。第10章信道编码 最后还要指出，假设接纳码字中错误位数超越1时， S也有能够正好与发生1位错误时的某个伴随式一样，这样，经纠错后反而“越纠越错。如发送码字A=0100111，传输过程中发生3位错误，设错误图样E=0000111，此时接纳码字B=0100000。根据上述所引见的纠错译码方法，计算出此接纳码字的伴随式S=0111，查表10-4-3得错误图样E=0100000，译码器以为第二位发生了错误，将第二位纠正，得纠正后的码字为0000000。由此可见，本来接纳码字中有3位错误，但经过纠错译码后，错误不但没有减少反而添加了1位，这就所谓的“越纠越错。 第10章信道编码 在传输过程中，也会发生发送码字的某几位发生错误后成为另一发送码字的情况，这种情况收端也无法检测，这种错误我们称之为不可检测的错误。从统计观念来看，这种情况出现的概率很小。如发送码字A=0100111，传输过程中发生4位错误变成B=0111010，计算其伴随式发现S=0，译码器以为没错。现实上，接纳到的B是另一个发送码字。不论是这种情况还是上述的“越纠越错，发生缘由都是由于码字中的错误个数超出了码的纠错才干。所以在设计信道编码方案时，应充分思索信道发生错误的情况。第10章信道编码 例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章信道编码 第10章信道编码 由表10-4-4可知， HT中的每一行都是一个伴随式。由于(7，4)汉明码中监视码元的个数为3，所以伴随式是个1行3列的矩阵。三位二进制不同的组合共有8种，除全“0组合外还有7种，这7种组合刚好与错1位的7种错误图样一一对应。所以，码长为7的码字中至少参与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中的对应关系得到第10章信道编码 所以，监视矩阵为第10章信道编码 由 ,得到另一个(7，4)汉明码的监视关系方程组为第10章信道编码 按此方法还可构造出不同的(7，4)汉明码的监视关系。我们知道，监视关系不同，码字集中的码字也会不同，但按这种方法构造的一切(7，4)汉明码具有一样的性能，即编码效率一样，纠、检错才干一样。第10章信道编码 例10.4.5 实验证(5，1)反复码最多能纠2位错误。解 最多能纠2位错误的码必需能纠恣意位置上的单个错误及恣意位置上的2个错误。长度为5的码字发生单个错误的错误图样有种，分别是第10章信道编码 恣意错2位的错误图样有种，它们是第10章信道编码 由例10.4.2 可知(5,1)反复码的监视矩阵为第10章信道编码 根据式(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章信道编码 第10章信道编码 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。第10章信道编码 第10章信道编码 第10章信道编码 在讨论循环码时，常用代数多项式来表示循环码的码字，这种多项式称为码多项式。 对于(n, k)循环码的码字，其码多项式的普通方式为 (10-5-1)码字中各位码元的数值是其码多项式中相应各项的系数值(0或1)。码字A=1001110的码多项式第10章信道编码 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。第10章信道编码 为了寻觅生成多项式，首先应对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章信道编码 用多项式来表示生成矩阵的各行，那么生成矩阵可写成 (10-5-2)第10章信道编码 例如表10-5-1中(7，3)循环码， n=7， k=3， r=4，其生成多项式及生成矩阵分别为第10章信道编码 即 (10-5-3)第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为信息多项式。按此方法可产生循环码的一切码字，但这种方法产生的码不是系统码。如信息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=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)循环码编码器第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) 由于循环码也是线性分组码，所以前面引见过的线性分组码的编码方法同样适用于循环码。由式 (10-5-3)所示的生成矩阵即可生成循环码的码字，方法如下A=MG(10-5-6)其中，M是信息矩阵。由于式(10-5-3)所示的生成矩阵不是典型生成矩阵，所以由式(10-5-6)生成的码字不是系统码的码字。要想用生成矩阵生成系统码的码字，生成矩阵必需为典型生成矩阵。将非典型生成矩阵中的行进展一些线性变换，即可得到典型生成矩阵。如将式(10-5-3)所示矩阵中第二行加到第一行(对应位模2加)，得生成矩阵(10-5-7)第10章信道编码 再将式(10-5-7)中的第三行加到第二行，得典型生成矩阵为 (10-5-8)其中 (10-5-9)将式(10-5-8)所示的典型生成矩阵代入式(10-5-6)，即可求得循环码的系统码字，改动式(10-5-6)中的信息矩阵可求得(7，3)循环码的一切码字。这个任务请读者完成，并把所得码字与表10-5-1所示码字进展比较。第10章信道编码 由式(10-5-9)可得循环码的监视矩阵H为有了监视矩阵，就可用线性分组码的译码方法对循环码进展译码。所以，完全可以用前面引见的线性分组码的编译码方法对循环码进展编码和译码，但这种方法没有利用循环码的循环移位特性。第10章信道编码 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次的多次的多项式。式。第10章信道编码 接纳码字多项式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)的对应关系列成译码表；第10章信道编码 (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所示。 第10章信道编码 第10章信道编码 如接纳码字为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章信道编码 图10.5.3 一种循环码译码器原理图第10章信道编码 图10.5.3所示译码器与前面引见的线性分组码译码器的不同之处在于：在循环码译码器中，接纳码字的伴随式计算可用循环移位存放器来实现，这个循环移位存放器的连线与生成多项式有关，由循环移位存放器构成的伴随式计算电路不但简单而且运算快速。第10章信道编码 10.6 卷卷 积积 码码10.6.1 卷积码编码卷积码编码卷积码与前面引见的线性分组码不同。在卷积码与前面引见的线性分组码不同。在线性分组码线性分组码(n, k)中，每个码字的中，每个码字的n个码元只与个码元只与本码字中的本码字中的k个信息码元有关，或者说，各码字个信息码元有关，或者说，各码字中的监视码元只对本码字中的信息码元起监视中的监视码元只对本码字中的信息码元起监视作用。卷积码那么不同，每个作用。卷积码那么不同，每个(n, k)码字码字(通常通常称其为子码，码字长度较短称其为子码，码字长度较短)内的内的n个码元不仅个码元不仅与该码字内的信息码元有关，而且还与前面与该码字内的信息码元有关，而且还与前面m个码字内的信息码元有关。或者说，各子码内个码字内的信息码元有关。或者说，各子码内的监视码元不仅对本子码起监视作用，而且对的监视码元不仅对本子码起监视作用，而且对前面前面m个子码内的信息码元也起监视作用。所个子码内的信息码元也起监视作用。所以，卷积码常用以，卷积码常用(n, k, m)表示。通常称表示。通常称m为编为编码存储，它反映了输入信息码元在编码器中需码存储，它反映了输入信息码元在编码器中需求存储的时间长短；称求存储的时间长短；称N=m+1为编码约束度，为编码约束度，它是相互约束的码字个数；称它是相互约束的码字个数；称nN为编码约束长为编码约束长度，它是相互约束的码元个数。卷积码也有系度，它是相互约束的码元个数。卷积码也有系统码和非系统码之分，假设子码是系统码，那统码和非系统码之分，假设子码是系统码，那么称此卷积码为系统卷积码，反之，那么称为么称此卷积码为系统卷积码，反之，那么称为非系统卷积码。非系统卷积码。第10章信道编码 图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章信道编码 图10.6.1 (2，1，2)卷积码编码电路第10章信道编码 例10.6.1 在图10.6.1所示的(2，1，2)卷积码编码电路中，当输入信息10011时，求输出码字序列。解 在计算第j个子码时的移存存放器的内容aj-1aj-2称为现形状(简称为现态)，编码任务时初始形状为00(清0)，第j个子码的信息进入移位存放器后的形状称为次态。当输入信息及现态知时，利用式(10-6-1)即可求出此输入信息所对应的码字。输入信息、输出码字、每个时辰的现态及次态均列于表10-6-1中。第10章信道编码 第10章信道编码 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章信道编码 第10章信道编码 表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章信道编码 图10.6.2 (2，1，2)卷积编码器的形状图第10章信道编码 2. 码树图图10.6.1所示所示(2，1，2)编码器的任器的任务原理也可用原理也可用图10.6.3所所示的示的图形来表示，此形来表示，此图形称形称为(2，1，2)卷卷积码的的码树图。它描。它描画了画了编码器在任器在任务过程中能程中能够产生的各种序列。最左生的各种序列。最左边为起点，起点，初始形状初始形状为a。从每个形状出。从每个形状出发有两条支路有两条支路(由于每个由于每个码字中只字中只需需1位信息位信息)，上支路表示，上支路表示输入入为“0，下支路表示，下支路表示输入入为“1。每个支路上的二位二每个支路上的二位二进数是相数是相应的的输出出码字。由字。由图可知，当信可知，当信息序列息序列给定定时，沿着，沿着码树图上的支路很容易确定相上的支路很容易确定相应的的输出出码序列。如序列。如输入信息入信息为10011时，从，从码树图可得可得输出出码字序列字序列为11、10、11、11、01，与前面从形状，与前面从形状图上得到的上得到的码字序列完全一字序列完全一样。第10章信道编码 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章信道编码 图10.6.3 (2，1，2)卷积码的码树图第10章信道编码 图10.6.4 (2，1，2)卷积码的格状图第10章信道编码 10.6.3 卷积码的维特比译码卷积码的维特比译码卷积码的译码分代数译码和概率译码两类。代数译码由于卷积码的译码分代数译码和概率译码两类。代数译码由于没有充分利用卷积码的特点，目前很少运用。维特比译码和序没有充分利用卷积码的特点，目前很少运用。维特比译码和序列译码都属于概率译码。维特比译码方法适用于约束长度不太列译码都属于概率译码。维特比译码方法适用于约束长度不太大的卷积码的译码，当约束长度较大时，采用序列译码能大大大的卷积码的译码，当约束长度较大时，采用序列译码能大大降低运算量，但其性能要比维特比译码差些。维特比译码方法降低运算量，但其性能要比维特比译码差些。维特比译码方法在通讯领域有着广泛的运用，市场上已有实现维特比译码的超在通讯领域有着广泛的运用，市场上已有实现维特比译码的超大规模集成电路。大规模集成电路。第10章信道编码 维特比译码是一种最大似然译码。其根本思想是：将曾经接纳到的码字序列与一切能够的发送序列进展比较，选择其中码距最小的一个序列作为发送序列(即译码后的输出序列)。详细的译码方法是：(1) 在格状图上，计算从起始形状(j=0时辰)开场，到达j=m时辰的每个形状的一切能够途径上的码字序列与接纳到的头m个码字之间的码距，保管这些途径及码距。(2) 从j=m到j=m+1共有2k2m条途径(形状数为2m个，每个形状往下走各有2k个分支)，计算每个分支上的码字与相应时间段内接纳码字间的码距，分别与前面保管途径的码距相加，得到2k2m个途径的累计码距，对到达j=m+1时辰各形状的途径进展比较，每个形状保管一条具有最小码距的途径及相应的码距值。第10章信道编码 (3) 按(2)的方法继续下去，直到比较完一切接纳码字。(4) 全部接纳码字比较完后，剩下2m个途径(每个形状剩下一条途径)，选择最小码距的途径，此途径上的发送码字序列即是译码后的输出序列。第10章信道编码 例10.6.2 以上述(2，1，2)编码器为例，设发送码字序列为0000000000，经信道传输后有错误，接纳码字序列为0100010000。显然，接纳码字序列中有两个错误。现对此接纳序列进展维特比译码，求译码后的输出序列。第10章信道编码 解 由于(2，1，2)编码器的编码存储m=2，运用译码方法中的步骤(1)， 应从(2，1，2)格状图的第j=m=2时辰开场。从图10.6.4可见， j=2时辰有4个形状，从初始形状出发，到达这4个形状的途径有4条，到达形状b途径的码字序列为0000； 到达形状b途径的码字序列为0011； 到达形状c途径的码字序列为1110； 到达形状d途径的码字序列为1101。途径长度为2，这段时间内接纳码字有2个，这2个码字为01，00。4条途径上能够发送的2个码字序列分别与接纳的2个码字比较，得到4条途径的码距分别为1、3、2、2，保管这4条途径及相应的码距，被保管下来的途径称为幸存途径。见图10.6.5 (a)。第10章信道编码 图10.6.5 (2，1，2)卷积码的维持比译码过程第10章信道编码 运用步骤(2)。察看格状图10.6.4可见，从j=2时辰的4个形状到达j=3时辰的4个形状共有8条途径，从形状a出发的2条途径上的码字分别为00和11，和这期间接纳码字01相比，码距分别为1和1，分别加到a形状前面这段途径的码距上，得到2条延伸途径000000和000011的码距，它们都等于2，一条到达j=3时辰的a形状，另一条到达j=3时刻的b形状。用一样的方法求得从j=2时辰的b、 c、 d出发到达j=3时辰各形状的6条途径的码距，并把这些码距分别加到前面保管途径的码距上，得到6条延伸途径的码距。各有2条途径到达j=3时辰的每个形状，在到达每个形状的2条途径中选择码距小的途径保管下来，同样将相应的码距也保管下来。见图10.6.5(b)所示。第10章信道编码 按上述方法继续计算到达j=4、 j=5时辰各形状途径的码距，并选择相应的保管途径及码距，见图10.6.5(c)、(d)。最后，在j=5时辰的4条保管途径中选择与接纳码字码距最小的一条途径，由图10.6.5(d)可见，码距最小的途径是aaaaaa，所对应的发送码字序列为0000000000。由此可见，经过上述维特比译码，接纳序列中0100010000中的两位错得到了纠正。第10章信道编码 10.7 交错码与级联码交错码与级联码从发生错误的类型来分，信道可分为三类：从发生错误的类型来分，信道可分为三类：(1) 随机信道，产生随机错误的信道。如随机信道，产生随机错误的信道。如白噪声信道。白噪声信道。(2) 突发信道，产生突发错误的信道。如突发信道，产生突发错误的信道。如瑞利衰落信道。瑞利衰落信道。(3) 混合信道，既产生随机错误又产生突混合信道，既产生随机错误又产生突发错误的信道。发错误的信道。第10章信道编码 10.7.1 交交错码交交错码又称交又称交错码，是一种能，是一种能纠正突正突发错误的的码。它利。它利用用纠随机随机错误的的码，以交，以交错的方法来构造的方法来构造码字。把字。把纠随机随机错误的的(n, k)线性分性分组码的的m个个码字，排成字，排成m行的一个行的一个码阵，该码阵称称为交交错码阵。一个交。一个交错码阵就是交就是交错码的一个的一个码字。字。交交错码阵中的每一行称中的每一行称为交交错码的子的子码或行或行码。行数。行数m称称为交交错度。度。图10.7.1所示是所示是(28，16)交交错码的一个的一个码字。其行字。其行码是是能能纠单个随机个随机错误的的(7，4)汉明明码，交，交错度度m=4。传输时按列按列的次序的次序进展，因此送往信道的交展，因此送往信道的交错码的一个的一个码字字为a61a62a63a64a51a52a01a02a03a04。第10章信道编码 图10.7.1 m=4的(28，16)交错码第10章信道编码 在传输过程中假设发生长度b4的单个突发错误，那么无论从哪一位开场，至多只影响图10.7.1码阵中每一行的一个码元。接纳端把收到的交错码的码字再排成如图10.7.1所示的码阵，然后逐行分别译码。由于每一行码能纠正一个错误，故四行译完后，就可把接纳码字中b4的突发错误纠正过来。显然，假设要纠正较长的突发错误，那么可把码阵中的行数添加，即增大交错度。普通，一个(n, k)码能纠正t个随机错误，按照上述方法交错，即可得到一个(nm, km)交错码。该交错码能纠正长度bmt的单个突发错误。第10章信道编码 10.7.2 级联码级联码在某些纠错要求比较高的系统中，可采用约束度非常长在某些纠错要求比较高的系统中，可采用约束度非常长的卷积码或级联码。当约束度很长时，卷积码的译码要采用的卷积码或级联码。当约束度很长时，卷积码的译码要采用序列译码，设备相对较为复杂。常用的一种编码方案是采用序列译码，设备相对较为复杂。常用的一种编码方案是采用级联码。图级联码。图10.7.2给出了一种级联编码方法。给出了一种级联编码方法。第10章信道编码 图10.7.2 级联编码第10章信道编码 图10.7.2中的级联码由三部分构成：外码、交错码和内码。外码通常运用线性分组码；内码通常采用约束度较小的卷积码，卷积码的译码采用维特比译码方法。由于维特比译码易产生突发错误(错误太多，无法纠正时)，所以在外码和内码之间添加交错编码的目的是将突发错误转变为随机错误。级联码的最大优点是在获得很强纠错才干的同时设备复杂度适中。第10章信道编码 10.8 m序列序列10.8.1 m序列的序列的产生生图10.8.1是是n级线性反响移位存放器的方框性反响移位存放器的方框图。它由。它由n级移存器、移存器、时钟脉冲脉冲产生器生器(未画未画)及及一些模一些模2加法器适当加法器适当衔接而成。接而成。图中，中，ai表示某表示某一一级移存器的形状移存器的形状(i=0, 1, 2, , n-1)， Ci表示表示反响反响线的的衔接形状接形状(反响系数反响系数)。 Ci=1表示此表示此线连通，参与反响；通，参与反响；Ci=0表示此表示此线断开，不参与断开，不参与反响。反响。 C1=C0=1。随着。随着时钟脉冲的脉冲的输入，入，电路路输出周期性序列，周期出周期性序列，周期长度度P2n-1。当。当P=2n-1时，称，称输出序列出序列为m序列。序列。第10章信道编码 图10.8.1 n级线性反响移位存放器第10章信道编码 将反响系数C0， C1， C2， Cn写成多项式此系数多项式称为n级移位存放器的特征多项式，由此可见特征多项式决议移位存放器电路构造。第10章信道编码 例10.8.1 设某移位存放器的特征多项式为f(x)=x3+x2+1。试画出此反响移位存放器，并求其输出序列(设初始形状a2a1a0=001)。解 由于f(x)=x3+x2+1中最高次数为3，所以反响移位存放器有3级。又根据给定的特征多项式知： C3=1、 C2=1、 C1=0、 C0=1。按照图10.8.1的构造画出特征多项式为f(x)=x3+x2+1的3级反响移位存放器，如图10.8.2所示。第10章信道编码 图10.8.2 反响移位存放器电路第10章信道编码 随着脉冲的输入，我们可求出各时辰电路形状及相应的输出，并将它们列于表10-8-1中。 第10章信道编码 第10章信道编码 从表10-8-1可见，电路从初始形状a2a1a0=001开场，输入7个脉冲后电路又回到001形状，当继续输入脉冲时，电路的形状及输出序列将周期反复出现，反复周期为7，一个周期内的输出序列为1001011。此序列是周期为7的m序列。例10.8.2 设三级反响移位存放器的特征多项式为f(x)=x3+x2+x+1。试画出电路，并求其输出序列。解 由给定多项式可知，此三级反响移位存放器的系数为： C3=1、 C2=1、 C1=1、C0=1。根据反响移位存放器的普通构造图，可画出特征多项式为f(x)=x3+x2+x+1的反响移位存放器电路图，如图10.8.3所示。第10章信道编码 图10.8.3 反响移位存放器电路第10章信道编码 按照反响移位存放器的任务原理，求出此电路任务时的形状的变化及相应的输出，列于表10-8-2(与上例一样，设电路初始形状a2a1a0=001)。第10章信道编码 第10章信道编码 由表10-8-2可见，此电路从初始形状a2a1a0=001开场，经4个脉冲后又回到001。也就是说，此电路的反复周期为4，输出序列的反复周期为4，一个周期内的输出序列为1001。显然， 423-1，所以输出序列不是m序列。第10章信道编码 由上述两个例子可见，特征多项式与输出序列的周期有着亲密的关系。实际曾经证明， n级反响移位存放器能产生m序列的充要条件是：(1) f(x)为既约多项式(不可再分解)。(2) f(x)能整除xP+1，其中P=2n-1。 (3) f(x)不能整除xq+1，其中qP。第10章信道编码 满足上述三个条件的特征多项式称为本原多项式。阅历证，例10.8.1中的特征多项式是本原多项式，因此根据它构成的三级反响移位存放器能产生m序列。而例10.8.2中的特征多项式不是本原多项式，由于有这样的分解因式： x4+1=(x3+x2+x+1)(x+1)，这阐明特征多项式f(x)=x3+x2+x+1能整除x4+1，所以此特征多项式不满足本原多项式的第3个条件，所以它不是本原多项式，也不能够产生m序列。由此可见，构造m序列产生器首要的义务是找出相应的本原多项式。第10章信道编码 例10.8.3 试用四级反响移位存放器构成周期为P=24-1的m序列产生器。解 要构成m序列产生器，关键是确定电路所对应的特征多项式。先将xP+1=x15+1分解因式，使各因式为既约因式，再从中寻觅次数为4(P=24-1)的本原多项式。即x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)其中，4次既约多项式有三个，但x4+x3+x2+x+1能整除x5+1，故它不是本原多项式。而x4+x+1或x4+x3+1不能整除xq+1(q15)，故它们都是本原多项式。用f(x)=x4+x+1构成m序列产生器，如图10.8.4所示。此电路任务时形状的变化及其输出序列见表10-8-3。第10章信道编码 第10章信道编码 需求留意的是移位存放器的初始形状不能设成“0，否那么输出序列为全“0了。表10-8-3中设为a3a2a1a0=1000，输出周期序列周期为15。第10章信道编码 10.8.2 m序列的运用序列的运用m序列的运用非常广泛。在数字通序列的运用非常广泛。在数字通讯系系统误码率的丈量中，率的丈量中，它是一个理想的它是一个理想的产生随机序列的信源；在通生随机序列的信源；在通讯系系统性能的丈量性能的丈量中，它也是一个理想的噪声中，它也是一个理想的噪声产生器。它生器。它还运用于运用于时延丈量、延丈量、测距、通距、通讯加密、加密、扩频通通讯及数据的及数据的扰乱等乱等领域。限于篇幅，域。限于篇幅，这里只引里只引见m序列在数据序列在数据扰乱中的运用。乱中的运用。在数字通在数字通讯系系统中，要求信源中，要求信源输出的出的“1、“0序列中序列中“1、“0等概出等概出现，且相互独立。但，且相互独立。但实践中，有的信源达不到践中，有的信源达不到这个要求，此个要求，此时可利用可利用m序列序列对信源信源输出出进展展扰乱，改乱，改动信源信源输出序列的分布出序列的分布规律，使其随机化且律，使其随机化且“1、“0趋近于等概。近于等概。 m序列被称序列被称为扰码。采用。采用扰码技技术的通的通讯系系统组成原理如成原理如图10.8.5所所示。示。第10章信道编码 图10.8.5 采用扰码的通讯系统第10章信道编码 图10.8.5中的扰乱器也称为扰码器。扰码器的作用是将输入数据序列与m序列产生器输出的m序列模2加，以到达扰乱数据的目的。解扰器的作用与扰码器那么刚好相反，它是从被扰乱了的序列中恢复原数据。图10.8.6(a)、(b)分别是用3级反响移位存放器构成的扰码器和解扰器的原理图。第10章信道编码 图10.8.6 3级反响移位存放器构成的扰码器和解扰器第10章信道编码 假设输入序列an是信源序列，扰码电路输出序列为bn，根据图10.8.6(a)可知， bn可表示为(10-8-1)经过信道传输，接纳序列为，解扰器输出序列为cn，由解扰器电路可知， cn可表示为 (10-8-2)当传输无过失时， ，由式(10-8-1)和式(10-8-2)可得上式阐明，扰码和解扰是互逆运算。第10章信道编码 例10.8.4 扰码器如图10.8.6(a)所示。当输入的信源序列an=111111111111(全1)时，求扰码器的输出序列bn。解 设反响移位存放器的初始形状为bn-1bn-2bn-3=001，那么扰码器的形状及输出如表10-8-4所示。第10章信道编码 第10章信道编码 由表10-8-4可知，输入全1序列，经扰码器后输出序列中“1、“0趋近于等概。实践运用中，往往采用更长周期的m序列，所以扰乱后的“1、“0序列更接近于随机序列。第10章信道编码 本章小结本章小结信道编码即过失控制编码，是指将信源编信道编码即过失控制编码，是指将信源编码器输出的数字序列人为地按照一定的规律参码器输出的数字序列人为地按照一定的规律参与假设干个码元，以便在接纳端译码器中发现与假设干个码元，以便在接纳端译码器中发现或纠正码元在传输过程中发生的错误。信道编或纠正码元在传输过程中发生的错误。信道编码的目是为了提高数字通讯系统的可靠性。其码的目是为了提高数字通讯系统的可靠性。其付出的代价是降低了数字通讯系统的有效性。付出的代价是降低了数字通讯系统的有效性。 本章首先引入了信道编译码的一些根本概本章首先引入了信道编译码的一些根本概念，如码重、码距及它和纠、检错才干之间的念，如码重、码距及它和纠、检错才干之间的关系。关系。 然后重点讨论了线性分组码，如汉明然后重点讨论了线性分组码，如汉明码、循环码的编译码原理和方法。码、循环码的编译码原理和方法。 最后，引最后，引见了解卷积码及见了解卷积码及m序列的概念。序列的概念。第10章信道编码 习 题1 (7，1)反复反复码假假设用于用于检错，最多能，最多能检出几位出几位错码？假？假设用于用于纠错，最多，最多纠正几正几位位错码？假？假设同同时用于用于检错、纠错，它能，它能检测、纠正几位正几位错码？2 知知(7，3)分分组码的的监视关系式关系式为求其求其监视矩矩阵H、生成矩、生成矩阵G、全部系、全部系统码字、字、纠错才干及才干及编码效率效率。第10章信道编码 3 汉明码的监视矩阵为(1) 求码长n和码字中的信息位数k。(2) 求编码效率。(3) 求生成矩阵G。(4) 假设信息位全为“1，求监视位码元。(5) 检验0100110和0000011能否为码字。假设有错，请指出错误并加以纠正。第10章信道编码 4 一码长n=7的汉明码，监视位数r为多少？信息位数k为多少？编码效率为多少？试设定一种伴随式与错误图样的对照表，并写出监视码元与信息码元之间的关系式。5 知(7，4)循环码的生成多项式g(x)=x3+x+1，求(1) 求典型生成矩阵G和监视矩阵H。(2) 写出系统循环码的全部码字。(3) 列出错误图样与伴随式的对照表。6 试构成周期长度为7的m序列发生器，并求出相应的m序列。第10章信道编码 7 有卷积编码器如以下图所示，求当输入信息序列为1100100011时的编码器输出的码字序列。题7图