第十章 差错控制编码 10.1 差错控制编码的基本原理 10.2常用的简单编码 10.3 线性分组码 10.4循环码 10.5卷积码.

Presentation on theme: "第十章 差错控制编码 10.1 差错控制编码的基本原理 10.2常用的简单编码 10.3 线性分组码 10.4循环码 10.5卷积码."— Presentation transcript:

1 第十章 差错控制编码 10.1 差错控制编码的基本原理 10.2常用的简单编码 10.3 线性分组码 10.4循环码 10.5卷积码

2 10.1 差错控制编码的基本原理 发生误码原因： 系统特性不理想（乘性干扰），数字信号通过系统时 产生波形失真，在接收端判决时会产生判决错误。 信道中的噪声（加性干扰），这种干扰随机地与信号 叠加，使信号波形产生失真，引起判决错误。 解决办法： （1）适当增加发送信号功率。 (2) 选择抗噪声性能好的调制解调方式。 (3) 采用最佳接收 。 （4）采用差错控制编码。 2019/2/25 信息与通信工程系

3 10.1 差错控制编码的基本原理 信源编码目的：提高通信系统的有效性。
差错控制编码（信道编码、抗干扰编码或纠错编码）目的：提高通信的可靠性。 差错控制编码方法：通过人为地加入多余度，使信 号在一定的干扰条件下，具有 检测或纠正错码的能力。 2019/2/25 信息与通信工程系

4 信道分类：随机信道、突发信道、混合信道。
10.1 差错控制编码的基本原理 信道分类：随机信道、突发信道、混合信道。 （1 ） 随机信道：错码出现互不相关、统计独立。 如：高斯白噪声引起的错码。 （2）突发信道：错码的出现前后相关。错码出现时， 在短时间内有一连串的错码，而该时间过后又 有较长的时间无错码。如：随机的强突发脉冲 干扰引起的错码。 （3）混合信道：产生的错码既有随机错码又有突发 错码。 2019/2/25 信息与通信工程系

5 1. ARQ(Automatic Repeat Request)方式
10.1 差错控制编码的基本原理 常用的差错控制方式 1. ARQ(Automatic Repeat Request)方式 (自动请求重发或检错重发) 发端发送出可以发现错误的码字。经过传输到接收端译码后，如果没有发现错误，则输出。如果发现错误，则自动请求发端重发，直到正确接收到码字为止。 2019/2/25 信息与通信工程系

6 10.1 差错控制编码的基本原理 ARQ系统组成 特点：设备简单、双向信道、传输效率低。 2019/2/25 信息与通信工程系

7 10.1 差错控制编码的基本原理 2.反馈校验方式 接收端收到码字后，立即将接收到的码字返回发送端。发送端将返回的码字与发端缓冲存储器中相应的码字比较，若发现与发送码不同，即认为产生了错误，就重发上一次的码字。 特点：设备简单、双向信道、传输效率低。 2019/2/25 信息与通信工程系

8 3. FEC（Forward Error Control，前向纠错 ）方式
10.1 差错控制编码的基本原理   3. FEC（Forward Error Control，前向纠错 ）方式 发送端发出的码字不仅能够发现错误，而且能够纠正错误。在接收端译码后，若没有错误则直接输出。若有错误，则在接收端自动纠正后，再输出。 特点：不需要反向信道、实时性好、传输效率高。 但纠错编译码方法复杂。 2019/2/25 信息与通信工程系

9 4.HEC（Hybrid Error Control,混合纠错）方式
10.1 差错控制编码的基本原理 4.HEC（Hybrid Error Control,混合纠错）方式 将ARQ方式和前向纠错方式结合使用。传输错码较少时，采用前向纠错方式，自动纠正错码。在错码较多时，采用ARQ方式自动请求重发。 2019/2/25 信息与通信工程系

10 10.1 差错控制编码的基本原理 香农有扰信道编码定理：
在有扰信道中只要信息的传输速率R小于信道容量C，总可以找一种编码方法，使信息以任意小的差错概率通过信道传送到接收端，即误码率Pe可以任意小，而且传输速率R可以接近信道容量C。但若R > C，在传输过程中必定带来不可纠正错误，不存在使差错概率任意小的编码。 香农有扰信道的编码定理本身并未给出具体的纠错编码方法，但它为信道编码奠定了理论基础。从理论上指出了信道编码的发展方向。 2019/2/25 信息与通信工程系

11 10.1 差错控制编码的基本原理 误码率： Pe = e –n E(R) 式中，n为编码的码字长度(简称码长)； E(R)为误码指数。
2019/2/25 信息与通信工程系

