RS編譯碼原理

《RS編譯碼原理》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1RS碼字RS碼(Reed-solomoncodes)一種低速率的前向糾錯(cuò)的信道編碼，是一類(lèi)具有強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH碼，在線(xiàn)性分組碼中，它的糾錯(cuò)能力和編碼效率是最高的。相比于其他線(xiàn)性分組碼而言，在同樣的效率下，RS的糾錯(cuò)能力是特別強(qiáng)的，特別是在短的中等碼長(zhǎng)下，其性能接近于理論值，它不但可以糾正隨機(jī)錯(cuò)誤，突發(fā)錯(cuò)誤及兩者的結(jié)合，而且可以用來(lái)構(gòu)造其他碼型，如級(jí)聯(lián)碼。其編碼過(guò)程首先在多個(gè)點(diǎn)上對(duì)這些多項(xiàng)式求冗余，然后將其傳輸或者存儲(chǔ)。對(duì)多項(xiàng)式的這種超出必要值的采樣使得多項(xiàng)式超定（過(guò)限定）。當(dāng)接收器正確的收到足夠的點(diǎn)后，它就可以恢復(fù)原來(lái)的多項(xiàng)式，即使接收到的多項(xiàng)式上有很多點(diǎn)被噪

2、聲干擾失真。1.1RS編碼RS碼是一類(lèi)糾錯(cuò)能力很強(qiáng)的特殊的非二進(jìn)制BCH碼。對(duì)于任選正整數(shù)S可構(gòu)造一個(gè)相應(yīng)的碼長(zhǎng)為n=qS-1的q進(jìn)制BCH碼，而q作為某個(gè)素?cái)?shù)的冪。當(dāng)S=1，q>2時(shí)所建立的碼長(zhǎng)n=q-1的q進(jìn)制BCH碼，稱(chēng)它為RS碼。當(dāng)q=2m(m>1)，其碼元符號(hào)取自于GF(2m)的二進(jìn)制RS碼可用來(lái)糾正突發(fā)差錯(cuò)，它是最常用的RS碼。一個(gè)RS碼有以下幾個(gè)參數(shù)：碼長(zhǎng)：n=2^m-1個(gè)符號(hào)或者m(2m-1)比特信息段：k個(gè)符號(hào)或者mk個(gè)比特監(jiān)督段：2t=n-k個(gè)符號(hào)2mt=m(n-k)個(gè)比特最小碼距：dmin=n-k+1個(gè)符號(hào)或者mdmin=m(n-k+1)例如，對(duì)R

3、S（204,188）碼來(lái)說(shuō)，源數(shù)據(jù)被分割為188個(gè)符號(hào)為一組，經(jīng)過(guò)編碼變換后，成為204個(gè)符號(hào)長(zhǎng)度的碼字。長(zhǎng)度為16個(gè)符號(hào)的監(jiān)督為可以糾正碼字中出現(xiàn)的最多8個(gè)符號(hào)錯(cuò)誤。RS編碼的框圖如圖所示：RS編碼器的結(jié)構(gòu)RS碼的基本思想就是選擇一個(gè)合適的生成多項(xiàng)式g(x)，并且使得對(duì)每個(gè)信息段計(jì)算得到的碼字多項(xiàng)式都是g(x)的倍式，即使得碼字多項(xiàng)式除以g(x)的余式為0。這樣，如果接收到的碼字多項(xiàng)式除以g(x)的余式不是0，則知道接收碼字的余式存在錯(cuò)誤；而且通過(guò)進(jìn)一步可以糾正最多t=(n-k)/2個(gè)錯(cuò)誤。RS碼生成多項(xiàng)式一般按照如下公式選擇，即g(x)=(x-a)(x-a2)(x-

4、a3)···(x-a2t-1)(x-a2t)式中，ai是GF(2m)中的一個(gè)元素。如果用d(x)表示信息段多項(xiàng)式，則可以按照如下方法構(gòu)造碼字多項(xiàng)式c(x)。首先計(jì)算商式h(x)和余式r(x)，得xn-kd(x)/g(x)=h(x)g(x)+r(x)取余式r(x)作為校驗(yàn)字，然后令c(x)=xn-kd(x)+r(x)即將信息位放置于碼字的前半部分，監(jiān)督位碼字放在后半部分，則c(x)/g(x)=xn-kd(x)/g(x)+r(x)/g(x)=h(x)g(x)+r(x)+r(x)=h(x)g(x)因此，碼字多項(xiàng)式c(x)，必可以被生成多項(xiàng)式g(x)整除。如果在接收端檢測(cè)不到余

5、式為0，則可判斷接收到的碼字有錯(cuò)誤。由于這種RS能糾正t個(gè)m進(jìn)制的錯(cuò)誤碼字，所以，RS碼特別適用于突發(fā)錯(cuò)誤的信道以RS（7,3）碼為例介紹RS碼的編碼過(guò)程。RS（7,3）碼利用3個(gè)信息符號(hào)得到長(zhǎng)度為7的編碼，碼元符號(hào)取自GF（23）.即m=3。域GF（23）的本原多項(xiàng)式為a3+a+1，RS碼的生成多項(xiàng)式為g(x)=x4+3x3+x2+2x+3。假如輸入符號(hào)為[406]，則信息多項(xiàng)式d(x)=4x2+6。生成碼字的過(guò)程如下：(1)由于碼元符號(hào)取自域GF（23），所以一個(gè)符號(hào)可以由3比特表示，x4d(x)的二進(jìn)制比特表示為[100000110000000000000]；(2

6、)g(x)的二進(jìn)制比特表示為[001011001010011]；(3)計(jì)算xn-kd(x)/g(x)得到的余式r(x)的二進(jìn)制比特表示為[100010010000]，因此校驗(yàn)位為[4220]；(4)生成的碼字即為[4064220].1.1RS譯碼RS碼的譯碼算法是從BCH碼的譯碼算法演變而來(lái)的。與編碼算法相比，譯碼算法比較復(fù)雜，需要的運(yùn)算量也比較大。其中，比較有代表性的算法是Berlekamp-Messay算法(簡(jiǎn)稱(chēng)BM算法)和Euclid算法。在這兩種算法的基礎(chǔ)上，后來(lái)又派生出了一些修正算法或陜速算法。RS碼的譯碼可以按照下面的步驟來(lái)進(jìn)行:1.由接收多項(xiàng)式計(jì)算伴隨式；

7、2.用BM算法或Euclid算法，由伴隨式，求出錯(cuò)誤位置多項(xiàng)式；3.用Chien搜索法求伴隨式的根，其倒數(shù)為錯(cuò)誤位置數(shù);4.計(jì)算錯(cuò)誤值；5.接收多項(xiàng)式減去錯(cuò)誤多項(xiàng)式，完成糾錯(cuò)。如圖所示RS譯碼器原理框圖譯碼最關(guān)鍵和最復(fù)雜的一個(gè)步驟是求出錯(cuò)位置多項(xiàng)式，求取關(guān)鍵方程組的常用算法Berlekamp-Massey算法、Euclid算法。以下是BM的算法流程