差错控制编码第三次课.pptVIP

循环码 循环码举例——(7,3)循环码 例如 A=0010111(1) A(x)=0x6+0x5+1x4+0x3+1x2+1x1+1x0 =x4+x2+x+1 xA(x)=x5+x3+x2+x A=0101110(2) 二、循环码的运算 1、码多项式的按模运算 多项式F(x)被n次多项式N(x)除，得到商式q(x)和一个次数小于n的余式R(x)，即 在循环码中，若T(x)是一个长为n的许用码组，则在按模 运算下，亦是一个许用码组。 例 表9—6的循环码, 唯一的一个(n-k)次码多项式代表的码组是0010111，相对应的码多项式为 这个生成矩阵不是系统码的生成矩阵，可以通过行变换，变换成系统码的生成矩阵。 说明g(x)是xn+1的因式。 因为任码多项式T(x)都是g(x)的倍式，所以有 T(x)=h(x)g(x) g(x)本身也是一个码组，其次数为n-k次。把它循环移位k次仍为一个码组。所以xkg(x)是n次多项式，在模xn+1 运算下，所以 即 最高次幂n-k g(x)是一个常数项为1 最多k-1个连0 是 的一个因式； 任意一码组多项式可表示为： d(x)代入T(X)得： 假如输入信息码元mk-1 mk-2 … m0 则 例 表9—6的循环码, 唯一的一个(n-k)次码多项式代表的码组是0010111，相对应的码多项式为 这个生成矩阵不是系统码的生成矩阵，可以通过行变换，变换成系统码的生成矩阵。 循环码的编码 例 (7,3)循环码 m(x)=x2+x, g(x)= x4 +x2+ x+1 检错电路图 (1)根据实际通信系统对纠错能力的要求，寻找合适的码型（通常是一种长码型）。要求该码型可以在数学上证明具有满足要求的纠错能力，并具有数学结构，且能够根据此结构用一些设备实现编码和译码。 (2)寻找实用的编码方法，尽量提高编码效率。 (3)寻找实用的译码方法，尽量降低译码的复杂性。 * 循环码除具有线性码的一般性质外,还具有循环性 即任一码组循环一位以后，仍为该循环码中的一个许用码组。 一、循环码的特点 线性分组码 0010 111 7 1001 011 3 0101 110 6 1110 010 2 1100 101 5 0111 001 1 1011 100 4 0000 000 0 a3a2a1a0 a6a5a4 编号 a3a2a1a0 a6a5a4 编号 监督位 信息位 码组 监督位 信息位 码组 2、码多项式——码组的多项式表示 若一个整数m,若可以表示为 则：m ≡ p(模n) 码多项式系数仍按模2运算，即只取值0和1 则写为F(x) ≡ R(x) ( 模N(x) ) 例如 则T’（X）也是该编码码组中的一个许用码组 2．循环码的生成矩阵G 若能找到k个线性无关的码组,就能构成矩阵G。在循环码中，一个(n，k)码有2k个不同码组，若用g(x)表示其中前(k-1)位皆为0的码组，即 g(x)=0 …1x … x k位 n-k位 则g(x) 、xg(x)，x2g(x) ，…，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此可以用来构成循环码的生成矩阵G。 一旦确定了g(x)，则整个(n．k)循环码就被确定了。因此,循环码的生成矩阵G可以写成 g(x)＝x4+x2+x+1 将此g(x)代入上式，得到 g(x)的性质： g(x)必须是一个常数项a0=1； 次数为(n-k)次； 唯一的(n-k)次多项式； 我们称这唯一的g(x)为码的生成多项式。 g(x)是xn+1的因式（见后面分析）。 因为xkg(x)是n次的，所以Q(x)=1 。所以 所以 即 g(x)是xn+1的因式。 这样就可以通过对xn+1的因式分解得到g(x). 循环码的生成多项式 生成多项式 一个k位的信息码组Ｄ＝［dk-1,dk-2, …….d0] 信息码多项式: T(x)=d(x)g(x) 循环码 不大于n-1次的多项式 例：求（7，4）循环码的生成多项式g(x),当信息码组D=[1010]时，求输出码组 若能找到k个线性无关的码组,就能构成矩阵G。 g(x) 、xg(x)，x2g(x) ，…，xk-1g(x)都是许用码组，而且这k个码组是线性无关的。因此可以用来构成循环码的生成矩阵G。