第8章差错控制编码技术

1、按照噪声或干扰的变化规律，可把信道分按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。即在短时间内出现大量错误。差错控制的基本工作方式有差错控制的基本工作方式有4种：前向种：前向纠错、检错重发、混合纠错和反馈校验。纠错、检错

2、重发、混合纠错和反馈校验。前向纠错方式记作前向纠错方式记作FEC。发端发送能发端发送能够纠正错误的码，收端收到信码后自动地够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。实时性好，但译码设备较复杂。检错重发方式又称自动请求重传方式，检错重发方式又称自动请求重传方式，记作记作ARQ。混合纠错方式记作混合纠错方式记作HEC，是是FEC和和ARQ方式的结合。方式的结合。信息反馈方式记作信息反馈方式记作IF，信息反馈是收信息反馈是收端将接收的消息原封不动地送回发端，由端将接收的消息原封不动地送回发端，由发端将反馈信

3、息和原发送信息进行比较，发端将反馈信息和原发送信息进行比较，发现错误进行重发，其优点是方法和设备发现错误进行重发，其优点是方法和设备简单，无需纠（检）错编译系统。简单，无需纠（检）错编译系统。（1） 按照差错控制编码的用途不同按照差错控制编码的用途不同可分为检错码、纠错码和纠删码。可分为检错码、纠错码和纠删码。（2） 按照信息码元和监督码元之间按照信息码元和监督码元之间的函数关系可分为线性码和非线性码。的函数关系可分为线性码和非线性码。（3） 按照对信息元处理方式的不同按照对信息元处理方式的不同可分为分组码和卷积码。可分为分组码和卷积码。（4） 按照码组中信息码元在编码前按照码组中信息码元在编

4、码前后是否相同可分为系统码和非系统码。后是否相同可分为系统码和非系统码。（5） 按照纠（检）错误的类型可分按照纠（检）错误的类型可分为纠（检）随机错误码、纠（检）突发错为纠（检）随机错误码、纠（检）突发错误码和既能纠（检）随机错误同时又能纠误码和既能纠（检）随机错误同时又能纠（检）突发错误码。（检）突发错误码。（6） 按照每个码元的取值可分为二按照每个码元的取值可分为二进码和多进码。进码和多进码。差错编码的基本思想是在被传输信息差错编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和码元之间的约束关系加以校验，

5、以检测和纠正错误，增加冗余码的个数可增加纠检纠正错误，增加冗余码的个数可增加纠检错能力。错能力。编码码组的码元总位数称为码组的长编码码组的码元总位数称为码组的长度，简称码长。度，简称码长。码组中，码组中，“1”码元的数目称为码组码元的数目称为码组的重量，简称码重。的重量，简称码重。两个等长码组之间对应位上码元不同两个等长码组之间对应位上码元不同的数目称为这两个码组的距离，简称码距。的数目称为这两个码组的距离，简称码距。 检测检测e个随机错误，则要求最小码个随机错误，则要求最小码距距d0e+1； 纠正纠正t个随机错误，则要求最小码个随机错误，则要求最小码距距d02t+1； 纠正纠正t个同时检测个

6、同时检测e（et）个随机个随机错误，则要求最小码距错误，则要求最小码距d0t+e+1。用差错控制编码提高通信系统的的可用差错控制编码提高通信系统的的可靠性，是以降低有效性为代价换来的。定靠性，是以降低有效性为代价换来的。定义编码效率义编码效率R来衡量有效性：来衡量有效性：R=k/n其中，其中，k是信息元的个数，是信息元的个数，n为码长。为码长。奇偶监督码是在原信息码后面附加一奇偶监督码是在原信息码后面附加一个监督元，使得码组中个监督元，使得码组中“1”的个数是奇数的个数是奇数或偶数，或者说，它是含一个监督元，码或偶数，或者说，它是含一个监督元，码重为奇数或偶数的（重为奇数或偶数的（n，n-1）

7、系统分组码。系统分组码。奇偶监督码又分为奇监督码和偶监督码。奇偶监督码又分为奇监督码和偶监督码。奇偶监督码不能发现偶数个错误。为奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。这种了改善这种情况，引入行列监督码。这种码不仅对水平（行）方向的码元，而且对码不仅对水平（行）方向的码元，而且对垂直（列）方向的码元实施奇偶监督。垂直（列）方向的码元实施奇偶监督。码字中码字中1的数目与的数目与0的数目保持恒定比的数目保持恒定比例的码称为恒比码。由于恒比码中，每个例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的码组均含有相同数目的1和和0，因此恒比码，因此恒比码又称等重码，定又称等

