信息論與編碼補充循環(huán)碼

信息論與編碼補充循環(huán)碼1第一頁，共六十頁，2022年，8月28日內(nèi)容提要循環(huán)碼是線性分組碼中一個重要的子類。將介紹循環(huán)碼的基本概念以及循環(huán)碼的多項式描述方法；循環(huán)碼的基本定理及其矩陣描述

；簡單的循環(huán)碼的編譯碼方法及其實現(xiàn)電路。2第二頁，共六十頁，2022年，8月28日多項式的引入如果將碼字描述成n階多項式的形式，A(x)=an-1xn-1+an-2xn-2+an-3xn-3+…+a2x2+a1,x+a0，則循環(huán)算法就可以描述為L(A(x))=xA(x)mod(xn-1)便于描述：對任何一個多項式D(x)，有D(x)A(x)mod(xn-1)為許用碼字，這里并沒有限定D(x)的冪次，但可以肯定的一點是不同的D(x)A(x)mod(xn-1)是有限的，其個數(shù)由A(x)決定，這也決定了碼集的冗余度和糾錯能力，什么樣的A(x)可以得到什么樣的冗余度？哪些A(x)是等價的？復(fù)習(xí)幾個概念:同余、剩余類;群;環(huán);域第三頁，共六十頁，2022年，8月28日同余和剩余類同余：若整數(shù)a和b被同一正整數(shù)m除時，有相同的余數(shù)，則稱a、b關(guān)于模m同余，記為剩余類(Residue)：給定正整數(shù)m，可將全體整數(shù)按余數(shù)相同進行分類，可獲得m個剩余類，分別用第四頁，共六十頁，2022年，8月28日群(Group)的定義

設(shè)G是一個非空集合，并在G內(nèi)定義了一種代數(shù)運算“?！?，若滿足：1)封閉性。對任意，恒有2)結(jié)合律。對任意，恒有3)G中存在一恒等元e,對任意，使4)對任意，存在a的逆元，使則稱G構(gòu)成一個群。若加法，恒等元用0表示，若為乘法，恒等元稱為單位元第五頁，共六十頁，2022年，8月28日環(huán)(Ring)的定義非空集合R中，若定義了兩種代數(shù)運算加和乘，且滿足：

1)集合R在加法運算下構(gòu)成阿貝爾群

2)乘法有封閉性

3)乘法結(jié)合律成立，且加和乘之間有分配律阿貝爾群，又稱交換群或可交換群，是這樣一類群(G,*)：對任意a，b屬于G，滿足a*b=b*a。阿貝爾群以挪威數(shù)學(xué)家尼爾斯·阿貝爾命名。第六頁，共六十頁，2022年，8月28日子環(huán)、理想和主理想子環(huán)：若環(huán)R中的子集S，在環(huán)R中的定義的代數(shù)運算也構(gòu)成環(huán)，則稱S為R的子環(huán)。理想：S是R的一個子環(huán)，若S中的元素由某幾個元素及其所有可能的倍數(shù)構(gòu)成，則S是一個理想.主理想：若理想中的元素由一個元素的所有倍數(shù)及其線性組合生成，則稱這個理想為主理想。第七頁，共六十頁，2022年，8月28日多項式

f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…n，該多項式稱為域Fp上的多項式多項式次數(shù)degf(x)

系數(shù)不為零的x的最高次數(shù)稱為多項式f(x)的次數(shù)首一多項式最高次數(shù)的系數(shù)為1的多項式有關(guān)多項式的幾個概念第八頁，共六十頁，2022年，8月28日

既約多項式設(shè)f(x)是次數(shù)大于零的多項式，若除常數(shù)和常數(shù)與本身的乘積以外，再不能被域Fp上的其他多項式整除，則稱f(x)為域Fp上的既約多項式

多項式的因式分解問題、根的問題有關(guān)多項式的幾個概念第九頁，共六十頁，2022年，8月28日f(x)=fnxn+fn-1xn-1+…+f1x+f0g(x)=gnxn+gn-1xn-1+…+g1x+g0若對所有i,fi=gi,則f(x)=g(x)多項式加法f(x)+g(x)=(fn+

gn)xn+(fn-1

+

gn-1)xn-1+…+(f1

+

g1)x+(f0

+

g0)多項式乘法結(jié)論：按上述定義的加法和乘法運算，F(xiàn)p[x]構(gòu)成一個具有單位元、無零因子的可換環(huán).多項式的加法和乘法第十頁，共六十頁，2022年，8月28日定義：以一個Fp上的多項式f(x)=fnxn+fn-1xn-1+…+f1x+f0為模的剩余類全體構(gòu)成一個多項式剩余類環(huán)

