信道編碼-循環(huán)碼

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

2、環(huán)移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一個碼矢，則稱此線性碼為 (n,k) 循環(huán)碼。1. 循環(huán)碼的多項式描述yyyy/M/d4/49(3) 碼多項式碼多項式：為了運算的方便，將碼矢的各分量作為多項式的系數(shù)，把碼矢表示成多項式，稱為碼多項式。其一般表示式為C(x)=Cn1xn1+Cn2xn2+C0)碼多項式 i 次循環(huán)移位的表示方法 記碼多項式C(x)的一次左移循環(huán)為 C(1)(x) ，i 次左移循環(huán)為 C(i)(x)1. 循環(huán)碼的多項式描述ininiinininininnnnnnnnnCxCxCxCxCxCxCxCxCxCxCxCx1102211)(102

3、312)1(02211)(C)(C)(Cyyyy/M/d5/49碼多項式的模 (xn+1) 運算0和1兩個元素模2運算下構成域。1. 循環(huán)碼的多項式描述yyyy/M/d6/49若 p 為素數(shù)，則整數(shù)全體在模 p 運算下的剩余類全 體 在模 p 下構成域。以 p=3 為模的剩余類全體 模3運算的規(guī)則如下：1, 3,2, 1,0p1. 循環(huán)碼的多項式描述120221010000210102202112100210構成域。2,1,0yyyy/M/d7/49碼矢 C 循環(huán) i 次所得碼矢的碼多項式 C(x) 乘以 x，再除以 (xn+1)，得1. 循環(huán)碼的多項式描述ininiinininininnnn

4、CxCxCxCxCxCxCxCx1102211)(02211)()(CC1)(11)()1(1102123121nnnnnnnnnnxxCxCxCxCxCxCCxxxCCyyyy/M/d8/49上式表明：碼矢循環(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)。) 1()()()1(nxxxx模CC1. 循環(huán)碼的多項式描述) 1()()()(niixxxx模

5、CCyyyy/M/d9/49(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)碼的多項式描述yyyy/M/d10/491. 循環(huán)碼的多項式描述yyyy/M/d11/49(1) 循環(huán)碼的生成矩陣根據(jù)循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位得到其它的非0碼字。在 (n,k) 循環(huán)碼的 2k 個碼字中，取前 (k1) 位皆為0的碼字 g(x)（其次數(shù)r=nk），再經(jīng)

6、 (k1) 次循環(huán)移位，共得到 k 個碼字：g(x),xg(x),xk1 g(x) 2. 循環(huán)碼的生成多項式)()()()()(21xxxxxxxxkkggggG 這 k 個碼字顯然是相互獨立的，可作為碼生成矩陣的 k 行，于是得到循環(huán)碼的生成矩陣 G(x)yyyy/M/d12/49(2) 循環(huán)碼的生成多項式碼的生成矩陣一旦確定，碼就確定了；這就說明： (n,k) 循環(huán)碼可由它的一個 (nk) 次碼多項式 g(x) 來確定；所以說 g(x) 生成了 (n,k) 循環(huán)碼，因此稱 g(x) 為碼的生成多項式。2. 循環(huán)碼的生成多項式多項式。次首是一個1)()()(0111knxxxxxknknkn

7、gggggyyyy/M/d13/49(3) 生成多項式和碼多項式的關系定理定理1 1：在 (n,k) 循環(huán)碼中，生成多項式 g(x) 是惟一的 (nk) 次碼多項式，且次數(shù)是最低的。 證明：先證在 (n,k) 循環(huán)碼系統(tǒng)中存在 (nk) 次碼多項式。 因為在 2k 個信息組中，有一個信息組為 ，它的對應碼多項式的次數(shù)為n1(k1)=nk(nk) 次碼多項式是最低次碼多項式。l若 g(x) 不是最低次碼多項式，那么設更低次的碼多項式為g(x) ，其次數(shù)為 (nk1)。 g(x) 的前面 k 位為0，即 k個信息位全為0，而監(jiān)督位不為0，這對線性碼來說是不可能的，因此 g(x) 是最低次的碼多項式

8、，即 gnk 必為1。l續(xù)下頁2. 循環(huán)碼的生成多項式10001個kyyyy/M/d14/49lg0=1，否則經(jīng) (n1) 次左移循環(huán)后將得到低于 (nk) 次的碼多項式。g(x) 是惟一的 (nk) 次多項式。 如果存在另一個 (nk) 次碼多項式，設為 g(x) ，根據(jù)線性碼的封閉性，則 g(x) + g(x) 也必為一個碼多項式。由于 g(x)和 g(x) 的次數(shù)相同，它們的和式的 (nk) 次項系數(shù)為0，那么 g(x) + g(x) 是一個次數(shù)低于 (nk) 次的碼多項式，前面已證明 g(x) 的次數(shù)是最低的，因此 g(x) 不能存在，所以 g(x) 是惟一的 (nk) 次碼多項式。2

9、. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d15/49定理定理2 2：在 (n,k) 循環(huán)碼中，每個碼多項式 C(x) 都是 g(x) 的倍式；而每個為 g(x) 倍式且次數(shù)小于或等于 (n1) 的多項式，必是一個碼多項式。 證明(續(xù)下頁)設 m=(mk1,mk2,m0) 為任一信息組，G(x) 為該 (n,k) 循環(huán)碼的生成矩陣，則相應的碼多項式為2. 循環(huán)碼的生成多項式)()()()()()(),()()()(0221121021xmxmxmxxxxxxxmmmxxxkkkkkkkkgggggCGmCyyyy/M/d16/49上式表明：循環(huán)碼的任一碼多項式為 g(x) 的倍式。顯然，凡是為 g(

10、x) 的倍式且次數(shù)小于或等于 (n1) 的多項式，一定能分解成上式的形式，因而它就是信息多項式 m(x)=(mk1xk1+mk2 1xk2+m0) 并由生成矩陣 G(x) 所生成的碼多項式。定理定理3 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)碼。2. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d17/49碼字循

