西工大通信原理期末复习考研求职必备差错控制编码P课件(PPT 57页)

1、2022/7/211通 信 原 理 电 子 教 案第9章 差错控制编码 西 北 工 业 大 学 （2008.3）第1页，共57页。2022/7/212研究的问题 9.1 引言9.2 纠错编码的基本原理 9.3 常用的简单编码 9.3 线性分组码 9.4 循环码 9.5 卷积码9.6 网格编码调制 第2页，共57页。2022/7/213干扰乘性：均衡加性：调制解调体制、发送功率、最佳接收9.1 引言一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。信道译码检/纠错编码若还不行，则需差错控制编码。目的：在数字通信系统中，为了提高数字

2、信号传输的有效性而采取的编码称为信源编码；为了提高数字通信的可靠性而采取的编码称为信道编码。差错可控第3页，共57页。2022/7/214二、错误的类型随机性错误 （白噪声引起）特点：单个错，错误之间不相关。主要出现在无记忆信道。2. 突发性错误 (脉冲干扰引起）特点：成串错，错误之间有相关性。主要出现在有记忆信道。错误传播。3. 混合性错误第4页，共57页。2022/7/215三、差错控制的方式1. 检错重发(ARQ)收发可检错的码特点: 1）双向通道 2）通信效率低 3）不适于实时通信 4）编、译码设备简单 5）编码效率高总码元 (n bit)= 信元 (k bit)+ 督元 (r bit

3、 )。只检不纠，有错自动要求重发。第5页，共57页。2022/7/2162. 前向纠错 (FEC)收发可纠错的码特点： 1）只需单向信道省信道！ 2）通信效率高； 3）适于实时传输； 4) 译码设备复杂。检错并纠错第6页，共57页。2022/7/2173. 反馈检验法收发原理：收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错重发；否则：PASS特点: 需要双向通道；收发设备简单；传输效率低（最低）。第7页，共57页。2022/7/2189.2 纠错编码的基本原理一. 基本思想信元督元信元督元信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，传输效率

4、（引入冗余码）例：天气预报 信元 督元 0 0 0 晴 0 1 1 云 1 0 1 阴 1 1 0 雨三位码元有23=8种组合，实际使用了22=4种许用码组。其余 001，010，100，111 为禁用码组。检错能力：可检错奇数个错；纠错能力：无。第8页，共57页。2022/7/219例：天气预报，可预报天晴信元 督元 0 0 0 1 1 1冗余量加大，禁用码组比例提高。检错能力：检2；纠错能力：纠1。许用码组2个，禁用码组6个晴阴第9页，共57页。2022/7/2110二. 纠错编码的分类线性码和非线性码分组码、卷积码和循环码系统码和非系统码三. 分组码定义:将信息码分组，为每信息码附加若干

5、个监督码编码，称为分组码。特点: 在分组码中，监督码元仅监督本码组中的信息码元。符号: ( n , k ) , r = n k码字:结构:an-1an-2arar-1a0k个信元r个督元码长n第10页，共57页。2022/7/2111码组的重量和码距及纠错能力1. 重量 码组中非0元素的个数 例: A= ( 10110 ) 码重 = 32. 码距 两两码组对应位上数值不同的个数，记为d。最小码距: 某种编码中各个码组间距离 的最小值，记做d0 d0=dmin码距的几何意义: (n=3) 各顶点沿立方体各边行走的几何距离。码元值：每一码组的三个码元值，就是此立方体各顶点的座标（a2a1a0）最小

6、码距: 1第11页，共57页。2022/7/2112前例中：天气预报 信元 督元 0 0 0 晴 0 1 1 云 1 0 1 阴 1 1 0 雨四个许用码组之间的距离均为2。Why?摈弃d=1的码禁用码组。许用码组最小码距愈大，抗干扰能力愈强！确定最小码距的目的：决定编码的检纠错能力。第12页，共57页。2022/7/21133. d0与纠检错能力若要求检测e个错,则 d0e+1 若要求纠正t个错,则 d02t+1 若要检测e纠正t 个错(同时),则 d0e+t+1, 且et码距与检错和纠错能力的关系如图：t 1 te第13页，共57页。2022/7/21140 1 2 3Ad0(a)0 1

7、2 3 4 5A Bt td0(b)A Bt 1 te(c)图9-4第14页，共57页。2022/7/21159.3 常用的简单编码属于分组码一类。简单、实用。一. 奇偶监督码满足: 偶监督码：码组中1的个数为偶数；奇监督码：码组中1的个数为奇数。检错能力: 所有奇数个错。一半！应用非常多。编码效率:第15页，共57页。2022/7/2116二维奇偶监督码进行横、纵向监督例:0 0 0 0 11 1 1 0 1 01 0 0 1 10 1 0 1 0 00 0 0 0 1 10 1 0 1 10 1 0 1 0横向监督纵 向 监 督纠检错能力: 仍可检错奇数个错 还可检错偶数个错 可纠正一些错

