循環(huán)碼課件講義整理

第八章循環(huán)碼1第八章1內(nèi)容提要循環(huán)碼是線(xiàn)性分組碼中一個(gè)重要的子類(lèi)。本章將介紹循環(huán)碼的基本概念以及循環(huán)碼的多項(xiàng)式描述方法；循環(huán)碼的基本定理及其矩陣描述

；簡(jiǎn)單的循環(huán)碼的編譯碼方法及其實(shí)現(xiàn)電路。2內(nèi)容提要循環(huán)碼是線(xiàn)性分組碼中一個(gè)重要的子類(lèi)。2§8.1循環(huán)碼的概念一．定義

設(shè)一個(gè)（n，k）線(xiàn)性分組碼C，如果它的任一碼字的每一次循環(huán)移位都還是C的一個(gè)碼字，則稱(chēng)C是循環(huán)碼。由于循環(huán)碼是線(xiàn)性分組碼，所有這些具有循環(huán)關(guān)系的碼字的全體構(gòu)成了n維矢量空間中具有循環(huán)特性的k維子空間。3§8.1循環(huán)碼的概念一．定義設(shè)一個(gè)（n，k）線(xiàn)性分組碼C，【例】（7，3）線(xiàn)性分組碼由：得由兩組碼字循環(huán)構(gòu)成的循環(huán)碼。

4【例】（7，3）線(xiàn)性分組碼由：二．循環(huán)碼的數(shù)學(xué)描述1．循環(huán)碼的特點(diǎn)：（1）它是線(xiàn)性分組碼，其數(shù)學(xué)模型應(yīng)具有線(xiàn)性特性；（2）具有循環(huán)特性。

故循環(huán)碼的數(shù)學(xué)模型必須能兼具線(xiàn)性和循環(huán)特性→多項(xiàng)式描述。2．線(xiàn)性分組碼的多項(xiàng)式描述字：

字多項(xiàng)式

碼字：

碼字多項(xiàng)式

對(duì)于線(xiàn)性分組碼C，可以表示成碼字多項(xiàng)式構(gòu)成的集合：

5二．循環(huán)碼的數(shù)學(xué)描述1．循環(huán)碼的特點(diǎn)：（1）它是線(xiàn)性分組碼，3．循環(huán)特性的表示以前面的（7，3）循環(huán)碼為例：（任取一碼字）移一位移兩位移三位?此時(shí)：7>n-1=6，超出了n=7的矢量空間。

要求：

則：，即63．循環(huán)特性的表示以前面的（7，3）循環(huán)碼為例：（任取一碼字下面用去除，得余對(duì)于上面第三次移位結(jié)果，可重新表示如下：

結(jié)論：如果將一個(gè)循環(huán)碼的某一非零碼字用碼多項(xiàng)式表示出來(lái)，那么其他的非零碼字多項(xiàng)式就可以用這個(gè)碼字多項(xiàng)式（或碼字多項(xiàng)式的和）乘上x(chóng)的一個(gè)冪，再求（xn+1）的余得到。說(shuō)明：一個(gè)碼字的移位最多能得到n個(gè)碼字，因此“循環(huán)碼字的循環(huán)仍是碼字”并不意味著循環(huán)碼集可以從一個(gè)碼字循環(huán)而得，還應(yīng)包含碼字的一些線(xiàn)性組合。7下面用去除§8.2循環(huán)碼的基本定理及其矩陣描述

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

gn-k=1

）（gn-k=1）

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

且所有小于n次的g(x)的倍式都是碼多項(xiàng)式。故循環(huán)碼完全由它的生成多項(xiàng)式確定。8§8.2循環(huán)碼的基本定理及其矩陣描述一．循環(huán)碼的生成多項(xiàng)（2）（n，k）循環(huán)碼的生成多項(xiàng)式g(x)一定是(xn+1)的因子，即

或?qū)懗上喾?，如果g(x)是xn+1的n-k次因子，則g(x)一定是（n，k）循環(huán)碼的生成多項(xiàng)式。生成多項(xiàng)式不唯一。2．（n，k）循環(huán)碼的構(gòu)造（1）對(duì)(xn+1)做因式分解，找出(n–k)次因式；（2）以該(n–k)次因式為生成多項(xiàng)式g(x)與不高于k–1次信息多項(xiàng)式u(x)相乘，即得到對(duì)應(yīng)消息序列的碼多項(xiàng)式。9（2）（n，k）循環(huán)碼的生成多項(xiàng)式g(x)一定是(xn+1)【例】一個(gè)長(zhǎng)度n=7的循環(huán)碼的構(gòu)造方法。（1）對(duì)x7+1作因式分解

故x7+1有如下因式：

一次因式：

三次因式：

四次因式：

六次因式：

（一個(gè)）

（兩個(gè)）

（一個(gè)）

（兩個(gè)）

10【例】一個(gè)長(zhǎng)度n=7的循環(huán)碼的構(gòu)造方法。（1）對(duì)x7n–k=1，k=6，生成一種（7，6）循環(huán)碼；n–k=3，k=4，生成兩種（7，4）循環(huán)碼；n–k=4，k=3，生成兩種（7，3）循環(huán)碼；n–k=6，k=1，生成一種（7，1）循環(huán)碼；例：要得到一（7，4）循環(huán)碼，可選n–k=3次多項(xiàng)式1+x2+x3或1+x+x3

為生成多項(xiàng)式：

以g（x）=1+x2+x3為例，（信息位長(zhǎng)度為4）

設(shè)信息多項(xiàng)式為：

則：循環(huán)碼編碼后的碼多項(xiàng)式為：

（2）若以n-k次因式作為生成多項(xiàng)式，可供選擇的有11n–k=1，k=6，生成一種（7，6）循環(huán)碼；例例：

