黑大《通信原理》第十一章课件.ppt

《黑大《通信原理》第十一章课件.ppt》由会员分享，可在线阅读，更多相关《黑大《通信原理》第十一章课件.ppt（94页珍藏版）》请在三一办公上搜索。

1、第11章 差错控制编码,11.1 概述11.2 纠错编码的基本原理11.3 纠错编码的性能11.4 简单的实用编码11.5 线性分组码11.6 循环码11.7 卷积码11.8 Turbo码 11. 9 低密度奇偶校验码11.10 网格编码调制,11.1 概述,一、按照加性干扰引起的错码分布规律的不同,信道,随机信道(random channel),突发信道(burst channel),混合信道(mixed channel),错码的出现是随机的，而且错码之间是统计独立的。例由正态分布白噪声引起的错码,错码是成串集中出现的，即在一些短促的时间段内会出现大量错码，而在这些短促的时间段之间存在较长的

2、无错码区间。 成串出现的错码称为突发错码。主要原因：脉冲干扰，【例】电火花 信道中的衰落现象。,既存在随机错码又存在突发错码,二、差错控制技术 (1)检错(error detection)重发(retransmission)： 在发送码元序列进行检错编码，接收端检测有无错码，利用反向信道通知发送端，有错时发送端重发，直到正确接收为止。 (2)前向纠错(Forward Error Correction, FEC): 在发送码元序列进行纠错编码，这时接收端能将错码恢复其正确取值。 不需要反向信道，也没有时延，故实时性好。设备要比检测重发设备复杂。,(3)反馈(feedback)校验(checkou

3、t)： 在发送不用编码，接收端将接收到的码元原封不动地转发回发送端。在发送端将它和原发送码元比较。 若发现有不同，就认为接收端收到的序列中有错码，发送端立即重发。 原理和设备都很简单。但是需要双向信道，传输效率也较低，每个码元都需要占用两次传输时间。 (4)检错删除(deletion)： 它和检错重发的区别在于，在接收端发现错码后，立即将其删除，不要求重发。,在发送端需要在信息码元序列中增加差错控制码元，称为监督(cheek)码元。这些监督码元和信息码元之间有确定的关系，使接收端有可能利用这种关系发现或纠正可能存在的错码。 设编码序列中信息码元数量为k，总码元数量为n，则编码效率(码率）为k/

4、n；冗余度(redundancy)为(n-k)/n三、ARQ系统 采用检错重发法的通信系统通常称为自动要求重发(Automatic Repeat reQuest，ARQ)系统。,11.2 纠错编码的基本原理,许用码组,000、011、101、110,禁用码组,001、010、100、111,一、“分组码”的一般概念 将信息码分组，为每组信码附加若干监督码的编码称为分组码(block code)。 监督码元仅监督本码组中的信息码元。 (n,k)分组码，n称为码组的长度(码长)，k是码组中信息码元的数目，n-k=r为码组中的监督码元数目，或称监督位数目。,把码组中“1”的个数目称为码组的重量，简称

5、码重(cod weight)。 把两个码组中对应位上数字不同的位数称为码组的距离，简称码距,码距又称汉明距离。 把某种编码中各个码组之间距离的最小值称为最小码距(d0)。,3位的编码组,码距就对应于各顶点之间沿立方体各边行走的几何距离。4个准用码组之间的距离均为2。,二、检错和纠错能力： (1)为检测e个错码，要求最小码距：,(2)为纠正t个错码，要求最小码距：,(3)为纠正t个错码，同时检测e个错码要求最小码距：,11.3 纠错编码的性能,1)若接收信噪比保持等于7dB， 在编码前误码率约等于810-4(图中A点)， 在采用纠错编码后，误码率降至约410-5(图中B点)。不用增大发送功率就能