8、码 适于检测突发性错误第16页，共57页。2022/7/2117横比码(等重码)例: 码重为31 . 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0许用码组: C35 = 10禁用码组: 25-10 = 22检错能力: 可检测所有奇数个码元的错 和部分偶数个码元的错,但 不能检测码组中“1”变为“0” 与“0”变为“1”的错码数目相同的那些偶数错码编码效率:第17页，共57页。2022/7/2118例： n=10 , 则 k=5信元码 监督码 合成码 校验码1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 01 0 0 0 1 0 1 1 1 0 1 1

9、1 1 1 0 0 0 0 0 接受端的检测三. 正反码编码规则: 信息位(n/2)中有奇数个“1”,则监督位与信息位相同 信息位(n/2)中有偶数个“1”,则监督位是信息位的反码第18页，共57页。2022/7/21199.4 线性分组码定义：若分组码（n,k）,督元与信元的关系可用一线性方程组来描述，则该分组码（n,k）称为线性分组码。一、汉明码 能纠一位错的线性分组码。定义：是一种能纠正一位错码，且编码效率较高的线性分组码。最小码距：d0=31. 构造原理考察：定义一个监督方程（监督关系式、偶监督）：由于一位校正子只有两种取值，故只能表示有错或无错，不能指出错码的位置。第19页，共57页

10、。2022/7/2120推想:如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有S1 S20 00 1 0 1 1无错可指示一个错码可能出现的位置，共有22-1=3 个位置。第20页，共57页。2022/7/2121再推广:S1 S2 Sr0 0 . 00 0 . 11 1 .1 1无错2r-1 个错的可能位置显然：要求 2r-1n（n=k+r），则可指示（仅一位错时）任一错码的位置包括信元、督元。或： 2rk+r+1可指示一个错码可能出现的2r-1个位置。第21页，共57页。2022/7/21222. 例: 构造k=4 的汉明码（1）确定 r由

11、2r k+r+1 得 r = 3，则 n= k+r=7 ( 7,4 ) 分组码第22页，共57页。2022/7/2123（2）写出校正子的编码表 r = 3 共有3个校正子 S1 S2 S3 错码位置 S1 S2 S3 错码位置0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a51 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 无错（3） 由校正子编码表得监督方程组校正子和哪些码元构成偶监督关系若 S1S2S3 = 000 时, 即无错得校验方程:偶监督关系第23页，共57页。2022/7/2124得校验方程:即实际上确定了督元和信元之间的关系:校验方程督信关

12、系有了校正子编码表，督元不是随便选的！（4） 给定了信元a6a5a4a3,可由“督信关系”确定督元全部( 7,4 ) 码组。第24页，共57页。2022/7/2125（4） 给定了信元a6a5a4a3,可确定督元全部( 7,4 ) 码组第25页，共57页。2022/7/2126二. 线性分组码1. 线性方程组和监督方程写成矩阵式:1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0第26页，共57页。2022/7/2127可见：H一旦确定，督元和信元之间的关系也就确定了。若:则称H为典型阵，一般，H总可以化为典型阵。1 1 1 0 1

13、 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0第27页，共57页。2022/7/21282. 生成矩阵矩阵形式:从督信方程入手由第28页，共57页。THANK YOUSUCCESS2022/7/2129可编辑第29页，共57页。2022/7/2130写成行阵形式:其中 Q = PT。上式表明：信息位给定后，就产生了监督位！进一步，令生成矩阵 G = Ik Q 则，码组行阵 A = a6a5a4a3 G 第30页，共57页。2022/7/2131例：生成矩阵讨论：由具有 Ik Q 形式的生成矩阵称为典型生成阵。由典型生成矩阵得出的码组A中，信息位不

14、变，监督位附加其后这种码称为系统码。码组行阵：第31页，共57页。2022/7/2132一般形式: A = an-1an-2ar G 3. G 和 H 的关系由 Q = PT 或 P = QT 则 : H = P Ir G = Ik Q 综上：线性分组码的编码，就是根据其监督阵H或生成阵G将长为k的信息码编成长为n的码组。第32页，共57页。2022/7/21334. 线性分组码的纠错译码过程怎样由含有错误的接收码组中的接收码组中恢复正确。 （1）错误图样设：发码组为A , 接受码组为B 则 B A = E ( 模 2 )错误行阵或错误图样： E= en-1en-2e0 例: A = 1 1

15、1 1 1 1 1 B = 1 0 0 1 1 0 1 则 E = 0 1 1 0 0 1 0 第33页，共57页。2022/7/2134（2）校正子（或称译码伴随式）B = A+E 代入上式，得结论：校正子S仅于错误图案有关，与发送码组无关。第34页，共57页。2022/7/2135由收到的码组B，按式：BHT=SS由 S=ET E按B+E=A A由A 原始信息（3）纠错译码过程 第35页，共57页。2022/7/21365. 线性分组码的重要性（1）封闭性 设： A1、A2 分别为一线性分组码的任意两个许用码组。 则：A1+A2 仍为该线性分组码的许用码组。证：由假设知A1HT=0、A2H

