第8讲 差错控制编码

1、9.1 概述概述 9.2 常用的几种简单分组码常用的几种简单分组码 9.3 线性分组码线性分组码 9.4 循环码循环码 9.5 卷积码卷积码 *9.6 网格编码调制网格编码调制 9.1.1 9.1.1 信道信道编码编码 9.1.2 9.1.2 差差错错控制方式控制方式 9.1.3 9.1.3 纠错码纠错码的分的分类类 9.1.4 9.1.4 纠错编码纠错编码的基本原理的基本原理 在数字通信中，根据不同的目的，编码可分为在数字通信中，根据不同的目的，编码可分为信源信源编码编码和和信道编码信道编码。信源编码信源编码是为了提高数字信号的有效性以及为了使模拟是为了提高数字信号的有效性以及为了使模拟信号

2、数字化而采取的编码。信号数字化而采取的编码。信道编码信道编码是为了降低误码率，是为了降低误码率， 提高数字通信的可靠性而提高数字通信的可靠性而采取的编码。采取的编码。9.1.2 差错控制方式差错控制方式 图图 9-1 差错控制方式差错控制方式 发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号 检错重发又称自动请求重传方式，记作检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 特点：需要反馈信道，译码设备简单，对突发错误和信道干特点：需要反馈信道，译码设备简单，对突发错误和信道干扰较严扰较严重

3、时有效，重时有效， 但实时性差，主要在计算机数据通信中得但实时性差，主要在计算机数据通信中得到应用。到应用。 海上通信海上通信NBDP 1. 检错重发方式检错重发方式 前向纠错方式记作前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设传输中的错误。其特点是单向传输，实时性好，但译码设备较备较复杂。复杂。 海上卫星通信海上卫星通信Inmarsat-A 2. 前向纠错方式前向纠错方式 混合纠错方式记作混合纠错方式记作HEC(H

4、ybrid ErrorCorrection)是是FEC和和ARQ方式的结合。发端发送具有自动纠错同时又具有方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。这种能力，但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，因此， 近年来得到广泛应用

5、。近年来得到广泛应用。海上卫星通信海上卫星通信 Inmarsat-C 3. 3. 混合纠错方式混合纠错方式 另外，按照噪声或干扰的变化规律，可把信道分为三另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。类：随机信道、突发信道和混合信道。恒参高斯恒参高斯白噪声信道是典型的随机信道，其中差错的出现白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的具有脉冲干扰的信道是典型的突发信道突发信道， 错误是成串成群错误是成串成群出现的，即在短时间内出现大量错误。出现的，即在短时间内出现大

6、量错误。短波信道和对流层散射信道是短波信道和对流层散射信道是混合信道混合信道的典型例子，随机的典型例子，随机错误错误和成串错误都占有相当比例。对于不同类型的信道，和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。应采用不同的差错控制方式。 (1) 根据纠错码各码组信息元和监督元的函数关系，可分根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分组码和卷

7、积码。根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，与本组的信息元有关， 而且还与前面若干组的信息元有关。而且还与前面若干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码以检根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检纠错码以纠错为目的，一定能检错。错。 1. 分组码分组码 分组码一般可用分组码一般可用(n,k)表示。其中，表示。其中，k是每组二进制信息是每组二进制信

8、息码元的数目，码元的数目，n是编码码组的码元总位数，又称为码组长度，是编码码组的码元总位数，又称为码组长度，简称码长。简称码长。n-k=r为每个码组中的监督码元数目。简单地说，为每个码组中的监督码元数目。简单地说，分组码是对每段分组码是对每段k位长的信息组以一定的规则增加位长的信息组以一定的规则增加r个监督元，个监督元， 组成长为组成长为n的码字。在二进制情况下，共有的码字。在二进制情况下，共有2k个不同的信息个不同的信息组，相应地可得到组，相应地可得到2k个不同的码字，称为许用码个不同的码字，称为许用码组。其余组。其余 2n-2k个码字未被选用，称为禁用码组。个码字未被选用，称为禁用码组。

9、krn 在 分 组 码 中 ， 非 零 码 元 的 数 目 称 为 码 字 的在 分 组 码 中 ， 非 零 码 元 的 数 目 称 为 码 字 的 汉 明汉 明(Hamming)重量重量， 简称简称码重码重。例如，码字。例如，码字 10110，码重，码重w=3。 两个等长码组之间相应位取值不同的数目称为这两个码两个等长码组之间相应位取值不同的数目称为这两个码组的组的汉明汉明(Hamming)距离距离， 简称简称码距码距。例如。例如 11000 与与 10011之间的距离之间的距离d=3。码组集中任意两个码字之间距离的最小值。码组集中任意两个码字之间距离的最小值称为称为码的最小距离码的最小距离

