【文章內(nèi)容簡介】 問題。在工程實踐中通常采用的“直接二級邏輯設(shè)計”僅僅依靠綜合工具對所設(shè)計的電路進行優(yōu)化，不能有效地利用 FPGA 所提供的資源，降 低有限域乘法器的時延。就作者所知，目前還沒有一種系統(tǒng)的方法，可以用來設(shè)計高速并行有限域乘法器。 RS 碼的硬判決譯碼器不能充分地利用接收信息，造成了一定的性能損失。眾所周知，從最小化不正確譯碼概率的意義上講，最大似然譯碼（ MLD）是最好的方法。在 AWGN 信道條件下， RS 碼的最大似然譯碼與硬判決距離譯碼相比，會有 ~ 的軟判決譯碼增益；在衰落信道條件下，其軟判決譯碼增益會更大。 2021 年， Guruswami 和 Vardy[90]在 IEEE 信息論會刊上撰文指出， RS 碼的最大似然譯 碼是 NPHard 問題。因此，低復雜度的次優(yōu)譯碼算法成為人們研究的熱點。 現(xiàn)有的 RS 碼軟判決譯碼算法主要有以下四類： ? 基于代數(shù)譯碼器的軟判決譯碼：主要有糾錯糾刪譯碼、廣義最小距離（ GMD）譯碼算法、 Chase 算法、 Lacan 算法、有序統(tǒng)計量譯碼（ OSD）算法等； ? 基于格圖的譯碼：主要有 Vardy 和 Be’ ery 提出的比特級軟判決譯碼算法、Ponnampalam 和 Vucetic 提出的簡化的比特級軟判決譯碼算法等； ? 基于 Tanner 圖的譯碼：基于自適應(yīng)校驗矩陣的軟判決譯碼算法、基于臨界抽取濾波器組表示的軟判決譯碼算法等； ? 表單譯碼：主要有 KoetterVardy 算法等。 這些譯碼算法各有千秋，就實用性而言， GMD 算法、 ChaseII 算法和 KoetterVardy算法略勝一籌。 3 Reed – Solomon 編碼抽象代數(shù) 基礎(chǔ) 群 定義 設(shè) G是一個 非空 集合， 稱 映射 :G G G? ??為 G上的 一個二元運算，即對于 G中 仍以兩個元 a和 b， 唯一確定 c ?? (a,b).記為 c ab?? ,為了 方便起見，可寫成 c=ab. 8 定義 設(shè) G是一個 非空 集合，是 G上的一個二元運算， 如果 G滿足下列 條件： a) （結(jié)合律 ）對于 任意 ,abc G? ,有 ( ) ( )a b c a b c? ? ? ? ? b) （ 單位元） G中存在單位元 e ，對于任意 aG? ，滿足 e a a e a? ? ? ? c) （逆元 ）對于任意 a ， 存在的 逆元 1a? ，滿足 11a a a a e??? ? ? ? 則稱 G為群，記為 ( , )G? . 如果 群 ( , )G? 滿足 交換律，即對于 任意 ,ab G? ，滿足 a b b a? ? ? 則稱 群 為交換群 或阿貝爾群 . 環(huán) 和域 定義 設(shè) R 是一個非空集合， R 上 有 兩個二 元 運算 ? 和 ? ，分別成為 加法 和 乘法 ，如果 R滿足 下列條件 a) ( , )R? 為 加法阿貝爾群 b) （結(jié)合律 ）對于 任意 ,abc R? ,有 ( ) ( )a b c a b c? ? ? ? ? c) （分配律 ）對于 任意 ,abc R? ,有 ()()a b c a b a cb c a b a c a? ? ? ? ? ?? ? ? ? ? ? 稱 R 為環(huán)，記為 ( , , )R?? ，如 果他對乘法滿足交換律， 即對 任何 ,ab R? a b b a? ? ? 稱 環(huán) ( , , )R?? 為交換環(huán) 定義 設(shè) ( , , )R?? 為交換環(huán)， *R 表示 R 中所有非零元的集合，如果 *R 在乘法運算下構(gòu)成交換群 ， 則稱 ( , , )R?? 為域 。 有限域 定義 設(shè) F為一個域，如果 F只含有有限個元素， 稱 F為有限域，含有 q個 元素 的有限域記為 qF ， 有限域也成為伽羅華域 (Galois field)， 用 GF(q)或 qF 表示 q階 有限域 。 最簡單 的有限域是二元域 GF(2)={0,1}。 定義 對于 GF(q)上 的每個非零元素 ? ，存在最小 整數(shù) k,使 1k?? 成立 ，則稱為 k階元素 。 定義 對于 GF(q)上的每個非零元素 ? ，如果其 階數(shù) 是 q1,則稱 ? 為本 原 元素 。 9 定義 ? ?2GF 上 的一個 m 次多項式 ()x? ，如果他的所有根都是 ? ?2mGF 中的本 原 元素，則 稱 ()x? 是 m次本原多項式 。 例如 ，對于 m = 8 時 8(2 ) (2 )mGF GF? 上 的 m次本原多項式為 2 3 4 8( ) 1x x x x x? ? ? ? ? ? 對于 m = 7 時 7(2 ) (2 )mGF GF? 上 的 m次本原多項式為 37( ) 1x x x? ? ? ? 定義 設(shè) ? 為 ? ?2mGF 中的元素，多項式 ()mx是 ? ?2GF 上使 ( ) 0m? ? 的 最低次 多項式 ，則稱 ()mx為最小多項式。具有 相同 最小多項式的元素，構(gòu)成同一共軛系 。 歐幾里得 算法 歐幾里得算法給定 兩個正整數(shù) a,b， 可以 用 歐幾里得除法得到其最大公約數(shù) (a,b)，并求得 A， B，滿足 (a,b)=Aa+Bb。 用 歐幾里得除法 求 (a,b)的步驟如下： 第一步 ： 不失 一般性，假設(shè) ab，且令 21, , 2r a r b k??? ? ? ? 第二步 ：用 1kr? 除以 kr 得到其商數(shù) 2ka? 和余數(shù) 2kr? ，亦即 2 1 2k k k kr a r r? ? ??? 第三步 ：如果 2 0kr? ? ，停止運算 ， 1( , ) kab r?? 并記 2nk??；否則， 1kk??轉(zhuǎn)第二步 。 歐幾里得 算法又被 稱為 輾轉(zhuǎn)相除法，這里 {}kr 是單調(diào)下降序列 。 用 歐幾里得算法可以求得 A、 B，沿用上述除法得到 {}ka 的和 n，其方法如下： 第一步 ：令 10 , 1, k 1nnb b n?? ? ? ? 第二步 ：計算 11k k k kb a b b??? ? ? 第三步： 如果 0k? ，停止運算，此時 01,A b B b???,否則 1kk??轉(zhuǎn) 第二 步 事實 上 ， 11, ( , ) , ( , )k k k kk a b b r b r A B??? ? ?只是其中的一個特例。 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碼 。 10 如果 定義在 ? ?2mGF 上 的本原元 ? 以及 2 3 2t? ? ?、 、 … 、 共 2t個連續(xù)冪次都是定義在 ? ?2GF 上的生成多項式 g()x 的根，那么該 BCH碼成為設(shè)計糾錯能力為 t 的二元本原BCH 碼。對于 任意 的 證書 m 和糾錯數(shù) t，都可以構(gòu)造出最小距離為 d的二元本原 BCH 碼，[n, k, d]， 滿足 2 1 , 2 1 , 2 1mmn k n m t m t d t? ? ? ? ? ? ? ? ?。另外 ， 實際的糾錯能力 t，可能會大于設(shè)計糾錯能力的 t. 同理 ， 如果 定義在 ? ?2mGF 上 的 非 本原元 ? 以及 2 3 2t? ? ?、 、 … 、 共 2t個連續(xù)冪次都是定義在 ? ?2GF 上的生成多項式 g()x 的根，那么該 BCH 碼成為設(shè)計糾錯能力為 t 的二元 非 本原 BCH碼。 進一步 假設(shè)非本原元 ? 和 本原元 ? 滿足 關(guān)系 c??? ， 其中 1 2 1mc? ? ? ，如果 21mnc??成立 ，那么 1n?? ， 也就是說 ? 是 n階非本原元。如果 21mnc??成立 ，那么可以構(gòu)造出最小距離為 d的二元 非 本原 BCH 碼， [n, k, d]， 滿足2 1 , 2 1 , 2 1mmn c k n m t m t d t? ? ? ? ? ? ? ? ?。另外 ， 實際的糾錯能力 t，可能會大于設(shè)計糾錯能力的 t. BCH 碼的編碼是在二元域完成的，對 比特 進行編碼，與普通的二進制循環(huán)碼并無不同 。 而 RS的編碼是在多元域 ? ?mGF p 上 完成 的 （ p 是 質(zhì)數(shù)） ， 對 符號 進行編碼，因為 RS碼又被視為 多元域上 的本原 BCH 碼。如果 定義 在 ? ?mGF p 上 的生成多項式21g( ) ( )t iixx?????， 其中 ? 是 定義在 ? ?mGF p 上 的本原元，那么該 BCH 碼 被稱為糾錯能力為 t的 RS碼。 RS 碼的構(gòu)造方法 第一步 ，由關(guān)系式 21mn??算出 m，查 本原多項式表 得到一個 m 次的本原多項式()Px ， 從而產(chǎn)生一個 ? ?2mGF 的 擴域， 使 域元素（符號） i? 與 m 重向量建立起一一 對應(yīng)的關(guān)系 本原 多項式表 m M 本原 多項式 2 21 xx?? 3 31 xx?? 4 41 xx?? 5 251 xx?? 6 61 xx?? 7 371 xx?? 8 2 3 4 81 x x x x? ? ? ? 第二步： 根據(jù)設(shè)計糾錯能力 t，直接 計算 定義在 ? ?2mGF 上 的生成多項式21g( ) ( )t iixx?????。 利用 1, 0n i i? ? ?? ? ?和 ()P? 等 運算規(guī)則，可以將 21 ()t ii x ?? ??展開 并化簡為 2 ()0g( )t k i iixx????。 11 第三步 ：已知生成多項式 ()gx， 根據(jù)關(guān)系式 ( ) ( ) ( )C x M x g x? ，對信息 位 ()Mx多項式編碼得到碼 字 多項式 ()Cx，這就完成了 RS碼 的編碼過程。這里 的 ()Cx、 ()Mx和 ()gx都是 ? ?2mGF 上的多項式。而對于 長度 為 mk 的二進制的輸入序列，以 m 個 比特位一組劃分可以得到 k個 m重向量，再將 每個 m 重向量映射為 ? ?2mGF 上的元素 i? ，從而得到長度為 k的多元序列 ()Mx。 得到 長度 為 n 的多元序列 ()Cx后，對于每一個 ? ?2mGF 上的元素，再映射為 m重向量，從而得到長度為 nm 的二進制編碼序列。 例如 ，對于信息輸入比特序列 {100,101,010}， 首先根據(jù)表格 ? 的 各次冪將序列映射為 ? ?32GF 上 的序列 { 26? ? ?,}， 則其信息 位 多項式 2 2 6()M x x x? ? ?? ? ?。那么 可以 求得 ? ?32GF 上的碼 字 多項式 。 2 2 6 4 3 3 2 3( ) ( ) ( ) ( ) ( )C x M x g x x x x x x x? ? ? ? ? ?? ? ? ? ? ? ? ?2 6 5 4 2 2 4x x x x? ? ? ? ?? ? ? ? ? 從而得到 ? ?32GF 上的編碼序列 2 2 4{ , , , 0 , , 0 , }? ? ? ? ?。再 根據(jù) 表格 ? 的 各次冪將其映射為二進制編碼序列即可得到 RS碼 { 100 , 010 , 010 , 000 , 100 , 000 , 110 }。 表格 ? 的 各次冪 即約 多項式 3重 向量 0 000 1 001 ? 010 2? 100 3 1???? 011 42? ? ??? 110 52 1? ? ?? ? ? 111 621???? 101 RS碼是糾正短突發(fā)差錯的首選糾錯碼，廣泛應(yīng)用于無線通信的存儲系統(tǒng)中。例如 ，美國宇航局（ NASA） 在 探險者號（ Voyager） 上 用了 256 進制 的 [255,223,33]RS碼 ， 其生成擴域的本原多項式是 2 3 4 8( ) 1 , 8P x x x x x m? ? ? ? ? ?， 生成多項式是2 32( ) ( ) ( ) ( )g x x x x? ? ?? ? ? ?… …。 ? 是 本原 多項式 ()Px 的根，因為 ()gx 含有 32個 連續(xù)冪次的根，因而改 碼 的糾錯能力為 符號 32 / 2 16t ??個符號（ 256 進制 ）或者等效長度是 ( 1) 1 121tm? ? ? 的二進制特發(fā)差錯。 12 5 RS 碼的譯碼 由于 BCH 碼和 RS 碼都是循環(huán)碼，所以可以采用一般的梅杰特解碼器，但是 BCH 碼和 RS 碼的設(shè)計糾錯能力都比較髙，從而使得梅杰特解碼器的 實現(xiàn)復雜度 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ù)定義有 101 (1 )nniixx???? ? ??，再令V是 F上的一個 n 維向量， 0 1 1( , , )nV v v ?? … ,v 稱為 時域向量 。 又 令 ^ ^ ^ ^0 1 1( , , )nV v v v ?? … ,，是 V的離散傅里葉 變換 （ DFT） ， 成為頻域向量 ； DFT（離散傅里葉變換）： 1^0 , [ 0 , 1]n ijjiiv v j n???? ? ?? 那么 ，可以證明，從頻域到時域的 IDFT（逆離散傅里葉變換）也成立 ； IDFT（逆離散傅里葉變換）