Fp上的所有次數(shù)小于n-1的多項式構(gòu)成n次多項式的剩余類全體

剩余類之間的加法和乘法運算規(guī)則多項式剩余類環(huán)第十一頁，共六十頁，2022年，8月28日有限域GF(2)上的運算定義12第十二頁，共六十頁，2022年，8月28日1、GF(2)上的多項式f(x)=x2+1的剩余類全體為：2、GF(2)上的多項式f(x)=x2+x+1的剩余類全體為：對所定義的加法和乘法運算，前者構(gòu)成剩余類環(huán)，后者構(gòu)成域.結(jié)論：若n次首一多項式f(x)在域Fp上既約，則f(x)的剩余類環(huán)構(gòu)成一個有pn個元素的有限域.Examples第十三頁，共六十頁，2022年，8月28日兩個結(jié)論多項式環(huán)Fp[x]的一切理想均是主理想多項式剩余類環(huán)Fp[x]/f(x)中的每一個理想都是主理想。第十四頁，共六十頁，2022年，8月28日

循環(huán)碼的概念一．定義

設(shè)一個（n，k）線性分組碼C，如果它的任一碼字的每一次循環(huán)移位都還是C的一個碼字，則稱C是循環(huán)碼。由于循環(huán)碼是線性分組碼，所有這些具有循環(huán)關(guān)系的碼字的全體構(gòu)成了n維矢量空間中具有循環(huán)特性的k維子空間。15第十五頁，共六十頁，2022年，8月28日將任一碼字中的7個碼元排在一個圓周上，則從圓周的任一碼元開始，按順時針方向移動一周，都將構(gòu)成該碼的一個碼字。這就是循環(huán)碼的由來。（見圖）16圖（7，4）漢明碼的碼字循環(huán)圖第二循環(huán)第一循環(huán)16第十六頁，共六十頁，2022年，8月28日二．循環(huán)碼的數(shù)學(xué)描述1．循環(huán)碼的特點：（1）它是線性分組碼，其數(shù)學(xué)模型應(yīng)具有線性特性；（2）具有循環(huán)特性。

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

字多項式

碼字：

碼字多項式

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

17第十七頁，共六十頁，2022年，8月28日3．循環(huán)特性的表示以前面的（7，3）循環(huán)碼為例：（任取一碼字）移一位移兩位移三位?此時：7>n-1=6，超出了n=7的矢量空間。

要求：

則：，即18第十八頁，共六十頁，2022年，8月28日下面用去除，得余對于上面第三次移位結(jié)果，可重新表示如下：

結(jié)論：如果將一個循環(huán)碼的某一非零碼字用碼多項式表示出來，那么其他的非零碼字多項式就可以用這個碼字多項式（或碼字多項式的和）乘上x的一個冪，再求（xn+1）的余得到。說明：一個碼字的移位最多能得到n個碼字，因此“循環(huán)碼字的循環(huán)仍是碼字”并不意味著循環(huán)碼集可以從一個碼字循環(huán)而得，還應(yīng)包含碼字的一些線性組合。19第十九頁，共六十頁，2022年，8月28日設(shè)c＝（cn-1cn-2

…c1c0）是（n，k）循環(huán)碼的一個碼字，則與其對應(yīng)的多項式

c(x)＝cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0

稱為碼字c的碼字多項式（或碼多項式）。如果c＝（cn-1cn-2

…c1c0）是（n，k）循環(huán)碼的一個碼字，則c(1)＝（cn-2…c1c0cn-1）也是該循環(huán)碼的一個碼字。這就是說c(x)＝cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0和c

(1)(x)＝cn-2xn-1＋…＋c1x2＋c0x＋cn-1都是（n，k）循環(huán)碼的碼字多項式。循環(huán)碼的多項式描述20第二十頁，共六十頁，2022年，8月28日比較c(x)和c(1)(x)后可得c

