第八章循環碼2內容提要循環碼是線性分組碼中一個重要的子類。本章將介紹循環碼的基本概念以及循環碼的多項式描述方法；循環碼的基本定理及其矩陣描述

；簡單的循環碼的編譯碼方法及其實現電路。3§8.1循環碼的概念一．定義

設一個（n，k）線性分組碼C，如果它的任一碼字的每一次循環移位都還是C的一個碼字，則稱C是循環碼。由于循環碼是線性分組碼，所有這些具有循環關系的碼字的全體構成了n維矢量空間中具有循環特性的k維子空間。4【例】（7，3）線性分組碼由：得由兩組碼字循環構成的循環碼。

5二．循環碼的數學描述1．循環碼的特點：（1）它是線性分組碼，其數學模型應具有線性特性；（2）具有循環特性。

故循環碼的數學模型必須能兼具線性和循環特性→多項式描述。2．線性分組碼的多項式描述字：

字多項式

碼字：

碼字多項式

對于線性分組碼C，可以表示成碼字多項式構成的集合：

63．循環特性的表示以前面的（7，3）循環碼為例：（任取一碼字）移一位移兩位移三位?此時：7>n-1=6，超出了n=7的矢量空間。

要求：

則：，即7下面用去除，得余對于上面第三次移位結果，可重新表示如下：

結論：如果將一個循環碼的某一非零碼字用碼多項式表示出來，那么其他的非零碼字多項式就可以用這個碼字多項式（或碼字多項式的和）乘上x的一個冪，再求（xn+1）的余得到。說明：一個碼字的移位最多能得到n個碼字，因此“循環碼字的循環仍是碼字”并不意味著循環碼集可以從一個碼字循環而得，還應包含碼字的一些線性組合。8§8.2循環碼的基本定理及其矩陣描述

一．循環碼的生成多項式1．定義：若g(x)是一個(n-k)次多項式，且是(xn-1)的因式，則由g(x)可以生成一個（n，k）循環碼，g(x)稱為該循環碼的生成多項式。兩個結論：（1）GF(2)上的（n，k）循環碼中，存在著一個次數為(n-k)的首一碼多項式g(x)（首一：多項式最高冪次項系數

gn-k=1

）（gn-k=1）

使得所有碼多項式都是g(x)的倍式，即：

且所有小于n次的g(x)的倍式都是碼多項式。故循環碼完全由它的生成多項式確定。9（2）（n，k）循環碼的生成多項式g(x)一定是(xn+1)的因子，即

或寫成相反，如果g(x)是xn-1的n-k次因子，則g(x)一定是（n，k）循環碼的生成多項式。生成多項式不唯一。2．（n，k）循環碼的構造（1）對(xn-1)做因式分解，找出(n–k)次因式；（2）以該(n–k)次因式為生成多項式g(x)與不高于k–1次信息多項式u(x)相乘，即得到對應消息序列的碼多項式。10【例】一個長度n=7的循環碼的構造方法。（1）對x7-1作因式分解

故x7-1有如下因式：

一次因式：

三次因式：

四次因式：

六次因式：

（一個）

（兩個）

（一個）

（兩個）

11n–k=1，k=6，生成一種（7，6）循環碼；n–k=3，k=4，生成兩種（7，4）循環碼；n–k=4，k=3，生成兩種（7，3）循環碼；n–k=6，k=1，生成一種（7，1）循環碼；例：要得到一（7，4）循環碼，可選n–k=3次多項式1+x2+x3或1+x+x3

為生成多項式：

以g（x）=1+x2+x3為例，（信息位長度為4）

設信息多項式為：

則：循環碼編碼后的碼多項式為：

（2）若以n-k次因式作為生成多項式，可供選擇的有12例：

