1、糾錯編碼的MATLAB仿真課程設計1/32編號:料件雷孑科津次冷GUILINUNIVERSITYOFELECTRONICTECHNOLOGY課程設計說明書題目：RS目55,223）糾錯編碼的MATLAB仿真院（系）:專業:學生姓名:學號：指導教師:2013年12月10日糾錯編碼的MATLAB仿真課程設計目錄1引言錯誤!未指定書簽。1.1信道編碼理論與技術的發展歷程及應用錯誤!未指定書簽。L2糾錯編碼簡介錯誤!未指定書簽。2Reed-Solomon編碼概述錯誤!未指定書簽。3Reed-Solomon編碼抽象代數基礎錯誤!未指定書簽。31群錯誤!未指定書簽。3.2環和域錯誤!未指定書簽。33有限域

2、錯誤!未指定書簽。3.4歐兒里得算法錯誤!未指定書簽。4BCH碼、RS碼及其編碼錯誤!未指定書簽。4.1BCH碼、RS碼簡介錯誤!未指定書簽。錯誤!未指定書簽。4.2RS碼的構造方法5RS碼的譯碼錯誤!未指定書簽。5.1關鍵方程的引入錯誤!未指定書簽。5.2多項式的歐兒里得算法錯誤！未指定書簽。5.3BCH/RS碼的解碼步驟錯誤!未指定書簽。6MATLAB主要程序及其仿真結果錯誤!未指定書簽。7總結錯誤!未指定書簽。致謝錯誤!未指定書簽。參考文獻錯誤!未指定書簽。附錄錯誤!未指定書簽。#/32糾錯編碼的MATLAB仿真課程設計摘要在糾錯碼領域中Reed-Solomon碼是一類具有嚴格代數結構的

3、線性分組碼。由于它突出的糾錯能力(特別是糾突發錯誤的能力)，常被應用于數據存儲以及現代數字通信系統中。在衛星通訊中，差錯控制編碼技術對降低誤碼率、提高通信的可靠性具有非常重要的作用。RS(Reed-Solomon)碼是差錯控制領域中一種性能優異的線性分組循環碼，由于其具有很強的隨機錯誤和突發錯誤的糾錯能力，所以被CCSDS、NASA.ESA等空間組織接受，廣泛用于深空探測中。目前我國還沒有高碼速率的RS硬件譯碼器，雖然“雙星計劃”已經采用RS糾錯編碼技術，在衛星上使用RS(255,223)硬件編碼器進行編碼，但是由于硬件譯碼器的復雜性，地面接收系統采用的是軟件譯碼，無法保證通信的實時性。為此，

4、本文在詳細介紹RS(255,223)編碼譯碼的基礎上，利用MATLAB軟件對該理論進行仿真。關鍵詞：Reed-Solomon編碼;抽象代數：RS碼編碼;RS碼譯碼算法；RS(255,223)仿真;MATLAB3/32糾錯編碼的MATLAB仿真課程設計1引言1.1 信道編碼理論與技術的發展歷程及應用Shannon的信道編碼定理給出了有噪信道通信的最大速率，證明了好碼的存在性，但對該定理證明是非構造性的，它沒有告訴我們怎么構造好碼。如何通過不可靠信道進行可靠的通信，是編碼理論所要研究的問題。半個多世紀以來，眾多的學者為構造逼近容量限的糾錯碼做了大量的工作，但這一問題直到45年后才基本得到解決。但是

5、，“過程比目標更重要”，在應對這一挑戰的過程中，編碼理論家和工程師們應用組合數學、線性代數、概率論、有限域理論等數學工具，建立了糾錯碼的性能參數限,發現了許多構造糾錯碼的方法，并設計了有效的編譯碼算法，為信息技術的蓬勃發展建立了不朽的功勛！在Shannon的論文發表之前，RichardHamming就已經為早期的計算機設計了一種糾單個錯誤的碼，邁出了信道編碼理論與技術研究的第一步。之后，信道編碼理論與與技術的大致經歷了以下幾個發展階段：1. 50年代至60年代初這是編碼理論從無到有并得到迅速發展的年代，現代編碼理論的許多思想都起源于這一時期。1）發現了幾種線性分組碼，如Golay碼、Reed-

