循環碼具有循環移位特性且能糾錯的分組碼循環碼是線性碼的一個重要的子類，它有以下兩大特點：第一，碼的結構可以用代數方法來構造和分析，并且可以找到各種實用的譯碼方法；第二，由于其循環特性，編碼運算和伴隨式計算，可用反饋移位寄存器來實現，硬件實現簡單。
常用CRC碼
CRC碼
生成多項式
CRC－12
x+x+x+x+x+1
CRC－16
x+x+x+1
CRC－ccitt
x+x+x+1
BCH碼
BCH碼是循環碼的一個重要的子類，它是一種能糾正多個隨機錯誤的應用最為廣泛和有效的差錯控制碼。
定義：對于任意正整數m(m≥3)和t(t<2=一定存在一個具有下列參數的二進制BCH碼：
碼長n=2－1
校驗位數目n－k≤mt
最小距離dmin≥2t+1
BCH碼可以分為兩類，即本原BCH碼和非本原BCH碼。本原BCH碼碼長n=2－1，它的生成多項式g(x)中含有最高次數為m的本原多項式，本原多項式是一個既約多項式，它能除盡x+1的最小正整數n，滿足n=2－1。具有循環碼特性，糾單個隨機錯誤的漢明碼，是可糾單個隨機錯誤的本原BCH碼。而非本原BCH碼中的生成多項式g(x)中不含本原多項式，且碼長n是2－1的一個因子，著名的戈雷(Golay)碼，就屬于非本原BCH碼。
給出了n≤31的本原BCH碼的參數和生成多項式。
本原BCH碼生成多項式
n?k?t
gt(x)
7 4 1
g1(x)=13
1 3
g1(x)(15)=177
15 11 1
g1(x)=23
7 2
g1(x)(37)=721
5 3
g2(x)(7)=2467
1 7
g3(x)(31)=77777
31 26 1
g1(x)=45
21 2
g1(x)(75)=3551
16 3
g2(x)(67)=10765 7
11 5
g3(x)(57)=54233 25
n?k?t
gt(x)
6 7
g5(x)(73)=31336 5047
1 15
g7(x)(51)=17777 77777 7
表中的每一位數字為八進制數，代表g(x)多項式中3個二進制系數。如n=31，k=26,t=1的BCH碼的生成多項式g1(x)=45。45表示100101，所以，該BCH碼的g(x)=x+x+1。有了生成多項式表就可很方便地構造所需的BCH碼。
里德—古斯塔夫·所羅門(Read-Solomon)碼
除了二進制碼之外，還有非二進制碼。如果P是一素數，q是p的任意次冪，存在著由伽羅華域GF(q)產生的碼。這些碼稱為q進制碼。q進制碼的編碼和譯碼都與二進制碼相似。
對任意選擇的正整數s和t，存在長度為n=q－1的q進制BCH碼。它能糾正t個錯誤，而只用2St個校驗位。S=1時的q進制BCH碼是q進制BCH碼中的一類最重要的子碼。這類子碼稱為里德——所羅門(Read-Solomon)碼，簡稱R-S碼。糾t位錯誤，系數為GF(q)中元素的R-S碼具有下列參數：
碼長：n=q－1
校驗位數目：n－k=2t
最小距離：dmin=2t+1
R-S碼對糾多重突發差錯非常有效。
R-S碼把L位(例如8位)的一個字節，作為一個編碼符號。如果我們要設計一個糾t=5位錯誤的，由8位字節組成的R-S碼，碼長為q－1=255字節(這里，p=2,q=2)。那么根據R-S碼的參數，校驗位的數目為r=n－k=2t=10字節(80位)，其余k=n－r=245字節(1960位)是信息位。
譯碼器
縮短循環碼
循環碼的生成多項式g(x)應該是x+1的一個(n－k) 次因子，但有時在給定碼長n時，x+1的因子不能滿足設計者的需要，為了增加選擇機會，往往采用縮短循環碼。
在(n,k)循環碼的2個碼字中選擇前i位信息位為0的碼字，共有2個，組成一個新的碼字集。這樣就構成了一個(n－i,k－i)縮短循環碼。
在縮短循環碼中，校驗碼原位數不變，縮短的僅僅是信息位，因此(n－i,k－i)縮短循環碼的糾檢錯的能力不低于(n,k)碼的糾檢錯能力。但碼字間已失去了循環特征。
在數據通信中廣泛采用的循環冗余檢驗碼(CRC，Cyclic Redundancy Checks)，是一種循環碼，常利用縮短循環碼，如CRC－12、CRC－16、CRC－CCITT碼，表8給出了它們的生成多項式。
譯碼
令S(x)是接收多項式R(x)=rn－1x+…+r1x+r0的伴隨式，利用生成多項式g(x)除xS(x)所得的余式S(x)，就是R(x)循環移位一次R(x)的伴隨式。
因此，可用伴隨式運算電路依次求出對應于各碼位的伴隨式。以g(x)=x+x+1的(7,4)循環碼為例.
表6是錯誤圖樣和相應的伴隨式。
表6 錯誤圖樣和伴隨式
移存器狀態
D0?D1飄移大獎賽?D2
錯誤圖樣
e0e1e2e3e4e5e6
伴隨式
S0?S1?S2
1 0 0
1 0 0 0 0 0 0
1 0 0
0 1 0
0 1 0 0 0 0 0
0 1 0
0 0 1
0 0 1 0 0 0 0
0 0 1
1 1 0
0 0 0 1 0 0 0
1 1 0
0 1 1
0 0 0 0 1 0 0
0 1 1
1 1 1
0 0 0 0 0 1 0
1 1 1
1 0 1
0 0 0 0 0 0 1
1 0 1
可以看出如果我們在伴隨式運算電路中賦予一個與e0出錯項對應的伴隨式S=001，隨著伴隨式電路的運算，移存器中的內容就會是依次是e1,e2,…,e6的伴隨式。
定理表明如果e(x)的伴隨式是S(x)，則xe(x)的伴隨式t(x)=S(x)。它相當于S(x)在伴隨式運算電路里的循環移一位。當差錯碼元移到最高位時，就和最高位出錯的伴隨式相同，這就大大簡化了編譯器的結構。g(x)=x+x+1的(7,4)循環碼的譯碼電路由圖7給出。
工作過程
輸入m
移位寄存器
D0?D1飄移大獎賽?D2
輸出
1
1 1 0
1
1
1 0 1
1
0
1 0 0
0
1
1 0 0
1
0
0 1 0
0
0
0 0 1
0
0
0 0 0
1
特征
為了探討循環碼的特征，把碼字C=(Cn－1?Cn－2…C1C0)用如下的碼多項式C(x)來表示。
（1）特性一
在一個(n,k)循環碼中，存在惟一的一個n－k次碼多項式：
每一個碼多項式C(x)都是g(x)的一個倍式，反之每個為g(x)倍式，且次數小于等于n－1的多項式必是一個碼多項式。
由此可見，(n,k)循環碼中的每一個碼多項式C(x)均可由下式表示：
如果m(x)的系數(mk－1…m1m0)就是表示待編碼的k位信息位，則C(x)就是對應于此信息組m(x)的碼多項式。因此(n,k)循環碼完全可由g(x)確定。g(x)也稱為循環碼(n,k)的生成多項式。g(x)的次數n－k等于碼中一致校驗位的位數。
（2）特性二
(n,k)循環碼的生成多項式是x+1的因子，即：
x+1=g(x)h(x)
其中h(x)稱為碼的一致校驗多項式，循環碼的H矩陣也可以通過h(x)來生成。
（3）特性三
若g(x)是一個n－k次多項式，并且是x+1的因子，則g(x)一定能生成一個(n,k)循環碼。
表2.5給出了多項式x+1中所含有的部分生成多項式和相應的循環碼。
循環碼的編碼
（1）編碼方法
根據上述的三個循環碼特征，可以有三種(n,k)循環碼的編碼方法。
表2x+1中的部分g?(x)
循環碼
碼距
生成多項式g(x)
校驗多項式h(x)
(7,6)
2
x+1
(x?+x+1)(x?+x?+1)
(7,4)
3
x?+x+1
(x?+x?+1)(x+1)
(7,3)
4
(x+1)(x?+x+1)
x?+x?+1
(7,1)
7
(x?+x?+1)(x?+x+1)
x+1
① 用生成多項式編碼
a．選擇一個能除盡x+1的n－k=r次生成多項式g(x)。
b．由g(x)生成各碼多項式。
c．找出與碼多項式相對應的循環碼字。
② 用生成矩陣編碼
有兩種求生成矩陣的方法：
a．因為g(x)是最低次數的碼多項式。且xg(x)，xg(x)，…，xg(x)皆為碼多項式。用它們構成G，再用行變換把G變換為典型生成矩陣，然后用其編碼。
b．用g(x)除x(i=0，1，…，k－1)，得：
于是是g(x)的倍式，且次數小于等于n－1，所以為碼多項式。用此方法可得到k個碼多項式，可以直接構成典型生成矩陣，用以編碼。
③ 用余式確定校驗位
a.用乘信息多項式m(x)。
b.用g(x)除m(x)得到余式r(x)。
c.生成碼多項式m(x)+r(x)。
第一種方法可用乘法電路來完成，第二種方法用生成矩陣G編碼是一般線性分組編碼的通用方法，利用這一種方法編循環碼，體現不出循環碼的優點，第三種方法可用除法電路來完成，應用比較廣泛。
（2）除法電路編碼器
以g(x)=x+x+1生成(7,4)循環碼的編碼器為例。
編碼器主要由一除法電路構成。除法電路由移位寄存器和模2加法器組成。移位寄存器的個數與g(x)的次數相等。因為g(x)=x+x+1，所以移位寄存器有三個。g(x)多項式中的系數是1還是0表示該移位寄存器的輸入端反饋線的有無。x的一次項的系數為1，所以D1的輸入端有反饋線及模2加法器。信息輸入時，門打開，K1接通，信息送入除法器的同時，向外輸出；信息位送完，門關閉，k2接通。除法電路中D2D1D0的內容，即所得余式，也就是校驗位緊隨信息位輸出，完成一個碼字的編碼過程。這里設信息碼元為1101，編碼結果為1101001。
編碼種類
十六進制數
自然二進制碼
循環二進制碼
十六進制數
自然二進制碼
循環二進制碼
0
0000
0000
8
1000
1100
1
0001
0001
9
1001
1101
2
0010
0011
A
1010
1111
3
0011
0010
B
1011
1110
4
0100
0110
C
1100
1010
5
0101
0111
D
1101
1011
6
0110
0101
E
1110
1001
7
0111
0100
F
1111
1000
信息組
表1(7,4)循環碼
信息組
碼字
0 0 0 0
0 0 0 0 0 0 0
0 0 0 1
0 0 0 1 1 0 1
0 0 1 0
0 0 1 0 1 1 1
0 0 1 1
0 0 1 1 0 1 0
0 1 0 0
0 1 0 0 0 1 1
0 1 0 1
0 1 0 1 1 1 0
0 1 1 0
0 1 1 0 1 0 0
0 1 1 1
0 1 1 1 0 0 1
1 0 0 0
1 0 0 0 1 1 0
1 0 0 1
1 0 0 1 0 1 1
1 0 1 0
1 0 1 0 0 0 1
1 0 1 1
1 0 1 1 1 0 0
1 1 0 0
1 1 0 0 1 0 1
1 1 0 1
1 1 0 1 0 0 0
1 1 1 0
1 1 1 0 0 1 0
1 1 1 1
1 1 1 1 1 1 1
給出(7,4)循環碼，由于循環碼是線性分組碼的一種，所以它也具有封閉性，任意兩個碼字相加之和必是另一碼字。所以它的最小碼距也就是非零碼字的最小碼重。在表1給出的(7,4)循環碼中，dmin=3。而且根據定義，任一碼字的每一循環移位的結果都是(7,4)循環碼的一個碼字。但某一碼字的循環移位，并不能生成所有的碼字。對于一個循環碼來說，可以同時存在多個循環圈。
定義
循環碼：無權碼，每位代碼無固定權值，任何相鄰的兩個碼組中，僅有一位代碼不同。
一個(n,k)線性分組碼C，若它的任一碼字的每一循環移位寄存器都是C的一個碼字，則稱C是一個循環碼。
參考資料 >