《通信原理》10信道编码和差错控制

1、信道编码和差错控制信道编码和差错控制 纠错编码纠错编码 线性分组码线性分组码 循环码循环码 2 2021-8-6 基本要求基本要求 了解信道编码的目的和要求了解信道编码的目的和要求 掌握纠错编码的基本原理和纠错编码系统的性掌握纠错编码的基本原理和纠错编码系统的性 能分析能分析 熟悉常用的简单编码熟悉常用的简单编码 掌握线性分组码、循环码的编码和解码方法掌握线性分组码、循环码的编码和解码方法 3 2021-8-6 基本内容基本内容 信道编码信道编码概念概念，指数字信号为了适应信道的传指数字信号为了适应信道的传 输特性，达到高效可靠的传输而进行的相应的输特性，达到高效可靠的传输而进行的相应的 信号

2、处理过程。信号处理过程。 信道编码的信道编码的目的目的：降低误码率，降低误码率，提高信号传输提高信号传输 的可靠性。的可靠性。 信道编码的信道编码的基本原理基本原理是在信号码元序列中增加是在信号码元序列中增加 监督码元，并利用监督码元去发现或纠正传输监督码元，并利用监督码元去发现或纠正传输 中发生的错误。中发生的错误。 4 2021-8-6 基本内容基本内容 在信道编码只有发现错码能力而无纠正错在信道编码只有发现错码能力而无纠正错 码能力时，必须结合其他措施来纠正错码，码能力时，必须结合其他措施来纠正错码， 否则只能将发现为错码的码元删除。这些否则只能将发现为错码的码元删除。这些 手段统称为手

3、段统称为差错控制差错控制。 差错控制编码是一种信道编码。差错控制编码是一种信道编码。 5 2021-8-6 基本内容基本内容 信道的分类信道的分类 v 随机信道随机信道 v 突发信道突发信道 v 混合信道混合信道 6 2021-8-6 基本内容基本内容 常用的差错控制方式主要有常用的差错控制方式主要有 v检错重发（简称检错重发（简称ARQ） v前向纠错（简称前向纠错（简称FECFEC） v混合纠错（简称混合纠错（简称HECHEC） 目的：目的：克服线路传输中出现的数据差错，实现克服线路传输中出现的数据差错，实现 调制解调器至终端调制解调器的无差错数调制解调器至终端调制解调器的无差错数 据传送。

4、据传送。 7 2021-8-6 基本内容基本内容 差错控制编码方法差错控制编码方法/ /纠错编码方法：纠错编码方法： 为了在接收端能够发现或纠正错码，为了在接收端能够发现或纠正错码， 在发送码元序列中加入一些差错控制码在发送码元序列中加入一些差错控制码 元（监督码元元（监督码元/监督位）。监督位）。 加入的监督码元越多，纠加入的监督码元越多，纠/检错的能检错的能 力越强，传输效率越低，从而可以用降力越强，传输效率越低，从而可以用降 低传输效率换取传输可靠性的提高。低传输效率换取传输可靠性的提高。 8 2021-8-6 基本内容基本内容 差错控制编码分类：差错控制编码分类： 按照差错控制编码的不

5、同功能分为按照差错控制编码的不同功能分为 检错码、纠错码和纠删码；检错码、纠错码和纠删码； 按照信息码元和附加的监督码元之间的检验关系分为按照信息码元和附加的监督码元之间的检验关系分为 线性码和非线性码；线性码和非线性码； 按照信息码元和监督码元之间的约束方式不同分为按照信息码元和监督码元之间的约束方式不同分为 分组码和卷积码；分组码和卷积码； 9 2021-8-6 基本内容基本内容 差错控制编码分类：差错控制编码分类： 按照信息码元在编码后是否保持原来的形式不变分为按照信息码元在编码后是否保持原来的形式不变分为 系统码和非系统码；系统码和非系统码； 按照纠正错误的类型不同分为按照纠正错误的类

6、型不同分为 纠正随机错误的码和纠正突发错误的码；纠正随机错误的码和纠正突发错误的码； 按照构造差错控制编码的数学方法分为按照构造差错控制编码的数学方法分为 代数码、几何码和算术码；代数码、几何码和算术码； 按照每个码元取值不同分为按照每个码元取值不同分为 二进制和多进制码。二进制和多进制码。 10 2021-8-6 基本内容基本内容 码率：码率： 编码序列中信息码元数量编码序列中信息码元数量k k和总码元数量和总码元数量n n之比：之比： k/nk/n 冗余度：冗余度： 监督码元数（监督码元数（n-kn-k）和）和总总码元数量码元数量n n之比之比: : ( (n-k)/nn-k)/n 11

