第6章 编码技术课件

1、第6章 编码技术6.1 概述6.2 常用的差错控制编码6.3 线性分组码6.4 循环码6.5 卷积码6.1 概述6.1.1 信源编码与信道编码6.1.2 差错控制与编码分类6.1.3 差错控制能力与编码效率6.1.4 差错控制方式6.1.1 信源编码与信道编码n信源编码(有效性编码)n去除冗余n降低传输速率n信道编码(可靠性编码)n添加冗余n降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性6.1.2 差错控制与编码分类n差错控制编码n理论依据：香农信道编码定理n基本思想：通过对信息码元序列作某种变换,使原来彼此相互独立,没有关联的信息码元序列,经过这种变换后,产生某种规律性或相关性,使

2、在接收端可根据这种规律性来检查,以至纠正传输序列中的差错n实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系n简单例子对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。香农信道编码定理举例说明：假如要传送A、B两个消息n编码一：编码一：n消息A-“0”；消息B-“1”n若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。n编码二：编码二：n消息A-“00”；消息B-“11”n若传输中产生一位错码，则变成“01”或“

3、10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。n这表明增加一位冗余码元后码具有检出一位错码的能力n编码三：编码三：n消息A-“000”；消息B-“111”n传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。n在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。n这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。n可见n纠错编码之所以具有检错和纠错能力，确实是因为在信息码元外添加了冗余码元（监督码元）n一般说来，添

4、加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。n涉及概念：检错、纠错；许用码组/字、禁用码组/字；错误译码6.1.2 差错控制与编码分类差错分类n随机差错独立差错n差错的出现随机，且差错之间是统计独立的n由随机噪声引起n存在这种差错的信道称为随机信道无记忆信道n突发差错n差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关n因脉冲噪声，也可能是由存储系统中磁带的缺陷或读写头接触不良引起n存在这种差错的信道称为突发信道有记忆信道例n设发送数据序列为：00000000001111111111n接收数据序列为：01101001001111001001n则差错序列为

5、： 01101001000000110110n差错序列：发送数据序列与接收序列对应码位的模和n发生了两个长度分别为和的突发差错，其错误图样分别为1101001和11011n突发长度：指突发差错首位与末位之间的长度（中间可能有没错的码位）n差错序列或错误图样中的“”表示对应码位没错，而“”表示有错n实际信道很复杂，所出现的差错并不是单一的，往往是随机和突发差错并存，只不过以某种错误为主6.1.2 差错控制与编码分类n编码分类n按功能分n按监督码元与信息码元关系分n按监督码元与信息码元约束关系分n按信息码元在码组中的形式分：系统码与非系统码n按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码n

6、按码元的取值分：二进制码与多进制码6.1.3 差错控制能力与编码效率n几个概念n码重：码字中非零码元的数目定义为该码字的重量，简称码重。如“10011”码字的码重为3。n码距：两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（Hamming）距离,简称码距。如两码字“10011”与“11010”间码距为2。n最小码距：在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为d0最小码距与检、纠错能力关系n一个码能检测e个错码，则要求其最小码距d0e+1反之，若码的最小距离为d0，则最多能检测d0-1个错码。n一个码能纠正t个错码，则要求其最小码距d

7、02t+1反之，若码的最小距离为d0，则最多能纠正(d0-1)/2个错码。n一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 d0e+t+1 (et) n假设随机信道中发送“0”码与发送“1”码传错概率相等,为Pe,且Pe(j-i)n能检出全部的奇数个错码：n含有奇数项错码的多项式必不含(x+1)因子，只要选取的g(x)含有(x+1)因子n能检测所有长度不超过(n-k)的突发错误：n突发长度不大于b的突发错误对应的错码多项式为E(x)=xi(eb-1xb-1+ eb-2xb-2+e1x+1)= xi E1(x)n由于g(x)除不尽xi； g(x)为n-k次多项式，只要E1(x)的次数

8、b-1不超过(n-k-1)次， g(x)便除不尽E1(x)。也就是说，能检测长度不超过(n-k)的突发错误。n在突发长度b大于(n-k)的错误中，若b=n-k+1，则(n，k)循环码不能检测概率为2-(n-k-1)；若bn-k+1，则不能检测概率为2-(n-k）。n设错码多项式为E(x)= xi E1(x) ，E1(x)的次数为(b-1)，必有x0 和xb-1项，还应有b-2项xj，因此共有2b-2种不同的多项式。n只有E1(x)有g(x)的因子时，即E1(x)= g(x) Q(x)时，这种错码才不能检测出来。ng(x)为(n-k)次，所以Q(x)定为b-1-(n-k)次；当b-1=n-k（即

9、b=n-k+1），则Q(x)=1，此时仅有一个E1(x)= g(x)的错误图样不可检测，占突发错误图样总数的1/2b-2=2-(n-k-1)BCH码n发现者：Hocguenghem(59)，Bose和 Chaudhuri(60)n特点：能纠正多个随机错误，并有严密的数学结构n循环码中一类重要子码：g(x)与dmin关系密切nBCH码的码长n与监督位、纠错能力t间关系：n对于任一正整数m和t(tn/2)，必定存在一个码长n=2m-1，监督位n-kmt，能纠正所有不大于t个随机错误的BCH码BCH码n分两类：n本原BCH码：g(x)中含有最高次数为m的本原多项式，且码长n= 2m-1n非本原BCH

10、码： g(x)中不含这种本原多项式，且码长n是2m-1的一个因子n本原多项式（次数为m)：不含因式的既约多项式，能除尽 ，但除不尽xr-1，r 2m-1。n例如m=3时， 2m-1=7， nx7-1=（x+1)(x3+x2+1)(x3+x+1)，此时最高次数为3的本原多项式有两个：(x3+x2+1) 和(x3+x+1)，它们都能除得尽x7-1，但除不尽x6-1和x5-112 mxn具有循环性质的汉明码就是纠正单个随机错误的本原BCH码：n汉明码是纠正单个随机错误的码，其码长n= 2m-1，k= 2m-1-mBCH码的构造举例n例1：构造一个纠错能力为3，码长为15的BCH码。n查表9-8得：n

