差错控制编码ppt课件.ppt

《差错控制编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《差错控制编码ppt课件.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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)：当收到少量的错码时，就在接收端直接纠正，当错码太多超过其纠错能力时，则采用差错重发方式。 前向纠错法：接收端不仅能在收到的信码中发现有错码，还

3、能够解定错码的位置，纠正错码。 检错重发(ARQ)：接收端在收到的信码中检测出(发现)错码时，即设法通知发送端重发，直到正确收到为止。发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号 既存在随机错误又存在突发错误的信道称为混合信道。 突发错误突发错误：错码成串出现，在短促的时间区间内错误密集成群，而在这些短促的时间区间之间却又存在较长的无错码区间。以突发错误为的信道称为突发信道。（脉冲干扰、信道中的衰落现象）。 随机错误随机错误:错误的位置是随机,且统计独立高斯白噪声)。以随机错误为主的信道称为随机信道。 2.差错控制编码的类别 按照编

4、码的用途不同，差错控制编码可分为检错码、纠错码、纠删码。 按照监督码元和信息码元的不同关系，差错控制编码可分为线性码和非线性码。 按照对信息码元的处理方式不同，差错控制编码可分为分组码和卷积码。 按照码组中的信息码元在编码前后的位置是否发生变化，差错控制编码分为系统码、非系统码。 按照编码针对的不同干扰类型，差错控制编码可分为纠(检)随机(独立)错误码、纠(检)突发错误码和既能纠(检)随机错误，有纠(检)突发错误码。纠错编码线性码分组码卷积码非线性码非循环码循环码纠随机错误码纠同步错误码纠随机突发错误码纠突发错误码纠错编码分类示意图 3.差错控制编码的基本方法 最小码距最小码距：在码字集合中全

5、体码字之间距离的最小数值用d0 表示表示 。 4 码间距离d及检错纠错能力码长码长:码字中码元的数目；码重码重:码字中非0数字的数目； 码距码距：两个等长码字之间对应位不同的数目，有时也称作这两个码字的汉明距离汉明距离，用d d表示表示。码组11010码长N=5，码重w=3码组11010 和10100，码距d= 3 1010011010=01110 两个码组的模二相加得到的新码组的重量就是这两个码组之间的距离。码组集合000 011 101 110的最小码距d0为 2码距 纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，抗干扰能力就越强。 (1)检测错误时，如果要检测e个错误

6、，则 dmin e+1；(2)纠正错误时，如果要纠正t个错误，则 dmin 2t+1； (3)纠t个错误，同时检e个错误时(et)，则dmint+e+1。eBAd0tAtB1tAeB1(a)(b)(c)d0d05. 编码效率是指码字的信息码元个数k与总的码长n的比值，即：nrnnk7.2 简单控制编码 7.7.2 奇偶监督码奇偶监督码 偶监督码规则:在信息位后加上一位监督位，要求整个码字中“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 11 0 1 0 0

7、 0 1 0 有错有错 奇偶监督码的编码可以用软件实现，也可用硬件电路实现。 如果码组B无错，BA，则M0；如果码组B有单个（或奇数个）错误，则M1。 a4a3a2a1a0a4a3a2a1信息组编码输出b0b4b3b2b1接收码组检错信号SBAM 二维奇偶监督码，它是将若干个信息码字按每个码字一行排列成矩阵形式，然后在每一行和每一列的码元后面附加一位奇（偶）监督码元。 信息码元信息码元 监督码元监督码元 信息码元信息码元 监督码元监督码元 1 0 1 1 0 0 0 1 1 0 1 1 0 0 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

8、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 线性分组码的定义及性质 线性码有一个重要性质，就是它具有封闭性。即线性码中的任意两个码组之各仍为该码中的一个码组。 所谓线性分组码，是指信息位和监督位满足一组信息位和监督位满足一组线性方程线性方程，编码规则用一组线性方程来描述的分组码。 分组码是一组固定长度的码组，可表示为(n,k)，k个信

9、息位被编为n位码组长度，而r=n-k个监督位的作用就是实现检错与纠错。 信息位(n) 监督位(r=n-k)a6 a5 a4 a3 a2 a1 a01 0 1 10 0 1(7,4)线性分组码编码效率=k/n(7,4)线性分组码a0= a6 a4 a3监督关系：a2= a6 a5 a4a1= a6 a5 a3线性分组码的生成矩阵和监督矩阵输入： 1 0 1 1a6 a5 a4 a3 a2 a1 a00011 0 1 1 0 0 11 1 1 1 0 0 1误码不满足监督关系(纠错)a2 a6 a5 a4 = 1a1 a6 a5 a3 = 1a0 a6 a4 a3 = 0=a5错a0= a6 a4