12 10.1 差错控制编码的基本原理 减小误码率Pe的两种途径： （1）n 及 R一定时，增加信道容量C。由图可见，E(R)
随C的增加而增大。由信道容量公式知， 增加C， 可通过增加S和B来实现；  （2）在C及 R一定的情况下，增加n可以使Pe指数减小。 2019/2/25 信息与通信工程系

13 10.1 差错控制编码的基本原理 重复编码的例子：天气预报消息发布 晴 雨 纠检错能力 第一种 编码方法 1 0 无纠检错能力 第二种
晴 雨 纠检错能力 第一种 编码方法 无纠检错能力 第二种 编码方法 可检1位错（01、10）、 无纠错能力 第三种 编码方法 可检2位错、可纠1位错 （001、010、 011、101、 ） 许用码、禁用码、最大似然准则 2019/2/25 信息与通信工程系

14 10.1 差错控制编码的基本原理 码间距离d 及检错纠错能力 码字：由信息位和监督位组成的一组码元。
用C = ( cn-1 cn-2 … c0 )表示。 （许用码、禁用码） 码元： 组成码字的元素，用Ci表示。 码长：码字中码元的个数，用n表示。 码组：由多个许用码组成的一组码字。 2019/2/25 信息与通信工程系

15 码间距离d（code distances）
10.1 差错控制编码的基本原理 码间距离d（code distances） 简称码距，又称汉明距离，是码组中任意两个 码字之间对应位上码元取值不同的个数。等于两个 码字对应位模2相加后“1”的个数 。 例：111 、000，d =3；11、00 ，d =2。 、 ，d =2 。 2019/2/25 信息与通信工程系

16 最小码间距离d0：码组中各码字之间最小的码距。
10.1 差错控制编码的基本原理 码间距离的几何意义 最小码间距离d0：码组中各码字之间最小的码距。 2019/2/25 信息与通信工程系

17 10.1 差错控制编码的基本原理 最小码间距离d0与检错纠错能力的关系 (1)当码组仅用于检测错误时，若要求检测e个错误，
2019/2/25 信息与通信工程系

18 10.1 差错控制编码的基本原理 (2)当码组仅用于纠正错误时，为纠正t个错误，要求 最小码距为：d0 ≥2t +1 2019/2/25
信息与通信工程系

19 (3)当码组既要检错，又要纠错时，为纠正t个错误，同时检测e个错误，则要求的最小码距为
10.1 差错控制编码的基本原理 (3)当码组既要检错，又要纠错时，为纠正t个错误，同时检测e个错误，则要求的最小码距为 d0≥ e +t +1 (e > t ) 2019/2/25 信息与通信工程系

20 10.1 差错控制编码的基本原理 差错控制编码的效果 在码长为n的码字中刚好发生r个错误的概率为： 当n =7，P=10-3 时，有：
2019/2/25 信息与通信工程系

21 10.1 差错控制编码的基本原理 纠错编码的分类 2019/2/25 信息与通信工程系

22 10.1 差错控制编码的基本原理 编码效率 K：码字的信息码元个数 r：监督码元个数 n: 码元总的个数（总码长） 2019/2/25
信息与通信工程系

23 10.2常用的简单编码 1.奇偶监督码 2.二维奇偶监督码 3.恒比码（等重码） 2019/2/25 信息与通信工程系

24 编码规则：在每个分组的信息位后增加监督位，无论
10.2常用的简单编码 1.奇偶监督码（奇偶校验码） 广泛应用于计算机数据传输中。 编码规则：在每个分组的信息位后增加监督位，无论 信息位有多少位，监督位只有一位。 偶监督码：给信息位后增加一位监督位，使码字中“1” 的数目为偶数。 上式为偶监督码的监督关系，也称为校验方程。 检测能力：检测奇数个错。 2019/2/25 信息与通信工程系

25 10.2常用的简单编码 奇监督码：给信息位后增加一位监督位，使码字 中“1”的数目为奇数。其校验方程为
奇偶监督码的编码效率η较高，尤其是当码长 n 较大时这一特点更为明显。 2019/2/25 信息与通信工程系

26 10.2常用的简单编码 2.二维奇偶监督码 （方阵码、行列监督码 或水平―垂直奇偶监督码） 编码方法：把m 个信息码字排列成一个方阵，每个码字构成方阵的一行，在每一行的最后按奇偶监督规则增加一位水平监督位，再按列的方向每列增加一位垂直监督位（包括行监督位的列） 2019/2/25 信息与通信工程系

