关于信息:循环码的编码译码与循环冗余校验

本专栏蕴含信息论与编码的外围常识，按知识点组织，可作为教学或学习的参考。markdown 版本已归档至【Github 仓库：https://github.com/timerring/information-theory】或者【AIShareLab】回复 信息论 获取。

循环码编码用硬件实现时, 可用除法电路来实现。除法电路次要是由移位寄存器和模 2 加法器组成。

$$
\begin{array}{c}
r(x)=x^{n-k} u(x) \bmod g(x) \\
c(x)=x^{n-k} u(x)+r(x)
\end{array}
$$

码多项式中 x 的幂次代表移位的次数。

例如图给出 (7,3) 循环码编码器的组成。$g(x)=1+x+x^{2}+x^{4}$。图中对应 g(x) 有 4 级移位寄存器, 别离用 $D_{1}, D_{2}, D_{3} , D_{4}$ 示意。

g(x) 多项式中系数是 1 或 0 示意该位上反馈线的有无, 信号 $\Phi_{1}$, $\quad \Phi_{2}$ , 管制门电路 1 -3。当信息位输出时, 管制信号使门 1, 门 3 关上, 门 2 敞开, 输出信息码元一方面送除法器进行运算, 另一方面间接输入。

在信息位全副输出除法器之后, 管制信号使门 1, 3 敞开, 门 2 关上, 这时寄存器通过门 2 间接输入, 将寄位寄存器中的除法余项顺次取出, 即将监督码元附加在信息码元之后。则编出的码组后面是原来 $\mathbf{k}$ 个信息码元，前面是 (n-k) 个监督码元，从而失去零碎分组码。

为便于了解，下表给出这一编码器的工作过程。这里设信息码元为 110，编出的监督码元为 0101，循环码组为 1100101。

循环码的译码电路如图所示。

无错: $y(x)_{\bmod g(x)}=0$ ;

有错: $y(x)_{\bmod g(x)} \neq 0 $。

收、发码字与谬误图样多项式关系:

谬误图样: $\overrightarrow{\boldsymbol{e}}=\left[e_{0} e_{1} \cdots e_{n-1}\right] \Rightarrow e(x)$;

接管码字: $\mathrm{y}(x)=c(x) \bigoplus e(x)$

随同式译码：

(1)对最可能呈现的谬误图样计算相应的随同多项式: $S(x)=e(x) \bmod g(x)$ , 并结构随同式一谬误图样表 $[(\vec{S}, \vec{e})]$ ;

(2)依据接管码式计算随同多项式; $S(x)=y(x) \bmod g(x)$

(3)由随同式 $\vec{S}$ 查谬误图样 $\vec{e}$ ;

(4)对接管码字进行纠错, 失去发送码字的估计值:

$$
\hat{\mathbf{c}}=\overrightarrow{\mathbf{y}}-\overrightarrow{\mathbf{e}}=\overrightarrow{\mathbf{y}} \oplus \overrightarrow{\mathbf{e}}
$$

(5)循环码能够用移位寄存器实现随同式译码

适宜于检测谬误, 具备很强的检错能力, 且实现简略。

CRC 检错性能如下:

能够检测出突发长度 $<\boldsymbol{n}-\boldsymbol{k}+\boldsymbol{1}$ 的突发谬误
大部分突发长度 $=\boldsymbol{n}-\boldsymbol{k}+1$ 的谬误能够检测出, 其中不可检出的谬误占 $2^{-(n-k-1)}$ ;
大部分突发长度 $>\boldsymbol{n}-\boldsymbol{k}+\mathbf{1}$ 的谬误能够检测出, 其中不可检出的谬误占 $2^{-(n-k)}$ ;
能够检测出所有与许用码字码距 $\leq d_{\min}-1$ 的谬误;
能够检测出所有奇数个谬误。
CRC 不肯定是循环码。然而码多项式肯定是生成多项式的倍式。

罕用的 CRC 冗余校验码生成方程

CRC-16 $g(x)=X^{16}+X^{15}+X^{2}+1$ (USB)

CRC-ITU $g(x)=X^{16}+X^{12}+X^{5}+1$ (HDLC, PPP)

CRC-32 $g(x)=X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+ X^{11}+X^{10}+X^{8}+X^{7}+X^{5}+X^{4}+X^{2}+X+1$ (LANS,
PPP)

留神:

探讨：若已知 CRC 生成多项式 g(x)，要信息位为 $\mathrm{k}$，需退出 r 位校验位，如何编码?

例: 若 $g(x)=x^{4}+x+1$，已知数据信息为 110010110，现要对其进行 CRC 编码，如何编? 若收到的码字为 1100101001010，请问是否出错?

r=4 ; $\mathrm{k}$=9

码多项式的最高阶次为 12 .

$$
\begin{array}{c}
x^{4} u(x)=x^{12}+x^{11}+x^{8}+x^{6}+x^{5} \\
r(x)=x^{4} u(x) \bmod g(x)=x^{3}+x^{2}+x
\end{array}
$$

故编码为 1100101101110，码字 1100101001010，有错, $r(x)=x \neq 0$

参考文献：

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

循环码的编码