8、重码，定1码。这种码在检测时，只码。这种码在检测时，只要计算接收码元中要计算接收码元中1的个数是否与规定的相的个数是否与规定的相同，就可判断有无错误。同，就可判断有无错误。群计数码是将信息码元分组后，计算群计数码是将信息码元分组后，计算每组码元中每组码元中“1”的个数，然后将这个数目的个数，然后将这个数目的二进制表示作为监督码元，一起送往发的二进制表示作为监督码元，一起送往发送端。送端。线性分组码，是指信息码元与监督码线性分组码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示元之间的关系可以用一组线性方程来表示的分组码，即在（的分组码，即在（n，k）分组码中，每一分组码中，每一个监督

9、码元都是码组中某些信息码元按模个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的纠和而得到的，线性分组码是一类重要的纠错码，应用很广。错码，应用很广。我们把我们把H称为监督矩阵，或称一致校称为监督矩阵，或称一致校验矩阵，一旦验矩阵，一旦H给定，信息位和监督位之给定，信息位和监督位之间的关系也就确定了。间的关系也就确定了。H为为 rn阶矩阵，阶矩阵，H矩阵每行之间是彼此线性无关的。矩阵每行之间是彼此线性无关的。H矩阵矩阵可分成两部分，其中可分成两部分，其中P为为rk阶矩阵，阶矩阵，Ir为为rr阶单位阵。能写成阶单位阵。能写成H=PIr形式的矩形式的矩阵称为典型监督矩阵。阵称

10、为典型监督矩阵。称为生成矩阵，由称为生成矩阵，由G和信息组就可以和信息组就可以产生全部码字。产生全部码字。G为为kn阶矩阵，各行也阶矩阵，各行也是线性无关的。生成矩阵也可以分为两部是线性无关的。生成矩阵也可以分为两部分：其中分：其中Q为为kr阶矩阵，阶矩阵，Ik为为k阶单位阶单位阵，可以写成式（阵，可以写成式（8-12）形式的）形式的G矩阵，称矩阵，称为典型生成矩阵。非典型形式的矩阵经过为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。运算也一定可以化为典型矩阵形式。由上可知，监督矩阵由上可知，监督矩阵H和生成矩阵和生成矩阵G之间有一一对应的关系。由于之间有一一对应的关系。由

11、于G的每一行的每一行都为码字，因此它必然满足式（都为码字，因此它必然满足式（8-7）即即若某一码字为许用码组，则它必然满若某一码字为许用码组，则它必然满足式（足式（8-7）。利用这一关系，在接收端将）。利用这一关系，在接收端将收到的码组和事先与发端约定好的监督矩收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位生了错误，进而设法确定错误的数目和位置。置。令令S=BHT，称为伴随式或校正子。称为伴随式或校正子。S=BHT=（A+E）

12、HT=EHT由此可见，伴随式由此可见，伴随式S与错误图样与错误图样E之间之间有确定的线性变换关系，与发送码组有确定的线性变换关系，与发送码组A无无关。接收端译码器的任务就是从伴随式确关。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去定错误图样，然后从接收到的码字中减去错误图样。错误图样。从以上分析可以得出线性分组码译码从以上分析可以得出线性分组码译码的基本步骤：的基本步骤： 计算接收码组计算接收码组B的伴随式的伴随式S； 根据根据S找出错误图样找出错误图样E，判定误码判定误码位置；位置； 根据根据E纠正错误，得到正确的码组纠正错误，得到正确的码组A=E+B。汉明码是一类常

13、见的线性分组码，是汉明码是一类常见的线性分组码，是一种能够纠正单个错误的完备码。要纠正一种能够纠正单个错误的完备码。要纠正码组中的单个错误，则要求与单个错误图码组中的单个错误，则要求与单个错误图样对应的伴随式各不相同，且不能为全零。样对应的伴随式各不相同，且不能为全零。若码长为若码长为n，监督码元的个数为监督码元的个数为r，则要求则要求2r-1n。码组为汉明码时取等号。即用来码组为汉明码时取等号。即用来纠正单个错误时，汉明码所用的监督码元纠正单个错误时，汉明码所用的监督码元个数最少，效率最高。个数最少，效率最高。汉明码的特点如下。汉明码的特点如下。（1） 监督码元的个数监督码元的个数r=n-k

