《差错控制编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《差错控制编码ppt课件.ppt（46页珍藏版）》请在三一办公上搜索。
1、第7章 差错控制编码,7.1差错控制编码的基本原理7.2 简单控制编码7.3 线性分组码和汉明码7.4循环码7.5 卷积码7.6 turbo码,传输ASCII码 01000111 01001100 01011010 I L Y 01000111 01000110 01011010 I H Y,7.1差错控制编码的基本原理,加性噪声、码间串扰都会产生误码。为提高系统抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，合理选择调制、解调方法等。,差错控制编码即是减少加性干扰造成错误判决的措施之一。,差错控制编码：是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原
2、始数字信号变为有规律的数字信号；,采用差错控制编码，即使仅能纠正（或检测）这种码组中12个错误，也可以使误码率下降几个数量级。,一般说来，编码中增加的监督码元越多，检(纠)错的能力就越强。,差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。,1.差错控制的工作方式,反馈校验法：接收端将收到的信码原封不动地转发回发送端，发送端将其与原发送信码比较，如果发现错误，则重发。,混合纠错(HEC)：当收到少量的错码时，就在接收端直接纠正，当错码太多超过其纠错能力时，则采用差错重发方式。,前向纠错法：接收端不仅能在收到的信码中发现有错码，还能够解定错码的位置，纠正错码。,检错重发(A
3、RQ)：接收端在收到的信码中检测出(发现)错码时，即设法通知发送端重发，直到正确收到为止。,既存在随机错误又存在突发错误的信道称为混合信道。,突发错误：错码成串出现，在短促的时间区间内错误密集成群，而在这些短促的时间区间之间却又存在较长的无错码区间。以突发错误为的信道称为突发信道。（脉冲干扰、信道中的衰落现象）。,随机错误:错误的位置是随机,且统计独立高斯白噪声)。以随机错误为主的信道称为随机信道。,2.差错控制编码的类别,按照编码的用途不同，差错控制编码可分为检错码、纠错码、纠删码。,按照监督码元和信息码元的不同关系，差错控制编码可分为线性码和非线性码。,按照对信息码元的处理方式不同，差错控
4、制编码可分为分组码和卷积码。,按照码组中的信息码元在编码前后的位置是否发生变化，差错控制编码分为系统码、非系统码。,按照编码针对的不同干扰类型，差错控制编码可分为纠(检)随机(独立)错误码、纠(检)突发错误码和既能纠(检)随机错误，有纠(检)突发错误码。,纠错编码分类示意图,3.差错控制编码的基本方法,最小码距：在码字集合中全体码字之间距离的最小数值用d0 表示 。,4 码间距离d及检错纠错能力,码长:码字中码元的数目；,码重:码字中非0数字的数目；,码距：两个等长码字之间对应位不同的数目，有时也称作这两个码字的汉明距离，用d表示。,码组11010,码长N=5，码重w=3,码组11010,和1
5、0100，码距d=,3,1010011010=01110 两个码组的模二相加得到的新码组的重量就是这两个码组之间的距离。,码组集合000 011 101 110的最小码距d0为,2,码距,纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，抗干扰能力就越强。,(1)检测错误时，如果要检测e个错误，则 dmin e+1；(2)纠正错误时，如果要纠正t个错误，则 dmin 2t+1； (3)纠t个错误，同时检e个错误时(et)，则dmint+e+1。,5. 编码效率是指码字的信息码元个数k与总的码长n的比值，即：,7.2 简单控制编码,7.7.2 奇偶监督码 偶监督码规则:在信息位后
6、加上一位监督位，要求整个码字中“1”的个数为偶数，例如1 0 1 1 0 0 1 0,1 0 1 0 0 1 1 0 不能确定,如果是奇监督，则要求整个码字中“1”的个数为奇数，例如1 0 1 1 0 0 1 1,1 0 1 0 0 0 1 0 有错,奇偶监督码的编码可以用软件实现，也可用硬件电路实现。 如果码组B无错，BA，则M0；如果码组B有单个（或奇数个）错误，则M1。,二维奇偶监督码，它是将若干个信息码字按每个码字一行排列成矩阵形式，然后在每一行和每一列的码元后面附加一位奇（偶）监督码元。,信息码元 监督码元 信息码元 监督码元 1 0 1 1 0 0 0 1 1 0 1 1 0 0
7、0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1监督码元 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1,7.2.2 二维奇偶监督码,7.3 线性分组码和汉明码,7.3.1 线性分组码的定义及性质,线性码有一个重要性质，就是它具有封闭性。即线性码中的任意两个码组之各仍为该码中的一个码组。,所谓线性分组码，是指信息位和监督位满足一组线性方程，编码规则用一组线性方程来描述
8、的分组码。,分组码是一组固定长度的码组，可表示为(n,k)，k个信息位被编为n位码组长度，而r=n-k个监督位的作用就是实现检错与纠错。,信息位(n),监督位(r=n-k),a6 a5 a4 a3 a2 a1 a0,1 0 1 1,0 0 1,编码效率=k/n,(7,4)线性分组码,a0= a6 a4 a3,监督关系：,a2= a6 a5 a4,a1= a6 a5 a3,线性分组码的生成矩阵和监督矩阵,输入： 1 0 1 1,a6 a5 a4 a3 a2 a1 a0,0,0,1,1 0 1 1 0 0 1,1 1 1 1 0 0 1,a2 a6 a5 a4 = 1,a1 a6 a5 a3 =
9、1,a0 a6 a4 a3 = 0,=,a5错,a0= a6 a4 a3,a2= a6 a5 a4,a1= a6 a5 a3,线性分组码的生成矩阵和监督矩阵,简记作 HAT = 0T 或 AHT = 0,写成矩阵形式,接收端 HAT 0T 说明有错,线性分组码的生成矩阵和监督矩阵,a6a5a4a3a2a1a0=a6a5a4a3,可以根据生成矩阵写出编码,1 0 1 1,0 0 1,G=Ik Q Q = PT,汉明码是一种能够纠正单个错误的线性分组码。它有以下特点： (1)最小码距dmin3，可纠正一位错误； (2)码长n与监督元个数r之间满足关系式：,6.7.3 汉明码,如果信息长度为5位，要
10、求纠正1位错，需要增加的校验位是( )。,对于(n,k)线性分组码，由于它的监督码元数为r=n-k，只发生一位错误时，监督码元的应能指出所有n个码元位置上出错及全对共(n+1)中情况。,2n-k,n+1,汉明码校验和与错误码元位置对应关系为：,S1= a6a5a4a2S2= a5a4a3a1S3= a6a4a3a0,a0,a1,假设某汉明码的监督关系为,a2,a3,已知某汉明码监督矩阵：,试求 （1）n=?，k=?， （2）验证1111001和0101011是否有错，若有错，请纠正之。 （3）若信息码元为1001，写出其相应的汉明码字 。,(1)n=7，k=4，,a3错误，正确的序列为1110
11、001,S=BHT=(A+E)HT= EHT,S1= a6a4a3a2S2= a5a4a3a1S3= a6a5a4a0,S=,当0101011，a2错误，正确的序列为0100011,(3) 1111001,(2) 信息码元1001，由监督矩阵H：,对应的生成矩阵为,G=Ik Q= Ik PT=,A=MG=1001G= 1001011,一对码字之间的海明距离是( ),A.码字之间不同的位数 B.两个码字之间相同的位数 C.两个码字的校验和之和 D.两个码字的校验和之差,A,一个码的最小码距是所有不同码字的码距的( ),A平均值 B最大值C最小值 D任意值,如果要检查出d位错，那么码的最小码距是(
12、 ),Ad-1 Bd+1 C2d-1D2d+l,如果信息长度为5位，要求纠正1位错，按照海明编码，需要增加的校验位是( ),A3 B4C5 D6,以太网中使用的校验码标准是( ),ACRC-12 BCRC-CCITT CCRC-16 DCRC-32,C,B,B,D,为了进行差错控制，必须对传送数据帧进行校验。在局域网中广泛使用的校验方法是(1)校验。CRC16标准规定的生成多项式为G(x)=X16+X15+X2+l，它产生的校验码是(2)位，接收端发现错误后采取的措施是(3)。如果(9,5)CRC的生成多项式为G(X)=X4+X+1，信息码字为10110，则计算出的CRC校验码是(4)。 (1
13、)A奇偶(Parity) B海明(Hamming) C格雷(Gray) D循环冗余(CyclicRedundancy) (2)A2 B4 C16 D32 (3)A. 自动纠错 B报告上层协议 C自动请求重发 D重新生成原始数据 (4)A0100 B1010 C0111 D1111,D,C,C,D,7.4 循环码,7.4.1 循环码的基本概念及码多项式,所谓循环码，是指任何一个码字循环右移一位后所得到的仍是一个合法码字。,属于线性分组码，应用：局域网数据传输。,循环码特点：编码电路简单，可以很容易的用带有反馈的移位寄存器来实现。,码字的多项式描述,设码字A=(a0 , a1 , , an-1)，
14、,1 0 1 1 1 ,A= an-1xn-1 + an-2 xn-2+ + a1x+ a0,例如：1011 x3+x+1,可以用码字多项式:,表示。,x4+x2+x+1,g(x)生成多项式，循环码的生成矩阵G可以写成,G=,例如：g(x)=x4+x2+x+1，则,7.4.2 循环码的生成多项式及生成矩阵,7.4.3 循环码的编码原理,步骤：,1.写出码多项式m(x),2.写出xn-k m(x),3.用(生成多项式)G(x) 除(码多项式)m(x),4.得余式R(x),模2运算,5.写出消息码组:信息码在前、监督码在后。,信息码0111(7,4)循环码组，生成多项式G(x)=x3+x+1,码多
15、项式m(x),=x2+x+1,x7-4m(x),=x5+x4+x3,用G(x)除m(x),得余式R(x),=x,-010,消息码组,0111,010,例计算信息码110的(7，3)循环码组，生成多项式G(x)= x4+x2+x+1 。步骤：码多项式 m(x)= x2+x+0 xn-k m(x)= x4 (x2+x)= x6 +x5用(生成多项式)G(x)除xn-km(x) x4+x2+x+1除x6 +x5(模2运算)得余式R (x)= x2 +1写出消息码组：信息码在前、监督码在后 1 10 0 1 0 1,1 1 1 101111 1 0 0 0 0 0 信息码补n-k个0 1 0 1 1
16、1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1编码为1 1 0 0 1 0 1计算1001的CRC码组,g(x),生成多项式G(x)= x4+x2+x+1,(7，3)循环码编码器,循环码的编码电路,1 +x +x2 +x4,7.4.4 循环码的译码原理,检错：将接收码组R(x)用原生成多项式g(x)去除，以余式r(x)是否为零判别码组中有无错码。(1)用生成多项式g(x)除接收码组R(x)，得出r(x)；(2)余式用查表的方法确定错码位置；(3)纠正错码。,T(x)0111010,-R(x)0111000,g(x)=x3+x+1,r(x)=010
17、,-,a1出错,练习(7,4)循环码组1001101，是否有错？生成多项式g(x)=x3+x+1。,7.5 卷积码,概念: 卷积码和分组码有明显的区别。线性分组码无记忆性。卷积码则不同，每个（n,k）码段（也称子码）n个码元不仅与该码段内的信息元有关，而且与前面m段的信息元有关。 有时候也用1/3，1/2表示卷积码。,a、b、c、d代表寄存器的四种状态。,1、树图,其中a = 00b = 10 c = 01d = 11,输出00,00,00,11,11,01,10,00,11,10,01,输入为 1 1 0 输出为：11 01 01,2、网格图例1 输入为 1 1 0 1 1 1 0 输出为：
18、11 01 01 00 01 10 01,卷积码图解法： 状态图 树图 格图,（2,1,2）码的状态图,（2,1,2）码的树图,卷积码的译码,卷积码译码可分为：代数译码，代数译码是利用生成矩阵和监督矩阵来译码，最主要的方法是大数逻辑译码。概率译码。概率译码比较实用的有两种：维特比译码和序列译码。目前，概率译码已成为卷积码最主要的译码方法。,维特比译码思路： 把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。,GSM系统中的(2，1，4)卷积编码器,IS-95 CDMA系统中的（2，1，8）卷积编码器,GSM移动台原理框图,交错码又称交织码，是一种能纠正突发错误的码，它是以交错
19、的方法来构造码的。 把纠随机错误的（n，k）线性分组码的m个码字，排成m行的一个码阵，该码阵称为交错码阵。一个交错码阵就是交错码的一个码子。码阵在传输时按列的次序进行，这样可以突发错误变为随机错误加以纠正。,7.6 Turbo码,如何纠正连续多个错误 (突发错误)？,a6 a5 a4 a3 a2 a1 a0 b6 b5 b4 b3 b2 b1 b0 c6 c5 c4 c3 c2 c1 c0 d6 d5 d4 d3 d2 d1 d0 ,横向写入,纵向读出,a6 a5 a4 a3 a2 a1 a0b6 b5 b4 b3 b2 b1 b0 c6 c5 c4 c3 c2 c1 c0 d6 d5 d4
20、d3 d2 d1 d0,纵向写入,a6b6c6d6,a5b5c5d5,a4b4c4d4,a3b3c3d3,a2b2c2d2,a0b0c0d0,a1b1c1d1,a6 b6 c6 d6,a5 b5 c5 d5,a0 b0 c0 d0 ,a1 b1 c1 d1,a4 b4 c4 d4,a3 b3 c3 d3,a2 b2 d2 c2,信道传输,横向读出,解码器,交织,解交织,c4 d4 a3,纠错码的发展概况,通信的数学理论，Shannon(1948)汉明码，Hamming (1950)级连码，Forney(1966)卷积码及有效译码, (60年代)RS码及BCH码的有效译码(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，Berrou(1993) LDPC 码，Gallager(1963),Macky(1996)空时编码,Tarokh(2000),
