通信原理差错控制编码课件

《通信原理差错控制编码课件》由会员分享，可在线阅读，更多相关《通信原理差错控制编码课件（80页珍藏版）》请在金锄头文库上搜索。

1、1,联合战术通信教研组 张伟明,理工大学通信工程学院,第七章 差错控制编码,数字通信原理,2,第7章 差错控制编码,7.1 概述 7.2 纠错编码的基本原理 7.3 常用的简单编码 7.4 线性分组码 7.5 循环码 7.6 卷积码 7.7 伪随机序列 7.8 现代编码技术,3,7-1 概述,信源编码：为了提高数字信号的有效性而采取的编码，又称有效性编码； 信道编码：为了提高数字通信的可靠性而采取的编码，又称可靠性编码、抗干扰编码、纠错编码或差错控制编码。 信道编码原理：在原始数字信号中加入带有规律性的码元，信道译码器利用这些规律性来鉴别是否发生错误，或进行错误纠正。,4,7-1 概述,编码的

2、本质：增加冗余度，牺牲有效性以提高可靠性。,编码的方法：对原信息进行变换，加入附加信息(即监督码)。,例: (4,1)重复码 0: 0000 1: 1111,5,对错误的处理方式：检错、纠错、纠检结合,一、差错及信道分类,6,二、差错控制的基本工作方式,7,7-2 纠错编码的基本原理,用两位编码可表示4种天气：,增加1位监督位，则可检测1位错误。,3位编码共有8个码组，上述4种为许用码组（合法码组），其它4种为禁用码组。,8,（1） 码长、码重和码距 码长n：码组(码字)中码元的数目。 码重w：码组中非0码元的数目。 码距d：两个等长码组之间对应位不同的数目称为这两个码组的的汉明距离，简称码距

3、。 例如码组C1=11010，则码长n=5，码重w=3； C1=11010与码组C2=10100之间的距离为d=3。 两个二进制码组模二相加得到的新码组的重量就是这两个码组之间的距离。,1.纠错码的基本概念,9,2.分组码的纠（检）错能力与d0的关系,最小码距d0：所有码组之间的最小码距，决定码的纠检错能力。,（1）检测e个随机错误：,（2）纠正t个随机错误：,（3）纠正t个同时检测e（t）个随机错误：,10,2.分组码的纠（检）错能力与d0的关系,以（n,1)重复码为例：,A、B两种消息用“1”、“0”表示，编为(2,1)重复码为“11”及“00”,d0为2，可检测1位错,编为(3,1)重复

4、码为“111”及“000”,d0为3，用于检错时，可检出2位错 用于纠错时，根据最大似然准则，可纠正1位错,编为(4,1)重复码为“1111”及“0000”,d0为4，用于检错时，可检出3位错 用于纠错时，可纠正1位错的同时检出2位错,11,对纠错码的基本要求是： 纠错和检错能力尽量强； 编码效率尽量高； 码长尽量短； 编码规律尽量简单。,3.对纠错编码的基本要求及效用,编码效率：码元中信息元所占的比例，通常用R=k/n来表示,12,4.纠错编码的效用,采用差错控制编码，即使仅能检测或纠正码组中12个错误，也可以使误码率下降几个数量级。这就表明，即使是较简单的差错控制编码也具有较大实际应用价值