10、 a3a2= a6 a5 a4a1= a6 a5 a3线性分组码的生成矩阵和监督矩阵Taaaaaaa0123456100110101010110010111000简记作 HAT = 0 0T 或 AHT = 0 0监督矩阵H写成矩阵形式接收端 HAT 0 0T 说明有错a0= a6 a4 a3a2= a6 a5 a4a1= a6 a5 a3线性分组码的生成矩阵和监督矩阵a3= a3a4= a4a5= a5a6= a6a6a5a4a3a2a1a0=a6a5a4a31 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1生成矩阵GGGMA345

11、6aaaa可以根据生成矩阵写出编码 1 0 1 1 0 0 11 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1H=P IrG=Ik Q Q = PT 汉明码是一种能够纠正单个错误的线性分组码。它有以下特点： (1)最小码距dmin3，可纠正一位错误； (2)码长n与监督元个数r之间满足关系式：12 rn6.7.3 汉明码汉明码 如果信息长度为5位，要求纠正1位错，需要增加的校验位是( )。 对于(n,k)线性分组码，由于它的监督码元数为r=n-k，只发生一位错误时，监督码元的应能指出所有n个码元位置上出错及全对共(n+1)中情况。2n-kn+1汉明码校验和与错误码

12、元位置对应关系为：S1= a6a5a4a2S2= a5a4a3a1S3= a6a4a3a0 S1S2S3错码位置 S1S2S3错码位置001101 010110 100 111 011000 a0 a1假设某汉明码的监督关系为a2 a3a6a5a4无错rIPH100011101011100011101已知某汉明码监督矩阵：试求 （1）n=?，k=?， （2）验证1111001和0101011是否有错，若有错，请纠正之。 （3）若信息码元为1001，写出其相应的汉明码字 。 ?rIPH100011101011100011101(1)n=7，k=4，7/ 401110011111000111010

13、11100011101a3错误，正确的序列为1110001S=BHT=(A+E)HT= EHTS1= a6a4a3a2S2= a5a4a3a1S3= a6a5a4a0S= 当0101011，a2错误，正确的序列为0100011(3) 1111001(2) 信息码元1001，由监督矩阵H：对应的生成矩阵为1 0 1 1 1 0 00 1 1 1 0 1 01 1 1 0 0 0 1H=P Ir1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0G=Ik Q= Ik PT=A=MG=1001G= 1001011一对码字之间的海明距离是( )

14、A.码字之间不同的位数 B.两个码字之间相同的位数 C.两个码字的校验和之和 D.两个码字的校验和之差 A一个码的最小码距是所有不同码字的码距的( )A平均值 B最大值C最小值 D任意值如果要检查出d位错，那么码的最小码距是( )Ad-1 Bd+1 C2d-1D2d+l如果信息长度为5位，要求纠正1位错，按照海明编码，需要增加的校验位是( )A3 B4C5 D6以太网中使用的校验码标准是( )ACRC-12 BCRC-CCITT CCRC-16 DCRC-32 CBBD 为了进行差错控制，必须对传送数据帧进行校验。在局域网中广泛使用的校验方法是(1)校验。CRC16标准规定的生成多项式为G(x

15、)=X16+X15+X2+l，它产生的校验码是(2)位，接收端发现错误后采取的措施是(3)。如果(9,5)CRC的生成多项式为G(X)=X4+X+1，信息码字为10110，则计算出的CRC校验码是(4)。 (1)A奇偶(Parity) B海明(Hamming) C格雷(Gray) D循环冗余(CyclicRedundancy) (2)A2 B4 C16 D32 (3)A. 自动纠错 B报告上层协议 C自动请求重发 D重新生成原始数据 (4)A0100 B1010 C0111 D1111DCCD7.4 循环码7.4.1 循环码的基本概念及码多项式 所谓循环码，是指任何一个码字循环右移一位后所得到

