信息论与编码(杜玉华)第8章

1、第第8 8章章 纠错编码纠错编码8.1纠错编码的基本概念纠错编码的基本概念8.2 纠错编码分类纠错编码分类8.3线性分组码线性分组码8.4循环码循环码8.1 纠错编码的基本概念纠错编码的基本概念 信源编码信源编码提高数字信号提高数字信号 将信源的模拟信号转变为数字信号将信源的模拟信号转变为数字信号 降低数码率降低数码率, ,压缩传输频带压缩传输频带( (数据压缩数据压缩) ) 信道编码信道编码提高数字通信提高数字通信 数字信号在信道的传输过程中数字信号在信道的传输过程中, ,由于实际信道的由于实际信道的传输特性不理想以及存在加性噪声传输特性不理想以及存在加性噪声, ,在接收端往在接收端往往会产

2、生误码。往会产生误码。8.1 纠错编码的基本概念纠错编码的基本概念 目的在于提高通信（或存储）的可靠性，目的在于提高通信（或存储）的可靠性，减低误码率。减低误码率。 假设信源信息是二进制数字序列，将信假设信源信息是二进制数字序列，将信源编码其的输出序列构成长度为源编码其的输出序列构成长度为n n的段，的段，记为记为C C C=c C=c1 1,c,c2 2, , ,c cn n8.1 纠错编码的基本概念纠错编码的基本概念 设有设有m m个不同的信息序列，每个不同的个不同的信息序列，每个不同的序列由序列由k k（kk 由于由于p 1，出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E

3、的重量越轻，所以该译码方法实际上体现了最小的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。距离译码准则，即最大似然译码。8.3 线性分组码线性分组码 方法：方法： (1)按最可能出现的按最可能出现的2r个差错图案个差错图案E，计算相计算相应的伴随式应的伴随式S，并构造伴随式一差错图案表并构造伴随式一差错图案表(S,E)。 (2)对接收向量对接收向量R计算伴随式计算伴随式S。 (3)查查(S,E)表得表得E。 (4)纠错计算纠错计算C=R-E。8.3.3 汉明码汉明码 常见的线性分组码有重复码、汉明码、里常见的线性分组码有重复码、汉明码、里得得-穆勒穆勒(Reed-Mul

4、ler)码码(RM码码)、戈雷、戈雷(Golay)码等。码等。 汉明码是汉明汉明码是汉明19501950年提出的纠一个错误的线性年提出的纠一个错误的线性分组码，也是第一个被人研究应用的纠错码。分组码，也是第一个被人研究应用的纠错码。由于其编译码电路简单，故至今在通信系统和由于其编译码电路简单，故至今在通信系统和数据存储系统中应用广泛。数据存储系统中应用广泛。8.3.3 汉明码汉明码 1 1、汉明码的构筑思路、汉明码的构筑思路 由由 知：纠一个错误，则知：纠一个错误，则 , ,即即 要求中任意两列线性无关。也就是要求要求中任意两列线性无关。也就是要求 的任意两列不相同，且无全的任意两列不相同，且

5、无全“0”“0”列。列。21mindt3mindHH8.3.3 汉明码汉明码 在在( (n,kn,k) )线性分组码中，校验元个数线性分组码中，校验元个数r=r=n-kn-k， 阵中每列有阵中每列有r r个元素，至多可构成个元素，至多可构成2 2r r-1-1种互不种互不相同的非相同的非0 0列。故对于任意的正整数列。故对于任意的正整数 ，存，存在具有以下参数的汉明码：在具有以下参数的汉明码：H3m12mkm码长码长信息位数信息位数校验位数校验位数mknr码的最小距离码的最小距离3mind如（如（7 7，4 4）汉明码，）汉明码，（1515，1111）汉明码）汉明码12 mn8.3.3 汉明码