6、降低误码率约一个半数量级。2)若保持误码率在10-5不变， 未采用编码时，约需要信噪比9.5dB(图中C点)。 在采用编码时，约需要信噪比7.5dB(图中D点)。节省功率2dB。通常称这2dB为编码增益。 上面两种情况付出的代价是带宽增大。,若希望提高传输速率RB，势必使信噪比下降，误码率增大。,假设系统原来工作在图中C点，提高速率后由C点升到E点。加用纠错编码后，仍可以将误码率降到原来的水平(D点)。这时付出的代价仍是带宽增大。,11.4 简单的实用编码,11.4.1奇偶监督码 监督位只有1位 1)偶数监督码使码组中“1”的数目为偶数,为信息位;,为监督位;,能够检测奇数个错码。 2)奇数监

7、督码码组中“1”的数目为奇数,11.4.2二维奇偶监督码(方阵码) 把奇偶监督码的若干码组排列成矩阵，每一码组写成一行 再按列的方向增加第二维监督位.,能够检测奇数个错码; 有可能检测偶数个错误。有一些偶数错码不可能检测出(如构成矩形的4个错码就检测不出); 适于检测突发错码。 不仅可用来检错，还可用来纠正一些错码。,11.4.3 恒比码 每个码组均含有相同数目的“1”(和“0”) 主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。 对于信源来的二进随机数字序列，这种码就不适合使用了。11.4.4 正反码 能够纠正错码的编码监督位数目与信息位数目相同. 例码长n10，信息位k=

8、5，监督位r=5. 编码规则为：（1）当信息位有奇数个“1”时，监督位是信息位的重复；（2）当信息位有偶数个“1”时，监督位是信息位的反码。例如，若信息位为11001，则码组为1100111001； 若信息位为10001，则码组为1000101110。,接收端解码的方法为： (1)将接收码组中信息位和监督位按位模2相加，得到一个5位的合成码组； (2)若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组； 若接收码组的信息位中有偶数个“1” ，则取合成码组的反码作为校验码组。,观察校验码组中“1”的个数，按表判决及纠正可能发现的错码。,a)发送码组为1100111001，接收码组中无错码

9、则合成码组应为00000由于接收码组信息位中有奇数个“1”，校验码组就是00000。按表判决，无错码。 b)若接收码组成1000111001，则合成码组为01000由于接收码组中信息位有偶数个“1” ，校验码组取合成码组的反码，即10111。由于其中有4个“1” ，1个“0” ，按表判断信息位中左边第二位为错码。 c)若接收码组成1100101001，则合成码组为10000由于接收码组中信息位有奇数个“1” ，校验码组就是10000。由于其中有4个“0” ，1个“1” ，按表判断监督码中左边第一位为错码。,d)若接收码组成1001111001，则合成码组为01010由于接收码组中信息位有奇数个

10、“1” ，校验码组就是01010。按表判断错码多于1个。 长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。,11.5 线性分组码,在线性码中信息位和监督位是由一些线性代数方程联系着 1.汉明（Hamming）码的构造原理。 汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。 偶数监督码的一位监督位和信息位构成一个代数式 在接收端解码时计算,监督关系式，S称为校正子。 (1)r与n的关系 1)一位S的取值只有这样两种，只能代表有错和无错，不能指出错码的位置。 2)两个校正子的可能值有4种不同信息。若用其一表示无错，则其余3种用来指示一位错码的3种

11、不同位置。,3)r个监督关系式,能指示一位错码的2r - 1个可能位置。,(2)如何具体构造这些监督关系式 设分组码(n,k)中k = 4.为了纠正一位错码。监督位数r3, 若取 r 3，则 n k r 7。规定校正子的值与错码位置的对应关系如下：,1)仅当一错码位置在a2, a4, a5 或a6时，校正子S1=1；否则S1=0,2)仅当一错码位置在a1, a3, a5 或a6时，校正子S2=1；否则S2=0,3)仅当一错码位置在a0, a3, a4 或a6时，校正子S3=1；否则S3=0,(3)发送端编码监督位使S1， S2， S3的值为零（表示编成的码组中应无错码）,(11.5-6),解出