(1)(x)＝xc(x),modxn－1以及c(i)(x)＝xic(x)（i＝1,2,…,n－1）,modxn+1定理在以多項式xn+1為模的剩余類全體所構(gòu)成的n維線性空間Vn中，其一個子空間Vn,k是一個循環(huán)子空間（循環(huán)碼）的充要條件是：Vn,k是一個理想。一個（n，k）循環(huán)碼的碼字多項式都是模xn+1運算下多項式剩余類環(huán)中的一個理想，而且一定是一個主理想子環(huán)。反之，多項式剩余類環(huán)的一個主理想子環(huán)也一定生成一個循環(huán)碼。21第二十一頁，共六十頁，2022年，8月28日§循環(huán)碼的基本定理及其矩陣描述

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

gn-k=1

）（gn-k=1）

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

且所有小于n次的g(x)的倍式都是碼多項式。故循環(huán)碼完全由它的生成多項式確定。22第二十二頁，共六十頁，2022年，8月28日（2）（n，k）循環(huán)碼的生成多項式g(x)一定是(xn+1)的因子，即

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

故x7+1有如下因式：

一次因式：

三次因式：

四次因式：

六次因式：

（一個）

（兩個）

（一個）

（兩個）

24第二十四頁，共六十頁，2022年，8月28日n–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次多項式1+x2+x3或1+x+x3

為生成多項式：

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

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

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

（2）若以n-k次因式作為生成多項式，可供選擇的有25第二十五頁，共六十頁，2022年，8月28日例：

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

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

→構(gòu)成基底

若：

則：

28第二十八頁，共六十頁，2022年，8月28日各多項式對應(yīng)的矢量分別為：

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

29第二十九頁，共六十頁，2022年，8月28日【例】（7，4）循環(huán)碼：

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

如：30第三十頁，共六十頁，2022年，8月28日（次數(shù)）

設(shè)：

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

用xn–k

和u（x）相乘，再除以g(x)31第三十一頁，共六十頁，2022年，8月28日a(x)g(x)是g(x)的一個倍式，則它是一個碼多項式，對應(yīng)的碼矢量為：碼矢量為系統(tǒng)形式的碼字，信息位在尾部?！到y(tǒng)碼的編碼步驟：(1)將k個消息位按升冪排列的次序?qū)懗上⒍囗検絬（x）

；

(2)用xn–k

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

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

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

(4)聯(lián)合b(x)和xn–k

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

u(x)；

(5)將碼多項式轉(zhuǎn)換為碼字。32第三十二頁，共六十頁，2022年，8月28日【例】（7，4）循環(huán)碼：

求

的系統(tǒng)碼字。

，

【解】

，n＝7，k＝4

（1）

（2）（3）（4）33第三十三頁，共六十頁，2022年，8月28日2．系統(tǒng)碼的生成矩陣（1）由生成矩陣做初等行變換，將其變?yōu)樾问?，即為系統(tǒng)形式的生成矩陣（單位陣在后，信息位在尾部）。

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

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

（2）分別求g（x）除的余式（記為），由余式對應(yīng)的矢量作行矢量構(gòu)成的k×n-k的分塊矩陣P聯(lián)合k×k的單位陣I就構(gòu)成系統(tǒng)形式的生成矩陣：34第三十四頁，共六十頁，2022年，8月28日，求系統(tǒng)形式的生成矩陣。

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

35第三十五頁，共六十頁，2022年，8月28日四．循環(huán)碼的校驗矩陣一般情況下，多項式xn+1可因式分解為xn+1=g(x)·h(x)

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

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

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

構(gòu)成。

36第三十六頁，共六十頁，2022年，8月28日設(shè)

則：將上述矢量按逆序排列作為一個（n-k）×n矩陣的行矢量，則該矩陣就是碼C的校驗矩陣。37第三十七頁，共六十頁，2022年，8月28日【例】（7，4）循環(huán)碼：

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

38第三十八頁，共六十頁，2022年，8月28日※系統(tǒng)形式的校驗矩陣

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

39第三十九頁，共六十頁，2022年，8月28日【例】（7，4）循環(huán)碼：

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

（3）40第四十頁，共六十頁，2022年，8月28日循環(huán)碼的編碼

