第11章未备份.ppt

1,通信原理,2,通信原理,第11章差错控制编码,3,第11章差错控制编码,11.1 概述信道分类：从差错控制角度看随机信道：错码的出现是随机的 突发信道：错码是成串集中出现的混合信道：既存在随机错码又存在突发错码 差错控制技术的种类 检错重发:差错控制码元出错重发前向纠错 差错控制码元有错误、且可纠正，则进行纠正有错误、但不可纠正，则仅报告错误反馈校验不需要差错控制码元出错重发检错删除 差错控制码元出错则放弃该组数据。,4,检错重发的实现：3种ARQ系统,3种ARQ（Automatic Repeat reQuest）系统停止等待ARQ系统拉后ARQ系统选择重发ARQ系统简单了解即可，主要了解其与“前向纠错方法”相比的优缺点ARQ的主要优点：监督码元较少即能使误码率降到很低，即编码效率较高；检错的计算复杂度较低；检错编码方法和加性干扰的统计特性基本无关，能适应信道ARQ的主要缺点：需要双向信道来重发，且不能用于一点到多点的通信系统。因为重发而使ARQ系统的传输效率降低。信道干扰严重时，会发生因不断重发而致实际的通信中断。在要求实时通信的场合，如电话通信，往往不允许使用ARQ法。,5,第11章差错控制编码,差错控制编码：常称为纠错编码差错控制编码过程：在发送端按照某种规则在需要发送的信息码元序列中增加一些冗余的码元，从而使接收端可以根据这些冗余码元来进行检错或纠错的过程。差错控制编码：具有检错和/或纠错能力的编码被称为“差错控制编码”。监督码元：差错控制编码中的冗余码元被称为“监督码元”。设编码序列中信息码元数量为k，总码元数量为n，即监督码元的数量为(n-k)，则多余度：定义为(n-k)/n冗余度：定义为(n-k)/k编码效率(简称码率)：定义为 k/n理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,6,第11章差错控制编码,11.2 纠错编码的基本原理某些信息被编码为k位二进制码元，并且每一个k位二进制数字的排列都被用来表示一个信息。设所有可能的天气被分为4种，它们可以用2位二进制数字构成的码组来表示，即k=2。这4种天气的编码为：“00”（晴），“01”（云），“10”（阴），“11”（雨）对于k位二进制码组，如果其所有的2k种组合都被用来表示有效信息，则任意一个有效码组在传输中发生错误、其结果仍然是一个有效的码组。接收端不能够区分以下两种情况：“接收的码组没有错误”、“接收的码组=一个正确的码组+错误”，从而无法进行检错或纠错。上例中，假设发送的是“00”（晴），但由于信道噪声，接收端错误地判决为“01”，则接收端只能认为天气是“云”，从而导致了错误。,7,第11章差错控制编码,为了进行检错或纠错，可以采用n位二进制数字来表示“用k位二进制数字即可表示的信息”，其中nk。采用n位二进制数字表示k位二进制数字即可表示的信息时，仅仅用了2n种排列中的2k种，其余（2n-2k）种排列并未被使用。所使用的2k种排列，即所使用的2k种码组，被称为“许用码组”。未使用的（2n-2k）种排列，即未使用的码组，被称为“禁用码组”。几种可能的情况如传输中未发生错误，则接收端得到的每一个码组都应该是许用码组。当传输中发生错误，接收端判决得到的的结果可能还是一个许用码组。当传输中发生错误，接收端判决得到的的结果可能是一个禁用码组接收端判决得到一个禁用码组，则表明传输过程中一定发生了错误，即达到了检错的目的。对于合理设计的编码，还可能纠正某些错误，从而达到纠错的目的。,8,第11章差错控制编码,用nk位二进制数字表示“用k位二进制数字即可表示的信息”的例子。采用如下的许用码组来表示4种天气：可检1个错、不能纠错；要纠错，需增加多余度,原始信息位,监督码元：监督位,9,第11章差错控制编码,分组码(Block code)将信息码分组，并在每组信息码附加若干监督码元的编码称为分组码。前面的编码即是一种分组码。在分组码中，监督码元仅监督本码组中的信息码元。分组码的一般结构分组码的符号：(n,k)N 一个码组的总位数，又称为码组的长度（码长），k 码组中信息码元的数目，n k r 码组中的监督码元数目，或称监督位数目。,10,第11章差错控制编码,分组码的码重和码距码重：把码组中“1”的个数目称为码组的重量，简称码重。码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。最小码距：把某种编码中各个码组之间距离的最小值称为最小码距(d0)。例如，上面的编码的最小码距d0=2。,11,第11章差错控制编码,码距和检纠错能力的关系一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力为检测e个错码，要求最小码距 d0 e+1【证】设一个码组A位于O点。当发生e个错误时，则我们可以认为A的位置将移动至以O点为圆心、以e为半径的圆上某点。只要d0e，则A就不会变成另一个准用码组。即，要检测e个错误，则必须有d0e，也即d0 e+1。,12,第11章差错控制编码,为了纠正t个错码，要求最小码距d0 2t+1,13,第11章差错控制编码,为纠正t个错码，同时检测e个错码，要求最小码距纠检结合：这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率。当错码数量多时，系统按反馈重发方式纠错，以降低系统总误码率。,14,第11章差错控制编码,11.3 纠错编码的性能监督码元的加入的两面性发送序列长度信息速率不变的情况下，码元速率带宽噪声Pe 具有纠错和/或纠错的能力Pe总的效果：一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。改善的代价是所用带宽增加。,15,第11章差错控制编码,由编码导致的性能改善相同信噪比时相同误比特率时编码增益,16,第11章差错控制编码,11.4简单的实用编码11.4.1 奇偶监督码偶数监督码：发送端的编码：监督位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：式中a0为监督位，其他位为信息位。接收端的解码：按照上式对判决器的输出求“模2和”。若计算结果为“1”就说明存在错码。若结果为“0”就认为无错码。检错/纠错能力：能够检测奇数个错码，不能纠错。奇数监督码：与偶数监督码相似，只不过其码组中“1”的数目为奇数：,17,第11章差错控制编码,11.4.2 二维奇偶监督码（方阵码）二维奇偶监督码的构成,18,第11章差错控制编码,二维奇偶监督码的性能有可能检测偶数个错码。有一些偶数错码不可能检测出来。例如，构成矩形的4个错码，譬如前页图中用方框标出的4个码元发生错误时，就检测不出。适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。有些时候可以使误码率下降至原误码率的1/1001/1000。二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。,19,第11章差错控制编码,11.5 线性分组码按编码原理（产生监督位的方法）分类基本概念代数码：建立在代数学基础上的编码。线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。线性分组码：按照一组线性方程构成的分组码。本节以汉明码为例介绍线性分组码的一般原理。,20,第11章差错控制编码,汉明码能够纠正1位错码且编码效率较高的一种线性分组码汉明码的构造原理。在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S=0，就认为无错码。若S=1，就认为有错码。上式称为监督关系式，S称为校正子（又称校验子、伴随式）。,21,第11章差错控制编码,若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4中组合：00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就可用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求,22,第11章差错控制编码,例：设分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：,23,第11章差错控制编码,由表中规定可见，仅当一位错码的位置在a2、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2、a4、a5和a6四个码元构成偶数监督关系：同理，a1、a3、a5和a6构成偶数监督关系：以及a0、a3、a4 和a6构成偶数监督关系,24,第11章差错控制编码,在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位 给定信息位后，可以直接按上式算出监督位（见下表）。,25,第11章差错控制编码,26,第11章差错控制编码,接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。按照上述方法构造的码是一种汉明码。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,27,第11章差错控制编码,线性分组码的一般原理线性分组码的构造H矩阵（监督矩阵，或称为校验矩阵）上面(7,4)汉明码的例子有以下的监督关系式：现在将上面它改写为上式中已经将“”简写成“+”。,28,第11章差错控制编码,上式可以表示成如下矩阵形式：上式还可以简记为H AT=0T 或A HT=0其中，A=a6 a5 a4 a3 a2 a1 a0，0=000H称为监督矩阵只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。,29,第11章差错控制编码,监督矩阵H的性质：H的行数就是监督关系式的数目，它等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。H矩阵可以分成两部分，例如式中，P为r k阶矩阵，Ir为r r阶单位方阵。具有P Ir形式的H矩阵称为典型阵。由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到 r个线性无关的监督关系式，从而也得不到 r个独立的监督位。,30,第11章差错控制编码,G矩阵（生成矩阵）：上面汉明码例子中的监督位公式为也可以改写成矩阵形式：或者写成式中，Q为一个k r阶矩阵，它为P的转置，即 Q=PT,31,第11章差错控制编码,生成矩阵G 由生成矩阵G可以产生整个码组，即有或者具有Ik Q形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码。,32,第11章差错控制编码,G矩阵的性质：G矩阵的各行是线性无关的。实际上，G的每一行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。,33,第11章差错控制编码,错码矩阵（也称为错误图样）发送的码组是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为n列的行矩阵B，即则发送码组和接收码组之差为B A=E(模2)它就是传输中产生的错码行矩阵 式中,34,第11章差错控制编码,若ei=0，表示该接收码元无错；若ei=1，则表示该接收码元有错。B A=E 可以改写成 B=A+E例如，若发送码组A=1000111，错码矩阵E=0000100，则接收码组B=1000011。错码矩阵有时也称为错误图样。,35,第11章差错控制编码,校正子S 将B=A+E代入B H T=S，可得 S=(A+E)H T=A H T+E H T 由于A HT=0，所以S=E H T 式中S称为校正子。它能用来指示错码的位置。S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。思考题：如何用S来确定错码位置？,36,第11章差错控制编码,线性分组码的性质封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。,37,第11章差错控制编码,11.6 循环码：线性分组码的一种11.6.1 循环码原理循环性：循环性是指任一码组循环移位1次或多次（即将最右端的一个码元移至左端，或反之）后，仍为该码中的一个码组。下表中给出一种(7,3)循环码的全部码组。,38,第11章差错控制编码,码多项式码组的多项式表示法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成例如，上表中的任意一个码组可以表示为 其中第7个码组可以表示为这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。,39,第11章差错控制编码,码多项式的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1+1=2 0(模2)，1+2=3 1(模2)，2 3=6 0(模2)等等。一般说来，若一个整数m可以表示为 式中，Q 整数，则在模 n 运算下，有m p(模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。,40,第11章差错控制编码,在码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一个 n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3+1)除，得到余项1。所以有同理因为,应当注意，由于在模2运算中，用加法代替了减法，故余项不是x2 x+1，而是x2+x+1。,41,第11章差错控制编码,循环码的码多项式在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若则T(x)也是该编码中的一个许用码组。【证明】因为若 则在模(xn+1)下有 所以，这时有,42,第11章差错控制编码,上式中T(x)正是T(x)代表的码组向左循环移位i次的结果。因为原已假定T(x)是循环码的一个码组，所以T(x)也必为该码中一个码组，从而证明了上述定理。例如，循环码组其码长n=7。现给定i=3，则其对应的码组为0101110，它正是表中第3码组。由上述分析可见，一个长为n的循环码必定为按模(xn+1)运算的一个余式。,43,第11章差错控制编码,循环码的生成矩阵G由上节例子中的分组码的公式可知有了生成矩阵G，就可以由k个信息位得出整个码组。生成矩阵G的每一行都是一个码组。由于G是k行n列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。在循环码中，一个(n,k)码有2k个不同的码组。若g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,44,第11章差错控制编码,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能有(k-1)位。否则，在经过若干次循环移位后将得到一个k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n k)的唯一多项式。因为如果有两个，则由码的封闭性，这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的，故是不可能的。我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。,45,第11章差错控制编码,因此，循环码的生成矩阵G可以写成 例：在上表所给出的(7,3)循环码中，n=7,k=3,n k=4。由此表可见，唯一的一个(n k)=4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式）g(x)=x4+x2+x+1。将此g(x)代入上式，得到或,46,第11章差错控制编码,由于上式不符合G=IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。我们可以写出此循环码组，即上式表明：所有码多项式T(x)都可被g(x)整除且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。,47,第11章差错控制编码,如何寻找任一(n,k)循环码的生成多项式 任意一个循环码多项式T(x)都可写成：T(x)=h(x)g(x)生成多项式g(x)也是一个码组，此处记为：T(x)=g(x)由于码组T(x)是一个(n k)次多项式，故xk T(x)是一个n次多项式。根据以前的结果知：xk T(x)在模(xn+1)运算下也是一个码组，故可以写成或写成上式左端分子和分母都是n次多项式，故商式Q(x)=1。因此，上式可以化成：,48,第11章差错控制编码,将T(x)和T(x)表示式代入上式，经过化简后得到上式表明，生成多项式g(x)应该是(xn+1)的一个因子。又由于g(x)是一个(n k)次多项式，所以，循环码的生成多项式g(x)应该是(xn+1)的一个(n k)次因式。例如，(x7+1)可以分解为为了求(7,3)循环码的生成多项式g(x)，需要从上式中找到一个(n k)=4次的因子。不难看出，这样的因子有两个：选用的生成多项式不同，产生出的循环码码组也不同。,49,第11章差错控制编码,11.6.2 循环码的编解码方法循环码的编码方法：手工计算时，也可用A=an-1,an-2,an-kG编码原则：这里的方法是为了导出适合于硬件实现的编码方法。在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即从(xn+1)的因子中选一个(n-k)次多项式作为g(x)。由于所有码多项式T(x)都可以被g(x)整除。根据这条原则，就可以对给定的信息位进行编码：设m(x)为信息码多项式：因信息为k位，所以m(x)的次数小于k。用xn-k乘m(x)，得到的xn-k m(x)的次数必定小于n：乘以xn-k的目的是使信息占据码组的高k位。假定xn-k m(x)除以g(x)得到的商多项式为p(x)、余数多项式为r(x)，则xn-k m(x)可以写成：其中，xn-k m(x)的次数必定小于n r(x)的次数必定小于g(x)的次数，即小于(n k)。上述式子可根据模2加法写成：这表明上式的左端可以被g(x)整除，而且它是阶次小于n的多项式，因此它是一个码多项式，也即它对应一个码组。也即，通过上述过程，把信息m(x)，编码成了表示的码组，其中，信息占据了码组的高k位，而监督位对应多项式r(x)、占据了码组的低(n-k)位。,50,第11章差错控制编码,编码步骤：用xn-k乘m(x)：实际是在信息码后附加(n k)个“0”。例如，信息码为110，也即m(x)=x2+x。当n k=7 3=4时，xn-k m(x)=x4(x2+x)=x6+x5，它相当于1100000。用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即例如，若选定g(x)=x4+x2+x+1，则 上式相当于：编出的码组T(x)为T(x)=xn-k m(x)+r(x)在上例中，T(x)=1100000+101=1100101，它是第40个PPT中的表中的第7个码组。,51,第11章差错控制编码,循环码的解码方法解码要求：检错和纠错。检错解码原理：由于任意一个码组多项式T(x)都应该能被生成多项式g(x)整除，所以在接收端可以将接收码组R(x)用原生成多项式g(x)去除。当传输中未发生错误时，接收码组与发送码组相同，即R(x)=T(x)，故接收码组R(x)必定能被g(x)整除；若码组在传输中发生错误，则R(x)T(x)，R(x)被g(x)除时可能除不尽而有余项，即有因此，就以余项是否为零来判别接收码组中有无错码。需要指出，有错码的接收码组也有可能被g(x)整除。这时的错码就不能检出了。这种错误称为不可检错误。不可检错误中的误码数必定超过了这种编码的检错能力。,52,第11章差错控制编码,纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。因为只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。因此，原则上纠错可按下述步骤进行：用接收码组R(x)除以生成多项式g(x)，得出余式r(x)。按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)。余式r(x)与错误图样E(x)的对应表可预先建立。也即：先假定一个错误图样E(x)，再将其除以g(x)，得到的余式即为该错误 图样对应的r(x)。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。上述解码方法称为捕错解码法。手工计算的一种方法：由生成矩阵G导出校验矩阵H：矩阵G和矩阵H的关系见11.5节“一般线性分组码原理”部分。对于每种可能的单个错误图样E(x)，将其与校验矩阵H相乘，从而得到相应的校正算子S。将对应的E(x)和S放在一个表中，每一对为一行。注意，当2n-kn时，编码可以校正多个错误，则表中将有多于n行。将矩阵H和实际接收的码组相乘就得到校正子S。由校正算子S，查表，就可得到相应的错误图样E(x)。将E(x)加到实际接收的码组上，就得到纠正的码组。,