12、监督位,(11.5-7),若接收码组为0000011计算可得校正子,表114可知在a3位有一错码。线性分组码满足封闭性.表11-5中所列的(7,4)汉明码的最小码距d0=3，能纠正一个错码或检测两个错码。汉明码的编码效率,当n很大时，则编码效率接近1。汉明码是一种高效码。,2.线性分组码的一般原理式(11.5-6)改写,模2加法,简记为,其中,将H称为监督矩阵。H的行数就是监督位的数目r。 H是rn矩阵.3.系统线性分组码的编码的方法,具有PIr形式的H称为典型监督矩阵。式(11.5-7)改写成,码的生成矩阵,由生成矩阵产生整个码组,具有IkQ形式的G称为典型生成矩阵。典型生成矩阵得出的码组A

13、为系统码。要求G矩阵的k行是线性无关的。任一码组A都是G的各行的线性组合。可组合出2k种不同的码组A，恰是有k位信息位的全部码组；,4.线性分组码的译码的方法线性分组码(n,k)，发送的码组,接收码组为,发送码组和接收码组之差,传输中产生的错码行矩阵(错误图样),校正子,若S和E之间一一对应，则S将能代表错码的位置。,封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。 两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量（除全“0”码组外）。,11.6 循环码,951循环码原理 是一种线性分组码中。 具有循环性:循环码中任一码组循环一位以后，仍为该码中的一个码组

14、。,码组中各码元当作是一个多项式的系数，即把一长为n的码组表示成,第7码组可以表示为,这种多项式有时称为码多项式。 1.码多项式的按模运算 整数运算中，有模n运算。若一整数m可以表示为,在模n运算下，一整数m等于其被n除得之余数。,若一任意多项式F(x)被一n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x),在(n,k)循环码中，若T(x)是一个许用码组，,设,还是一个许用码组。,的码组向左循环移位i次的结果。,表11-5中第7码组。,对应的码组为0101110，正是第3码组。 2循环码的生成矩阵G 在(n,k)循环码中，用g(x)表示其中前k - 1位皆为 “0”的码组.g

15、(x)唯一的次数为(n k)次,必须是一个常数项不为“0”多项式.称这唯一的(n k)次多项式g(x)为码的生成多项式。 一旦确定了g(x) ，则整个(n,k)循环码就被确定了。 g(x) ，x g(x) ， x2 g(x) ， xk-1 g(x)是k个线性无关的码组.,循环码的生成矩阵G,例表 11- 5所给出的循环码中,对应的生成多项式为,此生成矩阵不是典型的。,此循环码组,所有码多项式T(x) 都可被g(x)整除， 任一次数不大于(k-1) 的多项式乘g(x)都是码多项式。3如何寻找任一(n,k)循环码的生成多项式 任一循环码多项式T(x) 为,g(x)也是一个码组，,为(n k)次多项

16、式。,为n 次多项式。,T(x)一定是一个码组,g(x)是( xn + 1 )的一个因式。g(x)是( xn + 1 )的一个(n k)次因式。例 ( x7 + 1 )可以分解为,为了求(7,3)循环码的生成多项式g (x) ，要找到一个(n k) =4次的因子。,选用的生成多项式不同，产生出的循环码码组也不同。表115生成多项式为,9.5.2 循环码的编、解码方法 1. 系统循环码的编码方法(n,k)循环码的信息码多项式为m(x), m(x)次数小于k. 编码步骤：(1)用xn-k乘m(x)。(2)用g (x)除xn-km(x) ，得到商Q (x)和余式r (x) ，,(3)编出的码组T(x

17、)为,例 (7,3)循环码,信息码为110，生成多项式为,求相应的码组。,2循环码的解码方法 (1) 检错解码原理在接收端可以将接收码组R(x),a)若余式,传输中未发生错误，发送码组为,b)若余式,传输中发生错误，发送码组为,(2)纠错解码原理接收码组,余式相同。每个可纠正的错误图样必须与一个特定余式有一一对应关系。从上述余式唯一地决定错误图样，从而纠正错码。,纠错步骤:(l)用g(x)除接收码组R (x)=T (x)+E (x) ，得出余式r (x)；(2)按余式r (x) ，用查表的方法或通过某种计算得到错误图样E (x) ;(3)原发送码组T (x) = R (x) + E (x) .

