第8章 信道编码

1、第第8章章 差错控制编码差错控制编码 本章要点本章要点 * * 差错控制编码的基本概念差错控制编码的基本概念 * * 常用的几种检错编码常用的几种检错编码 第第8章章 差错控制编码差错控制编码 第第8章章 差错控制编码差错控制编码 8.1 差错控制编码的基本概念差错控制编码的基本概念 信道编码即差错控制编码，目的是为了提高数字通信信道编码即差错控制编码，目的是为了提高数字通信 系统的可靠性系统的可靠性 不同系统的误码率不同不同系统的误码率不同 传输雷达数据：传输雷达数据：10 5 传输数字话音：传输数字话音：10 3 10 4 传输计算机数据：传输计算机数据：10 9 一、概述一、概述 第第8

2、章章 差错控制编码差错控制编码 二、差错控制方式二、差错控制方式 1. 检错重发法（检错重发法（ARQ）:发送端发出有一定检错能力的码。接收端根发送端发出有一定检错能力的码。接收端根 据编码规则，判断这些码在传输中是否有错误产生，如有错，就通据编码规则，判断这些码在传输中是否有错误产生，如有错，就通 过反馈信道告之发端，发端将错码重新发送，直到收端认为正确。过反馈信道告之发端，发端将错码重新发送，直到收端认为正确。 特点：只需要少量的多余码就能获得较低的误码率，系统的适特点：只需要少量的多余码就能获得较低的误码率，系统的适 应性较强；必须有反馈信道，不能进行同播，实时、连应性较强；必须有反馈信

3、道，不能进行同播，实时、连 贯性差。贯性差。 应用：短波、有线通信应用：短波、有线通信 第第8章章 差错控制编码差错控制编码 2. 前向纠错法（前向纠错法（FEC）:前向纠错方式是发送端发送有纠错能力的码，前向纠错方式是发送端发送有纠错能力的码， 接收端的纠错译码器收到这些码之后，按预先规定的规则，自动接收端的纠错译码器收到这些码之后，按预先规定的规则，自动 的纠正传输中的错误。的纠正传输中的错误。 特点：不需反馈信道，译码的实时性好，控制电路简单；译码特点：不需反馈信道，译码的实时性好，控制电路简单；译码 设备比较复杂，因而对信道变化的适应性差，为了获得较低设备比较复杂，因而对信道变化的适应

4、性差，为了获得较低 的误码率，设计信道冗余度较大。的误码率，设计信道冗余度较大。 应用：移动通信应用：移动通信 第第8章章 差错控制编码差错控制编码 3. 混合差错控制（混合差错控制（HEC）:是是上述两种上述两种方式的结合。发送端发送的码方式的结合。发送端发送的码可可 检错检错、纠错。接收端译码器收到信码后，如果检查出的错误是在码纠错。接收端译码器收到信码后，如果检查出的错误是在码 的纠错能力以内，则接收端自动进行纠错，如果错误很多，超过了的纠错能力以内，则接收端自动进行纠错，如果错误很多，超过了 码的纠错能力但尚能检测时，接收端则通过反馈信道告知发送端必码的纠错能力但尚能检测时，接收端则通

5、过反馈信道告知发送端必 须重发这组码的信息。须重发这组码的信息。 特点：该方法不仅克服了前向纠错方式冗余度较大，需要复杂的译码电特点：该方法不仅克服了前向纠错方式冗余度较大，需要复杂的译码电 路的缺点，同时还增强了检错重发方式的连贯性路的缺点，同时还增强了检错重发方式的连贯性 应用：卫星通信应用：卫星通信 第第8章章 差错控制编码差错控制编码 三、检错和纠错编码基本原理三、检错和纠错编码基本原理 1. 基本原理基本原理 发送端发送端 信息序列信息序列 信道编码信道编码 增加监督码增加监督码 相关码序列相关码序列 接收端接收端 接收端接收端 接收码序列接收码序列 信道译码信道译码 相关检测相关检

