第九章 循環(huán)碼

本文格式為Word版，下載可任意編輯——第九章循環(huán)碼

信息論

第九章循環(huán)碼1

信息論

第九章循環(huán)碼

內(nèi)容提要：內(nèi)容提要：循環(huán)碼是線性分組碼中一個重要的子類。循環(huán)碼是線性分組碼中一個重要的子類。本章首先提出了循環(huán)碼的定義以及循環(huán)碼的多項式描述方法，項式描述方法，論述了循環(huán)碼構(gòu)成的有關(guān)重要定理；定理；接著探討了循環(huán)碼的編譯碼方法及其實現(xiàn)電路，現(xiàn)電路，最終介紹了已獲得廣泛應(yīng)用的循環(huán)漢明碼、碼等。明碼、BCH碼等。碼等

信息論

本章重點：本章重點：1.循環(huán)碼的基本概念；循環(huán)碼的基本概念；循環(huán)碼的基本概念2.循環(huán)碼的編碼和譯碼方法；循環(huán)碼的編碼和譯碼方法；3.BCH碼。碼

信息論

9.1循環(huán)碼的一般概念9.1.1循環(huán)碼的定義將任一碼字中的7個碼元排在一個圓周上，則從圓周的任一碼元開始，按順時針方向移動一周，都將構(gòu)成該碼的一個碼字。這就是循環(huán)碼的由來。(見圖9.1)

信息論

c1:c2:c3:c4:c5:c6:c7:c15:

0001011001011001011001011000第一循環(huán)011000111000101000101

0000000

c8:c9:c10:c11:c12:c13:c14:c16:

0011101011101011101001101001其次循環(huán)10100110100111100111011111115

圖9.1(7,4)漢明碼的碼字循環(huán)圖

信息論

定義9.1一個線性分組碼，若具有以下特性，則稱其為定義循環(huán)碼。設(shè)碼字循環(huán)碼c=(cn-1,cn-2,…,c1,c0)若將碼元循環(huán)左移一位，得c(1)=(cn-2,…,c1,c0,cn-1)c(1)也是一個碼字。

信息論

9.1.2循環(huán)碼的多項式描述設(shè)c=(cn-1cn-2…c1c0)是(n,k)循環(huán)碼的一個碼字，則與其對應(yīng)的多項式c(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0(9-1)稱為碼字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)碼的碼字多項式。7

信息論

比較c(x)和c(1)(x)后可得c(1)(x)=xc(x),modxn-1modxn-1(9-3)定理9.1在以多項式xn-1為模的剩余類全體所構(gòu)成的n維線定理VV性空間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)碼。8

(9-2)

以及c(i)(x)=xic(x)(i=1,2,…,n-1),

信息論

9.1.3循環(huán)碼的生成多項式定義9.2若一個循環(huán)碼定義的所有碼字多項式都是一個次數(shù)最低的非零首一多項式g(x)的倍式，則稱g(

x)生成該循環(huán)碼，并稱g(x)為該碼的生成元或生成多項式。定理9.2GF(2)上的(n,定理k)循環(huán)碼中，存在有唯一的n-k次首一多項式g(x)=xn-k+gn-k-1xn-k-1+…+g1x+g0使得每一個碼多項式c(x)都是g(x)的倍式，且每一低于或等于n-1次的g(x)倍式，一定是碼多項式。

定理9.3(n,k)循環(huán)碼的生成多項式g(x)一定是xn-1定理的因式：xn-1=g(x)h(x)。反之，若g(x)為n-k次，且除盡xn-1,則此g(x)一定生成一個(n,k)循環(huán)碼。9

信息論

定理9.4若g(x)是(n,k)循環(huán)碼的生成多項式，由xn-1=定理g(x)h(x),h(x)是k次多項式，稱為校驗多項式校驗多項式。令校驗多項式h(x)=hkxk+hk-1xk-1+…+h1x+h0則0h0h1Lhk0L0hhLh0L001kH=M(9-5)0h0h1Lhk0L為(n-k)n階矩陣，稱為碼的校驗矩陣校驗矩陣。校驗矩陣