5、。,码长为n的码组中恰好发生r个错码的概率为 ：,当码长n7，pe=103时，则有,13,1.奇偶监督码(奇偶校验码）： 在n1个信息元后面附加一个监督元，使得长n的码子中1的个数保持为奇数或偶数的码称为奇偶监督码。,7.3 常用的简单编码,偶校验码监督方程：,奇校验码监督方程：,d0=2，可检测1位错及其它奇数个错,14,码长为5的偶监督码,15,又称行列监督码或矩阵码。它同时对水平方向及垂直方向的码元实施奇偶监督。,2.二维奇偶监督码,L5，m10的行列监督码,16,突发错误：逐行传输时，能检测长度b m+1=11的突发错误; 逐列传输时,能检测长度bL+1=6的突发错误；,2.二维奇偶监

6、督码,随机错误：所有1、2、3及其它奇数个错；大部分偶数个错； 不能检矩形4个顶点的偶数个错,17,3.恒比码：,又称等重码或定1码，码字中1和0的位数保持恒定比例。我国电传通信采用3：2数字保护码，也称为5中取3恒比码。,3：2数字保护码,能够检测所有奇数个错误及部分偶数个错误；不能检测 “1”错为“0”与“0”错为“1”成对出现的错码。 实际使用经验表明，它能使差错减至原来的十分之一左右。,18,7.4 线性分组码,（系统）分组码的结构,19,7.4 线性分组码,7.4.1 线性分组码的特点 码字用 表示，监督码元与信息码元之间的关系可用如下线性 方程组表示(以（7，3）分组码为例)： 线

7、性分组码的封闭性：码字集中任意两个 码字对应位模2加后得到的组合仍然是该 码字集中的一个码字。 因此，线性分组码的最小码距必等于码字 集中非全0码字的最小重量。,（7，3）码的码字表,20,7.4.2 线性分组码的编码,简记为：,监督方程组改写为：,此（7，3）分组码的监督矩阵：,21,7.4.2 线性分组码的编码,22,7.4.2 线性分组码的编码,线性分组码的监督矩阵H由r行n列组成，r=n-k，且这r行是线性 无关的。监督矩阵具有形式： ，其中 为 的单位矩 阵。P是 的矩阵。从而 可通过以下矩阵运算由信息元求监督元： 或,23,7.4.2 线性分组码的编码,线性分组码的典型生成矩阵为:

8、 ,其中 是 的 单位矩阵。所以有 由典型生成矩阵生成的码是系统码: 如 时，通过生成矩阵求得的码字为 :,24,7.4.2 线性分组码的编码,例：已知（7，3）线性分组码监督矩阵为,求： （1）监督元与信息元之间的关系式； （2）生成矩阵； （3）此码的全部码字； （4）此码的码距 及纠、检错能力； （5）此码的编码效率。,25,7.4.2 线性分组码的编码,解：4个监督元和3个信息元之间的关系为,生成矩阵,除全零码字以外的7个码字的重量最小值即为此（7，3）分组码的最小码距。最小码距,如：,26,7.4.2 线性分组码的编码,例：重复码是最简单的一类线性分组码。（n，1）重复码总共只有2个

9、码字，一个全0码字，另一个是全1码字。如（5，1）重复码的两个码字分别为“00000”和“11111”。试求出（5，1）重复码的监督矩阵和生成矩阵。,解：,27,7.4.3 线性分组码的译码,S是1行r列矩阵，它与错误图样有对应关系，而与发送码字无关。故能确定传输中是否发生了错误及错误的位置。,发送码字：,接收码字：,发送码字和接收码字之差：,错误图样 ：,码字与监督矩阵约束关系：,若传输发生错误时：,伴随式：,28,7.4.3 线性分组码的译码,以前面所列举的（7，3）码为例： 1求出错误图样E与伴随式S之间的关系。错1位的7种错误图样所对应的伴随式，刚好对应 中的7行。,伴随式和错误图样的

10、对应关系:,29,7.4.3 线性分组码的译码,2计算接收码字的伴随式，然后查上面表得错误图样。 如接收码字为B1100111，则其伴随式为：,查上面表得错误图样E1000000 ，可见接收码字中b6有错误。,3用错误图样纠正接收码字中的错误。,30,7.4.3 线性分组码的译码,例：已知（7,3）线性分组码监督矩阵为 （1）检验“1100111”是否为码字； （2）当译码器接收到“1100111”时，求译码器的输出。,纠正后的码字：,译码器输出：前3位信息码元“100”。,31,7.4.4 汉明码,31,(1)加多少位监督元可满足要求，最经济？ (2)r位监督元如何加？有没有一般规则？ 以r

11、=3为例,编码器,k位信息元,n位码字,k位信息元,n-k=r位监督元,取“”号,最经济：在纠1位错情况下冗余最小,32,a4错,a3错,无错,a2错,a1错,a6错,a5错,a0错,s2 s1 s0,1 1 1,1 1 0,1 0 1,0 1 1,1 0 0,0 0 0,0 1 0,0 0 1,r=3,n=7, k=4,信道,对应标识,7.4.4 汉明码,33,a4错,a3错,无错,a2错,a1错,a6错,a5错,a0错,s2 s1 s0,1 1 1,1 1 0,1 0 1,0 1 1,1 0 0,0 0 0,0 1 0,0 0 1,r=3,n=7, k=4,S2=a6+a5+a4+a2,S

12、1=a6+a5+a3+a1,S0=a6+a4+a3+a0,1、列出所有差错情况；,2、确定一一对应标识；,3、找出监督码元与信息码元关系；,S2=a6+a5+a4+a2,S1=a6+a5+a3+a1,S0=a6+a4+a3+a0,7.4.4 汉明码,34,34,34,编码效率：,(7,4)汉明码所有16个码字,35,7.4.4 汉明码,汉明码：一种高效率的纠单个错误的线性分组码。其特点是最小码 距 ，码长n与监督元个数r满足关系式 。所以有（7，4）、（15，11）、（31，26）等汉明码。,1（7，4）汉明码的编码监督元 与信息元之间的关系：,从而：,36,7.4.4 汉明码编码,由汉明码监

13、督矩阵：,可得：,从而：,37,7.4.4 汉明码编码,由 ，可得汉明码16个码字：,38,7.4.4 汉明码译码,2汉明码的译码： 码长为7的码字中至少加入3位监督元才能纠单个错误，（7，4）汉明码在7位码字中只有3位监督元，因此（7，4）汉明码是一种纠单个错误的编码效率最高的线性分组码。,（7，4）汉明码伴随式和错误图样的对应关系：,39,7.4.4 汉明码译码,（7,4）汉明码的7种错误图样与7个伴随式之间的关系 只要一一对应就不会影响码的纠、检错能力。所以改变 上表的对应关系，即得到不同的（7，4）汉明码的 监督关系。如改变上表的对应关系为：,从而监督矩阵为,得到另一个（7，4）汉明码

14、的监督关系方程组为：,按此方法还可构造出其它不同的（7，4）汉明码的监督关系，进而得到不同的（7，4）汉明码。尽管码字集不同，但它们具有相同的性能，即编码效率相同，纠、检错能力相同。,40,作业,计算机处理信息一般以字节（8bit）或字（16bit或32bit）为单位。为便于处理，信息编码后最好为8、16或32bit。请设计一种（8，4）线性分组码，给出H、G、全部码字、最小码距d0及纠检错能力。,41,线性分组码小结,生成矩阵G,监督矩阵H,编码信道,信息M,码组A,BAE,错误图样E,A=MG,S=BHT,码组B,伴随式S,E,ABE,42,线性分组码,任一码组循环移位所得的序列仍在该码组

15、集中。,7-5 循环码,43,1、码多项式,例：A1101001,码多项式的系数表示码元值（取0或1），变量 的指数表示码元位置：,44,2、多项式除法及模运算,例：,对于二进制编码，码多项式的系数按模2运算。,又如：,45,3、生成多项式,循环码中，除全0码字外，次数最低的码字多项式称为生成多项式，并用g(x)表示。,g(x)具有如下特性： （1） g(x)是xn+1的一个因子； （2） g(x)是r=n-k次多项式； （3） g(x)的常数项为1。,如某(7,3)循环码生成多项式为,循环码完全由其码字长度n及生成多项式所决定。,46,3、生成多项式,例：对于n=7的循环码，有： x7+1 = (x+1 ) (x3+ x2 +1 ) (x3+x+1 ),(7,4)循环码:g(x)=(x3+ x2 +1 )或g(x)=(x3+x+1 ),(7,3)循环码:g(x)=(x4+x2+x+1 )或g(x)=(x4+x3+x2+1 ),生成多项式寻找： 对xn+1进行因式分解，找出r=n-k次因式， 也即寻找符合上述三个条件的多项式。,47,4