10、，用，用d表示。最小码距是码的一个重要参表示。最小码距是码的一个重要参数，数， 它是衡量码检错、纠它是衡量码检错、纠错能力的依据。错能力的依据。 2. 检错和纠错能力检错和纠错能力 若分组码码字中的监督元在信息元之后，而且是信息元的若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，简单重复， 则称该分组码为则称该分组码为重复码重复码。它是一种简单实用的检错。它是一种简单实用的检错码，码， 并有一定的纠错能力。例如并有一定的纠错能力。例如(2,1)重复码，两个许用码组是重复码，两个许用码组是 00 与与 11，d0=2，收端译码，出现，收端译码，出现 01、10 禁用码组时，可以发禁用

11、码组时，可以发现传输中的一位错误。如果是现传输中的一位错误。如果是(3,1)重复码，两个许用码组是重复码，两个许用码组是 000 与与111, d0=3; 当收端出现两个或三个当收端出现两个或三个 1 时，判为时，判为 1，否则判，否则判为为 0。此时，可以纠正单个错误，或者该码可以检出两。此时，可以纠正单个错误，或者该码可以检出两个错误。个错误。 码的最小距离码的最小距离d0直接关系着码的检错和纠错能力；任一直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内分组码，若要在码字内: (1) 检测检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d0e+1; (2)

12、 纠正纠正t个随机错误，个随机错误， 则要求码的最小距离则要求码的最小距离d02t+1; (3) 纠正纠正t个同时检测个同时检测e(t)个随机错误，则要求码的最小距个随机错误，则要求码的最小距离离d0t+e+1。 t1eAB 3. 编码效率编码效率 用差错控制编码提高通信系统的可靠性，用差错控制编码提高通信系统的可靠性， 是是以降低有效以降低有效性为代价换来的性为代价换来的。我们定义编码效率。我们定义编码效率R来衡量有效性来衡量有效性:R=k/n其中其中, k是信息元的个数，是信息元的个数，n为码长。为码长。 对纠错码的基本要求是对纠错码的基本要求是: 检错和纠错能力尽量强；检错和纠错能力尽量

13、强； 编码编码效率尽量高；编码规律尽量简单效率尽量高；编码规律尽量简单。实际中要根据具体指标要。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。求，保证有一定纠、检错能力和编码效率，并且易于实现。 奇偶监督码是在原信息码后面附加一个监督元，奇偶监督码是在原信息码后面附加一个监督元， 使得码使得码组中组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇系统分组码。奇偶监督码又分为奇监督码和偶监督码。监督码和偶监督码。 设码字设码字A=an-1

14、,an-2,a1,a0，对偶监督码有，对偶监督码有 12100nnaaaa-排排= 奇监督码情况相似，奇监督码情况相似， 只是码组中只是码组中“1”的数目为奇数，的数目为奇数， 即即满足条件满足条件 1201nnaaa-排而检错能力与偶监督码相同。而检错能力与偶监督码相同。 奇偶监督码的编码效率奇偶监督码的编码效率R为为 (1) /Rnn=-9.2.2 行列监督码行列监督码 图图 9-2 (66,50)行列监督码行列监督码 1100101000001000011010011110000111001110000010101010101110001111009.2.3 恒比码恒比码 码字中码字中

15、1 的数目与的数目与 0 的数目保持恒定比例的码称为恒比码。的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的由于恒比码中，每个码组均含有相同数目的 1 和和 0，因此恒比，因此恒比码又称等重码，定码又称等重码，定 1 码。这种码在检测时，只要计算接收码元码。这种码在检测时，只要计算接收码元中中 1 的数目是否正确，就知道有无错误。的数目是否正确，就知道有无错误。 目前我国电传通信中普遍采用目前我国电传通信中普遍采用 3 2 码，又称码，又称“5 中取中取 3”的恒比码，即每个码组的长度为的恒比码，即每个码组的长度为 5，其中，其中 3 个个“1”。这时可能。这时可能编

16、成的不同码组数目等于从编成的不同码组数目等于从 5 中取中取 3 的组合数的组合数 10，这，这 10 个许个许用码组恰好可表示用码组恰好可表示 10 个阿拉伯数字，如表个阿拉伯数字，如表 9 - 1 所示。而每个所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。我国汉字电报的差错率大为降低。 表表 9-1 3 2 恒比码恒比码 现以现以(7,4)分组码为例来说明线性分组码的特点。设其码字分组码为例来说明线性分组码的特点。设其码字为为A=a6 a5 a4 a3 a2 a1 a0，其中前，其中

17、前 4 位是信息元，后位是信息元，后 3 位是位是监督元，监督元， 可用下列线性方程组来描可用下列线性方程组来描述该分组码，产生监督元。述该分组码，产生监督元。 265416530643aaaaaaaaaaaa=+=+=+ 表表 9-2 (7,4)码的码字表码的码字表 9.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 其中其中,P为为rk阶矩阵，阶矩阵，Ir为为rr阶单位矩阵。可以写成阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型监督矩阵。形式的矩阵称为典型监督矩阵。 HAT=0T，说明，说明H矩阵与矩阵与码字的转置乘积必为零，可以用来码字的转置乘积必为零，可以用来作为判断接收码字作为

