查看“︁循环码”︁的源代码

在[[编码理论]]中，'''循环码'''（{{lang-en|'''cyclic code'''}}）是一种[[分組碼]]，每个码字[[循环移位]]会得到同样属于该码的另一个码字。它们是拥有便于误差检测与校正的[[前向錯誤更正|纠错码]]。
[[Image:Rotate right.svg|thumb|right|300px|若00010111是有效码字，将其右循环移位得到10001011。若该码是循环码，则10001011也会是一个有效的码字。一般来说，在右循环移位会将最低位（LSB）移到最左边的位置，于是变为了最高位（MSB）；其他位置会向右移一位。]]

==定义==
令 <math>\mathcal{C}</math> 为[[有限域]] <math>GF(q)</math> 上的[[分組碼|分组长度]]为 ''n'' 的{{le|线性码|linear code}}。如果对于 ''C'' 中的每个{{le|码字|codeword}} ''c''=(''c''<sub>1</sub>,...,''c''<sub>n</sub>)，由[[循环移位]]得到的 <math>GF(q)^n</math> 中的字 (''c''<sub>n</sub>,''c''<sub>1</sub>,...,''c''<sub>n-1</sub>) 仍是一个码字，则 <math>\mathcal{C}</math> 称为'''循环码'''。由于向右循环移一位就相当于向左循环移 ''n''&nbsp;&minus;&nbsp;1 位，循环码也可以用循环左移来定义。因此如果任何循环移位都不变的线性码 <math>\mathcal{C}</math> 是精确循环码。

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

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

:<math>((0,0,0), (1,1,0), (0,1,1), (1,0,1))\,</math>.

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

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

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

==参见==
* [[循環冗餘校驗]]
* [[BCH码]]

==参考文献==
* {{citation|last=Blahut|first=Richard E.|author-link=Richard Blahut|title=Algebraic Codes for Data Transmission|edition=2nd|publisher=[[劍橋大學出版社|Cambridge University Press]]|year=2003|isbn=0-521-55374-1}}
* {{citation|last=Hill|first=Raymond|title=A First Course In Coding Theory|publisher=[[牛津大學出版社|Oxford University Press]]|date=1988|isbn=0-19-853803-0}}
* {{citation|first1=F. J.|last1=MacWilliams|author1-link=F. J. MacWilliams|first2=N. J. A.|last2=Sloane|author2-link=N. J. A. Sloane|title=The Theory of Error-Correcting Codes|place=New York|publisher=North-Holland Publishing|year=1977|isbn=0-444-85011-2}}
* {{citation|first=J. H.|last=Van Lint|author-link=Jack van Lint|title=Introduction to Coding Theory|edition=3rd|series=[[數學研究生教材|Graduate Texts in Mathematics]] '''86'''|publisher=[[施普林格科学+商业媒体|Springer Verlag]]|year=1998|isbn=3-540-64133-5}}

==延伸阅读==
* [[Ranjan Bose]]'', Information theory, coding and cryptography'', ISBN 0-07-048297-7
* {{tsl|en|Irving S. Reed||Irving S. Reed}} and Xuemin Chen, ''Error-Control Coding for Data Networks'', Boston: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4.
* {{tsl|en|Scott A. Vanstone||Scott A. Vanstone}}, [[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] {{Wayback|url=http://www.math.msu.edu/~jhall/classes/codenotes/Cyclic.pdf |date=20140314060948 }} - pp. 100 - 123
* {{MathWorld|title=循环码|urlname=CyclicCode|author=David Terr}}

[[Category:编码理论]]
[[Category:有限域]]