循環碼

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

1 0 0

1

1 0 0

1

0 1 0

0 0 1

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。

自然二進位碼

循環二進位碼

十六進位數

自然二進位碼

循環二進位碼

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)循環碼

信息組

m3 m2 m1 m0

碼字

C6 C5 C4 C3 C2 C1 C0

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是一個循環碼。