對于上述（7，4）循環碼，有4個信息位，對應有16個信息序列，利用16個信息序列多項式與生成多項式的乘法運算，可得全部（7，4）循環碼得16個碼字，如表：信息位碼字信息位碼字信息位碼字信息位碼字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循環組1循環組2循環組3循環組4任何碼字的循環移位仍是碼字，并非由一個碼字循環移位可以得到所有碼字，上述（7，4）碼的碼集由4組碼字循環構成。結論：當一個循環碼給定其生成多項式g（x）后，根據生成多項式就可以進行編碼（但編出的碼不一定為系統碼）13二．循環碼的生成矩陣（n，k）循環碼是n維線性空間一個具有循環特性的k維的子空間，故（n，k）循環碼的生成矩陣可用碼空間中任一組k個線性無關的碼字構成，即k個線性無關的碼字構成（n，k）循環碼的基底，基底不唯一。如何得到k個線性無關的碼字？

方法：當循環碼的生成多項式g（x）給定后，可以取g（x）本身加上移位k–1次所得到的k–1碼字作為k個基底，即：

→構成基底

若：

則：

14各多項式對應的矢量分別為：

這k個矢量是線性無關的，且由g（x）循環移位得到，故都是碼字，由它們構成一個k×n的矩陣，它們就是循環碼的生成矩陣。

15【例】（7，4）循環碼：

當一個循環碼的生成矩陣確定后，其編碼規則為：

如：16（次數）

設：

則：三．循環碼的系統碼由上述方法作出的生成矩陣所編出的碼不是系統形式，如何得到系統形式的循環碼？1．系統循環碼的編碼：設

用xn–k

和u（x）相乘，再除以g(x)17a(x)g(x)是g(x)的一個倍式，則它是一個碼多項式，對應的碼矢量為：碼矢量為系統形式的碼字，信息位在尾部。※系統碼的編碼步驟：(1)將k個消息位按升冪排列的次序寫成消息多項式u（x）

；

(2)用xn–k

乘以u（x）得到一個次數的多項式；

(3)用生成多項式g（x）除xn–k

u（x）得余b（x）（一致校驗元）；

(4)聯合b(x)和xn–k

u(x)得到系統碼多項式v(x)=b(x)+xn–k

u(x)；

(5)將碼多項式轉換為碼字。18【例】（7，4）循環碼：

求

的系統碼字。

，

【解】

，n＝7，k＝4

（1）

（2）（3）（4）192．系統碼的生成矩陣（1）由生成矩陣做初等行變換，將其變為形式，即為系統形式的生成矩陣（單位陣在后，信息位在尾部）。

，求系統形式的生成矩陣。

【例】（7，4）循環碼：

（2）分別求g（x）除的余式（記為），由余式對應的矢量作行矢量構成的k×n-k的分塊矩陣P聯合k×k的單位陣I就構成系統形式的生成矩陣：20，求系統形式的生成矩陣。

【例】（7，4）循環碼：

21四．循環碼的校驗矩陣一般情況下，多項式xn-1可因式分解為xn-1=g(x)·h(x)

g(x)—（n，k）循環碼的生成多項式，

h(x)—（n，k）循環碼的一致校驗多項式，在因式分解中，g(x)和h(x)處于同等地位，既可以用g(x)去生成一個循環碼，也可以用h(x)去生成一個循環碼。設由g(x)生成的碼為C，在由h(x)生成的碼就是C的對偶碼C⊥。

循環碼C的對偶碼C⊥的基底由

構成。

22設

則：將上述矢量按逆序排列作為一個（n-k）×n矩陣的行矢量，則該矩陣就是碼C的校驗矩陣。23【例】（7，4）循環碼：

則：C⊥的基底（n-k-1=2）

24※系統形式的校驗矩陣

（1）對非系統形式的校驗矩陣作初等行變換，變成[In-k，PT]的形式；（2）分別求h（x）除的余式（記為），由余式對應的逆矢量可得到系統形式的校驗矩陣：（3）

25【例】（7，4）循環碼：

（1）（2）k=4，n–k–1=2

（3）26§8.3循環碼的編碼

