[發明專利]一種RS碼頻域快速譯碼方法

有效

• 申請號: 201510590971.0
• 申請日: 2015-09-16
• 公開（公告）號: CN105207683B
• 公開（公告）日: 2018-10-16
• 發明（設計）人: 李勝強;尚培;周亮
• 申請（專利權）人: 電子科技大學
• 主分類號: H03M13/15
• 分類號: H03M13/15
• 代理公司: 電子科技大學專利中心 51203
• 代理人: 周劉英

本發明公開了一種RS碼頻域快速譯碼方法。本發明在常規RS碼頻域譯碼的基礎上，將本發明的合并同類項法計算傅里葉變換應用到RS碼譯碼過程中，以降低譯碼的復雜度，提升譯碼效率，即基于元素的階將有限域的非零元素分成多個子集合，基于合并同類項法分別計算階為非碼長n的元素所對應的譜分量，其他譜分量由常規傅里葉變換處理得到；為了進一步降低譯碼的復雜度，還可以采用Cooley?Tukey FFT算法計算階為n的元素所對應的譜分量，尤其是當碼長為某些值時，采用合并同類項與Cooley?Tukey FFT算法相結合的譯碼方式，能顯著降低譯碼復雜度。

技術領域

本發明屬于糾錯碼技術領域，尤其涉及一種RS(Reed Solomon)碼頻域快速譯碼方法。

背景技術

糾錯碼的編譯碼歷史始于1948年香農發表的一篇著名論文。香農指出，只要一個通信系統所要求的傳信率R小于信道容量C，就有可能用糾錯碼為此信道設計一通信系統使其輸出差錯概率為任意小。RS碼是一種代數結構比較完美的一種糾錯碼，也是一類有很強糾錯能力的多進制BCH碼，能糾正突發錯誤。RS碼已廣泛應用于CD、DVD以及藍光光盤中，在數據傳輸中，它被用于DSL和WiMAX，在廣播系統中DVB和ATSC中也有其應用。若將碼字看作是時間域或頻率域上的信號，糾錯碼的譯碼可以分為基于有限域的傅里葉變換的頻域譯碼以及時域譯碼。在RS碼頻域譯碼中不需要求出錯誤位置和錯誤值，較其時域譯碼方式譯碼復雜度低。因此，研究RS碼的頻域快速譯碼算法具有重要的意義。

在GF(q^m)域上的糾t個錯誤的RS碼，碼參數n＝q^m-1關系如下：n＝q^m-1，k＝n-2t，d＝2t+1，其中q表示素數(通常取2)，n表示碼長，k表示信息段，d表示最小碼距，其接收多項式r(x)為r(x)＝r₀+r₁x+…+r_n-1x^n-1(n＝q^m-1)，對接收多項式r(x)進行頻域譯碼。常規RS碼頻域譯碼處理包括下列步驟：(1)計算接收多項式r(x)的傅里葉變換R(x)及系數R_j，其中R(x)＝R₀+R₁x+…+R_n-1x^n-1，而R(x)的各傅里葉分量其中α為GF(q^m)的本原元；(2)計算錯誤位置多項式σ(x)，其常用的為基于Berlekamp迭代算法求錯誤位置多項式σ(x)：RS碼頻域譯碼中其2t(t為糾錯個數)個伴隨式分量s₁,s₂,…,s_2t等于R(x)的2t個譜分量R₁,R₂,…,R_2t，由伴隨式分量迭代求出錯誤位置多項式σ(x)＝σ₀+σ₁x+…+σ_vx^v，其中v為實際錯誤個數；(3)計算頻域上錯誤多項式E(x)：RS碼頻域譯碼中的錯誤多項式e(x)的傅里葉變換E(x)的2t個譜分量E₁,E₂,…,E_2t等于R(x)的2t個譜分量R₁,R₂,…,R_2t，按式E_λ+t＝-(σ₁E_λ+t-1+σ₂E_λ+t-2+…+σ_vE_λ+t-v),t+1≤λ≤n-1-λ計算譜分量E_2t+1到E_n-1；按式計算譜分量E₀；(4)計算頻域譯碼V(x)的傅里葉逆變換，輸出譯碼結果。即根據公式V(x)＝R(x)-E(x)計算頻域譯碼V(x)，再計算其逆傅里葉變換，即得譯碼的碼字多項式逆傅里葉變換算法類似于傅里葉變換算法，根據步驟(1)采用的某種方法計算傅里葉逆變換，完成譯碼。