6、测 信息码序列信息码序列 第第8章章 差错控制编码差错控制编码 【 例子】例子】 表示天气：阴、晴表示天气：阴、晴 用一位码用一位码 1 0 无任何检、纠错能力无任何检、纠错能力 用二位码用二位码 11 00 01、10为禁用码，可为禁用码，可 检一位错，不可纠错检一位错，不可纠错 用三位码用三位码 111 000 001、010、011、100、 101、110为禁用码，可为禁用码，可 纠一位错，检二位错纠一位错，检二位错 第第8章章 差错控制编码差错控制编码 2. 几个概念几个概念 冗余度：在信息中附加比特以便于收端进行错误检测冗余度：在信息中附加比特以便于收端进行错误检测 分组码：在纠、

7、检错编码中，将纯信息码分组，然后在每组信息码分组码：在纠、检错编码中，将纯信息码分组，然后在每组信息码 后附加若干位监督码后附加若干位监督码 分组码结构：在分组码中，每组信息码为分组码结构：在分组码中，每组信息码为k位，后附加位，后附加r位监督码，位监督码， 总长度总长度n位，称码组（位，称码组（n, k ) ，n=k+r 例（例（7,3）3位信息码，位信息码，4位监督码位监督码 信息码元信息码元k监督码元监督码元r 码组长度码组长度n 第第8章章 差错控制编码差错控制编码 R ，有效性，有效性 k ， . 编码效率：编码效率：R= k/ n . 编码增益：在给定误码率下，非编码系统与编码系统

8、所需信噪比编码增益：在给定误码率下，非编码系统与编码系统所需信噪比 O b N S 之差（之差（dB） 第第8章章 差错控制编码差错控制编码 按信息码与监督码的函数关系分：线性码、非线性码按信息码与监督码的函数关系分：线性码、非线性码 按信息码与监督码的约束关系分：分组码、卷积码按信息码与监督码的约束关系分：分组码、卷积码 按编码后信息码是否保持原形式分：系统码、非系统码按编码后信息码是否保持原形式分：系统码、非系统码 按编码功能分：检错码、纠错码按编码功能分：检错码、纠错码 按纠、检错类型分：纠检随机错误、纠检突发错误按纠、检错类型分：纠检随机错误、纠检突发错误 按码元取值分：二进制码、多进

9、制码按码元取值分：二进制码、多进制码 四、差错控制编码分类四、差错控制编码分类 第第8章章 差错控制编码差错控制编码 五、纠检错能力五、纠检错能力 1. 码重：码重：码组中码元码组中码元“1” 的个数称为码组的重量，简称码重，的个数称为码组的重量，简称码重， 用用W表示。如码组：表示。如码组：10001，W=2。 2. 码距：码距：两个等长码组之间对应位不同的个数称为这两个码组两个等长码组之间对应位不同的个数称为这两个码组 的汉明距离，简称码距的汉明距离，简称码距d 如码组：如码组：10001和和01101，其码距，其码距 d3 3. 最小码距：最小码距：码组集合中各码组之间距离的最小值称为码

