16.编码.ppt

1、组合数学,1,编 码,目的要求 掌握编码理论的基本知识 掌握线性分组码的基本知识,组合数学,2,上节内容回顾,定义5-1 如果原有的信息编码含m位，按照一定的规则添加nm个（nm）附加位形成的n位长字符串称为码字，n称为码长，每一位称为码元。这样的编码称为分组码。 在分组码的码字中，前m位恰是原有的信息，称为信息位，后nm位用来检查错误和纠正错误，称为校验位。,组合数学,3,比率mn是编码的一项重要参数，称为码率。 在w后面添加1位校验位，并且如果信息位中有偶数个1，则校验位取0；否则校验位取1。这样产生的编码称为奇偶校验码。 如果原有的信息编码有m位，则在它的后面添加2m位，并且这2m位恰是

2、将信息位重复两次。这样产生的编码称为三次重复码。,组合数学,4,n位二进制数c、r和e之间有如下关系 rce，cre，ecr 定义5-2 对于每个由n位二进制数构成的字符串xx1x2xn，x中1的个数称为x的权，记为w(x)。若yy1y2yn也是n位二进制数构成的字符串，则称d(x,y)w(xy)为x与y的汉明(Hamming)距离。,组合数学,5,定义5-2 对于每个由n位二进制数构成的字符串xx1x2xn，x中1的个数称为x的权，记为w(x)。若yy1y2yn也是n位二进制数构成的字符串，则称d(x,y)w(xy)为x与y的汉明(Hamming)距离。 引理5-1 对于所有由n位二进制数构

3、成的字符串x和y，都有w(xy)w(x)w(y)。,组合数学,6,定理5-1 对于所有由n位二进制数构成的字符串x和y，都满足下面的4个性质： （1）d(x,y)0 （2）d(x,y)0 xy （3）d(x,y)d(y,x) （4）d(x,z)d(x,y)d(y,z) 对于长度为n的一组编码，将其码字间的最小距离记为d。,组合数学,7,定理5-2 一组编码可以查出k个错误的充分必要条件是这组编码的码字间的最小距离至少是k1。 定理5-3 设一组编码的任意两个码字间的最小距离至少是2k1，则权不超过k的误差可以得到纠正。,组合数学,8,线性分组码,实例5-1 矩阵 可以用来定义一个编码函数：E(

4、w)wG，其中w是任意一个由3位二进制数构成的字符串。在这种意义下称G为生成矩阵。例如,组合数学,9,可以用来定义一个编码函数：E(w)wG，其中w是任意一个由3位二进制数构成的字符串。在这种意义下称G为生成矩阵。例如,组合数学,10,由这个生成矩阵G得到的码字集合是 C000000,100110,010011,001101, 110101,101011,011110,111000 对于这个码字集合C，可以通过直接取码字的前3个码元来重现信息。 注意到，码字集合C的码字间的最小距离是3。因此，用这组码可以查出所有权2的错误。,组合数学,11,对于所有由3位二进制数构成的字符串ww1w2w3，有

5、 w1w2w3(w1w3)(w1w2)(w2w3) 所以有w4w1w3，w5w1w2，w6w2w3。,组合数学,12,因为这里的运算是模2加法，这些方程w4w1w3，w5w1w2，w6w2w3可以改写为 w1 w3w4 0 w1w2 w5 0 w2w3 w60 于是有,组合数学,13,因此，如果由6位二进制数构成的字符串rr1r2r3r4r5r6是一个码字当且仅当,组合数学,14,根据前面介绍的纠错理论，因为实例5-1中这些码字间的最小距离是3，所以可以建立一个译码函数来纠单错。 假定接收到的字符串是r110110，并希望求出离r最近的码字c。实际的做法是检验HrT，通常称HrT为r的校正子。

6、,组合数学,15,由于 所以r不是码字。这就可以断言，r110110至少有一个错误。回顾所有的码字中，只有d(100110, r)1。,组合数学,16,由 rce100110010000 可以看出，r110110恰好有一个错误，并且这个错误发生在r的第2位。,组合数学,17,细心的读者可能已经发现，校正子HrT恰好是H的第2列。这是巧合吗？不是。这是必然结果。换句话说，通过计算校正子HrT，如果结果和H的第i列相同，就意味着r恰好有一个错误，并且这个错误就发生在第i位。据此就可以纠错了。,组合数学,18,线性分组码的标准校验矩阵H与生成矩阵G是有明确关系的。为了方便表达，引用记号： GmnIm|Am(nm)， H(nm)nB(nm)m|Inm， 则有BAT。更简捷的表达是：若记GIm|A，则HAT|Inm。 实例5-1的结果可以推广到一般。,组合数学,19,课后作业,1、令C是一个码字集合，且下面的各小题中，都给出了c（码字）、r（接受到的字符串）和e（错误型式）中的两项，求第三项。 (1) c1010110，r1011111 (2) c1010110，e0100010 (3) e1000010，r0100111 2、在二元码中，针对下列各组