循環碼是線性分組碼的一個子類，因此循環碼可以按一般線性分組碼利用常用的組合邏輯電路來實現編碼。但對于線性分組碼，當其信息位分組長度較長，編碼位數較多時，其編碼電路非常復雜。由于循環碼具有循環特性，其編碼器通常用簡單的具有反饋連接的移位寄存器就可以實現，大大簡化了編碼器的復雜度。利用具有反饋連接的移位寄存器實現的循環碼編碼電路，實際上是多項式運算電路。首先研究多項式運算電路。27一．G(F2)上的多項式除法電路

設（被除式）（除式）q(x)→商，r(x)→余除法電路：28（1）除法電路的結構由除式b（x）決定；（2）組成：由r個存儲單元組成r級移位寄存器（D0～Dr-1）

bi：常乘器，（bi=1，輸出＝輸入；bi=0，輸出＝0）當bi=1，對應支路連通（直通）；當bi=0，對應支路斷開，對應的模2加法器可去掉。

故：電路有r個移位寄存器，最多r+1個常乘器，最多r個模2加法器。說明：29（3）工作原理簡述：①電路清零，被除式系數按高次到低次依次進入電路（ak首先進入），r次移位后，移存器自右至左內容為：（a

k，a

k-1，...，ak-r+1）②第r+1次移位后，輸出商的最高次位的系數（a

k

b

r

或ak

b

r-1），并反饋到前面作模2加運算后存入各級寄存器中，以后每次移位輸出商的對應次位的系數并反饋回去。③依次類推，經過k+1次移位后，完成整個除法運算，最后輸出商常數項系數，此時移存器中的內容就是余式r（x）各次項對應的系數（高位寄存器對應高次項系數）。30【例】工作過程:(r=3)節拍輸入D0D1D2輸出清零010000111000201100r次300110r＋1次411111（x）k＋1次5-0011（x0）31二．循環碼編碼器1．基于生成多項式g（x）的編碼器（n－k級編碼器）編碼器電路的結構由生成多項式決定，生成多項式g（x）的最高次數為n-k，故編碼器有n-k級移存器，故稱n-k級編碼器。對于循環碼的系統編碼，首先要得到u(x)xn-k除以g(x)的余式p(x)，再組合成系統碼，即：對于除法電路：一方面我們可以得到商，還可以得到余式。對于系統碼編碼我們可以先輸出信息位，再輸出余式（校驗位）就可以得到系統碼，另外由于被除式為u(x)x

n-k，u(x)應從n-k級移存器的最前端輸入。32編碼過程：（1）門打開，k接“1”，消息數據uk-1,...

u0移入電路，并同時送入信道，一旦k個消息全部移入電路，移存器中的n-k個數據就構成了余式的系數；（2）門關，斷開反饋連接，k接“2”；（3）移出移存器中的數據(校驗元)，并送入信道，與k個信息位組成碼字。33【例】（7，4）循環碼，

若：34編碼過程：（k＝4）節拍輸入D0D1D2輸出門開，k→1010001111012010113110004－1001門關，k→25－01006－00107－0001352．基于校驗多項式h（x）的編碼器（k級編碼器）編碼器電路的結構由校驗多項式決定，生成多項式h(x)的最高次數為k，故編碼器有k級移存器，故稱

k級編碼器。編碼器電路編碼過程（1）門1打開，門2關閉，k位消息數據u0，u1，...，uk-1移入電路，并同時送入信道；（2）k位消息全部移入，門1關，門2開；（3）以后的每次移位產生一個校驗元并送入信道，直到n－k個校驗元全部產生并送入信道為止。然后門2關，門1開，準備下一組消息編碼；36【例】（7，4）循環碼，

k＝4級編碼器編碼過程

輸入節拍D0D1D2D3輸出門1開，門2關100000111000102010001310101－411011門1關，門2開－501100－600110－700010373．兩種編碼器的比較（1）基于g（x）的編碼器為n－k級編碼器，需要n－k級移存器；基于h（x）的編碼器為k級編碼器，需要k級移存器。（2）當n－k<k時，采用n－k級編碼器需要資源少；當n－k>k時，采用k級編碼器需要資源少。

38§8.4循環碼譯碼

一．譯碼步驟：和線性分組碼一樣，循環碼譯碼步驟分三步：（1）計算接收多項式r(x)的伴隨多項式s(x)；（2）根據s

