第10章 差错控制编码

1、第第 10 10 章章 差错控制编码差错控制编码 10.1 概述概述 10.2 检错与纠错原理检错与纠错原理 10.3 简单分组码简单分组码 10.4 线性分组码线性分组码 10.5 循环码循环码 10.6 卷积码卷积码 10.1 概概 述述 10.1.1 信源编码与信道编码信源编码与信道编码 在数字通信中，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码。10.1.2 10.1.2 差错控制方式差错控制方式常用的差错控制方式有三种：检错重发、前向纠错和混合纠错。 1. 检错重发方

2、式检错重发方式 检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发。其特点是需要反馈信道，译码设备简单，但实时性差。 2. 前向纠错方式前向纠错方式 前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。 3. 混合纠错方式混合纠错方式 混合纠错方式记作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的结

3、合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广泛应用。 10.2.1纠错码的分类纠错码的分类 (1) 根据码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关， 而且还与前面若

4、干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。 10.2检错与纠错原理检错与纠错原理 1. 分组码分组码 分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。 10.2.2检错与纠错的原理检错与纠错的原理 在分组码中，非零码元的数目称为码字的汉明重量， 简称码重。例如，码字 10

5、110，码重w=3。 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离， 简称码距。例如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d表示。最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据。 2. 检错和纠错能力检错和纠错能力 若分组码码字中的监督元在信息元之后，而且是信息元的简单重复， 则称该分组码为重复码。它是一种简单实用的检错码， 并有一定的纠错能力。例如(2,1)重复码，两个许用码组是 00 与 11，d0=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。如果是(3

6、,1)重复码，两个许用码组是 000 与111, d0=3; 当收端出现两个或三个 1 时，判为 1，否则判为 0。此时，可以纠正单个错误，或者该码可以检出两个错误。 码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内: (1) 检测e个随机错误，则要求码的最小距离d0e+1; (2) 纠正t个随机错误， 则要求码的最小距离d02t+1; (3) 纠正t个同时检测e(t)个随机错误，则要求码的最小距离d0t+e+1。 3. 编码效率编码效率 用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。定义编码效率R来衡量有效性:其中, k是信息元的个数，n为

