跳至內容

循環碼

維基百科,自由的百科全書

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

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

定義

有限域 上的分組長度n線性碼英語linear code。如果對於 C 中的每個碼字英語codeword c=(c1,...,cn),由循環移位得到的 中的字 (cn,c1,...,cn-1) 仍是一個碼字,則 稱為循環碼。由於向右循環移一位就相當於向左循環移 n − 1 位,循環碼也可以用循環左移來定義。因此如果任何循環移位都不變的線性碼 是精確循環碼。

循環碼對碼有一些附加結構約束。它們都是基於伽羅華域,由於其結構性質,循環碼對差錯控制很有用。它們與伽羅華域密切相關,因此編碼和譯碼算法都方便計算。

例子

舉例來說,若 A=n=3,(1,1,0)循環碼中包含的碼字的集合為

.

它對應於 中由 生成的理想。

注意到 是該多項式環中的不可約多項式,因此該碼為不可約碼。

該碼的冪等為多項式 ,對應於碼字 (1,1,0)。

參見

參考文獻

延伸閱讀

外部連結