6、Muller碼（RM碼）、Reed-Solomon碼（RS碼）、Bose-Chaudhuri-Hocquengham碼（BCH碼）、低密度校驗碼（LDFC碼）等,以及卷積碼；2）為這些碼設計了有效的譯碼算法，如用于RS碼和BCH碼譯碼的PGZ算法、用于卷積碼譯碼的Fan。譯碼算法；3）證明了糾錯碼的幾個最小碼距限，如Hamming限（H限）、Singleton限、Plotkin限（P限）、GiIbert-Varshamove限（GV限），其證明可以在編碼理論的基礎教材中找到；4） 1957年，Elias提出了一種概念譯碼器表單譯碼器（ListDecoder）,以突破傳統的限定距離譯碼（BDD）

7、的半最小碼距的糾錯半徑；5） 1961年，W.W.Peterson編寫了第一本關于糾錯碼理論的專著，系統地闡述了糾錯碼的基本理論。2. 60年代至70年代初這是糾錯碼發展最為活躍的時期之一。在此期間，以代數方法特別是以有限域理論為基礎的線性分組碼理論已趨成熟。1）提出了許多有效的編、譯碼方法。1965年，E.R.Berlekamp提出了一種實用分組碼的代數譯碼算法，1969年,J.L.Massey從序列綜合的角度重新推導了這一算法，后人稱之為Berlekamp-Massey算法（BM算法）。BM算法的提出，是分組碼走向實用的一個重要里程碑。1966年，G.D.Forney第一次采用簡單的分量碼

8、構造級聯碼，以提高碼的性能。第一個成功的級聯碼是采用卷積碼作內碼、RS碼作外碼的串行級聯碼，其典型應用是在衛星通信、深空探測等領域，如Voyager、Galileo、Cassini等任務，這種編碼方式還被應用于美國的數字電視（ATSC）、歐洲的數字視頻廣播（DVB）和數字音頻廣播（DAB）等系統中；另一種典型的級聯碼是CBerrou于1993年發現的并行級聯卷積碼（PCCC）,即我們通常所稱的Turbo碼，這是一種逼近Shannon限的碼。1967年，A.J.Viterbi提出了卷積碼的最大似然譯碼算法，實現了數字通信中信道編碼技術的一次實質性突破。Viterbi算法還在其它領域得到了廣泛應用

9、。1974年，Bahl等提出了一種最大后驗概率（MAP）譯碼算法（也稱為BCJR算法），其誤比特率（BER）性能優于Viterbi算法。但由于計算復雜度大大增加,MAP算法直到1993年Berrou發現Turbo碼之后才得到廣泛應用。由于硬判決譯碼通常較軟判決譯碼損失2、3dB,對分組碼的軟判決譯碼算法的研究也逐漸成為一個重要的課題。對于卷積碼，硬判決譯碼和軟判決譯碼通過相同的格圖進行譯碼，其復雜度大體相同。而對于分組碼，基于格圖的譯碼與代數譯碼相比，復雜度會大大增加，因此次優的譯碼算法成為首選。在這方面，著名的有廣義最小距離（GMD）譯碼算法、Chase算法等。2）研究了與碼的性能有關的各種

10、問題，如碼的重量分布、譯碼錯誤概率和不可檢錯誤概率的計算、信道的模型化等，所有這些問題的研究為信道編碼技術的實用化打下了堅實的基礎。3. 70年代初至80年代這是信道編碼發展史中最具重要意義的時期，信道編碼在理論和實踐方面都取得了豐碩的成果。1）在理論上，以Goppa為首的一批學者在70年代初較系統地構造了一類逼近Shannon限的有理多項式碼Goppa碼,這在糾錯碼的歷史上具有劃時代的意義。80年代初，Goppa等將代數幾何的理論與方法系統地應用于編碼理論中，由Goppa碼引出了代數幾何碼，使得Goppa碼日益引起了人們的極大興趣。1987年，G.Ungerboeck提出了著名的格圖編碼調制

11、（TCM）技術，展示了如何將編碼和調制結合起來，改善系統的整體性能，這是編碼理論的乂一重要里程碑。之后，眾多研究者開始對TCM進行了深入研究，并將這一概念推廣到分組編碼調制（BCM）o2）這期間微電子技術的迅速發展，為編碼技術的實用化打下了堅實的物質基礎；各種實際應用也帶動了信道編碼技術的發展，編碼技術的實用化得到了極大關注，并取得了巨大的進展。例如，用于RS碼譯碼的BM算法進一步發展成熟，出現了無求逆的BM（iBM）算法、Euclid算法、Welch-Berlekamp算法（WB算法）等，其超大規模集成電路（VLSI）實現也得到了充分的發展。信道編碼技術最成功的應用在于衛星通信和深空探測領域

