循環碼

在編碼理論中，循環碼（英語：cyclic code）是一種分組碼，每個碼字循環移位會得到同樣屬於該碼的另一個碼字。它們是擁有便於誤差檢測與校正的糾錯碼。

若00010111是有效碼字，將其右循環移位得到10001011。若該碼是循環碼，則10001011也會是一個有效的碼字。一般來說，在右循環移位會將最低位（LSB）移到最左邊的位置，於是變為了最高位（MSB）；其他位置會向右移一位。

定義

令 ${\mathcal {C}}$ 為有限域 $GF(q)$ 上的分組長度為 n 的線性碼。如果對於 C 中的每個碼字 c=(c₁,...,c_n)，由循環移位得到的 $GF(q)^{n}$ 中的字 (c_n,c₁,...,c_n-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碼

參考文獻

• Blahut, Richard E., Algebraic Codes for Data Transmission 2nd, Cambridge University Press, 2003, ISBN 0-521-55374-1 
• Hill, Raymond, A First Course In Coding Theory, Oxford University Press, 1988, ISBN 0-19-853803-0 
• MacWilliams, F. J.; Sloane, N. J. A., The Theory of Error-Correcting Codes, New York: North-Holland Publishing, 1977, ISBN 0-444-85011-2 
• Van Lint, J. H., Introduction to Coding Theory, Graduate Texts in Mathematics 86 3rd, Springer Verlag, 1998, ISBN 3-540-64133-5 

延伸閱讀

• Ranjan Bose, Information theory, coding and cryptography, ISBN 0-07-048297-7
• Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks, Boston: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4.
• 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 – Notes #3, October 8, Handout #9, EE 387.
• Jonathan Hall's (MSU) class notes – Chapter 8. Cyclic codes （頁面存檔備份，存於網際網路檔案館） - pp. 100 - 123
• David Terr. 循环码. MathWorld.