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

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 概述,编码的本质：增加冗余度，牺牲有效性以提高可靠性。,编码的方法：对原信息进行变换，加入附加信息(即监督码)。,例: (4,1)重复码 0: 00001: 1111,5,对错误的处理方式：检错、纠错、纠检结合,一、差错及信道分类,6,二、差错控制的基本工作方式,7,7-2 纠错编码的基本原理,用两位编码可表示4种天气：,增加1位监督位，则可检测1位错误。,3位编码共有8个码组，上述4种为许用码组（合法码组），其它4种为禁用码组。,8,（1） 码长、码重和码距码长n：码组(码字)中码元的数目。码重w：码组中非0码元的数目。码距d：两个等长码组之间对应位不同的数目称为这两个码组的的汉明距离，简称码距。例如码组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)重复码为“111”及“000”,d0为3，用于检错时，可检出2位错用于纠错时，根据最大似然准则，可纠正1位错,编为(4,1)重复码为“1111”及“0000”,d0为4，用于检错时，可检出3位错用于纠错时，可纠正1位错的同时检出2位错,11,对纠错码的基本要求是：纠错和检错能力尽量强；编码效率尽量高；码长尽量短；编码规律尽量简单。,3.对纠错编码的基本要求及效用,编码效率：码元中信息元所占的比例，通常用R=k/n来表示,12,4.纠错编码的效用,采用差错控制编码，即使仅能检测或纠正码组中12个错误，也可以使误码率下降几个数量级。这就表明，即使是较简单的差错控制编码也具有较大实际应用价值。,码长为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.二维奇偶监督码,随机错误：所有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）分组码为例)： 线性分组码的封闭性：码字集中任意两个码字对应位模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 线性分组码的编码,线性分组码的典型生成矩阵为: ,其中 是 的单位矩阵。所以有由典型生成矩阵生成的码是系统码: 如 时，通过生成矩阵求得的码字为 :,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个码字，一个全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行。,伴随式和错误图样的对应关系:,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=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,S1=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 汉明码编码,由汉明码监督矩阵：,可得：,从而：,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）汉明码的监督关系方程组为：,按此方法还可构造出其它不同的（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,线性分组码,任一码组循环移位所得的序列仍在该码组集中。,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、生成矩阵G,若T(x)是一长为n的码字多项式，则xiT(x) mod xn+1相当于码字T(x)循环左移i位，因而也是一个码字。,如：码长n=7 的码多项式T(x)=(x6+x5+x2+1 )，对应的码字为1100101，则,对应的码字为0101110,48,4、生成矩阵G,由前面讨论的线性分组码可知，生成矩阵G由k个线性无关的码字组成，G是一k行n列矩阵。,又知g(x),xg(x),xk-1g(x)都是码字，且是线性不相关的，因此可以构成循环码的生成矩阵：,49,4、生成矩阵G,例：(7,3)循环码,r=4次码多项式为x4+x2+x+1，故有：,50,5、循环码的编码,由生成矩阵可生成循环码的所有码字：,结论：所有码多项式T(x)都可被g(x)整除；所有小于n次的g(x)的倍式都是码多项式。 即T(x)是次数n的多项式，则：,已知生成矩阵：,51,5、循环码的编码,（1）用xn-k乘m(x)，即信息码后附加上（nk）个“0”。,（2）用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即,（3）编出的码组T(x)为：,如(7,3)码g(x)=x4+ x2+ x+1，设 m(x)x2+x，即信息码为110：,（1）xn-km(x)x4（x2+x）= x6+x5,（2）,（3）T(x)1100000+1011100101,52,5、循环码的编码,多项式除法：g(x)除xn-km(x)，求余式r(x)的实现。,（1）开关S倒向下方，输入信息位。信息位输出的同时做除法运算。（2）信息位全部进入除法器后，开关转向上。此时反馈端为0，移存器中即为除法余项。,g(x)=x4+ x2+ x+1 的除法电路:,53,6、循环码的译码原理,纠错与检错,S(x) = R(x) mod g(x)= E(x) mod g(x),54,译码器的大致结构,除法电路(计算S),组合逻辑(S到E的转换),S,E,B,A,55,循环码译码器方案,(7,3)循环码,g(x)= x4+x2+ x +1,56,7-5-3缩短循环码,采用缩短循环码的原因：在系统设计中，码长n、信息位数k和纠错能力常常是预先给定的。并不是所有长度n和k上都能找到相应的满足某纠错能力的循环码。这时若将循环码缩短，即可满足n、k和纠错码能力的要求，且有循环码编译码简单的特点。,57,缩短循环码的构成,58,交织码又称交错码，是一种能纠正突发错误的码，它是以交错的方法来构造码的。 把纠随机错误的（n，k）线性分组码的m个码字，排成m行的一个码阵，该码阵称为交错码阵。一个交错码阵就是交错码的一个码子。码阵在传输时按列的次序进行，这样可以将突发错误变为随机错误加以纠正。,7-5-4 交织技术,59,交织码纠突发错的原理,例：(7,4)汉明码，4行，按列传输。,60,7-6 卷积码,初始态：00,输入：11010000,输出：,(2,1,2)卷积码,(n,k,m)卷积码,m:编码存储(m+1):约束度n(m+1):约束长度,C1=S1+S2+S3，C2=S1+S3,61,卷积码图解法： 状态图 树图 格图,卷积码的表示方法,62,(2,1,2) 卷积码的树图,0,1,63,00,a:00,00,00,00,00,00,11,b:01,c:10,d:11,11,11,11,11,11,(2,1,2) 卷积码的格状图,64,卷积码的译码,卷积码译码可分为：代数译码。代数译码是利用生成矩阵和监督矩阵来译码，最主要的方法是大数逻辑译码。概率译码。概率译码比较实用的有两种：维特比译码和序列译码。,维特比译码思路： 把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。,65,1,1,2,2,3,1,3,3,4,2,4,4,1,3,维特比译码(1),发送码字：11 01 01 00 10 11 ,发送信息：110100 ,66,维特比译码(2),67,7-7 伪随机序列,确知序列：有规律、可控、可复现序列,随机序列：无规律、不可控、不可复现序列,伪随机序列：具有随机特性的确知序列,m序列-由线性反馈移位寄存器产生的周期最长的码序列。它具有伪随机特性，是目前广泛应用的一种伪随机码。,68,线性反馈移位寄存器,抽头位置：由特征多项式f(x)决定,初始状态：非全0,应设置全0排除电路,69,m序列对特征多项式的要求：本原多项式,n次多项式f(x)是本原多项式，则：f(x)是既约多项式(不可再分解因式)f(x)可以整除(xp+1)，p=2n-1f(x)不可整除(xq+1)，qp,n次本原多项式决定n级移位寄存器的抽头系数，即决定了一个m序列。本原多项式通常可以查表得到。,70,m序列产生器,例：f(x) = x4+x+1,71,m序列的性质,1. 均衡特性（平衡性） m序列每一周期P(P=2n-1)中1的个数比0的个数多1。P足够大时，在每一周期中1与0出现的次数基本相同（均衡）。,2. 游程特性（游程分布的随机性） 游程是序列中连续出现同种元素的统称。M序列每个周期中游程总数为2n-1，“1”游程与“0”游程的数目各占一半。,m序列：0001111010110010001111,72,m序列的性质(2),3. 移位相加特性（线性叠加性） 一个周期为P的m序列mP与其任意次移位后的序列mr模二相加，所得序列mS必是mP某次移位后的序列，即mr仍是周期为P的m序列。,m序列：000111101011001000111101011001000,左移4：111010110010001111010110010001111,111101011001000111101011001000111,73,m序列的性质(3),4.自相关特性,自相关函数R(j): m序列与其右移j位的序列，对应位相乘相加。,约定：0: +1 + 1: -1 -,R(1),R(2),R(14),R(15),-1,-1,-1,15,74,m序列的性质(4),4.自相关特性(续),自相关函数R(j)是周期函数：,75,m序列的性质(5),5.伪噪声特性 对白噪声等间隔取样，把样值的极性排成序列，得到： (1)序列中、出现的概率相等； (2)游程长度为1的游程约占游程总数的1/2,长度为2的游程约占游程总数的1/4。一般长度为k的游程约占1/2k，且、游程的数目各占一半； (3)归一化自相关为R()=() ，是强度为1的冲激函数。,76,扩频通信帧同步头通信加密误码率的测量,m序列的应用,77,7-8 现代编码技术,一、网络编码调制二、Turbo编码三、LDPC编码,78,一、网格编码调制（TCM）,概念:网格编码调制（TCM）引入了编码和调制相结合统一进行设计的方法，在不增加信道传输带宽的前提下降低差错率编码。,两个特点：（1）信号点比无编码的信号点要多，这增加的信号点使编码有了冗余，而不牺牲带宽。（2）采用卷积码的编码规则，使信号点之间引入相互依赖关系。仅有某些信号点图样或序列是允许用的信号序列。,79,8PSK信号空间的集合划分,80,4状态编码方案,