【文章內(nèi)容簡介】 第二步：由伴隨多項(xiàng)式求出錯(cuò)誤圖樣； 第三步：由得到最可能發(fā)送的碼字，完成譯碼。針對整個(gè)譯碼過程，BCH碼的譯碼存在許多算法，這些算法根據(jù)不同的特點(diǎn)得以廣泛的應(yīng)用。其中，從變換域的觀點(diǎn)來分類，可將BCH譯碼分為時(shí)域和頻域兩種。所謂頻域算法是先將接收多項(xiàng)式進(jìn)行離散傅立葉變換，然后在頻域中求出錯(cuò)誤圖樣的頻譜，最后再進(jìn)行反變換求出錯(cuò)誤圖樣；而所謂時(shí)域算法則是求錯(cuò)誤圖樣的所有計(jì)算都是在時(shí)域中進(jìn)行的。就運(yùn)算量和實(shí)現(xiàn)而言，時(shí)域算法譯二進(jìn)制BCH碼比頻域算法簡單，于是下面就按照上述步驟對時(shí)域算法進(jìn)行論述。在時(shí)域里，一般二進(jìn)制BCH碼的譯碼步驟以第2步最為復(fù)雜，決定譯碼器復(fù)雜性和速度的主要因素也在于這一步如何求，如何簡化和加快這一步是BCH碼譯碼的關(guān)鍵。 有限域的基本運(yùn)算在譯碼算法實(shí)現(xiàn)中涉及到域上的元素的二進(jìn)制表示和指數(shù)表示形式。有限域上的運(yùn)算主要有域元素的加法、減法、乘法、求逆和除法運(yùn)算。對于特征為2的域，它的減法運(yùn)算與加法運(yùn)算是同樣的運(yùn)算。而除法運(yùn)算可以轉(zhuǎn)換成逆元相乘的運(yùn)算。因此最主要的就是加法、乘法和求逆的三種運(yùn)算。 元素的二進(jìn)制表示和指數(shù)形式表示域元素（指數(shù)形式）二進(jìn)制表示十進(jìn)制域元素（指數(shù)形式）二進(jìn)制表示十進(jìn)制00011010150010210101001004011171000811101400113111115011061101131100121001910111100011加法運(yùn)算非常簡單，只要把兩個(gè)元素對應(yīng)的向量表示進(jìn)行異或運(yùn)算。例如，本文涉及到伽羅華域中的兩個(gè)域元素相加，設(shè)兩個(gè)域元素為A、B，和為C。兩個(gè)域元素的乘法就是冪表示時(shí)的指數(shù)部分在實(shí)數(shù)域上的加法，對于域上的元素，利用伽邏華（Galois）域的循環(huán)性質(zhì)，就是對15求模運(yùn)算。 例如：在BCH碼的譯碼時(shí)需要應(yīng)用伽羅華域的求逆運(yùn)算，對于的一個(gè)域元素，用冪次表示為：，則它的逆為 ，而一個(gè)域元素在實(shí)際運(yùn)算時(shí)一般都用字節(jié)表示，我們可以利用“字節(jié)表示”和“冪次表示”對應(yīng)表進(jìn)行相互轉(zhuǎn)換。 伴隨多項(xiàng)式的計(jì)算伴隨多項(xiàng)式的計(jì)算是BCH碼譯碼的第一步，設(shè)發(fā)送碼字、接收碼字和錯(cuò)誤圖樣分別為： （211） （212） （213）若信道產(chǎn)生個(gè)錯(cuò)誤，則 （214）上式中，,稱為錯(cuò)誤位置數(shù)，說明錯(cuò)誤發(fā)生在中的第的系數(shù)算第一位）位，錯(cuò)誤值是。由伴隨式定義和BCH的校驗(yàn)矩陣可知： （215）若令，經(jīng)計(jì)算得： （216）我們的目的就是求式（216）中的個(gè)未知數(shù)，但是要直接求比較困難，所以分兩步進(jìn)行，先解出錯(cuò)誤位置數(shù)，再求錯(cuò)誤值。而對于二進(jìn)制情況，錯(cuò)誤值只可能為1，所以求錯(cuò)誤值這一步可以省略，關(guān)鍵是求出錯(cuò)誤位置數(shù)，為此我們引入錯(cuò)誤位置多項(xiàng)式。 錯(cuò)誤多項(xiàng)式的求取定義錯(cuò)誤多項(xiàng)式為： （217）的根就是錯(cuò)誤位置的倒數(shù)，通過求解的根可確定錯(cuò)誤的位置。若為錯(cuò)誤位置，則將上式兩邊乘以并對求和得由定義可將上式化簡為 （218）把上式展開，則 （219） 或 （220）式（219）是一組線性方程，有個(gè)方程和個(gè)未知數(shù)，該方程有解的充要條件是式（220）中的M矩陣滿秩。式（220）稱為求的關(guān)鍵方程式。所以如何快捷準(zhǔn)確地求出錯(cuò)誤位置多項(xiàng)式就成為BCH碼的關(guān)鍵。求的譯碼算法既有時(shí)域算法也有頻域算法，其中時(shí)域算法主要有Peterson算法、Euclidean算法、BerlekampMassey算法等。Peterson算法通過對式（220）應(yīng)用常規(guī)線性方程組的解法，將錯(cuò)誤位置多項(xiàng)式的系數(shù)直接表示為伴隨式值的解析關(guān)系式，這種算法的優(yōu)點(diǎn)是簡潔快速，但是當(dāng)t6時(shí)，則難以利用線性方程組直接求解，此時(shí)就必須采用遞歸的方法來進(jìn)行計(jì)算，即Euclidean算法、BerlekampMassey等。由于本文采用的是BCH(15,7,5)碼，此時(shí)t＝2，所以可以直接利用線性方程組求解。具體實(shí)現(xiàn)方法如下：（1）計(jì)算。根據(jù)式（215）得到：分別計(jì)算出。上式中計(jì)算根據(jù)伽邏華（Galois）域的循環(huán)性質(zhì)＝， ＝，＝， ＝，＝又根據(jù)二進(jìn)制編碼理論可知：，從而得到。（2）由于BCH（15,7,5）碼可糾正兩位錯(cuò)誤（t＝2），根據(jù)式（2－20）可得從上式可解出 從而得到錯(cuò)誤多項(xiàng)式 錯(cuò)誤位置的求取在求得錯(cuò)誤位置多項(xiàng)式后，需再求出的根以確定錯(cuò)誤位置，錢聞天提出了著名的Chien搜索算法[7]，從工程上解決了此問題，該算法本質(zhì)上是一種窮盡搜索法，即對碼的每個(gè)位置逐位予以檢索來確定其錯(cuò)誤位置。對于BCH（15,7,5）碼來說，其錯(cuò)誤多項(xiàng)式為：，在此，沒有采用傳統(tǒng)的Chien搜索算法，而是采用了分解因式法進(jìn)行求解。假設(shè)方程的兩個(gè)根分別為和，可知，利用上述關(guān)系搜索分解出相應(yīng)的根。經(jīng)過這樣的簡化，使得糾兩位錯(cuò)的BCH碼的譯碼算法更加簡便。主要實(shí)現(xiàn)程序如下：for i=1：1：（Q2+1） （Q2為二次項(xiàng)系數(shù)） D=B（ ： ，i）+B（ ： ，（Q2+2i））。 （搜索分解，計(jì)算分解項(xiàng)之和） D=mod（（D），2）。 （對向量D進(jìn)行系數(shù)模2運(yùn)算，）F=B（ ： ，（Q1+1））。 if D==F （說明這次分解因式成功） u=u+1。 （找到一個(gè)錯(cuò)誤位置，計(jì)數(shù)） E（15i+1）=mod（E（15i+1）+1，2）。 （修改錯(cuò)誤圖樣）endend在程序中，QQ2分別為錯(cuò)誤多項(xiàng)式的一次項(xiàng)和二次項(xiàng)系數(shù)，E為錯(cuò)誤圖樣。 BCH（15,7,5）碼的譯碼流程圖得到錯(cuò)誤圖樣后，就可以根據(jù)錯(cuò)誤圖樣修改收到的碼字了。BCH（15,7,5）碼譯碼的流程圖： BCH（15,7,5）碼譯碼流程圖 BCH碼的性能仿真1．仿真通信系統(tǒng)模型。 仿真通信系統(tǒng)模型框圖其中，信源為隨機(jī)輸入的二進(jìn)制碼元，信道為簡單的加性高斯白噪聲信道，調(diào)制方式為BPSK調(diào)制。2．誤碼性能分析（1）BCH（15,7,5）碼的誤碼性能按照前面給出的BCH碼的編譯碼算法實(shí)現(xiàn)了BCH（15,7,5）碼的性能仿真，統(tǒng)計(jì)平均200次后。 BCH(15,7,5)碼的誤碼性能曲線 （2） 碼長對誤碼性能的影響改變BCH碼的碼長，分別對BCH(31,16,7)、BCH(63,30,13)、BCH(127,50,27)、BCH(255,91,51)四種碼進(jìn)行仿真實(shí)驗(yàn)，這四種BCH碼的糾錯(cuò)能力非常相近，但是碼長不等，分別為、對應(yīng)這四種碼分別隨機(jī)輸入長度為L1=501L2=50L3=5050、L4=5091的二進(jìn)制碼元，經(jīng)過200次的統(tǒng)計(jì)平均后。 BCH碼在不同碼長下的性能曲線，雖然這四種碼的糾錯(cuò)能力相近，但是隨著碼長的逐漸增加，BCH碼的誤碼性能越來越好，這是因?yàn)楫?dāng)碼的糾錯(cuò)能力固定時(shí)，隨著碼長的增加，碼率不斷下降，碼率越小誤碼性能就越好。經(jīng)過仿真實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)碼長時(shí)，系統(tǒng)的誤碼性能很好。但是隨著碼長的繼續(xù)增大，誤碼性能逐漸變差，當(dāng)時(shí)，碼的糾錯(cuò)能力。由此可知，在中、短碼長時(shí)BCH碼是一個(gè)很好的碼，但是在長碼時(shí)性能變壞，因此BCH碼達(dá)不到香農(nóng)編碼定理所要求的能力。（3）糾錯(cuò)能力和碼率對誤碼性能的影響 BCH碼的糾錯(cuò)能力，碼率，隨機(jī)輸入長度L=1400的二進(jìn)制碼元，通過對三種不同碼率和糾錯(cuò)能力的BCH碼仿真實(shí)驗(yàn)，經(jīng)過200次的統(tǒng)計(jì)平均后，： BCH碼在不同的糾錯(cuò)能力下的性能曲線在碼長固定的情況下，當(dāng)改變BCH碼的糾錯(cuò)能力時(shí)，其誤碼性能也隨之而變化，在此通過對比三種BCH 碼，它們的糾錯(cuò)能力和碼率分別為： 且 且，誤碼性能曲線逐漸呈現(xiàn)出好的趨勢，但是碼率此時(shí)是逐漸減小的，由此可以看出，對于BCH碼來說，隨著碼率的逐漸增大，糾錯(cuò)能力逐漸下降，誤碼性能也逐漸劣化。 RS碼的定義以及有關(guān)性質(zhì)RS碼是在上，長的本原BCH碼，RS碼是一類非二進(jìn)制循環(huán)碼，（n,k,d）RS碼中，輸入信息分成km比特一組，每組包括k個(gè)符號(hào)，每個(gè)符號(hào)由m比特組成，一個(gè)糾t個(gè)錯(cuò)誤的RS碼有如下參數(shù)：碼長 符號(hào) 或比特信息段 k 符號(hào) 或km比特監(jiān)督段nk=2t 符號(hào) 或m（nk）比特最小碼距d＝2t+1符號(hào) 或m（2t+1）比特其生成多項(xiàng)式為 （2－21）RS碼有如下特性：真正的最小距離與設(shè)計(jì)距離總是相等的，每種RS碼都是一個(gè)最大距離可分碼。這是因?yàn)槠渥钚【嚯x等于n－k+1，當(dāng)省掉RS碼的某些信息符號(hào)后，分組長度縮短，但最小距離并不減少，故任何一個(gè)縮短的碼仍是一個(gè)最大距離可分碼。在其碼字內(nèi)的任何k個(gè)位置都可用作信息集合。RS碼的編譯碼是基于一組碼元而不是單獨(dú)的0或1，這也是RS碼糾錯(cuò)能力特別強(qiáng)的原因，并且這種特點(diǎn)使得RS碼特別適合處理突發(fā)成片的錯(cuò)誤。 RS碼的編碼與譯碼[10][11]由于RS碼為循環(huán)碼，所以系統(tǒng)形式的編碼方法同BCH碼，在此不再詳述，但是由于它的非二進(jìn)制性，多項(xiàng)式的系數(shù)就不能用單個(gè)的“0”或者是“1”來表示，而是用有限域中的域元素來表示。例如RS（15,9,7）編碼，此時(shí)m＝4，t=3，當(dāng)輸入3碼元信息為1101 0010 1011時(shí)，信息多項(xiàng)式表示為：生成多項(xiàng)式表示為：編碼多項(xiàng)式表示為：余式模具有非二進(jìn)制系數(shù)的多項(xiàng)式除法比起二進(jìn)制除法要復(fù)雜的多，因?yàn)樗裱邢抻虻某朔ㄟ\(yùn)算，在此不再詳述。RS碼的譯碼算法為：（1）計(jì)算伴隨多項(xiàng)式；（2）求取錯(cuò)誤多項(xiàng)式；（3）求取錯(cuò)誤位置；（4）計(jì)算錯(cuò)誤取值；（5）根據(jù)對錯(cuò)誤多項(xiàng)式的估計(jì)糾正接收多項(xiàng)式。其中前3步的計(jì)算方法和BCH碼的譯碼算法一樣，但是由于RS碼是多進(jìn)制的表示形式，因此在求得錯(cuò)誤位置后，還需要判斷到底是錯(cuò)在哪一位，這和BCH碼的譯碼是不同的，在此只對如何計(jì)算錯(cuò)誤取值展開論述。假設(shè)系統(tǒng)有兩個(gè)錯(cuò)誤，錯(cuò)誤位置已經(jīng)確定，分別為與，為了確定對應(yīng)于和的錯(cuò)誤值和，可以用伴隨多項(xiàng)式來求解：比如選取和： 通過求解得到錯(cuò)誤取值和。這樣根據(jù)錯(cuò)誤位置和錯(cuò)誤取值得到對錯(cuò)誤多項(xiàng)式的估計(jì)，其中和是錯(cuò)誤位置，最后根據(jù)譯出碼字。 RS碼的性能仿真（1）RS（15,9,7）碼的誤碼性能仿真系統(tǒng)模型同BCH碼，隨機(jī)輸入長度L=3600個(gè)的二進(jìn)制碼元，對RS(15,9,7)碼進(jìn)行了仿真實(shí)驗(yàn)，經(jīng)過200次統(tǒng)計(jì)平均后，該碼可以糾正長度為15碼元中的3碼元的錯(cuò)誤。 RS碼的誤碼性能曲線（2）RS（15,9,7）碼糾突發(fā)錯(cuò)誤的性能因?yàn)镽S碼也是循環(huán)碼，因此BCH碼具有的性質(zhì)RS碼也都具有，在此不再詳述，但是由于它的非二進(jìn)制性，在糾正突發(fā)錯(cuò)誤方面表現(xiàn)出良好的性能。在信道中人為的給BCH碼和RS碼分別加入長度不同的突發(fā)連續(xù)錯(cuò)誤，比較其誤碼性能。，這主要是因?yàn)镽S碼的一個(gè)碼元中包含有多個(gè)比特信息，一個(gè)碼元發(fā)生錯(cuò)誤時(shí)，任何比特都有可能發(fā)生錯(cuò)誤，當(dāng)譯碼器糾正錯(cuò)誤時(shí)，它將不正確的碼元糾正過來，不管這個(gè)錯(cuò)誤是由于一個(gè)比特的錯(cuò)誤還是一個(gè)碼元中的所有比特錯(cuò)誤造成，正因?yàn)槿绱?，就賦予了RS碼相對于二進(jìn)制碼具有抵抗突發(fā)噪聲的優(yōu)勢。 突發(fā)錯(cuò)誤的誤碼性能曲線 小結(jié)本章主要討論了循環(huán)碼的性能和特點(diǎn)，對具有代表性的二進(jìn)制循環(huán)碼——BCH碼進(jìn)行了算法研究，簡化了糾兩位錯(cuò)的BCH碼的譯碼算法，通過仿真與分析，總結(jié)出了BCH碼的性能特點(diǎn)如下:（1）在中、短碼長時(shí)BCH碼是一個(gè)很好的碼，隨著碼長的增加誤碼性能越來越好；但是在長碼（L1023）時(shí)性能變差，因此BCH碼達(dá)不到香農(nóng)編碼定理所要求的能力；（2）隨著碼率的逐漸增大，糾錯(cuò)能力逐漸下降，誤碼性能逐漸劣化。本章同時(shí)對非二進(jìn)制的循環(huán)碼——RS碼的編譯碼算法進(jìn)行了仿真實(shí)驗(yàn)，它不但具有BCH碼的所有特性，而且在糾正突發(fā)連續(xù)錯(cuò)誤方面表現(xiàn)出良好的性能。通過與BCH碼的仿真對比，驗(yàn)證了RS碼具有糾突發(fā)錯(cuò)誤的優(yōu)勢，并分析了原因。第三章 卷積碼第三章 卷積碼卷積碼作為一種信道編碼，是1955年由Elias提出的。它以其優(yōu)越的性能被廣泛使用在數(shù)字通信系統(tǒng)中，如今卷積碼使用于幾乎所有的無線通信標(biāo)準(zhǔn)中，如GSM、cdma2000、IS95。（2,1,7）卷積碼已經(jīng)成為國際衛(wèi)星通信的標(biāo)準(zhǔn)。卷積碼通常用（n, k, N）表示，它是把k個(gè)信息比特編成ｎ個(gè)信息比特，但k和ｎ通常很小，特別適宜于以串行方式傳輸信息，延時(shí)小。N為編碼約束長度，說明編碼過程中互相約束的碼段個(gè)數(shù)，卷積碼編碼后的n個(gè)碼元不僅與當(dāng)前組的k個(gè)信息比特有關(guān)，而且與前N1個(gè)輸入組的信息比特有關(guān)。編碼過程中相互關(guān)聯(lián)的碼元有Nn個(gè)。是卷積碼的碼率，碼率和約束長度是衡量卷積碼的兩個(gè)重要參數(shù)。通過對卷積碼的性能仿真，我們將從實(shí)驗(yàn)中證明卷積碼的性能優(yōu)于分組碼。所以從信道編碼定理看，卷積碼是一種非常有前途的，能達(dá)到信道編碼定理所提出的碼類。由于卷積碼各組之間相互有關(guān)，因此至今尚未找到像分析分組碼那樣有效的數(shù)學(xué)工具來分析卷積碼，以致性能分析比較困難。目前，大都借助計(jì)算機(jī)來搜索好碼。卷積碼的編碼描述方法有五種：① 沖激響應(yīng)描述法；② 生成矩陣描述法；③ 多項(xiàng)式乘積描述法；④ 狀態(tài)圖描述法；⑤ 網(wǎng)格圖描述法。它包括一個(gè)由N段組成的輸入移位寄存器，每段有k級，共Nk級寄存器，一組n個(gè)模2“和”相加器，一個(gè)由n級組成的輸出移位寄存器。對應(yīng)于每段k個(gè)比特的輸入序列，輸出n個(gè)比特，N為約束長度，記做（n,k,