RS編解碼的MATLAB實(shí)現(xiàn)與分析帶實(shí)驗(yàn)報(bào)告與源碼

ID:140725 · 發(fā)表于 2016-10-11 18:16

所有資料下載（含實(shí)驗(yàn)報(bào)告和仿真及源碼）：

RS編解碼的MATLAB實(shí)現(xiàn)與分析.rar (315.72 KB, 下載次數(shù): 79)

《信息論與編碼》課程設(shè)計(jì)

RS編解碼的MATLAB實(shí)現(xiàn)與分析

中文摘要

RS碼全稱為Reed-Solomon碼，是由Irving Reed和Gus Solomon在1960年發(fā)明的。RS碼是差錯(cuò)控制領(lǐng)域中一類重要的線性分組碼，具有較強(qiáng)的糾正突發(fā)錯(cuò)誤和隨機(jī)錯(cuò)誤的能力。特別是在短碼和中等長(zhǎng)度碼的情況下，其性能接近于理論值。

由于RS碼采用了q進(jìn)制（q=2m），所以它是多進(jìn)制調(diào)制時(shí)的自然和方便的編碼手段。因?yàn)镽S碼能夠糾正小于或等于t個(gè)的隨機(jī)差錯(cuò)，或者糾正單個(gè)長(zhǎng)度為（t-1）m+1的突發(fā)錯(cuò)誤，所以適合于在衰落信道中使用，以克服突發(fā)性差錯(cuò)。而且該碼具有各種成熟，可用，有效的譯碼算法。因此RS碼在工程中被廣泛應(yīng)用，包括各種通信和計(jì)算機(jī)存儲(chǔ)系統(tǒng)中。特別是RS碼和卷積碼構(gòu)成的級(jí)聯(lián)碼，已經(jīng)被定義為深空通信的下行鏈路中的標(biāo)準(zhǔn)[1]。另外，歐洲數(shù)字視頻廣播DVB（-S/T/C）統(tǒng)一采用（204，188）RS碼。

本文將對(duì)RS碼的編解碼原理進(jìn)行闡述，并運(yùn)用MATLAB對(duì)RS碼進(jìn)行仿真和分析。

Abstract

RS codes as Reed-Solomon code, found by Irving Reed and Gus Solomon in 1960. RS code is an important class of linear block codes in the field of error control code, with a strong capacity of correcting burst errors and random errors. Especially in the case of short and medium length code, the performance is close to the theoretical value.

Using a base-Q, RS codes are the natural and convenient means in a multi-ary modulation. RS code can correct a less than or equal to t random errors, or to correct a single length (t-1) m+1 burst error, so it is suitable for the use in the fading channel in order to overcome the unexpected errors. And that the codes have a variety of mature, available, efficient decoding algorithms. Therefore, RS codes are widely used in engineering, including various communications and computer storage systems. especially in concatenated codes which consists of RS code and convolutional code, has been defined as deep-space communications standards in the downlink[1]. In addition, the European Digital Video Broadcasting DVB (-S/T/C) uniform application of (204,188) RS codes.

This RS code and decoding will be explained the principle and the use of MATLAB code for simulation and analysis of RS is also includes in this principle

Key words: RS code,Correction,MATLAB

1. RS碼的發(fā)展和現(xiàn)狀[2]

根據(jù)香農(nóng)提出的信道編碼定理，任意離散輸入無(wú)記憶平穩(wěn)信道存在信道容量C，它標(biāo)志著信道傳輸能力的上限，只要信息傳輸速率R<c，就存在一種編碼方式，當(dāng)平均碼長(zhǎng)足夠大時(shí)，譯碼錯(cuò)誤概率可以做到任意小；反之，則無(wú)論采用何種編碼方式也不可能保證錯(cuò)誤概率任意小。該定理雖然沒(méi)有明確指出如何對(duì)數(shù)據(jù)信息進(jìn)行糾錯(cuò)編碼，也沒(méi)有給出這種具有糾錯(cuò)能力通信系統(tǒng)的具體實(shí)現(xiàn)方法．但它奠定了信道編碼的理論基礎(chǔ)，從理論上指出了信道編碼的努力方向。[ color][="" align]正由于目前其成熟的理論和技術(shù)，rs碼在現(xiàn)代數(shù)字通信、數(shù)據(jù)存儲(chǔ)系統(tǒng)中得到了廣泛的應(yīng)用，具體應(yīng)用[6]見(jiàn)表1.1。[="" 0)]表1.1[="" align]

