循环码

1. 简介

循环码是一类非常重要的线性码，其不仅在理论上有很好的代数结构，而且其编码和译码都可以很容易地利用线性移位寄存器来实现。一些重要的码，比如二元汉明码及其对偶码都等价于循环码。

2. 定义

设 C⊆V(n,q)C \subseteq V(n, q) 是一个线性码。如果 CC 的任意一个码字的循环移位还是一个码字，即当 a0a1⋯an−1∈Ca_0 a_1 \cdots a_{n-1} \in C 时，an−1a0a1⋯an−2∈Ca_{n-1} a_0 a_1 \cdots a_{n-2} \in C，则称 CC 是一个循环码。

3. 性质

令 Rn=Fq[x]/⟨xn−1⟩R_n = F_q[x] / \langle x^n - 1 \rangle，其中 FqF_q 表示 qq 元域 GF(q)GF(q)。显然，V(n,q)V(n, q) 中的向量与 RnR_n 中的多项式之间存在着一个自然的一一对应关系：

a0a1⋯an−1↔a0+a1x+⋯+an−1xn−1a_0 a_1 \cdots a_{n-1} \leftrightarrow a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}

为方便起见，将 V(n,q)V(n, q) 中的向量 a0a1⋯an−1a_0 a_1 \cdots a_{n-1} 与 RnR_n 中的 n−1n-1 次多项式 a(x)=a0+a1x+⋯+an−1xn−1a(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1} 看作是相同的。

对应的多项式系数依次从低次项到高次项。

  • 定理一：一个码 C⊆RnC \subseteq R_n 是循环码当且仅当 CC 满足下述两个条件：
    1. 如果 a(x),b(x)∈Ca(x), b(x) \in C，则 a(x)+b(x)∈Ca(x) + b(x) \in C；
    2. 如果 a(x)∈Ca(x) \in C，r(x)∈Rnr(x) \in R_n，则 r(x)a(x)∈Cr(x) a(x) \in C。

设 f(x)∈Rnf(x) \in R_n，令 ⟨f(x)⟩={r(x)f(x)∣r(x)∈Rn}\langle f(x) \rangle = \{r(x) f(x) | r(x) \in R_n\}。显然 ⟨f(x)⟩\langle f(x) \rangle 是由 f(x)f(x) 生成的多项式带幺交换环 RnR_n 的一个理想。

  • 定理二：对任意 f(x)∈Rnf(x) \in R_n，⟨f(x)⟩\langle f(x) \rangle 是一个循环码。

    称 ⟨f(x)⟩\langle f(x) \rangle 为由 f(x)f(x) 生成的循环码。

  • 定理三：设 CC 是 RnR_n 中的一个循环码，C≠{0}C \neq \{\boldsymbol{0}\}，则

    1. CC 中存在惟一一个具有最低次数并且首项系数为 11 的多项式 g(x)g(x)；
    2. C=⟨g(x)⟩C = \langle g(x) \rangle；
    3. g(x)g(x) 整除 xn−1x^n - 1，即 g(x)g(x) 是 xn−1x^n - 1 的因子。

4. 生成矩阵

  • 定义一：设 CC 是 RnR_n 中的一个循环码，C≠{0}C \neq \{\boldsymbol{0}\}。CC 中次数最低并且首项系数为 11 的多项式 g(x)g(x) 称为循环码 CC 的生成多项式。

  • 定理四：设 g(x)=g0+g1x+⋯+grxrg(x) = g_0 + g_1 x + \cdots + g_r x^r 是一个循环码 C⊆RnC \subseteq R_n 的生成多项式，则 g0≠0g_0 \neq 0。

  • 定理五：设 C⊆RnC \subseteq R_n 是一个循环码，其生成多项式为

    g(x)=g0+g1x+⋯+grxrg(x) = g_0 + g_1 x + \cdots + g_r x^r

    deg⁡(g(x))=r\deg{(g(x))} = r，则 dim⁡(C)=n−r\dim{(C)} = n-r，并且 CC 的生成矩阵为

    G=(g0g1g2⋯gr00⋯00g0g1g2⋯gr0⋯000g0g1g2⋯gr⋯0⋮⋮⋱⋱⋱⋱⋱⋮00⋯0g0g1g2⋯gr)\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)

易知 CC 是一个 qq 元 [n,n−r][n, n-r] 循环码。

5. 校验矩阵

设 C⊆RnC \subseteq R_n 是一个循环码，其生成多项式为 g(x)g(x)，deg⁡(g(x))=r\deg{(g(x))} = r。由定理三可知，存在 h(x)∈Rnh(x) \in R_n，使得

xn−1=h(x)g(x)x^n - 1 = h(x) g(x)