6、汉明码 2 2、汉明码的两种形式、汉明码的两种形式 1) 1)标准形式：依据一致校验矩阵的标准形式标准形式：依据一致校验矩阵的标准形式 所编出的汉明码，它是一种系统码所编出的汉明码，它是一种系统码。其中的。其中的 阵为一个阵为一个m m行和行和 列的矩列的矩阵。阵。mQIH Q12mm8.3.3 汉明码汉明码 2) 2)非标准形式：若按照其一致校验矩阵非标准形式：若按照其一致校验矩阵 的的一种特殊形式一种特殊形式( (校验阵中的各列就是校验阵中的各列就是1 1到到 所对应的二进制数所对应的二进制数) )所编出的汉明码，它是一所编出的汉明码，它是一种非系统完备码。这种形式的汉明码最常用，种非系统

7、完备码。这种形式的汉明码最常用，因为它具有编译码简单、扩展方便等优点，下因为它具有编译码简单、扩展方便等优点，下面对此稍作说明。面对此稍作说明。12 mH8.3.3 汉明码汉明码 说明：说明： 例如例如m=3m=3时的时的(7,4)(7,4)汉明码其一致校汉明码其一致校验阵为验阵为 据此据此 所对应的一致生成矩阵所对应的一致生成矩阵 来构筑的编来构筑的编码十分简单。码十分简单。101010111001101111000HHG8.3.3 汉明码汉明码 依据上一介绍的内容知：由于汉明码是只能纠单个依据上一介绍的内容知：由于汉明码是只能纠单个错误的码错误的码, ,因此当接收端译码器接收到的经信道传输