應(yīng)用領(lǐng)域	編碼方案
硬盤驅(qū)動(dòng)器	RS(32，28)碼
CD	交叉交織RS碼(CtRC)
DVD	RS(208，192)碼，RS(182，172)碼乘積碼
DAB、DVB	內(nèi)碼為卷積碼，外碼為RS(204，188)碼的級(jí)聯(lián)碼
ATSC	內(nèi)碼為卷積碼，外碼為RS(207，187)碼的級(jí)聯(lián)碼
深空通信	內(nèi)碼為卷積碼，外碼為RS(255，223)碼的級(jí)聯(lián)碼
光纖通信	RS(255，239)碼

3.研究RS碼的意義與目的[7]

在實(shí)際的通訊信道中，信號(hào)的傳輸會(huì)受到噪聲的干擾，從而在接收端不可避免地會(huì)發(fā)生錯(cuò)誤。要使信號(hào)能可靠的傳輸，即要降低信號(hào)傳輸中的誤碼率。人們采用了一系列相關(guān)技術(shù)來(lái)改善噪聲信道的接收性能，使接收信息的誤碼率盡可能降低。這些技術(shù)中，信道的糾錯(cuò)編碼及其譯碼方法處于非常重要的地位。自從1948年香農(nóng)發(fā)表了關(guān)于信道容量理論極限的重要論文之后，短短幾十年時(shí)間里，人們?cè)谛诺谰幋a研究領(lǐng)域相繼取得了眾多理論成果和突破。

信道編碼按照對(duì)信息元的處理方式不同，可分為線性分組碼和卷積碼，線性分組碼可以完全用代數(shù)方法來(lái)嚴(yán)格地表達(dá)，它的出現(xiàn)較早而且其譯碼方法也較為簡(jiǎn)單，因此容易被人們所認(rèn)識(shí)，現(xiàn)在有關(guān)線性分組碼的理論已經(jīng)相當(dāng)成熟。卷積碼雖然也早已出現(xiàn)，但由于其編碼結(jié)構(gòu)不能較好的用代數(shù)方法表示，因此給卷積碼的理論研究帶來(lái)了一定的困難。但是，單獨(dú)的線性分組碼或卷積碼在性能上離香農(nóng)理論極限還相差較遠(yuǎn)。為了進(jìn)一步提高編碼的糾錯(cuò)性能，人們采用了不同的措施，其中將兩個(gè)編碼進(jìn)行串行級(jí)聯(lián)是一種有效的方法。級(jí)聯(lián)碼一般采用Rs碼作為外碼，卷積碼作為內(nèi)碼，因此可以同時(shí)糾正隨機(jī)和突發(fā)的混合錯(cuò)誤。但是這種形式的級(jí)聯(lián)碼，對(duì)改善單個(gè)碼元的誤碼率仍沒(méi)有太大幫助。如何對(duì)現(xiàn)有的編碼方法進(jìn)行改進(jìn)，從而更加逼近香農(nóng)理論極限，已經(jīng)成為國(guó)際通信學(xué)界的重大課題。

RS碼具有很強(qiáng)的抗突發(fā)誤碼的能力，因此被廣泛應(yīng)用于各種通信領(lǐng)域。正因?yàn)镽S編碼的應(yīng)用范圍非常廣泛，對(duì)于RS編／解碼技術(shù)的研究一直是國(guó)內(nèi)外通信系統(tǒng)研究的一個(gè)熱點(diǎn)，特別是RS編／解碼的硬件設(shè)計(jì)更是其中之重點(diǎn)和難點(diǎn)。

4.基礎(chǔ)理論4.1 RS編碼

RS編碼是一種線性的塊編碼[8]，其表示形式為RS(n，k)。當(dāng)編碼器接收到一個(gè)數(shù)據(jù)信息序列，該數(shù)據(jù)信息序列被分割成若干長(zhǎng)度為k的信息塊，并通過(guò)運(yùn)算將每個(gè)數(shù)據(jù)信息塊編碼成長(zhǎng)度為k的編碼數(shù)據(jù)塊。在RS碼中的碼元符號(hào)不是二進(jìn)制而是多進(jìn)制符號(hào)，其中2m進(jìn)制使用更為廣泛。RS碼是建立在GF(2m)上(m>=3，m是任意整數(shù))有限域上，且RS碼是MDS碼，具有極大最小距離特性，它具有卓越的糾錯(cuò)能力，無(wú)論是糾突發(fā)錯(cuò)誤還是糾隨機(jī)錯(cuò)誤的能力，以及它的快速譯碼速度，均是其它碼類無(wú)法比擬的。用MS多項(xiàng)式產(chǎn)生的是非系統(tǒng)碼，而用BCH構(gòu)造方法能產(chǎn)生系統(tǒng)碼。我們用的是后一種。