對(duì)于上述（7，4）循環(huán)碼，有4個(gè)信息位，對(duì)應(yīng)有16個(gè)信息序列，利用16個(gè)信息序列多項(xiàng)式與生成多項(xiàng)式的乘法運(yùn)算，可得全部（7，4）循環(huán)碼得16個(gè)碼字，如表：信息位碼字信息位碼字信息位碼字信息位碼字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循環(huán)組1循環(huán)組2循環(huán)組3循環(huán)組4任何碼字的循環(huán)移位仍是碼字，并非由一個(gè)碼字循環(huán)移位可以得到所有碼字，上述（7，4）碼的碼集由4組碼字循環(huán)構(gòu)成。結(jié)論：當(dāng)一個(gè)循環(huán)碼給定其生成多項(xiàng)式g（x）后，根據(jù)生成多項(xiàng)式就可以進(jìn)行編碼（但編出的碼不一定為系統(tǒng)碼）12例：對(duì)于上述（7，4）循環(huán)碼，有4個(gè)信息位，對(duì)應(yīng)有16個(gè)信二．循環(huán)碼的生成矩陣（n，k）循環(huán)碼是n維線(xiàn)性空間一個(gè)具有循環(huán)特性的k維的子空間，故（n，k）循環(huán)碼的生成矩陣可用碼空間中任一組k個(gè)線(xiàn)性無(wú)關(guān)的碼字構(gòu)成，即k個(gè)線(xiàn)性無(wú)關(guān)的碼字構(gòu)成（n，k）循環(huán)碼的基底，基底不唯一。如何得到k個(gè)線(xiàn)性無(wú)關(guān)的碼字？

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

→構(gòu)成基底

若：

則：

13二．循環(huán)碼的生成矩陣（n，k）循環(huán)碼是n維線(xiàn)性空間一個(gè)具有循各多項(xiàng)式對(duì)應(yīng)的矢量分別為：

這k個(gè)矢量是線(xiàn)性無(wú)關(guān)的，且由g（x）循環(huán)移位得到，故都是碼字，由它們構(gòu)成一個(gè)k×n的矩陣，它們就是循環(huán)碼的生成矩陣。

14各多項(xiàng)式對(duì)應(yīng)的矢量分別為：這k個(gè)矢量是線(xiàn)性無(wú)關(guān)的，且由g（【例】（7，4）循環(huán)碼：

當(dāng)一個(gè)循環(huán)碼的生成矩陣確定后，其編碼規(guī)則為：

如：15【例】（7，4）循環(huán)碼：當(dāng)一個(gè)循環(huán)碼的生成矩陣確定后，其編（次數(shù)）

設(shè)：

則：三．循環(huán)碼的系統(tǒng)碼由上述方法作出的生成矩陣所編出的碼不是系統(tǒng)形式，如何得到系統(tǒng)形式的循環(huán)碼？1．系統(tǒng)循環(huán)碼的編碼：設(shè)

用xn–k和u（x）相乘，再除以g(x)16（次數(shù)）設(shè)：則：三．循環(huán)碼的系統(tǒng)碼由上述方法作a(x)g(x)是g(x)的一個(gè)倍式，則它是一個(gè)碼多項(xiàng)式，對(duì)應(yīng)的碼矢量為：碼矢量為系統(tǒng)形式的碼字，信息位在尾部。※系統(tǒng)碼的編碼步驟：(1)將k個(gè)消息位按升冪排列的次序?qū)懗上⒍囗?xiàng)式u（x）

；(2)用xn–k乘以u(píng)（x）得到一個(gè)次數(shù)的多項(xiàng)式；(3)用生成多項(xiàng)式g（x）除xn–k

u（x）得余b（x）（一致校驗(yàn)元）；(4)聯(lián)合b(x)和xn–k

u(x)得到系統(tǒng)碼多項(xiàng)式v(x)=b(x)+xn–k

u(x)；(5)將碼多項(xiàng)式轉(zhuǎn)換為碼字。17a(x)g(x)是g(x)的一個(gè)倍式，則它是一個(gè)碼多項(xiàng)式，對(duì)【例】（7，4）循環(huán)碼：

求

的系統(tǒng)碼字。

，

【解】

，n＝7，k＝4

（1）

（2）（3）（4）18【例】（7，4）循環(huán)碼：求的系統(tǒng)碼字。，【解】，n2．系統(tǒng)碼的生成矩陣（1）由生成矩陣做初等行變換，將其變?yōu)樾问剑礊橄到y(tǒng)形式的生成矩陣（單位陣在后，信息位在尾部）。

，求系統(tǒng)形式的生成矩陣。

【例】（7，4）循環(huán)碼：

（2）分別求g（x）除的余式（記為），由余式對(duì)應(yīng)的矢量作行矢量構(gòu)成的k×n-k的分塊矩陣P聯(lián)合k×k的單位陣I就構(gòu)成系統(tǒng)形式的生成矩陣：192．系統(tǒng)碼的生成矩陣（1）由生成矩陣做初等行變換，將其變?yōu)椋笙到y(tǒng)形式的生成矩陣。

【例】（7，4）循環(huán)碼：

20，求系統(tǒng)形式的生成矩陣?！纠浚?，4）循環(huán)碼：20四．循環(huán)碼的校驗(yàn)矩陣一般情況下，多項(xiàng)式xn+1可因式分解為xn+1=g(x)·h(x)

g(x)—（n，k）循環(huán)碼的生成多項(xiàng)式，

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

循環(huán)碼C的對(duì)偶碼C⊥的基底由

構(gòu)成。

21四．循環(huán)碼的校驗(yàn)矩陣一般情況下，多項(xiàng)式xn+1可因式分解為x設(shè)

則：將上述矢量按逆序排列作為一個(gè)（n-k）×n矩陣的行矢量，則該矩陣就是碼C的校驗(yàn)矩陣。22設(shè)則：將上述矢量按逆序排列作為一個(gè)（n-k）×n矩陣的行矢【例】（7，4）循環(huán)碼：

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

23【例】（7，4）循環(huán)碼：則：C⊥的基底（n-k-1=2）※系統(tǒng)形式的校驗(yàn)矩陣

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

