信息論與編碼-第16講-信道編碼-循環(huán)碼

第1頁2024/4/14

第9章循環(huán)碼9.1循環(huán)碼的多項式描述9.2循環(huán)碼的生成多項式9.3系統(tǒng)循環(huán)碼9.4多項式運算電路9.5循環(huán)碼的編碼電路9.6循環(huán)碼的譯碼ElectronicsEngineeringDepartment,XXXXXxxXxxx第2頁2024/4/149.1循環(huán)碼的多項式描述(1)循環(huán)碼的性質(zhì)(2)循環(huán)碼的定義(3)碼多項式(4)舉例第3頁2024/4/149.1循環(huán)碼的多項式描述(1)循環(huán)碼的性質(zhì)循環(huán)碼是線性分組碼的一個重要子類；由于循環(huán)碼具有優(yōu)良的代數(shù)結構，可用簡單的反饋移位寄存器實現(xiàn)編碼和伴隨式計算，并可使用多種簡單而有效的譯碼方法；循環(huán)碼是研究最深入、理論最成熟、應用最廣泛的一類線性分組碼。第4頁2024/4/149.1循環(huán)碼的多項式描述(2)循環(huán)碼的定義

循環(huán)碼：如果(n,k)線性分組碼的任意碼字：C=(cn－1,cn－2,…,c0)

的i次循環(huán)移位，所得矢量：C(i)=(cn－1－i,cn－2－i,…,c0,cn－1,…,cn－i)

仍是一個碼字，則稱此線性碼為(n,k)循環(huán)碼。第5頁2024/4/149.1循環(huán)碼的多項式描述(3)碼多項式

碼多項式：為了運算的方便，將碼字的各分量作為多項式的系數(shù)，把碼字表示成多項式，稱為碼多項式。其一般表示式為：C(x)=cn－1xn－1+cn－2xn－2+…+c0

碼多項式i

次循環(huán)移位的表示方法記碼多項式C(x)的一次左移循環(huán)為C(1)(x)

，i次左移循環(huán)為C(i)(x)第6頁2024/4/149.1循環(huán)碼的多項式描述(3)碼多項式

碼多項式的模(xn+1)運算

0和1兩個元素模2運算下構成域。若p為素數(shù)，則整數(shù)全體在模p運算下的剩余類全體在模p下構成域。第7頁2024/4/149.1循環(huán)碼的多項式描述(3)碼多項式碼多項式的模(xn+1)運算以p=3為模的剩余類全體模3運算的規(guī)則如下：第8頁2024/4/149.1循環(huán)碼的多項式描述(3)碼多項式

碼多項式的模(xn+1)運算碼字C

循環(huán)i次所得碼字的碼多項式：

C(x)乘以x，再除以(xn+1)，得：第9頁2024/4/149.1循環(huán)碼的多項式描述(3)碼多項式

碼多項式的模(xn+1)運算

上式表明：碼字循環(huán)一次的碼多項式C(1)(x)是原碼多項式C(x)乘以x除以(xn+1)的余式。寫作：

C(x)的i次循環(huán)移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即：

結論：循環(huán)碼的碼字的i次循環(huán)移位等效于將碼多項式乘xi后再模(xn+1)。第10頁2024/4/149.1循環(huán)碼的多項式描述(4)舉例：(7,3)循環(huán)碼可由任一個碼字，比如(0011101)經(jīng)過循環(huán)移位，得到其它6個非0

碼字；可由相應的碼多項式(x4+x3+x2+1)，乘以

xi(i=1,2,…,6)，再模(x7+1)運算得到其它6個非0

碼多項式。移位過程和相應的多項式運算如表9-1所示。第11頁2024/4/149.1循環(huán)碼的多項式描述(4)舉例：(7,3)循環(huán)碼第12頁2024/4/149.2循環(huán)碼的生成多項式(1)循環(huán)碼的生成矩陣(2)循環(huán)碼的生成多項式(3)生成多項式和碼多項式的關系(4)如何尋找一個合適的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣第13頁2024/4/149.2循環(huán)碼的生成多項式(1)循環(huán)碼的生成矩陣循環(huán)碼的循環(huán)特性：可由一個碼字的循環(huán)移位得到其它的非0

