循環碼
外觀
在編碼理論中,循環碼(英語:cyclic code)是一種分組碼,每個碼字循環移位會得到同樣屬於該碼的另一個碼字。它們是擁有便於誤差檢測與校正的糾錯碼。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Rotate_right.svg/300px-Rotate_right.svg.png)
定義
[編輯]令 為有限域 上的分組長度為 n 的線性碼。如果對於 C 中的每個碼字 c=(c1,...,cn),由循環移位得到的 中的字 (cn,c1,...,cn-1) 仍是一個碼字,則 稱為循環碼。由於向右循環移一位就相當於向左循環移 n − 1 位,循環碼也可以用循環左移來定義。因此如果任何循環移位都不變的線性碼 是精確循環碼。
循環碼對碼有一些附加結構約束。它們都是基於伽羅華域,由於其結構性質,循環碼對差錯控制很有用。它們與伽羅華域密切相關,因此編碼和譯碼算法都方便計算。
例子
[編輯]舉例來說,若 A= 而 n=3,(1,1,0)循環碼中包含的碼字的集合為
- .
它對應於 中由 生成的理想。
注意到 是該多項式環中的不可約多項式,因此該碼為不可約碼。
該碼的冪等為多項式 ,對應於碼字 (1,1,0)。
參見
[編輯]參考文獻
[編輯]- 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.