【正文】 含于 g(x)中的最小多項(xiàng)式一定滿足 式中“ |”表示整除， C（ x）表示碼多項(xiàng)式。若對于每個(gè) j， j＝ 1， 2， …… ， 2t，均有 即 g(x)包含 2t個(gè)連續(xù)冪次的根 ,則由該 g(x)生成的循環(huán)碼就是糾錯(cuò)能力不小于 t的 BCH碼 )())()(()1( 1210 ???????? nn axxxxx ???????11)()(|)liij xmxgax（信息論與編碼 BCH碼和 RS碼 BCH的出現(xiàn)為通訊系統(tǒng)設(shè)計(jì)者們在糾錯(cuò)能力，碼長和碼率的靈活設(shè)計(jì)上提供了很大的選擇余地，一旦要求的糾錯(cuò)能力 t給定，只要算出2t個(gè)連續(xù)冪次的根所對應(yīng)的多項(xiàng)式作為生成多項(xiàng)式，即可得出糾錯(cuò)能力符合要求的碼。 信息論與編碼 BCH碼和 RS碼 ? 已知碼長 n及糾錯(cuò)能力 t，二元本原 BCH碼的具體設(shè)計(jì)步驟如下： 1。以本原多項(xiàng)式 P(x)的根為本原元 a，分別計(jì)算 2t個(gè)連續(xù)冪次根 a， a2， … ， a2t所對應(yīng)的二元域上的最小多項(xiàng)式 m1(x), m2(x), …, m 2t(x). 3。 解：因 7=231,因此 m=3. ，本題為P(x)=x3+x+1 然后令 a為 P(x)的根，生成擴(kuò)域 GF(23)的所有元素，見表 67 最大糾錯(cuò)能力為 t=3。每個(gè)根所對應(yīng)的最小多項(xiàng)式，由表 67給出 3。 t=3, g(x)= x6+x5+x4+x3+x2+x+1 糾錯(cuò)能力至少是 t. 元素 多項(xiàng)式 矢量表示 極小多項(xiàng)式 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）擴(kuò)域 信息論與編碼 BCH碼和 RS碼 ? RS譯碼 RS譯碼（ Reed－ Solomon里德 索羅門碼）屬于 BCH碼的一個(gè)子類，是一種 q進(jìn)制（ q≠2）的 BCH碼，其碼的每個(gè)碼元取值于符號集 {0,a0,a1,…,a q2 } 實(shí)用時(shí)通常選取 q為 2的冪次（ q＝ 2m），以便一組 m個(gè)信息比特可以一一映射到 q個(gè)符號之一，也便于與 4， 8， 16， 32， …… 信號點(diǎn)集的 PSK或 QAM調(diào)制相適應(yīng)。 信息論與編碼 BCH碼和 RS碼 ?如果用 N表示 RS碼的碼長， K表示信息符號的長度， N－ K表示校驗(yàn)符號碼的長度，則RS碼的參數(shù)可以用以下式子來表達(dá) 碼長 n=q1 校驗(yàn)位 nk=2t 最小距離 dmin=nk+1(MDC碼 ) 生成多項(xiàng)式 g(x)=(xa)(xa2)…(x a2t) =ankxnk+ank1xnk1+…+a 1x+a0 信息論與編碼 BCH碼和 RS碼 ? RS碼的重量分布是已知的。第二是因?yàn)榇嬖谝环N有效的硬判決法，使得在許多需要長碼得應(yīng)用場合，該碼能夠被實(shí)現(xiàn)。 qA DjiDqin jiijjim i nm i n 1)1(0)1( ???????????? ??????????? ? ?信息論與編碼 BCH碼和 RS碼 ?二進(jìn)制衍生碼 對于一個(gè) q=2m進(jìn)制（ n， k） RS碼，如果不用 q進(jìn)制調(diào)制發(fā)送，而是將每碼元對應(yīng)為 m比特后以二進(jìn)制發(fā)送 ,實(shí)際上就是把 q進(jìn)制 RS碼化作了（ mn， mk）二進(jìn)制衍生碼，這樣的二進(jìn)制衍生碼特別適用于糾突發(fā)差錯(cuò)，下面舉例說明。如輸入的 8進(jìn)制信息元為 a5a3a1，問編出的 8進(jìn)制 RS碼字是什么，糾錯(cuò)能力如何？ 解： n=7,k=3,dmin=nk+1=5,糾錯(cuò)能力 t=2，生成多項(xiàng)式為 g(x)=(xa)(xa2)(xa3)(xa4) =x4+a3x3+x2+ax+a3 信息論與編碼 BCH碼和 RS碼 信息多項(xiàng)式為 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ā)錯(cuò)誤的能力： ? 八進(jìn)制 RS碼能糾每碼字兩個(gè)字符的差錯(cuò)。 ? 一般的結(jié)論：若 q進(jìn)制（ q=2m） RS碼的糾錯(cuò)能力是 t個(gè) q進(jìn)制符號，那么它的二進(jìn)衍生碼能糾正的二進(jìn)制突發(fā)差錯(cuò)長度 b為 1)1( ??? mtb信息論與編碼 碼的擴(kuò)展和縮短 ?碼的擴(kuò)展和縮短： 可以通過增加或刪除信息位或校驗(yàn)位的方法改變碼率，改變糾檢錯(cuò)能力，以滿足不同的需要。 若對每一個(gè)碼字 ( 1, 2, …, c1. c0)增加一個(gè)校驗(yàn)元 c’0， 滿足以下校驗(yàn)關(guān)系： 1+2+… +c1+c0+c’0=0 稱 c’0為全校驗(yàn)位 。 最小碼距由 3增加為 4 ^H信息論與編碼 碼的擴(kuò)展和縮短 信息論與編碼 碼的擴(kuò)展和縮短 碼的縮短： 縮短循環(huán)碼就是在 (n， k)循環(huán)碼的 個(gè)碼字中挑選出前 i位均為 0的所有碼字，組成一個(gè)新的 (ni, ki)縮短循環(huán)碼碼集。反之，次數(shù)小于 ni的所有 g(x)倍式一定包含于該子集中，是 (ni, ki),縮短循環(huán)碼的一個(gè)碼多項(xiàng)式。 k2信息論與編碼 碼的擴(kuò)展和縮短 knx?特點(diǎn)： 1. 碼的重量沒有變， 2. 校驗(yàn)位的數(shù)量也沒有變（ ni(ki)=nk） , 因此 (ni,ki)縮短循環(huán)碼的糾錯(cuò)能力于原來的（ n,k）循環(huán)碼碼完全一樣， 3. 碼率 R下降了，由 k/n變?yōu)?(ki)/(ni). 4. 循環(huán)碼的外部特征在縮短循環(huán)碼中已不復(fù)存在，縮短碼碼字的循環(huán)未必仍是碼字； 5. 循環(huán)碼的內(nèi)部特征仍然存在，即所有的碼多項(xiàng)式一定能夠被 g(x)整除。 ? 縮短循環(huán)碼用于檢錯(cuò)時(shí)也和循環(huán)碼一樣，只要將接收序列除以 g(x)后檢查其余式即可，余式全0(除盡 )則表示接收的時(shí)碼字 (g(x)的倍式 )，否則就不是碼字。 在數(shù)據(jù)通信中，信息都是先劃分成小塊再組裝成幀后(或叫分組、包、信元，僅名稱不同而已 )在線路上統(tǒng)計(jì)復(fù)用傳送或存入共同物理介質(zhì)的，幀尾一般都留有 8，12， 16或 32位用作差錯(cuò)校驗(yàn)。只要以一個(gè)選定的 (n， k)循環(huán)碼位基礎(chǔ)，改變 i值，就能適用于任何信息長度的編碼。由于 i可變，因此幀長可變。 另外，由此 g(x)生成的 碼字的重量一定是偶數(shù) ，所以它就能檢出所有奇數(shù)個(gè)差錯(cuò)。由于 i可變，因此幀長可變。輸完 k－ i信息位后斷開移存器的反饋線，將此時(shí)移存器內(nèi)的數(shù)據(jù)（余式，即 CRC校驗(yàn)碼）移位輸出即可。如為零，說明傳輸無誤；如余式非零，說明該幀有差錯(cuò)，須反饋重發(fā)和丟棄。 16x信息論與編碼 碼的擴(kuò)展和縮短 5x 12x 16x 10D接收端校驗(yàn)時(shí)，只要將整個(gè)幀除以 g（ x）檢查余式是否為零即可。 ?作業(yè) ? 611， 612， 613