12、，這使得宇宙飛船從遙遠的太空傳回了許多極其寶貴的天文學資料。特別值得一提的是，在1989年的Galileo任務中，由于主天線的故障，數據傳輸的速率比原設計指標大大下降，噴氣式推進實驗室（JPL）的科學家們從地面發送指令，重新配置板上計算機，在數據傳輸之前進行了更多的編碼處理，使得由于硬件故障引起的數據傳輸速率下降得以部分恢復，從而挽救了整個探測計劃。若不應用信道編碼技術，這些成就的取得是不可企及的。此外，信道編碼技術還用于數據存儲系統，提高數據存儲密度；用于數據傳輸系統,提高數據傳輸速率；用于各種數字通信系統，提高通信質量；用于數字音頻/視頻傳輸系統以及視聽娛樂設備，為我們的生活帶來美妙的音樂

13、和完美的視覺享受；而且糾錯碼技術還應用于超大規模集成電路設計中，以提高集成電路芯片的成品率，降低芯片的生產成本。4. 90年代以后這一時期，編碼理論的重大發現當首推1993年Berrou等發現的Turbo碼。Turbo碼是一種利用偽隨機交織器構造的具有隨機碼行為的長碼，它采用并行級聯卷積碼的方式進行編碼，用最大后驗概率（MAP）譯碼器進行迭代譯碼，分量譯碼器之間通過傳遞所謂的外信息來減少信息損失，其性能非常接近Shannon限，這一驚人的性能打破了長期以來的猜想：利用二元卷積碼和序列譯碼是達到截止速率R（即所謂的“實際容量”）的一種可實現的方法。在迭代譯碼器中，所采用的分量碼MAP譯碼器可以用

14、軟入輸出Viterbi算法（SOVA）代替，這會使Turbo碼譯碼性能略有下降，但大大降低了計算復雜度和存儲量要求。更為實用的分量碼譯碼器是Koch等提出的Max-Log-MAP譯碼算法和Robertson等提出的Log-MAP譯碼算法。后來，HagenauerPyndiah乂分別將Turbo碼迭代譯碼的思想用于級聯二元分組碼和乘積碼。現在，Turbo碼的迭代算法已經成為“Turbo原理”，廣泛應用于各種級聯系統，如均衡、編碼調制、信源壓縮、信源信道聯合編碼以及信號檢測等。另一方面，在探究Turbo碼迭代算法的過程中，Mackay和Neal于1996年重新發現了Gallager于60年代提出的

15、具有稀疏校驗矩陣的線性分組碼一一LDPC碼，基于Tanner圖進行迭代譯碼，其性能與Turbo碼差不多。最近，采用BCH碼作外碼、LDPC碼作內碼的級聯碼已經被DVB-S2采納。3/32糾錯編碼的MATLAB仿真課程設計1998年，Tarokh、Seshadri和Calderbank提出的格圖空時碼，在時間和空間上都引入了編碼，集前向糾錯(FEC)、發送分集和接收分集于一體，能獲得較大的編碼增益和分集增益，實現數據的高速傳輸。幾個月后，Alamouti發明了低復雜度的分組空時碼。空時碼的基本思想是采用多個發射天線和多個接收天線來提高系統容量，關于空時碼已有許多研究文獻。由于RS碼在眾多數字通信

16、系統、數據存儲系統中的成功應用，以及其軟判決譯碼性能的巨大潛力，RS碼的軟判決譯碼問題也得到了很大的關注。其中，Sudan于1997年提出了多項式復雜度的表單譯碼(ListDecoding)算法，將RS譯碼問題轉化成有限域上的曲線擬合問題，給出并證明了幾個重要的定理，奠定了RS碼表單譯碼的基礎。但Sudan算法只適用于碼率不大于1/3的RS碼，而1999年提出的Guruswami-Sudan算法則可適用于任意碼率的RS碼和代數幾何碼。另一方面，Koetter和Vardy基于Guruswami-Sudan算法，將接收符號的軟信息轉化為一系列的代數條件，用代數方法實現了RS碼的軟判決譯碼。1.1糾

17、錯編碼簡介我們知道，在計算機和數據通信中，經常需要將二進制數字信號進行傳遞，這種傳遞的距離近則數米!數毫米，遠則超過數千公里。在傳遞信息過程中，由于存在著各種干擾,可能會使二進制信號產生失真現象,即在傳遞過程中二進制信號0可能會變成1,1可能會變成Oo試想一個二進制信號傳遞的簡單模型,它有一個發送端和一個接收端,二進制信號申從發送端發出經傳輸介質而至接收端。由于存在著干擾，因而接收端接收到的二進制信號串可能與原來的二進制信號串不相等,從而產生了二進制信號的錯誤傳遞。由于在計算機和數據通信系統中的信號傳遞是非常的頻繁與廣泛，因此,如何防止傳輸錯誤就變得相當重要了，當然，要解決這個問題可以有不同的

