数据通信原理 第3章讲解

1、 第 3 章 差错控制 &3.1 3.1 差错控制的基本概念及原理差错控制的基本概念及原理 q3.1.1 3.1.1 差错控制的基本概念差错控制的基本概念 q3.1.2 3.1.2 差错控制的基本原理差错控制的基本原理 &3.2 3.2 简单的差错控制编码简单的差错控制编码 q3.2.1 3.2.1 奇偶监督码奇偶监督码 q3.2.2 3.2.2 水平奇偶监督码水平奇偶监督码 q3.2.3 3.2.3 二维奇偶监督码二维奇偶监督码 &3.3 3.3 汉明码及线性分组码汉明码及线性分组码 q3.3.1 3.3.1 汉明码汉明码 q3.3.2 3.3.2 线性分组码线性分组码 第 3 章 差错控制

2、 &3.4 3.4 循环码循环码 q3.4.1 3.4.1 循环码的循环特性循环码的循环特性 q3.4.2 3.4.2 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵 q3.4.3 3.4.3 循环码的解码方法循环码的解码方法 q3.4.4 3.4.4 循环码的解码方法循环码的解码方法 &3.5 3.5 卷积码卷积码 q3.5.1 3.5.1 卷积码的基本概念卷积码的基本概念 q3.5.2 3.5.2 卷积码的图解表示卷积码的图解表示 q3.5.3 3.5.3 卷积码的概率解码卷积码的概率解码 3.1 差错控制的基本概念及原理 数据信号在传输过程中不可避免地会发生差错，即数据信号在传

3、输过程中不可避免地会发生差错，即 出现出现误码误码。造成误码的主要原因可以归结为两个方面：。造成误码的主要原因可以归结为两个方面： r信道不理想造成的符号间干扰 由于信道不理想使得接收波形发生畸变，在接收由于信道不理想使得接收波形发生畸变，在接收 端抽样判决时会造成码间干扰，若此干扰严重时则导端抽样判决时会造成码间干扰，若此干扰严重时则导 致误码。这种原因造成的误码可以通过致误码。这种原因造成的误码可以通过均衡方法均衡方法予以予以 改善以至消除。改善以至消除。 r噪声对信号的干扰 信道等噪声叠加在接收波形上，对接收端信号的信道等噪声叠加在接收波形上，对接收端信号的 判决造成影响，如果噪声干扰严

4、重时也会导致误码。判决造成影响，如果噪声干扰严重时也会导致误码。 消除噪声干扰产生误码的方法就是进行消除噪声干扰产生误码的方法就是进行差错控制差错控制。 3.1.1 差错控制的基本概念 1.差错分类 数据信号在信道中传输会受到噪声干扰，噪声大体数据信号在信道中传输会受到噪声干扰，噪声大体 分为两类：分为两类：随机噪声和脉冲噪声随机噪声和脉冲噪声。 l随机差错随机差错又称独立差错，指那些独立地、稀疏地和互不相关地又称独立差错，指那些独立地、稀疏地和互不相关地 发生的差错。存在这种差错的信道称为无记忆信道或随机信道。发生的差错。存在这种差错的信道称为无记忆信道或随机信道。 l突发差错突发差错是指一

5、串串，甚至是成片出现的差错，差错之间有相是指一串串，甚至是成片出现的差错，差错之间有相 关性，差错出现是密集的。产生突发错误的信道称为有记忆信道关性，差错出现是密集的。产生突发错误的信道称为有记忆信道 或突发信道。或突发信道。 实际信道是复杂的，所出现的错误也不是单一的，而是随实际信道是复杂的，所出现的错误也不是单一的，而是随 机和突发错误并存的，这两类错误形式并存的信道称为机和突发错误并存的，这两类错误形式并存的信道称为组合组合 信道或复合信道信道或复合信道。 2.差错控制的基本思路 差错控制的核心是抗干扰编码，或差错控制编码，简称纠 错编码，也叫信道编码 q发送端发送端：将被传送的信息码（