RS碼的定義：GF(q)上的(q≠2，q=2m)，碼長(zhǎng)n=q-1的本原BCH碼成為RS碼[2]。可知RS碼最主要的特點(diǎn)之一是碼元取自GF(2m)上，而它的生成多項(xiàng)式也在GF(q)上，所以RS碼是碼元的符號(hào)域與根域一致的BCH碼。

因?yàn)?

，（其中

）的最小多項(xiàng)式

。所以，碼長(zhǎng)為N=q-l，校驗(yàn)位n-k=2t，設(shè)計(jì)距離為

的RS碼，最小距離dmin=n-k+1。由BCH碼的定義可知，它的生成多項(xiàng)式為

從RS碼的n、k值立即可斷定其糾錯(cuò)能力為

t=int[(dmin-1)/2]=int[(n-k)/2]

由此生成一個(gè)q進(jìn)制的[q-1，q-]RS碼，有最小距離。由于線性碼的最大可能的最小距離是校驗(yàn)元的個(gè)數(shù)加l，而RS碼恰好做到了這一點(diǎn)。因此，稱RS碼為極大最小距離可分碼，簡(jiǎn)稱MDS碼。顯然RS碼的設(shè)計(jì)距離與實(shí)際距離D是一致的。如果我們要設(shè)計(jì)一個(gè)=9的RS碼，顯然RS碼的冗余位為-1=8=2t它的生成多項(xiàng)式為：

將信息段看成信息碼多項(xiàng)式m(x)，即

用信息碼多項(xiàng)式m(x)除以生成多項(xiàng)式g(x)，所得余式r(x)為監(jiān)督碼多項(xiàng)式，即

將監(jiān)督碼多項(xiàng)式r(x)置于信息碼多項(xiàng)式之后，形成RS碼。

4.2 RS譯碼

RS解碼可分為時(shí)域解碼和頻域解碼。時(shí)域解碼直接根據(jù)接收到的數(shù)據(jù)確定錯(cuò)誤位置，不需要轉(zhuǎn)換計(jì)算，相對(duì)較容易實(shí)現(xiàn)。反之，頻域解碼首先要確定錯(cuò)誤位置的傅氏變換，然后通過(guò)傅氏反變換找到錯(cuò)誤位置，因此一般采用時(shí)域解碼[9]。

本文RS碼譯碼算法采用Berlekamp算法[10-11]，該算法是從計(jì)算接收碼字得到的伴隨式入手，以下我們用c(x)表示碼字，e(x)表示有

個(gè)錯(cuò)誤得錯(cuò)誤圖樣，r(x)表示接受字，r(x)=c(x)+e(x)，

其中xi是第i個(gè)差錯(cuò)得錯(cuò)誤位置，定義

，yi是它的錯(cuò)誤值。

（1）根據(jù)接收到的碼多項(xiàng)式計(jì)算伴隨式S

而計(jì)算伴隨式之值{Sp}(p=1,2,…，2t-1,2t),就是將碼得規(guī)定根代入多項(xiàng)式r(x) ，則得，

若S=0，認(rèn)為接收無(wú)誤。若

，則由S找出錯(cuò)誤圖樣。

因?yàn)?

，而

（p=1,2,…，2t）

即

從本質(zhì)上說(shuō)，譯碼器就是求解伽邏華域GF（2m）上得這組伴隨式非線性聯(lián)立方程，由伴隨式S找出錯(cuò)誤圖樣時(shí)，先確定錯(cuò)誤位置。

由于RS碼是由伽邏華域GF（2m）上某個(gè)元素的2t個(gè)連續(xù)冪次為根的生成多項(xiàng)式所定義的，用這些根取估算一個(gè)碼字多項(xiàng)式時(shí)，可寫出xi再求錯(cuò)誤值yi。一般避免直接求解錯(cuò)誤位置xi，而代之以間接法。