18、判断接收码字A是否出错的依据。是否出错的依据。 并简记为并简记为 若把监督方程补充为下列方程若把监督方程补充为下列方程 可改写为矩阵形式可改写为矩阵形式 1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1G轾犏犏犏=犏犏犏犏臌kGIQ=1 1 11 1 01 0 10 1 1TQP轾犏犏犏=犏犏犏犏臌9.3.3 伴随式伴随式(校正子校正子)S 设发送码组设发送码组A=an-1,an-2,a1,a0，在传输过程中可能发，在传输过程中可能发生误码。接收码组生误码。接收码组B=bn-1,bn-2,b1,b0，则收发码组之差定，则收发码组之差定义为

19、错误图样义为错误图样E， 也称为误差矢量，也称为误差矢量， 即即 E=B - A 其中其中E=en-1,en-2,e1,e0，且，且 01ie= 当当bi=ai 当当biai BAE=+令令S=BHT，称为伴随式或校正子。，称为伴随式或校正子。 ()TTTTTSBHAE HAHEHEH=+=+=表表 9-3 (7,4)码码S与与E的对应关系的对应关系 表表 9-4 (7,3)循环码循环码 在代数理论中，为了便于计算，常用码多项式表示码字。在代数理论中，为了便于计算，常用码多项式表示码字。(n,k)循环码的码字，其码多循环码的码字，其码多项式项式(以降幂顺序排列以降幂顺序排列)为为 121210

20、( )nnnnA xaxaxa xa-=+9.4.1 生成多项式及生成矩阵生成多项式及生成矩阵 如果一种码的所有码多项式都是多项式如果一种码的所有码多项式都是多项式g(x)的倍式，则称的倍式，则称g(x)为该码的生成多项式。在为该码的生成多项式。在(n,k)循环码中任意码多项式循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表都是最低次码多项式的倍式。如表 9-4 的的(7,3)循循环码中，环码中， 2431( )( )1g xA xxxx=+02327( )0( )( )(1)( )( )( )( )( )A xg xA xxg xA xx g xA xxg x=+=其它码多项式都是

21、g(x)的倍式， 即 循环码的生成矩阵常用多项式的形式来表示 111( )1rrrg xxgxg x-=+12( )( )( )( )( )kkxg xxg xG xxg xg x-轾犏犏犏犏=犏犏犏犏犏臌例如(7,3)循环码，n=7, k=3, r=4, 其生成多项式及生成矩阵分别为 9.4.2 监督多项式及监督矩阵监督多项式及监督矩阵 为了便于对循环码编译码，通常还定义监督多项式， 令 1111( )1( )nkkkxh xxhxh xg x-+=+其中g(x)是常数项为 1 的r次多项式，是生成多项式；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H 1*( )

22、( )*( )*( )nkxhxH xxhxhx-轾犏犏犏=犏犏犏犏臌是h(x)的逆多项式。例如(9，3)循环码，g(x)=x4+x3+x2+1，则 其中 12121*( )1kkkkhxxh xh xhx-=+73231( )1( )* ( )1xh xxxg xhxxx+=+=+643532423( )1xxxxxxH xxxxxx轾+犏犏+犏=犏+犏犏犏+臌1 0 1 1 0 0 00 1 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1H轾犏犏犏=犏犏犏犏臌9.4.3 编码方法和电路编码方法和电路 在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应

23、在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为 21123( )kkm xaa xa xa x-=+循环码的码多项式可表示为 ( )( )( )rA xxm xR x=+图 9-3 (7,3)循环码编码电路 D0D1D2D3门1门2输入信息组输出码字1表表 9-5 (7,3)循环码的编码过程循环码的编码过程 9.4.4 译码方法和电路译码方法和电路 图 9-4 (7,3)循环码译码电路 D0D1D2D37级缓存器接收码组B输出码组A&9.5.1 基本概念基本概念 图 9-5 卷积码(2,1,2)编码器 m1m2数据输入码字输出S1S2S3C1C2 起始状态

24、，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定 1123213CSSSCSS=排= 表 9-6 (2,1,2)编码器的工作过程 9.5.2 卷积码的描述卷积码的描述 1. 树图树图 图图 9-6 (2,1,2)码的树图码的树图 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a1100数码起点状态a00b01c10d11上半部下半部数码11012. 状态图状态图 图 9 -7 (2,1,2)

25、码的状态图 a00b01c10d11cbad01011111001000103. 格图格图 图 9-8 (2,1,2)码的格图 a00起点aaaaaabbbccccbbcbddddd0000000000000000001001010101010101101010101111111111111010101001019.5.3 卷积码的译码卷积码的译码 1. 维特比译码维特比译码 图图 9-9 维特比译码格图维特比译码格图 图79起点d80100(4)cba700(3)6500(3)4300(3)200(2)10 00(1)级11(1)11(3)11(3)11(3)10(2)10(4)00(3)01(3)01(3)10(3)10(3)10(3)01(1)01(1)01(5)00(2)11(2)收码01011010010001解码11010000 2. 序列译码序列译码 当m很大时，可以采用序列译码法。 其过程如下： 译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较， 沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后