第五章循环码 一、 循环码的数学概念 ●循环码：若线性码C=[n,满足(co,c,,cm2,cn-)∈C(cn-,cm,c,,cn-2)∈C,则称为循环码。 数学上，码字循环是码多项式乘x(左循环或x(右循环)取模x”1的余式.循环码的数学定义是模 ”1剩余类环中由一个mk次首一多项式x)生成的主理想（定理1,2）.可证（定理3），gxx”1;反 过来，由x”1的任一r次因式生成的模-1剩余类环的主理想必是一个[n,n-循环码. 循环码之所以重要，是因为只要找到仅对某位进行操作（如大数逻辑译码）的方法，就可以通过循环移位 实现对所有的位进行操作。注意」 1)循环码的码字多项式是gx)的倍式摸x”-1的余式，实际上是码字多项式gx)循环移位的线性组合 2)循环码有可能有多个循环模式（至少有g(x)和0两个），如下图是由gx)=x3+x+1生成的循环码. 0001101gx) 00000000·gx) 0010111(x+1)gx) 1000110 0011010 1001011 0101110 0100011 0110100 1100101 1011100 1010001 1110010 1111111 1101000 0111001 (x3+x+1)g(x) 二、循环码的校验矩阵H和生成矩阵G 由于g(x),xgx),,xk-1gx)是k个线性无关的码字，所以生成矩阵G为 「x-g(x) G= (1) xg(x) 8(x) 设心1Fx)h,x)=∑h,x称为码校验多项式，其反多项式h田)=∑h,x，取 0 x-k-h'(x) H= (2) xh"(x) h(x) 可证HG=O所以(2)确定的H是校验矩阵。 (I)式和(2)式确定G的H不是标准形式。系统码的码字应有C(x)=(x)-*+x)的形式，其中m(x)是信 息多项式，x)是监督多项式.因为C()=m(xx-k+(x)=0(mod g(x),所以(x)三-m(xr-k(mod g(x), 取m(x)=x(=1,2,,),可得相应的监督多项式rx)归-m(x)x-k=rxa-k=x(mod g(x))(=1,2,,,从而 可求得构成系统码生成矩阵的k个码字，C(x)=m:(x-k+n(x)(i=1,2,,),因此G的标准形式为 (x) G 其中，(x)=-x(mod g(x)(=1,2,。 k-(x) (x) 由G的标准形式可轻易求出H的标准形式
一、 循环码的数学概念 ⚫ 循环码：若线性码 C = [n,k]满足（c0, c1, ..., cn-2, cn-1） C: （cn-1, c0, c1, ..., cn-2） C, 则称为循环码。 数学上, 码字循环是码多项式乘 x (左循环)或 x -1 (右循环) 取模 x n -1 的余式. 循环码的数学定义是模 x n -1 剩余类环中由一个 n-k 次首一多项式 g(x)生成的主理想（定理 1,2）. 可证（定理 3）, g(x)| x n -1; 反 过来, 由 x n -1 的任一 r 次因式生成的模 x n -1 剩余类环的主理想必是一个[n, n-r]循环码. 循环码之所以重要，是因为只要找到仅对某位进行操作(如大数逻辑译码)的方法，就可以通过循环移位 实现对所有的位进行操作。注意: 1) 循环码的码字多项式是 g(x)的倍式摸 x n -1 的余式, 实际上是码字多项式 g(x)循环移位的线性组合. 2) 循环码有可能有多个循环模式(至少有 g (x) 和 0 两个), 如下图是由 g(x)=x 3 +x 2 +1 生成的循环码. 二、循环码的校验矩阵 H 和生成矩阵 G 由于 g(x), x g(x), ..., x k-1 g(x)是 k 个线性无关的码字, 所以生成矩阵 G 为 G = − ( ) ( ) ( ) g x xg x x g x k 1 (1) 设 x n -1=g(x)h(x), h(x) = = k i i i h x 0 称为码校验多项式, 其反多项式 h * (x) = = − k i k i i h x 0 ，取 H= − − ( ) ( ) ( ) * * * h x xh x x h x n k 1 , (2) 可证 HGT=0, 所以(2)确定的 H 是校验矩阵。 (1)式和(2)式确定 G 的 H 不是标准形式。系统码的码字应有 C(x)=m(x)x n-k+r(x)的形式，其中 m(x)是信 息多项式，r(x)是监督多项式. 因为 C (x) = m(x)x n-k+r(x)0 (mod g(x))，所以 r(x) - m(x)x n-k (mod g(x))， 取mi(x)=x k-i (i=1,2,...,k), 可得相应的监督多项式ri(x) - mi(x)x n-k x k-i x n-k x n-i (mod g(x)) (i=1,2,...,k), 从而 可求得构成系统码生成矩阵的 k 个码字，Ci (x) = mi (x)x n-k+ri (x) (i=1,2,...,k)，因此 G 的标准形式为 G = − ( ) ( ) ( ) r x r x r x I k k k k 1 1 , 其中，ri(x) - x n-i (mod g(x)) (i=1,2,...,k)。 由 G 的标准形式可轻易求出 H 的标准形式. 0010111 (x+1)g(x) 0111001 0101110 1011100 1110010 1100101 1001011 0000000 0 • g(x) 0001101 g(x) 1101000 0011010 0110100 1010001 0100011 1000110 1111111 (x 3+x+1)g(x) 00
三、x”1的因式分解 由上面的分析可知，要构造一个Fg上[n,循环码，关键是要找到生成多项式g(x),而g(x)是-1的n-k 次因式.因此对1的因式分解是构造循环码的关键问题 ●当n=gm-1 从第四章可知，x9--1在Fg的扩展域F,={0,a,d…,a=上可分解为 x9-1=(xamx)…(xa4-),把F,上的元素分成不同的共轭根系（设为s个，设第k个共轭根 系的共轭根为：%w以w,,w“,1为使w=最小的正整数（如果g为素数，n为：的阶 I为q对模n的方次数)，则含这个共轭根系的因子的乘积xw)(xw)(cw)(cw9)是F,上的 1次素多项式m(m(x是w%,w3w,,w4“的最小多项式)，因此xP-1=m() 特别地，当n=2m-l,n-k=m(g(x)的次数为m)时，可查表求F,。上的m次本原多项式p(x),由第四章定 理20（课本定理4.6.7，pl44)可知，p(x)”-1,可以证明（参看华工出版社R.E.Blahut《差错控制码的理论 与实践》，p.85),由p(x)生成的循环码-3，因此是一个汉明码 ●当n≠m-l,但nlgm-1,可在F。中找阶为n的元素B则生成的n阶循环群含有x-l=0的全部根 四、在扩展域中描述和构造循环码 在扩展域中研究问题往往可以帮助理解问题和简化问题的复杂性.在扩展域中描述和构造循环码最简 单的例子是把F,.的所有非0元素组成矩阵a2.a4-1]然后把每一元素转化为F2上的m重从而可得F2 上的矩阵，它是[2m-1,2m1-m,3]汉明码的校验矩阵 ●Fg上的循环码的生成多项式gx)在最小分裂域F,上的根为a,a,,k(设gx)在F,上无重根，其 充要条件是(nq广1)，则Fg上n维矢重C是码字多项式的充要条件是HC=0,其中， g …01 -2 H- a, … (计算在F,上进行)，设H中的g0=1,,nk=l,,m)的多项式表示为 -2 Rr,用，上的m重（以A。代替4，则H化为F,的矩阵F,但尚不是监督矩阵，因为 i=0 H内可能含有线性相关的行.可证，同一共轭根系分裂出的行之间是线性相关的，所以，同一共轭根 系的共轭根中，只保留其中之一即可.这样处理后的矩阵仍可能有线性相关的行（如全0行），去掉后得 到的n-xn矩阵就是监督矩阵 五、缩短循环码 ●缩短循环码是在循环码[n,风去掉i位信息位得到的[-i,k码，技术上，去掉的i位信息位可看作是O.这 样缩短循环码可认为是循环码的子集，从而可利用循环码的编译码电路.几何上，缩短循环码[-i,k 是循环码n,的码空间与-维超平面的交集，所以码的最小距离不会缩小，纠错能力不会下降
三、x n -1 的因式分解 由上面的分析可知, 要构造一个 Fq 上[n, k]循环码, 关键是要找到生成多项式 g(x), 而 g(x)是 x n -1 的 n-k 次因式. 因此对 x n -1 的因式分解是构造循环码的关键问题. ⚫ 当 n = q m-1 从第四章可知， 1 1 − − m q x 在 Fq 的扩展域 m q F ={0，， 2 , ... , −1 m q =1}上可分解为 1 1 − − m q x =(x-)(x- 2 ) ......(x- −1 m q ), 把 m q F 上的元素分成不同的共轭根系(设为 s 个), 设第 k 个共轭根 系的共轭根为: wk, wk q , 2 q wk , ... , l −1 q wk , l 为使 l −1 q wk = wk 最小的正整数(如果 q 为素数, n 为 wk 的阶, l 为 q 对模 n 的方次数), 则含这个共轭根系的因子的乘积(x- wk) (x- wk q ) (x- 2 q wk )...(xl −1 q wk )是 Fq 上的 l 次素多项式 mk(x) ( mk(x)是 wk, wk q , 2 q wk , ... , l −1 q wk 的最小多项式), 因此 1 1 − − m p x == s k k m x 1 ( ) . 特别地, 当 n = 2 m -1, n -k =m (g(x)的次数为 m)时, 可查表求 F m 2 上的 m 次本原多项式 p(x), 由第四章定 理 20(课本定理 4.6.7, p144)可知, p(x)|x n -1, 可以证明(参看华工出版社 R.E. Blahut 《差错控制码的理论 与实践》，p.85), 由 p(x)生成的循环码 d=3, 因此是一个汉明码. ⚫ 当 n q m-1, 但 n |q m-1, 可在 m q F 中找阶为 n 的元素, 则生成的 n 阶循环群含有 x n -1=0 的全部根. 四、在扩展域中描述和构造循环码 在扩展域中研究问题往往可以帮助理解问题和简化问题的复杂性, 在扩展域中描述和构造循环码最简 单的例子是把 F m 2 的所有非 0 元素组成矩阵[ 2 ... −1 m q ]然后把每一元素转化为 F2 上的 m 重从而可得F2 上的矩阵,它是[2m -1, 2 m -1-m,3]汉明码的校验矩阵. ⚫ Fq 上的循环码的生成多项式 g(x)在最小分裂域 m q F 上的根为1, 2, ... , n-k (设 g(x)在 m q F 上无重根, 其 充要条件是 (n, q)=1), 则 Fq 上 n 维矢重 C 是码 字 多 项 式的 充 要 条 件是 HCT=0, 其 中, H= 1 1 1 1 2 2 2 2 1 2 1 2 1 1 1 n k n n k n n k n n n n − − − − − − − − − (计算在 m q F 上进行), 设 H 中的j t (j = 1, ..., n-k, t=1, ..., n)的多项式表示为 − = 1 0 m i i i x , 用 Fq 上的 m 重 (m-1m-2... ) T代替j t , 则 H 化为 Fq 的矩阵 H , 但尚不是监督矩阵, 因为 H内可能含有线性相关的行. 可证, 同一共轭根系分裂出的行之间是线性相关的, 所以, 同一共轭根 系的共轭根中, 只保留其中之一即可. 这样处理后的矩阵仍可能有线性相关的行(如全 0 行), 去掉后得 到的 n-kn 矩阵就是监督矩阵. 五、缩短循环码 ⚫ 缩短循环码是在循环码[n, k]去掉i位信息位得到的[n-i,k-i]码, 技术上, 去掉的i位信息位可看作是0. 这 样缩短循环码可认为是循环码的子集, 从而可利用循环码的编译码电路. 几何上, 缩短循环码[n-i,k-i] 是循环码[n, k]的码空间与 n-i 维超平面的交集, 所以码的最小距离不会缩小, 纠错能力不会下降
●缩短循环码的生成矩阵和监督矩阵 缩短循环码引-i,k的生成矩阵G是循环码[n的生成矩阵G去掉前i行和前i列而成，而缩短循环码 [n-i,k的监督矩阵H是循环码[n,闷的监督矩阵H去掉前i列而成 六、循环码的编码电路 Fg上的循环码的编码电路是如何从信息多项式(x),生成码多项式C(x),因此编码电路不是构成整个码 空间，而是对应于信息多项式的心个码字 ●基于g(x)的n-k级编码器 1.非系统码：乘g(x)电路 原理： C(x)=m(x)g)(modx”-l),若m(x)sk则C(x)=Mx)g(x).因此可把m(x)作为信息多项 式，这样，编码电路实际上是一个乘gx)电路 C(x) 90 9 m(x) 2.系统码：除g(x)电路 原理： C(x)=mx)r-+x)=0(mod g(x)》一x)=-m(x)x-*(mod g(x)).因此可先把m(x)移动rk 位得m(x)x-*然后除-g(x)取余，再加上m(x)x- 时钟 n+k C(x) m(x) ●基于h(x)的k级编码器 原理：因g(x)为首一多项式，h(x)=(x-)g(x)亦为首一多项式，由(1)式可得 h。…h-1 0…… 0 0h。…h-10 0 0 h…hk-lhs=lLco 因此有cnk1=-(h0cm-+h1Cn-2++hk.cm),即由信息位cal…cnk求出第一个校验位cn-k1 Cn-k2=-(hocm-2+h1Cm-+.+hk1Cmk.),即由信息位cm-2.Cm-k及第一个校验位Cm-k1求出第二个校 验位cn-kl Co=-(hocg+hick+...+hk-ic), 即由ck.9及（有可能是信息位也有可能是校验位）求最后 一个校验位c0 k n 时钟 m() .C(x)
⚫ 缩短循环码的生成矩阵和监督矩阵 缩短循环码[n-i,k-i]的生成矩阵 G是循环码[n, k]的生成矩阵 G 去掉前 i 行和前 i 列而成; 而缩短循环码 [n-i,k-i]的监督矩阵 H是循环码[n, k]的监督矩阵 H 去掉前 i 列而成. 六、循环码的编码电路 Fq 上的循环码的编码电路是如何从信息多项式 m(x),生成码多项式 C(x), 因此编码电路不是构成整个码 空间, 而是对应于信息多项式的 q k个码字. ⚫ 基于 g(x)的 n-k 级编码器 1. 非系统码: 乘 g(x)电路 原理: C(x) m(x)g(x) (mod x n -1), 若m(x),k, 则 C(x) = m(x)g(x). 因此可把 m(x)作为信息多项 式, 这样,编码电路实际上是一个乘 g(x)电路. + g0 g1 gn-k-1 + gn-k ....... + m(x) C(x) 2. 系统码: 除 g(x)电路 原理: C(x) m(x)x n-k+r(x) 0 (mod g(x)) r(x) - m(x)x n-k (mod g(x)). 因此可先把 m(x)移动 n-k 位得 m(x)x n-k然后除-g(x)取余, 再加上 m(x)x n-k + g0 g1 gn-k-1 + - gn-k -1 ....... + m(x) C(x) 0 k n n+k 时 钟 ⚫ 基于 h(x)的 k 级编码器 原理: 因 g(x)为首一多项式, h(x)=(x n-1 )/g(x)亦为首一多项式, 由(1)式可得 = − − − − − 0 2 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 c c c h h h h h h h n n k k k k =0 因此有 cn-k-1 = -( h0 cn-1+ h 1cn-2+...+ h k-1cn-k) , 即由信息位 cn-1... cn-k求出第一个校验位 cn-k-1 cn-k-2 = -( h0 cn-2+ h 1cn-3+...+ h k-1cn-k-1) , 即由信息位 cn-2... cn-k及第一个校验位 cn-k-1 求出第二个校 验位 cn-k-1 ... ... ... .... c0 = -( h0 ck+ h 1ck-1+...+ h k-1c1), 即由ck... c1 及(有可能是信息位也有可能是校验位)求最后 一个校验位 c0 + - hk -1 ....... m(x) C(x) 0 k n 时 钟 + - hk -2 + - h1 - h0 ....... + n+k 2n