（2）從伴隨式S到差錯(cuò)位置多項(xiàng)式

的迭代算法

錯(cuò)誤位置多項(xiàng)式為：

顯然，差錯(cuò)位置多項(xiàng)式的v個(gè)根式差錯(cuò)位置數(shù)的倒數(shù)

。各次項(xiàng)的系數(shù)

和

一樣是未知數(shù)。將②式展開可得：

再將③式代入①式可得牛頓恒等式：

令第μ次迭代后所得

是

次多項(xiàng)式為

這時(shí)，

表示第μ次迭代后所得得i次項(xiàng)系數(shù)。得系數(shù)一定滿足式③得前μ個(gè)牛頓恒等式，但不一定滿足第μ+1個(gè)牛頓恒等式。為了求

，先求第μ次迭代的差值

如下：

差值實(shí)際上就是將第μ次迭代的結(jié)果代入最后一個(gè)牛頓恒等式所得的結(jié)果。

如果=0，說(shuō)明的系數(shù)也滿足第μ+1個(gè)牛頓恒等式，校驗(yàn)通過(guò)。這時(shí)可令

，如果

，說(shuō)明的系數(shù)不滿足第μ+1個(gè)牛頓恒等式，差距是，這時(shí)要求做修正并求修正后的。修正后的取法是：

I．從本次的迭代回退，尋找前面某一次，比如第ρ次迭代（ρ<μ）的差錯(cuò)多項(xiàng)式

，要求該次（即第ρ次）迭代差值且

最大。

是第ρ次迭代時(shí)多項(xiàng)式

最高項(xiàng)的次數(shù)，即

II．取修正項(xiàng)為

，即令：

式中，

，

，的最高次為：

（3）利用錯(cuò)誤位置多項(xiàng)式求出差錯(cuò)位置數(shù)

將得到的錯(cuò)誤位置多項(xiàng)式的系數(shù)代入式①，可算得

（4）利用伴隨式和

的系數(shù)求出差錯(cuò)幅值

由式④和式⑤，可得：

比較它們得同次項(xiàng)系數(shù)，再代入①式，即可得：

根據(jù)⑥式即可求得差錯(cuò)幅值。

5.模塊組合

本文采用RS（7，3）碼進(jìn)行仿真，各模塊組合及其仿真流程圖如圖1所示：

圖1

其中，RS編碼與解碼已經(jīng)在基礎(chǔ)理論中做了介紹，下面著重對(duì)其他組合模塊的功能和產(chǎn)生進(jìn)行簡(jiǎn)單的介紹。

5.1 多進(jìn)制信源

用MATLAB自帶函數(shù)rand產(chǎn)生隨機(jī)數(shù)，乘以M（所要產(chǎn)生的進(jìn)制數(shù)），再經(jīng)過(guò)向下取整即可。

5.2 將多進(jìn)制信息進(jìn)行分幀

由于多進(jìn)制信源產(chǎn)生的是一連串的多進(jìn)制符號(hào)，為了進(jìn)行編碼，需將這些符號(hào)進(jìn)行分組，本次設(shè)計(jì)采用MATLAB自帶函數(shù)reshape, 將信息串（本次設(shè)計(jì)采用12000）變換成一個(gè)矩陣，該矩陣的行數(shù)為幀數(shù)（本次設(shè)計(jì)取值為4000），列數(shù)為信息位數(shù)（本次設(shè)計(jì)取值為3）

5.3 PSK傳輸系統(tǒng)

圖2

（1）8PSK調(diào)制器

I.首先將RS編碼器的輸出，映射到數(shù)域。然后把每個(gè)八進(jìn)制符號(hào)都映射成三個(gè)二進(jìn)制符號(hào)，映射規(guī)則如表2所示：

八進(jìn)制符號(hào)	二進(jìn)制符號(hào)
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

表2

II.再將每三個(gè)二進(jìn)制符號(hào)按圖三進(jìn)行映射。

（2）高斯隨機(jī)數(shù)發(fā)生器

同時(shí)產(chǎn)生高斯隨機(jī)數(shù)的同相分量和正交分量。

（3）為了驗(yàn)證RS碼在突發(fā)差錯(cuò)情況下仍然保持良好性能，故在PSK傳輸系統(tǒng)中引入突發(fā)差錯(cuò)，與未加突發(fā)差錯(cuò)的情況形成對(duì)比。

（4）判決器

