[發明專利]一種Reed?Solomon碼糾錯方法

有效

• 申請號: 201310578455.7
• 申請日: 2013-11-14
• 公開（公告）號: CN103595423B
• 公開（公告）日: 2017-04-19
• 發明（設計）人: 王萍;王娟;王昭然
• 申請（專利權）人: 天津大學
• 主分類號: H03M13/15
• 分類號: H03M13/15
• 代理公司: 天津市北洋有限責任專利代理事務所12201
• 代理人: 溫國林

技術領域

本發明涉及Reed-Solomon(里德所羅門)碼領域，特別涉及一種Reed-Solomon碼糾錯方法。

背景技術

信道碼元在快速傳輸過程中難免會夾雜入噪聲，使得到的信息有誤，因此對其糾錯就極為重要。研究者在輸入碼中加入冗余校驗碼元來達到糾錯的目的，以保證傳輸的正確性。Reed-Solomon碼^[1]是此類糾錯碼的典型代表。Reed-Solomon碼首先由Reed和Solomon應用Mattson-Solomon多項式于1960年構造出來，是一類具有很強糾錯能力的多進制線性分組碼，具有糾正隨機錯誤和突發錯誤，以及在較中短碼長的條件下糾錯能力接近于理論值等特點，被廣泛應用于數字信號傳輸、深空通訊、高密度磁盤存儲和量子計算^[2]等多方面。

Reed-Solomon碼的糾錯方法由求解伴隨式、求解錯誤位置、求解錯誤值等步驟組成，其中關鍵技術在于如何求解錯誤位置多項式。

目前，Reed-Solomon碼糾錯技術主要有三：

現有技術1使用PGZ方法^[3]糾錯，它使用窮舉法求解錯誤位置多項式，方法實現簡單，易于理解，對于較短的碼非常有效。但耗時較長，不適合維數較高的方程求解。

現有技術2的歐幾里得算法^[4]在計算過程中采用多項式分解的原理來求解錯誤位置多項式的最大公因式，因此需要多次進行多項式的長除。迭代過程中需要計算多項式的次數，消耗大量的時間，延長糾錯周期，影響糾錯的速度，計算方法易陷入不收斂，糾錯率較低。

現有技術3由Truong T K等^[5]人提出。為提高糾錯的效率，他們提出使用變換譯碼的方法進行糾錯，將輸入碼變換至頻域，使用離散傅里葉變換的特性求解復雜的方程式，在GF(2^m)域上通過進行高效的離散傅里葉變換來計算錯誤位置多項式，但算法復雜度高的問題依然存在。

發明內容

本發明提供了一種Reed-Solomon碼糾錯方法，本發明縮短了計算時間，降低了計算復雜度，提高了糾錯率的精度，詳見下文描述：

一種Reed-Solomon碼糾錯方法，所述方法包括以下步驟：

(1)將接收碼元序列在GF(2^m)域上進行提升小波變換，GF表示伽羅華域，2^m是伽羅華域中的碼元長度；

(2)對小波變換序列不同層數中的系數求其伴隨式S_k，對每層分解系數進行糾錯；

(3)通過對分層后的系數伴隨式的階數進行評估選取獲取方法，得到錯誤位置多項式；

(4)求解錯誤位置多項式σ(p)的根，得到錯誤位置p_k；

(5)求解錯誤位置的錯誤值Y_k；

(6)將錯誤值Y_k與輸入碼元異或，得到小波域中的糾正碼元，然后進行信號重構，得到正確的碼流；

所述將接收碼元序列在GF(2^m)域上進行提升小波變換的操作具體為：

進行提升小波變換后得到的變換結果為{c_j-n,d_j-n,d_j-(n-1),...,d_j-1}，n為分解層數且n≥2，c為提升小波變換后的低頻分量，d為提升小波變換后的高頻分量，j＝2^m；每分解一層需判斷分解后系數個數，若分解系數的個數大于總數1/3，則繼續分解；

所述對小波變換序列不同層數中的系數求其伴隨式S_k，k＝1,2,...,n+1，對每層分解系數進行糾錯的操作具體為：

①計算q_k伴隨式的行列式值|S_k|，q為提升小波分解后各系數的替代標記；

②若|S_k|≠0，則記錄該層糾正的錯誤t_k，執行步驟③；若|S_k|＝0，k＝k+1后，再重新執行步驟①；

③若Σt_k＝t，則結束糾錯，否則k＝k+1；t為最大糾錯數，t_k為每層分解系數對應的糾錯個數。

所述通過對分層后的系數伴隨式的階數進行評估選取獲取方法的操作具體為：

分層后的系數伴隨式的階數小于次時，采用PGZ算法利用窮舉法來求解；否則使用BM算法迭代。