95循环码 选 循环码的原理 循环码的特性 (1)循环码是一种重要的线性分组码,易于 实现,性能较好。 (2)循环码除具有线性码的一般性质外,还 具有循环性,即循环码中任一码组循环一位以后, 仍为该码中的一个码组。 只关心其系数,而 2、码多项式的按模运算不关心x的取值。 长为m的码组可表示成码多项式 T(x=ax"+ax+.+a,x+a 2021/2/23 海南大学信息学院 Return Next
2021/2/23 海南大学 信息学院 Return Next 1、循环码的特性 （1）循环码是一种重要的线性分组码，易于 实现，性能较好。 （2）循环码除具有线性码的一般性质外，还 具有循环性，即循环码中任一码组循环一位以后， 仍为该码中的一个码组。 9.5 循环码 1 0 2 2 1 1 T(x) a x a x a x a n n n = n + + + + − − − − 2、码多项式的按模运算 一长为n的码组可表示成码多项式 只关心其系数，而 不关心 x 的取值。 一、循环码的原理
95循环码 选 若F(x)=N(x)Q(x)+R(x) 则F(x)三R(x)(模N(x) 例x-4+x2+1≡x2+x+1(模x3+1) 2 x+lx+x+ x+x 码多项式系数仍 按模运算;其减 x2甲x+1 法以加法代替。 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 则 F(x) ≡ R(x) ( 模 N(x) ) Return Back Next 9.5 循环码 若F(x) = N(x) Q(x) + R(x) 例 1 1 ( 1) 4 2 2 3 x + x + x + x + 模x + x x 1 x x 1 3 4 2 + + + x + x 4 1 2 x + x + 码多项式系数仍 按模2运算；其减 法以加法代替
95循环码 选 在循环码中,若T(x)是一个长为n的许用码 组,则xiT(x)在按模x+1运算下,也是一个许 用码组。 即若x·7(x)=T(x)(模x"+1) 则T'(x)也是一个许用码组。 在循环码中,一个(n,k)码有2k个不同码组 T(x=ax+a,x++a,x+a 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 在循环码中，若T(x)是一个长为 n 的许用码 组，则 x i T(x) 在按模 x n +1 运算下，也是一个许 用码组。 9.5 循环码 即若 则 T’(x)也是一个许用码组。 ( ) ( ) ( +1) i n x T x T x 模x 在循环码中，一个（n，k）码有2 k个不同码组 1 0 2 2 1 1 T(x) a x a x a x a n n n = n + + + + − − − −
95循环码 选 3、循环码的生成矩阵 A a4 a3G 有了生成矩阵G,就可以由k个信息位得出整 个码组;若能找到k个线性无关的已知码组,就 能构成生成矩阵。 在循环码中,一个(n,k)码有2k个不同码 组。若g(x)表示其中前k-1位皆为“0”的码组, 则g(x),xg(x),x2g(x),…,xkg(x)都是线性 无关的码组,由此可以构成循环码的生成矩阵。 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.5 循环码 3、循环码的生成矩阵 有了生成矩阵G，就可以由 k个信息位得出整 个码组；若能找到 k 个线性无关的已知码组，就 能构成生成矩阵。 6 5 4 3 A = a a a a G 在循环码中，一个（n，k）码有 2 k 个不同码 组。若 g(x) 表示其中前 k-1 位皆为“0” 的码组， 则 g(x) ，xg(x) ，x 2g(x) ，…，x k-1g(x) 都是线性 无关的码组，由此可以构成循环码的生成矩阵
95循环码 选 在循环码中,除全0码外,再没有连续k位 均为“0”的码组,即连“0”的长度最多只能k-1 位。因此g(x)必须是一个常数项不为“0”的n-k 次多项式。 gx=a x"-k+ +∴·+a xg(x) g( GO) 生成多项 式 2g(x) g(x) 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 在循环码中，除全0码外，再没有连续 k 位 均为“0”的码组，即连“0”的长度最多只能k-1 位。因此 g(x) 必须是一个常数项不为“0”的 n-k 次多项式。 Return Back Next 9.5 循环码 0 1 1 g(x) a x a x a n k n k n k = n k + + + − − − − − − 生成多项 式 = − − ( ) ( ) ( ) ( ) ( ) 2 1 g x xg x x g x x g x G x k k
95循环码 选 假如输入信息码元m1mk2…m,则循 环码组: 7(x)=(m1m12…91)G(x =(m1x2+m12x2+…+m0)g(x) 所有码多项式T(x)都可被g(x)整除,且 任一次数不大于k-1的多项式乘g(x)都是码多 项式。 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 ( ) ( ) 0 2 2 1 1 m x m x m g x k k k = k + + + − − − − Return Back Next 假如输入信息码元 mk-1 mk-2 … m0 ，则循 环码组： 9.5 循环码 ( ) ( ) ( ) 1 2 0 T x m m m G x = k− k− 所有码多项式 T(x) 都可被 g(x) 整除，且 任一次数不大于 k-1 的多项式乘 g(x)都是码多 项式
95循环码 选 4、任一(n,k)循环码的生成多项式的寻找 T()=h((x) 又g(x)为一个码组,故xg(x)在模x+1运算 下也为一码组,故可写成 x“g(x x"+1=9(x)+ x"+1 xg(x)=x"+1+T(x) x"+l=xg(x)+h(x)g(x)=g(xlxth() 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.5 循环码 1 ( ) ( ) 1 ( ) + = + + n n k x T x Q x x x g x =1 又 g(x)为一个码组， 故 x kg(x) 在模 x n+1 运算 下也为一码组，故可写成 ∵ T(x) = h(x) g(x) 4、任一（n，k）循环码的生成多项式的寻找 x g(x) x 1 T(x) k n = + + x 1 x g(x) h(x)g(x) g(x)[x h(x)] n k k + = + = +
95循环码 选 故g(x)是xn+1的一个n-k次因式,此即寻 找g(x)的方法。 例 x2+1=(x+1)(x3+x2+1)(x3+x+1) 都可作为(7,3)循环码的生成多项式 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 故 g(x) 是 x n+1 的一个 n – k 次因式，此即寻 找 g(x) 的方法。 9.5 循环码 1 ( 1)( 1)( 1) 7 3 2 3 x + = x + x + x + x + x + 都可作为(7,3)循环码的生成多项式 例：
95循环码 选 二、循环码的编、解码方法编码步骤 1、循环码的编码方法 (1)根据给定的(n,k)的值选定生成多项 式g(x),即从x+1的因子中选一n-k次多项式作 为g(x)。 (2)所有码多项式r(x)都可被g(x)整除,据 此对给定的信息码m(x)进行编码 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 二、循环码的编、解码方法编码步骤 （1）根据给定的（n，k）的值选定生成多项 式 g(x)，即从 x n+1 的因子中选一 n-k 次多项式作 为g(x)。 Return Back Next 9.5 循环码 1、循环码的编码方法 （2）所有码多项式T(x)都可被 g(x) 整除，据 此对给定的信息码 m(x) 进行编码
95循环码 选 步骤: (1)xm(x)相当于信息码后附加n-k个0 (2) m(x) 0(x)+ r(x) g(x) g(x) (3)(x)=x"m(x)+r(x) 例:给定(7,3)循环码的某一信息位为110, 试构造其码组T(x)。 解:因为m=110,则mx)=x2+x g(x)=x4+x2+x+1 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.5 循环码 ( ) ( ) ( ) ( ) ( ) (2) g x r x Q x g x x m x n k = + − (3)T(x) x m(x) r(x) n k = + − (1)x m(x) n−k 相当于信息码后附加n-k个0 步骤： 例：给定（7，3）循环码的某一信息位为110， 试构造其码组T(x)。 解：因为m=110，则 m(x)=x 2+x g(x)= x 4 +x 2+ x+1