很好的汉明码介绍.ppt

第9章差错控制编码,9.1引言9.2纠错编码的基本原理9.3常用的简单编码9.4线性分组码9.5循环码9.6卷积码9.7网格编码调制,返回主目录,9.1引言,设计数字通信系统时，应首先合理选择调制、解调方法及发送功率。若不满足要求，则考虑差错控制。从差错控制角度看，信道可以分为三类：即随机信道、突发信道和混合信道。随机信道在随机信道中、错码的出现是随机的，且错码之间是统计独立的。突发信道错码是成串集中出现的。混合信道存在随机和突发两种错码。,常用的差错控制方法有以下几种：检错重发法接收端在收到的信码中检测出(发现)错码时，即设法通知发送端重发，直到正确收到为止。前向纠错法接收端不仅能发现错码，还能够确定错码的位置，能够纠正它。反馈校验法接收端将收到的信码原封不动地转发回发送端与原信码比较。若发现错误则发端重发。三种差错控制方法可以结合使用。,接收端根据什么来识别有无错码由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码和信码之间有确定的关系，使接收端可以利用这种关系由信道译码器来发现或纠正可能存在的错码。在信息码元序列中加入监督码元就称为差错控制编码，有时也称为纠错编码。差错控制编码原则上是以降低信息传输速率为代价来换取传输可靠性的提高。,ARQ系统组成,ARQ优点：冗余码元少、对信道有自适应能力、成本和复杂性低；ARQ缺点：需要反向信道、重发控制较复杂、干扰大通信效率低、实时性差。,例：3位二进制数字构成的码组，共有8种不同的组合。若将其全部利用来表示天气，则可以表示8种不同的天气。000(晴)，001(多云)，010(阴)，011(雨)，100(雪)，101(霜)，110(雾)，111(雹)。任一码组在传输中若发生一个或多个措码则将变成另一信息码组。这时接收端将无法发现错误。,9.2纠错编码的基本原理,若：,000=晴001=不可用010=不可用011=云100=不可用101=阴110=雨111=不可用,则：虽然只能传送4种不同的天气但是接收消却有可能发现码组中的一个错码。例如，若000(晴)中错了一位，则接收码组将变成100或010或001，这三种码组都是不准许使用的，称为禁用码组，故接收端在收到禁用码组时，就认为发现了错码。,但是这种码不能发现两个措码，因为发生两个错码后产生的是许用码组。上述码只能检测错误，不能纠正错误。例如，当收到的码组为禁用码组100时，无法判断是哪一位码发生了错误因为晴、阴、雨三者错了一位都可以变成100。要想能纠正错误，还要增加多余度。例如，苦规定许用码组只有两个：000(晴)、111(雨)、其余都是禁用码组。这时，接收场能检测两个以下错码，或能纠正一个错码。,分组码的一般概念。为了传输4种不同的信息，用两位二进制码组就够了，它们是：00、01、10、11。代表所传信息的这些两位码，称为信息位。前面使用3位码，多出的一位称为监督位。信息码分组，每组信码附加若干监督码的编码集合，称为分组码。例如,分组码的结构,符号(n，k)表示分组码k信息码元数n码组长度(码长)n-k监督码元数,码重、码距与码的纠检错能力,码重“1”的数量称为码组的重量码距两个码组对应位上数字不同的位数称为码组的距离，简称码距。又称汉明(Hamming)距离。最小码距某种编码中各个码组间距离的最小值称为最小码距(d0)。若记：d0最小码距；e检错位数；t纠错位数；则有：,（1）e+1d0，即码的检错能力e比最小码距d0小1位；（2）2t+1d0，即码的纠错能力t的2倍比最小码距d0小1位；（3）e+t+1d0，即若码同时纠t个错并检出e个错误，则e+t比最小码距d0小1位。以下说明：,（1）e+1d0,（2）2t+1d0,（3）t+e+1d0,差错控制编码的效用,假设:发送“0”的错误概率和发送“1”的错误概率相等，都等于P，且P1，则在码长为n的码组中恰好发生r个错码的概率为,例如，当码长n7时，p=10-3则有P7(1)7p=710-3；P7(2)21p2=2.110-5；,P7(3)35p3=3.510-8。可见，采用差错控制编码，即使仅能纠正(或检测)这种码组中12个错误，也可以使误码率下降几个数量级。这就表明，即使是较简单的差错控制编码也具有较大实际应用价值。,9.3常用的简单编码,1奇偶监督码奇偶监督码包括奇数监督码和偶数监督码。只有一位监督位。在偶监督码中，监督位使码组中“l”的个数为偶数，即满足下式条件在奇监督码中，监督位使码组中“l”的个数为奇数，即满足下式条件,2二维奇偶监督码又称方阵码。每一行是奇偶监督码的一个码组，若干码组再按列排列成矩阵，每列增加一位监督位。,二维奇偶监督码特点：可检测偶数个错误适于检测突发错码。不仅可检错，还可纠一些错。检错能力强。,3恒比码每个码组均含有相同数目的“1”(和“0”)。应用：电传机传输汉字，每个汉字用4位阿拉伯数字表示。每个阿拉伯数字又用5位二进制符号构成的码组表示。每个码组的长度为5位，其中恒有3个1，称为5中取3恒比码。可能编成的不同码组数等于从5中取3组合数30。30种许用码组恰好可用来表示10个阿拉伯数字。,4正反码一种简单的能够纠正错码的编码。其中的监督位数与信息位数相同，监督码元与信息码元相同(是信息码的重复)或者相反(是信息码的反码)。由信息码中“1”的个数而定。解码方法：先将接收码组中信息位和监督值按位模2相加，产生校验码组。最后，观察校验码组中“1”的个数，按表93进行判决及纠正可能发现的错码。,9.4线性分组码,从上节介绍的一些简单编码可以看出，每种编码所依据的原理各不相同，而且是大不相同，其中奇偶监督码的编码原理利用了代数关系式。我们把这类建立在代数学基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。本节将以汉明(Hamming)码为例引入线性分组码的一般原理。,回顾奇偶监督码在接收端解码时，实际上就是在计算若S0，认为无错；若S1，认为有错。上式称为监督关系式，S称为校正子。S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。如果监督位增加一位，则增加一个监督关系式。由于两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同状态。,若用其一种表示无错，则其余3种就可能用来指示一位错码的3种不同位置。同理r个监督关系式能指示一位错码的(2r-1)个可能位置。一般地，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求2r-1n，或者2rr+k+1,举例说明如何构造监督关系式：设(n，k)分组码中r=4。为了纠正一位错码，要求监督拉数r3。若取r=3，则n=k+r=7。校正子与错码位置的对应关系如表94规定(也可以另外规定)。,由表可见，当一错码在a2,a4，a5或a6时校正子S为1；否则S为0即构成如下关系同理,在发送端编码时，信息位a6a5a4a3的值决定于稳入信号，因此它们是随机的。监督值a2a1ao应根据信息位的取值按监督关系来确定即监督位应使上三式中的值为零(表示编成的码组中应无错码)，由此得到方程组,由此解出,给定信息位后，可直接按上式算出监督位，其结果如表95所列。,接收端收到每个码组后，先按监督方程计算出S1、S2、S3，再按表94判断错码情况。例，接收0000011，可得：S1S2S3=011。由表94可知在a3位有错码。(7，4)汉明码：最小码距d0=3纠一个错码或检测两个错码。编码效率k/n=(2r-1-r)(2r-1)=I-rn。当n很大时，则编码效率接近1。,线性分组码的般原理。线性分组码是指信息位和监督位满足一组线性方程的编码。改写为,(模2),简记为或,称为监督矩阵,H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度,典型阵,转置得,称为生成矩阵,生成矩阵G的每一行都是一个码组。例如，（参照前页矩阵G）。利用生成矩阵，码字,再由得，,译码,若发送码组为接收码组为二者之差为其中E称为错误图样。,表示该位接收码元无错；表示该位接收码元有错。,接收端译码时计算当接收码组无错时S等于零有错但不超过检错能力时，S不等于零。在错码超过检错能力时，B变为另一许用码组，仍能成立S等于零。这样的错码是不可检测的。S称为校正子(伴随式)。S只与E有关，而与A无关，意味着S与E有的线性变换关系，能与E一一对应，可指示错码位置。,线性码重要性质之一，是它具有封闭性。若：A1和A2是线性码中的两个许用码组，则：(A1+A2)仍为其中的一个码组。由封闭性，两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量(除全“0”码组外)。线性码又称群码，这是由于线性码的各许用码组构成代数学中的群。,9.5循环码,9.5.1循环码原理：在线性分组码中，有一种重要的码称为循环码。循环码除了具有线性码的一般性质外还具有循环性，即任一码组循环一位(将最右端的码元移至左端，或反之)以后，仍为该码中的一个码组。即若是许用码组，则也是许用码组。,循环码举例(7,3)循环码,码组的多项式表示码多项式。例如A=1100101A(x)=1x6+1x5+0 x4+0 x3+1x2+0 x1+1x0=x6+x5+x2+1码多项式表示具有线性的性质,码多项式的按模运算循环移位对应的码多项式如果规定xn=x0，即规定xn+1=0，则有,这种xn+1=0的规定，实质上是一xn+1为模的运算。对于整数m,若可以表示为则称m=p(模n)，或称m与p是同余的。码多项式也有类似的运算。多项式F(x)被n次多项式N(x)除，得到商式q(x)和一个次数小于n的余式R(x)，即F(x)q(x)N(x)+R(x)则写为F(x)R(x)(模N(x),码多项式系数仍按模2运算，即只取值0和1。例如于是，可以有由此可见为了使xn=1，只需做模xn+1的运算即可。例如：x4+x2+1=x2+x+1模x3+1,由前面的分析可知，若T(x)是码多项式，则在模xn+1的运算条件下，xiT(x)仍然是码多项式。,2循环码的生成矩阵G若能找到k个线性无关的码组,就能构成矩阵G。在循环码中，一个(n，k)码有2k个不同码组，若用g(x)表示其中前(k-1)位皆为0的码组，即g(x)=01xxk位n-k位则g(x)、xg(x)，x2g(x)，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此可以用来构成循环码的生成矩阵G。,例表96的循环码,唯一的一个(n-k)次码多项式代表的码组是0010111，相对应的码多项式为,一旦确定了g(x)，则整个(nk)循环码就被确定了。因此,循环码的生成矩阵G可以写成,这个生成矩阵不是系统码的生成矩阵，可以通过行变换，变换成系统码的生成矩阵。,g(x)x4+x2+x+1将此g(x)代入上式，得到,g(x)的性质：g(x)必须是一个常数项a0=1；次数为(n-k)次；唯一的(n-k)次多项式；我们称这唯一的g(x)为码的生成多项式。g(x)是xn+1的因式（见后面分析）。,说明g(x)是xn+1的因式。因为任码多项式T(x)都是g(x)的倍式，所以有T(x)=h(x)g(x)g(x)本身也是一个码组，其次数为n-k次。把它循环移位k次仍为一个码组。所以xkg(x)是n次多项式，在模xn+1运算下，所以即,因为xkg(x)是n次的，所以Q(x)=1。所以所以即g(x)是xn+1的因式。这样就可以通过对xn+1的因式分解得到g(x).,因为所有码多项式T(x)都可被g(x)整除。所以非系统码编码：T(x)=m(x)g(x)系统码编码：用xn-k乘m(x)，即把m(x)左移n-k位；用xn-k除以g(x)，得余式r(x)；T(x)=xn-km(x)+r(x),9.5.2循环码的编、解码方法,例：信息码110，信息码多项式m(x)=x2+x生成多项式g(x)=x4+x2+x+1即于是，编出码字1100000+101=1100101,硬件实现固定除式的多项式除法,信息码元,校验码元,2循环码的解码方法检错,解码的要求有两个：检错和纠错。码多项式T(x)应能被生成多项式g(x)整除。若接收码组与发送码组相同，即R(x)=T(x)，则接收码组R(x)必定能被g(x)整除；若码组在传输中发生错误，则R(x)除以g(x)时可能有余项，即有R(x)/g(x)=Q(x)+r(x)/g(x),检错电路见图9-7(a),接收码组,2循环码的解码方法纠错,前提：每个可纠正的错误图样必须与伴随式一一对应。步骤：由接收多项式除以生成多项式得到余式r(x)；通过余式r(x)与错误图样的关系得到错误图样e(x)；从接收多项式中减去错误图样村e(x)。电路如下：,图9-7(b),假定接收码组为10*O0101，其中右上角打*号者为错码。此码组进入除法电路后，移位寄存器各级的状态变化过程列于表97(b)。(见演示),9.5.3缩短循环码,通过缩短循环码，可以满足系统设计中，码长、信息位和纠错能力的不同要求。对于(n,k)循环码，使前i(0ik)个信息位为零可得到有2k-i个码组的集合，然后从这些码组中删去这i个零信息位，得到一种新的(r-i，k-i)的线性码，称为缩短循环码。缩短循环码与产生该码的原循环码至少具有相同的纠错能力。缩短循环码的编码和译码可用原循环码使用的电路完成。,例：若要求构造一个能够纠正一位错误的(13，9)码，则可以由(15，11)汉明码选出前面两个信息位均为零的码组。然后在发送时，这两个零信息不发送，即发送的是(13，9)缩短循环码。因校验位数相同，(13，9)码与(15，11)循环码具有相同的纠错能力。,9.5.4BCH码,BCH码是一类纠正多个随机错误的特殊的循环码。特点是可以根据给定的纠错能力，找出生成多项式。BCH码分两类：本原BCH码和非本原BCH码。本原BCH码的码长为n=2m-1(M3)，生成多项式g(x)中含有最高次数为m次的本原多项式；非本原BCH码的码长n是2m-1的一个因子，它的生成多项式中不含有最高次数为m的本原多项式。,对于正整数m(M3)和t(t2)必存在有下列参数的二进制BCH码：码长n=2m-1，监督位数rmt，能纠正所有的小于或等于t个随机错误的BCH码。BCH码生成多项式g(x)=LCMm1(x)，m2(x)，m2t-1(x)式中t可纠正的错误个数；mi(x)最小多项式;LCM()指取括号内所有多项式的最小公倍式.,查表法得到生成多项式，用八进制数表示。例如当n=7,k=4,t=1g=(13)8意指g=(001011)2g(x)=x3+x+1,表98（部分）,R-S码是一类具有很强纠措能力的多进制BCH码。伽罗华域(即有限域)：对于有限个符号，若符号的数目是一素数的幂，可以定义有加法和乘法，则构成符号域为有限域；若它是2m个符号的域则称之为伽罗华域GF(2m).例如，两个符号0、1，定义有模2加法和模2乘法，即0+0=0，0+1=1，1+1=0；00=0，01=1，111，则称之为二元域，也是伽罗华域。,9.5.5里德-索罗门码（R-S码）,从两个符号0和1及一个m次多项式p(x)开始，并引入一个新符号，设p()=0。若适当地选择p(x)就可得到的各次幂，一直到2m-2次幂，都不相同，并且m-1=1。这样一来，构成GF(2m)的所有元素。域中每个非零元素还可以用上面元素的和来表示。例如，m=4和p(x)=x4+x+1，则,得到GF(24)的所有元素，详见表9-10。,R-S码是q进制BCH码的子类。具有如下的参数：码长：n=q-1符号监督位数：r=2t符号纠错位数：t符号生成多项式：每个码元都是q进制的，通常令q=2m，则每个q进制码元都可以表示为m位二进制码元，于是码长mn位，监督位数mr位，信息位数：mn-mr位。,R-S码应用：,由于采用多进制，所以对于多进制调制是自然和方便的编码手段;因为RS码能够纠正t个q位二进制码，即对以纠t个连续的突发性二进制错误,所以适合衰落信道应用;RS码可应用在计算机存储系统中以克服系统的差错。,卷积编码则把k比特信息段编成n比特的码组，但所编的n长码组不仅同当前的k比特信息段有关联，而且还同前面的(N-1)个信息段有关联，人们常称这N为该卷积码的约束长度。一般来说，对于卷积码，k和n是较小的整数,常把卷积码记作(n,k,N)卷积码，它的编码效率为R=k/n。,9.6卷积码,961卷积码的图形描述,(3,1,3)卷积码编码器,编码器的输入和输出,树状图,状态图,状态图,网格图,网格图特点：有2N-1种状态；对于k个输入信息比特，相应出现有2k条支路；码树中的上支路用实线表示，下支路用虚线表示：支路上标注的码元为输出比特；从第N个节点开始，图形开始重复，且完全相同。,例9-1(3,1,3)编码器，起始状态为a，输入序列为1101011，求输出序列和相应状态变化路径。解：由卷积码的网格图，可找出编码时网格图中的编码路径如图913所示，由此即可得到输出序列。为,9.6.2卷积码的解析描述,1生成矩阵卷积码是一种线性码。一个线性码完全由一个监督矩阵H或生成矩阵G所确定。生成矩阵G输入第一个信息比特m1时，y1,1=m1；y21=m1；y31=m1。输入第二个信息比特m2时，y1,2=m2；y22=m2；y32=m1+m2。,输入第j个信息比特mj时，y1j=mj；y2j=mj+mj-2；y3j=mj+mj-1+mj-2上式可写成矩阵形式mj+mj-1+mj-2A=y1jy2jy3j,其中生成矩阵为在过渡时刻m100T1=y11y21y31m1m20T2=y12y22y32其中,输出矩阵与输入矩阵的关系有Y=MG,111001011111001011111001011111001011111001011111001上面矩阵空白处均为0元素。该生成矩阵是半无限矩阵。,2.多项式描述例如：输入序列1101110可表示为m(x)=1+x+x3+x4+x5+连接关系表示为g1(x)=1g2(x)=1+x2g3(x)=1+x+x2编码输出为y1(x)=m(x)g1(x)=1+x+x3+x4+x5+y2(x)=m(x)g2(x)=(1+x+x3+x4+x5+)(1+x2),=1+x+x3+x4+x5+x2+x3+x5+x7+=1+x+x2+x4+x7y3(x)=(1+x+x3+x4+x5+)(1+x+x2)=1+x+x3+x4+x5+x+x2+x4+x5+x6+x2+x3+x5+x6+x7+=1+x5+x7+对应的序列为,y1=11011100；y2=11101001y3=10000101总的输出序列为Y=y11,y21,y31,y12,y22,y32,=111,110,010,100,110,101,000,011,结果与网格图是一样的。,卷积码编码器的一般结构,9.6.3卷积码译码,卷积码的译码方法有两类：一类是大数逻辑译码，又称门限译码：另一类是概率译码。概率译码又分为维特比译码和序列译码两种。门限译码方法是以分组码理论为基础的其译码设备简单，速度快，但其误码性能要比概率译码法差。下面只介绍维特比译码。,9.6.3维特比译码,维特比译码算法，简称VB算法。维特比(viterbi)译码和序列译码都属于概率译码。当卷积码的约束长度不太大时，与序列译码相比，维持比译码器比较简单，计算速度更快。VB算法在前向纠错系统中用得较多，在卫星通信中已被采用作为标准技术。,概率译码的基本想法是：把已接收序列与所有可能的发送序列做比较，选择其中码距最小的一个序列作为发送序列。如果发送L组信息比特，对于(n,k)卷积码来说，可能发送的序列有2kL个，计算机或译码器需存储这些序列并进行比较，以找到码距最小的那个序列。当传信率和信息组数人较大时，使得泽码器难以实现。,VB算法则对上述概率译码(又称最大似然译码)做了简化，使其成为一种实用的译码算法。它并不是在网格图上一次比较所有可能的2kL条路径(序列)，而是接收一段，计算和比较一段，选择一段有最大似然可能的码段。从而达到整个码序列是一个有最大似然值的序列。以下以（2,1,3)卷积码为例说明：,设输入信息数目L=5，所以画有L+N=8个时间单位。编码器从a状态开始工作。该网格图的每一条路径都对应着不同的输入信息序列。由于所有的可能输入信息序列共有2kL=32个.,设输入编码器的信息序列为(11011000)，则由编码器输出的序列y(1101000010,11100)，编码器的状态转移路线为abdcbdca。若收到的序列为R=0101011001011100，对照网格图来说明维特比译码的方法。前3步输入R=010101；根据不同输入信息，编码器的输出序列以及它们与接收序列的距离见下表,前3步对应网格图幸存路径，如下页,对应4条幸存路径的序列分别为：a-a-a-a000000a-a-a-b000011a-b-d-c110101a-a-b-d001101.,到第5步的幸存路径和对应的序列分别为：a-a-b-d-d-c0011011001.a-b-d-c-a-a1101011100a-b-d-c-a-b1101011111a-b-d-c-b-d1101011101,到第8步的幸存路径和对应的序列分别为：a-b-d-c-b-d-c-a-a110101,0001011100对应信息11011000与发送信息相同。对比接收0*101011*001011100纠正了两个错误。,总结与复习第一章绪论通信系统的基本组成模型；模拟与数字通信系统组成；通信系统分类；数字通信系统优点；模拟与数字通信系统的性能指标；离散消息的信息量和平均信息量；例题：例1.4.1，习题2、4、6、7,第二章随机信号分析平稳随机过程的定义、性质；什么是广义平稳随机过程？平稳随机过程的自相关函数与功率谱密度如何定义，有何性质？平稳随机过程通过线性系统后，均值、自相关与方差、功率谱密度有何关系？,什么是高斯噪声？什么是高斯白噪声？什么是窄带高斯噪声？窄带高斯噪声的幅度和相位服从什么分布？窄带高斯噪声的同相分量和正交分量服从什么分布？习题1、2、3、7、8、12,第三章信道信道分类：广义信道与狭义信道、调制信道与编码信道、恒参信道与变参信道；什么是幅频畸变、什么是相频畸变、什么是群延迟？什么是多径，它对信号的传输产生哪些影响（平坦瑞利衰落、频率选择性衰落）？什么是分集，它的作用是什么？有哪写分集方式？有哪几种合并方式？,离散信道信道的信道容量是如何定义的，它的物理意义是什么？连续信道信道的信道容量是如何定义的（山农公式）？习题8、13、14、15第五章数字信号的基带传输基带传输系统组成模型。基带数字信号的