11、=15，k=5，t=3的BCH码，对应码多项式标号为(2467)8=(10100110111)2，g(x)=x10+x8+x5+x4+x2+x+1BCH码的构造举例n例2：试求Golay码（23，12）（非本原BCH码）码的生成多项式。n查表9-9得： （23，12）非本原BCH码对应码多项式标号为(5343)8=(101011100011)2 ，g(x)=x11+x9+x7+x6+x5+x+1扩展BCH码n在BCH码上增加一奇偶校验位，扩展后码距增加1，同时具有检错、纠错能力，但不再是循环码了。RS码n多进制BCH码n具有很强的纠错能力，特别适合于纠正突发错误n纠t个符号错误的(n,k) R

12、S码：n码长n=2m-1 个符号 m(2m-1 ) bitn信息段k个符号 mk bitn监督段n-k=2t个符号 m (n-k ) bitn最小码距dmin=2t+1个符号 m (2t+1) bit6.5 卷积码n几点说明：n又名连环码，是一种非分组码n与分组码相比，在同等码率和相似的纠错能力下，卷积码的实现往往更简单n卷积码主要应用于FEC数据通信系统中n基本原理：n在任何一段规定时间里编码器产生的n个码元，不仅取决于这段时间中的k个信息码元,而且还取决于前m(m= N-1)段规定时间内的信息码元，编码过程中相互关联的码元为Nn个。nm或N段时间内的码元数目Nn称为卷积码的约束长度。n记作

13、(n，k，N)或 (n,k,m)，编码效率R=k/n。 卷积码(2,1,2)编码器 m1m2数据输入码字输出S1S2S3C1C2 起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定 1123213CSSSCSS=排= 表 (2,1,2)编码器的工作过程 卷积码的描述卷积码的描述 1. 树图树图 (2,1,2)码的树图码的树图 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a1100数码

14、起点状态a00b01c10d11上半部下半部数码11012. 状态图状态图 (2,1,2)码的状态图 a00b01c10d11cbad01011111001000103. 格图格图 (2,1,2)码的格图 a00起点aaaaaabbbccccbbcbddddd000000000000000000100101010101010110101010111111111111101010100101卷积码的译码卷积码的译码 1. 维特比译码维特比译码 维特比译码格图维特比译码格图 图79起点d80100(4)cba700(3)6500(3)4300(3)200(2)10 00(1)级11(1)11(3)

15、11(3)11(3)10(2)10(4)00(3)01(3)01(3)10(3)10(3)10(3)01(1)01(1)01(5)00(2)11(2)收码01011010010001解码11010000 2. 序列译码序列译码 当m很大时，可以采用序列译码法。 其过程如下： 译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较， 沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门

16、限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。 n举例说明：D0D1输入mj输出mjPj1Pj2c1c0c2c1c2c2c3c3c3c4c5c4c5图 7-11 n0=3, k0=1,m=2 的卷积编码器图 7-12 卷积子码间的约束关系n编码：n输入信息码位一方面直接输出，另一方面可暂存在移位器中。每当输入编码一个信息位，就立即计算出一监督位，并且此监督位紧跟此信息位之后发送出去。tm1m2m3m4tm1c1m2c2m3c3m4c4n编码器工作过程：移位寄存器按信息位的节拍工作，输入一位

17、信息，电子开关倒换一次，即前半拍（半个输入码元宽）接通m端，后半拍接通c端。n编码公式：c1=0+m1 c2=m1+m2 c3=m2+m3 ci=mi-1+min可见：n卷积码结构为：“信息码元、监督码元、信息码元、监督码元、 ”。n一个信息码元和一个监督码元组成一组，但每组中的监督码元除与本组信息码元有关外，还跟上一组信息码元有关。n译码：c简单 (2,1,2)卷积码译码器1D2D1+信息码输出卷积码输入+D3+Smc32解码器工作过程n解码器输入端的电子开关按节拍把信息码元与监督码元分接到m端与c端；n3个移位寄存器的节拍比码序列节拍低一倍，其中移位寄存器D1，D2在信息码元到达时移位，监

18、督码元到达期间保持原状；而移位寄存器D3在监督码元到达时移位，信息码元到达期间保持原状；3. 移位寄存器D1，D2和模2加法器1构成与发端一样的编码器，它从接收到的信息序列中计算出对应的监督序列来；4. 模2加法器2把计算出的监督序列与接收到的监督序列进行比较：两者相同，输出“0”；两者不同，输出“1”，显然此时，必定出现了差错。5. 如果有差错，则要确定差错位置并纠错n具体判决如下：n根据译码图，有校验子S的方程即解码方程如下：S0=（0+m1)+c1S1=（ m1 +m2)+c2 S2=（ m2 +m3)+c3 Si=（ mi +mi+1)+ci+1 n可见每个信息码元出现在两个S方程中，即mi与Si-1和Si有关，在判决mi是否有错时，应根据Si-1和Si的值。n（正交正交：决定Si-1和Si值的共有5个码元，但其中只有mi与Si-1、Si两值都有关，而其他码元只与一个值有关，这称为方程Si-1与Si正交于mi；或者说校验子方程Si-1与Si构成mi的正交方程组。）n在差错不多于1个条件下，根据正交性得判决规则如下：n当Si-1、S