1. 简介
循环码是一类非常重要的线性码，其不仅在理论上有很好的代数结构，而且其编码和译码都可以很容易地利用线性移位寄存器来实现。一些重要的码，比如二元汉明码及其对偶码都等价于循环码。
2. 定义
设
C \subseteq V(n, q) 是一个线性码。如果
C 的任意一个码字的循环移位还是一个码字，即当
a_0 a_1 \cdots a_{n-1} \in C 时，
a_{n-1} a_0 a_1 \cdots a_{n-2} \in C，则称
C 是一个循环码。
3. 性质
令
R_n = F_q[x] / \langle x^n - 1 \rangle，其中
F_q 表示
q 元域
GF(q)。显然，
V(n, q) 中的向量与
R_n 中的多项式之间存在着一个自然的一一对应关系：
a_0 a_1 \cdots a_{n-1} \leftrightarrow a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}
为方便起见，将
V(n, q) 中的向量
a_0 a_1 \cdots a_{n-1} 与
R_n 中的
n-1 次多项式
a(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1} 看作是相同的。
对应的多项式系数依次从低次项到高次项。
C \subseteq R_n 是循环码当且仅当
C 满足下述两个条件：
- 如果
a(x), b(x) \in C，则
a(x) + b(x) \in C；
- 如果
a(x) \in C，
r(x) \in R_n，则
r(x) a(x) \in C。
设
f(x) \in R_n，令
\langle f(x) \rangle = \{r(x) f(x) | r(x) \in R_n\}。显然
\langle f(x) \rangle 是由
f(x) 生成的多项式带幺交换环
R_n 的一个理想。
f(x) \in R_n，
\langle f(x) \rangle 是一个循环码。
称
\langle f(x) \rangle 为由
f(x) 生成的循环码。
C 是
R_n 中的一个循环码，
C \neq \{\boldsymbol{0}\}，则
C
中存在惟一一个具有最低次数并且首项系数为
1 的多项式
g(x)；
C = \langle g(x) \rangle；
g(x) 整除
x^n - 1，即
g(x) 是
x^n - 1 的因子。
4. 生成矩阵
C 是
R_n 中的一个循环码，
C \neq \{\boldsymbol{0}\}。
C 中次数最低并且首项系数为
1 的多项式
g(x) 称为循环码
C 的生成多项式。
g(x) = g_0 + g_1 x + \cdots + g_r x^r 是一个循环码
C \subseteq R_n 的生成多项式，则
g_0 \neq 0。
C \subseteq R_n 是一个循环码，其生成多项式为
g(x) = g_0 + g_1 x + \cdots + g_r x^r
\deg{(g(x))} = r，则
\dim{(C)} = n-r，并且
C 的生成矩阵为
\boldsymbol{G}=\left(\begin{array}{ccccccccc}
g_{0} & g_{1} & g_{2} & \cdots & g_{r} & 0 & 0 & \cdots & 0 \\
0 & g_{0} & g_{1} & g_{2} & \cdots & g_{r} & 0 & \cdots & 0 \\
0 & 0 & g_{0} & g_{1} & g_{2} & \cdots & g_{r} & \cdots & 0 \\
\vdots & \vdots & \ddots & \ddots & \ddots & \ddots & & \ddots & \vdots \\
0 & 0 & \cdots & 0 & g_{0} & g_{1} & g_{2} & \cdots & g_{r}
\end{array}\right)
易知
C 是一个
q 元
[n, n-r] 循环码。
5. 校验矩阵
设
C \subseteq R_n 是一个循环码，其生成多项式为
g(x)，
\deg{(g(x))} = r。由定理三可知，存在
h(x) \in R_n，使得
x^n - 1 = h(x) g(x)
因为
g(x) 的首项系数为
1，所以
h(x) 的首项系数也为
1，并且
\deg{(h(x))} = n-r。称
h(x) 为循环码
C 的校验多项式。
C \subseteq R_n 是一个循环码，其生成多项式为
g(x)，校验多项式为
h(x)，则对任意
c(x) \in R_n，
c(x) 是
C 的一个码字当且仅当
c(x) h(x) = 0。
C \subseteq R_n 是一个
q 元
[n, n-r] 循环码，其校验多项式为
h(x) = h_0 + h_1 x + \cdots + h_{n-r} x^{n-r}
则
C
的校验矩阵为
\boldsymbol{H}=\left(\begin{array}{ccccccccc}
h_{n-r} & h_{n-r-1} & h_{n-r-2} & \cdots & h_{0} & 0 & 0 & \cdots & 0 \\
0 & h_{n-r} & h_{n-r-1} & \cdots & h_{1} & h_{0} & 0 & \cdots & 0 \\
0 & 0 & h_{n-r} & \cdots & h_{2} & h_{1} & h_{0} & \cdots & 0 \\
\vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\
0 & 0 & 0 & \cdots & h_{n-r} & h_{n-r-1} & h_{n-r-2} & \cdots & h_{0}
\end{array}\right)
C 的对偶码
C^\bot 是一个由多项式
\bar{h}(x) = h_{n-r} + h_{n-r-1} x + \cdots + h_0 x^{n-r}
生成的
q 元循环码，即
C^\bot = \langle \bar{h}(x) \rangle。
多项式
\bar{h}(x) 称为
h(x) 的互反多项式。严格来说，
C^\bot 的生成多项式应为
h^{-1}_0 \bar{h}(x) = h_0^{-1} (h_{n-r} + h_{n-r-1} x + \cdots + h_0 x^{n-r})
\mathrm{Ham}(r, 2) 等价于一个循环码。
由于循环码的对偶码还是循环码，所以二元汉明码
\mathrm{Ham}(r, 2) 也等价于一个循环码。
p(x) 是二元域
GF(2) 上的一个本原多项式，
\deg{(p(x))} = r，则循环码
\langle p(x) \rangle 就是二元汉明码
\mathrm{Ham}(r, 2)，其中
\langle p(x) \rangle \subseteq R_n，
n = 2^r - 1。
q 元汉明码
\mathrm{Ham}(r, q) 不一定等价于一个循环码，但如果
r 与
q-1 互素，即
\gcd{(r, q-1)} = 1，则
q 元汉明码
\mathrm{Ham}(r, q) 一定等价于一个循环码。
6. 编码方法
设
C 是一个
q 元
[n, n-r] 循环码，其生成多项式为
g(x)，
\deg{(g(x))} = r。显然，
C 有
n-r 个信息位，
r 个校验位。
C 可以对
V(n-r, q) 中的数字信息进行编码。
循环码有两种非常直接的编码方法：一种是非系统的，另一种是系统的。
6.1 非系统编码方法
对任意信源信息向量
a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)，构造信息多项式
a(x) = a_0 + a_1 x + \cdots + a_{n-r-1} x^{n-r-1}
这个多项式对应于循环码
C 中的一个码字
c(x) = a(x) g(x)。因此，信源向量
a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)
被编码为
C 中的码字
c(x) = a(x) g(x)。
6.2 系统编码方法
对任意信源信息向量
a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)，构造信息多项式
\bar{a}(x) = a_0 x^{n-1} + a_1 x^{n-2} + \cdots + a_{n-r-1} x^r
显然，当
a_0, a_1, \cdots, a_{n-r-1} 不全为
0 时，
r \leq \deg{(\bar{a}(x))} \leq n-1。用
g(x) 去除
\bar{a}(x)，得到
\bar{a}(x) = q(x) g(x) + r(x)
其中
\deg{(r(x))} < \deg{(g(x))} = r。信源信息向量
a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q) 被编码为循环码
C 中的码字
c(x) = q(x) g(x) = \bar{a}(x) - r(x)
由于
\bar{a}(x) 与
r(x) 没有相同的项，如果将
c(x) 中的
x 的项按升幂次序排序，则码字中的后
n-r 位就是信息位，前
r 位是校验位。因此这种编码方案是一种系统编码。
附录
文章作者: hotarugali
文章链接: https://hotarugali.github.io/2022/06/20/Technique/ChannelCoding/循环码/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 お前はどこまで見えている！