因为 g(x)g(x) 的首项系数为 11，所以 h(x)h(x) 的首项系数也为 11，并且 deg⁡(h(x))=n−r\deg{(h(x))} = n-r。称 h(x)h(x) 为循环码 CC 的校验多项式。

  • 定理六：设 C⊆RnC \subseteq R_n 是一个循环码，其生成多项式为 g(x)g(x)，校验多项式为 h(x)h(x)，则对任意 c(x)∈Rnc(x) \in R_n，c(x)c(x) 是 CC 的一个码字当且仅当 c(x)h(x)=0c(x) h(x) = 0。

  • 定理七：设 C⊆RnC \subseteq R_n 是一个 qq 元 [n,n−r][n, n-r] 循环码，其校验多项式为

    h(x)=h0+h1x+⋯+hn−rxn−rh(x) = h_0 + h_1 x + \cdots + h_{n-r} x^{n-r}

    则

    1. CC 的校验矩阵为

      H=(hn−rhn−r−1hn−r−2⋯h000⋯00hn−rhn−r−1⋯h1h00⋯000hn−r⋯h2h1h0⋯0⋮⋮⋮⋮⋮⋮⋮000⋯hn−rhn−r−1hn−r−2⋯h0)\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)

    2. CC 的对偶码 C⊥C^\bot 是一个由多项式

      hˉ(x)=hn−r+hn−r−1x+⋯+h0xn−r\bar{h}(x) = h_{n-r} + h_{n-r-1} x + \cdots + h_0 x^{n-r}

      生成的 qq 元循环码，即 C⊥=⟨hˉ(x)⟩C^\bot = \langle \bar{h}(x) \rangle。

    多项式 hˉ(x)\bar{h}(x) 称为 h(x)h(x) 的互反多项式。严格来说，C⊥C^\bot 的生成多项式应为

    h0−1hˉ(x)=h0−1(hn−r+hn−r−1x+⋯+h0xn−r)h^{-1}_0 \bar{h}(x) = h_0^{-1} (h_{n-r} + h_{n-r-1} x + \cdots + h_0 x^{n-r})

  • 定理八：二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 等价于一个循环码。

    由于循环码的对偶码还是循环码，所以二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 也等价于一个循环码。

  • 定理九：设 p(x)p(x) 是二元域 GF(2)GF(2) 上的一个本原多项式，deg⁡(p(x))=r\deg{(p(x))} = r，则循环码 ⟨p(x)⟩\langle p(x) \rangle 就是二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2)，其中 ⟨p(x)⟩⊆Rn\langle p(x) \rangle \subseteq R_n，n=2r−1n = 2^r - 1。

qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 不一定等价于一个循环码，但如果 rr 与 q−1q-1 互素，即 gcd⁡(r,q−1)=1\gcd{(r, q-1)} = 1，则 qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 一定等价于一个循环码。

6. 编码方法

设 CC 是一个 qq 元 [n,n−r][n, n-r] 循环码，其生成多项式为 g(x)g(x)，deg⁡(g(x))=r\deg{(g(x))} = r。显然，CC 有 n−rn-r 个信息位，rr 个校验位。CC 可以对 V(n−r,q)V(n-r, q) 中的数字信息进行编码。

循环码有两种非常直接的编码方法：一种是非系统的，另一种是系统的。

6.1 非系统编码方法

对任意信源信息向量 a0a1⋯an−r−1∈V(n−r,q)a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)，构造信息多项式

a(x)=a0+a1x+⋯+an−r−1xn−r−1a(x) = a_0 + a_1 x + \cdots + a_{n-r-1} x^{n-r-1}

这个多项式对应于循环码 CC 中的一个码字 c(x)=a(x)g(x)c(x) = a(x) g(x)。因此，信源向量

a0a1⋯an−r−1∈V(n−r,q)a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)

被编码为 CC 中的码字 c(x)=a(x)g(x)c(x) = a(x) g(x)。

6.2 系统编码方法

对任意信源信息向量 a0a1⋯an−r−1∈V(n−r,q)a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)，构造信息多项式

aˉ(x)=a0xn−1+a1xn−2+⋯+an−r−1xr\bar{a}(x) = a_0 x^{n-1} + a_1 x^{n-2} + \cdots + a_{n-r-1} x^r

显然，当 a0,a1,⋯ ,an−r−1a_0, a_1, \cdots, a_{n-r-1} 不全为 00 时，r≤deg⁡(aˉ(x))≤n−1r \leq \deg{(\bar{a}(x))} \leq n-1。用 g(x)g(x) 去除 aˉ(x)\bar{a}(x)，得到

aˉ(x)=q(x)g(x)+r(x)\bar{a}(x) = q(x) g(x) + r(x)

其中 deg⁡(r(x))<deg⁡(g(x))=r\deg{(r(x))} < \deg{(g(x))} = r。信源信息向量 a0a1⋯an−r−1∈V(n−r,q)a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q) 被编码为循环码 CC 中的码字

c(x)=q(x)g(x)=aˉ(x)−r(x)c(x) = q(x) g(x) = \bar{a}(x) - r(x)

由于 aˉ(x)\bar{a}(x) 与 r(x)r(x) 没有相同的项，如果将 c(x)c(x) 中的 xx 的项按升幂次序排序，则码字中的后 n−rn-r 位就是信息位，前 rr 位是校验位。因此这种编码方案是一种系统编码。

附录

  • 《编码理论基础》by 陈鲁生
Technique ChannelCoding
Technique ChannelCoding

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！