循环码的特点与多项式描述

文章目录

• 循环码
• • 循环码的特点
  • 基本概念
  • 循环码的多项式描述

循环码

能够识记循环码的基本概念;

能够说明循环码生成多项式的特点;

能够应用多项式运算完成循环码（系统型和非系统型)的编译码;

能根据生成多项式求出循环码的生成矩阵（系统型和非系统型）;

能够解释循环码的编译码电路;

了解循环冗余校验(CRC) ，BCH和RS三种线性循环码

循环码的特点

1.可以用线性反馈移位寄存器很容易地实现编码和伴随式计算;

2.由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法。

由于循环码具有很多的良好性质，所以它在理论和实践中都很重要。

基本概念

定义: 设 C \mathrm{C} C 是某 ( n , k \boldsymbol{n}, \boldsymbol{k} n,k) 线性分组码的码字集合, 如果对任何
c = ( c n − 1 , c n − 2 , ⋯   , c 0 ) ∈ C \mathbf{c}=(c_{n-1}, c_{n-2}, \cdots, c_{0}) \in \mathbf{C} c=(cn−1​,cn−2​,⋯,c0​)∈C
它的循环移位(左移)
c ( 1 ) = ( c n − 2 , c n − 3 , ⋯   , c 0 , c n − 1 ) \mathbf{c}^{(1)}=(c_{n-2}, c_{n-3}, \cdots, c_{0}, c_{n-1}) c(1)=(cn−2​,cn−3​,⋯,c0​,cn−1​)
也属于 C \mathrm{C} C , 则称该 ( n , k \boldsymbol{n}, \boldsymbol{k} n,k) 码为循环码。

同理, 左移 i 位
c ( i ) = ( c n − i − 1 , c n − i − 2 , ⋯   , c 0 , c n − 1 , … , c n − i ) \mathbf{c}^{(i)}=(c_{n-i-1}, c_{n-i-2}, \cdots, c_{0}, c_{n-1}, \ldots, c_{n-i}) c(i)=(cn−i−1​,cn−i−2​,⋯,c0​,cn−1​,…,cn−i​)
仍是这个循环码的一个码字。

循环码的多项式描述

对任意一个长为 n n n 的码字
c = ( c n − 1 , c n − 2 , ⋯   , c 1 , c 0 ) ∈ C \mathbf{c}=(c_{n-1}, c_{n-2}, \cdots, c_{1}, c_{0}) \in \mathbf{C} c=(cn−1​,cn−2​,⋯,c1​,c0​)∈C
可用一多项式来表示, 称其为码多项式:
c ( x ) = c n − 1 x n − 1 + c n − 2 x n − 2 + ⋯ + c 1 x + c 0 c(x)=c_{n-1} x^{n-1}+c_{n-2} x^{n-2}+\cdots+c_{1} x+c_{0} c(x)=cn−1​xn−1+cn−2​xn−2+⋯+c1​x+c0​

C = ( c n − 1 , c n − 2 , … , c 1 , c 0 ) < C ( x ) = c n − 1 x n − 1 + c n − 2 x n − 2 + … + c 1 x + c 0 \begin{array}{l} \mathrm{C}=(c_{n-1}, c_{n-2}, \ldots, c_{1}, c_{0}) \\ \lt C(x)=c_{n-1} x^{n-1}+c_{n-2} x^{n-2}+\ldots+c_{1} x+c_{0} \end{array} C=(cn−1​,cn−2​,…,c1​,c0​)<C(x)=cn−1​xn−1+cn−2​xn−2+…+c1​x+c0​​

c i \boldsymbol{c}_{i} ci​ 是多项式的系数, 一切系数的运算均是在 G F ( 2 ) \boldsymbol{G F}(2) GF(2) 上的运算。

多项式的阶数一系数不为 0 的 x 的最高幂次:
deg ⁡ c ( x ) ≤ n − 1 \operatorname{deg} c(x) \leq n-1 degc(x)≤n−1

多项式的加法和乘法运算 GF (2)