8、而因此当接收端译码器接收到的经信道传输而来的这类码字时，其伴随式所对应的二进制数值正是来的这类码字时，其伴随式所对应的二进制数值正是阵中对应列，也就是接收码字中错误码元的位置号，阵中对应列，也就是接收码字中错误码元的位置号，据此译码十分方便。如：上例中，若在译码输出端通据此译码十分方便。如：上例中，若在译码输出端通过伴随式计算电路算得某接收码字的伴随式为过伴随式计算电路算得某接收码字的伴随式为 则可直接判定接收码字的第则可直接判定接收码字的第5 5位出错位出错。)101(S8.3.3 汉明码汉明码 汉明码可纠错误图样数为汉明码可纠错误图样数为n=2n=2m m-1 ,-1 ,等于该等于该汉明码

9、的码长，故汉明码是完备码。汉明码的码长，故汉明码是完备码。 若将汉明码加以改造，使它除了能纠单个若将汉明码加以改造，使它除了能纠单个错误外，还能发现两个错误，这样所得到的错误外，还能发现两个错误，这样所得到的“纠纠1 1检检2 2错码错码”称为称为“扩展汉明码扩展汉明码”（或者（或者“增增余汉明码余汉明码”、“推广汉明码推广汉明码”）。）。8.3.3 汉明码汉明码 设原汉明码的一致校验阵为设原汉明码的一致校验阵为 , ,则扩展汉明则扩展汉明码的一致校验阵应为码的一致校验阵应为111001HHH8.3.3 汉明码汉明码 故至少应在原码基础上增加一个校验位，且故至少应在原码基础上增加一个校验位，且

10、应使新的一致校验矩阵应使新的一致校验矩阵 阵中任意两列之和阵中任意两列之和不等于其它任一列，这就要求不等于其它任一列，这就要求 阵的任三列阵的任三列线性无关。线性无关。, 1t41minltd2l1H1H8.3.3 汉明码汉明码例：例：设某（设某（7 7,3 ,3）线性分组码的一致校验矩阵为：）线性分组码的一致校验矩阵为： 发送端发送的码字为发送端发送的码字为 （注：接收端译码器并不知道发送码字）（注：接收端译码器并不知道发送码字）。试讨。试讨论下面三种接收情况下的判错情形：论下面三种接收情况下的判错情形：1000110010001100101110001101H)1010011(C8.3.3

11、 汉明码汉明码 接收端接收的码字为接收端接收的码字为 接收端接收的码字为接收端接收的码字为 接收端接收的码字为接收端接收的码字为 解解: 当接收端接收的码字为当接收端接收的码字为 时，时， 故译码器判为没错。故译码器判为没错。)1010011(R)1110011(R)0011011(R)1010011(RTTTHRS08.3.3 汉明码汉明码 当接收端接收的码字为当接收端接收的码字为 时，时， 又由其又由其H阵知该阵知该(7,3)码为能纠码为能纠1个错误的码型，且个错误的码型，且ST正好等于正好等于H阵中的第二列，因此可判定第二位有阵中的第二列，因此可判定第二位有错。错。)1110011(RT

12、TTHRS011108.3.3 汉明码汉明码 当接收端接收的码字为当接收端接收的码字为 时，时， 译码器判为有错。又由于此时的伴随式译码器判为有错。又由于此时的伴随式ST与与H中中 任一列均不同，故一定出现了两位或两位以上的任一列均不同，故一定出现了两位或两位以上的错误，译码器无法判定错误究竟出现在哪些位上错误，译码器无法判定错误究竟出现在哪些位上。)0011011(R00110TTHRS8.3.3 汉明码汉明码 伴随式计算电路伴随式计算电路(以上例中的以上例中的(7,3)码为例码为例)1000110010001100101110001101H)(0123456RRRRRRRR 设接收字为设接

13、收字为8.3.3 汉明码汉明码04515624563460123RRRRRRRRRRRRRSSSSHRSTT8.3.3 汉明码汉明码0R1R2R3R4R5R6R码字码字输入输入0S1S2S3S移位寄存器组半加器8.3.3 汉明码汉明码伴随式计算电路伴随式计算电路组合逻辑电路组合逻辑电路纠错译码电路纠错译码电路SEER输入输入（信道输出）（信道输出）译码输出译码输出8.4 循环码循环码 循环码是线性分组码的一个重要子类。由循环码是线性分组码的一个重要子类。由于它具有循环特性和优良的代数结构，使得它于它具有循环特性和优良的代数结构，使得它在发送端可用简单的反馈移位寄存器实现编码在发送端可用简单的反

14、馈移位寄存器实现编码，而在接收端也可由简单的反馈移位寄存器实，而在接收端也可由简单的反馈移位寄存器实现伴随式计算，从而实现简单有效的编译码。现伴随式计算，从而实现简单有效的编译码。所以循环码已成为研究最深入、理论最成熟、所以循环码已成为研究最深入、理论最成熟、应用最广泛的一类线性分组码。应用最广泛的一类线性分组码。8.4.1 循环码的描述循环码的描述 1.循环码的定义循环码的定义 定义定义1：如将一个码系的全部码字分成若干组：如将一个码系的全部码字分成若干组，则每组的所有码字可由其中任一码字的循环，则每组的所有码字可由其中任一码字的循环移位得到。移位得到。 如如(7,3)循环码的个数为：循环码

15、的个数为：23 个，分成两个组个，分成两个组8.4.1 循环码的描述循环码的描述 (0000000) (0010111)(0101110)(1011100)(0111001)(1110010)(1100101)(1001011)8.4.1 循环码的描述循环码的描述 又如：又如：(7, 4)循环码，码的个数为循环码，码的个数为24个，分成四个组个，分成四个组 (0000000) (1111111) (1001110)(0011101)(0111010)(1110100)(1101001)(1010011)(0100111) (1000101)(0001011)(0010110)(0101100)

16、(1011000)(0110001)(1100010)8.4.1 循环码的描述循环码的描述 定义定义2: : 一个一个( (n n, , k k) )线性分组码线性分组码C C，若它一个码若它一个码矢的每一循环移位都是矢的每一循环移位都是C C的一个码字，则的一个码字，则C C是一是一个循环码。个循环码。 循环码是一种线性码，因此线性码的一切特循环码是一种线性码，因此线性码的一切特性均适合于循环码；但它的特殊性是其循环性性均适合于循环码；但它的特殊性是其循环性，码字集合或者说码组中任意一个码字的循环，码字集合或者说码组中任意一个码字的循环移位得到的序列仍是该码字集合中的码字，即移位得到的序列仍

17、是该码字集合中的码字，即它对循环操作满足封闭性。它对循环操作满足封闭性。8.4.1 循环码的描述循环码的描述 例例 分析二进制码组分析二进制码组000, 110, 101, 011, 00000, 000, 110, 101, 011, 00000, 01111, 10100, 11011, 0000, 1101, 0111, 1011, 01111, 10100, 11011, 0000, 1101, 0111, 1011, 11101110是不是循环码。是不是循环码。 解解 看码组符不符合线性和循环的条件。看码组符不符合线性和循环的条件。 对于码组对于码组000, 110, 101, 01

18、1000, 110, 101, 011，它既是线性码又，它既是线性码又是循环码。事实上，它是对是循环码。事实上，它是对00, 01, 10, 1100, 01, 10, 11进行偶校进行偶校验得到的码，是验得到的码，是(3, 2)(3, 2)循环码。循环码。8.4.1 循环码的描述循环码的描述 对于码组对于码组00000, 01111, 10100, 1101100000, 01111, 10100, 11011，它是线性码但不是循环码。事实上，它是对消它是线性码但不是循环码。事实上，它是对消息序列息序列00, 01, 10, 1100, 01, 10, 11进行编码得到的线性分进行编码得到的

19、线性分组码组码(5, 2) (5, 2) 码。码。 对于码组对于码组0000, 1101, 0111, 1011, 11100000, 1101, 0111, 1011, 1110，它尽管满足循环性但由于不是线性码，故也，它尽管满足循环性但由于不是线性码，故也不是循环码。不是循环码。8.4.1 循环码的描述循环码的描述 2.循环码的码多项式循环码的码多项式 由此可以建立码序列和码多项式的一一对应关系。由此可以建立码序列和码多项式的一一对应关系。设码序列为设码序列为 则它可用多项式表示为则它可用多项式表示为 将它进行将它进行i i次循环左移，得次循环左移，得 称称 为码序列循环移位为码序列循环移

20、位i i次后的码多项式。次后的码多项式。),.,(021CCCCnn02211.)(CxCxCxCnnnnininininniniCxCxCxCxCxC.)(1102211)()()(xCi8.4.1 循环码的描述循环码的描述 定理定理 设循环码的码多项式为设循环码的码多项式为 循环移位循环移位i次后次后的码多项式为的码多项式为 ，则，则 是是xn+1除多项除多项式式xi C(x)所得之余式。所得之余式。 即即 (模模xn+1) 02211.)(CxCxCxCnnnn)()(xCi)()(xCi)()()(xCxxCiiininininniniCxCxCxCxCxC1102211)()(8.4

21、.1 循环码的描述循环码的描述ininininniniCxCxCxCxCxC1102211)()(11)(1023121nnnnnnnnxcxcxcxccxxCx1)()1(1nnxxCc则则上式表明：码矢上式表明：码矢)(xC循环一次的码多项式循环一次的码多项式)()1(xC是原码多项式是原码多项式)(xC乘乘x除以除以1nx的余式：记作的余式：记作)()()1(xCxxC(模模xn+1)8.4.1 循环码的描述循环码的描述由此类推：由此类推：)()()(xCxxCii(模模xn+1)即：循环码的码矢的即：循环码的码矢的次循环移位等效于将码多项式乘次循环移位等效于将码多项式乘ix后再模后再模

22、1nxi8.4.1 循环码的描述循环码的描述移位次数移位次数 码字码字 码多项式码多项式 模模x7+1 0 0011101 x4+x3+x2+1 1 0111010 x(x4+x3+x2+1) x5+x4+x3+x 2 1110100 x2(x4+x3+x2+1) x6+x5+x4+x2 3 1101001 x3(x4+x3+x2+1) x6+x5+x3+1 4 1010011 x4(x4+x3+x2+1) x6+x4+x2+1 5 0100111 x5(x4+x3+x2+1) x5+x2+x+1 6 1001110 x6(x4+x3+x2+1) x6+x3+x2+x如（如（7，3）循环码：）

23、循环码：8.4.1 循环码的描述循环码的描述 3.循环码的生成多项式循环码的生成多项式 在在(n , k)循环码的循环码的2k个码字中，取前个码字中，取前k-1位皆为位皆为0的码的码字所对应的码多项式字所对应的码多项式g(x) (其次数其次数r=n-k)，再经再经k-1次循次循环移位，共得环移位，共得k个码字：个码字：g(x)，xg(x)，xk-1g(x)。这这k个码字显然是相互独立的。可作为码生成矩阵的个码字显然是相互独立的。可作为码生成矩阵的k行行，得到，得到(n , k)循环码的生成矩阵循环码的生成矩阵G(x)。称称g(x)为生成多为生成多项式。项式。 其中其中 为为n-k次首次首1多项

24、式。多项式。0111.)(gxgxgxxgknknkn8.4.1 循环码的描述循环码的描述 几个关于生成多项式的定理几个关于生成多项式的定理 定理定理1：在：在(n,k)循环码中，生成多项式循环码中，生成多项式g(x)是是唯一的唯一的(n-k)次多项式，且次数是最低的。次多项式，且次数是最低的。 定理定理2：在：在(n,k)循环码中，每个码多项式循环码中，每个码多项式C(x)都是生成多项式都是生成多项式g(x)的倍式，而每个的倍式，而每个g(x)倍倍式的次数小于或等于式的次数小于或等于(n-1)的多项式必为的多项式必为(n,k)循循环码的码多项式。环码的码多项式。 8.4.1 循环码的描述循环

25、码的描述 定理定理3： (n,k)循环码的生成多项式循环码的生成多项式g(x)是是xn+1的因式，即的因式，即xn+1=h(x)g(x) 定理定理4：若：若g(x)是一个是一个(n-k)次多项式，且为次多项式，且为xn+1的因式，则的因式，则g(x)生成唯一一个生成唯一一个(n-k)循环码循环码码系。码系。8.4.1 循环码的描述循环码的描述 以上几个定理说明：构建一个以上几个定理说明：构建一个(n,k)循环码时循环码时，只要分解多项式，只要分解多项式xn+1的因式，从中取出的因式，从中取出(n-k)次因式作生成多项式即可。次因式作生成多项式即可。 8.4.1 循环码的描述循环码的描述 例例

26、求求(7,3)循环码的生成多项式。循环码的生成多项式。 解：分解多项式解：分解多项式x7+1 ，取，取4次因式作生成多项次因式作生成多项式式 因为因为 可将一次和任一个三次因式的乘积作为生成可将一次和任一个三次因式的乘积作为生成多项式，所以多项式，所以) 1)(1)(1(13237xxxxxx1) 1)(1()(24231xxxxxxxg1) 1)(1()(23432xxxxxxxg8.4.2 循环码的生成矩阵循环码的生成矩阵 在在(n , k)循环码的循环码的2k个码字中，取前个码字中，取前k-1位皆位皆为为0的码字所对应的码多项式的码字所对应的码多项式g(x) (其次数其次数r=n-k)，

27、再经再经k-1次循环移位，共得次循环移位，共得k个码字：个码字：g(x)，xg(x)，xk-1g(x)。这这k个码字显然是相互个码字显然是相互独立的。可作为码生成矩阵的独立的。可作为码生成矩阵的k行，得到行，得到(n , k)循环码的生成矩阵循环码的生成矩阵G。8.4.2 循环码的生成矩阵循环码的生成矩阵nkrrrrrkkggggggggggxgxxgxgxxgxG000101210000000000)()()()(8.4.3 校验多项式和校验矩阵校验多项式和校验矩阵 设设g(x)为为(n,k)循环码的生成多项式，则循环码的生成多项式，则g(x)必必为为xn+1的因式，的因式， 若有若有xn+

28、1=h(x)g(x) 其中其中h(x)为为k次因式，那么次因式，那么g(x)为为n-k次因式次因式 则称则称h(x)为为(n,k)循环码的一致校验多项式。循环码的一致校验多项式。 既然既然(n,k)循环码可由循环码可由g(x)唯一生成，那么唯一生成，那么(n,k)循环码亦可由循环码亦可由h(x) 完全确定。完全确定。8.4.3 校验多项式和校验矩阵校验多项式和校验矩阵 例例 (7,3)循环码循环码 因为因为 由等式由等式 两端同次项系数相等两端同次项系数相等得：得：) 1)(1(13247xxxxxx xg xh01223344241)(gxgxgxgxgxxxxg01223331)(hxhx

29、hxhxxxh)()(17xhxgx8.4.3 校验多项式和校验矩阵校验多项式和校验矩阵3x4x5x6x的系数：的系数：的系数：的系数：的系数：的系数：的系数的系数：030211203hghghghg031221304hghghghg0322314hghghg03324hghg8.4.3 校验多项式和校验矩阵校验多项式和校验矩阵将方程组写成矩阵形式：将方程组写成矩阵形式：0000000000003210321032103210hhhhhhhhhhhhhhhh0123400ggggg08.4.3 校验多项式和校验矩阵校验多项式和校验矩阵 由上式可见：列阵的元素是生成多项式由上式可见：列阵的元素是

30、生成多项式 的系数，是一个码字。的系数，是一个码字。 则第一个矩阵为（则第一个矩阵为（7，3）循环码的校验矩阵）循环码的校验矩阵， 记为记为 的构成特点：的构成特点： 的第一行是码的校验多项式的第一行是码的校验多项式 的系数的系数的反序排列，记为的反序排列，记为 xg nknHH3 ,73 ,7H3 ,7H xh 332210 xhxhxhhxh8.4.3 校验多项式和校验矩阵校验多项式和校验矩阵 第二、三、四、行是第一行的移位。第二、三、四、行是第一行的移位。 0001011001011001011001011000*3*2*)3,7(xhxxhxxxhxhH又因为又因为所以所以 xgxhx

31、n110khh8.4.3 校验多项式和校验矩阵校验多项式和校验矩阵所以所以 kn,循环码的校验矩阵可推广到一般：循环码的校验矩阵可推广到一般：001101101100111111,kkknknknhhhhhhHH8.4.4 循环码编码循环码编码 1.基本原理基本原理 循环码的编码包含两步循环码的编码包含两步 求生成多项式求生成多项式g(x)：分解分解xn+1；取；取n-k次因式作生成多项式次因式作生成多项式g(x)； 利用利用g(x)设计编码电路。设计编码电路。8.4.4 循环码编码循环码编码 设信息多项式为：设信息多项式为： 校验数字多项式为：校验数字多项式为： (n,k)循环码的码多项式为

32、：循环码的码多项式为：02211.)(mxmxmxmkkkk02211.)(rxrxrxrrrrr0112211.)(cxcxcxcxcxcknknknknnnnn前k项后r项8.4.4 循环码编码循环码编码 c(x)前前k项系数为信息数字，后项系数为信息数字，后r项系数为校项系数为校验数字。验数字。 所以所以 所以所以c(x)=xn-km(x)+r(x) 又因为又因为c(x)=q(x)g(x) 所以所以q(x)g(x)= xn-km(x)+r(x)(.)(.01111xrcxcxmxxcxcknknknknknnn8.4.4 循环码编码循环码编码 同除同除g(x)得：得： 所以所以r(x)

33、xn-km(x) (模模g(x) 即：校验数字多项式即为信息多项式即：校验数字多项式即为信息多项式(n-k)次次移位后的模移位后的模g(x)的余式。的余式。)()()()()(xgxrxqxgxmxkn所以所以 xrxmxxCkn的集合是（的集合是（n,k）循环码循环码8.4.4 循环码编码循环码编码 例：在由例：在由 生成的生成的(7,3)循环码中循环码中，对信息，对信息101进行编码。进行编码。 解：因为解：因为 又因为又因为 所以所以 即该信息在所给循环中应编为（即该信息在所给循环中应编为（1010011）1)(234xxxxg462437) 1()(xxxxxmx1)()()(37xxrxgxmx1)(46xxxxc 循环码编码电路和工作原理循环码编码电路和工作原理 二元二元(n,k)循环码的编码是将信息多项式循环码的编码是将信息多项式m(x)乘乘xn-k后再除