18、这种解码方法称为捕错解码法。 还有大数逻辑解码等算法。 11.6.3截短循环码 在设计纠错编码方案时，信息位数k、码长n和纠错能力都是预先给定的。并不一定有恰好满足这些条件的循环码存在。 设(n,k)循环码，它共有2k种码组，现使其前i(0ik)个信息位全为“0”，然后从中删去这i位全“0”的信息位，于是它变成仅有2k-i种码组。最终得到一个(n-i,k-i)的线性码。将这种码称为截短循环码(truncated cyclic code)。,截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。 例原(15,11)循环码能够纠正1位错码，从211种码组

19、中选出前两信息位均为“0”的码组，构成一个新(13,9)截短循环码。 此(13,9)截短循环码，也能够纠正1位错码。 11.6.4 BCH码 BCH码能够纠正多个错码的循环码， 它是以3位发明这种码的人名(Bose，Chaudhuri，Hocguenghem)命名的。,BCH码,本原BCH码,非本原BCH码,g(x)中含有最高次数为m的本原多项式，且码长为n=2m-1，(m3，为正整数),g(x)中不含有这种本原多项式，且码长为n是2m-1的一个因子,P348,生成多项式系数是八进制数字,P349,BCH码的码长n与监督位、纠错个数 t之间的关系：对于正整数m(m3)和正整数t1，且除得尽(2

20、m-1)，则为非本原BCH码。,生成多项式系数是八进制数字,1)具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。 2)在表11-7中的(23,12)码称为戈莱(Golay)码。它能纠正三个随机错码，并且容易解码，实际应用较多。 3)BCH码的长度都为奇数。为了得到偶数长度的码，并增大检错能力，可以在BCH码生成多项式中乘上一个因式(x+1)，从而得到扩展BCH码(n+1,k)。 扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展 BCH码已经不再具有循环性。 例扩展戈莱码(24,12)，其最小码距为8，码率为1/2，能够纠正3个错码和检测4个错码。,1

21、1.6.5 RS码 是用其发明人的名字Reed和Solomon命名的。 是一类具有很强纠错能力的多进制BCH码。 若码长为n的m进制RS码，有,对于能够纠正t个错误的RS码，其监督码元数目为,这时的最小码距,RS码的生成多项式为,是伽罗华域GF(2q)中的本原元,码长,监督码,能够纠正码组中t个不超过q位连续的二进制错码，RS码适用于存在突发错误的信道,11.7 卷积码,卷积码(convolutional code)是一种非分组码。 把k比特的信息段编成n个比特的码组，监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N-1)个信息段有关。 所以一个码组中的监督码元监督着N个信息段。 将

22、N称为编码约束(constraint)度， 并将nN称为编码约束长度。 将卷积码记作(n,k,N)。码率为k/n。,11.7.1 卷积码的基本原理,(3,1,3)卷积码的编码器，其码率等1/3。,设输入信息比特序列是,则当输入bi时，此编码器输出cidiei,bi为当前输入信息位；bi-1和bi-2为移存器存储的前两信息位,是一种线性码,P350,在输出中信息位在前，监督位在后，是系统码。编码约束长度nN=9。,11.7.2卷积码的代数表达 1.监督矩阵H 在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态，则监督位di、ei和信息位bi之间的关系,图11-9,(11.7-2),图1

23、1-9,图11-9,监督矩阵为,监督矩阵H是一个有头无尾的半无穷矩阵,图11-9,n=3,k=1,N=3,截短监督矩阵,(11.7-6),n=3,k=1,N=3,图11-9,为(n-k)=2阶单位方阵,为(n-k)k=21阶矩阵,为(n-k)=2阶全零方阵,(n,k,N)卷积码的截短监督矩阵具的形式：,H1的末行称为基本监督矩阵,只要给定了h，则H1也就随之决定了,2.生成矩阵G,(11.7-2),图11-9,此码的生成矩阵,它也是一个半无穷矩阵,截短生成矩阵,为k=1阶单位方阵,为k(n-k)=12阶矩阵,P,P值,一般截短生成矩阵,G1中第一行称为基本生成矩阵,这就是卷积码的代数表述,11