7、码长。 对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。nkR def10.2.1 奇偶监督码奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元， 使得码组中“1”的个数是奇数或偶数。它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。 10.3简单分组码简单分组码设码字A=an-1,an-2,a1,a0，对偶监督码有 00121aaaann 奇监督码情况相似， 只是码组中“1”的数目为奇数， 即满足条件 1021aaann而检错能力与偶监督码相同。 奇偶监督码的编码效率R为 nnR/ ) 1( 10.3.3 1

8、0.3.3 行列监督码行列监督码 奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。这种码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶监督。这种码既可以逐行传输，也可以逐列传输。一般地，LM个信息元附加L+M+1个监督元，组成(LM+L+M+1,LM)行列监督码的一个码字(L+1行，M+1列)。这种码具有较强的检测能力，适于检测突发错误，还可用于纠错。 110010100000100001101001111000011100111000001010101010111000111100(66,50)行列监督码 10.3.5 恒比码恒比码 码字中 1 的数目与 0

9、的数目保持恒定比例的码称为恒比码。 这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。 目前我国电传通信中普遍采用 3 2 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。3 2 恒比码恒比码 10.4 线线 性性 分分 组组 码码 10.4.1基本概念基本概念 在(n,k)分组码中，若每一个监督元都是码组中某些信息元按模二加而得到的，即监督元是按线性关系相加而得到的，则称为线性分组码。 现以(7,3)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 3 位是信息元，后 4 位是监督元， 可用下

10、列线性方程组来描述该分组码，产生监督元。 4445556660123aaaaaaaaaaaaa码 元 序号 信息元 监督元 0 000 0000 1 001 1101 2 010 0111 3 011 1010 4 100 1110 5 101 0011 6 110 1001 7 111 0100 （7，3）分组码的八个码字 长度为n的码组共有2n个，但线性分组码的码字共有2k个许用码组，剩余的是禁用码组。 10.4.2汉明汉明(Hamming)码码汉明码是一种用来纠正单个错误的线性分组码，已作为差错控制码广泛用于数字通信和数据存储系统中。一般来说，若码长为n，信息位为k，则监督元为r=n-k

11、。如果求用r个监督位构造出r个监督方程能纠正一位或一位以上错误的线性码，则必须有 2r-1n 在前面讨论奇偶监督码时，如考虑偶监督，则用式（10-2）作为监督方程，而在接收端译码时，实际是按下式计算的： 0121aaaaSnn若S=0，就认为无错；若S=1，就认为有错，我们称上式为监督方程，S校正子（校验子。如果增加一位监督元，就可以写出两个监督方程，计算出两个校正子S1和S2。S1S2为00时，表示无错；S1S2为01、10、11时，指示3种不同的错误图样。由此可见，若有r位监督元，就可以构成r个监督方程，计算得到的校正子有r位，可用来指示2r-1种不同的错误图样，r位校正子为全零时，表示无

12、错。 设分组码中信息位k=4，又假设该码能纠正一位错码，这时d03，要满足2r-1n，取r3时，当r=3时，n=k+r=7，这样就构成了（7，4）汉明码。这里用A=a6 a5 a4 a3 a2 a1 a0表示码字，其中前4位是信息元，后3位是监督元，用S1，S2，S3表示由3个监督方程得到的3个校正子。3个校正子S1，S2，S3指示23-1种不同的错误图样，校正子与错码位置的对应关系如下。 S1 S2 S3 错码位置 S1 S2 S3 错码位置 001 010 100 011 a0 a1 a2 a3 101 110 111 000 a4 a5 a6 无错 由表可知，校正子S1为1的错码位置为a

13、2，a4，a5，a6；校正子S2为1的错码位置为a1，a3，a5，a6；校正子S3为1的错码位置为a0，a3，a4，a6。这样，我们可以写出3个监督方程，即 034631356224561aaaaSaaaaSaaaaS当3个校正子S1，S2，S3均为0时，编码组中无错码发生，于是有下列方程组 000034613562456aaaaaaaaaaaa由上式可以求得监督元a2，a1，a0为 346035614562aaaaaaaaaaaa(7,4)汉明码的汉明码的16个许用码组个许用码组 码 字 码 字 序号 信 息 元 监 督 元 序号 信 息 元 监 督 元 0 0000 000 8 1000

14、111 1 0001 011 9 1001 100 2 0010 101 10 1010 010 3 0011 110 11 1011 001 4 0100 110 12 1100 001 5 0101 101 13 1101 010 6 0110 011 14 1110 100 7 0111 000 15 1111 111 在接收端收到每组码后，按监督方程计算出S1，S2和S3，如不全为0，则可确定误码的位置，然后加以纠正。汉明码编码效率为 121rrnrnnk010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa

15、10.4.3 监督矩阵监督矩阵不难看出，上述(7，4)码的最小码距d0=3，它能纠正一个错误或检测两个错误。 (7,4)汉明码的3个监督方程式可以改写成线性方程组如下 这组线性方程可用矩阵形式表示为 0001001101010101100101110123456aaaaaaa并简记为 0THA其中，A AT是A A的转置，HT是H的转置。 100110101010110010111HH称为监督矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为rn阶矩阵，H矩阵每行之间是彼此线性无关的。H矩阵可分成两部分 其中,P为rk阶矩阵，Ir为rr阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型

16、监督矩阵。 HAT=0，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。 100110101010110010111rIPH若把监督方程补充为下列方程 10.4.4 生成矩阵生成矩阵 34603561456233445566aaaaaaaaaaaaaaaaaaaa可改写为矩阵形式 即 345601234561101101101111000010000100001aaaaaaaaaaa3456aaaaGATT变换为 GaaaaA3456其中, 1101000101010001100101110001G称为生成矩阵，由G和信息组就可以产生全部码字。G为kn阶矩阵，各行也

17、是线性无关的。生成矩阵也可以分为两部分，即 QIGkT110101011111PQ其中 Q为kr阶矩阵,I Ik为k阶单位阵。可以写成式(10-13)形式的G G矩阵，称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。 10.4.5 校正子和检错校正子和检错 设发送码组A=an-1,an-2,a1,a0，在传输过程中可能发生误码。接收码组B=bn-1,bn-2,b1,b0，则收发码组之差定义为错误图样E， 也称为误差矢量， 即 ABE其中E=en-1,en-2,e1,e0，且 10ie当bi=ai 当biai 式(10-23)也可写作 EAB令S=BHT，称为伴随式或校正子

18、。 TTTEHHEABHS)( 由此可见，伴随式S S与错误图样E E之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。 (7,4)码码S与与E的对应关系的对应关系 E S 序号 错误码位 e6 e5 e4 e3 e2 e1 e0 s2 s1 s0 0 / 0000000 000 1 b0 0000001 001 2 b1 0000010 010 3 b2 0000100 100 4 b3 0001000 011 5 b4 0010000 101 6 b5 0100000 110 7 b6 1000000 111 10.4.610.4.6线

19、性分组码的性质线性分组码的性质线性分组码是一种群码，对于模二加运算，其性质满足以下几条：(1)有封闭性。所谓封闭性是指群码中任意两个许用码组之和仍为一许用码组，这种性质也称为自闭率。(2)有零码。所有信息元和监督元均为零的码组，称为零码，即A0=000。任一码组与零码相运算其值不变，即 Ai+Ai= A0 (4)满足结合律。即 （A1+A2）+A3=A1+（A2+A3） (5)满足交换律。即 A2+A3=A3+A2 (6)最小码距等于线性分组码中非全零码组的最小重量。线性分组码的封闭性表明，码组集中任意两个码组模二相加所得的码组一定在该码组集中，因而两个码组之间的距离必是另一码组的重量。所以，码的最小距离也就是码的最小重量，即 d0=Wmin(Ai) Ai n,k,i 0线性分