碼字。在(n,k)循環(huán)碼的2k個碼字中，取前

(k－1)位皆為0的碼字g(x)（次數(shù)r=n－k），再經(jīng)

(k－1)次循環(huán)移位，共得到k個碼字：g(x),xg(x),…,xk－1g(x)

第14頁2024/4/149.2循環(huán)碼的生成多項式(1)循環(huán)碼的生成矩陣這k個碼字是相互獨立的，可作為碼生成矩陣的k行，得到循環(huán)碼的生成矩陣G(x)。矩陣中的元素是多項式：第15頁2024/4/149.2循環(huán)碼的生成多項式(1)循環(huán)碼的生成矩陣將矩陣中的多項式改寫成對應的n重矢量形式：第16頁2024/4/149.2循環(huán)碼的生成多項式(2)循環(huán)碼的生成多項式碼的生成矩陣一旦確定，碼就確定了；(n,k)循環(huán)碼可由它的一個(n－k)次碼多項式g(x)來確定；g(x)生成了(n,k)循環(huán)碼，稱g(x)為碼的生成多項式。

g(x)是一個(n－k)次首1多項式第17頁2024/4/149.2循環(huán)碼的生成多項式(3)生成多項式和碼多項式的關系定理9-1：在(n,k)循環(huán)碼中，生成多項式g(x)是惟一的(n－k)次碼多項式，且次數(shù)是最低的。定理9-2：在(n,k)循環(huán)碼中，每個碼多項式C(x)都是g(x)的倍式；而每個為g(x)倍式且次數(shù)小于或等于(n－1)的多項式，必是一個碼多項式。第18頁2024/4/149.2循環(huán)碼的生成多項式(3)生成多項式和碼多項式的關系定理9-3(定理9-2的逆定理)：在一個(n,k)線性碼中，如果全部碼多項式都是最低次的(n－k)次碼多項式的倍式，則此線性碼為一個(n,k)循環(huán)碼。注：一般說來，這種循環(huán)碼仍具有把(n,k)線性碼碼中任一非0

碼字循環(huán)移位必為一碼字的循環(huán)特性，但從一個非0

碼字出發(fā)，進行循環(huán)移位，就未必能得到碼的所有非0

碼字了。所以稱這種循環(huán)碼為推廣循環(huán)碼。第19頁2024/4/149.2循環(huán)碼的生成多項式(3)生成多項式和碼多項式的關系

碼字循環(huán)關系圖單純循環(huán)碼的碼字循環(huán)圖：(7,3)循環(huán)碼第20頁2024/4/149.2循環(huán)碼的生成多項式(3)生成多項式和碼多項式的關系

碼字循環(huán)關系圖推廣循環(huán)碼的碼字循環(huán)圖：

(6,3)循環(huán)碼(4)如何尋找一個合適的生成多項式循環(huán)碼的碼多項式等于信息多項式乘以生成多項式：對一個循環(huán)碼只要生成多項式一旦確定，碼就確定了，編碼問題就解決了。作一循環(huán)碼的關鍵，就在于尋找一個適當?shù)纳啥囗検?。?1頁2024/4/149.2循環(huán)碼的生成多項式第22頁2024/4/149.2循環(huán)碼的生成多項式(4)如何尋找一個合適的生成多項式定理9-4：(n,k)循環(huán)碼的生成多項式g(x)是(xn+1)的因式，即：xn+1=h(x)

g(x)。歐幾里德除法：設

b是正整數(shù)，則任意正整數(shù)a>b

皆可唯一地表示成：a=q?b+r0≤r<b第23頁2024/4/149.2循環(huán)碼的生成多項式(4)如何尋找一個合適的生成多項式定理9-5：若g(x)是一個(n－k)次多項式，且為(xn+1)的因式，則g(x)生成一個(n,k)循環(huán)碼。結論：求作一個(n,k)循環(huán)碼時，只要分解多項式(xn+1)，從中取出(n－k)次因式作生成多項式即可。第24頁2024/4/149.2循環(huán)碼的生成多項式(4)如何尋找一個合適的生成多項式例：求(7,3)循環(huán)碼的生成多項式。[解]：分解多項式x7+1，取其4次因式作生成多項式：x7+1=(x+1)(x3+x2+1)(x3+x+1)