6、无规律）按照一定的：将被传送的信息码（无规律）按照一定的 规则加入监督码元后进行传输，加入的监督码元与规则加入监督码元后进行传输，加入的监督码元与 信息码元存在某种确定的约束关系。信息码元存在某种确定的约束关系。 q接收端接收端：检验信息码元与监督码元之间的既定的约：检验信息码元与监督码元之间的既定的约 束关系，如关系被破坏，则传输中有错。束关系，如关系被破坏，则传输中有错。 信息码(k)+监督码(r)=码组(n) 3. 差错控制方式 差错控制方式 （1）检错重发（ARQ） 优缺点 所需的监督码位数少，编码效率比较高； 译码设备较简单； 接收端检测到差错后，要通过反向信道发回NAK，要求发端重

7、发， 所以需要反向信道，实时性差 ARQARQ有有3 3种种重重发发方式，即方式，即停停发发等候重等候重发发，返回重，返回重发发和和选择选择重重发发。 差错控制方式 （2）前向纠错（FEC） 优缺点 不需要反向信道，自动纠错，不要求重发，因而实时性好； 缺点是所选择的纠错码必须与信道的错码特性密切配合，否则 很难达到降低错码率的要求； 要纠正较多的错码，译码设备复杂，且要求附加的监督码较多， 编码效率低。 差错控制方式 （3）混合纠错检错（HEC） 是ARQ和FEC方式的折衷方案 优缺点 集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大 幅度提高了整个系统的可靠性，但需要反向信道。

8、 差错控制方式 （4）信息反馈（IRQ） 数据信息 数据信息 （d） 信息反馈 优缺点 优点是不需要纠错、检错，设备简单； 缺点是需要和前向信道相同的反向信道，实时性差，且发送端 需要一定容量的存储器。 3.1.2 差错控制的基本原理 1. 差错控制的原理 3.1.2 差错控制的基本原理 1. 差错控制的原理（续） 要想具有检错和纠错能力，必须有禁用码组。 禁用码组的获得方法：加监督位。 结论 若要传送若要传送A A和和B B两个消息：若用两个消息：若用1 1位码表示，则没有检位码表示，则没有检 错和纠错能力；若用错和纠错能力；若用2 2位码表示（加位码表示（加1 1位监督码），可以位监督码）

9、，可以 检错检错1 1位；若用位；若用3 3位码表示（加位码表示（加2 2位监督码），最多可以检位监督码），最多可以检 出出2 2位或纠错码位或纠错码1 1位。位。 在纠错编码中将信息传输效率也称为编码效率，定在纠错编码中将信息传输效率也称为编码效率，定 义为义为 显然，显然，R R越大编码效率越高，它是衡量码性能的一个越大编码效率越高，它是衡量码性能的一个 重要参数。对于一个好的编码方案，不但希望它检错纠重要参数。对于一个好的编码方案，不但希望它检错纠 错能力强，而且还希望它的编码效率高，但两方面的要错能力强，而且还希望它的编码效率高，但两方面的要 求是矛盾的，在设计中要全面考虑。求是矛盾的

10、，在设计中要全面考虑。 差错控制的基本原理 n k R 2. 汉明距离与检错和纠错能力的关系 码长：码组或码字中编码的总位数为码组的长度。 （1）几个概念 码重：码组中非零码元的数目为码组的重量。 例如“11010”的码长为5，码重为3。 码距：两个等长码组中对应码位上具有不同二进制码的数目 称为码距。 例如：码组1 11010 码组2 01101 (000) (001) (101) (100) (110) (010) (011) (111) a2 a0 a1 在一种编码中，任意两个许用码组间距离的最小值。 汉明距离（最小码距） ： （2）汉明距离和检错和纠错能力的关系 a)a)为为了了检测检

11、测e e位位错码错码，要求最小，要求最小码码距距 min 1de b)b)为为了了纠纠正正t t位位错码错码，要求最小，要求最小码码距距 min 21dt c)c)为为了了纠纠正正t t位位错码错码，同，同时检测时检测e(et)e(et)位位错码错码，要求最小，要求最小码码距距 min 1det 3. 纠错编码的分类 (1)按码组的功能分，有检错码和纠错码两类。 (2)按码组中监督码元与信息码元之间的关系分，有线性码和 非线性码两类。 (3)按照信息码元与监督码元的约束关系，可分为分组码和 卷积码。 (4)按照信息码元在编码前后是否保持原来的形式不变， 可分为系统码和非系统码。 (5)按纠正差

