【文章內(nèi)容簡介】 Tanner 圖的譯碼：基于自適應(yīng)校驗矩陣的軟判決譯碼算法、基于臨界抽取濾波器組表示的軟判決譯碼算法等；l 表單譯碼：主要有 KoetterVardy 算法等。這些譯碼算法各有千秋，就實用性而言，GMD算法、ChaseII算法和KoetterVardy算法略勝一籌。3 Reed – Solomon編碼抽象代數(shù)基礎(chǔ) 群定義 設(shè)G是一個非空集合，稱映射為G上的一個二元運算，即對于G中仍以兩個元a和b，唯一確定(a,b).記為,為了方便起見，可寫成c=ab.定義 設(shè)G是一個非空集合，是G上的一個二元運算，如果G滿足下列條件：a) （結(jié)合律）對于任意,有b) （單位元）G中存在單位元，對于任意，滿足c) （逆元）對于任意，存在的逆元，滿足則稱G為群，記為. 如果群滿足交換律，即對于任意，滿足則稱群 為交換群或阿貝爾群. 環(huán)和域定義 設(shè)R是一個非空集合，R上有兩個二元運算和，分別成為加法和乘法，如果R滿足下列條件a) 為加法阿貝爾群b) （結(jié)合律）對于任意,有c) （分配律）對于任意,有 稱R為環(huán)，記為，如果他對乘法滿足交換律，即對任何稱環(huán)為交換環(huán) 定義 設(shè)為交換環(huán)，表示R中所有非零元的集合，如果在乘法運算下構(gòu)成交換群，則稱為域。 有限域定義 設(shè)F為一個域，如果F只含有有限個元素，稱F為有限域，含有q個元素的有限域記為，有限域也成為伽羅華域(Galois field)，用GF(q)或表示q階有限域。最簡單的有限域是二元域GF(2)={0,1}。定義 對于GF(q)上的每個非零元素，存在最小整數(shù)k,使成立，則稱為k階元素。定義 對于GF(q)上的每個非零元素，如果其階數(shù)是q1,則稱為本原元素。定義 上的一個m次多項式，如果他的所有根都是中的本原元素，則稱是m次本原多項式。例如，對于m = 8時上的m次本原多項式為對于m = 7時上的m次本原多項式為 定義 設(shè)為中的元素，多項式是上使的最低次多項式，則稱為最小多項式。具有相同最小多項式的元素，構(gòu)成同一共軛系。 歐幾里得算法歐幾里得算法給定兩個正整數(shù)a,b，可以用歐幾里得除法得到其最大公約數(shù)(a,b)，并求得A，B，滿足(a,b)=Aa+Bb。用歐幾里得除法求(a,b)的步驟如下：第一步：不失一般性，假設(shè)ab，且令第二步：用除以得到其商數(shù)和余數(shù)，亦即第三步：如果，停止運算，并記；否則，轉(zhuǎn)第二步。歐幾里得算法又被稱為輾轉(zhuǎn)相除法，這里是單調(diào)下降序列。用歐幾里得算法可以求得A、B，沿用上述除法得到的和n，其方法如下：第一步：令第二步：計算第三步：如果，停止運算，此時,否則轉(zhuǎn)第二步事實上，只是其中的一個特例。4 BCH碼、RS碼及其編碼 BCH碼、RS碼簡介如前所述，BCH碼是糾錯能力可能的循環(huán)碼，由Bose、Chandhari和Hocquenghem在1950~1960年間分別獨立地提出。最初的BCH碼定義在二元域上，成為二元BCH碼，后來推廣到多源于上。對于設(shè)計糾錯能力為t的循環(huán)碼，器生成多項式含有2t個連續(xù)冪次的根，這樣的循環(huán)碼稱為BCH碼。如果BCH碼的根是本原元，成為本原BCH碼。如果BCH碼的根是非本原元，稱為非本原BCH碼。如果定義在上的本原元以及共2t個連續(xù)冪次都是定義在上的生成多項式的根，那么該BCH碼成為設(shè)計糾錯能力為t的二元本原BCH碼。對于任意的證書m和糾錯數(shù)t，都可以構(gòu)造出最小距離為d的二元本原BCH碼，[n, k, d]，滿足。另外，實際的糾錯能力t，可能會大于設(shè)計糾錯能力的t.同理，如果定義在上的非本原元以及共2t個連續(xù)冪次都是定義在上的生成多項式的根，那么該BCH碼成為設(shè)計糾錯能力為t的二元非本原BCH碼。進一步假設(shè)非本原元和本原元滿足關(guān)系，其中，如果成立，那么，也就是說是n階非本原元。如果成立，那么可以構(gòu)造出最小距離為d的二元非本原BCH碼，[n, k, d]，滿足。另外，實際的糾錯能力t，可能會大于設(shè)計糾錯能力的t.BCH碼的編碼是在二元域完成的，對比特進行編碼，與普通的二進制循環(huán)碼并無不同。而RS的編碼是在多元域上完成的（p是質(zhì)數(shù)），對符號進行編碼，因為RS碼又被視為多元域上的本原BCH碼。如果定義在上的生成多項式，其中是定義在上的本原元，那么該BCH碼被稱為糾錯能力為t的RS碼。 RS碼的構(gòu)造方法第一步，由關(guān)系式算出m，查本原多項式表得到一個m次的本原多項式，從而產(chǎn)生一個的擴域，使域元素（符號）與m重向量建立起一一對應(yīng)的關(guān)系本原多項式表mM本原多項式2345678第二步：根據(jù)設(shè)計糾錯能力t，直接計算定義在上的生成多項式。利用和等運算規(guī)則，可以將展開并化簡為。第三步：已知生成多項式，根據(jù)關(guān)系式，對信息位多項式編碼得到碼字多項式，這就完成了RS碼的編碼過程。這里的、和都是上的多項式。而對于長度為mk的二進制的輸入序列，以m個比特位一組劃分可以得到k個m重向量，再將每個m重向量映射為上的元素，從而得到長度為k的多元序列。得到長度為n的多元序列后，對于每一個上的元素，再映射為m重向量，從而得到長度為nm的二進制編碼序列。例如，對于信息輸入比特序列{100,101,010}，首先根據(jù)表格的各次冪將序列映射為上的序列{}，則其信息位多項式。那么可以求得上的碼字多項式。從而得到上的編碼序列。再根據(jù)表格的各次冪將其映射為二進制編碼序列即可得到RS碼。表格 的各次冪即約多項式3重向量00001001010100011110111101RS碼是糾正短突發(fā)差錯的首選糾錯碼，廣泛應(yīng)用于無線通信的存儲系統(tǒng)中。例如，美國宇航局（NASA）在探險者號（Voyager）上用了256進制的[255,223,33]RS碼，其生成擴域的本原多項式是，生成多項式是。是本原多項式的根，因為含有32個連續(xù)冪次的根，因而改碼的糾錯能力為符號個符號（256進制）或者等效長度是的二進制特發(fā)差錯。5 RS碼的譯碼由于BCH碼和RS碼都是循環(huán)碼，所以可以采用一般的梅杰特解碼器，但是 BCH碼和RS碼的設(shè)計糾錯能力都比較髙，從而使得梅杰特解碼器的實現(xiàn)復(fù)雜度 BCH碼和RS碼的解碼原理是一樣的，其髙效解碼算法的基礎(chǔ)在于一個關(guān)鍵方程 的引入和基于多項式的歐幾里德算法。在BCH/RS碼的解碼算法的發(fā)展歷史上， 彼得森（Peterson)于1960年提出了第一個BCH的解碼算法。之后，錢（Chien)、 福尼（Formey)、梅西（Massey)和巴勒坎普（Berlekamp)相繼提出了更高效的 BCH解碼算法。到了 1975 年，Sugiyama、Kasahara、Hirasawa和Namekawa發(fā)現(xiàn) 也可以采用歐幾里德(Euclid)算法對BCH/RS碼解碼，并發(fā)現(xiàn)巴勒坎普（Berlekamp) 解碼算法與歐幾里德（Euclid)算法相比僅差一個很小的常數(shù)因子。而歐幾里德（Euclid)算法更容易理解些，所以得到了更廣泛的應(yīng)用。具體解碼又可以分為時域解碼和頻域解碼。 關(guān)鍵方程的引入令F是一個含有n階單元本原元的域，那么根據(jù)定義有，再令V是F上的一個n維向量， 稱為時域向量。又令，是V的離散傅里葉變換（DFT），成為頻域向量；DFT（離散傅里葉變換）：那么，可以證明，從頻域到時域的IDFT（逆離散傅里葉變換）也成立；IDFT（逆離散傅里葉變換）：設(shè)F是，p是質(zhì)數(shù)，那么特征是p。IDFT中的是以特征p為模的同余類。易知，所以，根據(jù)歐幾里得算法有。對于,在定義V和的生成多項式：和。那么，可以將上述的離散傅里葉變換寫為：對于V，定義他的支持集，亦即I是V中非零元素的索引集。在定義V的位置多項式。對于，再定義i階穿孔位置多項式。最后，定義V的數(shù)值多項式。那么，可以證明。定理 關(guān)鍵方程：對于固定的向量V，多項式，和滿足一下關(guān)鍵方程有了上述的數(shù)學(xué)基礎(chǔ)，就可以引入BCH/RS碼的關(guān)鍵方程了。設(shè)編碼向量為，信道錯誤圖案為向量，那么接收向量，解碼的第一步是計算伴隨式向量 ,的定義如下那么，令時域向量，那么易知，伴隨式向量S與頻域向量滿足關(guān)系，亦即，伴隨式向量S是的錢2t個分量，這是可以直接觀測到的，而的后（n2t）個分量不能直接觀測到。記伴隨式多項式 解碼算法的目的是已知伴隨式向量S求錯誤圖案向量E，從而得到解碼向量，由于只是知道頻域向量的前2t個分量，需要用對關(guān)鍵方程降次。 所以得到BCH/RS的關(guān)鍵方程 由于V的支持集是發(fā)生誤碼的標(biāo)號集合，所以又被成為錯誤位置多項式，而又被成為錯誤數(shù)值多項式，其中，t是最高次的數(shù)字。t是BCH/RS碼的設(shè)計糾錯能力。 多項式的歐幾里得算法BCH解碼的目標(biāo)是已知，通過求解關(guān)鍵方程，得到和，進而求出。求解的關(guān)鍵算法是歐幾里得算法。在抽象代數(shù)基礎(chǔ)已經(jīng)介紹了歐幾里得算法，這里將其推廣到多項式上。多項式上的歐幾里得算法 給定兩個有限域F上的兩個多項式可以用歐幾里得除法得到其最大公約數(shù)，并求得，滿足歐幾里得除法求的步驟如下：第一步：不失一般性，假設(shè)