14、，码长满码长满足足n=2r-1，则则k=n-r。r2。（2） 无论码长无论码长n为多少，汉明码最小为多少，汉明码最小码距码距d0=3。（3） 其编码效率为其编码效率为=k/n=2r-1-r/2r-1=1-r/n。循环码是另一类重要的线性分组码，循环码是另一类重要的线性分组码，它除了具有线性码的一般性质外，还具有它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。所得的码组仍为该循环码中的一许用码组。在代数理论中，为了便于计算，常用在代数理论中，为了便于计算，常用码多项式表示码字。（码多项式表示码字。（

15、n，k）循环码的码循环码的码字，其码多项式（以降幂顺序排列）为字，其码多项式（以降幂顺序排列）为如果一种码的所有码多项式都是多项如果一种码的所有码多项式都是多项式式g（x）的倍式，则称的倍式，则称g（x）为该码的生为该码的生成多项式。在（成多项式。在（n，k）循环码中任意码多循环码中任意码多项式项式A（x）都是最低次码多项式的倍都是最低次码多项式的倍式。如表式。如表8-5的（的（7，3）循环码中）循环码中g（x）=A1（x）=x4+x3+x2+1循 环 码循 环 码的生成矩阵可的生成矩阵可以很容易的由以很容易的由生成多项式得生成多项式得到，常用矩阵到，常用矩阵的形式表示。的形式表示。)()()