信息論

綜上所述，有如下結(jié)論：①(n,k)循環(huán)碼的生成多項式g(x)是一個次數(shù)最低的唯一的首一多項式，其次數(shù)r=n-k正好是碼字中校驗元的數(shù)目；②生成多項式g(x)是xn-1的因式。要構(gòu)造一個(n,k)循環(huán)碼，就是要在xn-1的因式中找一個n-k次的首一多項式g(x),它的所有次數(shù)低于或等于n-1的倍式就構(gòu)成一個(n,k)循環(huán)碼。反之，循環(huán)碼的每一個碼字多項式必是g(x)的倍式；③由xn-1=g(x)h(x),h(x)稱為校驗多項式。對于任意一個(n,k)循環(huán)碼，必有g(shù)(x)h(x)=0modxn-1及GHT=0循環(huán)碼是線性分組碼的一個子類。因此，所有線性分組碼的性質(zhì)均適用于循環(huán)碼。11

信息論

9.2循環(huán)碼的編碼9.2.1利用生成多項式利用生成多項式g(x)實現(xiàn)編碼實現(xiàn)編碼若已知g(x)=gn-kxn-k+gn-k-1xn-k-1+…+g1x+g0

并設(shè)信息元多項式m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0要編碼成系統(tǒng)循環(huán)碼形式，須用xn-k乘以m(x),再加上校驗元多項式r(x),這樣得到的碼字多項式c(x)為：c(x)=xn-km(x)+r(x)=mk-1xn-1+mk-2xn-2+…+m0xn-k+rn-k-1xn-k-1+…+r1x+r0其中r(x)=rn-k-1xn-k-1+…+r1x+r012

信息論

c(x)一定是g(x)的倍式，即有c(x)=xn-km(x)+r(x)=q(x)g(x)或c(x)=xn-km(x)+r(x)=0,modg(x)

注意到g(x)為n-k次多項式，而r(x)至多為n-k-1次多項式，必有r(x)=xn-km(x),modg(x)即r(x)必是xn-km(x)除以g(x)的余式。(9-6)式指出了系統(tǒng)循環(huán)碼的編碼方法：首先將信息元多項式m(x)乘以xn-k成為xn-km(x);然后將xn-km(x)除以生成多項式g(x)得到余式r(x),該余式就是校驗元多項式，從而得到碼字多項式c(x)=xn-km(x)+r(x)。13

(9-6)

信息論

9.2.2除法電路設(shè)GF(2)上的兩個多項式a(x)=akxk+ak-1xk-1+…+a1x+a0b(x)=brxr+br-1xr-1+…+b1x+b0a(x)是被除式，b(x)是除式。用圖9.2所示

的電路完成a(x)除以b(x)的運算。

圖9.2除法電路的一般形式14

信息論

設(shè)被除式a(x)=x4+x+1,除式b(x)=x3+x2+1,完成二例個多項式相除的運算。長除法：

x3+x2+1x4x4+x3x3x3+x2x2

x+1+x+1+1+1

+x

多項式的系數(shù)運算

1111011001111011001110110015

信息論

實現(xiàn)以上除法運算的除法電路如圖9.3所示

圖9.3以b(x)=x3+x2+1為除式的除法電路

信息論

9.2.3編碼電路系統(tǒng)循環(huán)碼的編碼方法是：首先將信息元多項式m(x)乘以xn-k成為xn-km(x);然后將xn-km(x)除以生成多項式g(x)得到余式r(x),該余式就是校驗元多項式，從而可得碼字多項式c(x)=xnkm(x)+r(x)。

信息論

用電路實現(xiàn)編碼時可采用以g(x)為除式的除法電路。作為實例，圖9.4示出了生成多項式g(x)=x3+x2+1的(7,4)循環(huán)碼的編碼電路。

圖9.4以g(x)=x3+x2+1的(7,4)循環(huán)碼編碼器18

信息論

9.3循環(huán)碼的譯碼當(dāng)碼字c通過噪聲信道傳送時