循環碼

循環碼：無權碼，每位代碼無固定權值，任何相鄰的兩個碼組中，僅有一位代碼不同。

一個(n,k)線性分組碼C，若它的任一碼字的每一循環移位寄存器都是C的一個碼字，則稱C是一個循環碼。

表1(7,4)循環碼

信息組

m₃ m₂ m₁ m₀

碼字

C₆ C₅ C₄ C₃ C₂ C₁ C₀

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)循環碼中，d_min=3。而且根據定義，任一碼字的每一循環移位的結果都是(7,4)循環碼的一個碼字。但某一碼字的循環移位，並不能生成所有的碼字。對於一個循環碼來説，可以同時存在多個循環圈。

十六進制數

自然二進制碼

十六進制數

自然二進制碼

循環二進制碼

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

為了探討循環碼的特徵，把碼字C=(C_n－1 C_n－2…C₁C₀)用如下的碼多項式C(x)來表示。

（1）特性一

在一個(n,k)循環碼中，存在惟一的一個n－k次碼多項式：

每一個碼多項式C(x)都是g(x)的一個倍式，反之每個為g(x)倍式，且次數小於等於n－1的多項式必是一個碼多項式。

由此可見，(n,k)循環碼中的每一個碼多項式C(x)均可由下式表示：

如果m(x)的係數(m_k－1…m₁m₀)就是表示待編碼的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)，x²g(x)，…，x^k－1g(x)皆為碼多項式。用它們構成G，再用行變換把G變換為典型生成矩陣，然後用其編碼。

b．用g(x)除x^n－k+i (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，所以D₁的輸入端有反饋線及模2加法器。信息輸入時，門打開，K₁接通，信息送入除法器的同時，向外輸出；信息位送完，門關閉，K₂接通。除法電路中D₂D₁D₀的內容，即所得餘式，也就是校驗位緊隨信息位輸出，完成一個碼字的編碼過程。這裏設信息碼元為1101，編碼結果為1101001。 ^[2] 

輸入m

移位寄存器

D₀ D₁ D₂

輸出

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

令S(x)是接收多項式R(x)=r_n－1x^n－1+…+r₁x+r₀的伴隨式，利用生成多項式g(x)除xS(x)所得的餘式S⁽¹⁾(x)，就是R(x)循環移位一次R⁽¹⁾(x)的伴隨式。

因此，可用伴隨式運算電路依次求出對應於各碼位的伴隨式。以g(x)=x³+x+1的(7,4)循環碼為例.

表6是錯誤圖樣和相應的伴隨式。

表6 錯誤圖樣和伴隨式

移存器狀態

D₀ D₁ D₂

錯誤圖樣

伴隨式

S₀ S₁ S₂

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

可以看出如果我們在伴隨式運算電路中賦予一個與e₀出錯項對應的伴隨式S=001，隨着伴隨式電路的運算，移存器中的內容就會是依次是e₁,e₂,…,e₆的伴隨式。

定理表明如果e(x)的伴隨式是S(x)，則xe(x)的伴隨式t(x)=S^（1）(x)。它相當於S(x)在伴隨式運算電路里的循環移一位。當差錯碼元移到最高位時，就和最高位出錯的伴隨式相同，這就大大簡化了譯碼器的結構。g(x)=x³+x+1的(7,4)循環碼的譯碼電路由圖7給出。

縮短循環碼

循環碼的生成多項式g(x)應該是xⁿ+1的一個(n－k) 次因子，但有時在給定碼長n時，xⁿ+1的因子不能滿足設計者的需要，為了增加選擇機會，往往採用縮短循環碼。

在(n,k)循環碼的2^k個碼字中選擇前i位信息位為0的碼字，共有2^k－i個，組成一個新的碼字集。這樣就構成了一個(n－i,k－i)縮短循環碼。

在縮短循環碼中，校驗碼原位數不變，縮短的僅僅是信息位，因此(n－i,k－i)縮短循環碼的糾檢錯的能力不低於(n,k)碼的糾檢錯能力。但碼字間已失去了循環特徵。

在數據通信中廣泛採用的循環冗餘檢驗碼(CRC，Cyclic Redundancy Checks)，是一種循環碼，常利用縮短循環碼，如CRC－12、CRC－16、CRC－CCITT碼，表8給出了它們的生成多項式。

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^m－1=一定存在一個具有下列參數的二進制BCH碼：

碼長n=2^m－1

校驗位數目n－k≤mt

最小距離d_min≥2t+1

BCH碼可以分為兩類，即本原BCH碼和非本原BCH碼。本原BCH碼碼長n=2^m－1，它的生成多項式g(x)中含有最高次數為m的本原多項式，本原多項式是一個既約多項式，它能除盡xⁿ+1的最小正整數n，滿足n=2^m－1。具有循環碼特性，糾單個隨機錯誤的漢明碼，是可糾單個隨機錯誤的本原BCH碼。而非本原BCH碼中的生成多項式g(x)中不含本原多項式，且碼長n是2^m－1的一個因子，著名的戈雷(Golay)碼，就屬於非本原BCH碼。

給出了n≤31的本原BCH碼的參數和生成多項式。

本原BCH碼生成多項式

n k t

g_t(x)

7 4 1

g₁(x)=13

1 3

g₁(x)(15)=177

15 11 1

g₁(x)=23

7 2

g₁(x)(37)=721

5 3

g₂(x)(7)=2467

1 7

g₃(x)(31)=77777

31 26 1

g₁(x)=45

21 2

g₁(x)(75)=3551

16 3

g₂(x)(67)=10765 7

11 5

g₃(x)(57)=54233 25

n k t

g_t(x)

6 7

g₅(x)(73)=31336 5047

1 15

g₇(x)(51)=17777 77777 7

表中的每一位數字為八進制數，代表g(x)多項式中3個二進制係數。如n=31，k=26,t=1的BCH碼的生成多項式g₁(x)=45。45表示100101，所以，該BCH碼的g(x)=x⁵+x²+1。有了生成多項式表就可很方便地構造所需的BCH碼。

裏德—所羅門(Read-Solomon)碼

除了二進制碼之外，還有非二進制碼。如果P是一素數，q是p的任意次冪，存在着由伽羅華域GF(q)產生的碼。這些碼稱為q進制碼。q進制碼的編碼和譯碼都與二進制碼相似。

對任意選擇的正整數s和t，存在長度為n=q^s－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

最小距離：d_min=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位)是信息位。