12、错的类型可分为纠正随机错误的码和纠正突发 错误的码。 (6)按照每个码元取值来分，可分为二进制码与多进制码。 3.2 简单的差错控制编码 1. 奇偶监督码 特点：只有一个监督位。 偶监督：码组中“1”的个数为偶数。 1210 , nn aaa a 1210 0 nn aaaa 信息位监督位 奇监督：码组中“1”的个数为奇数。 1210 1 nn aaaa 只能检出奇数位错码。 2. 水平奇偶监督码 思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶 监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输： 11101110011000010101，接收端仍将码元排成与发送端一样的

13、方阵形 式，然后按行进行奇偶校验。 信信 息息 码码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 水平偶监督码 可以检出奇数位错误和长度不大于方阵中行数的突发错误。 3. 二维奇偶监督码（水平垂直奇偶监督码） 思想方法：在水平监督基础上对方阵中的每一列再进行奇偶校验。 发送时按行或按列的顺序传输，接收端重新将码元排成与发送时的方阵 形式，然后每行、每列都进行奇偶校验。 二维偶监督码 信信 息息 码

14、码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 监督码元监督码元 0 1 1 0 1 1 0 0 0 1 1 可以纠1位错码； 可以检出某行或某列上的奇数位错码和长度不大于方阵中行数(列数)的突发错码； 可以检出一部分偶数位错码； 不能检出错码恰好分布在矩阵4个顶点上的偶数位错码。 3.3 汉明码及线性分组码 汉明码特点 可以纠正一位错码，且d0=3 3.3.1 汉明码 1.码长和监督位的关系：

15、1021nn aSaaa 若使用偶监督：只有一位监督位 0 a 接收端译码时，实际上就是计算： 0S 1S 若 无错； 有错。 1位监督位，有1个校正子。 只能表示有错和无错，不能指示错码位置。 21 r n 7,44,3,kr如汉明码，只能纠一位错码 码长和监督位的关系 2位监督位，就有2个监督关系式，也有2个校正子。 12 S S 12 00 01 10 11S S ， ， ， 无错 指示错码位置 （n, k）汉明码，监督位 r=n-k，可构造出r个监督关系式 来指示一位错码的n种可能位置，要求 3460 3561 4562 aaaa aaaa aaaa 1.1.（7 7, , 4 4）汉

16、汉明明码码 a6 a5 a4 a3：信息码元； a2 a1 a0：监督码元 信息码元与监督码元的关系： 1）（）（7, 4）汉明码汉明码 16542 Saaaa s1 s2 s3 错码位置错码位置 0 0 0 无错 0 0 1 a0 0 1 0 a1 1 0 0 a2 0 1 1 a3 1 0 1 a4 1 1 0 a5 1 1 1 a6 校正子与错码位置的关系 26531 Saaaa 36430 Saaaa 3r 有3个校正子 123 ,SSS 例例3-13-1： 接收端收到某（7,4）汉明码为1001010，问：此（7,4）汉明 码是否有错？错码位置如何？ 计算校正子 16542 1000

17、1Saaaa 26531 10111Saaaa 36430 10100Saaaa 得校正子 为110， 123 S S S 码组有错。 5 a 正确码组：1101010 3460 3561 4562 aaaa aaaa aaaa 6542 6531 6430 0 0 0 aaaa aaaa aaaa 2）（7,4）汉明码的产生 由监督关系式： 移项，解出监督位： 解决问题：由信息位计算监督位解决问题：由信息位计算监督位 （7,4）汉明码的许用码组 假设发送端的码字是A15=1111111， 传输过程中第4位a3出现了错误，即接收的码字是B=1110111 不是许用码组。 信息码 a6 a5 a

18、4 a3 码组A a6 a5 a4 a3 a2 a1 a0 信息码 a6 a5 a4 a3 码组A a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1

19、 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 例例3-23-2： 已知信息码为1101，求所对应的（7,4）汉明码。 计算监督位 2654 1100aaaa 1653 1111aaaa 0643 1010aaaa 汉明码码组：1101010 3）编码效率编码效率 （7,4）汉明码的编码效率： 4 57% 7 k R n 3.3.2 线性分组码 线性码：监督码元与信息码元之间满足一组线性方程。 分组

20、码：监督码元仅对本码组中的码元起监督作用。 1.监督矩阵 以（7,4）汉明码为例 6542 6531 6430 0 0 0 aaaa aaaa aaaa 6543210 6543210 6543210 11101000 11010100 10110010 aaaaaaa aaaaaaa aaaaaaa 简写为+ + 线性分组码：既是线性码又是分组码。 6 5 4 3 2 1 0 11101000 110101002 10110010 a a a a a a a 模 1110100 1101010 1011001 H 写成矩阵形式 00 TTT HAAH 简写为 r = P I 2654 165