18、途徑。人們所想到的第一個途徑是提高設備的抗干擾能力和信號的抗干擾能力。但是,大家都知道,這種從物理角度去提高抗干擾能力并不能完全消除錯誤的出現。第二個途徑就是我們所要談到的采用糾錯碼(Errorcorrectingcode)的方法以提高抗干擾能力。這種糾錯碼的方法是從編碼上下功夫，使得二進制數碼在傳遞過程中一旦出錯，在接收端的糾錯碼裝置就能立刻發現錯誤,并將其糾正。由于這種方法簡單易行,因此目前在計算機和數據通信系統中被廣泛采用采用這種方法后，二進制信號傳遞模型就可以變為糾錯碼模型了。由糾錯碼模型可以想到，當二進制信號串從發送端發送時:需按規定轉換成具有抗干擾能力的糾錯碼，然后才發送出去。在接

19、收端，當接收到二進制信號串后立即對接收到的糾錯碼進行檢查,查對在途中是否失真,如失真則負責糾正。該模型的一個典型實現，就是在遠程數據傳輸系統中具有糾錯能力的數據傳輸裝置，該裝置的糾錯過程是二進制信號發生器發出信號(二進制信號發生器可以是計算機，或者是山人控制的某些裝置如終端)，經差錯控制器形成糾錯碼，然后經調制器使二進制信號變成為適宜于信道傳播的電信號,這種信號通過信道傳輸至接收端，首先通過解調器將其還原為原來的二進制信號，再經差錯控制器檢驗經信道傳輸后是否產生失真，并采取措施進行糾正。經糾正后的二進制信號送入二進制信號接收器，從而完成整個傳輸過程二進制信號接收器可以是計算機,或其他接收裝置如

20、終端等。但是，為什么糾錯碼具有發現錯誤！糾正錯誤的能力呢？糾錯碼乂是按什么樣的原理去編的呢？為了說明這些問題，我們首先介紹一些基本概念：由0和1組成的串稱為字(Word),一些字的集合稱為碼(Code)。碼中的字稱為碼字(CodeWord)。不在碼中的字稱為廢碼(InvalidCode)。碼中的每個一.進制信號0或1稱為碼元(CodeLetter)。我們下面舉出幾個關于糾錯碼的例子。設有長度為2的字,它們一共可有2x2=4個，創門所組成的字集S,=00,01,10,11o當選取編碼為52時，這種編碼不具有抗干擾能力。因為當52中的一個字如10,在傳遞過程中其第一個碼元1變為0,因而整個字成為0

21、0時，由于00也是52中的字，故我們不能發現傳遞中是否出錯。但是，當我們選取52的一個子集如C2二00,川作為編碼時就會發生另一種完全不同的情況。因為此時01和10均為廢碼,而當H在傳遞過程中第一個碼元由1變為0,即整個字成為01時，由于01是廢碼，因而我們發現傳遞過程中出現了錯誤。對00也有同樣的情況。但是，這種編碼有一個缺點，即它只能發現錯誤而不能糾正錯誤，因此我們還需要選擇另一種能糾錯的編碼現在我們考慮長度為3的字，它們一共可有2!3=8個，它們所組成的字集凡000,001,010,011,100,101,110,111中我們選取編碼q二001,110o利用此編碼我們不僅能發現錯誤而且能

22、糾正錯誤。因為碼字001出現錯誤后將變為：ooo,on,101,而碼字no出現錯誤后將變為:m,wo,010。故如碼字ooi在傳遞過程中任何一個碼元出現了錯誤，整個碼字只會變為101!011或000,但是都可知其原碼為001o對于碼字110也有類似的情況故對編碼Q,我們不僅能發現錯誤而且能糾正錯誤”當然,上述編碼還有一個缺點,就是它只能發現并糾正單個錯誤。當錯誤超過兩個碼元時,它就既不能發現錯誤,更無法糾正了。2Reed-SoIomon編碼概述Reed-Solomon碼(RS碼)是Reed和Solomon于1960年發現的一類多元最大距離可分(MDS)碼,其最小距離達到了Singletonmi

