第9章 差错控制编码1.ppt

通 信 原 理 电 子 教 案第9章 差错控制编码 西 北 工 业 大 学 （2012.5） 9.1 引言一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。 9.5.1 循环码的概念 定义：是一种具有循环移位特性的线性分组码。 特点：编译码设备简单；检纠错能力强。 9.5 循环码 构成原理： 具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。 码多项式 定义： 为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。 设：许用循环码 A=(an-1 an-2 … a1 a0) 则：它的码多项式表示为： 其中：xi 仅是码元位置的标记。 码字与码多项式一一对应！ 表9-6 (7，3)循环码 反之，由码多项式易得出码组。 2.码多项式的按模运算 1）整数的按模运算 若一个整数m可以表示为: 则在模n运算下，有m≡p（模n）。 例： 同样对于多项式而言，也有类似按模运算。 其中：商Q(x)为多项式，余数R(x)的幂次低于N(x)的幂次。 例: 求 x4+x2+1 按模 x3+1 运算的余式 R(x) 2）码多项式的按模运算 若 则 3）循环性 可以证明：在循环码中，若A(x) 是一个长为n的许用码组，则xiA(x) 在按模xn+1运算下，亦是许用码组。即若有 则A(x)也是一个许用码组。 例: 前述（7，3）码：A(x) = x6+x5+x4+x2 （1110100） －－前码组循环左移1位！ 多项式除法： 余式 9.5.2 循环码的生成多项式g(x) （1）存在性 ( n，k ) 循环码中有且仅有一个g(x)，为 g(x)=xn-k+……+1 特点: 最高的次数为n-k=r； 常数项系数必为1 。 在循环码中，除了全0码组外，再也没有连续k位均为0的码组。即连0长度最多为k-1位！ 这唯一的n-k次多项式称为生成多项式，记为g(x)！ （2）生成多项式 g(x) 与生成矩阵 G(x) 的关系 A = [ an-1…ar ] G G = [ Ik Q ] ∵生成矩阵G的每一行都是一个码组；G是k行n列矩阵。 ∴只要找到k个已知码组，就能构成生成矩阵G！ 生成多项式确定后，则g(x)、x g(x)、……、 xk-1 g(x)都是码组，且这k个码组信息无关，因此可以用来构成生成矩阵。 g(x)确定了→G(x)也就确定了→整个码组即确定！ 例: ( 7，3 )循环码， g(x) = x4+x2+x+1 求典型生成矩阵 解: 可方便地直接写成码组形式 典型阵: （3）生成多项式g(x) 与码多项式A(x) 的关系－－（7，3） 表明：所有A(x)都可以被g(x)整除，而且任一次数不大于(k-1)的多项式乘以g(x)都是码多项式。 A(x)∣模g(x)=0 。 h(x)为不大于(k-1)的多项式！ 结论: g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。 证明：任一循环多项式A(x)都是g(x)的倍式，即 而生成多项式g(x)本身也是一个码组，即有 由于码组A(x)为一（n-k）次多项式，故xkA(x) 为一n次多项式。由 知，xkA (x)在模（xn+1）的运算下，亦为一码组，故可写成 （4） 如何寻找g(x) 上式左端分子和分母都是n次多项式，故商Q(x)＝1，因此上式可化成即 将A(x)=h(x)g(x)、 A(x)=g(x)代入，并整理，得 表明: g(x)应该是xn+1的一个因式！ 证得: g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。 例：如 (x7+1) = (x+1)(x3+x2+1)(x3+x+1) 则有g(x)： （7，4）： x3+x2+1、x3+x+1 （7，3）： (x+1)(x3+x2+1) 、(x+1)(x3+x+1) （7，6）： x+1 例: （7，3）循环码有多项式如下，找出（7，3）码的生成多项式g(x)。 （1） x4+x3+x （2） x3+x2+1 （3） x+1 （4） x4+x2+x+1 （5） x4+x+1 解: 依据 r = 7-3 = 4，常数项不为零，有 （4） x4+x2+x+1