24※系統(tǒng)形式的校驗(yàn)矩陣（1）對(duì)非系統(tǒng)形式的校驗(yàn)矩陣作初等行【例】（7，4）循環(huán)碼：

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

（3）25【例】（7，4）循環(huán)碼：（1）（2）k=4，n–k§8.3循環(huán)碼的編碼

循環(huán)碼是線(xiàn)性分組碼的一個(gè)子類(lèi)，因此循環(huán)碼可以按一般線(xiàn)性分組碼利用常用的組合邏輯電路來(lái)實(shí)現(xiàn)編碼。但對(duì)于線(xiàn)性分組碼，當(dāng)其信息位分組長(zhǎng)度較長(zhǎng)，編碼位數(shù)較多時(shí)，其編碼電路非常復(fù)雜。由于循環(huán)碼具有循環(huán)特性，其編碼器通常用簡(jiǎn)單的具有反饋連接的移位寄存器就可以實(shí)現(xiàn)，大大簡(jiǎn)化了編碼器的復(fù)雜度。利用具有反饋連接的移位寄存器實(shí)現(xiàn)的循環(huán)碼編碼電路，實(shí)際上是多項(xiàng)式運(yùn)算電路。首先研究多項(xiàng)式運(yùn)算電路。26§8.3循環(huán)碼的編碼循環(huán)碼是線(xiàn)性分組一．G(F2)上的多項(xiàng)式除法電路

設(shè)（被除式）（除式）q(x)→商，r(x)→余除法電路：27一．G(F2)上的多項(xiàng)式除法電路設(shè)（被除式）（除式）q（1）除法電路的結(jié)構(gòu)由除式b（x）決定；（2）組成：由r個(gè)存儲(chǔ)單元組成r級(jí)移位寄存器（D0～Dr-1）bi：常乘器，（bi=1，輸出＝輸入；bi=0，輸出＝0）當(dāng)bi=1，對(duì)應(yīng)支路連通（直通）；當(dāng)bi=0，對(duì)應(yīng)支路斷開(kāi)，對(duì)應(yīng)的模2加法器可去掉。

故：電路有r個(gè)移位寄存器，最多r+1個(gè)常乘器，最多r個(gè)模2加法器。說(shuō)明：28（1）除法電路的結(jié)構(gòu)由除式b（x）決定；說(shuō)明：28（3）工作原理簡(jiǎn)述：①電路清零，被除式系數(shù)按高次到低次依次進(jìn)入電路（ak首先進(jìn)入），r次移位后，移存器自右至左內(nèi)容為：（a

k，a

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

k

b

r或ak

b

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

n-k，u(x)應(yīng)從n-k級(jí)移存器的最前端輸入。31二．循環(huán)碼編碼器1．基于生成多項(xiàng)式g（x）的編碼器（n－k級(jí)編碼過(guò)程：（1）門(mén)打開(kāi)，k接“1”，消息數(shù)據(jù)uk-1,...

u0移入電路，并同時(shí)送入信道，一旦k個(gè)消息全部移入電路，移存器中的n-k個(gè)數(shù)據(jù)就構(gòu)成了余式的系數(shù)；（2）門(mén)關(guān)，斷開(kāi)反饋連接，k接“2”；（3）移出移存器中的數(shù)據(jù)(校驗(yàn)元)，并送入信道，與k個(gè)信息位組成碼字。32編碼過(guò)程：（1）門(mén)打開(kāi)，k接“1”，消息數(shù)據(jù)uk-1,【例】（7，4）循環(huán)碼，

若：33【例】（7，4）循環(huán)碼，若：33編碼過(guò)程：（k＝4）節(jié)拍輸入D0D1D2輸出門(mén)開(kāi)，k→1010001111012010113110004－1001門(mén)關(guān)，k→25－01006－00107－000134編碼過(guò)程：（k＝4）節(jié)拍輸入D0D1D2輸出門(mén)開(kāi)，k→1012．基于校驗(yàn)多項(xiàng)式h（x）的編碼器（k級(jí)編碼器）編碼器電路的結(jié)構(gòu)由校驗(yàn)多項(xiàng)式?jīng)Q定，生成多項(xiàng)式h(x)的最高次數(shù)為k，故編碼器有k級(jí)移存器，故稱(chēng)

k級(jí)編碼器。編碼器電路編碼過(guò)程（1）門(mén)1打開(kāi)，門(mén)2關(guān)閉，k位消息數(shù)據(jù)u0，u1，...，uk-1移入電路，并同時(shí)送入信道；（2）k位消息全部移入，門(mén)1關(guān)，門(mén)2開(kāi)；（3）以后的每次移位產(chǎn)生一個(gè)校驗(yàn)元并送入信道，直到n－k個(gè)校驗(yàn)元全部產(chǎn)生并送入信道為止。然后門(mén)2關(guān)，門(mén)1開(kāi)，準(zhǔn)備下一組消息編碼；352．基于校驗(yàn)多項(xiàng)式h（x）的編碼器（k級(jí)編碼器）編碼器電路的【例】（7，4）循環(huán)碼，

k＝4級(jí)編碼器編碼過(guò)程

輸入節(jié)拍D0D1D2D3輸出門(mén)1開(kāi)，門(mén)2關(guān)100000111000102010001310101－411011門(mén)1關(guān)，門(mén)2開(kāi)－501100－600110－70001036【例】（7，4）循環(huán)碼，k＝4級(jí)編碼器編碼過(guò)程輸入節(jié)拍D3．兩種編碼器的比較（1）基于g（x）的編碼器為n－k級(jí)編碼器，需要n－k級(jí)移存器；基于h（x）的編碼器為k級(jí)編碼器，需要k級(jí)移存器。（2）當(dāng)n－k<k時(shí)，采用n－k級(jí)編碼器需要資源少；當(dāng)n－k>k時(shí)，采用k級(jí)編碼器需要資源少。

373．兩種編碼器的比較（1）基于g（x）的編碼器為n－k級(jí)編碼§8.4循環(huán)碼譯碼

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