7、2021-8-6 纠错编码纠错编码 纠错编码中的基本概念纠错编码中的基本概念 v纠错编码：具有检错能力或纠错能力的编码。纠错编码：具有检错能力或纠错能力的编码。 v纠错编码分为纠错编码分为分组码分组码和和卷积码卷积码两大类。两大类。 v分组码分组码：将若干监督码元附加在一组信息位上：将若干监督码元附加在一组信息位上 构成一个具有纠错能力的独立码组，并且监督构成一个具有纠错能力的独立码组，并且监督 位仅监督本组中的信息码元。位仅监督本组中的信息码元。 v分组码用符号（分组码用符号（n,k）表示，其中）表示，其中n是码组长度，是码组长度， k为信息码元数目，为信息码元数目，r=n-k为监督码元数目

8、。为监督码元数目。 12 2021-8-6 纠错编码纠错编码 纠错编码中的基本概念纠错编码中的基本概念 v由代数关系确定监督位的分组码称为由代数关系确定监督位的分组码称为代数码代数码。 v在代数码中，若监督位和信息位的关系是由在代数码中，若监督位和信息位的关系是由 线性方程式决定的，则称这种编码为线性方程式决定的，则称这种编码为线性分线性分 组码组码。例如：奇偶监督码、汉明码、循环码。例如：奇偶监督码、汉明码、循环码。 13 2021-8-6 纠错编码纠错编码 纠错编码中的基本概念纠错编码中的基本概念 v汉明码汉明码：能够纠正：能够纠正1位错码的效率较高的线性位错码的效率较高的线性 分组码。分

9、组码。 v循环码循环码：就有循环性的线性分组码。：就有循环性的线性分组码。 vBCH码码：能够纠正多个随机错码的循环码。：能够纠正多个随机错码的循环码。 vRS码码：具有很强纠错能力的多进制：具有很强纠错能力的多进制BCH码。码。 14 2021-8-6 纠错编码纠错编码 纠错编码中的基本概念纠错编码中的基本概念 v码长：一个码组中码元的数目。码长：一个码组中码元的数目。 v码重：一个码组中码重：一个码组中“1”的个数。的个数。 v码距码距d：两个等长码组之间对应位不同的个数。：两个等长码组之间对应位不同的个数。 v最小码距最小码距 ：码组集合中所有码距的最小值。：码组集合中所有码距的最小值。

