【文章內(nèi)容簡介】 力 和 效 果 ， 有 兼 容 性 強 等 更 完 善 的 特 點 ， 本 次 設(shè) 計 也 主 要 使 用 VHDL 語 言 進行 代 碼 編 寫 ， QuartusII 軟 件 進 行 模 擬 仿 真 。北華航天工業(yè)學(xué)院畢業(yè)論文9第 3 章 常用循環(huán)碼簡介 循環(huán)碼循環(huán)碼是在嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)上建立起來的，是線性分組碼的一種。這種碼的編碼和解碼設(shè)備都不太復(fù)雜，而且糾錯的能力較強。顧名思義，循環(huán)碼除具有線性碼的一般性質(zhì)之外，還具有循環(huán)性，即任一碼組循環(huán)移位以后，仍為該碼中的一個碼組。在代數(shù)編碼理論中，為了便于計算，經(jīng)常將循環(huán)碼表示成碼多項式的形式，設(shè)碼組為 ，則碼多項式定義如下：),(0121aan??? 0121)( axaxXTn?????在循環(huán)碼除全“0”碼組外，再沒有連續(xù) k 位均為“0”的碼組，即連“0”的長度最多只有 位。否則，在經(jīng)過若干次循環(huán)移位后將得到一個 k 位信息位全為“0” ，但)1(?k監(jiān)督位不全為“0”的一個碼組。因此， 必須是一個常數(shù)項不為“0”的 次多)(xg )(kn?項式，而且這個 還是這種碼中次數(shù)為 的唯一一個多項式，稱這唯一的)(xgkn?次多項式 為碼的生成多項式。一旦確定了 ，則整個 循環(huán)碼就被確)(kn? )(xg),(定了。由此，可以寫出循環(huán)碼的生成矩陣 G.通常這時得到的循環(huán)碼的生成矩陣不是典型矩陣，可通過線性變換轉(zhuǎn)為典型矩陣，則循環(huán)碼組可寫成： ??)()(21XGaXTknn???? )1(xgxaG??所有的碼組多項式 都可被 整除，而且任意一個次數(shù)不大于 的多項式)(x)(g )1(?k乘 都是碼多項式，該條性質(zhì)用于編碼，還可用于驗證接收碼組是否出錯。)(xg由于任一循環(huán)碼多項式 都是 的倍式，故可寫成 ，而)(T)(x )()(xghXT?本身也是一個碼組，即有 。由于 是一個 次多項式，故)( gX?? )(?kn?是一個 n 次多項式，在模 運算下，也是該編碼中的一個許用碼組?？梢詫懗蒟Txk? 1?n，又由于等式左端分子和分母都是 n 次多項式，故 。因此，)()(xQ?? 1)(?xQ上式可化成 。最后，可得到 。由此說明，)(1xTn?? ??)(1hxgk???北華航天工業(yè)學(xué)院畢業(yè)論文10應(yīng)該是 的一個因子。)(xg1?n RS 碼RS 碼以它的發(fā)現(xiàn)者理得（Reed）和索羅蒙（Solomon）的姓氏開頭字母命名，是BCH 碼最重要的一種子類（q 進制 BCH 碼） 。RS 碼的每個碼元取值于 q 元符號集，使用時通常選取 q 為 2 的冪次 ，使 q 元符號集的所有非},0{21?q?? )2(mq?零元素 是基于某個 m 次本原多項式 擴域的元素。編碼時，每 m0? GF個信息比特映射為一個 q 進制碼元， 便于與具有 4，8，16，32…點數(shù)的 PSK 或)(?QAM 調(diào)制信號集相匹配。近年來采用最多的是 m=8，即 進制的 RS 碼，以便256?q將整個 8bit 字節(jié)變?yōu)?RS 碼的一個碼元。本原 RS 碼具有如下參數(shù)：碼長 ，校驗位 nk=2t，最小距離 ，生成多項式1??qn 1min???kd0122)(,)()( axxaaxxaxg knkt ?????式中， 的各次系數(shù) 對照 可知，RS??22,1,0??qin???? mi?d碼是極大最小距離碼，從這種碼的 n、k 值立即可斷定其糾錯能力 ])(int[]it[mi kd??RS 碼的重量分布是已知的。在碼重多項式第 i 次項的系數(shù)是：?? min01,)()1(min mindqqADj Djijiini ?????? 非本原 BCH 碼非本原 BCH 碼與本原 BCH 碼的主要區(qū)別在于采用的根是否是本原元。本原多項式的根 的階 ，因此給定 n 后即可知道本原多項式的次數(shù) m，從而得到擴域?12??mn；而非本原多項式的根 的階 n 是 的因式，給定 n 后還需要計算 m。)(GF?12?m若碼長 ，但 n 是 的因子； 是 域中的一個 n 階元素但不是?m?)(GF本原元；設(shè) 是以 為根的最低次多項式，則用 生成的循環(huán)碼稱為非)(xgt2,? (xg本原 BCH 碼。北華航天工業(yè)學(xué)院畢業(yè)論文11給定碼長 n 和糾錯能力 t 后，二進制非本原 BCH 碼的構(gòu)造方法如下：（1） 找出滿足 n 是 的因子的最小 m 值。12?m（2） 找出一個 m 階本原多項式 ，生成二元擴域 。)(xp)2(mGF（3） 求出 的根 ，找出一個 n 階的非本原元 ， 。)(xp??n1???（4） 計算 對應(yīng)的最小多項式 ，并計算生成1253,?t?? )(,)(,221xxt???多項式 。??)(,)(,)( 23xLCMgt????BCH 碼的基本特點是其生成多項式 包含 2t 個連續(xù)冪次的根。若生成多項式含有g(shù)2t 個連續(xù)冪次的根，則該碼的最小距離 ，也就是說該碼糾錯能力是1??tdm，BCH 的出現(xiàn)為通信系統(tǒng)設(shè)計者們在糾錯能力、碼長和碼率的選擇和控??tdm??2)1(int制上提供了很大的靈活性，一旦要求的糾錯能力 t 給定，只要算出 2t 個連續(xù)冪次的根所對應(yīng)的多項式作為生成多項式，就可以得到糾錯能力符合要求的碼。 小結(jié)本章主要對循環(huán)碼、RS 碼、非本原 BCH 碼做了簡單介紹，同時也做了簡單的分析比較，對本次設(shè)計優(yōu)化方法選擇起到關(guān)鍵作用，有關(guān)本原 BCH 碼的介紹在下一章中有詳細(xì)的內(nèi)容，本原 BCH 碼也是循環(huán)碼中最具特殊性的碼類之一，主要考慮本原 BCH 碼的計算量小的特點，本次設(shè)計中應(yīng)用的是本原 BCH 碼。下面討論的就是(15,7)本原 BCH 碼編譯碼器的 VHDL 設(shè)計。北華航天工業(yè)學(xué)院畢業(yè)論文12第 4 章 基于 BCH 碼設(shè)計原理 編碼器設(shè)計原理BCH（bose chaudhuri hocquenghem）碼是循環(huán)碼中的一大子類，它可以是二進制碼，也可以是非二進制碼。本次設(shè)計中主要討論二進制本原 BCH 碼。二進制本原 BCH 碼具有下列參數(shù) ，式中 ,和糾錯能力????????12mintdk)3(?m是任意正整數(shù)。BCH 碼的基本特點是其生成多項式 包含 個連續(xù)冪次的)2(1??mt )(xgt2根。若生成多項式含有 個連續(xù)冪次的根，則該碼的最小距離 ，也就是說該t2 1min??d碼糾錯能力是 。BCH 碼的出現(xiàn)為通信系統(tǒng)設(shè)計者們在糾錯能力、碼長和????d?1intmi碼率的選擇和控制上提供了很大的靈活性，一旦要求的糾錯能力 t 給定，只要算出 個t2連續(xù)冪次的根所對應(yīng)的多項式作為生成多項式，就可能得到糾錯能力符合要求的碼。已知碼長 n 及糾錯能力 t，二元本原 BCH 碼具體的設(shè)計步驟如下：1. 由關(guān)系 算出 m，表查找 m 次本原多項式 ，用它產(chǎn)生一個 擴12?? )(xP)2(mGF域。2. 以本原多項式 的根為本原元 ，分別計算 2t 個連續(xù)冪次根 所)(xP?t2,??對應(yīng)的二元域上的最小多項式 。)(,221xmmt?3. 計算這些最小多項式的最小公倍式，得到生成多項式為。][)(221LCMxgt??4. 用關(guān)系式 ，導(dǎo)出系統(tǒng)碼字 ，也可利用)(rkn? )()(xrx??編出 BCH 碼字。)(xgmxC?根據(jù)課題要求利用 VHDL 分別設(shè)計 BCH 碼的編碼器和譯碼器，代入上式，得)7,15(，計算出 即（111010001）,導(dǎo)出5,27,415?dtkn 14678???xxg系統(tǒng)碼字 ,將 從 0000000 到 1111111 分別代入，得部份)()(xrx?0123456m北華航天工業(yè)學(xué)院畢業(yè)論文13系統(tǒng)碼字為 譯碼器設(shè)計原理BCH 碼是一種循環(huán)碼，因此線性分組碼和循環(huán)碼的譯碼方法對 BCH 碼同樣適用，其中伴隨式譯碼仍是最為通用的譯碼方法。譯碼的具體步驟與循環(huán)碼一樣，包括： 計算出伴隨式 s。)(xr 。)(e 得到發(fā)送碼字的估值，完成譯碼。如果是非系統(tǒng)碼，還須由)(rxC??計算出信息多項式 。)(gm)(xm但鑒于 BCH 碼自身的結(jié)構(gòu)特點，BCH 碼的譯碼方法也具有一些特殊性。 由接收多項式 r(x)求伴隨式 s設(shè) BCH 碼的碼多項式為 由01221)( cxcxcxCnn ??????????????1101001001000)(???????xC北華航天工業(yè)學(xué)院畢業(yè)論文14知，若 是生成多項式 的根，則必是 的根，因此)()(xghC?)21(tii??)(xg)(xC （401)21 ?????? cccc iinnii ???1）寫成矩陣形式為 ??)((210??Tniin??（42）設(shè) ，代入式（42） ，得到ti? （43）即 cA=0，將上式與0)()()( 121321223210 ??????????? ???ntnnttnccA????????相比較可以看出，式（43）中的矩陣 A 等效為校驗矩陣0()(??TTTGHmcH的轉(zhuǎn)置，即 BCH 碼的校驗矩陣為 （44）??????????12212321)()(1)(nttt ntn??????如果 是 的共軛元，則當(dāng)且僅當(dāng) 時，有 。也就是說，如果碼j?i 0?ic0?jc字序列 c 和 H 矩陣第 i 行的內(nèi)積為零，則 c 和 H 的第 j 行的內(nèi)積也為零，因此可消去 H的第 j 行。于是 BCH 碼的校驗矩陣 H 可以改寫成為 ??????????12121232)()(nttt nt?????（45）設(shè)接收多項式 （4)()( 0121 xecrxxrxrnn ????????6）該接收多項式的伴隨式為 ，將式（45）和式（46）代入TtrHss),(21?s，得 tirrr njjiiiinini 21,)((100)2()1( ????? ???? ????（47）由此求出伴隨式的各個分量?？紤]碼長 n 為 15，糾 2 個錯誤的 BCH 碼。令 為 的本原元，則該碼的奇偶)(4GF北華航天工業(yè)學(xué)院畢業(yè)論文15校驗矩陣為 。利用 的四維向量??????? 423963027418512963 119764 ???H )2(4GF表示法和等式 ，將 H 的每個元素都表示為它所對應(yīng)的四維向量，得到該碼的二進15制奇偶校驗矩陣如下：。???????????011011H接收多項式 ，接收多項式的伴隨式)()(11314 xecrxrxr ?????， 。THss?,(4321 41,013 ?irs iiiii ??? 由伴隨式求出錯誤位置由于錯誤圖樣和伴隨式一一對應(yīng)，求出伴隨式理論上就知道了錯誤位置。如前所述，與線性分組碼中介紹的查表法譯碼原理一樣，利用標(biāo)準(zhǔn)陣的陪集首與伴隨式的關(guān)系，將其制成表格，在求得了伴隨式后，通過查表就可以得到所對應(yīng)的錯誤圖樣。標(biāo)準(zhǔn)陣中的陪集首通常按照錯誤的個數(shù)從小到大排列。對于 循環(huán)碼，產(chǎn)生 1 個),(kn傳輸錯誤的錯誤樣圖個數(shù)為 ，產(chǎn)生 i 個的個數(shù)為 ，等等。當(dāng)碼長 n 比較小且糾錯1nCinC能力 t 較小時，查表法簡單有效。但是隨著 n 和 t 的增大，查表法將變得復(fù)雜，這時可以采用通過求解錯誤位置多項式的方法來確定錯誤位置，從而避免復(fù)雜的查表過程。BCH 碼伴隨式的各個分量 可以表示為 （4is )()(iiiii ecrs?????8）假設(shè) 已由式（47）求出。設(shè) 在 位置上出錯，即is )(xevjjx,21? （4vjjj jxxev ?????? 210,)(21北華航天工業(yè)學(xué)院畢業(yè)論文169）將（49）代入式（48） ，得 ,為方便起見，令???????tjtjtjt jjj jvvvss 2222 22221 )()()(11 ??????，則上式可化簡得 （4vlljl??1,????????tttt vvs22222211??????10）式（410）中列出了 個方程，其中 是 個已知數(shù)， 是 vt ts21,? ?,21?個未知數(shù)，需要求解這個非線性方程，從而得到錯誤位置數(shù) 。而實際上任何v?,21?一種解方程的方法就是一種譯碼算法。下面用迭代算法解答（410）式。首先定義一個錯誤位置多項式 ，它的根是錯誤位置的倒數(shù) ，即)(x? 112,??v?? （4vv xxx ???? ?? ????? 210211()()(11）將式（410）的乘積展開，比較等式兩邊同冪次的系數(shù)，有???????vv vv???????2113210（412）式 410）給出了 與 的關(guān)系，式（411）給出了 與 的關(guān)系，將兩者結(jié)合起來并isl l?l?利用式（410）——式（412）可以得到 與 的關(guān)系isl???????????03021211312 sssvvvv ????（413）稱為牛頓恒等式。如果 和錯誤個數(shù) v 已知，則利用上述 v 個方程組即可求出 v 個未知is數(shù)；如果 v 未知，假設(shè) v=t，根據(jù)自回歸建模技術(shù)，可以由伴隨式構(gòu)造出一個矩陣，利北華航天工業(yè)學(xué)院畢業(yè)論文17用前 t 個伴隨式來得到下一個伴隨式，經(jīng)過數(shù)學(xué)運算，可得到有 t 個未知數(shù)的 t 個方程構(gòu)成的一個線性方程組，用矩陣表示為 ??????????