(x)找出相應(yīng)錯(cuò)誤圖樣多項(xiàng)式e(x)；（3）將e

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

(x)

。二．伴隨式計(jì)算及錯(cuò)誤檢測(cè)1．伴隨式及計(jì)算設(shè)接收多項(xiàng)式為r(x)，碼多項(xiàng)式為v(x)，錯(cuò)誤圖樣多項(xiàng)式為e(x)，則用生成多項(xiàng)式g（x）除r（x），得

（求余運(yùn)算）

38§8.4循環(huán)碼譯碼一．譯碼步驟：和線(xiàn)性分組碼一樣，循環(huán)【定理】設(shè)g(x)是(n，k)系統(tǒng)循環(huán)碼的生成多項(xiàng)式，接收字多項(xiàng)式為r(x)，對(duì)應(yīng)錯(cuò)誤圖樣為e(x),則

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

可見(jiàn)，循環(huán)碼的伴隨式計(jì)算電路就是一個(gè)接收多項(xiàng)式r(x)除以生成多項(xiàng)式g（x）的除法電路。電路初始狀態(tài)為0，當(dāng)r(x)全部移入后，移存器中的內(nèi)容為伴隨式多項(xiàng)式s(x)。

39【定理】設(shè)g(x)是(n，k)系統(tǒng)循環(huán)碼的生成多項(xiàng)式，接收2．伴隨式計(jì)算電路的性質(zhì)由于碼的循環(huán)結(jié)構(gòu)，伴隨式有個(gè)重要的性質(zhì)，用定理描述。

【定理】設(shè)s(x)是r(x)的伴隨式，則r(x)的循環(huán)移位x·r(x)的伴隨式s(1)(x)是s(x)在伴隨式計(jì)算電路中無(wú)輸入時(shí)右移一位的結(jié)果，即：【推論】用生成多項(xiàng)式g(x)除x

is(x)所得余式s(i)(x)是r(x)經(jīng)i次移位后r(i)(x)的伴隨式。說(shuō)明：把含有s(x)的伴隨式移存器的輸入門(mén)斷開(kāi)，移位一次就得到r(1)(x)的伴隨式s(1)(x)

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

。402．伴隨式計(jì)算電路的性質(zhì)由于碼的循環(huán)結(jié)構(gòu)，伴隨式有個(gè)重要的性【例】（7，4）循環(huán)碼，計(jì)算對(duì)應(yīng)的伴隨式。伴隨式計(jì)算電路計(jì)算過(guò)程：（開(kāi)始時(shí)，移存器清零）節(jié)拍輸入S0S1S2節(jié)拍輸入S0S1S210000601112110070101s311108—100s(1)400119—010s(2)5101141【例】（7，4）循環(huán)碼，計(jì)算對(duì)應(yīng)的伴隨式。伴隨式計(jì)算電路計(jì)算由

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

2．錯(cuò)誤糾正過(guò)程

（1）開(kāi)始譯碼時(shí)，門(mén)開(kāi)，移存器和伴隨式計(jì)算電路清零，接收字r（x）一方面送入n級(jí)緩存，一方面送入伴隨式計(jì)算電路，形成伴隨式。當(dāng)n位數(shù)據(jù)接收完后，門(mén)關(guān)，禁止輸入。44三．循環(huán)碼一般譯碼器1．組成：（三部分）（梅吉特：Meggi（2）將伴隨式輸入錯(cuò)誤圖樣檢測(cè)電路，找出對(duì)應(yīng)的錯(cuò)誤圖樣。

方法：當(dāng)且僅當(dāng)緩存器中最高位出錯(cuò)時(shí)，組合邏輯電路輸出才為“1”，即，若檢測(cè)電路輸出為“1”，說(shuō)明緩存中最高位的數(shù)據(jù)是錯(cuò)誤的，需要糾正。這時(shí)輸出的“1”同時(shí)反饋到伴隨式計(jì)算電路，對(duì)伴隨式進(jìn)行修正，消除該錯(cuò)誤對(duì)伴隨式的影響（修正后為高位無(wú)錯(cuò)對(duì)應(yīng)的伴隨式）。（3）如高位無(wú)錯(cuò)誤，組合電路輸出“0”，高位無(wú)需糾正，然后，伴隨式計(jì)算電路和緩存各移位一次，這是高位輸出。同時(shí)，接收字第二位移到緩存最高位，而伴隨式計(jì)算電路得到此高位伴隨式，用來(lái)檢測(cè)接收字的次高位，即緩存最右一位是否有錯(cuò)。如有錯(cuò)，組合電路輸出“1”與緩存輸出相加，完成第二個(gè)碼元的糾錯(cuò)，如無(wú)錯(cuò)，則重復(fù)上述過(guò)程，一直譯完一個(gè)碼字為止。45（2）將伴隨式輸入錯(cuò)誤圖樣檢測(cè)電路，找出對(duì)應(yīng)的錯(cuò)誤圖樣。方【例】（7，4）循環(huán)碼，dmin(C)=3，可以糾正一個(gè)錯(cuò)誤。

所有單重錯(cuò)誤的錯(cuò)誤圖樣：

錯(cuò)誤圖樣伴隨式對(duì)應(yīng)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)=11100146【例】（7，4）循環(huán)碼，dmin(C)=3，可以糾正一個(gè)錯(cuò)誤由上表可知：最高位x6出錯(cuò)的伴隨式為1+x2，因此，識(shí)別最高位x6是否出錯(cuò)，只要識(shí)別所對(duì)應(yīng)的伴隨式是否為1+x2。譯碼電路如下：

設(shè)

