【正文】 nc??成立 ，那么 1n?? ， 也就是說 ? 是 n階非本原元。 如果 BCH碼 的根是 非 本原元 ，稱為 非本原 BCH碼 。 4 BCH 碼、 RS 碼 及其 編碼 BCH 碼、 RS 碼簡介 如前所述 ， BCH 碼是糾錯(cuò)能力可能的循環(huán)碼，由 Bose、 Chandhari 和 Hocquenghem在 1950~1960 年 間 分別 獨(dú)立地提出 。 歐幾里得 算法 歐幾里得算法給定 兩個(gè)正整數(shù) a,b， 可以 用 歐幾里得除法得到其最大公約數(shù) (a,b)，并求得 A， B，滿足 (a,b)=Aa+Bb。 定義 對(duì)于 GF(q)上的每個(gè)非零元素 ? ，如果其 階數(shù) 是 q1,則稱 ? 為本 原 元素 。 3 Reed – Solomon 編碼抽象代數(shù) 基礎(chǔ) 群 定義 設(shè) G是一個(gè) 非空 集合， 稱 映射 :G G G? ??為 G上的 一個(gè)二元運(yùn)算，即對(duì)于 G中 仍以兩個(gè)元 a和 b， 唯一確定 c ?? (a,b).記為 c ab?? ,為了 方便起見，可寫成 c=ab. 8 定義 設(shè) G是一個(gè) 非空 集合，是 G上的一個(gè)二元運(yùn)算， 如果 G滿足下列 條件： a) （結(jié)合律 ）對(duì)于 任意 ,abc G? ,有 ( ) ( )a b c a b c? ? ? ? ? b) （ 單位元） G中存在單位元 e ，對(duì)于任意 aG? ，滿足 e a a e a? ? ? ? c) （逆元 ）對(duì)于任意 a ， 存在的 逆元 1a? ，滿足 11a a a a e??? ? ? ? 則稱 G為群，記為 ( , )G? . 如果 群 ( , )G? 滿足 交換律，即對(duì)于 任意 ,ab G? ，滿足 a b b a? ? ? 則稱 群 為交換群 或阿貝爾群 . 環(huán) 和域 定義 設(shè) R 是一個(gè)非空集合， R 上 有 兩個(gè)二 元 運(yùn)算 ? 和 ? ，分別成為 加法 和 乘法 ，如果 R滿足 下列條件 a) ( , )R? 為 加法阿貝爾群 b) （結(jié)合律 ）對(duì)于 任意 ,abc R? ,有 ( ) ( )a b c a b c? ? ? ? ? c) （分配律 ）對(duì)于 任意 ,abc R? ,有 ()()a b c a b a cb c a b a c a? ? ? ? ? ?? ? ? ? ? ? 稱 R 為環(huán)，記為 ( , , )R?? ，如 果他對(duì)乘法滿足交換律， 即對(duì) 任何 ,ab R? a b b a? ? ? 稱 環(huán) ( , , )R?? 為交換環(huán) 定義 設(shè) ( , , )R?? 為交換環(huán)， *R 表示 R 中所有非零元的集合，如果 *R 在乘法運(yùn)算下構(gòu)成交換群 ， 則稱 ( , , )R?? 為域 。 2021 年， Guruswami 和 Vardy[90]在 IEEE 信息論會(huì)刊上撰文指出， RS 碼的最大似然譯 碼是 NPHard 問題。就作者所知，目前還沒有一種系統(tǒng)的方法，可以用來設(shè)計(jì)高速并行有限域乘法器。之后幾十年里， RS 碼的硬判決譯碼得到了深入的研究，其理論和技術(shù)都已經(jīng)非常成熟。故如碼字 001 在傳遞過程中任何一 個(gè)碼元出現(xiàn)了錯(cuò)誤 ,整個(gè)碼字只會(huì)變?yōu)?101!011 或 000,但是都可知其原碼為 001。對(duì) 00 也有同樣的情況。當(dāng)選取編碼為 52 時(shí) ,這種編碼不具有抗干擾能力。不在碼中的字稱為廢碼 (Invalid Code)。 該模型的一個(gè)典型實(shí)現(xiàn) ,就是在遠(yuǎn)程數(shù)據(jù)傳輸系統(tǒng)中具有糾錯(cuò)能力的數(shù)據(jù)傳輸裝置 ,該裝置的糾錯(cuò)過程是二進(jìn)制信號(hào)發(fā)生器發(fā)出信號(hào) (二進(jìn)制信號(hào)發(fā)生器可以是計(jì)算機(jī) ,或者是由人控制的某些裝置如終端 ),經(jīng)差錯(cuò)控制器形成糾錯(cuò)碼 ,然后經(jīng)調(diào)制器使二進(jìn)制信 6 號(hào)變成為適宜于信道傳播的電信號(hào) ,這種信號(hào)通過信道傳輸至接收端 ,首先通過解調(diào)器將其還原為原來的二進(jìn)制信號(hào) ,再經(jīng)差錯(cuò)控制器 檢驗(yàn)經(jīng)信道傳輸后是否產(chǎn)生失真 ,并采取措施進(jìn)行糾正。這種糾錯(cuò)碼的方法是從編碼上下功夫 ,使得二進(jìn)制數(shù)碼在傳遞過程中一旦出錯(cuò) ,在接收端的糾錯(cuò)碼裝置就能立刻發(fā)現(xiàn)錯(cuò)誤 ,并將其糾正。 由于在計(jì)算機(jī)和數(shù)據(jù)通信系統(tǒng)中的信號(hào)傳遞是非常的頻繁與廣泛 ,因此 ,如何防止傳輸錯(cuò)誤就變得相當(dāng)重要了 ,當(dāng)然 ,要解決這個(gè)問題可以有不同的途徑。 糾錯(cuò)編碼 簡介 我們知道 ,在計(jì)算機(jī)和數(shù)據(jù)通信中 ,經(jīng)常需要將二進(jìn)制數(shù)字信號(hào)進(jìn)行傳遞 ,這種傳遞的距離近則數(shù)米 !數(shù)毫米 ,遠(yuǎn)則超過數(shù) 千公里。 由于 RS 碼在眾多數(shù)字通信系統(tǒng)、數(shù)據(jù)存儲(chǔ)系統(tǒng)中的成功應(yīng)用，以及其軟判決譯碼性能的巨大潛力， RS 碼的軟判決譯碼問題也得到了很大的關(guān)注。最近，采用 BCH 碼作外碼、 LDPC 碼作內(nèi)碼的級(jí)聯(lián)碼已經(jīng)被 DVBS2采納。更為實(shí)用的分量碼譯碼器是 Koch 等提出的 MaxLogMAP 譯碼算法和 Robertson 等提出的 LogMAP 譯碼算法。 此外，信道編碼技術(shù)還用于數(shù)據(jù)存儲(chǔ)系統(tǒng)，提高數(shù)據(jù)存儲(chǔ)密度；用于數(shù)據(jù)傳輸系統(tǒng)，提高數(shù)據(jù)傳輸速率；用于各種數(shù)字通信系統(tǒng)，提高通信質(zhì)量 ；用于數(shù)字音頻 /視頻傳輸系統(tǒng)以及視聽娛樂設(shè)備，為我們的生活帶來美妙的音樂和完美的視覺享受；而且糾錯(cuò)碼技術(shù)還應(yīng)用于超大規(guī)模集成電路設(shè)計(jì)中，以提高集成電路芯片的成品率，降低芯片的生產(chǎn)成本。例如，用于 RS 碼譯碼的 BM 算法進(jìn)一步發(fā)展成熟，出現(xiàn)了無求逆的 BM（ iBM）算法、 Euclid 算法、 WelchBerlekamp 算法（ WB 算法）等，其超大規(guī)模集成電路（ VLSI）實(shí)現(xiàn)也得到了充分的發(fā)展。 80 年代初， Goppa 等將代數(shù)幾何的理論與方法系統(tǒng)地應(yīng)用于編碼理論中，由 Goppa 碼引出了代數(shù)幾何碼，使得 Goppa 碼日益引起了人們的極大興趣。在這方面，著名的有廣義最小距離（ GMD）譯碼算法、 Chase 算法等。但由于計(jì)算復(fù)雜度大大增加， MAP 算法直到 1993 年 Berrou 發(fā)現(xiàn) Turbo 碼之后才得到廣泛應(yīng)用。第一個(gè)成功的級(jí)聯(lián)碼是采用卷積碼作內(nèi)碼、 RS碼作外碼的串行級(jí)聯(lián)碼，其典型應(yīng)用是在衛(wèi)星通信、深空探測(cè)等領(lǐng)域，如 Voyager、 Galileo、 Cassini 等任務(wù)，這種編碼方式還被應(yīng)用于美國的數(shù)字電視（ ATSC）、歐洲的數(shù)字視頻廣播（ DVB）和數(shù)字音頻廣播（ DAB）等系統(tǒng)中；另一種典型的級(jí)聯(lián)碼是 C. Berrou 于 1993 年發(fā)現(xiàn)的并行級(jí)聯(lián)卷積碼（ PCCC），即我們通常所稱的 Turbo 碼，這是一種逼近 Shannon 限的碼。 1）提出了許多有效的編、譯碼方法。之后，信道編碼理論與與技術(shù)的大致經(jīng)歷了以下幾個(gè)發(fā)展階段： 1. 50 年代至 60 年代初 這是編碼理論從無到有并得到迅速發(fā)展的年代，現(xiàn)代編碼理論的許多思想都起源于這一時(shí)期。 關(guān)鍵 詞 ： ReedSolomon 編碼 ； 抽象代數(shù) ； RS碼 編碼 ； RS 碼 譯碼 算法； RS(255,223)仿真；MATLAB 2 1 引言 信道編碼 理論與技術(shù)的發(fā)展歷程及應(yīng)用 Shannon 的信道編碼定理給出了有噪信道通信的最大速率，證明了好碼的存在性，但對(duì)該定理證明是非構(gòu)造性的，它沒有告 訴我們?cè)趺礃?gòu)造好碼。在衛(wèi)星通訊中，差錯(cuò)控制編碼技術(shù)對(duì)降低誤碼率、提高通信的可靠性具有非常重要的作用。 20 附 錄 18 致謝 13 BCH/RS 碼的解碼步驟 9 4 BCH 碼、 RS 碼及其編碼 8 歐幾里得算法 8 有限域 7 環(huán)和域 7 群 編號(hào)： 課程設(shè)計(jì)說明書 題 目： RS(255,223)糾錯(cuò)編碼的 MATLAB 仿真 目 錄 1 引言 2 糾錯(cuò)編碼簡介 5 2 Reed – Solomon 編碼概述 6 3 Reed – Solomon 編碼抽象代數(shù)基礎(chǔ) 9 RS 碼的構(gòu)造方法 10 5 RS 碼的譯碼 12 多 項(xiàng)式的歐幾里得算法 16 7 總結(jié) 由于它突出的糾錯(cuò)能力 (特別是糾突發(fā)錯(cuò)誤的能力 ),常被應(yīng)用于數(shù)據(jù)存儲(chǔ)以及現(xiàn)代數(shù)字通信系統(tǒng)中。為此，本文在 詳細(xì)介紹 RS(255,223)編碼 譯碼的 基礎(chǔ)上，利用 MATLAB 軟件對(duì)該理論進(jìn)行 仿真 。 但是，“過程比目標(biāo)更重要”，在應(yīng)對(duì)這一挑戰(zhàn)的過程中，編碼理論家和工程師們應(yīng)用組合數(shù)學(xué)、線性代數(shù)、概率論、有限域理論等數(shù)學(xué)工具，建立了糾錯(cuò)碼的性能參數(shù)限，發(fā)現(xiàn)了許多構(gòu)造糾錯(cuò)碼的方法，并設(shè)計(jì)了有效的編譯碼算法，為信息技術(shù)的蓬勃發(fā)展建立了不朽的功勛！ 在 Shannon 的論文發(fā)表之前， Richard Hamming 就已經(jīng)為 早期的計(jì)算機(jī)設(shè)計(jì)了一種糾單個(gè)錯(cuò)誤的碼，邁出了信道編碼理論與技術(shù)研究的第一步。在此期間，以代數(shù)方法特別是以有限域理論 3 為基礎(chǔ)的線性分組碼理論已趨成熟。 1966 年， G. D. Forney 第一次采用簡單的分量碼構(gòu)造級(jí)聯(lián)碼，以提高碼的性能。 1974 年，Bahl 等提出了一種最大后驗(yàn)概率（ MAP）譯碼算法（也稱為 BCJR 算法），其誤比特率（ BER）性能優(yōu)于 Viterbi 算法。而對(duì)于分組碼，基于格圖的譯碼與代數(shù)譯碼相比，復(fù)雜度會(huì)大大增加，因此次優(yōu)的譯碼算法成為首選。 1）在理論上，以 Goppa 為首的一批學(xué)者在 70 年代初較系統(tǒng)地構(gòu)造了一類逼近 Shannon 限的有理多項(xiàng)式碼 —— Goppa 碼，這在糾錯(cuò)碼的歷史上具有劃時(shí)代的意義。 4 2）這期間微電子技術(shù)的迅速發(fā)展，為編碼技術(shù)的實(shí)用化打下了堅(jiān)實(shí)的物質(zhì)基礎(chǔ)；各種實(shí)際應(yīng)用也帶動(dòng)了信道編碼技術(shù)的發(fā)展，編碼技術(shù)的實(shí)用化得到了極大關(guān)注，并取得了巨大的進(jìn)展。若不應(yīng)用信道編碼技術(shù)，這些成就的取得是不可企及的。在迭代譯碼器中，所采用的分量碼 MAP 譯碼器可以用軟入輸出Viterbi 算法（ SOVA）代替，這會(huì)使 Turbo 碼譯碼性能略有下降，但大大降低了計(jì)算復(fù)雜度和存儲(chǔ)量要求。 另一方面，在探究 Turbo 碼迭代算法的過程中， Mackay 和 Neal 于 1996 年重新發(fā)現(xiàn)了 Gallager于 60年代提出的具有稀疏校驗(yàn)矩陣的線性分組碼 —— LDPC碼，基于 Tanner圖進(jìn)行迭代譯碼，其性能與 Turbo 碼差不多?？諘r(shí)碼的基本思想是采用多個(gè)發(fā)射天線和多個(gè)接收天線來提高系統(tǒng)容量，關(guān)于空時(shí)碼已有許多研究文獻(xiàn)。另一方面， Koetter 和 Vardy 基于GuruswamiSudan 算法，將接收符號(hào)的軟信息轉(zhuǎn)化為一系列的代數(shù)條件，用代數(shù)方法實(shí)現(xiàn)了 RS 碼的軟判決譯碼。由于存在著干擾 ,因而接收端接收到的二進(jìn)制信號(hào)串可能與原來的二進(jìn)制信號(hào)串不相等 ,從而產(chǎn)生了二進(jìn)制信號(hào)的錯(cuò)誤傳遞。第二個(gè)途徑就是我們所要談到的采用糾錯(cuò)碼 (Error correcting code)的方法以提高抗干擾能力。在接收端 ,當(dāng)接收到二進(jìn)制信號(hào)串后立即對(duì)接收到的糾錯(cuò)碼進(jìn)行檢查 ,查對(duì)在途中是否失真 ,如失真則負(fù)責(zé)糾正。碼中的字稱為碼字 (Code Word)。設(shè)有長度為 2的字 ,它們一共可有 2x2=4 個(gè) ,創(chuàng)門所組成的字集 S,={00,01,10,11}。因?yàn)榇藭r(shí) 01和10 均為廢碼 ,而當(dāng) H 在傳遞過程中第一個(gè)碼元由 1 變?yōu)?O,即整個(gè)字成為 01 時(shí) ,由于 01是廢碼 ,因而我們發(fā)現(xiàn)傳遞過程中出現(xiàn)了錯(cuò)誤。因?yàn)榇a字 001 出現(xiàn)錯(cuò)誤后將變?yōu)?:000,011,101,而碼字 110出現(xiàn)錯(cuò)誤后將變?yōu)?:111,100,010。 2 Reed – Solomon 編碼 概述 ReedSolomon 碼（ RS 碼）是 Reed 和 Solomon 于 1960 年發(fā)現(xiàn)的一類多元最大距離可分（ MDS）碼，其最小距離達(dá)到了 Singleton 限 mind = n ? k+ 1，從這個(gè)意義上講， RS 碼是最佳的。在工程實(shí)踐中通常采用的“直接二級(jí)邏輯設(shè)計(jì)”僅僅依靠綜合工具對(duì)所設(shè)計(jì)的電路進(jìn)行優(yōu)化，不能有效地利用 FPGA 所提供的資源，降 低有限域乘法器的時(shí)延。在 AWGN 信道條件下， RS 碼的最大似然譯碼與硬判決距離譯碼相比，會(huì)有 ~ 的軟判決譯碼增益；在衰落信道條件下，其軟判決