16、T=0 所以A1HT+A2HT=（A1+A2）HT0 即A1+A2也是一个码组。结论：线性码组中任意两个码字之和，仍为该线性码组之码字。（2）线性分组码的最小码距即为该码的最小重量:d0=Wmin（除全0码组）证：由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！第36页，共57页。2022/7/21379.5 循环码 仍属于线性分组码特点: 编译码设备简单，检纠错能力强。9.5.1 循环码的原理具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。第37页，共57页。2022/7/2138码多项式 T

17、(x)（1）定义为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。设：许用循环码A=(an-1 an-2 a1 a0)，则：它的码多项式表示为：其中：x仅是码元位置的标记。第38页，共57页。2022/7/2139例: 设 ( 7,3 ) 循环码组为 ( 0 1 1 1 0 0 1 )则相应码多项式为：反之，由码多项式易得出码组：( 0 1 1 1 0 0 1 )可由码组直接写出。第39页，共57页。2022/7/2140（2）码多项式的按模运算1）整数的按模运算若一个整数m可以表示为:则在模n运算下，有mp（模n）。例：同样对于多项式而言，也有类似按模运算。

18、第40页，共57页。2022/7/2141其中：商Q(x)为多项式，余数R(x)的幂次低于N(x)的幂次。例: 求 x4+x2+1 按模 x3+1 运算的余式 R(x)2）码多项式的按模运算若则第41页，共57页。2022/7/2142 3）循环性在循环码中，若T(x) 是一个长为n的许用码组，则xiT(x) 在按模xn+1运算下，亦是一个许用码组。即设： T(x) 是长为n的许用码组多项式则： T(x)仍为该码组中的一个码多项式。例: （7，3）码T(x) = x6+x5+x2+1 ( 1 1 0 0 1 0 1)前码组循环左移3位！第42页，共57页。2022/7/2143由此类推可见：一

19、个长为n的循环码，必为按模（xn+1）运算的一个余式。第43页，共57页。2022/7/21442. 生成多项式g(x)（1）存在性 ( n，k ) 循环码中有且仅有一个g(x) g(x)=xn-k+1特点: 最高的次数: n-k=r； 最高次项和常数项系数必为1 。 在循环码中，除了全0码组外，再也没有连续k位均为0的码组。即连0长度最多为k-1位！这唯一的n-k次多项式称为生成多项式，记为g(x)！第44页，共57页。2022/7/2145（2） g(x) 与生成矩阵 G(x) 的关系A = an-1ar GG = Ik Q 生成矩阵G的每一行都是一个码组；G是k行n列矩阵，只要找到k个已

20、知码组，就能构成生成矩阵G！生成多项式确定后，则g(x)、x g(x)、 xk-1 g(x)都是码组，且这k个码组信息无关，因此可以用来构成生成矩阵。g(x)确定了G(x)也就确定了整个码组即确定！第45页，共57页。2022/7/2146例: ( 7，3 )循环码， g(x) = x4+x2+x+1 求 典型生成矩阵解:典型阵:可方便地直接写成码组形式第46页，共57页。2022/7/2147（3） g(x) 与 T(x) 的关系（7，3）表明：所有T(x)都可以被g(x)整除，而且任一次数不大于(k-1)的多项式乘以g(x)都是码多项式。第47页，共57页。2022/7/2148依据: g

21、(x)是xn+1的一个(n-k)次的因子，且常数项不为零。证：任一循环多项式T(x)都是g(x)的倍式，即而生成多项式g(x)本身也是一个码组，即有由于码组T(x)为一（n-k）次多项式，故xkT(x)为一n次多项式。由知，xkT(x)在模（xn+1）的运算下，亦为一码组，故可写成（4） 如何寻找g(x)第48页，共57页。2022/7/2149上式左端分子和分母都是n次多项式，故商Q(x)1，因此上式可化成即将T(x)=h(x)g(x)、 T(x)=g(x)代入，并化简，得表明: g(x)应该是xn+1的一个因式！结论: g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。第49页，

22、共57页。2022/7/2150（4） 如何寻找g(x)依据: g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。如 (x7+1) = (x+1)(x3+x2+1)(x3+x+1)n=7（7，4）： x3+x2+1、x3+x+1（7，3）： (x+1)(x3+x2+1) 、(x+1)(x3+x+1)（7，6）： x+1第50页，共57页。2022/7/2151例: （7，3）循环码有多项式如下，找出（7，3）码的生成多项式g(x)。 （1） x4+x3+x （2） x3+x2+1 （3） x+1 （4） x4+x2+x+1 （5） x4+x+1解: 依据 r = 7-3 = 4，常数项不为零，有 （4） x4+x2+x