錯(cuò)誤圖樣伴隨式（0000001）e6(x)=x61+x2101（0000010）e5(x)=x51+x+x2111（0000100）e4(x)=x4x+x2011（0001000）e3(x)=x31+x110（0010000）e2(x)=x2x2001（0100000）e1(x)=xx010（1000000）e0(x)=1110031)(xxxg++=47由上表可知：最高位x6出錯(cuò)的伴隨式為1+x2，因此，識(shí)別最高譯碼過(guò)程：（1100111）

節(jié)拍輸入S0S1S2與門(mén)輸出緩存內(nèi)容譯碼輸出（門(mén)1、2開(kāi)，3關(guān)）00000111000211100311110401010501000611100711110（門(mén)1、2關(guān)，3開(kāi)）81010110011119000111100110100000011100111101011100012001011100130001011111401001011131)(xxxg++=48譯碼過(guò)程：（1100111）節(jié)拍輸入S0S1S2與門(mén)輸出緩§8.5一些重要的循環(huán)碼一.循環(huán)Hamming碼定義9.3設(shè)是GF(2m)上的一個(gè)本原元，則以的本原多項(xiàng)式為生成多項(xiàng)式的（2m－1，2m－1－m）Hamming碼是循環(huán)碼。碼的校驗(yàn)矩陣為

本原元在GF(q)中，某一元素

的階為q-1，即q-1=e(q–1是使等式成立的最小正整數(shù))，則稱(chēng)

為本原元。本原元多項(xiàng)式是以本原元為根的即約多項(xiàng)式。即約多項(xiàng)式階大于0且在給定集合F上除了常數(shù)和常數(shù)與本身的乘積外，不能被其它多項(xiàng)式除盡的多項(xiàng)式49§8.5一些重要的循環(huán)碼一.循環(huán)Hamming碼定義9.第八章循環(huán)碼50第八章1內(nèi)容提要循環(huán)碼是線(xiàn)性分組碼中一個(gè)重要的子類(lèi)。本章將介紹循環(huán)碼的基本概念以及循環(huán)碼的多項(xiàng)式描述方法；循環(huán)碼的基本定理及其矩陣描述

；簡(jiǎn)單的循環(huán)碼的編譯碼方法及其實(shí)現(xiàn)電路。51內(nèi)容提要循環(huán)碼是線(xiàn)性分組碼中一個(gè)重要的子類(lèi)。2§8.1循環(huán)碼的概念一．定義

設(shè)一個(gè)（n，k）線(xiàn)性分組碼C，如果它的任一碼字的每一次循環(huán)移位都還是C的一個(gè)碼字，則稱(chēng)C是循環(huán)碼。由于循環(huán)碼是線(xiàn)性分組碼，所有這些具有循環(huán)關(guān)系的碼字的全體構(gòu)成了n維矢量空間中具有循環(huán)特性的k維子空間。52§8.1循環(huán)碼的概念一．定義設(shè)一個(gè)（n，k）線(xiàn)性分組碼C，【例】（7，3）線(xiàn)性分組碼由：得由兩組碼字循環(huán)構(gòu)成的循環(huán)碼。

53【例】（7，3）線(xiàn)性分組碼由：二．循環(huán)碼的數(shù)學(xué)描述1．循環(huán)碼的特點(diǎn)：（1）它是線(xiàn)性分組碼，其數(shù)學(xué)模型應(yīng)具有線(xiàn)性特性；（2）具有循環(huán)特性。

故循環(huán)碼的數(shù)學(xué)模型必須能兼具線(xiàn)性和循環(huán)特性→多項(xiàng)式描述。2．線(xiàn)性分組碼的多項(xiàng)式描述字：

字多項(xiàng)式

碼字：

碼字多項(xiàng)式

對(duì)于線(xiàn)性分組碼C，可以表示成碼字多項(xiàng)式構(gòu)成的集合：

54二．循環(huán)碼的數(shù)學(xué)描述1．循環(huán)碼的特點(diǎn)：（1）它是線(xiàn)性分組碼，3．循環(huán)特性的表示以前面的（7，3）循環(huán)碼為例：（任取一碼字）移一位移兩位移三位?此時(shí)：7>n-1=6，超出了n=7的矢量空間。

要求：

則：，即553．循環(huán)特性的表示以前面的（7，3）循環(huán)碼為例：（任取一碼字下面用去除，得余對(duì)于上面第三次移位結(jié)果，可重新表示如下：

結(jié)論：如果將一個(gè)循環(huán)碼的某一非零碼字用碼多項(xiàng)式表示出來(lái)，那么其他的非零碼字多項(xiàng)式就可以用這個(gè)碼字多項(xiàng)式（或碼字多項(xiàng)式的和）乘上x(chóng)的一個(gè)冪，再求（xn+1）的余得到。說(shuō)明：一個(gè)碼字的移位最多能得到n個(gè)碼字，因此“循環(huán)碼字的循環(huán)仍是碼字”并不意味著循環(huán)碼集可以從一個(gè)碼字循環(huán)而得，還應(yīng)包含碼字的一些線(xiàn)性組合。56下面用去除§8.2循環(huán)碼的基本定理及其矩陣描述

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

gn-k=1

）（gn-k=1）

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

且所有小于n次的g(x)的倍式都是碼多項(xiàng)式。故循環(huán)碼完全由它的生成多項(xiàng)式確定。57§8.2循環(huán)碼的基本定理及其矩陣描述一．循環(huán)碼的生成多項(xiàng)（2）（n，k）循環(huán)碼的生成多項(xiàng)式g(x)一定是(xn+1)的因子，即

或?qū)懗上喾?，如果g(x)是xn+1的n-k次因子，則g(x)一定是（n，k）循環(huán)碼的生成多項(xiàng)式。生成多項(xiàng)式不唯一。2．（n，k）循環(huán)碼的構(gòu)造（1）對(duì)(xn+1)做因式分解，找出(n–k)次因式；（2）以該(n–k)次因式為生成多項(xiàng)式g(x)與不高于k–1次信息多項(xiàng)式u(x)相乘，即得到對(duì)應(yīng)消息序列的碼多項(xiàng)式。58（2）（n，k）循環(huán)碼的生成多項(xiàng)式g(x)一定是(xn+1)【例】一個(gè)長(zhǎng)度n=7的循環(huán)碼的構(gòu)造方法。（1）對(duì)x7+1作因式分解

