第十一章 循环码

11-1 循环码的描述

11-1-1 循环码的定义

定义 11.1 一个(n, k)线性分组码C，若它一个码矢的每一循环移位都是C的一个码字，则C是一个循环码

定理 11.1 设循环码的码多项式为 $v(x)=v_{n-1}{x}^{n-1}+v_{n-2}{x}^{n-2}+\dots +v_{1}x+v_0$, 循环移位 $i$ 次后 的码多项式为 $v^{(i)}(x)$, 则 $v^{(i)}(x)$ 是 $x^n+1$ 除多项式 $x^{i}v(x)$ 所得之余式。

定理 11.2 循环码C中，次数最低的非零码多项式是惟一的。

定理 11.3 令 $g(x)=x^r+g_{r-1}{x}^{r-1}+\cdots +g_{1}x+g_0$ 是 $(\mathbf{n},\mathbf{k})$ 循环码 C中最低次数的非零码多项式, 则常数项 $g_0$ 必为 1 。

定理 11.4 令 $g(x)=x^r+g_{r-1}{x}^{r-1}+\cdots +g_{1}x+1$ 是一个 $(\mathbf{n},\mathbf{k})$ 循环码 C中次数最低的非零码多项式, 一个次数等于或小于 $\mathbf{n}-1$ 次 的二元多项式, 当且仅当它是 $g(x)$ 的倍式时才是码多项式。

$$v(x)=u(x)g(x)$$

定理 11. 4 说明，一个次数等于或小于 $n–1$ 次的二元多项式是码多项式的充要条件为它是 $g(x)$ 的倍式。

定理 11.5 $(n,k)$ 循环码的生成多项式 $g(x)$ 是 $x^n+1$ 的因式

定理 11.6 若 $g(x)$ 是一个 $(n-k)$ 次多项式且是 $x^n+1$ 的因式，则 $g(x)$ 生成一个 $(n,k)$ 循环码。

任何一个码字都是 $c(x)=g(x)\cdot x^m\mathrm{mod}(x^n+1)$

11-1-3 生成矩阵和一致校验矩阵

若待编码的消息用行矩阵表示为 $$\mathbf{U}=\left[\begin{array}{lllll}{u}_{k-1}& u_{k-2}& \dots & u_1& u_0\end{array}\right]$$ 则非系统循环码的编码输出为 $$\mathbf{C}=\mathbf{UG}$$ 由 $\mathbf{G}\cdot {\mathbf{H}}^{\mathrm{T}}=0$ 可得非系统形式的一致校验矩阵 $\mathbf{H}$

系统码

系统形式的循环码生成矩阵，由非系统形式的生成矩阵通过行变换而获得

对所有的 $i=0,1,\dots ,k-1$, 用生成多项式 $g(x)$ 除 $x^{n-k+i}$，有 $$x^{n-k+i}=a_i(x)g(x)+b_i(x)$$ 其中 ${\mathbf{b}}_i(\mathbf{x})$ 是余式，表示为 $$b_i(x)=b_{i,n-k-1}{x}_{i,n-k-1}+\dots +b_{i,1}x+b_{i,0}$$ 因此$x^{n-k+i}+b_i(x)$ 是 $g(x)$ 的倍式，即码多项式。系统形式的生成多项式为 $$\mathbf{G}=\left[\begin{array}{cccccccc}1& 0& \cdots & 0& b_{0,n-k-1}& \cdots & b_{01}& b_{00}\\ 0& 1& \cdots & 0& b_{1,n-k-1}& \cdots & b_{11}& b_{10}\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & \\ 0& 0& \cdots & 1& b_{k-1,n-k-1}& \cdots & b_{k-1,1}& b_{k-1,0}\end{array}\right]$$

11-2 循环码的编码和译码

11-2-1 循环码的编码

$$C(x)=g(x)u(x)$$

系统循环码： 定理 $11.7$ 设循环码的生成多项式为, 待编码的消息多项式为 $u(x),g(x)$ 和 $u(x)$ 的次数分别是 $r$ 和 $k$, 则 $$C(x)=u(x)\cdot x^{n-k}+{u(x)\cdot x^{n-k}|}_{\mathrm{mod}g(x)}$$ 为码多项式, 用此方法编得的码字为系统循环码。

11-2-2 循环码的译码和错误检测

伴随多项式 $s(x)$ $$r(x)=a(x)g(x)+s(x)$$

定理 11.8 令 $s(x)$ 是接收多项式 $r(x)=r_{n-1}{x}^{n-1}+r_{n-2}{x}^{n-2}+\dots +r_0$ 的伴随多项式, 则用生成多项式 $g(x)$ 除 $xs(x)$ 所得之余式 $s^{(1)}(x)$, 就是 $r(x)$ 循环移位一次 $r^{(1)}(x)$ 的伴随式。

推论 用生成多项式 $g(x)$ 除 $x^{i}s(x)$ 所得的余式 $s^{(i)}(x)$, 是 $r$ $(x)$ 的第 $i$ 次循环移位 $r^{(i)}(x)$ 的伴随式。