《(精品)差错控制编码.ppt》由会员分享，可在线阅读，更多相关《(精品)差错控制编码.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9章 差错控制编码9.1 引言9.2 纠错编码的基本原理9.3 常用的简单编码9.4 线性分组码9.5 循环码9.6 卷积码19.1 引言差错控制编码的基本方法 在发送端被传输的信息序列上附加一些监督码元,这些多余码元与信息码元之间以某种确定的规则相互关联(约束),接收端按照既定的规则检验信息码元与监督码元之间的关系.2常用差错控制方法检错重发前向纠错发收检错码应答信号发收纠错码3混合纠错发收纠检错应答信号常用检错重发系统:停发等候重发,返回重发和选择重发4停发等候重发12331TI23发接收ACKNAK发现错误这是一种半双工的通信方式,原理简单,效率低.5返回重发1 2 3 4 5 6 2
2、 3 4 5 6 7 8 91 2 3 4 5 6 2 3 4 5 6 7 8 9发接收发现错误NAK从码组2开始重发 (传输效率最高,需复杂的控制,收、发数据缓存)选择重发7 8 9 10 11 12重发码组269.2 纠错编码的基本原理分类 按差错控制编码的功能功能：检错码、纠错码、纠删码。按信息码元和附加的监督码元之间的检检验关系：验关系：线性码、非线性码。按信息码元和监督码元之间的约束方式：约束方式：分组码、卷积码。7例：3位二进制数构成的码组表示天气全用用4种 用2种全用用4种 用2种000晴晴晴100雪001云101霜阴010阴110雾雨011雨云111雹雨8如不要检（纠）错，传输
3、4种不同的信息，用两位码组就够了，这两位码代表所传信息，称为信息位，多增加的称为监督位。将信息码分组，为每组信码附加若干监督码的编码，称为分组码。在分组码中，监督码元仅监督本码组的中的信息码元。分组码用（n，k）表示，n码组长度，k 信息位数，n k=r 监督位数。1的数目称为码组的重量，两个码组对应位上数字不同的位数称为码组距离（汉明距离）。各码组间距离的最小值为最小码距 d0 9d0的大小直接关系着编码的检，纠错能力。为检测 e 个错码，要求 d0 e+1为纠正 t 个错码，要求 d0 2 t+1为纠正 t 个错码，同时检测 e 个错码，要求 d0 e+t+1Bd0BA12BA12BB34
4、5d010AB1te若随机信道中，发送“0”和发送“1”时的错误概率相等，为P，且P1,则码长为n 的码组恰好发生r个错码的概率为:11当 n=7 P=10-3时 P(1)710-3 P(2)2.110-5 P(3)3.510-8 可见,采用差错控制编码,即使仅能纠正这种码组中的1 2个错误,也可以使误码率下降几个数量级.129.3 常用的简单编码奇偶监督码 无论信息位有多少,监督位只有一位,使码组中“1”的数目为偶(或奇)数.接收端这种码能够检测奇数个错码,适用检测随机错误13二维奇偶监督码把上述奇偶监督码的若干码组排列成矩阵,每一码组写成一行,然后,再按列的方向增加第二维监督位14恒比码每
5、个码组均含有相同数目的“1”(和“0”).由于“1”的数目与“0”的数目之比保持恒定,故得此名.正反码 是一种简单的能够纠正错码的编码,监督位数目与信息位数目相同,监督位与信息位相同或相反,由信息码中的“1”的个数而定.159.4 线性分组码 线性分组码中信息码元和监督码元是用线性方程联系起来的.线性码建立在代数学群论基础上,线性码各许用码组的集合构成代数学中的群,因此,又称群码.主要性质 任意两许用码组之和(模2和)仍为一许用码组.(封闭性)码的最小距离等于非零码的最小重量16奇偶监督码是一种最简单的线性码,偶校验时S称为校正子,又称伴随式.S=0无错,S=1 有错.一般,由r个监督方程式计
6、算得r个校正子,可以用来指示2r-1种错误,对于一位误码来说,就可以指示2r-1个误码位置.对于(n,k)码,如果满足2r-1n 则可能构造出纠正一位或一位以上错误的线性码.17设分组码(n,k)中k=4,为纠正一位错码,要求r3,则 n=k+r=7S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错18计算监督位判断错码位置按上述方法构造的纠正单个错误的线性分组码称为汉明码。码长 n=2r 1 信息位 k=2r 1 r 监督位r（1）（2）19编码速率=（1）改写为表示成矩阵形式=PIr20简记为 或 H称为监督矩阵，H确定
7、，则编码时监督位和信息位的关系就完全确定了。P为r k 阶 Ir为 r r 阶单位方阵 具有 P Ir 形式的H矩阵称为典型阵。（2）改写为：=21或Q生成矩阵GAG22具有 形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后，这种码称为系统码。23发送码组A在传输过程中可能发生误码，设接收到的码组为B=bn-1 bn-2 b0则 B A=E E=en-1 en-2 e0 错误图样 也可写作 B=A+E24接收端计算校正子为错误图样与校正子之间有确定的关系25例 设 且有3个接收码组验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后
8、再指出发生错码的码字中，哪位有错？26解：1）若无错，则错误图样为0，S为0B1无错B2错B3错2）S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错27线性码的重要性质封闭性 任意许用两个码组之和仍为许用码组两个码组之间的距离必是另一码组的重量,故最小码距即码的最小重量(除全0码外)289.5 循环码9.5.1 循环码原理循环码是一种重要的线性分组码,易于实现,性能较好.循环码除具有线性码的一般性质外,还具有循环性,即循环码中任一码组循环一位以后,仍为该码中的一个码组.一长为n的码组可表示成码多项式29码多项式的按模运算若F(x
9、)=N(x)Q(x)+R(x)则 F(x)R(x)(模 N(x)例 30在循环码中,若 T(x)是一个长为n的许用码组,则xi T(x)在按模xn+1运算下,也是一个许用码组.即 若 则 T(x)也是一个许用码组31在循环码中，一个（n，k）码有2k个不同码组假设用g（x）表示一个前k-1位皆为0（第k位不为0）的码组 则 在循环码中，除全0码外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能k-1位。因此g（x）必须是一个常数项不为“0”的n-k次多项式生成多项式32g(x),xg(x),x2g(x),xk-1g(x)都是码组,且线性无关,故循环码的生成矩阵G可写成假如输入信息码元
10、mk-1 mk-2 m0 则33所有码多项式T(x)都可被g(x)整除,而且,任一次数不大于k-1的多项式乘g(x)都是码多项式.生成多项式g(X)的确定 T(x)=h(x)g(x)又 g(x)为一个码组,故xkg(x)在模xn+1运算下也为一码组,故可写成=134故 g(x)是 xn+1的一个n k次因式,此即寻找 g(x)的方法.例 都可作为(7,3)循环码的生成多项式359.5.2 循环码的编、解码方法编码步骤根据给定的（n,k)选定生成多项式g(x),即从xn+1的因子中选一n-k次多项式作为g(x).所有码多项式T(x)都可被g(x)整除,据此对给定的信息位m(x)进行编码.1.信息
11、码后附加n-k个02.3.36监督位信息位例(7,3)循环码 m(x)=x2+x,g(x)=x4+x2+x+1解 r(x)37a+b+cd+输入m输出feS（7，3）码编码器m a b c d e f0 0 0 0 0 0 01 1 1 1 0 1 11 1 0 0 1 1 10 1 0 1 0 1 00 0 1 0 1 0 00 0 0 1 0 1 10 0 0 0 1 0 00 0 0 0 0 1 1f=mf=e38循环码的解码将接收码组R(x)用g(x)去除,若未发生错误,R(x)能被g(x)整除,发生错误则有余项.399.6 卷积码 在编码器复杂性相同的情况下,卷积码的性能优于分组码.
12、卷积码把k个信息位编n位,k和n通常很小,特别适宜于串行形式传输,延时小.n 个码元与当前段的k个信息位有关,而且与前N-1段的信息有关,编码过程相互关联的码元为Nn个.N或nN称为卷积码的约束长度,常把卷积码记作(n,k,N)40 6 5 4 3 2 1+输入bici输出bici卷积码编码器k=1,n=2,N=641 b6 b5 b4 b3 b2 b1+一级移存+S6 S5 S4 S3 S2 S1+门限电路(2,1,6)卷积码门限译码器输入bici重算ci输出校正子“1”的个数3?42假定b1以前各码元均未发生错误,则(1)43(1)式经线性变换这是一组正交于E(b1)的正交校验方程,在所考
13、察的12个码元(b1b6,c1c6)中错误不多于2个的条件下,仅当E(b1)=1,(2)式才有可能有3个或3个以上方程等于1.门限电路门限设为3,此时,门限电路输出“1”,纠正b1错误,同时送到受E(b1)影响的各级校正子移存器纠正其中错误.(2)44监督矩阵H假定b1进入编码器之前，各级移存器处于“0”状态则 即45 H1用矩阵表示为 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 nn-k46H1：截短监督矩阵自第7
14、行起，每行结构相同，只是每行的起始比上一行多两个“0”。一般，卷积码的截短监督矩阵形式为：47In-k n-k阶单位方阵Pi （n-k）k矩阵0 n-k 阶全零方阵基本监督矩阵 h=PN 0 PN-1 0 PN-2 0 P1 In-k 只要给定h，H1随之确定。48生成矩阵G 基本生成矩阵g g=IK Q1 0 Q2 0 Q3 0 QN 截短生成矩阵Ik k阶单位方阵Qi=PiT k （n-k）矩阵0 k 阶全零方阵49卷积码的图解表示 （3，1，3）卷积码编码器 a 状态m1m2为00，b 状态m1m2为01，c 状态m1m2为10，d 状态m1m2为11。M3 M2 M1+输入序列 mjm
15、jy1，jY2，j50（3，1，3）卷积码的树状图000000111000111001110000111001110011100010101aababcdabcdabcd111001110011100010101000111001110011100010101bcdabcdabcdabcda51（3，1，3）卷积码的网格图abcd00000000000000011111111111111101101101100100100100111011011011001001001010110110110052（3，1，3）卷积码的状态图aabbccda111110101000011100001010abcd11100011010110000101101053在前述编码器中，若起始状态为a，输入序列为11010111，求输出序列和状态变化路径abcd00000000000000011111111111111101101101100100100100111011011011001001001010110110110054对于（n，k，N）卷积码的一般情况，有如下结论：对应于每组k个输入比特，编码后产生n个输出比特。树状图每个节点引出2k条支路。网格图和状态图都有2k(N-1)种可能的状态，每个状态引出2k条支路，同时也有2k条支路从其它状态或本状态引入。55