21、3 0643 aaaa aaaa aaaa 6 2 5 1 4 0 3 1110 1101 1011 a a a a a a a 2106543 111 110 101 011 a a aa a a a 6543 a a a aQ T QP 其中： 监督位 信息位 监督位与信息位的关系（矩阵表示） 2.生成矩阵 用途：由信息位和生成矩阵可得出整个码组。 生成矩阵： k GI Q 以（7,4）汉明码为例 120 nn AaaaG 信信息息位位典典型型的的 111 110 101 011 Q k GI Q 1000111 0100110 0010101 0001011 如（7,4）汉明码表中的第3

22、个码组 信息码 a6 a5 a4 a3 码组A a6 a5 a4 a3 a2 a1 a0 信息码 a6 a5 a4 a3 码组A a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0

23、0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 66432106643 Aa a a a a a aa a a aG 求整个码组 1000111 0100110 0010 0010101 0001011 0010101 注意：生成矩阵G各 行本身就是一个码组。 加例题！ 二元域上只有两种运算：加和乘。运算规则如下： 加乘 000 0 11 1 01 1 10 0 00

24、0 10 1 00 1 11 3.监督矩阵和生成矩阵的关系 , T rk H = PIQPGI Q 例例3-33-3：某（7,4）线性分组码，监督方程如下，求监督矩阵H和典型的 生成矩阵G。如信息码为0010，求整个码组。 2653 1643 0543 aaaa aaaa aaaa 6543210 6543210 6543210 11011000 10110100 01110010 aaaaaaa aaaaaaa aaaaaaa 监督方程改写为 得监督矩阵： 1101100 1011010 0111001 r HP I 110 101 011 111 T QP 典型生成矩阵： 1000110

25、0100101 0010011 0001111 k GI Q 如信息码为0010，则整个码组为 0010AG 1000110 0100101 0010 0010011 0001111 0010011 4.线性分组码的主要性质 (1) (1)封封闭闭性性 是指一是指一种线种线性分性分组码组码中的任意中的任意两个码组两个码组之逐位模之逐位模2 2和仍和仍为这种为这种 码码中的另一中的另一个许个许用用码组码组。 (2) (2) 码码的最小距离等于非零的最小距离等于非零码码的最小重量。的最小重量。 3.4 循环码 循环码是一种线性分组码。 3.4.1 循环码的循环特性 表表3-13-1（7,37,3）

26、循）循环码环码的一的一种码组种码组 码组编号码组编号 信息位信息位监督位监督位 码组编号码组编号 信息位信息位监督位监督位 a6a5a4a3a2a1a0a6a5a4a3a2a1a0 1000000051001011 2001011161011100 3010111071100101 4011100181110010 循环码的循环特性是指在循环码中任一许用码组经过循环 移位后所得到的码组仍为它的一个许用码组。 第2码组右移1位得到第5码组； 第5码组右移1位得到第7码组。 1210 1210 ( ) nn nn A xaxaxa xa x 1210 (,) nn Aaaa a 2.码多项式的表示

27、及运算规则 643 1A xxxxx 1011011A 例如，码组为 则码多项式为： 码多项式的运算：加、减、乘、除运算 1 1）码码多多项项式的加法式的加法运运算：同算：同幂幂次相加，系次相加，系数进数进行行异异或或运运算算 kkkkk k k k k k k cbabaxcxbxa 2 2）码码多多项项式的式的减减法法运运算：同加法算：同加法运运算算 k k k k xaxa- 码组为码组为 则码则码多多项项式式为为： A B C 000 011 101 110 3 3）异异或或运运算（算（逻辑逻辑加和加和逻辑减逻辑减）的）的真值真值表表 CBABABA 4 4）码码多多项项式的乘法式的乘