10、 0 d 15 2021-8-6 纠错编码纠错编码 纠错编码纠错编码 纠检错能力与最小码距纠检错能力与最小码距 的关系的关系： 0 d v一个码组内检测一个码组内检测e个误码：个误码： v一个码组内纠正一个码组内纠正t t个误码：个误码： v一个码组内纠正一个码组内纠正t t个误码同时检测个误码同时检测 e e（etet） 个误码：个误码： 1 0 ed 12 0 td )(1 0 teted 16 2021-8-6 纠错编码纠错编码 码距与检错和纠错能力的关系：码距与检错和纠错能力的关系： 0 d 0 d BA AB e tt 0123012345 (a) (b) AB e tt1 (c)

11、17 2021-8-6 纠错编码纠错编码 纠错编码系统的性能：纠错编码系统的性能： v误码率性能和带宽的关系：误码率性能和带宽的关系：采用编码降低采用编码降低 误码率所付出的代价是带宽的增大。误码率所付出的代价是带宽的增大。 v功率和带宽的关系：功率和带宽的关系：采用编码以节省功率，采用编码以节省功率， 并保持误码率不变，付出的代价也是带宽并保持误码率不变，付出的代价也是带宽 的增大。的增大。 18 2021-8-6 纠错编码纠错编码 纠错编码系统的性能：纠错编码系统的性能： v传输速率和带宽的关系：传输速率和带宽的关系：对于给定的传输系对于给定的传输系 统，其传输速率和信噪比统，其传输速率和

12、信噪比 的关系为的关系为 0 / b En 0000 (1/) bsss B EPTPP nnnTn R 提高传输速率，采用编码以保持误码提高传输速率，采用编码以保持误码 率不变，代价是带宽增大。率不变，代价是带宽增大。 19 2021-8-6 纠错编码纠错编码 纠错编码系统的性能：纠错编码系统的性能： v编码增益：编码增益：在保持误码率恒定的条件下，采在保持误码率恒定的条件下，采 用纠错编码所节省的信噪比用纠错编码所节省的信噪比 0 / b En 00 (/)(/) dBbubc GEnEndB 未编码时的信噪比未编码时的信噪比编码后所需的信噪比编码后所需的信噪比 20 2021-8-6 奇

13、偶监督码奇偶监督码 监督位只有监督位只有1位，码率为位，码率为 k/(k+1) 奇偶监督码能够检测奇数个错码奇偶监督码能够检测奇数个错码 分为奇数监督码和偶数监督码分为奇数监督码和偶数监督码 在奇数监督码中，监督位使码组中在奇数监督码中，监督位使码组中“1”的个的个 数数 为奇数为奇数 21 2021-8-6 奇偶监督码奇偶监督码 在偶数监督码中，监督位使码组中在偶数监督码中，监督位使码组中“1”的个数的个数 为偶数。在接收端检测时，将接收码组按照式为偶数。在接收端检测时，将接收码组按照式 求求“模模2和和”，若计算结果为，若计算结果为“1”就说明有错码，就说明有错码， 为为“0”就认为无错码

14、。（就认为无错码。（a0为监督位，其余位为监督位，其余位 为信息位）为信息位） 120 0 nn aaa 22 2021-8-6 二维奇偶监督码二维奇偶监督码 方阵码或矩形码方阵码或矩形码 构造方法构造方法：先将若干奇偶监督码按行排列成：先将若干奇偶监督码按行排列成 矩阵，再按列增加第二维监督位矩阵，再按列增加第二维监督位 码率为：码率为： 有可能检测出偶数个错码有可能检测出偶数个错码 适合检测突发错码，能够纠正部分错码适合检测突发错码，能够纠正部分错码 (1) (1) km n nmn 23 2021-8-6 线性分组码线性分组码 代数码代数码是利用代数关系式产生监督位的编码。是利用代数关系

15、式产生监督位的编码。 线性分组码线性分组码是代数码的一种，其监督位和信息是代数码的一种，其监督位和信息 位的关系由线性方程决定。位的关系由线性方程决定。 汉明码汉明码是能够纠正一个错误的效率较高的线性是能够纠正一个错误的效率较高的线性 分组码。分组码。 24 2021-8-6 线性分组码线性分组码 校正子校正子S（监督关系式）（监督关系式） 纠错就是通过计算纠错就是通过计算S，实际中，实际中S只有两种只有两种 取值，故只能表示有错和无错，而不能进一取值，故只能表示有错和无错，而不能进一 步指明错码的位置。步指明错码的位置。 120nn Saaa 25 2021-8-6 线性分组码线性分组码 若

16、有若有r个监督关系式，则个监督关系式，则r个校正子可以指明一个个校正子可以指明一个 错码的（错码的（2r-1）个不同位置。）个不同位置。 当校正子可以指明的错码位置数目等于或大于当校正子可以指明的错码位置数目等于或大于 码组长度码组长度n时，才能纠正码组中任何一个位置上时，才能纠正码组中任何一个位置上 的错码，即要求的错码，即要求 2121 rr nkr 或 26 2021-8-6 线性分组码线性分组码 汉明码汉明码 要求设计一个能够纠正要求设计一个能够纠正1个错误的分组码个错误的分组码(n,k)， 给定的码组中有给定的码组中有4个信息位，个信息位，k=4，则监督位数，则监督位数 r3。若取。

17、若取r=3，则，则n=k+r=7。 现在用现在用a6a5a4a3a2a1a0表示这表示这7个码元，用个码元，用 S1S2S3表示校正子，则这表示校正子，则这3个校正子恰好能够指个校正子恰好能够指 明明7个错码的位置。个错码的位置。 27 2021-8-6 线性分组码线性分组码 S1S2S3错码位置S1S2S3错码位置 001a0101a4 010a1110a5 100a2111a6 011a3000无错码 16542 26531 36430 Saaaa Saaaa Saaaa 汉明码汉明码 28 2021-8-6 线性分组码线性分组码 2654 1653 0643 aaaa aaaa aaaa

18、 汉明码汉明码 信息位的值决定于输入信号，是随机的。信息位的值决定于输入信号，是随机的。 监督位是按监督关系确定的，应保证校正子监督位是按监督关系确定的，应保证校正子 S等于等于0，既有：，既有： 6542 6531 6430 0 0 0 aaaa aaaa aaaa 29 2021-8-6 汉明码汉明码 （7,4）码，若）码，若 代表代表4个信息个信息 位，这位，这 代表代表3个监督码元。个监督码元。 线性分组码线性分组码 3456 aaaa、 012 aaa、 （信息位） 3456 aaaa（监督位） 012 aaa（信息位） 3456 aaaa（监督位） 012 aaa 0000 000

19、1 0010 0011 0100 0101 0110 0111 000 011 101 110 110 101 011 000 1000 1001 1010 1011 1100 1101 1110 1111 111 100 010 001 001 010 100 111 30 2021-8-6 线性分组码线性分组码 汉明码汉明码 接收端解码方法：接收端解码方法： 根据接收码组，先计算出校正子根据接收码组，先计算出校正子S1S2S3 ， 然后查表判断错码位置。然后查表判断错码位置。 16542 26531 36430 Saaaa Saaaa Saaaa 31 2021-8-6 线性分组码线性分组

20、码 汉明码汉明码 码率：码率： 21 21 r r kr n 32 2021-8-6 线性分组码线性分组码 用矩阵形式表示用矩阵形式表示 ）模 2( 0 0 0 1011001 1101010 1110100 0 1 2 3 4 5 6 a a a a a a a TTT H AOA HO或 33 2021-8-6 线性分组码线性分组码 监督矩阵监督矩阵H矩阵可以分成两部分矩阵可以分成两部分 r PIH 0011011 0101101 1001110 典型形式监督矩阵典型形式监督矩阵具有具有 形式的形式的H矩阵矩阵 r PI 各行必须是线各行必须是线 性无关的性无关的 rn 34 2021-8

21、-6 线性分组码线性分组码 0001011 0010101 0100110 1000111 QIG r 生成矩阵生成矩阵 T PQ 转置矩阵转置矩阵 65432106543 Aa a a a a a aa a a a G G的各行必须是的各行必须是 线性无关的线性无关的 kn kr rk 35 2021-8-6 线性分组码线性分组码 解码过程解码过程 发送码组发送码组A，接收到的码组，接收到的码组B，收发码，收发码 组之差记为组之差记为E（错误图样错误图样） ABE 021 eee nn ()SB HAE HE H TTT 校正子校正子 若若S和和E之间有一一对应，则能代表错码的位置。之间有一

22、一对应，则能代表错码的位置。 36 2021-8-6 线性分组码线性分组码 0000001 0 a0010000 4 a 0000010 0100000 0000100 2 a 1000000 6 a 0001000 3 a0000000 无错 001101 010110 100111 011000 1 a 5 a SSEE 错码位置错码位置错码位置错码位置 37 2021-8-6 线性分组码线性分组码 线性码的封闭性线性码的封闭性 若若M1和和M2是一种线性分组码中的两个码组，是一种线性分组码中的两个码组， 则则( M1 + M2 )仍是其中一个码组。仍是其中一个码组。 码的最小距离就是码的

23、最小重量码的最小距离就是码的最小重量 38 2021-8-6 循环码循环码 具有循环性。即循环码中任一码组循环一位具有循环性。即循环码中任一码组循环一位 （将最右端的码元移至左端，或反之）以后，（将最右端的码元移至左端，或反之）以后， 仍为该码中的一个码组。仍为该码中的一个码组。 为便于计算，把这样的码组中个码元当作是一为便于计算，把这样的码组中个码元当作是一 个多项式的系数，即把一个长为个多项式的系数，即把一个长为n的码组表示成的码组表示成 为信息码多项式为信息码多项式 12 1210 ( ) nn nn T xaxaxa xa x仅是码元位置的标记，我们并不关心仅是码元位置的标记，我们并不

24、关心x的取的取 值，这种多项式称为值，这种多项式称为码多项式码多项式。 ( )m x 39 2021-8-6 循环码循环码 )( )( )( )( )( 2 1 xg xxg xgx xgx xG k k 循环码的循环码的生成多项式生成多项式 是常数项不是常数项不 为为”0” 的的 的一个（的一个（n-k）次因式）次因式 )(xg ) 1( n x 循环码的生成矩阵循环码的生成矩阵 40 2021-8-6 循环码循环码 循环码的编码方法循环码的编码方法 根据给定的根据给定的(n,k)值选定生成多项式值选定生成多项式 )(xg ( )g x 即从即从 的因子中选一的因子中选一(n-k)次多项次多项 式作为式作为 ) 1( n x 41 2021-8-6 循环码循环码 循环码的编码方法循环码的编码方法 将信息码多项式将信息码多项式 升升(n-k)次幂后除以生成多次幂后除以生成多 项式项式 得到的系统循环码多项式得到的系统循环码多项式 )(xm )(xg )( )( )( )( )( xg xr xQ xg xmx kn )()()(xrxmxxT kn 42 2021-8-6 循环码循环码 例：例：求求