故x7+1有如下因式：

一次因式：

三次因式：

四次因式：

六次因式：

（一個(gè)）

（兩個(gè)）

（一個(gè)）

（兩個(gè)）

59【例】一個(gè)長(zhǎng)度n=7的循環(huán)碼的構(gòu)造方法。（1）對(duì)x7n–k=1，k=6，生成一種（7，6）循環(huán)碼；n–k=3，k=4，生成兩種（7，4）循環(huán)碼；n–k=4，k=3，生成兩種（7，3）循環(huán)碼；n–k=6，k=1，生成一種（7，1）循環(huán)碼；例：要得到一（7，4）循環(huán)碼，可選n–k=3次多項(xiàng)式1+x2+x3或1+x+x3

為生成多項(xiàng)式：

以g（x）=1+x2+x3為例，（信息位長(zhǎng)度為4）

設(shè)信息多項(xiàng)式為：

則：循環(huán)碼編碼后的碼多項(xiàng)式為：

（2）若以n-k次因式作為生成多項(xiàng)式，可供選擇的有60n–k=1，k=6，生成一種（7，6）循環(huán)碼；例例：

對(duì)于上述（7，4）循環(huán)碼，有4個(gè)信息位，對(duì)應(yīng)有16個(gè)信息序列，利用16個(gè)信息序列多項(xiàng)式與生成多項(xiàng)式的乘法運(yùn)算，可得全部（7，4）循環(huán)碼得16個(gè)碼字，如表：信息位碼字信息位碼字信息位碼字信息位碼字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循環(huán)組1循環(huán)組2循環(huán)組3循環(huán)組4任何碼字的循環(huán)移位仍是碼字，并非由一個(gè)碼字循環(huán)移位可以得到所有碼字，上述（7，4）碼的碼集由4組碼字循環(huán)構(gòu)成。結(jié)論：當(dāng)一個(gè)循環(huán)碼給定其生成多項(xiàng)式g（x）后，根據(jù)生成多項(xiàng)式就可以進(jìn)行編碼（但編出的碼不一定為系統(tǒng)碼）61例：對(duì)于上述（7，4）循環(huán)碼，有4個(gè)信息位，對(duì)應(yīng)有16個(gè)信二．循環(huán)碼的生成矩陣（n，k）循環(huán)碼是n維線(xiàn)性空間一個(gè)具有循環(huán)特性的k維的子空間，故（n，k）循環(huán)碼的生成矩陣可用碼空間中任一組k個(gè)線(xiàn)性無(wú)關(guān)的碼字構(gòu)成，即k個(gè)線(xiàn)性無(wú)關(guān)的碼字構(gòu)成（n，k）循環(huán)碼的基底，基底不唯一。如何得到k個(gè)線(xiàn)性無(wú)關(guān)的碼字？

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

→構(gòu)成基底

若：

則：

62二．循環(huán)碼的生成矩陣（n，k）循環(huán)碼是n維線(xiàn)性空間一個(gè)具有循各多項(xiàng)式對(duì)應(yīng)的矢量分別為：

這k個(gè)矢量是線(xiàn)性無(wú)關(guān)的，且由g（x）循環(huán)移位得到，故都是碼字，由它們構(gòu)成一個(gè)k×n的矩陣，它們就是循環(huán)碼的生成矩陣。

63各多項(xiàng)式對(duì)應(yīng)的矢量分別為：這k個(gè)矢量是線(xiàn)性無(wú)關(guān)的，且由g（【例】（7，4）循環(huán)碼：

當(dāng)一個(gè)循環(huán)碼的生成矩陣確定后，其編碼規(guī)則為：

如：64【例】（7，4）循環(huán)碼：當(dāng)一個(gè)循環(huán)碼的生成矩陣確定后，其編（次數(shù)）

設(shè)：

則：三．循環(huán)碼的系統(tǒng)碼由上述方法作出的生成矩陣所編出的碼不是系統(tǒng)形式，如何得到系統(tǒng)形式的循環(huán)碼？1．系統(tǒng)循環(huán)碼的編碼：設(shè)

用xn–k和u（x）相乘，再除以g(x)65（次數(shù)）設(shè)：則：三．循環(huán)碼的系統(tǒng)碼由上述方法作a(x)g(x)是g(x)的一個(gè)倍式，則它是一個(gè)碼多項(xiàng)式，對(duì)應(yīng)的碼矢量為：碼矢量為系統(tǒng)形式的碼字，信息位在尾部。※系統(tǒng)碼的編碼步驟：(1)將k個(gè)消息位按升冪排列的次序?qū)懗上⒍囗?xiàng)式u（x）

；(2)用xn–k乘以u(píng)（x）得到一個(gè)次數(shù)的多項(xiàng)式；(3)用生成多項(xiàng)式g（x）除xn–k

u（x）得余b（x）（一致校驗(yàn)元）；(4)聯(lián)合b(x)和xn–k

u(x)得到系統(tǒng)碼多項(xiàng)式v(x)=b(x)+xn–k

u(x)；(5)將碼多項(xiàng)式轉(zhuǎn)換為碼字。66a(x)g(x)是g(x)的一個(gè)倍式，則它是一個(gè)碼多項(xiàng)式，對(duì)【例】（7，4）循環(huán)碼：

求

的系統(tǒng)碼字。

，

【解】

，n＝7，k＝4

（1）

（2）（3）（4）67【例】（7，4）循環(huán)碼：求的系統(tǒng)碼字。，【解】，n2．系統(tǒng)碼的生成矩陣（1）由生成矩陣做初等行變換，將其變?yōu)樾问?，即為系統(tǒng)形式的生成矩陣（單位陣在后，信息位在尾部）。

，求系統(tǒng)形式的生成矩陣。

【例】（7，4）循環(huán)碼：