加法
u ( x ) = u 2 x 2 + u 1 x + u 0 , g ( x ) = g 1 x + g 0 u ( x ) + g ( x ) = ( u 2 + 0 ) x 2 + ( u 1 + g 1 ) x + ( u 0 + g 0 ) \begin{array}{l} u(x)=u_{2} x^{2}+u_{1} x+u_{0}, g(x)=g_{1} x+g_{0} \\ u(x)+g(x)=(u_{2}+0) x^{2}+(u_{1}+g_{1}) x+(u_{0}+g_{0}) \end{array} u(x)=u2​x2+u1​x+u0​,g(x)=g1​x+g0​u(x)+g(x)=(u2​+0)x2+(u1​+g1​)x+(u0​+g0​)​
乘法
u ( x ) g ( x ) = u 2 g 1 x 3 + ( u 2 g 0 + u 1 g 1 ) x 2 + ( u 1 g 0 + u 0 g 1 ) x + u 0 g 0 \begin{array}{l} u(x) g(x) \\ =u_{2} g_{1} x^{3}+(u_{2} g_{0}+u_{1} g_{1}) x^{2}+(u_{1} g_{0}+u_{0} g_{1}) x+u_{0} g_{0} \end{array} u(x)g(x)=u2​g1​x3+(u2​g0​+u1​g1​)x2+(u1​g0​+u0​g1​)x+u0​g0​​
写成矩阵形式
c = ( u 2 , u 1 , u 0 ) ( g 1 g 0 0 0 0 g 1 g 0 0 0 0 g 1 g 0 ) = ( u 2 g 1 , ( u 2 g 0 + u 1 g 1 ) , ( u 1 g 0 + u 0 g 1 ) , u 0 g 0 ) c=(u_{2}, u_{1}, u_{0})(\begin{array}{llll} g_{1} & g_{0} & 0 & 0 \\ 0 & g_{1} & g_{0} & 0 \\ 0 & 0 & g_{1} & g_{0} \end{array})=(u_{2} g_{1},(u_{2} g_{0}+u_{1} g_{1}),(u_{1} g_{0}+u_{0} g_{1}), u_{0} g_{0}) c=(u2​,u1​,u0​)(g1​00​g0​g1​0​0g0​g1​​00g0​​)=(u2​g1​,(u2​g0​+u1​g1​),(u1​g0​+u0​g1​),u0​g0​)
例:
( x 6 + x 2 + 1 ) + ( x 3 + x 2 ) = x 6 + x 3 + ( 1 + 1 ) x 2 + 1 = x 6 + x 3 + 1 \begin{array}{l} (x^{6}+x^{2}+1)+(x^{3}+x^{2})\\ =x^{6}+x^{3}+(1+1) x^{2}+1 \\ =x^{6}+x^{3}+1 \end{array} (x6+x2+1)+(x3+x2)=x6+x3+(1+1)x2+1=x6+x3+1​
基本多项式关系
( x + 1 ) 2 = x 2 + 1 ( x + 1 ) ( x 3 + x + 1 ) ( x 3 + x 2 + 1 ) = x 7 + 1 ( x + 1 ) ( x n − 1 + x n − 2 + ⋯ + x + 1 ) = x n + 1 \begin{array}{c} (x+1)^{2}=x^{2}+1 \\ (x+1)(x^{3}+x+1)(x^{3}+x^{2}+1)=x^{7}+1 \\ (x+1)(x^{n-1}+x^{n-2}+\cdots+x+1)=x^{n}+1 \end{array} (x+1)2=x2+1(x+1)(x3+x+1)(x3+x2+1)=x7+1(x+1)(xn−1+xn−2+⋯+x+1)=xn+1​

多项式的模运算

模 N \mathbf{N} N 运算： M / N = Q + R / N 0 ≤ R < N M / N=Q+R / N \quad 0 \leq R \lt N M/N=Q+R/N0≤R<N ; 其中 M, N 为 正 整数, Q \mathbf{Q} Q 为整数, 则在模 N \mathbf{N} N 运算下, 有 M ≡ R M \equiv \mathbf{R} M≡R （模 $\mathbf{N} $, 记为   m o d   N \bmod \mathbf{N} modN )

例 : 14 ≡ 2 (   m o d   12 ) 14 \equiv 2(\bmod 12) 14≡2(mod12), 1 + 1 = 2 ≡ 0 ( m o d 2 ) 1+1=2 \equiv 0 (mod 2) 1+1=2≡0(mod2), 3 + 2 = 5 ≡ 1 (   m o d   2 ) 3+2=5 \equiv 1(\bmod 2) 3+2=5≡1(mod2), 5 × 4 = 20 ≡ 0 (   m o d   2 ) 5 \times 4=20 \equiv 0(\bmod 2) 5×4=20≡0(mod2)

给定任意两个系数在 $G F(2) $ 上的多项式 a(x) 和 p(x) , 一定存在有唯一的多项式 Q(x) 和 r(x) , 使
a ( x ) = Q ( x ) p ( x ) + r ( x ) a(x)=Q(x) p(x)+r(x) a(x)=Q(x)p(x)+r(x)
称 Q(x) 是 a(x) 除以 p(x) 的商式, r(x) 是 a(x) 除以 p(x) 的余式， 在模 p(x) 运算下,
a ( x ) ≡ r ( x ) [   m o d   p ( x ) ] a(x) \equiv r(x) \quad[\bmod p(x)] a(x)≡r(x)[modp(x)]
记 a(x) 除以 p(x) 的余式为 r ( x ) = [ a ( x ) ]   m o d   p ( x ) r(x)=[a(x)] \bmod p(x) r(x)=[a(x)]modp(x) , 其中
0 ≤ deg ⁡ r ( x ) < deg ⁡ p ( x ) , 或  r ( x ) = 0 0 \leq \operatorname{deg} r(x)<\operatorname{deg} p(x) \text {, 或 } r(x)=0 0≤degr(x)<degp(x), 或 r(x)=0

对于任意多项式 a(x) 、 b(x) 和 p(x) , 可以证明