16、的仍是一个合法码字。属于线性分组码，应用：局域网数据传输。00000000010111100101111001011110010 01011101011100 0111001 循环码特点：编码电路简单，可以很容易的用带有反馈的移位寄存器来实现。码字的多项式描述码字的多项式描述 设码字A=(a0 , a1 , , an-1)，1 0 1 1 1 A= an-1xn-1 + an-2 xn-2+ + a1x+ a0例如：1011 x3+x+1可以用码字多项式: 表示。x4+x2+x+1xk-1g(x)xk-2g(x) xg(x) g(x)G= g(x)生成多项式，循环码的生成矩阵G可以写成x2g(

17、x)xg(x) g(x)1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 G=1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 =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码多项式m(x)=x2+x+1x7-4m(x) =

18、x5+x4+x3用G(x)除m(x)得余式R(x)=x -010消息码组 0111010例计算信息码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 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0

19、 1 0 1 1 1 1 0 1编码为1 1 0 0 1 0 1计算1001的CRC码组g(x)abcd1122输出输入mef生成多项式G(x)= x4+x2+x+1(7，3)循环码编码器循环码的编码电路1 +x +x2 +x47.4.4 循环码的译码原理 检错：将接收码组R(x)用原生成多项式g(x)去除，以余式r(x)是否为零判别码组中有无错码。(1)用生成多项式g(x)除接收码组R(x)，得出r(x)；(2)余式用查表的方法确定错码位置；(3)纠正错码。T(x)0111010-R(x)0111000g(x)=x3+x+1r(x)=010 -a1出错 练习(7,4)循环码组1001101，

20、是否有错？生成多项式g(x)=x3+x+1。7.5 卷积码 概念: 卷积码和分组码有明显的区别。线性分组码无记忆性。卷积码则不同，每个（n,k）码段（也称子码）n个码元不仅与该码段内的信息元有关，而且与前面m段的信息元有关。 有时候也用1/ /3，1/ /2表示卷积码。输入输入外编码器外编码器RS（255，223）交织器交织器内编码器内编码器卷积码（卷积码（n，k，L）信道信道外译码器外译码器RS（255，223）去交织去交织内译码器内译码器卷积码（卷积码（n，k，L）输出输出m010101010m1m20000010110101111 aaccbbddc1c21100001101101001

21、状态1000100011011101 babadcdcm1m2输入输出1b2b3b1C2C a、b、c、d代表寄存器寄存器的四种状态。 起点起点aa01babcdabcdabcd 1、树图 其中a = 00b = 10 c = 01d = 11输出输出0000001111011000111001 输入为 1 1 0 输出为：11 01 01 2、网格图 例1 输入为 1 1 0 1 1 1 0 输出为：11 01 01 00 01 10 01 卷积码图解法： 状态图 树图 格图 （2,1,2）码的状态图 （2,1,2）码的树图 卷积码的译码卷积码译码可分为：代数译码，代数译码是利用生成矩阵和监

22、督矩阵来译码，最主要的方法是大数逻辑译码大数逻辑译码。概率译码。概率译码比较实用的有两种：维维特比译码特比译码和序列译码序列译码。目前，概率译码已成为卷积码最主要的译码方法。维特比译码思路： 把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。GSMGSM系统中的系统中的(2(2，1 1，4)4)卷积编码器卷积编码器IS-95 CDMAIS-95 CDMA系统中的（系统中的（2 2，1 1，8 8）卷积编码器）卷积编码器01234567G1=（753）8=（111101011）G2=（561）8=（101110001）G1=（23）8=（10011）0123G2= （33）8

23、=（11011）GSM移动台原理框图移动台原理框图 交错码又称交织码，是一种能纠正突发错误的码，它是以交错的方法来构造码的。 把纠随机错误的（n，k）线性分组码的m个码字，排成m行的一个码阵，该码阵称为交错码阵。一个交错码阵就是交错码的一个码子。码阵在传输时按列的次序进行，这样可以突发错误变为随机错误加以纠正。输入输入编码器编码器I编码器编码器II交织器交织器开开关关单单元元复复接接单单元元输出输出如何纠正连续多个连续多个错误 (突发突发错误)？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

24、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 d3 d2 d1 d0纵向写入a6b6c6d6a5b5c5d5a4b4c4d4a3b3c3d3a2b2c2d2a0b0c0d0a1b1c1d1a6 b6 c6 d6a5 b5 c5 d5 a0 b0 c0 d0 a1 b1 c1 d1a4 b4 c4 d4a3 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)