[發明專利]一種高效低延時并行錢搜索方法和裝置

有效

• 申請號: 201210046129.7
• 申請日: 2012-02-27
• 公開（公告）號: CN102594370A
• 公開（公告）日: 2012-07-18
• 發明（設計）人: 鐘孟辰;陳嵐;楊航;謝文剛;任民
• 申請（專利權）人: 成都國微電子有限公司
• 主分類號: H03M13/15
• 分類號: H03M13/15
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 李贊堅;曹志霞

技術領域

本發明涉及數字通信領域，尤其涉及一種高效低延時并行錢搜索方法和裝置，可廣泛地用于糾錯碼解碼技術。

背景技術

糾錯碼技術在數據通信、數據存儲等方面應用廣泛，現在常見的糾錯碼有：RS(Reed-Solomon，里德-所羅門)碼、BCH碼、海明碼，其中：海明碼由于碼距較小，只能糾正一位錯誤；RS碼、BCH碼可以進行多比特糾錯，因而應用十分廣泛。在RS碼、BCH碼等糾錯碼的解碼過程中，需要根據錯誤位置多項式(以下簡稱錯誤多項式)，利用錢搜索找到錯誤碼發生的位置。

錢搜索算法是通過遍歷碼塊中的所有位置，最終確定錯誤發生的位置。錢搜索算法，即對于接受碼多項式r(x)＝r₀+r₁x…+r_n-1x^n-1?進行逐比特譯碼，其中，在伽羅華域GF(2^m)中n＝2^m-1。為了譯r_n-1，譯碼器檢驗α^n-1是否是錯誤位置數，也就是檢驗它的倒數α是不是錯誤位置多項式σ(x)的根。如果α是σ(x)的根，則有σ₀+σ₁α+σ₂α²+…+σ_tα^t＝0，其中t為錯誤位置多項式的階。由此，譯碼器要構造σ₁α，σ₂α²，…，σ_tα^t，然后再判斷他們的和是不是等于σ₀。一般地，如需要要譯r_n-i，就要檢驗αⁱ是不是滿足σ₀+σ₁αⁱ+σ₂(αⁱ)²+…+σ_t(αⁱ)^t＝0；根據伽羅華域的加法計算規則，也就是檢驗是否滿足σ₁σ+σ₂σ²+…+σ₂σ²＝σ₀。

傳統的錢搜索方法需要逐位搜索檢驗，具體采用串行處理的方式，也即一個時鐘周期只能處理一個bit的數據，一般軟件解碼系統等對速度要求不高的應用系統多采用這種方法。但對于數據傳輸率要求高的數據通信系統而言，這嚴重地制約了傳輸速度。

為了提高數據的傳輸速率，文獻“10-and?40-Gb/s?Forward?Error?Correction?Devices?for?Optical?Communications-By?Leiei?Song，Meng-Lin?Yu?and?Michael?S.Shaffer”提到了一種并行錢搜索方法。該方法采用級聯乘法器實現并行錢搜索，對于GF(2^m)域的二進制BCH碼(n，k)(n＝2^m-1)而言，其從最高位r_n-1(n＝2^m-1)開始進行并行錢搜索。該方法雖然做到了并行錢搜索，相比于傳統的串行錢搜索電路提高了效率，但是由于其采用級聯乘法器的方式，并行度越大，級聯的乘法器越深，因而電路的關鍵路徑延時就越大，由此不適用于高并行度的錢搜索要求。

為了解決此問題，論文“Small?Area?Parallel?Chien?Search?Architectures?for?Long?BCH?Codes-By?Yanni?Chen?and?Keshab?K.Parhi”公布了一種新的并行錢搜索方法。該方法增加的乘法器相對獨立，并沒有級聯，從而可使電路關鍵路徑的延時固定，不受并行度的影響。同時，該電路兼容性好，適用于同一域下的任意縮短碼。但是，此錢搜索方法和之前的錢搜索方法一樣，仍然是從高位r_n-1(n＝2^m-1)開始進行譯碼的，其搜索周期長。例如，若對于1K信息進行二進制BCH碼的編譯碼，為了滿足BCH碼的碼字長度2^m-1，采用GF(2¹⁴)域并采用32位并行計算方式時，若完成一個碼字的錢搜索就需要2¹⁴/32＝512個時鐘周期，故同樣不能滿足實時解碼糾錯的要求。