24、.7.3 卷积码的解码,代数解码,概率解码(最大似然解码),大数逻辑解码(门限解码),维特比(Viterb)算法,1.大数逻辑解码 这里的错码检测是采用二进制码的大数逻辑解码算法。 它利用一组正交校验方程进行计算。 “正交”定义是： 若被校验的那个信息位出现在校验方程组的每一个方程中，而其他的信息位至多在一个方程中出现，则称这组方程为正交校验方程。,例(2,1,6)卷积码编码器。当输入序列为,监督位为,监督关系式,Si(i=16)称为校正子,正交校验方程组,只有信息位b1出现在每个方程中，监督位和其他信息位均最多只出现一次。,在接收端解码时，考察b1c1至b6c6等12个码元， 仅当b1出错时

25、，校验方程组中才可能有 3个或 3个以上方程等于“ 1”。从而能够纠正b1的错误。,1)当信息位出现一个错码时，仅当它位于信息位移存器的第6、3、2和1级时，才使校正子等于“1”。这时的校正子序列为100111； 2)当监督位出现一个错码时，校正子序列将为100000。 由此可见，当校正子序列中出现第一个“1”时，表示已经检出一个错码。后面的几位校正子则指出是信息位错了，还是监督位错了。 此卷积码除了能够纠正两位在约束长度中的随机错误外，还能纠正部分多于两位的错误。,2.卷积码的几何表述 1)码树图(code tree diagram) (3,1,3)卷码 a)编码 初始状态000作为码树的起

26、点。 输入信息位为“0”，则状态向上支路移动； 输入信息位为“1”，则状态向下支路移动。 b)解码 按照汉明距离最小的准则沿上面的码树进行搜索。例如，若接收码元序列为 111 010 010 110 码树搜索解码法并不实用，因为随着信息序列的增长，码树分支数目按指数规律增长； 在上面的码树图中，只有四个信息位，分支已有24=16个。,表,接收码元序列为,111,010,010,110,2)状态图(state diagram),(3,1,3)卷码,虚线表示输入信息位为“1”时状态转变的路线；实线表示输入信息位为“0”时状态转变的路线。线条旁的3位数字是编码输出比特。,3)网格图(trellis

27、diagram) 将状态图在时间上展开,(3,1,3)卷码,设发送信息位为1 1 0 1 ，为了使编码器中移存器的信息位全部移出，在信息位后面加入三个“0，故编码后的发送序列为,000,111,110,010,100,001,011,3.维特比解码算法 将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送信号序列。若发送一个k位序列，则有2k种可能的发送序列。存储量太大，使实用受到限制。维特比算法对此作了简化。 (3,1,3)卷积码假设接收序列为111 010 010 110 001 011 000 由于这是一个(n,k,N)=(3,1,3)卷积码，发送序列

28、的约束度N=3，所以首先需考察nN=9比第一步考察接收序列前9位“111 010 010”。由此码的网格图每种状态只有两条路径可以到达。有8条路径。现在比较网格图中的这8条路径和接收序列之间的汉明距离。 现在将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，则可以任意保存一条。这样就剩下4条路径了,第一步考察接收序列前9位“111 010 010”,第二步将继续考察接收序列中的后继3位“110”。计算 4条幸存路径上增加一级后的8条可能路径的汉明距离。,第三步将继续考察接收序列中的后继3位“001”。计算 4条幸存路径上增加一级后的8条可能路径的汉明距离。,第四步将继续考察接收序列中的后继3位“011”。计算 4条幸存路径上增加一级后的8条可能路径的汉明距离。,第五步将继续考察接收序列中的后继3位“000”。计算 4条幸存路径上增加一级后的8条可能路径的汉明距离。,最小的总距离等于2，其路径是abdcbcaa相应序列为111 110 010 100 001 011 000它和发送序列相同，故对应发送信息位 1101,11.8 Turbo码,11. 9 低密度奇偶校验码,11.10 网格编码调制,