計(jì)算接受信號(hào)在發(fā)送向量的投影，判斷哪個(gè)投影最大，就判哪個(gè)向量輸出。

圖3

5.4 將信息幀合并一串信息

由于從RS譯碼器輸出的消息是分組的，應(yīng)將這些消息進(jìn)行合并，以便與信源產(chǎn)生的消息進(jìn)行比較，計(jì)算誤碼率。

5.5 誤碼率計(jì)算

只要將上述輸出與信源比較，計(jì)算有多少不同的符號(hào)，然后再除于信源產(chǎn)生的符號(hào)數(shù)，即得誤碼率。

6.結(jié)果分析

根據(jù)以上仿真過(guò)程，采用信源產(chǎn)生N=

（為節(jié)約程序運(yùn)行時(shí)間，故N取值較小）個(gè)符號(hào)，固定信號(hào)功率S=1，得出以下圖表。

經(jīng)RS編碼后，信道采用pskmoto.m文件，信息流通過(guò)未加隨機(jī)差錯(cuò)的曲線如下圖所示：

圖4

經(jīng)RS編碼后，信道采用pskmoto2.m文件，信息流通過(guò)加上隨機(jī)差錯(cuò)的曲線如下圖所示：

圖5

對(duì)比兩圖可見(jiàn)，未加突發(fā)差錯(cuò)和加上突發(fā)差錯(cuò)的信噪比與誤碼率曲線圖相差不多，故得出結(jié)論，RS編碼對(duì)突發(fā)差錯(cuò)具有良好的抵抗能力。

7.總結(jié)

通過(guò)本次課程設(shè)計(jì)的學(xué)習(xí)讓我了解了RS編碼的歷史、原理和編碼的步驟還有它的實(shí)際應(yīng)用和不足之處、也使我對(duì)RS編碼有了重新的認(rèn)識(shí)。通過(guò)本課程的學(xué)習(xí)，我也認(rèn)識(shí)了自己還有很多不足，需要進(jìn)一步學(xué)習(xí)的地方，在接下來(lái)的學(xué)習(xí)中我會(huì)花更多時(shí)間，我要不斷的努力，多聯(lián)系，多思考，來(lái)認(rèn)真加深知識(shí)理解與運(yùn)用，我相信我能有所進(jìn)步的。

參考文獻(xiàn)

[1] 蘇艷琴等．基于RS碼和LDPC碼的糾錯(cuò)性能分析．海軍航空工程學(xué)院電子信息工程系．

[2] 陳曦．基于RS編碼的光通信系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)：[碩士學(xué)位論文]．成都：電子科技大學(xué)，2009

[3] Xu Youzhi．Implementation of Berlekamp-Massey algorithm without inversion．1EE E

Proceedings-I，1991，138(2)：138-140

[4] Hsie-Chia Chang，C．Bernard Shung．New Serial Architecture for the Berlekamp-Massey

Algorithm．IEEE Transactions on communications，1999，47(4)：48 1-483

[5] DiHp V Sarwate，Narcsh R Shanbhag．High-Speed Architectures for Reed-Solomon Decoders．

IEEE Transactions Very Large Scaleintegration(VLSD Systems，2001，9(5)：641-655

[6]陳飛，周德新．高速光網(wǎng)絡(luò)系統(tǒng)中FEC編碼器的設(shè)計(jì)與實(shí)現(xiàn)．光通信技術(shù)，2004，4(5)：35．37

[7] 曹立朋．?dāng)?shù)字視頻廣播傳輸系統(tǒng)中的的信道編碼技術(shù)：[碩士學(xué)位論文]．西安：西安電子科技大學(xué)，2006

[8] 曹雪虹，張宗橙．信息論與編碼．清華大學(xué)出版社．2004．

[9] 堯勇仕．DVB系統(tǒng)的RS編解碼的設(shè)計(jì)及ASIC實(shí)現(xiàn)：[碩士學(xué)位論文]．江蘇：江南大學(xué)，2008

[10] Marconetti, R. Guenard, D. Savage, P. Crowe, I. Epelde, L. Bradley, F. Cali.A fully programmable Reed Solomon 8-bit codec based on a re-shapedBerlekamp Massey algorithm. Proceedings of the IEEE InternationalSymposium on Circuits and Systems (ISCAS ’02), 2002, 5: 553-556.

[11] 朱起悅．RS碼編碼和譯碼算法．中國(guó)期刊網(wǎng)．1999．4．