【正文】 () printf(接收碼字正確，無(wú)誤碼)。首先用C語(yǔ)言偽代碼說明BCH碼的時(shí)域解碼算法，如下所示：/*二元域BCH碼的屬于解碼算法*//*碼長(zhǎng)n，設(shè)計(jì)糾錯(cuò)能力t，接收向量R，錯(cuò)誤圖案向量E，解碼碼字向量*/{ for(j = 1 to 2t) 。而對(duì)于多元域上的RS碼，是多元域元素，還需要進(jìn)一步求出。所以，如果，說明第個(gè)位置上的接收向量，存在誤碼，否則第個(gè)位置上的接收向量是正確的。求出后，解碼碼字向量時(shí)域算法的本質(zhì)就是對(duì)錯(cuò)誤位置多項(xiàng)式進(jìn)行驗(yàn)根。 BCH/RS碼的解碼步驟有了關(guān)鍵方程和歐幾里得抽象函數(shù)，討論BCH/RS解碼的步驟就水到渠成了。那么存在且唯一存在標(biāo)號(hào)使得用一個(gè)歐幾里得抽象函數(shù)表示上述結(jié)果。這里，是單調(diào)遞增函數(shù)，而也是單調(diào)遞增函數(shù)。用歐幾里得算法可以求得。多項(xiàng)式上的歐幾里得算法 給定兩個(gè)有限域F上的兩個(gè)多項(xiàng)式可以用歐幾里得除法得到其最大公約數(shù)，并求得，滿足歐幾里得除法求的步驟如下：第一步：不失一般性，假設(shè)且令第二步：用除以，得到其商數(shù)和余數(shù)，亦即第三步：如果，停止運(yùn)算，并記；否則，轉(zhuǎn)第二步。求解的關(guān)鍵算法是歐幾里得算法。t是BCH/RS碼的設(shè)計(jì)糾錯(cuò)能力。記伴隨式多項(xiàng)式 解碼算法的目的是已知伴隨式向量S求錯(cuò)誤圖案向量E，從而得到解碼向量，由于只是知道頻域向量的前2t個(gè)分量，需要用對(duì)關(guān)鍵方程降次。定理 關(guān)鍵方程：對(duì)于固定的向量V，多項(xiàng)式，和滿足一下關(guān)鍵方程有了上述的數(shù)學(xué)基礎(chǔ)，就可以引入BCH/RS碼的關(guān)鍵方程了。最后，定義V的數(shù)值多項(xiàng)式。在定義V的位置多項(xiàng)式。對(duì)于,在定義V和的生成多項(xiàng)式：和。IDFT中的是以特征p為模的同余類。 關(guān)鍵方程的引入令F是一個(gè)含有n階單元本原元的域，那么根據(jù)定義有，再令V是F上的一個(gè)n維向量， 稱為時(shí)域向量。而歐幾里德（Euclid)算法更容易理解些，所以得到了更廣泛的應(yīng)用。之后，錢（Chien)、 福尼（Formey)、梅西（Massey)和巴勒坎普（Berlekamp)相繼提出了更高效的 BCH解碼算法。5 RS碼的譯碼由于BCH碼和RS碼都是循環(huán)碼，所以可以采用一般的梅杰特解碼器，但是 BCH碼和RS碼的設(shè)計(jì)糾錯(cuò)能力都比較髙，從而使得梅杰特解碼器的實(shí)現(xiàn)復(fù)雜度 BCH碼和RS碼的解碼原理是一樣的，其髙效解碼算法的基礎(chǔ)在于一個(gè)關(guān)鍵方程 的引入和基于多項(xiàng)式的歐幾里德算法。例如，美國(guó)宇航局（NASA）在探險(xiǎn)者號(hào)（Voyager）上用了256進(jìn)制的[255,223,33]RS碼，其生成擴(kuò)域的本原多項(xiàng)式是，生成多項(xiàng)式是。再根據(jù)表格的各次冪將其映射為二進(jìn)制編碼序列即可得到RS碼。那么可以求得上的碼字多項(xiàng)式。得到長(zhǎng)度為n的多元序列后，對(duì)于每一個(gè)上的元素，再映射為m重向量，從而得到長(zhǎng)度為nm的二進(jìn)制編碼序列。這里的、和都是上的多項(xiàng)式。利用和等運(yùn)算規(guī)則，可以將展開并化簡(jiǎn)為。如果定義在上的生成多項(xiàng)式，其中是定義在上的本原元，那么該BCH碼被稱為糾錯(cuò)能力為t的RS碼。另外，實(shí)際的糾錯(cuò)能力t，可能會(huì)大于設(shè)計(jì)糾錯(cuò)能力的t.BCH碼的編碼是在二元域完成的，對(duì)比特進(jìn)行編碼，與普通的二進(jìn)制循環(huán)碼并無(wú)不同。進(jìn)一步假設(shè)非本原元和本原元滿足關(guān)系，其中，如果成立，那么，也就是說是n階非本原元。對(duì)于任意的證書m和糾錯(cuò)數(shù)t，都可以構(gòu)造出最小距離為d的二元本原BCH碼，[n, k, d]，滿足。如果BCH碼的根是非本原元，稱為非本原BCH碼。對(duì)于設(shè)計(jì)糾錯(cuò)能力為t的循環(huán)碼，器生成多項(xiàng)式含有2t個(gè)連續(xù)冪次的根，這樣的循環(huán)碼稱為BCH碼。4 BCH碼、RS碼及其編碼 BCH碼、RS碼簡(jiǎn)介如前所述，BCH碼是糾錯(cuò)能力可能的循環(huán)碼，由Bose、Chandhari和Hocquenghem在1950~1960年間分別獨(dú)立地提出。歐幾里得算法又被稱為輾轉(zhuǎn)相除法，這里是單調(diào)下降序列。 歐幾里得算法歐幾里得算法給定兩個(gè)正整數(shù)a,b，可以用歐幾里得除法得到其最大公約數(shù)(a,b)，并求得A，B，滿足(a,b)=Aa+Bb。例如，對(duì)于m = 8時(shí)上的m次本原多項(xiàng)式為對(duì)于m = 7時(shí)上的m次本原多項(xiàng)式為 定義 設(shè)為中的元素，多項(xiàng)式是上使的最低次多項(xiàng)式，則稱為最小多項(xiàng)式。定義 對(duì)于GF(q)上的每個(gè)非零元素，如果其階數(shù)是q1,則稱為本原元素。最簡(jiǎn)單的有限域是二元域GF(2)={0,1}。3 Reed – Solomon編碼抽象代數(shù)基礎(chǔ) 群定義 設(shè)G是一個(gè)非空集合，稱映射為G上的一個(gè)二元運(yùn)算，即對(duì)于G中仍以兩個(gè)元a和b，唯一確定(a,b).記為,為了方便起見，可寫成c=ab.定義 設(shè)G是一個(gè)非空集合，是G上的一個(gè)二元運(yùn)算，如果G滿足下列條件：a) （結(jié)合律）對(duì)于任意,有b) （單位元）G中存在單位元，對(duì)于任意，滿足c) （逆元）對(duì)于任意，存在的逆元，滿足則稱G為群，記為. 如果群滿足交換律，即對(duì)于任意，滿足則稱群 為交換群或阿貝爾群. 環(huán)和域定義 設(shè)R是一個(gè)非空集合，R上有兩個(gè)二元運(yùn)算和，分別成為加法和乘法，如果R滿足下列條件a) 為加法阿貝爾群b) （結(jié)合律）對(duì)于任意,有c) （分配律）對(duì)于任意,有 稱R為環(huán)，記為，如果他對(duì)乘法滿足交換律，即對(duì)任何稱環(huán)為交換環(huán) 定義 設(shè)為交換環(huán)，表示R中所有非零元的集合，如果在乘法運(yùn)算下構(gòu)成交換群，則稱為域?，F(xiàn)有的 RS 碼軟判決譯碼算法主要有以下四類：l 基于代數(shù)譯碼器的軟判決譯碼：主要有糾錯(cuò)糾刪譯碼、廣義最小距離（GMD）譯碼算法、Chase 算法、Lacan 算法、有序統(tǒng)計(jì)量譯碼（OSD）算法等；l 基于格圖的譯碼：主要有 Vardy 和 Be’ery提出的比特級(jí)軟判決譯碼算法、Ponnampalam 和 Vucetic提出的簡(jiǎn)化的比特級(jí)軟判決譯碼算法等；l 基于 Tanner 圖的譯碼：基于自適應(yīng)校驗(yàn)矩陣的軟判決譯碼算法、基于臨界抽取濾波器組表示的軟判決譯碼算法等；l 表單譯碼：主要有 KoetterVardy 算法等。2005 年，Guruswami 和 Vardy[90]在 IEEE 信息論會(huì)刊上撰文指出，RS 碼的最大似然譯碼是 NPHard 問題。眾所周知，從最小化不正確譯碼概率的意義上講，最大似然譯碼（MLD）是最好的方法。就作者所知，目前還沒有一種系統(tǒng)的方法，可以用來(lái)設(shè)計(jì)高速并行有限域乘法器。如何用現(xiàn)場(chǎng)可編程門陣列（FPGA）實(shí)現(xiàn)通用有限域乘法器，降低其運(yùn)算時(shí)延，是軟件無(wú)線電中 RS 碼譯碼子系統(tǒng)設(shè)計(jì)過程中要考慮的一個(gè)關(guān)鍵的問題。之后幾十年里，RS 碼的硬判決譯碼得到了深入的研究，其理論和技術(shù)都已經(jīng)非常成熟。當(dāng)錯(cuò)誤超過兩個(gè)碼元時(shí),它就既不能發(fā)現(xiàn)錯(cuò)誤,更無(wú)法糾正了。故如碼字001在傳遞過程中任何一個(gè)碼元出現(xiàn)了錯(cuò)誤,整個(gè)碼字只會(huì)變?yōu)?01!011或000,但是都可知其原碼為001。利用此編碼我們不僅能發(fā)現(xiàn)錯(cuò)誤而且能糾正錯(cuò)誤。對(duì)00也有同樣的情況。但是,當(dāng)我們選取52的一個(gè)子集如C2二{00,川作為編碼時(shí)就會(huì)發(fā)生另一種完全不同的情況。當(dāng)選取編碼為52時(shí),這種編碼不具有抗干擾能力。我們下面舉出幾個(gè)關(guān)于糾錯(cuò)碼的例子。不在碼中的字稱為廢碼(Invalid Code)。但是,為什么糾錯(cuò)碼具有發(fā)現(xiàn)錯(cuò)誤!糾正錯(cuò)誤的能力呢?糾錯(cuò)碼又是按什么樣的原理去編的呢?為了說明這些問題,我們首先介紹一些基本概念:由0和1組成的串稱為字(Word),一些字的集合稱為碼(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)制信號(hào)變成為適宜于信道傳播的電信號(hào),這種信號(hào)通過信道傳輸至接收端,首先通過解調(diào)器將其還原為原來(lái)的二進(jìn)制信號(hào),再經(jīng)差錯(cuò)控制器檢驗(yàn)經(jīng)信道傳輸后是否產(chǎn)生失真,并采取措施進(jìn)行糾正。由糾錯(cuò)碼模型可以想到,當(dāng)二進(jìn)制信號(hào)串從發(fā)送端發(fā)送時(shí),需按規(guī)定轉(zhuǎn)換成具有抗干擾能力的糾錯(cuò)碼,然后才發(fā)送出去。這種糾錯(cuò)碼的方法是從編碼上下功夫,使得二進(jìn)制數(shù)碼在傳遞過程中一旦出錯(cuò),在接收端的糾錯(cuò)碼裝置就能立刻發(fā)現(xiàn)錯(cuò)誤,并將其糾正。但是,大家都知道,這種從物理角度去提高抗干擾能力并不能完全消除錯(cuò)誤的出現(xiàn)。由于在計(jì)算機(jī)和數(shù)據(jù)通信系統(tǒng)中的信號(hào)傳遞是非常的頻繁與廣泛,因此,如何防止傳輸錯(cuò)誤就變得相當(dāng)重要了,當(dāng)然,要解決這個(gè)問題可以有不同的途徑。試想一個(gè)二進(jìn)制信號(hào)傳遞的簡(jiǎn)單模型,它有一個(gè)發(fā)送端和一個(gè)接收端,二進(jìn)制信號(hào)串從發(fā)送端發(fā)出經(jīng)傳輸介質(zhì)而至接收端。 糾錯(cuò)編碼簡(jiǎn)介我們知道,在計(jì)算機(jī)和數(shù)據(jù)通信中,經(jīng)常需要將二進(jìn)制數(shù)字信號(hào)進(jìn)行傳遞,這種傳遞的距離近則數(shù)米!數(shù)毫米,遠(yuǎn)則超過數(shù)千公里。但Sudan算法只適用于碼率不大于1/3的RS碼，而1999年提出的GuruswamiSudan算法則可適用于任意碼率的RS碼和代數(shù)幾何碼。由于RS碼在眾多數(shù)字通信系統(tǒng)、數(shù)據(jù)存儲(chǔ)系統(tǒng)中的成功應(yīng)用，以及其軟判決譯碼性能的巨大潛力，RS碼的軟判決譯碼問題也得到了很大的關(guān)注。幾個(gè)月后，Alamouti發(fā)明了低復(fù)雜度的分組空時(shí)碼。最近，采用BCH碼作外碼、LDPC碼作內(nèi)碼的級(jí)聯(lián)碼已經(jīng)被DVBS2采納?，F(xiàn)在，Turbo碼的迭代算法已經(jīng)成為“Turb