11、環(huán)關系圖單純循環(huán)碼的碼字循環(huán)圖：(7,3)循環(huán)碼2. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d18/49推廣循環(huán)碼的碼字循環(huán)圖：(6,3)循環(huán)碼2. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d19/49(4) 如何尋找一個合適的生成多項式由下面式子可知：循環(huán)碼的多項式等于信息多項式乘以生成多項式。 這說明：對一個循環(huán)碼只要生成多項式一旦確定，碼就確定了，編碼問題就解決了。 所以：作一循環(huán)碼的關鍵，就在于尋找一個適當?shù)纳啥囗検健?. 循環(huán)碼的生成多項式)()()()()()(),()(0221121021xmxmxmxxxxxxxmmmxkkkkkkkkgggggCyyyy/M/d20/49定理定理4 4：

12、 (n,k) 循環(huán)碼的生成多項式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)g(x)。 證明：由于 xk g(x) 是 n 次多項式，可表示為xk g(x)=1(xn+1)+ g(k)(x) (6.3.1) 式中 g(k)(x) 是碼多項式 g(x) 乘以 xk 除以 (xn+1) 的余式。 根據(jù)循環(huán)碼的移位關系，它是 g(x) 循環(huán)移位 k 次所得到的碼多項式，因而 g(k)(x) 是 g(x) 的倍式。設 g(k)(x)=m(x)g(x) 代入式(6.3.1)得(xn+1)=xk+m(x)g(x)上式表明： g(x) 是 (xn+1) 的因式。2. 循環(huán)碼的生成多項式y(tǒng)yyy