23、nd=n-k+l,從這個意義上講,RS碼是最佳的。之后兒十年里，RS碼的硬判決譯碼得到了深入的研究，其理論和技術都已經非常成熟。因而，RS碼在現代數字通信、數據存儲系統中得到了廣泛的應用，見下表應用領域編碼方案硬盤驅動器RS(32,28,5)碼CD交叉交織RS碼(CIRC)DVDRS(208,192,17)碼、RS(182,172,11)碼乘積碼5/32糾錯編碼的MATLAB仿真課程設計DAB、DVB內碼為卷積碼、外碼為RS(204,188,17)碼的級聯碼ATSC內碼為卷積碼、外碼為RS(207,187,21)碼的級聯碼深空通信內碼為卷積碼、外碼為RS(255,223,33)碼的級聯碼光纖通

24、信RS(255,239,17)碼有限域算術是RS碼的基礎，并行通用有限域乘法器的時延決定了RS碼譯碼器的工作頻率。如何用現場可編程門陣列(FPGA)實現通用有限域乘法器，降低其運算時延，是軟件無線電中RS碼譯碼子系統設計過程中要考慮的一個關鍵的問題。在工程實踐中通常采用的“直接二級邏輯設計”僅僅依靠綜合工具對所設計的電路進行優化，不能有效地利用FPGA所提供的資源，降低有限域乘法器的時延。就作者所知，目前還沒有一種系統的方法，可以用來設計高速并行有限域乘法器。RS碼的硬判決譯碼器不能充分地利用接收信息，造成了一定的性能損失。眾所周知，從最小化不正確譯碼概率的意義上講，最大似然譯碼(MLD)是最

25、好的方法。在AWGN信道條件下，RS碼的最大似然譯碼與硬判決距離譯碼相比，會有2.5、3.2dB的軟判決譯碼增益；在衰落信道條件下，其軟判決譯碼增益會更大。2005年，Guruswami和Vardy90在IEEE信息論會刊上撰文指出，RS碼的最大似然譯碼是NP-Hard問題。因此，低復雜度的次優譯碼算法成為人們研究的熱點。現有的RS碼軟判決譯碼算法主要有以下四類： 基于代數譯碼器的軟判決譯碼：主要有糾錯糾刪譯碼、廣義最小距離(GMD)譯碼算法、Chase算法、Lacan算法、有序統計量譯碼(OSD)算法等； 基于格圖的譯碼：主要有Vardy和Beery提出的比特級軟判決譯碼算法、Ponnamp

26、alam和Vucetic提出的簡化的比特級軟判決譯碼算法等； 基于Tanner圖的譯碼：基于自適應校驗矩陣的軟判決譯碼算法、基于臨界抽取濾波器組表示的軟判決譯碼算法等； 表單譯碼：主要有Koetter-Vardy算法等。這些譯碼算法各有千秋，就實用性而言，GMD算法、Chase-II算法和Koetter-Vardy算法略勝一籌。3Reed-Solomon編碼抽象代數基礎3.1 群定義設G是一個非空集合，稱映射0:GxGfG為G上的一個二元運算，即對于G中仍以兩個元a和6,唯一確定c=(a,b).記為c=a-b,為了方便起見，可寫成c=ab.定義設G是一個非空集合，是G上的一個二元運算，如果G滿

27、足下列條件：(結合律)對于任意4,ceG,有(a-b),c=aQ-c)(單位元)G中存在單位元e,對于任意aeG,滿足=(逆元)對于任意。，存在的逆元，尸，滿足a-1=a-a=e則稱G為群，記為(G,).如果群(G,)滿足交換律，即對于任意“/eG,滿足為=則稱群為交換群或阿貝爾群.3.2環和域定義設斤是一個非空集合，斤上有兩個二元運算+和，分別成為加法和乘法，如果斤滿足下列條件a)(2+)為加法阿貝爾群(結合律)對于任意有(ab)c=a-(bc)(分配律)對于任意有:稱萬為環，記為(凡十),如果他對乘法滿足交換律，即對任何(b+c)-a=ba+c-aa,beRah=ba稱環(R,+,)為交換

28、環定義設(凡+,)為交換環，之表示A中所有非零元的集合，如果*在乘法運算下構成交換群，則稱(凡+,)為域。3.3有限域定義設尸為一個域，如果尸只含有有限個元素，稱尸為有限域，含有。個元素的有限域記為尸7,有限域也成為伽羅華域(Galoisfield),用Yq)或表示q階有限域。最簡單的有限域是二元域GF(2)=0,1o定義對于小3上的每個非零元素?，存在最小整數上使加=1成立，則稱為A階元素。定義對于成上的每個非零元素夕，如果其階數是Q-1,則稱僅為本原元素。定義Gb(2)上的一個卬次多項式雙x),如果他的所有根都是6/(2)中的本原元素，則稱；r(x)是加次本原多項式。例如，對于m=8時G尸