28、法运运算：服算：服从从一般的代一般的代数规数规律律 1 23 xxx) 1() 1( 2 xxx) 1)(1( 2 xx 5 5）码码多多项项式的除法式的除法运运算：服算：服从从一般的代一般的代数规数规律律 1 1 1 1 22 23 x x x x xx 6 6）码码多多项项式的除法式的除法运运算算简简化表示化表示 ) 1(1 223 xxxx模 余式（模除式）被除式 例如例如 上式上式还还可表示可表示为为 3.4.2 循环码的生成多项式和生成矩阵 1.生成多项式 g(x) 生成多项式的寻找方法： （n,k）循环码的 个码组中，有一个码组前k-1位码元均为0，第k 位码元为1，最后一位为1，

29、此码组对应的多项式为生成多项式。 2k 对于线性分组码，有了典型的生成矩阵G，就可以由k个信息 码得出整个码组。如果知道监督方程，便可得到监督矩阵H，而由 监督矩阵和生成矩阵G之间的关系则可以求出生成矩阵G。这里介 绍求生成矩阵G的另一种方法，即根据循环码的基本性质来找出它 的生成矩阵。 由于G的各行本身就是一个码组，如果能找到k个线性无关的 码组，就能构成生成矩阵G。 。其最高幂次为 即为生成多项式，此码组对应的多项式位（最后一位）码元为，第为 位码元，第位码元均为前个码组中，有一个码组循环码的 称为生成多项式。，组便可构成生成矩阵 个许用码个许用码组。这对应的码组共构成的一个许用码组，连同

30、 循环码所对应的码组都是根据循环码的特性 kn k k kn kn kn kn x xgn kkkn xgG kkxg knxgxxgxxxg xgxgxxg k ggg ),(11 012),( )( )( ),()(),(),(, 100)( 1 ) 101000( 12 1 1 1 121 例例3-4:3-4: 求表3-1所示的（7,3）循环码的生成多项式。 码组编号码组编号 信息位信息位监督位监督位 码组编号码组编号 信息位信息位监督位监督位 a6a5a4a3a2a1a0a6a5a4a3a2a1a0 1000000051001011 2001011161011100 301011107

31、1100101 4011100181110010 42 1g xxxx 2.生成矩阵G 1 2 k k xg x xg x G x xg x g x 典型的生成矩阵 k GI Q 通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵 单位方阵 例例3-53-5：求例3-4所示的（7,3）循环码的典型生成矩阵G。 42 1g xxxx 生成矩阵多项式 2 x g x G xxg x g x 6432 532 42 1 xxxx xxxx xxx 生成矩阵 1011100 0101110 0010111 G 1001011 0101110 0010111 31 1 行行行行 取取代代第第 行行 3

32、.生成多项式的另一种求法 （n,k）循环码的生成多项式是 的一个（n-k）次因式。 1 n x 例例3-63-6： 求（7,3）循环码的生成多项式。 7323 1111xxxxxx 生成多项式有两个： 3242 111g xxxxxxx 3432 111g xxxxxxx 生成多项式不同，产生出的循环码码组也不同。 3.4.3 循环码的编码方法 121 1210 nnn kn k kk m xmxmxm xm x 信息位对应的码多项式： 循环码的码多项式 1 n k xm x 求求 2 n k xm xr x q x g xg x 3 n k A xxm xr x 下一页上一页 循环码的编码

33、当M=110，所以 即所得的码字为A=1100101 。 xxxM 2 )( 5624 )()(xxxxxxMx kn )( 1 1 1)( )( 2 2 24 56 xg x xx xxx xx xg xMx kn 1)( 2 xxr 1)()()( 256 xxxxrxMxxA kn 3.4.4 循环码的解码方法 1.检错的实现 无差错 A x ， 发送码组 R x ， 接收码组 若码组无错 A xR x ， R xrx Qx g xg x A xR x 若码组有错，则 接收码组 若码组无错 0rx 0rx 检测到差错 解码器的核心：除法器 121132 121CRCxxxxx 国际通信中

34、常用的是循环冗余校验（CRC） 生成多项式为： 16152 161CRCxxx 16125 1CRCITUxxx 1 24 5781011121622232632 xxx xxxxxxxxxxxCRC-32 CRC IS-95 CDMA 1 2 6781112131520212930 xx xxxxxxxxxxx 3.5.1 卷积码的基本概念 卷积码又称连环码，是非分组码。没有严格的代数结构 卷积码的监督位不仅取决于这段时间的k个信息位，还取 决于前N-1段规定时间内的信息位。 1.卷积码的概念 编码效率： 即卷即卷积码积码的的监监督位不督位不仅对仅对本本码组码组起起监监督作用，督作用，对对前