西工大通信原理（期末复习考研求职必备） 第9章 差错控制编码课件.ppt

2022/12/3,1,通 信 原 理 电 子 教 案第9章 差错控制编码,西 北 工 业 大 学 （2008.3）,2022/12/3,2,研究的问题,9.1 引言9.2 纠错编码的基本原理 9.3 常用的简单编码 9.3 线性分组码 9.4 循环码 9.5 卷积码9.6 网格编码调制,2022/12/3,3,9.1 引言一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。,2022/12/3,4,二、错误的类型随机性错误 （白噪声引起）特点：单个错，错误之间不相关。主要出现在无记忆信道。2. 突发性错误 (脉冲干扰引起）特点：成串错，错误之间有相关性。主要出现在有记忆信道。错误传播。3. 混合性错误,2022/12/3,5,三、差错控制的方式1. 检错重发(ARQ),特点: 1）双向通道 2）通信效率低 3）不适于实时通信 4）编、译码设备简单 5）编码效率高,总码元 (n bit)= 信元 (k bit)+ 督元 (r bit )。,只检不纠，有错自动要求重发。,2022/12/3,6,2. 前向纠错 (FEC),特点： 1）只需单向信道省信道！ 2）通信效率高； 3）适于实时传输； 4) 译码设备复杂。,检错并纠错,2022/12/3,7,3. 反馈检验法,原理：收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错重发；否则：PASS特点: 需要双向通道；收发设备简单；传输效率低（最低）。,2022/12/3,8,9.2 纠错编码的基本原理一. 基本思想,信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，传输效率（引入冗余码）例：天气预报,三位码元有23=8种组合，实际使用了22=4种许用码组。其余 001，010，100，111 为禁用码组。检错能力：可检错奇数个错；纠错能力：无。,2022/12/3,9,例：天气预报，可预报天晴,冗余量加大，禁用码组比例提高。检错能力：检2；纠错能力：纠1。,许用码组2个，禁用码组6个,晴阴,2022/12/3,10,二. 纠错编码的分类线性码和非线性码分组码、卷积码和循环码系统码和非系统码三. 分组码定义:将信息码分组，为每信息码附加若干个监督码编码，称为分组码。特点: 在分组码中，监督码元仅监督本码组中的信息码元。,符号: ( n , k ) , r = n k码字:,结构:,k个信元,r个督元,码长n,2022/12/3,11,码组的重量和码距及纠错能力1. 重量 码组中非0元素的个数 例: A= ( 10110 ) 码重 = 32. 码距 两两码组对应位上数值不同的个数，记为d。最小码距: 某种编码中各个码组间距离 的最小值，记做d0 d0=dmin码距的几何意义: (n=3) 各顶点沿立方体各边行走的几何距离。码元值：每一码组的三个码元值，就是此立方体各顶点的座标（a2a1a0）最小码距: 1,2022/12/3,12,前例中：天气预报,四个许用码组之间的距离均为2。Why?摈弃d=1的码禁用码组。许用码组最小码距愈大，抗干扰能力愈强！确定最小码距的目的：决定编码的检纠错能力。,2022/12/3,13,3. d0与纠检错能力若要求检测e个错,则 d0e+1 若要求纠正t个错,则 d02t+1 若要检测e纠正t 个错(同时),则 d0e+t+1, 且et码距与检错和纠错能力的关系如图：,t 1 t,e,2022/12/3,14,0 1 2 3A,d0,(a),0 1 2 3 4 5A B,t t,d0,(b),A B,t 1 t,e,(c),图9-4,2022/12/3,15,9.3 常用的简单编码属于分组码一类。简单、实用。一. 奇偶监督码满足:,偶监督码：码组中1的个数为偶数；奇监督码：码组中1的个数为奇数。检错能力: 所有奇数个错。一半！应用非常多。编码效率:,2022/12/3,16,二维奇偶监督码进行横、纵向监督例:,横向监督,纵 向 监 督,纠检错能力: 仍可检错奇数个错 还可检错偶数个错 可纠正一些错码 适于检测突发性错误,2022/12/3,17,横比码(等重码)例: 码重为3,1 . 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0,许用码组: C35 = 10禁用码组: 25-10 = 22,检错能力: 可检测所有奇数个码元的错 和部分偶数个码元的错,但 不能检测码组中“1”变为“0” 与“0”变为“1”的错码数目相同的那些偶数错码编码效率:,2022/12/3,18,例： n=10 , 则 k=5, 接受端的检测,三. 正反码编码规则: 信息位(n/2)中有奇数个“1”,则监督位与信息位相同 信息位(n/2)中有偶数个“1”,则监督位是信息位的反码,2022/12/3,19,9.4 线性分组码定义：若分组码（n,k）,督元与信元的关系可用一线性方程组来描述，则该分组码（n,k）称为线性分组码。一、汉明码 能纠一位错的线性分组码。定义：是一种能纠正一位错码，且编码效率较高的线性分组码。最小码距：d0=31. 构造原理考察：定义一个监督方程（监督关系式、偶监督）：,由于一位校正子只有两种取值，故只能表示有错或无错，不能指出错码的位置。,2022/12/3,20,推想:如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有,2022/12/3,21,再推广:,S1 S2 Sr0 0 . 00 0 . 11 1 .1 1,显然：要求 2r-1n（n=k+r），则可指示（仅一位错时）任一错码的位置包括信元、督元。或： 2rk+r+1,可指示一个错码可能出现的2r-1个位置。,2022/12/3,22,2. 例: 构造k=4 的汉明码（1）确定 r由 2r k+r+1 得 r = 3，则 n= k+r=7 ( 7,4 ) 分组码,2022/12/3,23,（2）写出校正子的编码表 r = 3 共有3个校正子,（3） 由校正子编码表得监督方程组校正子和哪些码元构成偶监督关系,若 S1S2S3 = 000 时, 即无错得校验方程:,偶监督关系,2022/12/3,24,得校验方程:,即实际上确定了督元和信元之间的关系:,校验方程,督信关系,有了校正子编码表，督元不是随便选的！,（4） 给定了信元a6a5a4a3,可由“督信关系”确定督元全部( 7,4 ) 码组。,2022/12/3,25,（4） 给定了信元a6a5a4a3,可确定督元全部( 7,4 ) 码组,2022/12/3,26,二. 线性分组码1. 线性方程组和监督方程,写成矩阵式:,2022/12/3,27,可见：H一旦确定，督元和信元之间的关系也就确定了。若:,则称H为典型阵，一般，H总可以化为典型阵。,2022/12/3,28,2. 生成矩阵,矩阵形式:,从督信方程入手由,2022/12/3,29,写成行阵形式:,其中 Q = PT。上式表明：信息位给定后，就产生了监督位！,进一步，令生成矩阵 G = Ik Q 则，码组行阵 A = a6a5a4a3 G,2022/12/3,30,例：生成矩阵,讨论：由具有 Ik Q 形式的生成矩阵称为典型生成阵。由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后这种码称为系统码。,码组行阵：,2022/12/3,31,一般形式: A = an-1an-2ar G,3. G 和 H 的关系由 Q = PT 或 P = QT 则 : H = P Ir G = Ik Q 综上：线性分组码的编码，就是根据其监督阵H或生成阵G将长为k的信息码编成长为n的码组。,2022/12/3,32,4. 线性分组码的纠错译码过程怎样由含有错误的接收码组中的接收码组中恢复正确。 （1）错误图样设：发码组为A , 接受码组为B 则 B A = E ( 模 2 )错误行阵或错误图样： E= en-1en-2e0 ,例: A = 1 1 1 1 1 1 1 B = 1 0 0 1 1 0 1 则 E = 0 1 1 0 0 1 0 ,2022/12/3,33,（2）校正子（或称译码伴随式）,B = A+E 代入上式，得,结论：校正子S仅于错误图案有关，与发送码组无关。,2022/12/3,34,由收到的码组B，按式：BHT=SS由 S=ET E按B+E=A A由A 原始信息,（3）纠错译码过程,2022/12/3,35,5. 线性分组码的重要性（1）封闭性 设： A1、A2 分别为一线性分组码的任意两个许用码组。 则：A1+A2 仍为该线性分组码的许用码组。证：由假设知A1HT=0、A2HT=0 所以A1HT+A2HT=（A1+A2）HT0 即A1+A2也是一个码组。结论：线性码组中任意两个码字之和，仍为该线性码组之码字。（2）线性分组码的最小码距即为该码的最小重量:d0=Wmin（除全0码组）证：由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！,2022/12/3,36,9.5 循环码 仍属于线性分组码特点: 编译码设备简单，检纠错能力强。9.5.1 循环码的原理具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。,2022/12/3,37,码多项式 T(x)（1）定义为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。设：许用循环码A=(an-1 an-2 a1 a0)，则：它的码多项式表示为：,其中：x仅是码元位置的标记。,2022/12/3,38,例: 设 ( 7,3 ) 循环码组为 ( 0 1 1 1 0 0 1 )则相应码多项式为：,反之，由码多项式易得出码组：( 0 1 1 1 0 0 1 ),可由码组直接写出。,2022/12/3,39,（2）码多项式的按模运算1）整数的按模运算若一个整数m可以表示为:,则在模n运算下，有mp（模n）。例：,同样对于多项式而言，也有类似按模运算。,2022/12/3,40,其中：商Q(x)为多项式，余数R(x)的幂次低于N(x)的幂次。例: 求 x4+x2+1 按模 x3+1 运算的余式 R(x),2）码多项式的按模运算若,则,2022/12/3,41,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位！,2022/12/3,42,由此类推,可见：一个长为n的循环码，必为按模（xn+1）运算的一个余式。,2022/12/3,43,2. 生成多项式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)！,2022/12/3,44,（2） g(x) 与生成矩阵 G(x) 的关系,A = an-1ar GG = Ik Q ,生成矩阵G的每一行都是一个码组；G是k行n列矩阵，只要找到k个已知码组，就能构成生成矩阵G！,生成多项式确定后，则g(x)、x g(x)、 xk-1 g(x)都是码组，且这k个码组信息无关，因此可以用来构成生成矩阵。,g(x)确定了G(x)也就确定了整个码组即确定！,2022/12/3,45,例: ( 7，3 )循环码， g(x) = x4+x2+x+1 求 典型生成矩阵,解:,典型阵:,可方便地直接写成码组形式,2022/12/3,46,（3） g(x) 与 T(x) 的关系（7，3）,表明：所有T(x)都可以被g(x)整除，而且任一次数不大于(k-1)的多项式乘以g(x)都是码多项式。,2022/12/3,47,依据: g(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),2022/12/3,48,上式左端分子和分母都是n次多项式，故商Q(x)1，因此上式可化成即,将T(x)=h(x)g(x)、 T(x)=g(x)代入，并化简，得,表明: g(x)应该是xn+1的一个因式！,结论: g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。,2022/12/3,49,（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,2022/12/3,50,例: （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+1 （5） x4+x+1,还须证其是不是xn+1=x7+1的因子?,X7+1 = (x4+x2+x+1)(x3+x+1) + 0X7+1 = (x4+x+1)(x3+1) + (x2+x),故: 仅有 x4+x2+x+1 为生成多项式 g(x)。,2022/12/3,51,9.5.2 循环码的编码方法1. ( n，k ) 循环码的编码步骤 设: 已选好g(x)，给定信息码组m(x):,（1）作xn-km(x)实际上是把信息码后附加上（n-k）个“0”。（2）作,（3）编码输出系统循环码多项式T(x)为：,得到了r(x)。,由于循环码多项式T(x)都可被g(x)整除，也就是：,2022/12/3,52,例: ( 7，3 ) 循环码，选 g(x) = x4+x2+x+1 设 m(x) = x2+x+1 ( 1 1 1 )解:,2.编码的电路,2022/12/3,53,上述三步编码过程，在硬件实现时，可以利用除法电路（曹志刚p344348）来实现。,编码的电路,2022/12/3,54,工作过程：信息输入时，开关合2：输入码一方面输入除法器，另一方面直接输出，在信息位全部进入除法器后开关合1：输出端接到移位寄存器，将移位寄存器中存储的余项依次输出，同时切断反馈线。系统码！,2022/12/3,55,2、译码过程循环码的译码可以分三步进行：（1）由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)；（2）由校正子S(x)确定错误图样E(x)；（3）将错误图样E(x)与B(x)相加，纠正错误。,