29、(2小)=6/(2,上的m次本原多項式為%(x)=1+/+/+/+/對于m=7時GFQ、=6/(2，)上的m次本原多項式為產(x)=1+1+x7定義設夕為G尸(2中的元素，多項式口)是GE(2)上使m(0)=0的最低次多項式，則稱，)為最小多項式。具有相同最小多項式的元素，構成同一共桅系。1.1歐幾里得算法歐兒里得算法給定兩個正整數a,b,可以用歐兒里得除法得到其最大公約數(a,b),并求得A,B,滿足(a,b);Aa+Bb。用歐兒里得除法求勿的步驟如下：第一步：不失一般性,假設a6,且令二2=。，二1=，4=-2第二步：用除以乙得到其商數怎+2和余數加2,亦即=%2+1+2第三步：如果4+2

30、=。，停止運算，并記=4+2；否則，k=+1轉第二步。歐兒里得算法乂被稱為輾轉相除法，這里是單調下降序列。用歐兒里得算法可以求得兒B,沿用上述除法得到/的和力其方法如下：第一步：令2=0立1=1*=1第二步：計算瓦_1=4仄+bk+第三步：如果k=0,停止運算，此時A=%,8=%，否則攵=左-1轉第二步事實上，9,(=44+心m_1，04,8)只是其中的一個特例。2BCH碼、RS碼及其編碼2.1BCH碼、RS碼簡介如前所述，BCH碼是糾錯能力可能的循環碼，illBose、Chandhari和Hocquenghem在19501960年間分別獨立地提出。最初的BCH碼定義在二元域上，成為二元BCH

31、碼，后來推廣到多源于上。對于設計糾錯能力為t的循環碼，器生成多項式含有2t個連續幕次的根，這樣的循環碼稱為BCH碼。如果BCH碼的根是本原元，成為本原BCH碼。如果BCH碼的根是非本原元，稱為非本原BCH碼。如果定義在G/(2)上的本原元。以及a?、。”共2t個連續幕次都是定義在GE(2)上的生成多項式g(x)的根，那么該BCH碼成為設計糾錯能力為t的二元本原BCH碼。對于任意的證書卬和糾錯數t,都可以構造出最小距離為，的二元本原BCH碼，%,刃，n=2n-,kn-mt=2n,-1-mt,d2t+o另外，實際的糾錯能力t,可能會大于設計糾錯能力的t.同理，如果定義在G/(21上的非本原元月以及

32、獷、夕、夕”共2t個連續幕次都是定義在GE(2)上的生成多項式g(x)的根，那么該BCH碼成為設計糾錯能力為匕的二元非本原BCH碼。進一步假設非本原元月和本原元。滿足關系夕=優，其中lvcv2”-l,如果衣=2桁-1成立，那么/T=l,也就是說夕是n階非本原元。如果c=2-l成立，那么可以構造出最小距離為，的二元非本原BCH碼，6,2司，滿足nc=2n-,kn-mt=2-1-mt,J2r+1o另外，實際的糾錯能力力可能會大于設計糾錯能力的士.BCH碼的編碼是在二元域完成的，對比特進行編碼，與普通的二進制循環碼并無不同。而RS的編碼是在多元域GF(p，)上完成的(p是質數)，對符號進行編碼，因為

33、RS碼又被挈為多元域上的本原BCH碼。如果定義在G/p)上的生成多項式g(x)=n(x-a),其中a是定義在W(p)上的本原元，那么該BCH碼被稱為糾錯能力為t的詼碼。1.1RS碼的構造方法第一步，由關系式=2，”-1算出小查本原多項式表得到一個m次的本原多項式P(x),從而產生一個G/(2”)的擴域，使域元素(符號)優與m重向量建立起一一對應的關系本原多項式表mM本原多項式21+X+A23+x+x341+x+x45l+x2+x56+x+x67l+x3+x78+x2+x3+x4+x第三步：根據設計糾錯能力t,直接計算定義在Gf)上的生成專項式g(x)=n(x-a,)o利用a”=ld+=0和P(

34、a)等運算規則，可以將*-優)展開并化簡為軟幻=/改。第三步：代知生成多項式g(x),根據關系式C(x)=M(x)g(x),對信息位M多項式9/32糾錯編碼的MATLAB仿真課程設計編碼得到碼字多項式C(x),這就完成了RS碼的編碼過程。這里的C(x)、M(x)和gj)23 / 32都是GF(2川)上的多項式。而對于長度為mk的二進制的輸入序列，以m個比特位一組劃分可以得到k個m重向量，再將每個m重向量映射為GF(2“l上的元素，從而得到長度為k的多元序列M(x)o得到長度為n的多元序列C*)后，對于每一個GF(2。上的元素，再映射為m重向量，從而得到長度為nm的二進制編碼序列。例如，對于信息

35、輸入比特序列100,101,010，首先根據表格。的各次罌將序列映射為GF(23)上的序列a?,/，,。,則其信息位多項式加(工)=&-2+261+2。那么可以求得G&j上的碼字多項式。C(x)=M(x)g(x)=(a2x2+abx+a)(x4+x2+ax+a)=a2x6+ad+a/+-從而得到G42，)上的編碼序列aaao,/,。,/。再根據表格。的各次暴將其映射為二進制編碼序列即可得到RS碼100,010,010,000,100,000,110)o表格。的各次事即約多項式3重向量00001001a010a2100a3=a+Oil42.a=a+a110a、=a2+a+1111a=a+1101