27 10.2常用的简单编码 检测能力： 可以检测每行的奇数个错和每列的奇数个错； 行列交叉可以检测每行或每列的偶数个错；但
当发生的错误为刚好构成矩形的四个错码时， 则不能检测出错误。 纠错能力： 只有一行出现奇数个错码时，按行检测可以判断出错在那一行，按列检测可以确定该行的那一列发生了错误，行列交叉可以判断错误的位置，即可纠错。此外，此种编码的效率较高。 2019/2/25 信息与通信工程系

28 10.2常用的简单编码 3.恒比码（等重码） 每个许用码含有相同数目的“1”。码字中“1”与“0”的个数之比是恒定的，故称恒比码。码字中“1”的个数称为码重，因此恒比码又称等重码。 对于某种特定的恒比码，当码长确定后，其“1”的个数就确定了。所以在检测中只要计算“1”的个数就可以确定是否发生错误。恒比码多用于电传机中。 我国电传机传输汉字采用的是“5中取3” 恒比码，其码长为5，码字中“1”的个数为3。这种码我国称为保护电码。码长为5的二进制数共有32种组合，选择其中含有3个“1”的组合作为许用码，为10个。 2019/2/25 信息与通信工程系

29 10.2常用的简单编码 我国的保护电码与国际电码 阿拉伯数字 保护电码 国际电码 01101 5 00111 00001 1 01011
01101 5 00111 00001 1 01011 11101 6 10101 2 11001 7 11100 3 10110 10000 8 01110 01100 4 11010 01010 9 10011 00011 2019/2/25 信息与通信工程系

30 10.3 线性分组码 记为（n, k） 一、线性分组码概念
线性分组码是指信息位和监督位满足一组线性方程，即其编码规则可用一组线性方程来描述的分组码。 记为（n, k） 信息位k 信息位k 监督位r n: 码元总的个数（总码长） 2019/2/25 信息与通信工程系

31 k 位长的二进制码共有 码字, 故 个信息段仅构成 个n 位长的码字，称为许用码字
10.3 线性分组码 系统码：码字的前一部分是连续k 位信息码元，后一部 分是连续r 位监督码元，具有这种结构的线性 分组码称为系统码。否则称为非系统码。 纠错原理 n 位长的二进制码共有 码字。 k 位长的二进制码共有 码字, 故 个信息段仅构成 个n 位长的码字，称为许用码字 而其他 个码字为禁用码字，当出现禁 用码字时就可以发现或纠正错误。 2019/2/25 信息与通信工程系

32 10.3 线性分组码 r 行 二、线性分组码的一致检验（监督矩阵）矩阵[H] 码字矢量 C= [c6c5c4c3c2c1c0]
以（7，3）码 ( k=3, r =4, n =7) 为例： 码字矢量 C= [c6c5c4c3c2c1c0] 信息码元： c6c5c 监督码元 ：c3c2c1c0 监督方程为： r 行 2019/2/25 信息与通信工程系

33 10.3 线性分组码 将上方程系数写为矩阵形式 2019/2/25 信息与通信工程系

34 称[H]为线性分组码的一致检验矩阵（监督矩阵）。
10.3 线性分组码 令 [H]= [H]=[P I4] 称[H]为线性分组码的一致检验矩阵（监督矩阵）。 故有： 2019/2/25 信息与通信工程系

35 10.3 线性分组码 [H]的性质： （1）[H]是 阶矩阵，即行数为监督码元个数， 列数为码长。 [H]中每行元素表明监督方程
元之间的监督关系唯一确定。 （2）[H]=[P I4]，即[H]由两部分组成，前半部称 为[P]矩阵 ，后 半部称为[I]矩阵 。 此时，称 [H]为典型矩阵，只有系统码才具有。 （3）[H]是接收端检错的依据。 2019/2/25 信息与通信工程系

36 [G]矩阵是在给定信息位的条件下，如何生成码字的矩阵。
10.3 线性分组码 三、线性分组码的生成矩阵[G] [G]矩阵是在给定信息位的条件下，如何生成码字的矩阵。 仍以（7，3）码 ( k=3, r =4, n =7) 为例： 码字矢量 C= [c6c5c4c3c2c1c0] 信息码元： c6c5c4 ；监督码元 ：c3c2c1c0 在监督方程基础上，加上信息码元方程。 监督方程 2019/2/25 信息与通信工程系

37 10.3 线性分组码 2019/2/25 信息与通信工程系

38 10.3 线性分组码 生成矩阵[G] 转置 码字 矩阵 故有： 2019/2/25 信息与通信工程系

39 10.3 线性分组码 生成矩阵 2019/2/25 信息与通信工程系