循環(huán)碼是線性分組碼的一個子類，因此循環(huán)碼可以按一般線性分組碼利用常用的組合邏輯電路來實現(xiàn)編碼。但對于線性分組碼，當(dāng)其信息位分組長度較長，編碼位數(shù)較多時，其編碼電路非常復(fù)雜。由于循環(huán)碼具有循環(huán)特性，其編碼器通常用簡單的具有反饋連接的移位寄存器就可以實現(xiàn)，大大簡化了編碼器的復(fù)雜度。利用具有反饋連接的移位寄存器實現(xiàn)的循環(huán)碼編碼電路，實際上是多項式運算電路。首先研究多項式運算電路。41第四十一頁，共六十頁，2022年，8月28日一．G(F2)上的多項式除法電路

設(shè)（被除式）（除式）q(x)→商，r(x)→余除法電路：42第四十二頁，共六十頁，2022年，8月28日（1）除法電路的結(jié)構(gòu)由除式b（x）決定；（2）組成：由r個存儲單元組成r級移位寄存器（D0～Dr-1）

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

故：電路有r個移位寄存器，最多r+1個常乘器，最多r個模2加法器。說明：43第四十三頁，共六十頁，2022年，8月28日（3）工作原理簡述：①電路清零，被除式系數(shù)按高次到低次依次進入電路（ak首先進入），r次移位后，移存器自右至左內(nèi)容為：（a

k，a

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

k

b

r

或ak

b

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

n-k，u(x)應(yīng)從n-k級移存器的最前端輸入。46第四十六頁，共六十頁，2022年，8月28日編碼過程：（1）門打開，k接“1”，消息數(shù)據(jù)uk-1,...u0移入電路，并同時送入信道，一旦k個消息全部移入電路，移存器中的n-k個數(shù)據(jù)就構(gòu)成了余式的系數(shù)；（2）門關(guān)，斷開反饋連接，k接“2”；（3）移出移存器中的數(shù)據(jù)(校驗元)，并送入信道，與k個信息位組成碼字。47第四十七頁，共六十頁，2022年，8月28日【例】（7，4）循環(huán)碼，

若：48第四十八頁，共六十頁，2022年，8月28日編碼過程：（k＝4）節(jié)拍輸入D0D1D2輸出門開，k→1010001111012010113110004－1001門關(guān)，k→25－01006－00107－000149第四十九頁，共六十頁，2022年，8月28日2．基于校驗多項式h（x）的編碼器（k級編碼器）編碼器電路的結(jié)構(gòu)由校驗多項式?jīng)Q定，生成多項式h(x)的最高次數(shù)為k，故編碼器有k級移存器，故稱

k級編碼器。編碼器電路編碼過程（1）門1打開，門2關(guān)閉，k位消息數(shù)據(jù)u0，u1，...，uk-1移入電路，并同時送入信道；（2）k位消息全部移入，門1關(guān)，門2開；（3）以后的每次移位產(chǎn)生一個校驗元并送入信道，直到n－k個校驗元全部產(chǎn)生并送入信道為止。然后門2關(guān)，門1開，準備下一組消息編碼；50第五十頁，共六十頁，2022年，8月28日【例】（7，4）循環(huán)碼，

k＝4級編碼器編碼過程

輸入節(jié)拍D0D1D2D3輸出門1開，門2關(guān)100000111000102010001310101－411011門1關(guān)，門2開－501100－600110－70001051第五十一頁，共六十頁，2022年，8月28日3．兩種編碼器的比較（1）基于g（x）的編碼器為n－k級編碼器，需要n－k級移存器；基于h（x）的編碼器為k級編碼器，需要k級移存器。（2）當(dāng)n－k<k時，采用n－k級編碼器需要資源少；當(dāng)n－k>k時，采用k級編碼器需要資源少。

52第五十二頁，共六十頁，2022年，8月28日§8.4循環(huán)碼譯碼

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

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

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

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

（求余運算）

53第五十三頁，共六十頁，2022年，8月28日【定理】設(shè)g(x)是(n，k)系統(tǒng)循環(huán)碼的生成多項式，接收字多項式為r(x)，對應(yīng)錯誤圖樣為e(x),則

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

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

54第五十四頁，共六十頁，2022年，8月28日2．伴隨式計算電路的性質(zhì)由于碼的循環(huán)結(jié)構(gòu)，伴隨式有個重要的性質(zhì)，用定理描述。

【定理】設(shè)s(x)是r(