【正文】 )1( 23 ?? xx )1( 3 ?? xx)1)(1( 23 ??? xxx )1)(1( 3 ??? xxx)1)(1( 233 ???? xxxx信息論與編碼 循環(huán)碼 設選取 為生成多項式，則 nk=3， k=4，所以信息多項式為 信息碼組共有 16種不同的組合，因此，共有 16個碼字。因此也一定可以用生成矩陣來描述循環(huán)碼。 )(xmknx ?)( xmx kn ?)( xmx kn ?信息論與編碼 循環(huán)碼 例題： （ 7， 4）循環(huán)碼的生成多項式為 求（ 1）該循環(huán)碼系統(tǒng)形式的生成矩陣； （ 2）對于給定的信息組（ 1001），求其對應的系統(tǒng)形式的碼字。 信息論與編碼 循環(huán)碼 到第 4拍完成時，除法器移存里的數(shù)據(jù)就是余式系數(shù)。 k+r+1次移位后， 移存器輸出 C(x)的常數(shù)項 a0+b0， 移存器中的內容全部恢復到全為 0 初態(tài)， 乘法 完成。 信息論與編碼 循環(huán)碼 (2) 第 r+1次移位后 ， ak輸出與 b1r 相乘得到ak b1r ， 這就是商式 q(x)的第一項 xkr的系數(shù) 。 顯然 ， r+1=4 次移位后得到商的第一個系數(shù) ， k+1=5 次移位后 ， 就完成了整個除法運算 ， 并在 D0、 D D2組成的移存器中保留了余式 001， 即 x2。 ?針對循環(huán)碼的特點，在譯碼上也出了許多高效的算法，如捕錯譯碼、大數(shù)邏輯譯碼等，限于篇幅，這里不再討論譯碼的問題。由上面關于循環(huán)碼的論述可知，若在二元域 GF(2)上把 分解為 l個最小多項式 m(x)， i＝ 1,2,……,l 之積，其中 l1個組成 g(x)而剩余的組成 h(x)，則包含于 g(x)中的最小多項式一定滿足 式中“ |”表示整除， C（ x）表示碼多項式。 解：因 7=231,因此 m=3. ，本題為P(x)=x3+x+1 然后令 a為 P(x)的根，生成擴域 GF(23)的所有元素，見表 67 最大糾錯能力為 t=3。第二是因為存在一種有效的硬判決法，使得在許多需要長碼得應用場合，該碼能夠被實現(xiàn)。 若對每一個碼字 ( 1, 2, …, c1. c0)增加一個校驗元 c’0， 滿足以下校驗關系： 1+2+… +c1+c0+c’0=0 稱 c’0為全校驗位 。 ? 縮短循環(huán)碼用于檢錯時也和循環(huán)碼一樣，只要將接收序列除以 g(x)后檢查其余式即可，余式全0(除盡 )則表示接收的時碼字 (g(x)的倍式 )，否則就不是碼字。 另外，由此 g(x)生成的 碼字的重量一定是偶數(shù) ，所以它就能檢出所有奇數(shù)個差錯。 16x信息論與編碼 碼的擴展和縮短 5x 12x 16x 10D接收端校驗時，只要將整個幀除以 g（ x）檢查余式是否為零即可。輸完 k－ i信息位后斷開移存器的反饋線，將此時移存器內的數(shù)據(jù)（余式，即 CRC校驗碼）移位輸出即可。只要以一個選定的 (n， k)循環(huán)碼位基礎，改變 i值，就能適用于任何信息長度的編碼。反之，次數(shù)小于 ni的所有 g(x)倍式一定包含于該子集中，是 (ni, ki),縮短循環(huán)碼的一個碼多項式。如輸入的 8進制信息元為 a5a3a1，問編出的 8進制 RS碼字是什么，糾錯能力如何？ 解： n=7,k=3,dmin=nk+1=5,糾錯能力 t=2，生成多項式為 g(x)=(xa)(xa2)(xa3)(xa4) =x4+a3x3+x2+ax+a3 信息論與編碼 BCH碼和 RS碼 信息多項式為 m(x)=a5x2+a3x+a， 對應碼字為 c(x)=m(x)g(x) 系統(tǒng)碼字為 c(x)=xnkm(x)+r(x) =a5x6+a3x5+ax4+a6x3+a4x2+a2x+1 r(x)= xnkm(x) mod g(x) 二進制衍生碼： 信息碼元： a5a3a1?(111,011,010) 碼字： a5a3aa6a4a21? (111,011,010,101,110,100,001) 信息論與編碼 BCH碼和 RS碼 ? 衍生碼就突發(fā)錯誤的能力： ? 八進制 RS碼能糾每碼字兩個字符的差錯。 t=3, g(x)= x6+x5+x4+x3+x2+x+1 糾錯能力至少是 t. 元素 多項式 矢量表示 極小多項式 0 0 000 x a0 1 001 x+1 a1 a 010 x3+x+1 a2 a2 100 x3+x+1 a3 a+1 011 x3+x2+1 a4 a2 +a 110 x3+x+1 a5 a2 +a+1 111 x3+x2+1 a6 a2 +1 101 x3+x2+1 x3+x+1生成的 GF（ 23）擴域 信息論與編碼 BCH碼和 RS碼 ? RS譯碼 RS譯碼（ Reed－ Solomon里德 索羅門碼）屬于 BCH碼的一個子類，是一種 q進制（ q≠2）的 BCH碼，其碼的每個碼元取值于符號集 {0,a0,a1,…,a q2 } 實用時通常選取 q為 2的冪次（ q＝ 2m），以便一組 m個信息比特可以一一映射到 q個符號之一，也便于與 4， 8， 16， 32， …… 信號點集的 PSK或 QAM調制相適應。 信息論與編碼 BCH碼和 RS碼 ? 已知碼長 n及糾錯能力 t，二元本原 BCH碼的具體設計步驟如下： 1。在無線信道上應用最廣泛的 BCH碼、 RS碼也是循環(huán)碼，它們在具有循環(huán)特性的基礎上又兼有另一些特點。 信息論與編碼 循環(huán)碼 圖 5 8 乘 H(x)除 G(x)電路 信息論與編碼 循環(huán)碼 例 設 GF(2)上的 3 個多項式為： A(x)=x4+x+1， H(x)=x2+1， G(x)=x3+x+1 則 A(x)H(x)=(x4+x+1)(x2+1)=x6+x4+x3+x2+x+1 =x3(x3+x+1)+(x2+x+1) =q(x)G(x)+r(x) 可用下圖的電路實現(xiàn)， 該電路的工作過程如下表所示， 移位 A(x)+1=5 次后， 即得到了商式 x3 和余式 x2+x+1。 除 B(x)的除法電路如下圖 所示， 它由 3 級移存器和 2 個模 2 相加器組成。 k≥r 信息論與編碼 循環(huán)碼 除 B(x)=brxr+…+ b1x+b0電路 信息論與編碼 循環(huán)碼 為了理解除法電路的工作過程， 下面我們列出 B(x)除 A(x)的豎式運算式子： brxr+b r1 x r1+… +b1x+b0 (除式 ) b1rakxkr+b1r(ak1b1rbr1ak)xkr1+… (商式 ) akxk+ak1xk1+… +a1x+a0 (被除式 ) (akxk+b1rbr1akxk1+… +b0b1rakxkr) (ak1b1rbr1ak)xk1+… +(akrb0b1rak)xkr+… (A) ((ak1b1rbr1ak)xk1+… ) … … (余式 ) 由上面