10、组的码组集合中各码组之间距离的最小值称为码组的 最小距离，用最小距离，用d0表示。表示。 第第8章章 差错控制编码差错控制编码 4. 纠错与检错能力纠错与检错能力 1 0 ed （1 1）为检测）为检测e e个错误，最小码距个错误，最小码距d d0 0应满足应满足 （2 2）为纠正为纠正t t个错误，最小码距个错误，最小码距d d0 0应满足应满足 12 0 td )(1 0 teted （3 3）为纠正为纠正t t个错误，同时又能检测个错误，同时又能检测e e个错误，最小码距个错误，最小码距d d0 0应满足应满足 第第8章章 差错控制编码差错控制编码 例例 已知两码组（已知两码组（0000

11、0000）和（）和（11111111），若该码组），若该码组 用于检错，能检出几位错码？若用于纠错，能纠用于检错，能检出几位错码？若用于纠错，能纠 正几位错码？若同时用于纠错和检错，问各能纠、正几位错码？若同时用于纠错和检错，问各能纠、 检几位错码？检几位错码？ 4 0 d 14 e3e 124 t 1t 14te1t2e （1） （2） （3） 解：解： 第第8章章 差错控制编码差错控制编码 例例 已知已知8 8个码组为：（个码组为：（O00000O00000），（），（001110001110），）， （010101010101），（），（011011011011），（），（1000111

12、00011），）， （1O11011O1101），）， （110110110110），（），（111000111000），）， （1 1）求以上码组的最小码距；（）求以上码组的最小码距；（2 2）若此）若此8 8个码组用于检个码组用于检 错，可检出几位错？（错，可检出几位错？（3 3）若用于纠错码，能纠几位？）若用于纠错码，能纠几位？ （4 4）若同时用于纠错和检错，纠错、检错性能如何？）若同时用于纠错和检错，纠错、检错性能如何？ 第第8章章 差错控制编码差错控制编码 例例 已知已知8 8个码组为：（个码组为：（O00000O00000），（），（001110001110），）， （01010

13、1010101），（），（011011011011），（），（100011100011），）， （1O11011O1101），）， （110110110110），（），（111000111000），）， （1 1）求以上码组的最小码距；（）求以上码组的最小码距；（2 2）若此）若此8 8个码组用于检个码组用于检 错，可检出几位错？（错，可检出几位错？（3 3）若用于纠错码，能纠几位？）若用于纠错码，能纠几位？ （4 4）若同时用于纠错和检错，纠错、检错性能如何？）若同时用于纠错和检错，纠错、检错性能如何？ 3 0 d 1 0 ed 13 e2e 12 0 td 123 t 1t 1 0 ted

14、 （1） （2） （3） （4）1t 第第8章章 差错控制编码差错控制编码 8.2 常用的几种检错编码常用的几种检错编码 1 0121 aaaa nn 一、奇偶监督码一、奇偶监督码 1.奇监督码：奇监督码：在每组信息码之后加一位监督位，使码组在每组信息码之后加一位监督位，使码组 中中“1”的数目为奇数。的数目为奇数。 * * 纠检错能力：只能发现奇数个错误，不能发现偶数个错误。纠检错能力：只能发现奇数个错误，不能发现偶数个错误。 0aaaa 012n1n 2.偶监督码：偶监督码： 第第8章章 差错控制编码差错控制编码 例：已知信息码组例：已知信息码组m1、m2、m3为为 (000)，(001)

15、，(010)，(011)，(100)，(101)，(110)，(111)， 试写出奇数监督码组和偶数监督码组。试写出奇数监督码组和偶数监督码组。 第第8章章 差错控制编码差错控制编码 二、二维奇偶监督码二、二维奇偶监督码 1.概念：概念：每一码组先写成一行，然后再按列的方向排列，若干每一码组先写成一行，然后再按列的方向排列，若干 码组排列成矩阵，最后加一行、列构成二维监督位。码组排列成矩阵，最后加一行、列构成二维监督位。 0121 0121 2 0 2 1 2 2 2 1 1 0 1 1 1 2 1 1 cccc aaaa aaaa aaaa nn mmm n m n nn nn * * 纠检

16、错能力：纠一行中的奇数个错误，检偶数个错纠检错能力：纠一行中的奇数个错误，检偶数个错 误，但不可检测对角式错误。误，但不可检测对角式错误。 第第8章章 差错控制编码差错控制编码 例：已知行列矩阵，写出监督码（奇校验）。例：已知行列矩阵，写出监督码（奇校验）。 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 第第8章章 差错控制编码差错控制编码 三、群计数码三、群计数码 1.概念：概念：将信息码中将信息码中“1”的个数用二进制表示，并作为监督码的个数用二进制表示，并作为监督码 放在信息码的后面。放在信息码的后面。 例：信息码：例：信息码：1

17、010111-“1”的个数为的个数为5-101 纠检错码组为纠检错码组为1010111101 * * 纠检错能力：除码组中纠检错能力：除码组中“1”“0”、“0” “1”的成的成 对错误外，可纠正所有形式的错误。对错误外，可纠正所有形式的错误。 第第8章章 差错控制编码差错控制编码 四、恒比码四、恒比码 1.概念：概念：每个码组每个码组 中中“1”和和“0”的数目保持恒定的数目保持恒定。 例如：我国电传通信中普遍采用例如：我国电传通信中普遍采用5中取中取3恒比码，即每个码组长度为恒比码，即每个码组长度为 5，“1”的个数为的个数为3，“0”的个数为的个数为2。该码组共有。该码组共有 个许用码字

18、，个许用码字， 用来传送用来传送10个阿拉伯数字。个阿拉伯数字。 * * 纠检错能力：不能检测纠检错能力：不能检测“1”错成错成“0”和和“0”错成错成“1”成对出现的成对出现的 差错外，能发现几乎任何形式的错码。差错外，能发现几乎任何形式的错码。 3 5 C 第第8章章 差错控制编码差错控制编码 五、正反码五、正反码 1.概念：概念：监督位数目与信息位数目相同，监督码元与信息码监督位数目与信息位数目相同，监督码元与信息码 元是相同（是信息码的重复）或相反（是信息码的反码由元是相同（是信息码的重复）或相反（是信息码的反码由 信息码中信息码中“1”的个数而定。的个数而定。 例如：电报通信用的正反

19、码的码长例如：电报通信用的正反码的码长n=10，其中信息位，其中信息位k=5，监督位，监督位r=5。 其编码规则为：其编码规则为： (1)当信息位中有奇数个当信息位中有奇数个“1”时，监督位是信息位的简单重复；时，监督位是信息位的简单重复； (2)当信息位中有偶数个当信息位中有偶数个“1”时，监督位是信息位的反码。时，监督位是信息位的反码。 第第8章章 差错控制编码差错控制编码 收端解码的方法为：先将收码组中信息位和监督位按位模收端解码的方法为：先将收码组中信息位和监督位按位模2相加，得到一相加，得到一 个个5位的位的合成码组合成码组，然后，由此合成码组产生一校验码组。若接收码组，然后，由此合

20、成码组产生一校验码组。若接收码组 的信息位中有奇数个的信息位中有奇数个“1”，则，则合成码组就是校验码组合成码组就是校验码组；若接收码组的；若接收码组的 信息位中有偶数个信息位中有偶数个“1”，则取，则取合成码组的反码作为校验码组合成码组的反码作为校验码组。最后，。最后， 观察校验码组中观察校验码组中“1”、“0”的个数，按表进行判决及纠正可能发现的的个数，按表进行判决及纠正可能发现的 错码。错码。 * * 纠检错能力：有纠正一位错码的能力，并能检测全部两纠检错能力：有纠正一位错码的能力，并能检测全部两 位以下的错码和大部分两位以上的错码。位以下的错码和大部分两位以上的错码。 第第8章章 差错

21、控制编码差错控制编码 例如：例如： 信息码信息码 11001 监督码监督码 11001 发送码组发送码组 1100111001 其编码规则为：其编码规则为： (1)当信息位中有奇数个当信息位中有奇数个“1”时，监督位是信息位的简单重复；时，监督位是信息位的简单重复； (2)当信息位中有偶数个当信息位中有偶数个“1”时，监督位是信息位的反码。时，监督位是信息位的反码。 其解码规则为：其解码规则为： (1)将收码组中信息位和监督位按位模将收码组中信息位和监督位按位模2相加，得到一相加，得到一5位的合成码组位的合成码组 ； (2)然后，由此合成码组产生一校验码组。然后，由此合成码组产生一校验码组。

22、a.若收到信息位中有奇数个若收到信息位中有奇数个“1”，则，则校验码组合成码组；校验码组合成码组； b.若收到信息位中有偶数个若收到信息位中有偶数个“1”，则，则校验码组合成码组的反码校验码组合成码组的反码 接收码组接收码组1 ：1100111001 合成码组：合成码组：00000 校验码组：校验码组：00000 接收码组接收码组2 ：1000111001 合成码组：合成码组：01000 校验码组：校验码组：10111 接收码组接收码组3 ：1100101001 合成码组：合成码组：10000 校验码组：校验码组：10000 第第8章章 差错控制编码差错控制编码 发送码组发送码组 110011

23、1001 接收码组接收码组1 ：1100111001 合成码组：合成码组：00000 校验码组：校验码组：00000 接收码组接收码组2 ：1000111001 合成码组：合成码组：01000 校验码组：校验码组：10111 接收码组接收码组3 ：1100101001 合成码组：合成码组：10000 校验码组：校验码组：10000 第第8章章 差错控制编码差错控制编码 10.3 10.3 线性分组码线性分组码 现以现以(7,4)(7,4)分组码为例来说明线性分组码的特点。设其码分组码为例来说明线性分组码的特点。设其码 字为字为A=A=a a6 6 a a5 5 a a4 4 a a3 3 a

24、a2 2 a a1 1 a a0 0，其中前，其中前 4 4 位是信息元，后位是信息元，后 3 3 位是监督元，位是监督元， 可用下列线性方程组来描述该分组码，产生可用下列线性方程组来描述该分组码，产生 监督元。监督元。 2654 1653 0643 aaaa aaaa aaaa =+ =+ =+ 第第8章章 差错控制编码差错控制编码 (7,4)码的码字表码的码字表 第第8章章 差错控制编码差错控制编码 一、监督矩阵一、监督矩阵H和生成矩阵和生成矩阵G 1.1.上述（上述（7 7，4 4）码的监督方程为）码的监督方程为 线性方程可用矩阵表示为线性方程可用矩阵表示为 第第8章章 差错控制编码差错

25、控制编码 其中其中, ,P P为为r rk k阶矩阵，阶矩阵，IrIr为为r rr r阶单位矩阵。可以写成阶单位矩阵。可以写成H H= = P IrP Ir形式的矩阵称为典型监督矩阵。形式的矩阵称为典型监督矩阵。 HAHAT=0TT=0T，说明，说明H H矩阵与码字的转置乘积必为零，可以矩阵与码字的转置乘积必为零，可以 用来作为判断接收码字用来作为判断接收码字A A是否出错的依据。是否出错的依据。 并简记为并简记为 第第8章章 差错控制编码差错控制编码 若把监督方程补充为下列方程若把监督方程补充为下列方程 第第8章章 差错控制编码差错控制编码 可改写为矩阵形式可改写为矩阵形式 第第8章章 差错

26、控制编码差错控制编码 k GIQ= 1000111 0100110 0010101 0001011 G = Q = =PT 111 110 101 011 第第8章章 差错控制编码差错控制编码 二、伴随式二、伴随式(校正子校正子)S 设发送码组设发送码组A=an-1,an-2,a1,a0，在传输过程中可能发，在传输过程中可能发 生误码。接收码组生误码。接收码组B=bn-1,bn-2,b1,b0，则收发码组之差定，则收发码组之差定 义为错误图样义为错误图样E，也称为误差矢量，也称为误差矢量， 即即 EBA=- 其中其中E=en-1,en-2,e1,e0，且，且 0 1 i e = 当当bi=ai

27、 当当biai BAE=+ 令令S=BHT，称为伴随式或校正子。，称为伴随式或校正子。 () TTTTT SBHAE HAHEHEH=+=+= 第第8章章 差错控制编码差错控制编码 (7,4)码码S与与E的对应关系的对应关系 第第8章章 差错控制编码差错控制编码 7.4 循环码循环码 (7,3)循环码循环码 第第8章章 差错控制编码差错控制编码 在代数理论中，为了便于计算，常用码多项式表示码字。在代数理论中，为了便于计算，常用码多项式表示码字。 ( (n,kn,k) )循环码的码字，其码多项式循环码的码字，其码多项式( (以降幂顺序排列以降幂顺序排列) )为为 12 1210 ( ) nn n

28、n A xaxaxa xa - - =+. 第第8章章 差错控制编码差错控制编码 一、一、 生成多项式及生成矩阵生成多项式及生成矩阵 如果一种码的所有码多项式都是多项式如果一种码的所有码多项式都是多项式g g( (x x) )的倍式，则称的倍式，则称 g(xg(x) )为该码的生成多项式。在为该码的生成多项式。在( (n n, ,k k) )循环码中任意码多项式循环码中任意码多项式A(x)A(x) 都是最低次码多项式的倍式。如表都是最低次码多项式的倍式。如表 9-4 9-4 的的(7,3)(7,3)循环码中，循环码中， 2 43 1 ( )( )1g xA xxxx=+ 第第8章章 差错控制编

29、码差错控制编码 循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示 1 11 ( )1 rr r g xxgxg x - - =+ () x k-1g(x) Gx xg(x) g(x) x k-2g(x) . . 第第8章章 差错控制编码差错控制编码 例如例如(7,3)(7,3)循环码，循环码，n n=7, =7, k k=3, =3, r r=4, =4, 其生成多项式为其生成多项式为 生成矩阵为生成矩阵为 第第8章章 差错控制编码差错控制编码 二、监督多项式及监督矩阵二、监督多项式及监督矩阵 为了便于对循环码编译码，通常还定义监督多项式，为了便于对循环码编译码，通

30、常还定义监督多项式， 令令 1 11 1 ( )1 ( ) n kk k x h xxhxh x g x - - + =+ 其中其中g g( (x x) )是常数项为是常数项为 1 1 的的r r次多项式，是生成多项式；次多项式，是生成多项式；h h( (x x) ) 是常数项为是常数项为 1 1 的的k k次多项式，称为监督多项式。同理，可得次多项式，称为监督多项式。同理，可得 监督矩阵监督矩阵H H 第第8章章 差错控制编码差错控制编码 是是h h( (x x) )的逆多项式。例如的逆多项式。例如(9(9，3)3)循环码，循环码，g g( (x x)=)=x x4 4+ +x x3 3+

31、+x x2 2+1+1，则，则 其中其中 12 121 *( )1 kkk k hxxh xh xhx - - =+ 7 32 3 1 ( )1 ( ) * ( )1 x h xxx g x hxxx + =+ =+ 第第8章章 差错控制编码差错控制编码 () x6+x4+x3 Hx x5+x3+x2 x4+x2+x x3+x+1 1011000 0101100 0010110 0001011 H 第第8章章 差错控制编码差错控制编码 三、编码方法和电路三、编码方法和电路 在编码时，首先要根据给定的在编码时，首先要根据给定的( (n,kn,k) )值选定生成多项式值选定生成多项式 g(xg(x

32、) )，即应在，即应在x xn n+1+1的因式中选一的因式中选一r r= =n-kn-k次多项式作为次多项式作为g(xg(x) )。设。设 编码前的信息多项式编码前的信息多项式m(xm(x) )为为 21 123 ( ) k k m xaa xa xa x - =+ 循环码的码多项式可表示为循环码的码多项式可表示为 ( )( )( ) r A xxm xR x=+ . 第第8章章 差错控制编码差错控制编码 (7,3)循环码编码电路循环码编码电路 D0D1D2D3门1 门2 输入信息组 输出码字 1 第第8章章 差错控制编码差错控制编码 表表 9-5 (7,3)循环码的编码过程循环码的编码过程

33、 第第8章章 差错控制编码差错控制编码 四、译码方法和电路四、译码方法和电路 (7,3)循环码译码电路循环码译码电路 D0D1D2D3 7级缓存器 接收码组 B 输出码组 A & & 第第8章章 差错控制编码差错控制编码 7.57.5 卷积码卷积码 一、基本概念一、基本概念 卷积码卷积码(2,1,2)(2,1,2)编码器编码器 m1m2 数据 输入 码字 输出 S1S2S3 C1 C2 第第8章章 差错控制编码差错控制编码 起始状态，各级移位寄存器清零，即起始状态，各级移位寄存器清零，即S S1 1S S2 2S S3 3为为000000。S S1 1等等 于当前输入数据，而移位寄存器状态于当

34、前输入数据，而移位寄存器状态S S2 2S S3 3存储以前的数据，存储以前的数据， 输出码字输出码字C C由下式确定由下式确定 (2,1,2)编码器的工作过程 C1=S1+S2+S3 C2=S1+S3 第第8章章 差错控制编码差错控制编码 二、卷积码的描述二、卷积码的描述 1. 树图树图 图图 9-6 (2,1,2)码的树图码的树图 a11 00 a b b01 10 c d c00 11 a b d10 01 c d 00 10 a 11 01 b a 00 11 a11 00 a b b01 10 c d c00 11 a b d10 01 c d 11 01 c 00 10 d b 10 01 a 11 00 数码起点 状 态 a00 b01 c10 d11上半部 下半部 数码1101