可將一次和任一個三次因式的乘積作為生成多項式，可?。篻1(x)=(x+1)(x3+x2+1)=x4+x2+x+1

或g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1第25頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣

循環(huán)碼的監(jiān)督多項式：設g(x)為(n,k)循環(huán)碼的生成多項式，必為(xn+1)的因式，則有：xn+1=h(x)

g(x)，式中h(x)為k次多項式，稱為(n,k)循環(huán)碼的監(jiān)督多項式。

(n,k)循環(huán)碼也可由其監(jiān)督多項式完全確定。第26頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣

循環(huán)碼的監(jiān)督多項式：舉例：(7,3)循環(huán)碼：x7+1=(x3+x+1)(x4+x2+x+1)4次多項式為生成多項式：g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多項式是監(jiān)督多項式：h(x)=x3+x+1=h3x3+h2x2+h1x+h0第27頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣由等式x7+1=h(x)

g(x)兩端同次項系數(shù)相等得：第28頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣將上面的方程組寫成矩陣形式：第29頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣上式中，列陣的元素是生成多項式g(x)的系數(shù)，是一個碼字，那么第一個矩陣則為(7,3)循環(huán)碼的監(jiān)督矩陣，即：第30頁2024/4/14(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼監(jiān)督矩陣的構成由式(9-18)可見，監(jiān)督矩陣的第一行是碼的監(jiān)督多項式h(x)的系數(shù)的反序排列，第二、三、四行是第一行的移位；9.2循環(huán)碼的生成多項式第31頁2024/4/14(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼監(jiān)督矩陣的構成可用監(jiān)督多項式的系數(shù)來構成監(jiān)督矩陣：

其中h*(x)表示h(x)的反多項式9.2循環(huán)碼的生成多項式第32頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼監(jiān)督矩陣的構成(n,k)循環(huán)碼的監(jiān)督矩陣：第33頁2024/4/149.2循環(huán)碼的生成多項式(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣對偶問題如果xn+1=h(x)

g(x)，其中g(x)為(n－k)

次多項式，以g(x)為生成多項式，則生成一個(n,k)循環(huán)碼；以h(x)為生成多項式，則生成(n,n－k)循環(huán)碼；這兩個循環(huán)碼互為對偶碼。第34頁2024/4/14(1)系統(tǒng)循環(huán)碼構成信息向量：m=(mk－1,mk－2,…,m0)信息多項式：m(x)=mk－1xk－1+mk－2xk－2+…+m0

碼多項式的高次冪部分等于m(x)，即：

C(x)=cn－1xn－1+…+cn－kxn－k+cn－k－1xn－k－1

…+c1x+c0

=xn－km(x)+q(x)（q(x)的次數(shù)<n－k）監(jiān)督位多項式：q(x)9.3系統(tǒng)循環(huán)碼第35頁2024/4/14(1)系統(tǒng)循環(huán)碼構成由于碼多項式是生成多項式的倍式，所以：C(x)=xn－km(x)+q(x)=a(x)g(x)≡0（modg(x)）q(x)=C(x)+xn－km(x)≡xn－km(x)

（modg(x)）9.3系統(tǒng)循環(huán)碼第36頁2024/4/149.3系統(tǒng)循環(huán)碼(1)系統(tǒng)循環(huán)碼構成

循環(huán)碼的系統(tǒng)碼形式為：C(x)=xn－km(x)+

(xn－km(x)

modg(x))

系統(tǒng)循環(huán)碼構造過程步驟：

信息多項式乘xn－k：xn－km(x)

對xn－km(x)求余式：q(x)≡xn－km(x)(modg(x))

求碼多項式：C(x)=xn－km(x)+(xn－km(x)modg(x))=xn－km(x)+q(x)第37頁2024/4/149.3系統(tǒng)循環(huán)碼(2)舉例[例9-5]：在由g(x)=x4+x3+x2+1生成的(7,3)循環(huán)碼中，求信息碼組m=(101)的對應碼多項式。第38頁2024/4/149.4多項式運算電路(1)多項式加法電路(2)多項式乘法電路(3)多項式除法電路第39頁2024/4/149.4多項式運算電路(1)多項式加法電路多項式a(x)=anxn+an－1xn－1+…+a1x+a0表示的是時間序列

a=(an,an－1,…,a1,a0)，因此多項式的計算表現(xiàn)為對時間序列的操作；對二進制多項式系數(shù)的基本操作為模2加和模2乘；電路圖運算符號的意義：第40頁2024/4/149.4多項式運算電路(1)多項式加法電路

a(x)與b(x)的相加電路第41頁2024/4/149.4多項式運算電路(2)多項式乘法電路多項式乘法電路：第42頁2024/4/149.4多項式運算電路(3)多項式除法電路一般的多項式模g(x)=grxr+gr－1xr－1+…+g1x+g0

的運算電路如圖所示。移位寄存器初態(tài)全為0；當a(x)輸入完后，移位寄存器內(nèi)容(qr－1,…,q1,

q0)就是余式：q(x)=qr－1xr－1+qr－2xr－2+…+q1x+q0≡a(x)

(modg(x))(3)多項式除法電路多項式除法電路舉例

(x5+x2)÷(x4+x3+x+1)運算電路工作過程：第43頁2024/4/149.4多項式運算電路第44頁2024/4/149.4多項式運算電路(3)多項式除法電路多項式除法電路舉例第45頁2024/4/149.5循環(huán)碼的編碼電路系統(tǒng)碼編碼電路(1)系統(tǒng)碼編碼的基本原理(2)用(n－k)

級移位寄存器實現(xiàn)的編碼電路第46頁2024/4/149.5循環(huán)碼的編碼電路(1)系統(tǒng)碼編碼的基本原理

求生成多項式g(x)：分解多項式(xn+1)，取(n－k)次因式作生成多項式g(x)，一般可通過查表完成。利用g(x)實現(xiàn)編碼：設信息多項式為：m(x)=mk－1xk－1+mk－2xk－2+…+m0

設監(jiān)督多項式為：q(x)=qr－1xr－1+qr－2xr－2+…+q0(n,k)循環(huán)碼的碼多項式為：

C(x)=cn－1xn－1+cn－2xn－2+…+cn－kxn－k

+cn－k－1xn－k－1+…+c1x+c0前k項系數(shù)為信息位，后r=n－k項為監(jiān)督位。第47頁2024/4/149.5循環(huán)碼的編碼電路(1)系統(tǒng)碼編碼的基本原理

求生成多項式g(x)：分解多項式(xn+1)，取(n－k)次因式作生成多項式g(x)，一般可通過查表完成。利用g(x)實現(xiàn)編碼所以：cn－1xn－1+…+cn－kxn－k=xn－k(mk－1xk－1+…+m0)=xn－km(x)cn－k－1xn－k－1+…+c0=qr－1xr－1+…+q0=q(x)第48頁2024/4/149.5循環(huán)碼的編碼電路(2)用(n－k)

級移位寄存器實現(xiàn)的編碼電路

循環(huán)碼編碼電路結構和工作原理

工作原理：二元(n,k)循環(huán)碼的編碼是將信息多項式m(x)乘xn－k后再除以生成多項式g(x)求出它的余式，即為監(jiān)督位多項式q(x)。C(x)=xn－km(x)+（xn－km(x)

modg(x)）二元(n,k)循環(huán)碼的編碼電路就是以g(x)為除式的除法電路，而輸入的被除式為xn－km(x)。第49頁2024/4/149.5循環(huán)碼的編碼電路(2)用(n－k)

級移位寄存器實現(xiàn)的編碼電路循環(huán)碼編碼電路結構和工作原理實際的編碼電路如圖9-11所示：其級數(shù)等于g(x)的次數(shù)(n－k)；反饋連接決定于g(x)的系數(shù)當gi=0時(i=0,1,2,…,n－k)，反饋斷開；當gi=1時，對應級加入反饋。第50頁2024/4/149.5循環(huán)碼的編碼電路(2)用(n－k)

級移位寄存器實現(xiàn)的編碼電路循環(huán)碼編碼電路結構和工作原理由于被除式中含有因子