信道编码(中).ppt

第三章 信道编码  3.4 循环码  （第12讲 2007.11.13.） 上节回顾：线性分组码 基本概念： 表达方式：(n,k)码，k是信息位数，r是监督位数，n=k+r是码长。 编码：已知信息K（k位二进序列），求相应码字的方法是 C=KG，G叫生成矩阵，是k行n列的， 一般G具有[Ik Q]的形式， Ik 是k行k列单位方阵，Q是k行r列的矩阵。 生成矩阵的设计，应使许用码字之间的最小汉明距离尽量地大。 译玛：当收到码字R时，首先计算伴随子向量：S=RHT；若S=0，则R=C为正确码字；若S ≠ 0，则R≠C为错误码字。 这里H叫一致监督矩阵，是r行n列的。一般H具有[P Ir]的形式， Ir 是r行r列单位方阵，P是r行k列的矩阵， P与Q互为转置关系。 纠正1位错：当S ≠ 0时，由S=R·HT 求出S ，比较S 与HT ， HT的那一行与S相同，相应的错误格式向量E的那一位就等于1。于是R的那一位就是错误的，根据 C=R+E进行将其纠正。 引言： 构造线性分组码关键是设计出一个好的生成矩阵，使所有码字之间的汉明距离尽量大。怎样找这样的矩阵呢？循环码的出现提供了一整套理论和方法，使人们能够借助数学工具来寻找更好的线性分组码，并由此引发出一大类很常用检、纠错编译码。 不难发现 上节所讨论过的(7,3) 线性分组码具有循环移位特性： C0=(0000000); C0=(0000000); C1=(0011101); C1=(0011101); C2=(0100111); C3=(0111010); C3=(0111010); C7=(1110100); C4=(1001110); C6=(1101001); C5=(1010011); C5=(1010011); C6=(1101001); C2=(0100111); C7=(1110100); C4=(1001110); 循环码是线性分组码中的一个子集。 对于循环码，有了一个的码字，按循环移位规律就能写出n个码字。从中选出k个来构造生成矩阵G，就能生成全部2k个许用码字。 循环码与近代数学有密切联系。由此我们便可以借助数学工具来设计编码。 3.4.1 码多项式 二进制自然码可表达为以2为底的多项表达形式，如： C = (1010111)= =1×26 +0×25 +1×24 +0×23 +1×22 +1×21 +1×20 ； 把底换为x，则得到 “码多项式”： C (x) = 1·x6 +0·x5 +1·x4 +0·x3 +1·x2 +1·x1 +1·x0 = x6 + x4 + x2 + x +1 码长为n时，可写： C (x) = cn-1 xn-1 + cn-2 xn-2 +…… + c1×x1 + c0 x0 如三位二元码的8个码字对应的码多项式为： 000， 001， 010，011， 100， 101， 110， 111； 0， 1， x , x+1, x2, x2 +1, x2 + x , x2 + x +1 3.4.2 循环移位的数学表达 对二进数，左移一位相当于乘以2，而将最高位的进位(2 n位)上的数码拿回到2 0位，叫做循环移位，相当于作模2n -1运算。 如：101→1010→011 实际是 5×2 mod 7 = 3 码多项式的循环移位，实际是乘x后作模 xn -1运算。 如： 1100010 →→ 1000101 (x6 +x5 +x) → x(x6 +x5 +x) mod (x7-1) = (x7 +x6 +x2) mod (x7-1) = x6 +x2 +1 用循环移位得到（7, 4）循环码的码多项式 序号 信息 循环码 循环次数 码多项式 模x7-1运算后 1 0001 0001011 0 x3 +x +1 x3 +x +1 2 0010 0010110 1 x (x3 +x +1) x4 +x2 +x 3 0101 0101100 2 x2 (x3 +x +1)