循环码

在编码理论中，循环码（）是一种分組碼，每个码字循环移位会得到同样属于该码的另一个码字。它们是拥有便于误差检测与校正的纠错码。

定义
令 \mathcal{C} 为有限域 GF(q) 上的分组长度为 n 的线性码。如果对于 C 中的每个 c=(c1,...,cn)，由循环移位得到的 GF(q)^n 中的字 (cn,c1,...,cn-1) 仍是一个码字，则 \mathcal{C} 称为循环码。由于向右循环移一位就相当于向左循环移 n − 1 位，循环码也可以用循环左移来定义。因此如果任何循环移位都不变的线性码 \mathcal{C} 是精确循环码。

循环码对码有一些附加结构约束。它们都是基于伽罗华域，由于其结构性质，循环码对差错控制很有用。它们与伽罗华域密切相关，因此编码和译码算法都方便计算。

例子
举例来说，若 A=\mathbb{F}_2 而 n=3，(1,1,0)循环码中包含的码字的集合为

:((0,0,0), (1,1,0), (0,1,1), (1,0,1))\,.

它对应于 \mathbb{F}_2[x]/(x^3-1) 中由 (1+x) 生成的理想。

注意到 (1+x) 是该多项式环中的不可约多项式，因此该码为不可约码。

该码的幂等为多项式 x + x^2，对应于码字 (1,1,0)。

参见

• 循環冗餘校驗
• BCH码

参考文献
*
*
*
*

延伸阅读

• Ranjan Bose, Information theory, coding and cryptography, ISBN 0-07-048297-7
• and Xuemin Chen, Error-Control Coding for Data Networks, Boston: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4.
• , Paul C. Van Oorschot, An introduction to error correcting codes with applications, ISBN 0-7923-9017-2

外部链接

• John Gill's (Stanford) class notes – [https://web.archive.org/web/20121023015831/http://www.stanford.edu/class/ee387/handouts/notes3.pdf Notes #3, October 8, Handout #9], EE 387.
• Jonathan Hall's (MSU) class notes – [http://www.math.msu.edu/~jhall/classes/codenotes/Cyclic.pdf Chapter 8. Cyclic codes] - pp. 100 - 123

*