循环码

hotarugali

发布于 2022-09-09 11:30:37

7950

发布于 2022-09-09 11:30:37

文章被收录于专栏：hotarugaliの技术分享

1. 简介

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

2. 定义

设

C \subseteq V(n, q)

是一个线性码。如果

的任意一个码字的循环移位还是一个码字，即当

a_0 a_1 \cdots a_{n-1} \in C

时，

a_{n-1} a_0 a_1 \cdots a_{n-2} \in C

，则称

是一个循环码。

3. 性质

令

R_n = F_q[x] / \langle x^n - 1 \rangle

，其中

F_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

是循环码当且仅当

满足下述两个条件：

如果

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)

生成的循环码。

定理三：设

是

R_n

中的一个循环码，

C \neq \{\boldsymbol{0}\}

，则

中存在惟一一个具有最低次数并且首项系数为

的多项式

g(x)

；

C = \langle g(x) \rangle

；

g(x)

整除

x^n - 1

，即

g(x)

是

x^n - 1

的因子。

4. 生成矩阵

定义一：设

是

R_n

中的一个循环码，

C \neq \{\boldsymbol{0}\}

。

中次数最低并且首项系数为

的多项式

g(x)

称为循环码

的生成多项式。

定理四：设

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

，并且

的生成矩阵为

\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)

易知

是一个

元

[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)

的首项系数为

，所以

h(x)

的首项系数也为

，并且

\deg{(h(x))} = n-r

。称

h(x)

为循环码

的校验多项式。

定理六：设

C \subseteq R_n

是一个循环码，其生成多项式为

g(x)

，校验多项式为

h(x)

，则对任意

c(x) \in R_n

，

c(x)

是

的一个码字当且仅当

c(x) h(x) = 0

。

定理七：设

C \subseteq R_n

是一个

元

[n, n-r]

循环码，其校验多项式为

h(x) = h_0 + h_1 x + \cdots + h_{n-r} x^{n-r}

则

的校验矩阵为

\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^\bot

是一个由多项式

\bar{h}(x) = h_{n-r} + h_{n-r-1} x + \cdots + h_0 x^{n-r}

生成的

元循环码，即

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

。

元汉明码

\mathrm{Ham}(r, q)

不一定等价于一个循环码，但如果

与

q-1

互素，即

\gcd{(r, q-1)} = 1

，则

元汉明码

\mathrm{Ham}(r, q)

一定等价于一个循环码。

6. 编码方法

设

是一个

元

[n, n-r]

循环码，其生成多项式为

g(x)

，

\deg{(g(x))} = r

。显然，

有

n-r

个信息位，

个校验位。

可以对

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(x) = a(x) g(x)

。因此，信源向量

a_0 a_1 \cdots a_{n-r-1} \in V(n-r, q)

被编码为

中的码字

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}

不全为

时，

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(x) = q(x) g(x) = \bar{a}(x) - r(x)

由于

\bar{a}(x)

与

r(x)

没有相同的项，如果将

c(x)

中的

的项按升幂次序排序，则码字中的后

n-r

位就是信息位，前

位是校验位。因此这种编码方案是一种系统编码。

附录

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

文章作者: hotarugali

文章链接: https://hotarugali.github.io/2022/06/20/Technique/ChannelCoding/循环码/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-06-20，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

循环码

循环码

1. 简介

2. 定义

3. 性质

4. 生成矩阵

5. 校验矩阵

6. 编码方法

6.1 非系统编码方法

6.2 系统编码方法

附录

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