（2）分別求g（x）除的余式（記為），由余式對(duì)應(yīng)的矢量作行矢量構(gòu)成的k×n-k的分塊矩陣P聯(lián)合k×k的單位陣I就構(gòu)成系統(tǒng)形式的生成矩陣：682．系統(tǒng)碼的生成矩陣（1）由生成矩陣做初等行變換，將其變?yōu)?，求系統(tǒng)形式的生成矩陣。

【例】（7，4）循環(huán)碼：

69，求系統(tǒng)形式的生成矩陣。【例】（7，4）循環(huán)碼：20四．循環(huán)碼的校驗(yàn)矩陣一般情況下，多項(xiàng)式xn+1可因式分解為xn+1=g(x)·h(x)

g(x)—（n，k）循環(huán)碼的生成多項(xiàng)式，

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

循環(huán)碼C的對(duì)偶碼C⊥的基底由

構(gòu)成。

70四．循環(huán)碼的校驗(yàn)矩陣一般情況下，多項(xiàng)式xn+1可因式分解為x設(shè)

則：將上述矢量按逆序排列作為一個(gè)（n-k）×n矩陣的行矢量，則該矩陣就是碼C的校驗(yàn)矩陣。71設(shè)則：將上述矢量按逆序排列作為一個(gè)（n-k）×n矩陣的行矢【例】（7，4）循環(huán)碼：

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

72【例】（7，4）循環(huán)碼：則：C⊥的基底（n-k-1=2）※系統(tǒng)形式的校驗(yàn)矩陣

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

73※系統(tǒng)形式的校驗(yàn)矩陣（1）對(duì)非系統(tǒng)形式的校驗(yàn)矩陣作初等行【例】（7，4）循環(huán)碼：

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

（3）74【例】（7，4）循環(huán)碼：（1）（2）k=4，n–k§8.3循環(huán)碼的編碼

循環(huán)碼是線(xiàn)性分組碼的一個(gè)子類(lèi)，因此循環(huán)碼可以按一般線(xiàn)性分組碼利用常用的組合邏輯電路來(lái)實(shí)現(xiàn)編碼。但對(duì)于線(xiàn)性分組碼，當(dāng)其信息位分組長(zhǎng)度較長(zhǎng)，編碼位數(shù)較多時(shí)，其編碼電路非常復(fù)雜。由于循環(huán)碼具有循環(huán)特性，其編碼器通常用簡(jiǎn)單的具有反饋連接的移位寄存器就可以實(shí)現(xiàn)，大大簡(jiǎn)化了編碼器的復(fù)雜度。利用具有反饋連接的移位寄存器實(shí)現(xiàn)的循環(huán)碼編碼電路，實(shí)際上是多項(xiàng)式運(yùn)算電路。首先研究多項(xiàng)式運(yùn)算電路。75§8.3循環(huán)碼的編碼循環(huán)碼是線(xiàn)性分組一．G(F2)上的多項(xiàng)式除法電路

設(shè)（被除式）（除式）q(x)→商，r(x)→余除法電路：76一．G(F2)上的多項(xiàng)式除法電路設(shè)（被除式）（除式）q（1）除法電路的結(jié)構(gòu)由除式b（x）決定；（2）組成：由r個(gè)存儲(chǔ)單元組成r級(jí)移位寄存器（D0～Dr-1）bi：常乘器，（bi=1，輸出＝輸入；bi=0，輸出＝0）當(dāng)bi=1，對(duì)應(yīng)支路連通（直通）；當(dāng)bi=0，對(duì)應(yīng)支路斷開(kāi)，對(duì)應(yīng)的模2加法器可去掉。

故：電路有r個(gè)移位寄存器，最多r+1個(gè)常乘器，最多r個(gè)模2加法器。說(shuō)明：77（1）除法電路的結(jié)構(gòu)由除式b（x）決定；說(shuō)明：28（3）工作原理簡(jiǎn)述：①電路清零，被除式系數(shù)按高次到低次依次進(jìn)入電路（ak首先進(jìn)入），r次移位后，移存器自右至左內(nèi)容為：（a

k，a

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

k

b

r或ak

b

r-1），并反饋到前面作模2加運(yùn)算后存入各級(jí)寄存器中，以后每次移位輸出商的對(duì)應(yīng)次位的系數(shù)并反饋回去。③依次類(lèi)推，經(jīng)過(guò)k+1次移位后，完成整個(gè)除法運(yùn)算，最后輸出商常數(shù)項(xiàng)系數(shù)，此時(shí)移存器中的內(nèi)容就是余式r（x）各次項(xiàng)對(duì)應(yīng)的系數(shù)（高位寄存器對(duì)應(yīng)高次項(xiàng)系數(shù)）。78（3）工作原理簡(jiǎn)述：29【例】工作過(guò)程:(r=3)節(jié)拍輸入D0D1D2輸出清零010000111000201100r次300110r＋1次411111（x）k＋1次5-0011（x0）79【例】工作過(guò)程:(r=3)節(jié)拍輸入D0D1D2輸出清零01二．循環(huán)碼編碼器1．基于生成多項(xiàng)式g（x）的編碼器（n－k級(jí)編碼器）編碼器電路的結(jié)構(gòu)由生成多項(xiàng)式?jīng)Q定，生成多項(xiàng)式g（x）的最高次數(shù)為n-k，故編碼器有n-k級(jí)移存器，故稱(chēng)n-k級(jí)編碼器。對(duì)于循環(huán)碼的系統(tǒng)編碼，首先要得到u(x)xn-k除以g(x)的余式p(x)，再組合成系統(tǒng)碼，即：對(duì)于除法電路：一方面我們可以得到商，還可以得到余式。對(duì)于系統(tǒng)碼編碼我們可以先輸出信息位，再輸出余式（校驗(yàn)位）就可以得到系統(tǒng)碼，另外由于被除式為u(x)x

n-k，u(x)應(yīng)從n-k級(jí)移存器的最前端輸入。80二．循環(huán)碼編碼器1．基于生成多項(xiàng)式g（x）的編碼器（n－k級(jí)編碼過(guò)程：（1）門(mén)打開(kāi)，k接“1”，消息數(shù)據(jù)uk-1,...

