第21讲 差错控制技术.ppt

纠错编码 纠错编码基本原理 在循环码中，设T(x)是一个长度为n的码组，若 则T? (x)也是该编码中的一个码组。 [证] 设一循环码为 则有 上式中的T? (x) 正是码组T (x)向左循环移位 i 次的结果。 例： 一循环码为1100101，即 若给定 i = 3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果。 结论：一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 循环码的生成 有了生成矩阵G，就可以由k个信息位得出整个码组： 例： 式中， 生成矩阵G的每一行都是一个码组。 因此，若能找到 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。 在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到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)循环码就被确定了。 因此，循环码的生成矩阵G可以写成 例： 上表中的编码为(7, 3)循环码，n = 7, k = 3, n – k = 4，其中唯一的一个(n – k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为 g(x) = x4 + x2 + x + 1。 g(x) = x4 + x2 + x + 1 即 “1 0 1 1 1” 将此g(x)代入上矩阵，得到 或 上式不符合G = [IkQ]形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。 此循环码组的多项式表示式T(x)： 上式表明，所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k – 1)的多项式乘g(x)都是码多项式。 寻求码生成多项式 因为任意一个循环码T(x)都是g(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。因此，上式可以写成 将 T(x) = h(x)?g(x) 和 T ?(x) = g(x) 代入 化简后，得到 上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。 例：(x7 + 1)可以分解为 为了求出(7, 3)循环码的生成多项式 g(x)，需要从上式中找到一个(n – k) = 4次的因子。这样的因子有两个，即 以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。 循环码的编码方法 用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 循环码的解码方法 在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即下式 中余项r(x)