信息論--傅祖蕓7

1、1 、循環(huán)碼的多項式描述2 、循環(huán)碼的生成多項式3 、系統(tǒng)循環(huán)碼4 、多項式運算電路5 、循環(huán)碼的編碼電路6 、循環(huán)碼的譯碼7 、循環(huán)漢明碼8 、縮短循環(huán)碼循環(huán)碼(1) 循環(huán)碼的性質(zhì)n循環(huán)碼是線性分組碼的一個重要子類；n由于循環(huán)碼具有優(yōu)良的代數(shù)結(jié)構(gòu)，使得可用簡單的反饋移位寄存器實現(xiàn)編碼和伴隨式計算，并可使用多種簡單而有效的譯碼方法；n循環(huán)碼是研究最深入、理論最成熟、應用最廣泛的一類線性分組碼。(2) 循環(huán)碼的定義n循環(huán)碼：如果 (n,k) 線性分組碼的任意碼矢C=(Cn1,Cn2,C0) 的 i 次循環(huán)移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一個碼矢，則稱此線

2、性碼為 (n,k) 循環(huán)碼。(3) 碼多項式n碼多項式：為了運算的方便，將碼矢的各分量作為多項式的系數(shù)，把碼矢表示成多項式，稱為碼多項式。其一般表示式為C(x)=Cn1xn1+Cn2xn2+C0)n碼多項式 i 次循環(huán)移位的表示方法 記碼多項式C(x)的一次左移循環(huán)為 C(1)(x) ，i 次左移循環(huán)為 C(i)(x)ininiinininininnnnnnnnnnCxCxCxCxCxxCxCxCxCxCxCxCx1102211)(1103322)1(02211)()()(CCCn碼多項式的模 (xn+1) 運算n0和1兩個元素模2運算下構(gòu)成域。n碼矢 C 循環(huán) i 次所得碼矢的碼多項式n C

3、(x) 乘以 x，再除以 (xn+1)，得ininiinininininnnnCxCxCxCxCxCxCxCx1102211)(02211)()(CC1)(11)() 1 (1102123121nnnnnnnnnnxxCxCxCxCxCxCCxxxCC上式表明：碼矢循環(huán)一次的碼多項式 C(1)(x) 是原碼多項式 C(x)乘以 x 除以 (xn+1) 的余式。寫作因此，因此， C(x) 的 i 次循環(huán)移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即n結(jié)論：循環(huán)碼的碼矢的 i 次循環(huán)移位等效于將碼多項式乘 xi 后再模 (xn+1)。)1()()()1(nxxxx模

4、CC)1()()()(niixxxx模CC(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碼多項式。移位過程和相應的多項式運算如表6.3.1所示。(1) 循環(huán)碼的生成矩陣n根據(jù)循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位得到其它的非0碼字。在 (n,k) 循環(huán)碼的 2k 個碼字中，取前 (k1) 位皆為0的碼字 g(x)（其次數(shù)r=nk），再經(jīng) (k1) 次循環(huán)移位，共得到 k 個碼字:g(x),xg(x),xk1 g(x) )

5、()()()()(21xxxxxxxxkkggggG 這 k 個碼字顯然是相互獨立的，可作為碼生成矩陣的 k 行，于是得到循環(huán)碼的生成矩陣 G(x)(2) 循環(huán)碼的生成多項式n碼的生成矩陣一旦確定，碼就確定了；n這就說明： (n,k) 循環(huán)碼可由它的一個 (nk) 次碼多項式 g(x) 來確定；n所以說 g(x) 生成了 (n,k) 循環(huán)碼，因此稱 g(x) 為碼的生成多項式。多項式。次首是一個1)()()(0111knxxxxxknknknggggg(3) 生成多項式和碼多項式的關(guān)系n定理定理：在 (n,k) 循環(huán)碼中，生成多項式 g(x) 是惟一的 (nk) 次碼多項式，且次數(shù)是最低的。n

6、定理定理：在 (n,k) 循環(huán)碼中，每個碼多項式 C(x) 都是 g(x) 的倍式；而每個為 g(x) 倍式且次數(shù)小于或等于 (n1) 的多項式，必是一個碼多項式。 10001個kn定理定理6.3.36.3.3(定理6.3.2的逆定理)：在一個 (n,k) 線性碼中，如果全部碼多項式都是最低次的 (nk) 次碼多項式的倍式，則此線性碼為一個 (n,k) 循環(huán)碼。 注注：一般說來，這種循環(huán)碼仍具有把 (n,k) 線性碼碼中任一非0碼矢循環(huán)移位必為一碼矢的循環(huán)特性，但從一個非0碼矢出發(fā)，進行循環(huán)移位，就未必能得到碼的所有非0碼矢了。所以稱這種循環(huán)碼為推廣循環(huán)碼。n碼字循環(huán)關(guān)系圖n單純循環(huán)碼的碼字循

7、環(huán)圖：(7,3)循環(huán)碼n推廣循環(huán)碼的碼字循環(huán)圖：(6,3)循環(huán)碼(4) 如何尋找一個合適的生成多項式n由下面式子可知：循環(huán)碼的多項式等于信息多項式乘以生成多項式。 這說明：對一個循環(huán)碼只要生成多項式一旦確定，碼就確定了，編碼問題就解決了。 所以：作一循環(huán)碼的關(guān)鍵，就在于尋找一個適當?shù)纳啥囗検健?()()()()()(),()(0221121021xmxmxmxxxxxxxmmmxkkkkkkkkgggggCn定理定理： (n,k) 循環(huán)碼的生成多項式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)g(x)。n定理定理：若 g(x) 是一個 (nk) 次 多項式，且為(xn+1) 的

8、因式，則 g(x) 生成一個 (n,k) 循環(huán)碼。結(jié)論結(jié)論：當求作一個(n,k)循環(huán)碼時，只要分解多項式(xn+1) ，從中取出(nk)次因式作生成多項式即可。n舉例：求 (7,3) 循環(huán)碼的生成多項式。解：分解多項式 xn+1，取其4次因式作生成多項式x7+1= (x+1) (x3+x2+1) (x3+x+1)可將一次和任一個三次因式的乘積作為生成多項式，因而可取 g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1(5) 循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣n循環(huán)碼的監(jiān)督多項式：設 g(x) 為 (n,k)

9、循環(huán)碼的生成多項式，必為 (xn+1) 的因式，則有 xn+1=h(x)g(x)，式中h(x) 為 k 次多項式，稱為 (n,k) 循環(huán)碼的監(jiān)督多項式。n(n,k) 循環(huán)碼也可由其監(jiān)督多項式完全確定。n舉例： (7,3) 循環(huán)碼 x7+1= (x3+x+1)(x4+x2+x+1)n4次多項式為生成多項式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0n3次多項式是監(jiān)督多項式h(x)=x3+x+1=h3x3+h2x2+h1x+h0n循環(huán)碼的監(jiān)督矩陣n由等式 x7+1= h(x)g(x) 兩端同次項系數(shù)相等得n將上面的方程組 寫成矩陣形式000033246322314531

10、2213044302112033hghgxhghghgxhghghghgxhghghghgx的系數(shù)的系數(shù)的系數(shù)的系數(shù)Tggggghhhhhhhhhhhhhhhh001234321032103210321000000000000000n上式中，列陣的元素是生成多項式 g(x) 的系數(shù)，是一個碼字，那么第一個矩陣則為(7,3)循環(huán)碼的監(jiān)監(jiān)督矩陣督矩陣，即01230123(7,3)01230123000000H000000hhhhhhhhhhhhhhhhn循環(huán)碼監(jiān)督矩陣的構(gòu)成循環(huán)碼監(jiān)督矩陣的構(gòu)成n由式 (6.3.2) 可見，監(jiān)督矩陣的第一行是碼的監(jiān)督多項式 h(x) 的系數(shù)的反序排列反序排列，第二、

11、三、四行是第一行的移位；n可用監(jiān)督多項式的系數(shù)來構(gòu)成監(jiān)督矩陣*(7,3)2*3*0001101h ( )0011010h ( )H0110100h ( )1101000h ( )h ( )h( )xxxxxxxxx其中表示的反多項式。n(n,k) 循環(huán)碼的監(jiān)督矩陣n對偶問題n如果 xn+1=h(x)g(x)，其中 g(x) 為 (nk) 次多項式，以 g(x)為生成多項式，則生成一個 (n,k) 循環(huán)碼；n以 h(x) 為生成多項式，則生成 (n,nk) 循環(huán)碼；n這兩個循環(huán)碼互為對偶碼。0011101101100)()()(11111111*1*),(kkkkknknhhhhhhhhxxxx

12、xhhhH線性碼的譯碼是根據(jù)接收字多項式的伴隨式和可糾的錯誤圖樣間的一一對應關(guān)系，由伴隨式得到錯誤圖樣；循環(huán)碼是線性碼的一個特殊子類，循環(huán)碼的譯碼與線性碼的譯碼步驟基本一致。不過由于循環(huán)碼的循環(huán)特性，使它的譯碼更加簡單易行；循環(huán)碼的譯碼過程仍包括三個步驟：接收多項式的伴隨式計算；求伴隨式對應的錯誤圖樣；用錯誤圖樣糾錯。6.3.6 循環(huán)碼的譯碼(1) 根據(jù)伴隨式定義 ST=HRT 計算伴隨式Sn設n設的行矢量。表示其中HhhhhH)0,2, 1(021knkniiknkn120111112222200000S(,)SHRhRhhhhhRRhhh Rn kn kTTTn kn kn knn kTn

13、 kn knn kTn kTSSSSRSRSR ，得到伴隨式各分量的表示式n這是前面介紹過的由接收矢量相應分量直接求和計算伴隨式的方法，對所有線性碼都適用。TTknknTknknSSSRhRhRh002211所以0123045156345634601234561000110010001100101110001101SSSSRRRRRRRRRRRRRRRRRRRRTTRHS)11. 2 . 6(11nkknGmC)12.2.6(rkknkQIGkrTrkTkrrkrkrSrkkSPQPQIPHQIG)()(或(4) 接收字循環(huán)移位的伴隨式與伴隨式循環(huán)移位的關(guān)系n定理定理6.3.76.3.7：設 S(x) 為