[發明專利]一種錯誤位置多項式求解方法及裝置

有效

• 申請號: 201210364948.6
• 申請日: 2012-09-26
• 公開（公告）號: CN102891689A
• 公開（公告）日: 2013-01-23
• 發明（設計）人: 王俊敏;鐘孟辰;楊航;謝文剛;任民
• 申請（專利權）人: 成都國微電子有限公司
• 主分類號: H03M13/15
• 分類號: H03M13/15
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 李麗

技術領域

本申請涉及數字通信和數據信息處理領域，尤其涉及一種錯誤位置多項式求解方法及裝置。

背景技術

糾錯碼技術在數據通信、數據存儲等方面應用廣泛，現在常見的糾錯碼有：RS（Reed-Solomon里德-所羅門）碼、BCH碼、海明碼，其中海明碼由于碼距較小，只能糾正一位錯誤。而RS碼、BCH碼可以進行多比特糾錯，因而應用十分廣泛。在BCH碼的解碼過程中，最關鍵的一步是求解關鍵方程以獲得錯誤位置多項式，它占用了最大的資源和最多的運算量。

對于一個最多可糾t個錯的二進制BCH碼，解關鍵方程就是由求得的2t個伴隨式值S₁、S₂、…、S_2t來確定錯誤位置多項式σ(x)=1+σ₁x+σ₂x²+…+σ_t?x^t的系數σ₁、σ₂、…、σ_t，得到了這個多項式后，就可以通過錢氏搜索等方法來確定錯誤發生的位置，從而糾正產生的錯誤。

圖1為現有技術通用的IBM迭代算法流程圖，設σ^(k)(x)是待求的差錯位置多項式，λ^(k)(x)是輔助計算的中間多項式，δ_(k+1)是連續迭代前后兩個錯誤位置多項式的差值，這里稱為修正值，k代表迭代計算的次數，l^(k)表示多項式σ^(k)(x)的階，γ^(k)是輔助計算的中間量，迭代步驟如下：

第一步：設置初始值：

σ⁽⁰⁾(x)=1;λ⁽⁰⁾(x)=1;l⁽⁰⁾=0;γ⁽⁰⁾=1;k=0

第二步：計算當前迭代值對于牛頓恒等式的誤差：

δk+1=Σi=0l(k)sk+1-iσi(k)]]>

第三步：修正σ(x)產生滿足當前牛頓等式的σ(x)：

σ^(k+1)(x)=γ^(k)σ^(k)(x)+δ^(k+1)λ^(k)(x)x

第四步：根據條件修改中間變量值：

當δ^(k+1)(x)=0or?2l^(k)>k時：

λ^(k+1)(x)=xλ^(k)(x)

l^(k+1)＝l^(k)

γ^(k+1)=γ^(k)

k=k+1

當δ^(k+1)(x)≠0?and?2l^(k)≤k時：

λ^(k+1)(x)=σ^(k)(x)

l^(k+1)＝k+1-l^(k)

γ^(k+1)=δ^(k+1)

k=k+1

第五步：判斷k是否等于2t，如果不是進入第二步；否則結束運算。輸出錯誤位置多項式的系數。