40 推论：由K互相独立的码字可构成生成矩阵。
10.3 线性分组码 [G]的性质： （1）[G]是 阶矩阵，即行数为信息码元个数， 列数为码长。 故若[G]给定，则在已知信息码 元的情况下，就可得到码字（生成矩阵）。 （2）[G]=[IK Q]为标准生成矩阵，[G]中每行是互相 独立的（线性不相关）。实际上，[G]中每行就是 一个许用码字。 推论：由K互相独立的码字可构成生成矩阵。 2019/2/25 信息与通信工程系

41 10.3 线性分组码 [G]的性质（二） （3）[G]与[H]的 关系 [G]=[IK Q] [H]=[P Ir] 可以证明： 或
如上例中： 2019/2/25 信息与通信工程系

42 10.3 线性分组码 [G]的性质（三） （4）对偶码 将一码组（A）中的[H]当作另一码组（B）中的[G]，或反之，则称B为A的对偶码。
如： 则（7，4）为（7，3）的对偶码。 （5）封闭性 线性分组码组中，任意两个码字之和仍是此码组中的一个码字。 2019/2/25 信息与通信工程系

43 10.3 线性分组码 四、线性分组码的译码及伴随式 1.译码 译码是判断接收码字是否为许用码，即根据 判断接收码字 是否满足
判断接收码字 是否满足 定义 为错误图样， 当 时，无误码。 2019/2/25 信息与通信工程系

44 10.3 线性分组码 当 时，认为第i 位发生了误码。 将 代入 中，得： 称 为伴随式，又称校验子。 当 时， 无错误出现。
将 代入 中，得： 称 为伴随式，又称校验子。 当 时， 无错误出现。 2019/2/25 信息与通信工程系

45 10.3 线性分组码 当 时，认为第i 位发生了误码。 此时， 为 中的第i列（从右起）， 故可用 的列来表示误码位置。
故可用 的列来表示误码位置。 由 伴随式可检测 个错误。 2019/2/25 信息与通信工程系

46 10.3 线性分组码 当 时，认为第i 位发生了误码。 此时， 为 中的第i列（从右起）， 故可用 的列来表示误码位置。
故可用 的列来表示误码位置。 由 伴随式可检测 个错误。 要纠正小于或等于t 个错，必须满足 或 2019/2/25 信息与通信工程系

47 10.3 线性分组码 汉明码 汉明码是一种可以纠正单个随机错误的线性分组码。它是一种完备码，编码效率很高。 编码效率 2019/2/25
信息与通信工程系

48 10.3 线性分组码 例： 2019/2/25 信息与通信工程系

49 10.3 线性分组码 汉明码特点 （1）汉明码长 （2）信息位 （3）最小码距 ，纠错能力为 。 （4）编码效率高。 2019/2/25
（3）最小码距 ，纠错能力为 。 （4）编码效率高。 2019/2/25 信息与通信工程系

50 10.4 循环码 一、 循环码的基本概念及码多项式 定义：具有循环性的线性分组码。 循环性：码组中任一许用码字（全“0”码除外）循环左移
（或循环右移）后所得到的码字仍为该循环码组 中的另一许用码字。 2019/2/25 信息与通信工程系

51 10.4 循环码 一种（7，3）循环码 序号 移位次数 信 息 位 监 督 位 000 0000 4 6 100 1110 1 001 1101 5 101 0011 2 010 0111 3 110 1001 011 1010 7 111 0100 2019/2/25 信息与通信工程系

52 10.4 循环码 码多项式：把循环码中的码字用多项式来表示，码字中各 码元的取值作为码多项式的系数。 例：对 码 2019/2/25
例：对 码 2019/2/25 信息与通信工程系

53 10.4 循环码 （模 运算） 则 码多项式运算： [定理10.4.1] 若T (x )是长为n 的循环码中某个许用码字的码
（模 运算） [定理10.4.1] 若T (x )是长为n 的循环码中某个许用码字的码 多项式，则xi· T(x) 在按模 xn +1运算下，也是该 循环码中一个许用码字的码多项式。 如：（7，3）循环码中许用码字 的码多项式为 则 2019/2/25 信息与通信工程系

54 10.4 循环码 （模 运算） 对应的码字为 ，它是该（7，3）循环码中的一另一许用码字，它是循环码 左移3次后形成的。 2019/2/25 信息与通信工程系

55 10.4 循环码 生成多项式及生成矩阵 [定理10.4.2] 在循环码（n，k）中，n-k 次幂的码多项式有一
个，且仅有一个，用g(x)表示。称这唯一的n-k次 多项式g(x)为循环码的生成多项式。g(x)的常数项 不为零。 一旦g(x)确定，则该（n，k）循环码就被确定了。g(x)是循环码中幂次最低的码多项式。由它左移就可产生其它码多项式。比如xg(x)、x2g(x)、x3g(x)等。用k个互相独立的码多项式g(x)、xg(x)、x2g(x)… xk-1g(x)可以构造出循环码的生成矩阵G(x)为 2019/2/25 信息与通信工程系

