[發明專利]糾錯碼

無效

• 申請號: 200680002430.0
• 申請日: 2006-01-12
• 公開（公告）號: CN101142746A
• 公開（公告）日: 2008-03-12
• 發明（設計）人: 塞巴斯蒂安·安吉爾
• 申請（專利權）人: NXP股份有限公司
• 主分類號: H03M13/00
• 分類號: H03M13/00;H03M13/49
• 代理公司: 中科專利商標代理有限責任公司
• 代理人: 朱進桂

技術領域

本發明涉及糾錯碼，更具體地，涉及一種生成糾錯碼的方法、一種使用糾錯碼計算奇偶校驗符號的方法、以及一種使用糾錯碼對所接收矢量中的錯誤進行校正的方法。本發明還涉及一種用于執行所述方法的軟件和一種使用所述方法的系統。

背景技術

眾所周知，糾錯碼用于存儲或傳輸系統中，以能夠對字的存儲/讀取或傳輸期間可能已發生的至少一個錯誤進行檢測和校正。字(信息符號)典型包括多個比特，例如32比特。一個或多個符號組合在一起成為碼字。糾錯碼生成通常稱作奇偶校驗符號的附加信息。然后，存儲/傳輸整個碼字(信息符號和奇偶校驗符號)。高級糾錯碼基于有限域中的計算，如Galois域(例如，GF(2ⁿ))。熟知的糾錯碼是里德-所羅門碼(Reed-Solomon?code)。典型地，在存儲/傳輸之前計算該碼，并在讀取/接收之后使用用于執行特定有限域計算的定制設計的硬件檢查該碼。在許多應用中，可以使用微控制器或數字信號處理器，然而這些處理器通常具有針對這種運算的硬件支持。實質上，如何使用傳統處理器的其它運算來執行有限域計算是公知的，通常是通過表查找方法。由于使用整數運算執行傳統有限域計算需要太多處理周期、因而很慢，所以對于大多數應用來說，這是不實際的。對于低成本應用，附加的專用軟件的成本會成為問題。

發明內容

本發明的目的是提供一種糾錯碼，該糾錯碼可在整數處理單元上執行，并且能夠對碼字中的至少一個q-ary符號進行校正，其中，q是2的r次冪，r≥1，(q＝2^r)。具體地，本發明目的是要能夠對4級存儲單元(例如，通常用于NAND存儲器中的存儲單元)的4-ary符號(q＝2²)中的錯誤進行校正。

為了實現本發明的目的，提供了一種用于生成對至少一個q-ary符號進行校正的糾錯碼的方法，其中，q是2的r次冪，r≥1，(q＝2^r)；所述方法包括：

-將包括k個信息符號u[0]，...，u[k-1]，k＞1和用于保護信息符號的奇偶校驗符號u[k]的碼字u用作糾錯碼(例如，u＝(u[0]，...，u[k-1]，u[k]))；每個信息符號表示范圍{0，...，2^w-1}內的整數，其中，w＝n^*r，n≥1；

-將項-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod?M包括在奇偶校驗符號u[k]中，其中，M≥2n(k+1)(q-1)+1，乘法·和加法+是可由整數處理單元執行的整數運算，以及a[0]，...，a[k-1]是{0，...，M-1}中的常數；以及

-選擇常數a[0]，...，a[k-1]，以使元素a[i]·d·q^j?mod?M對于i∈{0，...，k-1}和j∈{0，...，n-1}來說是唯一的，-q＜d＜q，d≠0。

為了實現本發明的目的，提供了一種用于保護碼字u免受至少一個q-ary符號中的錯誤的系統，其中，q是2的r次冪，r≥1，(q＝2^r)；所述系統包括：

-用于接收包括k個信息符號u[0]，...，u[k-1]的碼字u的裝置，k＞1，每個信息符號表示范圍{0，...，2^w-1}范圍內的整數，其中，w＝n^*r，n≥1；

-處理器，包括整數處理器單元，用于在程序的控制下計算用于保護信息符號的奇偶校驗符號u[k]，其中，奇偶校驗符號包括-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod?M，M≥2n(k+1)(q-1)+1，乘法·和加法+是整數運算，以及a[0]，...，a[k-1]是在{0，...，M-1}中選擇的、以使元素a[i]·d·q^j?mod?M對于i∈{0，...，k-1}和j∈{0，...，n-1}來說是唯一的常數，-q＜d＜q，d≠0；以及

-用于在傳輸或存儲所述碼字之前將奇偶校驗符號u[k]添加至碼字u的裝置。

所述碼可以對一個或多個q-ary符號錯誤進行校正，并且只使用整數運算(加法、乘法和求模)。這樣，可以在傳統的整數硬件上容易地執行所述碼。僅需要幾個周期，從而所述碼比較快速。