【正文】 16x信息論與編碼 碼的擴展和縮短 5x 12x 16x 10D接收端校驗時，只要將整個幀除以 g（ x）檢查余式是否為零即可。輸完 k－ i信息位后斷開移存器的反饋線，將此時移存器內(nèi)的數(shù)據(jù)（余式，即 CRC校驗碼）移位輸出即可。 另外，由此 g(x)生成的 碼字的重量一定是偶數(shù) ，所以它就能檢出所有奇數(shù)個差錯。只要以一個選定的 (n， k)循環(huán)碼位基礎(chǔ)，改變 i值，就能適用于任何信息長度的編碼。 ? 縮短循環(huán)碼用于檢錯時也和循環(huán)碼一樣，只要將接收序列除以 g(x)后檢查其余式即可，余式全0(除盡 )則表示接收的時碼字 (g(x)的倍式 )，否則就不是碼字。反之，次數(shù)小于 ni的所有 g(x)倍式一定包含于該子集中，是 (ni, ki),縮短循環(huán)碼的一個碼多項式。 若對每一個碼字 ( 1, 2, …, c1. c0)增加一個校驗元 c’0， 滿足以下校驗關(guān)系： 1+2+… +c1+c0+c’0=0 稱 c’0為全校驗位 。如輸入的 8進(jìn)制信息元為 a5a3a1，問編出的 8進(jìn)制 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， 對應(yīng)碼字為 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) 二進(jìn)制衍生碼： 信息碼元： a5a3a1?(111,011,010) 碼字： a5a3aa6a4a21? (111,011,010,101,110,100,001) 信息論與編碼 BCH碼和 RS碼 ? 衍生碼就突發(fā)錯誤的能力： ? 八進(jìn)制 RS碼能糾每碼字兩個字符的差錯。第二是因為存在一種有效的硬判決法，使得在許多需要長碼得應(yīng)用場合，該碼能夠被實現(xiàn)。 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進(jìn)制（ q≠2）的 BCH碼，其碼的每個碼元取值于符號集 {0,a0,a1,…,a q2 } 實用時通常選取 q為 2的冪次（ q＝ 2m），以便一組 m個信息比特可以一一映射到 q個符號之一，也便于與 4， 8， 16， 32， …… 信號點集的 PSK或 QAM調(diào)制相適應(yīng)。 解：因 7=231,因此 m=3. ，本題為P(x)=x3+x+1 然后令 a為 P(x)的根，生成擴域 GF(23)的所有元素，見表 67 最大糾錯能力為 t=3。 信息論與編碼 BCH碼和 RS碼 ? 已知碼長 n及糾錯能力 t，二元本原 BCH碼的具體設(shè)計步驟如下： 1。由上面關(guān)于循環(huán)碼的論述可知，若在二元域 GF(2)上把 分解為 l個最小多項式 m(x)， i＝ 1,2,……,l 之積，其中 l1個組成 g(x)而剩余的組成 h(x)，則包含于 g(x)中的最小多項式一定滿足 式中“ |”表示整除， C（ x）表示碼多項式。在無線信道上應(yīng)用最廣泛的 BCH碼、 RS碼也是循環(huán)碼，它們在具有循環(huán)特性的基礎(chǔ)上又兼有另一些特點。 ?針對循環(huán)碼的特點，在譯碼上也出了許多高效的算法，如捕錯譯碼、大數(shù)邏輯譯碼等，限于篇幅，這里不再討論譯碼的問題。 信息論與編碼 循環(huán)碼 圖 5 8 乘 H(x)除 G(x)電路 信息論與編碼 循環(huán)碼 例 設(shè) 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。 顯然 ， r+1=4 次移位后得到商的第一個系數(shù) ， k+1=5 次移位后 ， 就完成了整個除法運算 ， 并在 D0、 D D2組成的移存器中保留了余式 001， 即 x2。 除 B(x)的除法電路如下圖 所示， 它由 3 級移存器和 2 個模 2 相加器組成。 信息論與編碼 循環(huán)碼 (2) 第 r+1次移位后 ， ak輸出與 b1r 相乘得到ak b1r ， 這就是商式 q(x)的第一項 xkr的系數(shù) 。 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+… ) … … (余式 ) 由上面式子 ， 我們討論除法電路的工作過程 。 k+r+1次移位后， 移存器輸出 C(x)的常數(shù)項 a0+b0， 移存器中的內(nèi)容全部恢復(fù)到全為 0 初態(tài)， 乘法 完成。 信息論與編碼 循環(huán)碼 乘 B(x)運算電路 信息論與編碼 循環(huán)碼 ?工作開始時， r級移位存貯器中的存數(shù)全清洗為 0， 且規(guī)定被乘多項式 A(x)的高次項系數(shù) ak首先送入電路， 電路的工作過程如下： (1) 當(dāng) A(x)的最高次系數(shù) ak首先送入時 ， 乘積C(x)的最高次項 xk+r的系數(shù) akbr就出現(xiàn)在輸出端 ， 同時 ak存入移存器的第一級 (最左一級 )。 信息論與編碼 循環(huán)碼 到第 4拍完成時，除法器移存里的數(shù)據(jù)就是余式系數(shù)。如 m(x)右移一位，則應(yīng)從 g(x)一次項 x的位置進(jìn)入，相當(dāng)于作 xm(x)運算再去做除法。 )(xmknx ?)( xmx kn ?)( xmx kn ?信息論與編碼 循環(huán)碼 例題： （ 7， 4）循