u0移入電路，并同時(shí)送入信道，一旦k個(gè)消息全部移入電路，移存器中的n-k個(gè)數(shù)據(jù)就構(gòu)成了余式的系數(shù)；（2）門(mén)關(guān)，斷開(kāi)反饋連接，k接“2”；（3）移出移存器中的數(shù)據(jù)(校驗(yàn)元)，并送入信道，與k個(gè)信息位組成碼字。81編碼過(guò)程：（1）門(mén)打開(kāi)，k接“1”，消息數(shù)據(jù)uk-1,【例】（7，4）循環(huán)碼，

若：82【例】（7，4）循環(huán)碼，若：33編碼過(guò)程：（k＝4）節(jié)拍輸入D0D1D2輸出門(mén)開(kāi)，k→1010001111012010113110004－1001門(mén)關(guān)，k→25－01006－00107－000183編碼過(guò)程：（k＝4）節(jié)拍輸入D0D1D2輸出門(mén)開(kāi)，k→1012．基于校驗(yàn)多項(xiàng)式h（x）的編碼器（k級(jí)編碼器）編碼器電路的結(jié)構(gòu)由校驗(yàn)多項(xiàng)式?jīng)Q定，生成多項(xiàng)式h(x)的最高次數(shù)為k，故編碼器有k級(jí)移存器，故稱(chēng)

k級(jí)編碼器。編碼器電路編碼過(guò)程（1）門(mén)1打開(kāi)，門(mén)2關(guān)閉，k位消息數(shù)據(jù)u0，u1，...，uk-1移入電路，并同時(shí)送入信道；（2）k位消息全部移入，門(mén)1關(guān)，門(mén)2開(kāi)；（3）以后的每次移位產(chǎn)生一個(gè)校驗(yàn)元并送入信道，直到n－k個(gè)校驗(yàn)元全部產(chǎn)生并送入信道為止。然后門(mén)2關(guān)，門(mén)1開(kāi)，準(zhǔn)備下一組消息編碼；842．基于校驗(yàn)多項(xiàng)式h（x）的編碼器（k級(jí)編碼器）編碼器電路的【例】（7，4）循環(huán)碼，

k＝4級(jí)編碼器編碼過(guò)程

輸入節(jié)拍D0D1D2D3輸出門(mén)1開(kāi)，門(mén)2關(guān)100000111000102010001310101－411011門(mén)1關(guān)，門(mén)2開(kāi)－501100－600110－70001085【例】（7，4）循環(huán)碼，k＝4級(jí)編碼器編碼過(guò)程輸入節(jié)拍D3．兩種編碼器的比較（1）基于g（x）的編碼器為n－k級(jí)編碼器，需要n－k級(jí)移存器；基于h（x）的編碼器為k級(jí)編碼器，需要k級(jí)移存器。（2）當(dāng)n－k<k時(shí)，采用n－k級(jí)編碼器需要資源少；當(dāng)n－k>k時(shí)，采用k級(jí)編碼器需要資源少。

863．兩種編碼器的比較（1）基于g（x）的編碼器為n－k級(jí)編碼§8.4循環(huán)碼譯碼

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

(x)找出相應(yīng)錯(cuò)誤圖樣多項(xiàng)式e(x)；（3）將e

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

(x)

。二．伴隨式計(jì)算及錯(cuò)誤檢測(cè)1．伴隨式及計(jì)算設(shè)接收多項(xiàng)式為r(x)，碼多項(xiàng)式為v(x)，錯(cuò)誤圖樣多項(xiàng)式為e(x)，則用生成多項(xiàng)式g（x）除r（x），得

（求余運(yùn)算）

87§8.4循環(huán)碼譯碼一．譯碼步驟：和線(xiàn)性分組碼一樣，循環(huán)【定理】設(shè)g(x)是(n，k)系統(tǒng)循環(huán)碼的生成多項(xiàng)式，接收字多項(xiàng)式為r(x)，對(duì)應(yīng)錯(cuò)誤圖樣為e(x),則

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

可見(jiàn)，循環(huán)碼的伴隨式計(jì)算電路就是一個(gè)接收多項(xiàng)式r(x)除以生成多項(xiàng)式g（x）的除法電路。電路初始狀態(tài)為0，當(dāng)r(x)全部移入后，移存器中的內(nèi)容為伴隨式多項(xiàng)式s(x)。

88【定理】設(shè)g(x)是(n，k)系統(tǒng)循環(huán)碼的生成多項(xiàng)式，接收2．伴隨式計(jì)算電路的性質(zhì)由于碼的循環(huán)結(jié)構(gòu)，伴隨式有個(gè)重要的性質(zhì)，用定理描述。

【定理】設(shè)s(x)是r(x)的伴隨式，則r(x)的循環(huán)移位x·r(x)的伴隨式s(1)(x)是s(x)在伴隨式計(jì)算電路中無(wú)輸入時(shí)右移一位的結(jié)果，即：【推論】用生成多項(xiàng)式g(x)除x

is(x)所得余式s(i)(x)是r(x)經(jīng)i次移位后r(i)(x)的伴隨式。說(shuō)明：把含有s(x)的伴隨式移存器的輸入門(mén)斷開(kāi)，移位一次就得到r(1)(x)的伴隨式s(1)(x)

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

。892．伴隨式計(jì)算電路的性質(zhì)由于碼的循環(huán)結(jié)構(gòu)，伴隨式有個(gè)重要的性【例】（7，4）循環(huán)碼，計(jì)算對(duì)應(yīng)的伴隨式。伴隨式計(jì)算電路計(jì)算過(guò)程：（開(kāi)始時(shí)，移存器清零）節(jié)拍輸入S0S1S2節(jié)拍輸入S0S1S210000601112110070101s311108—100s(1)400119—010s(2)5101190【例】（7，4）循環(huán)碼，計(jì)算對(duì)應(yīng)的伴隨式。伴隨式計(jì)算電路計(jì)算由