{ b ( x ) [ a ( x ) ]   m o d   p ( x ) }   m o d   p ( x ) = [ b ( x ) ⋅ a ( x ) ]   m o d   p ( x ) \{b(x)[a(x)]_{\bmod p(x)}\}_{\bmod p(x)}=[b(x) \cdot a(x)]_{\bmod p(x)} {b(x)[a(x)]modp(x)​}modp(x)​=[b(x)⋅a(x)]modp(x)​

若：

a ( x ) = x 7 + x + 1 b ( x ) = x 2 + 1 p ( x ) = x 3 + x + 1 \begin{array}{c} a(x)=x^{7}+x+1 \\ b(x)=x^{2}+1 \\ p(x)=x^{3}+x+1 \end{array} a(x)=x7+x+1b(x)=x2+1p(x)=x3+x+1​

请验证上式。余式=1。

对于 (n, k) 循环码, 若 c(x) 对应码字
c = ( c n − 1 , c n − 2 , … , c 1 , c 0 ) , \mathbf{c}=(c_{n-1}, c_{n-2}, \ldots, c_{1}, c_{0}), c=(cn−1​,cn−2​,…,c1​,c0​),

c ( 1 ) ( x ) \boldsymbol{c}^{(1)}(\boldsymbol{x}) c(1)(x) 对应 c \boldsymbol{c} c 的一次移位 c ( 1 ) = ( c n − 2 , … , c 1 , c 0 , c n − 1 ) \mathbf{c}^{(1)}=(c_{n-2}, \ldots, c_{1}, c_{0}, c_{n-1}) c(1)=(cn−2​,…,c1​,c0​,cn−1​) , 对 c ( i ) ( x ) c^{(i)}(x) c(i)(x) 对应 c 的 i 次移位 c ( i ) c^{(i)} c(i) ，则
c ( 1 ) ( x ) = [ x c ( x ) ]   m o d   ( x n + 1 ) c ( i ) ( x ) = [ x i c ( x ) ]   m o d   ( x n + 1 ) \begin{array}{c} c^{(1)}(x)=[x c(x)] \bmod (x^{n}+1) \\ c^{(i)}(x)=[x^{i} c(x)] \bmod (x^{n}+1) \end{array} c(1)(x)=[xc(x)]mod(xn+1)c(i)(x)=[xic(x)]mod(xn+1)​
证：

c ( 1 ) ( x ) = [ x c ( x ) ]   m o d   ( x n + 1 ) ,  c ( i ) ( x ) = [ x i c ( x ) ]   m o d   ( x n + 1 ) c ( x ) = c n − 1 x n − 1 + c n − 2 x n − 2 + ⋯ + c 1 x + c 0 x c ( x ) = c n − 1 x n + c n − 2 x n − 1 + ⋯ + c 1 x 2 + c 0 x = c n − 1 x n + c n − 2 x n − 1 + ⋯ + c 1 x 2 + c 0 x + c n − 1 + c n − 1 = c n − 1 ( x n + 1 ) + c ( 1 ) ( x ) a r r o w [ x c ( x ) ]   m o d   ( x n + 1 ) = [ c n − 1 ( x n + 1 ) + c ( 1 ) ( x ) ]   m o d   ( x n + 1 ) = c ( 1 ) ( x ) \begin{array}{l} c^{(1)}(x)=[x c(x)] \bmod (x^{n}+1) \text {, } \\ c^{(i)}(x)=[x^{i} c(x)] \bmod (x^{n}+1) \\ c(x)=c_{n-1} x^{n-1}+c_{n-2} x^{n-2}+\cdots+c_{1} x+c_{0} \\ x c(x)=c_{n-1} x^{n}+c_{n-2} x^{n-1}+\cdots+c_{1} x^{2}+c_{0} x \\ =c_{n-1} x^{n}+c_{n-2} x^{n-1}+\cdots+c_{1} x^{2}+c_{0} x+c_{n-1}+c_{n-1} \\ =c_{n-1}(x^{n}+1)+c^{(1)}(x) \\ arrow[x c(x)]_{\bmod (x^{n}+1)}=[c_{n-1}(x^{n}+1)+c^{(1)}(x)]_{\bmod (x^{n}+1)} \\ =c^{(1)}(x) \\ \end{array} c(1)(x)=[xc(x)]mod(xn+1), c(i)(x)=[xic(x)]mod(xn+1)c(x)=cn−1​xn−1+cn−2​xn−2+⋯+c1​x+c0​xc(x)=cn−1​xn+cn−2​xn−1+⋯+c1​x2+c0​x=cn−1​xn+cn−2​xn−1+⋯+c1​x2+c0​x+cn−1​+cn−1​=cn−1​(xn+1)+c(1)(x)arrow[xc(x)]mod(xn+1)​=[cn−1​(xn+1)+c(1)(x)]mod(xn+1)​=c(1)(x)​

参考文献：

1. Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
2. Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
3. 周炯槃. 通信原理（第3版）[M]. 北京：北京邮电大学出版社, 2008.
4. 樊昌信, 曹丽娜. 通信原理（第7版） [M]. 北京：国防工业出版社, 2012.