16、()()(21xgxxgxgxxgxxGkk为了便于对循环码编译码，通常还定为了便于对循环码编译码，通常还定义监督多项式，令义监督多项式，令其中其中g（x）是常数项为是常数项为1的的r次多项式，是次多项式，是生成多项式；生成多项式；h（x）是常数项为是常数项为1的的k次多次多项式，称为监督多项式。同理，它的监督项式，称为监督多项式。同理，它的监督矩阵矩阵H1)(1)(111xhxhxxgxxhkkkn在编码时，首先要根据给定的（在编码时，首先要根据给定的（n，k）值选定生成多项式值选定生成多项式g（x），），即从即从xn+1的因的因式中选一个式中选一个r次多项式作为次多项式作为g（x）。）。根

17、据上述原理，循环码编码步骤可归根据上述原理，循环码编码步骤可归纳如下。纳如下。 用用xr乘乘m（x）。）。这一运算实际上这一运算实际上是把信息码后附加上是把信息码后附加上r个个“0”，给监督位，给监督位留出地方。留出地方。 用用g（x）去除去除xrm（x），），得到商得到商Q（x）和余式和余式r（x）。）。 编出的码组为编出的码组为A（x）=xrm（x）+r（x）。）。原则上纠错可按下述步骤进行：原则上纠错可按下述步骤进行： 用生成多项式用生成多项式g（x）去除接收码去除接收码组组B（x）=A（x）+E（x），），得出余式得出余式r（x）；）； 按余式按余式r（x）用查表的方法或通用查表的方法

18、或通过某种运算得到错误图样过某种运算得到错误图样E（x），），就可以就可以确定错码位置。确定错码位置。 从从B（x）中减去中减去E（x），），便得到便得到已纠正错误的原发送码组已纠正错误的原发送码组A（x）。）。卷积码又称连环码，是卷积码又称连环码，是1955年提出来年提出来的一种纠错码，它和分组码有明显的区别，的一种纠错码，它和分组码有明显的区别，属于非分组码。属于非分组码。卷积码常用符号（卷积码常用符号（n，k，m）表示。表示。其中，其中，n为码长，为码长，k为码组中信息码元的个为码组中信息码元的个数，数，m为相互关联的码组的个数。为相互关联的码组的个数。卷积码同样也可以用矩阵的方法描述，

19、卷积码同样也可以用矩阵的方法描述，但较抽象。因此，采用图解的方法直观描但较抽象。因此，采用图解的方法直观描述其编码过程。常用的图解法有述其编码过程。常用的图解法有3种：树图、种：树图、状态图和格图。状态图和格图。树图描述的是在任何数据序列输入时，树图描述的是在任何数据序列输入时，码字所有可能的输出。对应于图码字所有可能的输出。对应于图8-4所示的所示的（2，1，2）卷积码的编码电路，可以画出）卷积码的编码电路，可以画出其树图如图其树图如图8-5所示。所示。图图8-4 卷积码（卷积码（2，1，2）编码器）编码器图图8-5（2，1，2）卷积码的树图）卷积码的树图除了用树图表示编码器的工作过程外，除

20、了用树图表示编码器的工作过程外，还可以用状态图来描述。图还可以用状态图来描述。图8-6所示的是该所示的是该（2，1，2）卷积编码器的状态图。）卷积编码器的状态图。格图也称网络图或篱笆图，它由状态格图也称网络图或篱笆图，它由状态图在时间上展开而得到。图在时间上展开而得到。图图8-6 （2，1，2）卷积码的状态图）卷积码的状态图卷积码的译码可分为代数译码和概率卷积码的译码可分为代数译码和概率译码两大类。卷积码不是分组码，但仍属译码两大类。卷积码不是分组码，但仍属于线性码，同样可由生成矩阵于线性码，同样可由生成矩阵G和监督矩和监督矩阵阵H来确定。代数译码就是利用生成矩阵来确定。代数译码就是利用生成矩

21、阵和监督矩阵来译码，最主要的方法是代数和监督矩阵来译码，最主要的方法是代数逻辑译码。逻辑译码。维特比译码。它是一种最大似然译码维特比译码。它是一种最大似然译码算法。最大似然译码算法的基本思路是，算法。最大似然译码算法的基本思路是，把接收码字与所有可能的码字比较，选择把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。一种码距最小的码字作为解码输出。当当m很大时，可以采用序列译码法。很大时，可以采用序列译码法。其过程如下。其过程如下。译码先从码树的起始节点开始，把接译码先从码树的起始节点开始，把接收到的第一个子码的收到的第一个子码的n个码元与自始节点出个码元与自始节点出发的两条分

22、支按照最小汉明距离进行比较，发的两条分支按照最小汉明距离进行比较，沿着差异最小的分支走向第二个节点。在沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达第二个节点上，译码器仍以同样原理到达下一个节点，依此类推，最后得到一条路下一个节点，依此类推，最后得到一条路径。径。若接收码组有错，则自某节点开始，若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时

23、，译码码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码数次返回找出一条正确的路径，最后译码输出。输出。引入了编码和调制相结合统一进行设引入了编码和调制相结合统一进行设计的方法，也就是网络编码调制（计的方法，也就是网络编码调制（Trellis Coded Modulation，TCM）技术。它是利技术。它是利用编码效率为用编码效率为n/（n+1）的卷积码，并将每的卷积码，并将每一码段映射为一码段映射为2n+1个调制信号集中的一个信个调制信号集中的一个信号，使信号点之间相互依赖。号，使信号点之间相互依赖

24、。它有两个基本特点。它有两个基本特点。（1） 在信号空间中的信号点数目比在信号空间中的信号点数目比无编码的调制情况下对应的信号点数目要无编码的调制情况下对应的信号点数目要多，这些增加的信号点使编码有了冗余，多，这些增加的信号点使编码有了冗余，而不牺牲带宽。而不牺牲带宽。（2） 采用卷积码的编码规则，使信采用卷积码的编码规则，使信号点之间引入相互依赖关系。仅有某些信号点之间引入相互依赖关系。仅有某些信号点图样或序列是允许用的信号序列，并号点图样或序列是允许用的信号序列，并可模型化成为网格状结构，因此又称为可模型化成为网格状结构，因此又称为“格状格状”编码。编码。在收端采用维特比算法执行最大似然在

25、收端采用维特比算法执行最大似然检测。编码网格状图中的每一条支路对应检测。编码网格状图中的每一条支路对应于一个子集，而不是一个信号点。检测的于一个子集，而不是一个信号点。检测的第一步是确定每个子集中的信号点，在欧第一步是确定每个子集中的信号点，在欧氏距离意义下，这个子集是最靠近接收信氏距离意义下，这个子集是最靠近接收信号的子集。号的子集。图图8-11描述了最简单的传输描述了最简单的传输2比特码字比特码字的的8PSK四状态四状态TCM编码方案。它采用了编码方案。它采用了效率为效率为1/2的卷积码编码器，对应的格图如的卷积码编码器，对应的格图如图图8-12所示。所示。图图8-11 8PSK四状态四状态TCM编码方案编码方案图图8-12 卷积编码网格图卷积编码网格图典型的典型的Turbo码编码器结构如图码编码器结构如图8-13所所示。它由两个成员码编码器、一个交织器示。它由两个成员码编码器、一个交织器和一个截取复接器组成。第一个编码器直和一个截取复接器组成。第一个编码器直接对信源信息序列的分组进行编码，第二接对信源信息序列的分组进行编码，第二个编码器对经过交织器交织后的信息序列个编码器对经过交