56 10.4 循环码 生成矩阵 2019/2/25 信息与通信工程系

57 例如，（7，3）循环码中最高次幂为n-k次的码字为0010111，
10.4 循环码 例如，（7，3）循环码中最高次幂为n-k次的码字为 ， 其生成多项式g(x)= x4+ x2+x+1。则利用上式可得其 生成矩阵G(x)为 上式不符合典型生成矩阵的形式，所以它不是典型生成矩阵，由它编出的码字不是系统码。但是对此矩阵作线性变化可以变换成典型生成矩阵的形式。 2019/2/25 信息与通信工程系

58 例如，（7，3）循环码中最高次幂为n-k次的码字为0010111，
10.4 循环码 例如，（7，3）循环码中最高次幂为n-k次的码字为 ， 其生成多项式g(x)= x4+ x2+x+1。则利用上式可得其 生成矩阵G(x)为 上式不符合典型生成矩阵的形式，所以它不是典型生成矩阵，由它编出的码字不是系统码。但是对此矩阵作线性变化可以变换成典型生成矩阵的形式。 2019/2/25 信息与通信工程系

59 10.4 循环码 [定理10.4.3] 循环码（n，k）的生成多项式g(x)是xn +1的一个因式。
x7+1=（x+1）（x3+x2+1）（x3+x+1） 生成多项式可选为 g1(x)=（x+1）（x3+x2+1）=x4+x2+x+1 或 g2(x)=（x+1）（x3+x+1）=x4+ x3+x2+ 2019/2/25 信息与通信工程系

60 10.4 循环码 循环码的编码及解码 m(x)=mk-1 x k-1+ mk-2 x k-2+…+ m1 x+ m0
1. 编码 设信息码多项式为m(x) m(x)=mk-1 x k-1+ mk-2 x k-2+…+ m1 x+ m0 m(x)的最高次幂为k-1。 将m(x)左移n-k位成为xn-km(x)，其最高次幂为n-1。xn-km(x)的前一部分为连续k位信息码，后一部分为r=n-k位的“0”，r正好是监督码的位数。所以在它的后一部分添上监督码，就编出了相应的系统码。 2019/2/25 信息与通信工程系

61 10.4 循环码 所以T(x)能被g(x)整除，其最高次幂为n-1。T(x) 的前一部分为连续k位信息码，后一部分为r=n-k位的监督码。T(x)为循环码的码多项式，而且是系统码。 2019/2/25 信息与通信工程系

62 选择生成多项式：g(x)=x4+ x3+x2+ 1，设信息码为111。
10.4 循环码 例：（7，3）循环码编码过程。 选择生成多项式：g(x)=x4+ x3+x2+ 1，设信息码为111。 （1）信息位m(x)左移n-k位成为xn-km(x)。信息码111左 移4位成为 。 （2）作除法，求出余式r(x)。 （ ） （3） 构成系统码T (x)= xn-km(x)+ r(x)。 = 。 2019/2/25 信息与通信工程系

63 10.4 循环码 g(x)=x4+ x3+x2+ 1， （7，3）循环码的编码器 2019/2/25 信息与通信工程系

64 10.4 循环码 g(x)= gn-k xn-k+gn-k-1xn-k-1+…+ g1 x+1 （n，k）循环码的编码器 2019/2/25
信息与通信工程系

65 判断余式是否为零，即可判断码字R(x)有无错码。
10.4 循环码 2.解码：分检错和纠错两种情况 检错解码原理：它利用任何码多项式都可以被生成多项式g(x)整除原理实现。设发送码字为T(x),接收码多项式为R(x)，做除法有 判断余式是否为零，即可判断码字R(x)有无错码。 2019/2/25 信息与通信工程系

66 10.4 循环码 纠错解码原理 纠正错误，需要知道错误图样E(x)，以便纠正错误。原则上纠错解码可按以下步骤进行。
（1）用生成多项式g(x)除接收码字R(x)=T(x)+E(x)，得到余式； （2）按余式用查表方法或通过某种运算得到错误图样E(x)； （3）从R(x)中减去E(x)，得到纠错后的原发送码字T(x)。 2019/2/25 信息与通信工程系

67 本章习题：10-4、 10-5、10-8、 10-10、10-13、10-18 2019/2/25 信息与通信工程系