通信原理课件11差错控制编码.pptVIP

第11章 差错控制编码 循环码的码多项式 在循环码中，若T(x)是一个长为n的许用码组，则xi?T(x)在按模xn + 1运算下，也是该编码中的一个许用码组，即若 则T ?(x)也是该编码中的一个许用码组。 【证】因为若 则 （模(xn + 1)） 所以，这时有 上式中T ?(x)正是T(x)代表的码组向左循环移位i次的结果。因为原已假定T(x)是循环码的一个码组，所以T? (x)也必为该码中一个码组。例如，循环码组 其码长n = 7。现给定i = 3，则 其对应的码组为0101110，它正是表中第3码组。 由上述分析可见，一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 循环码的生成矩阵G 由上节中公式 可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。例如，在此式中，若a6a5a4a3 = 1000，则码组A就等于G的第一行；若a6a5a4a3 = 0100，则码组A就等于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。 在循环码中除全“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)循环码就被确定了。 因此，循环码的生成矩阵G可以写成 例：在上表所给出的(7, 3)循环码中，n = 7, k = 3, n – k = 4。由此表可见，唯一的一个(n – k) = 4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式）g(x) = x4 + x2 + x + 1。将此g(x)代入上式，得到 或 由于上式不符合G = [IkQ]的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。 我们可以写出此循环码组，即 上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k – 1)的多项式乘g(x)都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是T(x)。为了简洁，式中直接将乘积写为此元素。 如何寻找任一(n, k)循环码的生成多项式 由上式可知，任一循环码多项式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)和T?(x)表示式代入上式，经过化简后得到 上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。这一结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是(xn +1)的一个(n – k)次因式。例如，(x7 + 1)可以分解为 为了求(7, 3)循环码的生成多项式g(x)，需要从上式中找到一个(n – k) = 4次的因子。不难看出，这样的因子有两个，即 11.6.2 循环码的编解码方法 循环码的编码方法 编码原则 在编码时，首先要根据给定的(n, k)值选定生成多项式g(x)，即从(xn + 1)的因子中选一个(n - k)次多项式作为g(x)。 由于所有码多项式T(x)都可以被g(x)整除。根据这条原则，就可以对给定的信息位进行编码： 设m(x