第八章第八章 差错控制编码技术差错控制编码技术8.1 差错控制编码的基本概念差错控制编码的基本概念8.2 线性分组码线性分组码8.3 循循 环环 码码8.4 卷卷 积积 码码8.5 网格编码调制（网格编码调制（TCM）8.6 Turbo码码8.7 差错控制编码对系统性能的改善差错控制编码对系统性能的改善8.1 差错控制编码的基本概念差错控制编码的基本概念1. 差错控制的工作方式差错控制的工作方式按按照照噪噪声声或或干干扰扰的的变变化化规规律律，可可把把信信道道分分为为三三类类：随随机机信信道道、突突发发信信道道和和混混合合信信道道。恒恒参参高高斯斯白白噪噪声声信信道道是是典典型型的的随随机机信信道道，其其中中差差错错的的出出现现是是随随机机的的，而而且且错错误误之之间间是是统统计计独独立立的的。具具有有脉脉冲冲干干扰扰的的信信道道是是典典型型的的突突发发信信道道，错错误误是是成成串串成成群群出出现现的的，即在短时间内出现大量错误。即在短时间内出现大量错误。差差错错控控制制的的基基本本工工作作方方式式有有4种种：前前向向纠错、检错重发、混合纠错和反馈校验。纠错、检错重发、混合纠错和反馈校验。（1） 前向纠错方式前向纠错方式前前向向纠纠错错方方式式记记作作FEC。发发端端发发送送能能够够纠纠正正错错误误的的码码，收收端端收收到到信信码码后后自自动动地地纠纠正正传传输输中中的的错错误误。其其特特点点是是单单向向传传输输，实时性好，但译码设备较复杂。实时性好，但译码设备较复杂。（2） 检错重发方式检错重发方式检检错错重重发发方方式式又又称称自自动动请请求求重重传传方方式式，记作记作ARQ。（3） 混合纠错方式混合纠错方式混混合合纠纠错错方方式式记记作作HEC，是是FEC和和ARQ方式的结合。方式的结合。（4） 信息反馈方式信息反馈方式信信息息反反馈馈方方式式记记作作IF，信信息息反反馈馈是是收收端端将将接接收收的的消消息息原原封封不不动动地地送送回回发发端端，由由发发端端将将反反馈馈信信息息和和原原发发送送信信息息进进行行比比较较，发发现现错错误误进进行行重重发发，其其优优点点是是方方法法和和设设备备简单，无需纠（检）错编译系统。简单，无需纠（检）错编译系统。2. 差错控制编码的分类差错控制编码的分类（1） 按按照照差差错错控控制制编编码码的的用用途途不不同同可分为检错码、纠错码和纠删码。可分为检错码、纠错码和纠删码。（2） 按按照照信信息息码码元元和和监监督督码码元元之之间间的函数关系可分为线性码和非线性码。的函数关系可分为线性码和非线性码。（3） 按按照照对对信信息息元元处处理理方方式式的的不不同同可分为分组码和卷积码。可分为分组码和卷积码。（4） 按按照照码码组组中中信信息息码码元元在在编编码码前前后是否相同可分为系统码和非系统码。后是否相同可分为系统码和非系统码。（5） 按按照照纠纠（检检）错错误误的的类类型型可可分分为为纠纠（检检）随随机机错错误误码码、纠纠（检检）突突发发错错误误码码和和既既能能纠纠（检检）随随机机错错误误同同时时又又能能纠纠（检）突发错误码。（检）突发错误码。（6） 按按照照每每个个码码元元的的取取值值可可分分为为二二进码和多进码。进码和多进码。3. 差错控制编码的基本原理差错控制编码的基本原理差差错错编编码码的的基基本本思思想想是是在在被被传传输输信信息息中中增增加加一一些些冗冗余余码码，利利用用附附加加码码元元和和信信息息码码元元之之间间的的约约束束关关系系加加以以校校验验，以以检检测测和和纠纠正正错错误误，增增加加冗冗余余码码的的个个数数可可增增加加纠纠检检错能力。错能力。（1） 码长、码重、码距码长、码重、码距编编码码码码组组的的码码元元总总位位数数称称为为码码组组的的长长度，简称码长。度，简称码长。码码组组中中，“1”码码元元的的数数目目称称为为码码组组的重量，简称码重。的重量，简称码重。两两个个等等长长码码组组之之间间对对应应位位上上码码元元不不同同的数目称为这两个码组的距离，简称码距。的数目称为这两个码组的距离，简称码距。（2） 检错和纠错能力检错和纠错能力 检检测测e个个随随机机错错误误，则则要要求求最最小小码码距距d0e+1； 纠纠正正t个个随随机机错错误误，则则要要求求最最小小码码距距d02t+1； 纠纠正正t个个同同时时检检测测e（et）个个随随机机错误，则要求最小码距错误，则要求最小码距d0t+e+1。（3） 编码效率编码效率用用差差错错控控制制编编码码提提高高通通信信系系统统的的的的可可靠靠性性，是是以以降降低低有有效效性性为为代代价价换换来来的的。定定义编码效率义编码效率R来衡量有效性：来衡量有效性：R=k/n其中，其中，k是信息元的个数，是信息元的个数，n为码长。为码长。4. 常用的几种简单编码常用的几种简单编码（1） 奇偶监督码奇偶监督码奇奇偶偶监监督督码码是是在在原原信信息息码码后后面面附附加加一一个个监监督督元元，使使得得码码组组中中“1”的的个个数数是是奇奇数数或或偶偶数数，或或者者说说，它它是是含含一一个个监监督督元元，码码重重为为奇奇数数或或偶偶数数的的（n，n-1）系系统统分分组组码码。奇偶监督码又分为奇监督码和偶监督码。奇偶监督码又分为奇监督码和偶监督码。（2） 行列监督码行列监督码奇奇偶偶监监督督码码不不能能发发现现偶偶数数个个错错误误。为为了了改改善善这这种种情情况况，引引入入行行列列监监督督码码。这这种种码码不不仅仅对对水水平平（行行）方方向向的的码码元元，而而且且对对垂直（列）方向的码元实施奇偶监督。垂直（列）方向的码元实施奇偶监督。（3） 恒比码恒比码码码字字中中1的的数数目目与与0的的数数目目保保持持恒恒定定比比例例的的码码称称为为恒恒比比码码。由由于于恒恒比比码码中中，每每个个码码组组均均含含有有相相同同数数目目的的1和和0，因因此此恒恒比比码码又又称称等等重重码码，定定1码码。这这种种码码在在检检测测时时，只只要要计计算算接接收收码码元元中中1的的个个数数是是否否与与规规定定的的相相同，就可判断有无错误。同，就可判断有无错误。（4） 群计数码群计数码群群计计数数码码是是将将信信息息码码元元分分组组后后，计计算算每每组组码码元元中中“1”的的个个数数，然然后后将将这这个个数数目目的的二二进进制制表表示示作作为为监监督督码码元元，一一起起送送往往发发送端。送端。8.2 线性分组码线性分组码1. 线性分组码的定义和特点线性分组码的定义和特点线线性性分分组组码码，是是指指信信息息码码元元与与监监督督码码元元之之间间的的关关系系可可以以用用一一组组线线性性方方程程来来表表示示的的分分组组码码，即即在在（n，k）分分组组码码中中，每每一一个个监监督督码码元元都都是是码码组组中中某某些些信信息息码码元元按按模模2和和而而得得到到的的，线线性性分分组组码码是是一一类类重重要要的的纠纠错码，应用很广。错码，应用很广。2. 监督矩阵监督矩阵H和生成矩阵和生成矩阵G（1） 监督矩阵监督矩阵我我们们把把H称称为为监监督督矩矩阵阵，或或称称一一致致校校验验矩矩阵阵，一一旦旦H给给定定，信信息息位位和和监监督督位位之之间间的的关关系系也也就就确确定定了了。H为为 rn阶阶矩矩阵阵，H矩矩阵阵每每行行之之间间是是彼彼此此线线性性无无关关的的。H矩矩阵阵可可分分成成两两部部分分，其其中中P为为rk阶阶矩矩阵阵，Ir为为rr阶阶单单位位阵阵。能能写写成成H=PIr形形式式的的矩矩阵称为典型监督矩阵。阵称为典型监督矩阵。（2） 生成矩阵生成矩阵称称为为生生成成矩矩阵阵，由由G和和信信息息组组就就可可以以产产生生全全部部码码字字。G为为kn阶阶矩矩阵阵，各各行行也也是是线线性性无无关关的的。生生成成矩矩阵阵也也可可以以分分为为两两部部分分：其其中中Q为为kr阶阶矩矩阵阵，Ik为为k阶阶单单位位阵阵，可可以以写写成成式式（8-12）形形式式的的G矩矩阵阵，称称为为典典型型生生成成矩矩阵阵。非非典典型型形形式式的的矩矩阵阵经经过过运运算算也一定可以化为典型矩阵形式。也一定可以化为典型矩阵形式。（3） 监督矩阵监督矩阵H和生成矩阵和生成矩阵G之之间的关系间的关系由由上上可可知知，监监督督矩矩阵阵H和和生生成成矩矩阵阵G之之间间有有一一一一对对应应的的关关系系。由由于于G的的每每一一行行都为码字，因此它必然满足式（都为码字，因此它必然满足式（8-7）HAT=0T即即HGT=0T3. 线性分组码的译码线性分组码的译码伴随伴随式（校正子）式（校正子）S若若某某一一码码字字为为许许用用码码组组，则则它它必必然然满满足足式式（8-7）。利利用用这这一一关关系系，在在接接收收端端将将收收到到的的码码组组和和事事先先与与发发端端约约定定好好的的监监督督矩矩阵阵相相乘乘，看看是是否否为为零零。若若满满足足条条件件，则则认认为为接接收收正正确确；反反之之，则则认认为为传传输输过过程程中中发发生生了了错错误误，进进而而设设法法确确定定错错误误的的数数目目和和位位置。置。令令S=BHT，称为伴随式或校正子。称为伴随式或校正子。S=BHT=（A+E）HT=EHT由由此此可可见见，伴伴随随式式S与与错错误误图图样样E之之间间有有确确定定的的线线性性变变换换关关系系，与与发发送送码码组组A无无关关。接接收收端端译译码码器器的的任任务务就就是是从从伴伴随随式式确确定定错错误误图图样样，然然后后从从接接收收到到的的码码字字中中减减去去错错误误图样。图样。从从以以上上分分析析可可以以得得出出线线性性分分组组码码译译码码的基本步骤：的基本步骤： 计算接收码组计算接收码组B的伴随式的伴随式S； 根根据据S找找出出错错误误图图样样E，判判定定误误码码位置；位置； 根根据据E纠纠正正错错误误，得得到到正正确确的的码码组组A=E+B。4. 汉明码汉明码汉汉明明码码是是一一类类常常见见的的线线性性分分组组码码，是是一一种种能能够够纠纠正正单单个个错错误误的的完完备备码码。要要纠纠正正码码组组中中的的单单个个错错误误，则则要要求求与与单单个个错错误误图图样样对对应应的的伴伴随随式式各各不不相相同同，且且不不能能为为全全零零。若若码码长长为为n，监监督督码码元元的的个个数数为为r，则则要要求求2r-1n。码码组组为为汉汉明明码码时时取取等等号号。即即用用来来纠纠正正单单个个错错误误时时，汉汉明明码码所所用用的的监监督督码码元元个个数最少，效率最高。数最少，效率最高。汉明码的特点如下。汉明码的特点如下。（1） 监监督督码码元元的的个个数数r=n-k，码码长长满满足足n=2r-1，则则k=n-r。r2。（2） 无无论论码码长长n为为多多少少，汉汉明明码码最最小小码距码距d0=3。（3） 其编码效率为其编码效率为=k/n=2r-1-r/2r-1=1-r/n。8.3 循循 环环 码码循循环环码码是是另另一一类类重重要要的的线线性性分分组组码码，它它除除了了具具有有线线性性码码的的一一般般性性质质外外，还还具具有有循循环环性性，即即循循环环码码组组中中任任一一码码组组循循环环移移位位所得的码组仍为该循环码中的一许用码组。所得的码组仍为该循环码中的一许用码组。在在代代数数理理论论中中，为为了了便便于于计计算算，常常用用码码多多项项式式表表示示码码字字。（n，k）循循环环码码的的码码字，其码多项式（以降幂顺序排列）为字，其码多项式（以降幂顺序排列）为A（x）=an-1xn-1+an-2xn-2+a1x+a01. 生成多项式和生成矩阵生成多项式和生成矩阵如如果果一一种种码码的的所所有有码码多多项项式式都都是是多多项项式式g（x）的的倍倍式式，则则称称g（x）为为该该码码的的生生成成多多项项式式。在在（n，k）循循环环码码中中任任意意码码多多项式项式A（x）都是最低次码多项式的倍都是最低次码多项式的倍式。如表式。如表8-5的（的（7，3）循环码中）循环码中g（x）=A1（x）=x4+x3+x2+1循循 环环 码码的的生生成成矩矩阵阵可可以以很很容容易易的的由由生生成成多多项项式式得得到到，常常用用矩矩阵阵的形式表示。的形式表示。2. 监督多项式和监督矩阵监督多项式和监督矩阵为为了了便便于于对对循循环环码码编编译译码码，通通常常还还定定义监督多项式，令义监督多项式，令其其中中g（x）是是常常数数项项为为1的的r次次多多项项式式，是是生成多项式；生成多项式；h（x）是常数项为是常数项为1的的k次多次多项项式式，称称为为监监督督多多项项式式。同同理理，它它的的监监督督矩阵矩阵H3. 循环码的编解码方法和电路循环码的编解码方法和电路（1） 循环码的编码循环码的编码在在编编码码时时，首首先先要要根根据据给给定定的的（n，k）值值选选定定生生成成多多项项式式g（x），即即从从xn+1的的因式中选一个因式中选一个r次多项式作为次多项式作为g（x）。）。根根据据上上述述原原理理，循循环环码码编编码码步步骤骤可可归归纳如下。纳如下。 用用xr乘乘m（x）。这这一一运运算算实实际际上上是是把把信信息息码码后后附附加加上上r个个“0”，给给监监督督位位留留出地方。出地方。 用用g（x）去去除除xrm（x），得得到到商商Q（x）和余式和余式r（x）。）。 编出的码组为编出的码组为A（x）=xrm（x）+r（x）。）。（2） 循环码的译码循环码的译码原则上纠错可按下述步骤进行：原则上纠错可按下述步骤进行： 用用生生成成多多项项式式g（x）去去除除接接收收码码组组B（x）=A（x）+E（x），得得出出余余式式r（x）；）； 按按余余式式r（x）用用查查表表的的方方法法或或通通过过某某种种运运算算得得到到错错误误图图样样E（x），就就可可以以确确定错码位置。定错码位置。 从从B（x）中中减减去去E（x），便便得得到到已纠正错误的原发送码组已纠正错误的原发送码组A（x）。）。8.4 卷卷 积积 码码卷卷积积码码又又称称连连环环码码，是是1955年年提提出出来来的的一一种种纠纠错错码码，它它和和分分组组码码有有明明显显的的区区别别，属于非分组码。属于非分组码。1. 卷积码编码卷积码编码卷卷积积码码常常用用符符号号（n，k，m）表表示示。其其中中，n为为码码长长，k为为码码组组中中信信息息码码元元的的个个数，数，m为相互关联的码组的个数。为相互关联的码组的个数。卷卷积积码码同同样样也也可可以以用用矩矩阵阵的的方方法法描描述述，但但较较抽抽象象。因因此此，采采用用图图解解的的方方法法直直观观描描述述其其编编码码过过程程。常常用用的的图图解解法法有有3种种：树树图图、状态图和格图。状态图和格图。（1） 树图树图树树图图描描述述的的是是在在任任何何数数据据序序列列输输入入时时，码码字字所所有有可可能能的的输输出出。对对应应于于图图8-4所所示示的的（2，1，2）卷卷积积码码的的编编码码电电路路，可可以以画画出出其树图如图其树图如图8-5所示。所示。图图8-4 卷积码（卷积码（2，1，2）编码器）编码器图图8-5（2，1，2）卷积码的树图）卷积码的树图（2） 状态图状态图除除了了用用树树图图表表示示编编码码器器的的工工作作过过程程外外，还还可可以以用用状状态态图图来来描描述述。图图8-6所所示示的的是是该该（2，1，2）卷积编码器的状态图。）卷积编码器的状态图。（3） 格图格图格格图图也也称称网网络络图图或或篱篱笆笆图图，它它由由状状态态图在时间上展开而得到。图在时间上展开而得到。图图8-6 （2，1，2）卷积码的状态图）卷积码的状态图2. 卷积码的译码卷积码的译码卷卷积积码码的的译译码码可可分分为为代代数数译译码码和和概概率率译译码码两两大大类类。卷卷积积码码不不是是分分组组码码，但但仍仍属属于于线线性性码码，同同样样可可由由生生成成矩矩阵阵G和和监监督督矩矩阵阵H来来确确定定。代代数数译译码码就就是是利利用用生生成成矩矩阵阵和和监监督督矩矩阵阵来来译译码码，最最主主要要的的方方法法是是代代数数逻辑译码。逻辑译码。（1） 维特比译码维特比译码维维特特比比译译码码。它它是是一一种种最最大大似似然然译译码码算算法法。最最大大似似然然译译码码算算法法的的基基本本思思路路是是，把把接接收收码码字字与与所所有有可可能能的的码码字字比比较较，选选择择一种码距最小的码字作为解码输出。一种码距最小的码字作为解码输出。（2） 序列译码序列译码当当m很很大大时时，可可以以采采用用序序列列译译码码法法。其过程如下。其过程如下。译译码码先先从从码码树树的的起起始始节节点点开开始始，把把接接收收到到的的第第一一个个子子码码的的n个个码码元元与与自自始始节节点点出出发发的的两两条条分分支支按按照照最最小小汉汉明明距距离离进进行行比比较较，沿沿着着差差异异最最小小的的分分支支走走向向第第二二个个节节点点。在在第第二二个个节节点点上上，译译码码器器仍仍以以同同样样原原理理到到达达下下一一个个节节点点，依依此此类类推推，最最后后得得到到一一条条路路径。径。若若接接收收码码组组有有错错，则则自自某某节节点点开开始始，译译码码器器就就一一直直在在不不正正确确的的路路径径中中行行进进，译译码码也也一一直直错错误误。因因此此，译译码码器器有有一一个个门门限限值值，当当接接收收码码元元与与译译码码器器所所走走的的路路径径上上的的码码元元之之间间的的差差异异总总数数超超过过门门限限值值时时，译译码码器器判判定定有有错错，并并且且返返回回试试走走另另一一分分支支。经经数数次次返返回回找找出出一一条条正正确确的的路路径径，最最后后译译码码输出。输出。8.5 网格编码调制网格编码调制（TCM）引引入入了了编编码码和和调调制制相相结结合合统统一一进进行行设设计计的的方方法法，也也就就是是网网络络编编码码调调制制（Trellis Coded Modulation，TCM）技技术术。它它是是利利用用编编码码效效率率为为n/（n+1）的的卷卷积积码码，并并将将每每一一码码段段映映射射为为2n+1个个调调制制信信号号集集中中的的一一个个信信号，使信号点之间相互依赖。号，使信号点之间相互依赖。它有两个基本特点。它有两个基本特点。（1） 在在信信号号空空间间中中的的信信号号点点数数目目比比无无编编码码的的调调制制情情况况下下对对应应的的信信号号点点数数目目要要多多，这这些些增增加加的的信信号号点点使使编编码码有有了了冗冗余余，而不牺牲带宽。而不牺牲带宽。（2） 采采用用卷卷积积码码的的编编码码规规则则，使使信信号号点点之之间间引引入入相相互互依依赖赖关关系系。仅仅有有某某些些信信号号点点图图样样或或序序列列是是允允许许用用的的信信号号序序列列，并并可可模模型型化化成成为为网网格格状状结结构构，因因此此又又称称为为“格状格状”编码。编码。在在收收端端采采用用维维特特比比算算法法执执行行最最大大似似然然检检测测。编编码码网网格格状状图图中中的的每每一一条条支支路路对对应应于于一一个个子子集集，而而不不是是一一个个信信号号点点。检检测测的的第第一一步步是是确确定定每每个个子子集集中中的的信信号号点点，在在欧欧氏氏距距离离意意义义下下，这这个个子子集集是是最最靠靠近近接接收收信信号的子集。号的子集。图图8-11描描述述了了最最简简单单的的传传输输2比比特特码码字字的的8PSK四四状状态态TCM编编码码方方案案。它它采采用用了了效效率率为为1/2的的卷卷积积码码编编码码器器，对对应应的的格格图图如如图图8-12所示。所示。图图8-11 8PSK四状态四状态TCM编码方案编码方案图图8-12 卷卷积积编编码码网网格格图图8.6 Turbo码码1. Turbo码编码器码编码器典典型型的的Turbo码码编编码码器器结结构构如如图图8-13所所示示。它它由由两两个个成成员员码码编编码码器器、一一个个交交织织器器和和一一个个截截取取复复接接器器组组成成。第第一一个个编编码码器器直直接接对对信信源源信信息息序序列列的的分分组组进进行行编编码码，第第二二个个编编码码器器对对经经过过交交织织器器交交织织后后的的信信息息序序列列的的分分组组进进行行编编码码，最最后后的的编编码码输输出出由由信信息息序序列列和和两两个个编编码码器器产产生生的的校校验验序序列列经经截截取取和复接后得到。和复接后得到。图图8-13 Turbo码编码器码编码器卷卷积积码码编编码码器器在在一一帧帧结结束束时时，通通常常要要加加m（m为为编编码码存存储储长长度度）个个比比特特的的收收尾尾序序列，使编码器返回全列，使编码器返回全0状态。状态。2. 译码器译码器典典型型的的译译码码器器结结构构如如图图8-15所所示示，译译码码器器1完完成成对对一一个个数数据据帧帧的的译译码码并并经经过过交交织织后后，由由译译码码器器2进进行行译译码码，经经过过解解交交织织，由由译译码码器器1完完成成再再译译码码，如如此此反反复复迭迭代代，直直至至正确译码或不能再纠正错误为止。正确译码或不能再纠正错误为止。图图8-15Turbo码译码器码译码器在在Turbo码码出出现现以以前前，编编码码界界对对于于级级联联码码的的次次优优译译码码算算法法进进行行了了大大量量的的研研究究，包包括括多多个个（通通常常是是两两个个）译译码码器器协协同同循循环环译译码码。其其译译码码算算法法可可采采用用逐逐符符号号MAP算算法法，又常被称为又常被称为BCJR算法、算法、BAHL算法。算法。8.7 差错控制编码对系统性能的改善差错控制编码对系统性能的改善将将以以上上两两式式的的结结果果化化成成曲曲线线，如如图图8-16所所示示，当当误误码码组组率率较较小小且且相相同同时时，编编码码系系统统比比无无编编码码系系统统的的约约小小1dB，即即平平均均功功率率可可以以小小1dB，这这是是用用设设备备的的复复杂杂性性换换来来的的。如如果果用用纠纠错错能能力力更更强强的的编编码码，可可期期望望得得到到更更大大的的好好处处，但但设设备备会会更更加加复复杂杂。但但同同时时也也要要看看到到，当当误误码码组组率率较较大大时时，改改善善并不明显。并不明显。图图8-16 有有无无纠纠错错时时误误码码组组率率的的比比较较