13、/M/d21/49定理定理5 5：若 g(x) 是一個 (nk) 次 多項式，且為(xn+1) 的因式，則 g(x) 生成一個 (n,k) 循環(huán)碼。 證明：(續(xù)下頁)由于 g(x) 是一個 (nk) 次多項式，且為 (xn+1) 的因式，所以 g(x), xg(x), xk1 g(x) 是 k 個次數(shù)小于 n，并且彼此獨立的多項式；2. 循環(huán)碼的生成多項式)()()()()(21xxxxxxxxkkggggG將此多項式用作碼的生成矩陣的 k 行，得到 (n,k) 線性碼的生成矩陣；yyyy/M/d22/49設信息組 m=(mk1,mk2,m0)，則相應的碼字為 C(x)=mG(x)=(mk1x

14、k1+mk2 1xk2+m0)g(x)= m(x)g(x)lC(x)n1；lm(x) 是 2k 個信息多項式的表示式；l所以 C(x) 即為相應 2k 個碼多項式的表示式。因此，g(x) 生成一個 (n,k) 線性碼。C(x) 是 (nk) 次多項式 g(x) 的倍式，所以 g(x) 生成一個 (n,k)循環(huán)碼。 結論結論：當求作一個(n,k)循環(huán)碼時，只要分解多項式(xn+1) ，從中取出(nk)次因式作生成多項式即可。2. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d23/49舉例：求 (7,3) 循環(huán)碼的生成多項式。解：分解多項式 xn+1，取其4次因式作生成多項式x7+1= (x+1) (x3+

15、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+12. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d24/49(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)督多項式完全確定。舉例： (7,3) 循環(huán)碼 x7+1=

16、(x3+x+1)(x4+x2+x+1)l4次多項式為生成多項式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0l3次多項式是監(jiān)督多項式h(x)=x3+x+1=h3x3+h2x2+h1x+h02. 循環(huán)碼的生成多項式y(tǒng)yyy/M/d25/49循環(huán)碼的監(jiān)督矩陣由等式 x7+1= h(x)g(x) 兩端同次項系數(shù)相等得將上面的方程組 寫成矩陣形式0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的系數(shù)的系數(shù)的系數(shù)的系數(shù)2. 循環(huán)碼的生成多項式Tggggghhhhhhhhhhhhhhhh0012343

17、21032103210321000000000000000yyyy/M/d26/49上式中，列陣的元素是生成多項式 g(x) 的系數(shù)，是一個碼字，那么第一個矩陣則為(7,3)循環(huán)碼的監(jiān)督矩陣監(jiān)督矩陣，即2. 循環(huán)碼的生成多項式)2 . 3 . 6(0000000000003210321032103210)3 ,7(hhhhhhhhhhhhhhhhHyyyy/M/d27/49循環(huán)碼監(jiān)督矩陣的構成循環(huán)碼監(jiān)督矩陣的構成由式 (6.3.2) 可見，監(jiān)督矩陣的第一行是碼的監(jiān)督多項式 h(x) 的系數(shù)的反序排列反序排列，第二、三、四行是第一行的移位；可用監(jiān)督多項式的系數(shù)來構成監(jiān)督矩陣2. 循環(huán)碼的生成多項

18、式的反多項式。表示其中)()()3 . 3 . 6(0001011001011001011001011000)()()()(*3*2*)3 ,7(xxxxxxxxxhhhhhhHyyyy/M/d28/49(n,k) 循環(huán)碼的監(jiān)督矩陣對偶問題如果 xn+1=h(x)g(x)，其中 g(x) 為 (nk) 次多項式，以 g(x)為生成多項式，則生成一個 (n,k) 循環(huán)碼；以 h(x) 為生成多項式，則生成 (n,nk) 循環(huán)碼；這兩個循環(huán)碼互為對偶碼。0011101101100)()()(11111111*1*),(kkkkknknhhhhhhhhxxxxxhhhH2. 循環(huán)碼的生成多項式y(tǒng)yy

19、y/M/d29/49(1) 系統(tǒng)循環(huán)碼構成設信息向量 m=(mk1,mk2,m0)信息多項式 m(x)=mk1xk1+mk2 xk2+m0 碼多項式的高次冪部分等于m(x)，即 C(x)=cn1xn1+ cnkxnk+ cnk1xnk1 +c1x +c0 =xnk m(x)+q(x) q(x)的次數(shù)nk校驗位多項式 q(x)由于碼多項式是生成多項式的倍式，所以C(x)= xnkm(x)+q(x)=a(x)g(x)0 (mod g(x)q(x)=C(x)+ xnkm(x)xnkm(x) (mod g(x)因此，循環(huán)碼的系統(tǒng)碼形式為C(x)= xnkm(x)+ (xnkm(x) mod g(x)3

20、. 系統(tǒng)循環(huán)碼yyyy/M/d30/49系統(tǒng)循環(huán)碼構造過程步驟信息多項式乘 xnk： xnkm(x)對 xnkm(x) 求余式：q(x)xnkm(x) (mod g(x)求碼多項式： C(x)=xnkm(x)+ ( xnkm(x) mod g(x) =xnkm(x)+ q(x)令 m(x) 為單項式 xnk+i，i=0,1,2,k1xnk+i= a(x)g(x)+qi(x)，qi(x)的次數(shù)nkCi(x)= xnk+i+qi(x)可見： Ci(x)對應的向量Ci，i=0,1,2,k1是線性無關的，從而得到循環(huán)碼系統(tǒng)碼的生成矩陣 Gs 為3. 系統(tǒng)循環(huán)碼yyyy/M/d31/493. 系統(tǒng)循環(huán)碼

21、1, 01 , 00, 01, 21 , 20, 21, 11 , 10, 1021100010001100010001knknkkkknkkkkksqqqqqqqqqqqqGyyyy/M/d32/49(2) 舉例例： (7,4) 循環(huán)碼 g(x)=x3+x+1，x6=(x3 + x2 +1)g(x)+(x2+1) q3(x)=(x2+1) C3(x)=x6+x2+1 x5=(x2+1)g(x)+(x2+x+1) q2(x)=(x2+x+1) C2(x)=x5+x2+x+1 x4= xg(x)+(x2+x) q1(x)=(x2+x) C1(x)=x4+x2+xx3= g(x)+(x+1) q0

22、(x)=(x+1) C0(x)=x3+x+1 3. 系統(tǒng)循環(huán)碼)()()() 1()() 1(1101000011010011100101010001223xxxxxxxxsggggGyyyy/M/d33/49(1) 多項式加法電路多項式 a(x)=anxn+an1xn1+a1x+a0 表示的是時間序列 a=(an,an1,a1,a0)，因此多項式的計算表現(xiàn)為對時間序列的操作；4. 多項式運算電路 對二進制多項式系數(shù)的基 本操作為模模2加加和模模2乘乘； 電路圖運算符號的意義：yyyy/M/d34/49a(x) 與 b(x) 的相加電路。如圖6.3.3。4. 多項式運算電路yyyy/M/d35

23、/49(2) 多項式乘法電路多項式乘以 x 等價為時間序列 a 延遲一位；多項式與多項式相乘等價為不同位移后的相加： a(x)g(x)=a(x)(g1(x)+ g2(x)= a(x)g1(x)+ a(x)g2(x) 多項式乘法電路如圖6.3.4。假設多項式的低位在前，電路中所有寄存器初態(tài)為0。4. 多項式運算電路yyyy/M/d36/49圖6.3.5表示了多項式乘法電路。4. 多項式運算電路yyyy/M/d37/49(3) 多項式除法電路當 g(x) =1,多項式 a(x) 模 g(x) 的余式為0,電路如圖6.3.7所示。4. 多項式運算電路yyyy/M/d38/49當 g(x)是單項式 g

24、(x)=xk， a(x) 模 g(x) 的余式的次數(shù)小于 k，進入電路的輸入順序為 an,an1,a1,a0。a(x)ak1xk1+ak2xk2+a1x+a0 (mod xk) 運算電路如圖6.3.8所示。4. 多項式運算電路yyyy/M/d39/49由于 xk1 mod(x+1), i=0,1,2,。若 a(x) 的次數(shù)為 n，則 a(x) mod(x+1)an1+an2+a1+a0 =q0 (mod 2) 運算電路如圖6.3.9所示。4. 多項式運算電路yyyy/M/d40/49同樣由長除法得 運算電路如圖6.3.10所示。4. 多項式運算電路niiiniiiniiiniiiaqaqxqq

25、aax5 , 3 , 114, 2, 002105 , 3 , 14, 2, 0)1(mod()(其中ayyyy/M/d41/49類似地：多項式a(x)模(x2+x+1)的運算電路如圖6.3.11所示。4. 多項式運算電路yyyy/M/d42/49一般的多項式模 g(x)=grxr+gr1xr1+g1x+g0 的運算電路如圖6.3.12所示。移位寄存器初態(tài)全為0；當 a(x) 輸入完后，移位寄存器內(nèi)容(qr, qr1,q1,q0 )就是余式q(x)=pr1xr1+ pr2xr2+ +p1x+p0 a(x) (mod g(x)4. 多項式運算電路yyyy/M/d43/49多項式除法電路的構造多項式除法電路是一個由除式(這里就是生成多項式g(x) g(x)=gnkxnk+gnk1xnk1+g1x+g0 所確定的反饋移位寄存器。除法電路的構造方法移位寄存器的級數(shù)等于除式的次數(shù) nk；移位寄存器的反饋抽頭，由除式的各項系數(shù) gi(i=0,1,nk) 決定：p當某個抽頭=0時，對應的反饋斷開；p當某個抽頭=1時，對應的反饋接通。完成除法所需的移位次數(shù)等于被除式的次數(shù)加1。4. 多項式運算電路yyyy/M/d44/49多項式除法電路舉例利用除法電路完成兩個多項式除法運算，求其余式的過程和將兩個多項式進行長除運算是完全一致的；例如 (x5