36、RS碼是糾正短突發差錯的首選糾錯碼，廣泛應用于無線通信的存儲系統中。例如，美國宇航局(NASA)在探險者號(Voyager)上用了256進制的255,223,33RS碼，其生成擴域的本原多項式是尸(幻=1+/+/+/+/,相=8,生成多項式是g(x)=(x-a)(x-a2)(x-a32)oa是本原多項式P(x)的根,因為g(x)含有32個連續幕次的根，因而改碼的糾錯能力為符號1=32/2=16個符號(256進制)或者等效長度是(-1)帆+1E21的二進制特發差錯。4RS碼的譯碼由于BCH碼和R-S碼都是循環碼，所以可以采用一般的梅杰特解碼器，但是BCH碼和R-S碼的設計糾錯能力都比較高，從而使

37、得梅杰特解碼器的實現復雜度BCH碼和RS碼的解碼原理是一樣的，其高效解碼算法的基礎在于一個關鍵方程的引入和基于多項式的歐兒里德算法。在BCH/RS碼的解碼算法的發展歷史上，彼得森(Peterson)于1960年提出了第一個BCH的解碼算法。之后,錢(Chien)、福尼(Formey)梅西(Massey)和巴勒坎普(Berlekamp)相繼提出了更高效的BCH解碼算法。到了1975年，Sugiyama、KasaharaHirasawa和Namekawa發現也可以采用歐兒里德(Euclid)算法對BCH/RS碼解碼，并發現巴勒坎普(Berlekamp)解碼算法與歐兒里德(Euclid)算法相比僅差

38、一個很小的常數因子。而歐凡里德(Euclid)算法更容易理解些，所以得到了更廣泛的應用。具體解碼又可以分為時域解碼和頻域解碼。1.1關鍵方程的引入一】令尸是一個含有a階單元本原元。的域，那么根據定義有l-x=n(l-ax)，再令/是尸上的一個A維向量，V稱為時域向量。又令V=,；Q,辱V的離散傅里葉變換(DFT),成為頻域向量；DFT(離散傅里葉變換)：)=匕，,小0,-1那么，可以證明，從頻域到時域的IDFT(逆離散傅里葉變換)也成立；1AIDFT(逆離散傅里葉變換)：,二上2以/，/。，“設尸是GF(pD，是質數，=p5二f,那么特征是外IDFT中的是以特征為模In的同余類。易知=(-l)

39、mod，所以一=Imodp,根據歐幾里得算法有11n-=(/?-l)modpo對于GF(2,”)，一=1在定義/和V的生成多項式：V(x)=%+匕x+匕和(、)歷邛4M7(.才尸婷。那么，可以將上述的離散傅里葉變換寫為：人對于V，定義他的支持集/,/=，：匕。0,，0,-1,亦即/是V中非緣品羞肺幫窿r桂定義/的位置多項式(x)R(x)=q(i-優幻。對于運/,再定義階穿孔位置多項式b，a),b?(x)=口(1-0公)/(1行：最后，定義/的數值多項式程.(x),q(x)=%b，(x)。那么，可照正明GCD(5(x)，5(x)=1。定理為鍵方程/對于固定的向量匕多項式4，q(x)和V(x)滿足

40、一下關鍵方程%(x)V(x)=4*)(l-x”)有了上述的數學基礎，就可以引入BCH/RS碼的關鍵方程了。設編碼向量為C=c,信道錯誤圖案為向量石=52,j_J,那么接收向量R=C+E,解碼的第一步是計算伴隨式向量S=%,S,S的定義如下/r-1一I一13=小。那么，=ZW=ZW令時域向量丫。)=4，60,易知，祥隨式向量S與頻域向量丫滿足關系;=%/。,力-1,亦即，伴隨式向量S是V的錢2匕個分量，這是可以A一直接觀測到的，而V的后(n-2t)個分量不能直接觀測到。記伴隨式多項式S(x)=M.解碼算法的目的是已知伴隨式到量S求錯誤圖案向量凡從而得到解碼向量C=R-E,由于只是知道頻域向量V(

41、x)的前2t個分量，需要用mod.一對關鍵方程降次A5.(x)V(x)modx2!=yy(x)(l-x)modx。所以得到BCH/RS的關鍵方程(x)SCt)=.(A)mod.r,由于V的支持集是發生誤碼的標號集合，所以b(x)乂被成為錯誤位置多項式，b(x)=b、(x),而以x)乂被成為錯誤數值多項式，其中以幻=%(%),deg(o-(x)r,deg()deg(6(x)且令匚i=a(x),“=匕),女=一1第二步：用修除以，得到其商數%2。)和余數仁21)，亦即4(X)=%2(X)+l(X)+4+2(X)第三步:如果+20)=0，停止運算，d(x)=gcd(a,。)=+i(x),并記=k+1