(x)找出相應錯誤圖樣多項式e(x)；（3）將e

(x)和r(x)模2加，得到譯碼輸出v

(x)

。二．伴隨式計算及錯誤檢測1．伴隨式及計算設接收多項式為r(x)，碼多項式為v(x)，錯誤圖樣多項式為e(x)，則用生成多項式g（x）除r（x），得

（求余運算）

39【定理】設g(x)是(n，k)系統循環碼的生成多項式，接收字多項式為r(x)，對應錯誤圖樣為e(x),則

且它們的系數就是該接收字的伴隨式。即

可見，循環碼的伴隨式計算電路就是一個接收多項式r(x)除以生成多項式g（x）的除法電路。電路初始狀態為0，當r(x)全部移入后，移存器中的內容為伴隨式多項式s(x)。

402．伴隨式計算電路的性質由于碼的循環結構，伴隨式有個重要的性質，用定理描述。

【定理】設s(x)是r(x)的伴隨式，則r(x)的循環移位x·r(x)的伴隨式s(1)(x)是s(x)在伴隨式計算電路中無輸入時右移一位的結果，即：【推論】用生成多項式g(x)除x

is(x)所得余式s(i)(x)是r(x)經i次移位后r(i)(x)的伴隨式。說明：把含有s(x)的伴隨式移存器的輸入門斷開，移位一次就得到r(1)(x)的伴隨式s(1)(x)

，移位i次，就得到r(i)(x)的伴隨式s(i)(x)

。41【例】（7，4）循環碼，計算對應的伴隨式。伴隨式計算電路計算過程：（開始時，移存器清零）節拍輸入S0S1S2節拍輸入S0S1S210000601112110070101s311108—100s(1)400119—010s(2)5101142由

計算電路性質的意義：對于在同一循環組中的接收字，只需計算一個接收字的伴隨式，即可以通過移位來計算其他接收字的伴隨式。43普通(n,k)線性分組碼的譯碼電路框圖44三．循環碼一般譯碼器1．組成：（三部分）（梅吉特：Meggit通用譯碼器）（1）一個n位的緩沖寄存器（2）組合邏輯電路（3）一個r位的伴隨式計算電路

2．錯誤糾正過程

（1）開始譯碼時，門開，移存器和伴隨式計算電路清零，接收字r（x）一方面送入n級緩存，一方面送入伴隨式計算電路，形成伴隨式。當n位數據接收完后，門關，禁止輸入。45（2）將伴隨式輸入錯誤圖樣檢測電路，找出對應的錯誤圖樣。

方法：當且僅當緩存器中最高位出錯時，組合邏輯電路輸出才為“1”，即，若檢測電路輸出為“1”，說明緩存中最高位的數據是錯誤的，需要糾正。這時輸出的“1”同時反饋到伴隨式計算電路，對伴隨式進行修正，消除該錯誤對伴隨式的影響（修正后為高位無錯對應的伴隨式）。（3）如高位無錯誤，組合電路輸出“0”，高位無需糾正，然后，伴隨式計算電路和緩存各移位一次，這是高位輸出。同時，接收字第二位移到緩存最高位，而伴隨式計算電路得到此高位伴隨式，用來檢測接收字的次高位，即緩存最右一位是否有錯。如有錯，組合電路輸出“1”與緩存輸出相加，完成第二個碼元的糾錯，如無錯，則重復上述過程，一直譯完一個碼字為止。46【例】（7，4）循環碼，dmin(C)=3，可以糾正一個錯誤。

所有單重錯誤的錯誤圖樣：

錯誤圖樣伴隨式對應H的列（0000001）e6(x)=x61+x21017（0000010）e5(x)=x51+x+x21116（0000100）e4(x)=x4x+x20115（0001000）e3(x)=x31+x1104（0010000）e2(x)=x2x20013（0100000）e1(x)=xx0102（1000000）e0(x)=11100147由上表可知：最高位x6出錯的伴隨式為1+x2，因此，識別最高位