通信原理差错控制编码-课件.ppt

本章内容,第11章 差错控制编码,基本概念 差控方式 编码原理 码距 码率 性能简单实用码 奇偶监督 恒比码 线性分组码 汉明码 监督矩阵H、生成矩阵G 循环码 生成多项式 编译方法 BCH码 RS码卷积码 编译原理 代数表述 几何表述,11.1,概 述,开销。这就好像我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000个玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。,为保证运送途中不出现打碎灯泡的情况,有效性,可靠性,通信中的情况：,开销。这就好像我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000个玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。,针对乘性干扰,针对加性干扰,合理选择调制/解调方法，增大发射功率,采用均衡等措施,差错控制编码,信道类型 根据错码的不同分布规律分为：,差错控制方式：,差错控制方式,（ARQ）,（FEC）,自动请求重发,缺点：工作在半双工状态，传输效率较低。,3 种自动要求重发(ARQ)系统,（1）停止等待ARQ系统,系统需要双工信道。,（2）拉后ARQ系统,第5组,传输速率比第（1）种高。,（3）选择重发ARQ系统,ARQ的主要缺点：,码率较高。用较少的监督码元就能使误码率降到很低；检错的计算复杂度较低；检错用的编码方法 和 加性干扰的统计特性基本无关，能适应不同特性的信道。,需双向信道来重发，不适用单向信道和一点到多点的通信系统。重发使得ARQ系统的传输效率降低。信道干扰严重时，将发生因反复重发而造成事实上的通信中断。不适用于要求实时通信的场合，例如电话通信。,ARQ的主要优点：与前向纠错（FEC）方法相比,ARQ系统的原理方框图,11.2,纠错编码的基本原理,规则：使码组中“1”的个数为偶数,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,冗余,另外4个码组,许用码组,禁用码组,也不能 纠正 错误。,（奇数个错码）,这时，能够发现 2个以下错码，或者纠正 1位 错码。,综上所述：,-信息码元位数,-编码后码字位数,不同的编码方法，检错 或 纠错 能力也不同。,分组码和系统码,编码后的每组长度为 n=k+r,就是分组码,前面的例子：,信息位与监督位关系：,分组码 的 符号：,分组码 的 结构：,（n，k）,码长(n)：码组（码字）中的码元个数。,码重(W)：码组中“1”的数目。,“0 1 1 0 1 1”的距离为 3,码重和码距,码重为 3,对于3位的编码组，可用3维空间来说明,（4个许用码组之间）,各顶点之间沿立方体各边行走的几何距离 码距=2,码距的几何意义：,对于（n，k）分组码，有以下结论：,最小码距d0 和检纠错能力的关系,检个错码，要求：,纠个错码，要求：,纠 t 个错码,同时检 e 个错码，要求：,证明：,11.3,纠错编码的性能,系统带宽和信噪比的矛盾,右图所示的某种编码性能,可见：不增大发送功率,就能 降低误码率约一个半数量级。,A点,B点,2PSK调制,可见：能节省功率 2 dB 称为编码增益,D点,2PSK调制,C点,因此，纠错码主要应用于功率受限而带宽不太受限的信道中。,付出的代价是带宽增大。,设编码前 系统工作在图中C点，提高速率后Pe由C点升到E点。,传输速率RB 和 信噪比Eb/n0的关系,若希望提高RB，则必使Eb/n0下降，误码率Pe增大。,这时付出的代价仍是带宽增大。,但采用纠错编码后，Pe仍可降到 D点。,11.4,简单的实用编码,11.4.1 奇偶监督码,偶监督码,奇监督码,适用：检测随机出现的零星差错。,编码规则：,只一位监督码元,（不知错码位置）,很高（只有一位监督位）。,码率：,编出的码字应为：,若收到 10011，检测结果为：,根据偶数监督规则：,-有错,若收到 00011，检测结果为：,奇偶监督码 不能 检出 偶数 个错,解,-认为无错,1 1 0 1 1,11.4.2 二维奇偶监督码,编码规则：,（方阵码）,检测方法：计算接收码组中“1”的数目，可知是否有错。,11.4.3 恒比码,适用：用于电报传输系统或其他键盘设备产生的字母和符号。,编码规则：,(等重码),个许用码组，可分别用来代表26个英文字母 及 其他符号。,11.4.4 正反码,编码规则：,设码长n=10，即信息位 k=5，监督位 r=5。,监督位数与信息位数相同；能纠错。编码效率低：50%。,译码方法：,=00000,校验码组和错码的关系：,无错,信息位中有奇数个“1”，校验码组=00000,发送码组为11001 11001,纠检能力：,（n,k）线性分组码,11.5,线性码：按照一组线性方程构成的代数码。即每个码字的监督码元是信息码元的线性组合。,基本概念,代数码：建立在代数学基础上的编码。,正反码，效率50%，太低。纠正1位错，最少增加多少监督位？,构造出以最小多余度代价换取最大抗干扰能力的好码,纠错编码任务：,汉明码：能纠正1位错，编码效率较高,-监督关系式,若 S=0，认为无错（偶监督时）；若 S=1，认为有错。,若要构造具有纠错能力的（n，k）码，则需增加督码元的数目。,当“=”成立时，构造的线性分组码 称为汉明码,校正子,构造原理,只有一位监督元,-检错,汉明码的,能纠1位错码 的高效 线性分组码,(7,4)汉明码,可以其他假设,由表可见:,仅当一位错码的位置在a2、a4、a5 或a6 时，校正子S1为1；否则S1为 0。,同理：,(A),移项运算解出监督位,(A),接收端译码检错纠错过程,以上构造的线性分组码，称为汉明码。,最小码距：,当 n很大 r 很小时，Rc 1。,编码效率：,汉明码特点:,d0=3（纠1或检2）,r 是不小于3的任意正整数,答：最小码距:,故能 纠1 或检2,d0=3,线性分组码的一般原理,将前面(7,4)汉明码的监督方程：,改写为：,表示成如下矩阵形式：,H-监督矩阵,简记为,H,A=a6 a5 a4 a3 a2 a1 a0,0=000,监督矩阵,或,转置,转置,“T”,r n,=P Ir,r k 阶矩阵,r r 阶方阵,典型监督矩阵,H 矩阵的性质,H 的行数 等于监督位的数目r。,H 的每行中“1”的位置表示相应码元之间存在的监督关系。,H的各行应该是线性无关的，否则得不到r个线性无关的监督关系式。,若一矩阵能写成典型阵形式 P Ir，则其各行一定是线性无关的。,将上面汉明码例子中的监督位公式：,改写成矩阵形式：,G-生成矩阵,或者写成：,P 阵,式中，Q 为一个k r 阶矩阵，它为P 的转置，即:,Q=PT,P 阵,Q 阵,将Q的左边加上1个k k 阶单位方阵，就构成矩阵:,生成矩阵，,或者,因此，若找到了码的G，则编码的方法就完全确定了。,具有IkQ形式的称为典型生成矩阵。,由典型G得到的码称为系统码。,称为,典型生成矩阵,信息位不变，监督位在后。,由它可以产生整个码组，即有:,k n,G 矩阵的性质,G 矩阵的各行是线性无关的。,由式,可看出:,任一码组A都是G的各行的线性组合。,G共有k行，若它们线性无关，则可以组合出2k 种不同的码组A。,它恰是有k位信息位 的全部码组。,G 和H 的关系,校正子与错误图样,设发送码组为一个n列的行矩阵 A，,接收码组的行矩阵 B,错码矩阵（错误图样）,(模2),A=B+E,在接收端，若能求出错误图样E 就能恢复出发送码组 A，即,任一发送码组 A 都应满足式：,对于接收码组 B，可通过计算:,来进行检测。,将 B=A+E 代入上式，可得,0,因此，可根据S 是否为0 判断 接收码组 是否 出错!,由以上分析可知，（n,k)线性分组码译码的三个步骤：,2)由S 找到错误图样E；,3)由公式 A=B+E 得到译码器译出的码组。,（n,k)线性分组码译码的三个步骤：,封闭性,A1和A2,(A1+A2),证明：若A1和A2是两个码组，则有,A1 HT=0 和 A2 HT=0，,将两式相加，有,A1 HT+A2 HT=(A1+A2)HT=0,最小距离,（证毕）,线性分组码的性质,根据性质 线性分组码计算最小码距，只需找最小码重，无需两两码组比较,完备性：汉明码中，伴随式的非零形式与错误图样一一对应，且伴随式的图样除全0外为 个，正好等于码长，最充分利用了监督位所提供的信息。,循 环 码,西安电子科技大学 通信工程学院,课件制作：曹丽娜,它除了具有线性分组码的一般性质外，还具有循环性。,11.6,表中的第 2 码组向 右移一位即得到第 5 码组；,(7,3)循环码,11.6.1 循环码原理,表中的第 6 码组向 右移一位即得到第 3码组。,码字（）的多项式可表示为：,码多项式,多项式的系数就是码组中的各码元，x 仅是码元位置标记。,n=7 时,码字（码组）的多项式表示,1.码多项式的按模运算,一般说来，若一个整数m 可以表示为,（Q 为整数）,m p(模n),则在模n 运算下，有,码多项式的按模运算：,或,则,码多项式系数之间的加法和乘法：按模2 运算。,解 运算过程：,即有,则有,余式,因为，A(x)是 A(x)代表的码组向左循环移位 i 次的结果。,循环码的码多项式,则 余式A(x)也是该编码中的一个许用码组。,循环码组,，码长n=7。,i=3时，有,左移 i 位,3,由上述分析可见:,2.循环码的生成矩阵G,生成矩阵G可由k 个线性无关的码组构成。,引思：,如何寻找这 k 个线性无关的码组？,因此，用这个线性无关的码组可构成该循环码的生成矩阵G，即,生成多项式,g(x)是xn+1的因式,g(x)的性质：,g(x)必有一常数项a01,g(x)的次数为n-k次，且唯一,否则，循环右移1位出现k连0,线性分组码不可能信息位全0，监督位不全为0,若2个，由封闭性得两者和为码组，连0个数至少多出2位：a0、an-k 线性分组码不可能,后面说明,r=n-k=7-3=4，,解,码组中唯一一个4次码多项式代表的,或,此循环码多项式A(x):,(n-k)+(k-1)=n-1,任一循环码多项式 A(x)都是 g(x)的倍式，可以写成,而生成多项式 g(x)本身也是一个码组，即有,A(x)=g(x),A(x)=h(x)g(x),码组 A(x)是一个(n k)次多项式，故 xkA(x)是一个n次多项式。,xk A(x)在模(xn+1)运算下也是一个码组,，故可写成,左端分子和分母都是n次多项式，故Q(x)=1：,将 和 代入上式，化简后得到,A(x)=g(x),A(x)=h(x)g(x),求(7,3)循环码的生成多项式 g(x)。,将(x7+1)进行因式分解：,解：,n k,即有,或,11.6.2 循环码的编解码方法,1.循环码的编码,设 信息码(an-1 an-2 an-k)的多项式为：,m(x)=an-1xk-1+an-2 xk-2+an-k,其最高次数为k-1,则 循环码的多项式为：,A(x)=,A(x)=m(x)g(x),即,（1）xn-k 乘 m(x)，得 xn-k m(x),（2）xn-k m(x)除以g(x)：,将信元左移（n k）位，附上（n k）个0，预留给监督码元。,得到余式 r(x)，作为监督码元,即得循环码的码多项式。,系统循环码的编码步骤：,（3）作 A(x)=xn-k m(x)+r(x),通常是 非系统码,（n k）+（k-1）,（n 1）-（k-1）=r,（n 1）,最高次数,2.循环码的解码,目的：检错 和 纠错。,若能除尽，则无错；若除不尽而有余项，则表示在传输中发生错误。,11.6.3 截短循环码,例：构造一个能够纠正1位错码的(13,9)码。可由(15,11)循环码的码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。在发送时不发送这两位“0”。于是发送码组成为(13,9)截短循环码。,截短目的：在设计纠错编码方案时，若找不到合适的码长n及信息位k 时，可以把循环码的码长截短以得到符合要求的编码。,截短方法：设给定一个(n,k)循环码，它共有 2k 种码组，现使其前 i(0 i k)个信息位全为“0”，于是它变成仅有 2k-i 种码组。然后从中删去这 i 位全“0”的信息位，最终得到一个(n i,k i)的线性码截短循环码。,截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。,11.6.4 BCH码,解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。,BCH码的重要性:,BCH码的分类：,多个,汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。,BCH码的性能：,码长n 与监督位、纠错个数 t 之间的关系：对于正整数m(m 3)和正整数t 1，且除得尽(2m-1)），则为非本原BCH码。,BCH码的设计：,在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。,教材348/353页的表11-7 给出了码长n 127的二进制本原BCH码生成多项式。,n=(2m-1),n=(2m-1),BCH码的长度都为奇数。为得到偶数长度的码，并增大检错能力，在BCH码生成多项式中乘因式(x+1)，得扩展BCH码(n+1,k)。扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展BCH码已经不再具有循环性。例如，广泛实用的扩展戈莱码(24,12)，其最小码距为8，码率为1/2，能够纠3个错码和检4个错码。它比汉明码的纠错能力强很多。代价：解码更复杂，码率也比汉明码低。不再是循环码。,扩展BCH码：,11.6.5 RS码,一类具有很强纠错能力的多进制BCH码。由里德和索洛蒙(Reed Solomon)提出。,一个能够纠t个错误符号的m进制的RS码有如下参数：,最小码距：d0=2t+1个 符号，或 q（2t+1）比特,码组长度：n=m 1=2q 1个符号，,督元长度：r=n-k=2t 个符号，或 2tq 比特,信元长度：k 个符号，或 k q个比特,参数,或 q(2q 1)个比特,RS码能够纠正t个m进制错码，即能纠正码组中t个不超过q位连续的二进制 错码，RS码特别适用于存在突发错误的信道，例如，移动通信网等衰落信道中。它是多进制纠错编码，特别适合用于多进制调制 的场合。,RS码的生成多项式：,g(x)=(x+)(x+2)(x+2t),式中，是伽罗华域GF(2q)中的本原元素。,卷 积 码,一种非分组码,11.7,非分组码概念：,分组码:,每个码组中的监督码元仅与本码组中的k个信元有约束关系。,非分组码:,即一个码组中的监督码元监督着N个信息段。,卷积码的符号:(n,k,N),N-编码约束度，表示编码过程中互相约束的码段个数；,nN-编码约束长度，表示编码过程中互相约束的码元个数。,卷积码的码率:R=k/n,(n,1,N)简单,常用,N 或nN 也反映了卷积码编码器的复杂度。,将k比特信息段编成n比特码组,一般，k，n较小，N较大；随着N增大，误码率呈指数下降；更适用于前向纠错，性能优于分组码，运算简单。,GSM（2,1,5）IS-95（2,1,9）CDMA2000（2,1,9),11.7.1 卷积码的基本原理,编码器原理方框图,存储以前的k(N-1)个信息码,当前 K个,共有N 段移存器，每段k 级,如图所示的(n,k,N)=(3,1,3)卷积码编码器。,共有3 段移存器，每段1 级（存储1个信元）,每次输入1b，输出 3b,分析：,信息位-,设移存器初始是全零状态，当输入信息序列：,则编码器输出序列：,结果为系统码形式。,信息位bi 的监督位和各信息位之间的约束关系如下图中虚线所示：（编码约束度 N=3，约束长度 nN=33=9）,卷积码的表述方法：,11.7.2 卷积码的代数表述,上式：,表示的卷积码也是一种线性码。,可完全由 H 或 G 所确定。,监督矩阵,生成矩阵,分类：,代数解码：利用编码本身的代数结构进行解码，不考虑信道的统计特性。,概率解码（最大似然解码）：基于信道的统计特性和卷积码的特点进行计算。,11.7.3 卷积码的解码,如：大数逻辑解码（门限解码），适用 nN 较短的卷积码。,序贯解码:适用无记忆信道,维特比算法：当码的 nN 较短时，效率更高、速度更快,约束长度,2 卷积码的几何表述 维特比解码算法的基础,1）码树图,以前面(3,1,3)卷积码为例：,并设 M1，M2和 M3 的初始状态 000,(n,k,N),(3,1,3)码树图：,规定,每条树枝上标注的码元为输出比特，每个节点为移存器的状态a b c d,若信息位 1 1 0 1,编码输出 111 110 010 100,(3,1,3)码树图：,M1M2M3,110,011,101,100,M3M2,01,11,10,01,00,状态,1101,1 1 0 1,(3,1,3)码树图：,若信息位 1 1 0 1,编码输出 111 110 010 100,码树图原则上还可用于解码。,发送序列,010,110,不实用基础,2）状态图,码树图状态图,由(3,1,3)编码器结构可知：,前一状态 a只能转到下一状态a或b；前一状态b只能转到下一状态c或d，等等。,按照 表中的规律 画出的状态图：,由表看出：,利用状态图可方便地从输入序列得到输出序列。例如：,输入信息位 1 1 0 1,编码输出 111 110 010 100,111,110,010,100,第4时隙后完全是第3时隙的重复，因（3,1,3）码约束长度为3。,3）网格图,将状态图在时间上展开 网格图,5个时隙,当输入信息位为11010时，在网格图中的编码路径：,这时的输出编码序列：111 110 010 100 011。,基于上面的状态图和网格图，讨论维特比解码算法。,3 维特比解码算法,基本原理,仍用上面(3,1,3)卷积码的例子来说明维特比算法的原理。,设发送信息位为1101，为了使图中移存器的信息位全部移出，在信息位后面加入3个“0”，故编码后的发送序列为 111 110 010 100 001 011 000设接收序列为 111 010 010 110 001 011 000,比较网格图中的这8条路径和接收序列之间的汉明距离。,(n,k,N),第1步,例如，由出发点状态 a 经 3级 路径后到达状态 a 的两条路径中：上面一条为“000 000 000”，它和接收序列“111 010 010”的汉明距离=5下面一条为“111 001 011”，它和接收序列 的汉明距离=3同样，由出发点a经过3级路径后到达状态b、c和d的路径分别都有两条，故总共有8条路径。下表中列出了这8条路径和其汉明距离。,接收序列 111 010 010 110 001 011 000,比较到达每个状态的两条路径的汉明距离作，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，可任意保存一条。就剩下4条路径：2,4,6，8,第2步,接收序列 111 010 010 110 001 011 000,按照表中的幸存路径画出的网格图示于下图中：,上例卷积码的约束度 N=3，需要存储和计算 8 条路径的参量。,故维特比解码算法适合约束度较小（N 10）的编码。对于约束度大的卷积码，可以采用其他解码算法。,由此可见，维特比解码算法的复杂度 随约束长度 N 按指数形 式 2N 增长。,交织编码主要用来纠正突发差错，即使突发差错分散成为随机差错而得到纠正。,交织编码不增加监督元，交织编码前后，码速率不变，不影响有效性。,常与其它纠正随机差错的编码(如卷积码或其它分组码)结合使用，既能纠正随机差错又能纠正突发差错。,在移动信道中数字信号传输常出现成串的突发差错，数字化移动通信中经常使用交织编码技术。,交织编码,第一个码字：c11c12c13c14c15c16c17，第二个码字：c21c22c27，第m个码字：cm1cm2 cm7。,交织方法,将每个码字按行存入存储器：,一般在交织之前，先进行分组码编码，如采用(7，3)码,