42、；否則k=k+1,轉第二步。歐兒里得處理乂被成為輾轉相除法，這里deg)是單調下降序列。用歐兒里得算法可以求得(x),i，(x)。沿用上述除法得到外和“，其方法如下：第一步：M_iW=1,M()(A)=O；V(X)=O,VO(X)=1；=1第二步：計算一(x)=%式幻-%(X)；吊(X)=%(X)-%(x)k(x)；第三步:如果k=,停止運算,此時u(x)=ii(x),v(x)=v(x)；否則k=k+1,轉第二步。這里，deg(式x)是單調遞增函數，而deg0(x)也是單調遞增函數。容易得到以下兩條性質：/(幻心)+”3)=(x”k+從而推出以下性質:(2)deg(唳+deg(_()=deg(

43、a(x),V攵e0,n+l(l)/(x)(x)=(工)moda(x),e-1,71+1進一步有如下.)加8(匕)+deg)deg(/?(x)滿足：v(x)b(x)=r(x)moda(x)deg-mdeg(r(x)nm+n=deg(a(x)-1進一步假設vA(X)和“(%)伏eji+1)是對(a),/?(%)應用歐兒里得算法得到的多項式序列。那么存在且唯一存在標號力+使得V.(a)/?(A-)=o(x)moda(x)用一個歐兒里得抽象函數Vj(x),7)(x)=Euclid(x),/?(x),m9n表示上述結果。進加存在一個常數多項式X(x),使得：v(x)=A(x)v(x)這個定理表明完全可以

44、用歐幾里得算法解決BCH/RS碼的關鍵方程。r(x)=A(x)r.(x)1.1BCH/RS碼的解碼步驟有了關鍵方程和歐兒里得抽象函數，討論BCH/RS解碼的步驟就水到渠成了。假設已經求得了錯誤位置多項式b(x)和錯誤數值多項式次x),為工求差錯圖案多項式七(幻，有時域和頻域處理兩種方法。求出E(x)后，解碼碼字向量Z=R-E時域算法的本質就是對錯誤位置多項式b(x)進行驗根。由于b(x)=n(l-/)，那么b(a-i)=0；反之，如果7(。-)=0,那么含有因子(1一x)。所以，揖臬b(a-，)=0,說明第i個位置上的接收向量小存在誤碼，否則第i個位置上的接收向量是正確的。對于二元域BCH碼，

45、e,e0,l比較簡單，如果6。7)=0,那么巧=1,否則4=0。而對于多元域上的RS碼，4號多元域元素，還需零進一步求出。對于RS碼，如果b(2Tj=0,那么匕絲0,亦即e產一絲?，否則=0。首先用C語言由脩馬明BCH碼的品輸4馬算法，如下所示：/*二元域BCH碼的屬于解碼算法*/“/*碼長n,設計糾錯能力t,接收向量R,錯誤圖案向量E,解碼碼字向量2*/(for(j=lto2t)n1，；卜u，2s)=；if(SM-o)printf(接收碼字正確，無誤碼“)；else(用歐兒里得算法解關鍵方程vy(x),.(x)=Euclid1%2,S(x)JJ-1;if(v.(O)=O)printf(誤碼超出了糾錯能力t,不可解碼)；else(o-(A)=v/x)/vy(O);for(i=Oton-l)if(cr(a-,)=0)4=1elseq=0for(i=0ton-l)RCi=ri-ei,aapr