(57)【要約】少なくとも１つのｑアレイシンボル（ただし、qは２のｒ乗，ｒ≧１，（ｑ＝２ｒ）とする）における誤りからコードワードｕを保護するシステム１００。コードワードｕ３００は、情報シンボル３１０ｕ［０］，．．．，ｕ［ｋ−１］（ただし、ｋ＞１）を含み、各情報シンボルは、｛０，．．．，２ｗ−１｝の範囲の整数（ただし、ｗ＝ｎ×ｒ，ｎ≧１）を表す。プロセッサ１３０は、プログラムの制御のもとで、情報シンボルを保護するパリティシンボル３１２ｕ［ｋ］を計算するための、整数処理ユニット１４０を有し、だたし、パリティシンボルは、-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) modMの項を含み、乗算・および加算記号＋は、整数演算とする。定数ａ［０］，．．．，ａ［ｋ−１］は、集合｛０，．．．，Ｍ−１｝内の定数（ただし、Ｍ≧１）であり、これら定数は、ｋ要素ａ［ｉ］・ｄ・ｑjｍｏｄＭが、ｉ∈｛０，．．．，ｋ｝，ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に一意となるように選択される。
2008527890.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのｑアレイシンボル（ｑは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１とする）を訂正することができる誤り訂正符号を生成する誤り訂正符号生成方法において、
誤り訂正符合として、ｋ個（ｋ≧１）の情報シンボル（３１０）ｕ［０］，．．．，ｕ［ｋ−１］、および、この情報シンボルを保護するためのパリティシンボル（３１２）ｕ［ｋ］とを含むコードワードｕ（例えば、ｕ＝（ｕ［０］，．．．，ｕ［ｋ−１］，ｕ［ｋ］））を使用するステップであって、各情報シンボルが集合｛０，．．．，２ｗ−１｝内の整数（ただし、ｗ＝ｎ×ｒ，ｎ≧１）を表すものとしたコードワード使用ステップと、
前記パリティシンボルｕ［ｋ］に以下の項を含ませる、すなわち、
-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) mod Mの項を組み込むステップであって、ここで、Ｍ≧２ｎ（ｋ＋１）（ｑ−１）＋１、乗算記号・および加算記号＋は、整数処理ユニットで実行できる整数演算とし、ａ［０］，．．．，ａ［ｋ−１］は｛０，．．．，Ｍ−１｝に含まれる定数とする該項組み込みステップと、
ａ［ｋ］＝１であって、要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭが、ｉ∈｛０，．．．，ｋ｝，
ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に異なるように、
ａ［０］，．．．，ａ［ｋ−１］を選択する選択ステップと
を有することを特徴とする誤り訂正符号生成方法。
【請求項２】
請求項１に記載の誤り訂正符号生成方法において、前記コードワードｕと誤りベクトルｅとを含む受信ベクトルｘのｑアレイシンボル内の１つの誤りを訂正するためのテーブルＴを形成するテーブル形成ステップを有し、
ここで、x=u+e=(u[0]+e[0],...,u[ｋ-1]+e[ｋ-1], u[ｋ]+e[ｋ])であり、加算記号＋は整数処理ユニットによって実行される整数演算であり、
前記テーブルはすべてのあり得るシンドローム、すなわち、
s(x) = (a[0]・x[0]+a[1]・x[1]+...+a[ｋ-1]・x[ｋ-1]+x[ｋ]) mod Mを、それぞれの
（ｉ，ｊ，ｄ）の組み合わせセットと関連付けることにより、ｄの値に基づきｉ番目の情報シンボルｘ［ｉ］におけるｊ番目のｑアレイシンボルの訂正を可能にすることを特徴とする誤り訂正符号生成方法。
【請求項３】
請求項１に記載の誤り訂正符号生成方法において、ｗ＞１とし、前記モジュロＭとして２ｗより小さい最大の素数を選択するステップを有することを特徴とする誤り訂正符合生成方法。
【請求項４】
請求項１に記載の誤り訂正符号生成方法において、ｉ∈｛０，．．．，ｋ｝，
ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、前記要素
ａ［ｉ］・ｄ・ｑｊｍｏｄＭが相互に異なる値となる少なくとも１つの整数の組み合わせセットが見つかるまで、前記定数ａ［０］，．．．，ａ［ｋ−１］の値をランダムに選択することにより、定数ａ［０］，．．．，ａ［ｋ−１］を選択するステップを有することを特徴とする誤り訂正符号生成方法。
【請求項５】
請求項４に記載の誤り訂正符号生成方法において、
それぞれの前記定数ａ［０］，．．．，ａ［ｋ−１］について初期の上限界値Ａ＝Ｍを選択するステップと、
前記定数ａ［０］，．．．，ａ［ｋ−１］の値をランダムに選択するステップと、
ｉ∈｛０，．．．，ｋ｝，ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、前記要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭが相互に異なる値となることを検証するステップと、
肯定的な前記検証の結果に基づいて、前記上限界値Ａを下げて前記選択と検証を繰り返し、連続して検証を行い予め決められた回数の否定的な結果が続いた場合は、最後に肯定的な検証結果が得られた前記ランダムに選定した値を前記定数として使用するステップと
を有することを特徴とする誤り訂正符号生成方法。
【請求項６】
ｑアレイシンボル（ｑは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１）の少なくとも１つの誤りに対してコードワードｕを保護する保護方法において、
情報シンボルｕ［０］，．．．，ｕ［ｋ−１］，を含む（ただし、ｋ≧１）前記コードワードｕを受信する受信ステップ（２１０）であって、各情報シンボルが｛０，．．．，２ｗ−１｝の範囲の整数（ただし、ｗ＝ｎ×ｒ，ｎ≧１）を表すものとした受信ステップと、
前記情報シンボルを保護するパリティシンボルｕ［ｋ］を算出する算出ステップ（２２０）であって、ここで、パリティシンボルは
-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) mod Mの項を含み、この場合Ｍ≧２ｎ（ｋ＋１）（ｑ−１）＋１であり、さらに、乗算記号・および加算記号＋は、整数処理ユニットで実行できる整数演算とし、また、ａ［ｋ］＝１であって、ａ［０］，．．．，ａ［ｋ−１］は、前記要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭがｉ∈｛０，．．．，ｋ｝，
ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に異なるように選択した、｛０，．．．，Ｍ−１｝内の定数とする該算出ステップと、
前記コードワードを送信または蓄積する前に、前記コードワードｕに前記パリティシンボルｕ［ｋ］を付加するステップ（３２０）と
を有することを特徴とする保護方法。
【請求項７】
コードワードｕおよび誤りベクトルｅを含む受信ベクトルｘのｑアレイシンボル中の単独の誤りを訂正する誤り訂正方法であって、ここで、x=u+e=(u[0]+e[0],...,u[ｋ-1]+e[ｋ-1], u[ｋ]+e[ｋ])であり、加算記号＋は整数処理ユニットによって実行される整数演算であり、
前記コードワードｕは情報シンボルｕ［０］，．．．，ｕ［ｋ−１］，ｋ≧１および情報シンボルを保護するためのパリティシンボルｕ［ｋ］を含み、各情報シンボルは｛０，．．．，２ｗ−１｝の範囲の整数（ただし、ｗ＝ｎ×ｒ，ｎ≧１）を表し、前記パリティシンボルは、
-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) mod Mの項を含み、ここで、Ｍ≧２ｎ（ｋ＋１）（ｑ−１）＋１、乗算記号・および加算記号＋は、整数処理ユニットで実行できる整数演算であり、ａ［ｋ］＝１であって、ａ［０］，．．．，ａ［ｋ−１］は、要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭがｉ∈｛０，．．．，ｋ｝，ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に異なるように選択された｛０，．．．，Ｍ−１｝の中の定数である、誤り訂正方法において、
シンドロームs(x) = (a[0]・x[0]+a[1]・x[1]+...+a[ｋ-1]・x[ｋ-1]+x[ｋ]) mod Mを算出するステップ（２６０）と、
シンドロームの結果が０でない場合に、あり得る各シンドロームの結果とそれぞれの（ｉ，ｊ，ｄ）の組み合わせセットを関連付けるテーブルＴを使用して、前記算出したシンドロームについての（ｉ，ｊ，ｄ）の値を決定するステップ（２７０）と、
ｄの値に基づきｉ番目の情報シンボルｘ［ｉ］におけるｊ番目のｑアレイシンボルを訂正するステップ（２８０）と
を含むことを特徴とする誤り訂正方法。
【請求項８】
少なくとも１個のｑアレイシンボル（qは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１）における誤りからコードワードｕを保護するシステム（１００）において、、
情報シンボルｕ［０］，．．．，ｕ［ｋ−１］，ｋ＞１を含むコードワードｕを受信する受信手段であって、各情報シンボルが集合｛０，．．．，２ｗ−１｝内の整数（ｗ＝ｎ×ｒ、ただしｎ≧１）を表すものとした該受信手段と、
プログラムの制御のもとで、情報シンボルを保護するためにパリティシンボルｕ［ｋ］を算出するための、整数処理ユニット（１４０）を含むプロセッサ（１３０）であって、ここで、前記パリティシンボルは、-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) mod Mを含み、また、Ｍ≧２ｎ（ｋ＋１）（ｑ−１）＋１であり、さらに、乗算記号・および加算記号＋は、整数処理ユニットで実行できる整数演算であり、また、ａ［ｋ］＝１であって、ａ［０］，．．．，ａ［ｋ−１］は、要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭがｉ∈｛０，．．．，ｋ｝，ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に異なるように選択した、集合｛０，．．．，Ｍ−１｝内の定数とする、該プロセッサと、
前記コードワードを送信または格納する前に、前記コードワードｕに前記パリティシンボルｕ［ｋ］を付加する手段と
を備えたことを特徴とするシステム。
【請求項９】
請求項８に記載のシステムにおいて、
前記コードワードｕと誤りベクトルｅとを含むベクトルｘを受信または読み出し手段であって、ここに、x=u+e=(u[0]+e[0],...,u[ｋ-1]+e[ｋ-1], u[ｋ]+e[ｋ])であり、加算記号＋は整数演算とする、該受信または読み出し手段と、
プログラムの制御下で、シンドローム
s(x) = (a[0]・x[0]+a[1]・x[1]+...+a[ｋ-1]・x[ｋ-1]+x[ｋ]) mod Mを算出し、このシンドロームの結果が０でない場合は、あり得る各シンドロームの結果とそれぞれの（ｉ，ｊ，ｄ）の組み合わせセットを関連付けるテーブルＴを使用して、算出したシンドロームについての（ｉ，ｊ，ｄ）の値の組み合わせセットを読み出し、さらに、前記ｄの値に基づき前記ｉ番目の情報シンボルｘ［ｉ］における前記ｊ番目のｑアレイシンボルを訂正することによって、前記受信ベクトルｘのｑアレイシンボルの単独の誤りを訂正するように動作する該プロセッサと、
を備えたことを特徴とするシステム。
【請求項１０】
請求項８に記載のシステムにおいて、前記システムは前記コードワードｕを格納するためのメモリ（１１０）を含み、ここで、前記メモリの個々のメモリセルは、ｑ＞２において、単一のｑアレイシンボルを格納するように物理的に配列したことを特徴とするシステム。
【請求項１１】
請求項１０に記載のシステムにおいて、前記メモリをＮＡＮＤ型フラッシュメモリとしたことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正符号に関し、特に、誤り訂正符号を生成する方法、誤り訂正符号を使用してパリティシンボルを算出する方法、および、受信したベクトル内の誤りを訂正するために誤り訂正符号を使用する方法に関する。更に、本発明は、その方法を実行するためのソフトウェアとその方法を使用するシステムに関する。
【背景技術】
【０００２】
誤り訂正符号は、１ワードの記憶／読み込み中や伝送中に起きたかもしれない少なくとも１つの誤り（エラー）を検出し、かつ訂正することが可能な、記憶装置や伝送システムに使用されることが良く知られている。このワード（情報シンボル）は、概して複数個のビット（例えば３２ビット）を含む。一個以上のシンボルを、グループ化してコードワードとする。誤り訂正符号は、通常パリティシンボルと称される付加情報を生成する。その後、コードワード全体（情報シンボルおよびパリティシンボル）が、格納／伝送される。高度な誤り訂正符号は、有限体（例えばガロア体（例えばＧＦ（２ｎ）））の演算に基づいている。良く知られている誤り訂正コードは、リード−ソロモン符号である。これらのコードは、概して、格納／伝送の前に算出され、読み込み／受信した後に特定の有限体計算を実行するための専用設計のハードウェアを使用して検査される。多くのアプリケーションにおいて、マイクロコントローラまたはデジタル信号プロセッサを利用できるが、通常これらのプロセッサは、この種の演算のための支援ハードウェアを有している。有限体計算が、この種の従来のプロセッサ自体の他の操作を使用して、どのように実行することができるかについては知られており、それはしばしば表検索によって行われる。ほとんどのアプリケーションについて、これは実用的に可能ではない、なぜならば、整数演算を使用して従来の有限体計算を実行するには、非常に多くの処理サイクルを必要とし、したがって処理が遅すぎるためである。低コスト用途には、付加的な特定のハードウェアコストが課題である。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明の目的は、整数処理ユニットで実行でき、コードワード内の少なくとも1個のｑアレイシンボル（qは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１）の訂正が可能な、誤り訂正符号を提供することである。とくに、本発明の目的は、例えば、ＮＡＮＤ型メモリにしばしば使用されるような４レベルのメモリセル用の４アレイシンボル（ｑ＝２２）内の誤りを訂正できるようにすることにある。
【課題を解決するための手段】
【０００４】
本発明の目的を解決するために、少なくとも1個のｑアレイシンボル（qは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１）を訂正するための誤り訂正符号を生成する方法を提供する。本発明方法は、以下のステップを含む、すなわち、
‐誤り訂正符号として、ｋ個（ｋ＞１）の情報シンボルｕ［０］，．．．ｕ［ｋ−１］、およびこの情報シンボルを保護するパリティシンボルｕ［ｋ］を含むコードワードｕ（例えば、ｕ＝（ｕ［０］，．．．，ｕ［ｋ−１］，ｕ［ｋ］））を使用するステップであって、各情報シンボルが集合｛０，．．．，２ｗ−１｝内の整数（ただし、ｗ＝ｎ×ｒ、ｎ≧１）を表するものとしたコードワード使用ステップと、
‐パリティシンボルｕ［ｋ］に以下の項を含ませる、すなわち、
-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) mod Mの項を組み込むステップであって、ここで、Ｍ≧２ｎ（ｋ＋１）（ｑ−１）＋１であり、乗算記号・および加算記号＋は、整数処理ユニットによって実行可能な整数演算とし、さらに、ａ［０］，．．．，ａ［ｋ−１］は、｛０，．．．，Ｍ−１｝内の定数とする該項組み込みステップと、
‐要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭが、ｉ∈｛０，．．．，ｋ−１｝，
ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に異なるように、定数ａ［０］，．．．，ａ［ｋ−１］を選択するステップと
を有することを特徴とする。
【０００５】
本発明の課題を解決するために、少なくとも一個のｑアレイシンボル（qは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１）における誤りに対してコードワードｕを保護するためのシステムを提供する。本発明システムは以下のものを有する、すなわち、
‐情報シンボルｕ［０］，．．．ｕ［ｋ−１］，ｋ＞１を含むコードワードｕを受信する受信手段であって、各情報シンボルが、集合｛０，．．．，２ｗ−１｝内の整数（ｗ＝ｎ×ｒ、ただしｎ≧１）を表するものとした該受信手段と、
‐プログラムの制御下において、情報シンボルを保護するために、パリティシンボルｕ［ｋ］を計算するための整数処理ユニットを含むプロセッサであって、パリティシンボルは、-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) mod Mを含み、また、Ｍ≧２ｎ（ｋ＋１）（ｑ−１）＋１であり、乗算記号・および加算記号＋は、整数演算であり、ａ［０］，．．．，ａ［ｋ−１］は、要素ａ［ｉ］・ｄ・ｑｊｍｏｄＭがｉ∈｛０，．．．，ｋ−１｝，ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０について、相互に異なるように集合｛０，．．．，Ｍ−１｝内で選択した定数とする、該プロセッサと、
‐さらに、コードワードを送信または格納する前に、パリティシンボルｕ（ｋ）をコードワードｕに付加する手段と
を備えたことを特徴とする。
【０００６】
この符号（コード）は、一個以上のｑアレイシンボルの誤りを訂正することができ、整数演算（加算、乗算およびモジュロ演算）だけを使用する。このように、このコードは、従来の整数演算ハードウェア上で容易に実行することができる。ほんの少数の演算サイクルだけを必要とし、このことはこの符号（コード）生成を高速にする。
【０００７】
上述のような関係に類似した線形合同によって定義されるコードは、Ｒ.Ｒ.ヴァルシャモフ(R. R. Varshamov)氏の文献「A class of codes for asymmetric channels and a problem from the additive theory of numbers」IEEE Transactions on Information Theory, Vol. IT- 19, No. 1, January 1973、に記載されているヴァルシャモフ‐テネンゴルツ(Varshamov-Tenengolts)コード（1965）として文献において公知の点に留意する必要がある。このコードは、非対称の誤り（たとえば、「０」は「１」にマップされるかもしれないが、その逆は成り立たないような）を訂正するそれらの潜在的能力に関して研究がされてきた。レベンシュタイン(Levenshtein)氏が、これらのコードは挿入および削除を訂正するための特性をも有していると述べた点は更に注意される。しかしながら、これらのコードは、距離特性が劣るために、ｑアレイシンボル誤りの訂正用に考慮されなかった。請求項に記載の符号（コード）は、情報シンボルがモデュラスＭ（２ｗ≧Ｍ）で特定される範囲を超える場合がある点で、さらに従来とはかけはなれている。
【発明を実施するための最良の形態】
【０００８】
従属請求項２の手段によれば、テーブルが形成され、このテーブルは、受信ベクトルのｑアレイシンボル内における各単独の誤りのために、どのｑアレイシンボルが壊れ、どのようにすると訂正できるかを示す情報の検索を可能にする。このようなテーブルを使用することにより、実行を速く行うことができる。このテーブルは、低コストメモリ（例えばＲＯＭなど）に保存することができる。
【０００９】
従属請求項３の手段によって定義されるように、モデュラスＭは、好ましくは、許容範囲における最も大きい素数として選ばれる。これは、適切な定数を選択することを単純化する。
【００１０】
従属請求項４の手段によって定義されるように、ランダムに選択した値を反復的に選択し検証することによって、適切な定数を見つけることができる。
【００１１】
従属請求項５の手段に定義されるように、必要条件を満たす小さい定数を選択するために努力が払われる。小さい定数（例えば８ビット値）を用いて、単純なプロセッサ上の処理速度を増加させる。
【００１２】
これらおよび他の本発明の態様は、以下に記載する実施例より明らかであり、この実施例につき説明する。
【実施例】
【００１３】
図１は、本発明によるシステム１００の実施例のブロック図を示す。この実施例において、このシステムは、誤り訂正符号の中核となる演算（すなわち、コードワードの送信／格納前にパリティシンボルを演算し、および／または、受信／読み出したコードワード内の誤りを決定するためのシンドロームを計算する）を実行するプロセッサ１３０を含む。本発明による方法およびシステムは、これらの中核的な計算を、従来の整数処理ＣＰＵコア上で実行するように設計する。図１において、この種のコアを、Ｉ−ｐｒｏｃ１４０として示す。また、このシステムは、コードワード（パリティを含む）を出力し、および／または１個以上の誤りによって乱される可能性のあるコードワードを含むベクトルを受信するＩ／Ｏ手段１２０を有する。例えば、ローカルエリア・ネットワークもしくはワイドエリアのネットワークなどのような通信システムを通じて、コードワードを送信するとき、または、コードワードをメモリ／記憶装置に格納するときに、概して、誤り訂正を使用する。送信中、または、読み出し／書き込みのオペレーション中に、コードワードの１ビット以上が、壊れることがある。誤り訂正符合は、エラーが発生したことを検出し、また、１個以上のエラーを訂正することを支援する。Ｉ／Ｏ手段１２０それ自体は、送信またはメモリ／記憶装置のタイプに従う従来型である。
【００１４】
本発明によるシステムは、少なくとも１つのｑアレイシンボルを訂正するために設計されている（ｑは２のｒ乗（ｑ＝２ｒ）、ただしｒ≧１）。好ましい実施例において、システムは、メモリ１１０を含む。好ましくは、メモリは、情報が４個の個別レベル（ｑ＝４，ｒ＝２）を使用して情報を格納するＮＡＮＤ型とする。したがって、１個のメモリセルは、２ビットの情報を格納する。よって、このセル内の欠陥または誤りは、このようなセルに格納される情報全体、すなわちｑアレイシンボル全体に影響を及ぼし得る。
【００１５】
以下において、本発明による誤り訂正符号の原理を、実施例を交えて一般的用語で説明する。
【００１６】
図２は、本発明による処理ステップを示す。ステップ２１０において、保護すべき１個のコードワードｕを受信する。プロセッサ１３０は、例えばこのようなコードワードを、プログラム実行中に計算するか、または、（図示しない）送信源（ソース）から受け取る。図３は、コードワードｕ３００がｋ個の情報シンボル、すなわちｕ［０］，．．．，ｕ［ｋ−１］を含む（ただし、ｋ≧１）ことを示す。この情報シンボルは、番号３１０によって示す。各情報シンボルは、｛０，．．．，２ｗ−１｝の範囲の整数を表し、ここで、ｗ＝ｎ×ｒ（ただし、ｎ≧１）である。図３に示す実施例において、コードワードｕ３００は、それぞれ３２ビット情報（したがってｗ＝３２）を有する１６個の情報シンボルｕ［０］，．．．ｕ［１５］（したがって、ｋ＝１６）を含む。コードワードｕ３００の情報シンボルは、インデックスｉ∈｛０，．．．，ｋ−１｝で示す。この実施例において、ｑ＝４およびｒ＝２として、４アレイシンボルを１個のメモリセルに格納する。したがって、各情報シンボルは、ｗ／ｒ＝３２／２＝１６個のｑアレイシンボルを含む。１個の情報シンボルについて、１６個のｑアレイシンボルの各々を、図３において参照符号３１５で示す。情報シンボルｕ［ｉ］内のｑアレイシンボルを、インデックスｊによって示す。
【００１７】
ステップ２２０において、単独のパリティシンボルｕ［ｋ］を、情報シンボルを保護するために算出する。図３では、参照符号３１２を使用してパリティシンボルを示す。本発明によれば、パリティシンボルｕ［ｋ］は、次の項を含むものとする。すなわち、
-(a[0]・u[0]+a[1]・u[1]+...+ a[ｋk-1]・u[ｋk-1]) modM
ここで、乗算記号・および加算記号＋は、図１の装置１４０のような整数処理ユニットで実行可能な整数演算である。例えば、次式（１）となる。
【数１】
2008527890.tif 000003
【００１８】
本発明方法は、このように単独のパリティシンボルを付加することによって、ｋ個の情報シンボルｕ［０］，．．．，ｕ［ｋ−１］を保護する。係数ａ［０］，．．．，ａ［ｋ−１］は、集合｛０，．．．，Ｍ−１｝内に含まれる定数（ただし、Ｍ≧１）である。この定数は、以下に詳述するように適切な方法で選択する。パリティシンボルとして、
(a[0]・u[0]+a[1]・u[1]+...+ a[ｋ-1]・u[ｋ-1]) modMの項を使用することは、コードワードの点検／検査を行うシンドロームを同様に変更する限り、完全に等価であることは、当業者の能力の範囲内で理解できるであろう。
【００１９】
図３のステップ３２０は、パリティシンボル３１２を情報シンボルに付加することを示す。本明細書に記載する実施例においては、パリティシンボルを付加し、このパリティシンボルは、このように構成されたコードワードの最後のシンボルをなす。しかし、このことは重要なことではなく、当業者は容易に他の位置にパリティシンボルを挿入し、または、他の適切な方法でパリティシンボルの情報を情報シンボルに加えることができ、同様の方法でコードワードを検査／訂正するためのシンドロームを変更することができる。
【００２０】
図２のステップ２３０および図３のステップ３３０において、結合したコードワードを「伝送チャネル」に対して発する。上述のように、これは通信システムへの現実の送信であっても、または、メモリにおける格納／検索であってもよい。このことにより、情報保護ステップ、すなわち「センダ（送信側）」の役目を完了する。
【００２１】
図２Ｂおよび図３の残りの部分は、「レシーバ（受信側）」の処理、すなわち伝送チャネルで発生したかもしれない誤りを検出し、訂正するために使用されるステップを示す。受信されるコードワードを、ベクトルｘと称する。伝送チャネルで、誤りベクトルｅが送信されたコードワードｕに加わったと仮定する。エラーが発生しなかった場合、ｅは零成分のみを有する零ベクトルであると理解する。したがって、送信されたコードワードｕは、次のベクトルとして受信される。すなわち、
x=u+e=(u[0]+e[0],...,u[ｋ-1]+e[ｋ-1], u[ｋ]+e[ｋ])
ここで、「＋」は本来の整数加算を意味し、要素ｅ［ｉ］は整数（正，負または零）である。ｘの受信を、図２Ｂのステップ２５０および図３のブロック３３０と３４０との間の矢印の隣に示す。次のステップ（図２のステップ２６０、図３のステップ３４０）において、この受信したベクトルのシンドロームを算出する。シンドロームは、以下のように定義される。すなわち、
s(x) = (a[0]・x[0]+a[1]・x[1]+...+a[ｋ-1]・x[ｋ-1]+x[ｋ]) mod M
ｓ（‐）は整数について線形であるため、また、式（１）で与えられる任意のコードワードｕについてｓ（ｕ）＝０なので、次の関係が得られる。
s(x)=s(u)+s(e)=s(e)=(a[0]e[0]+...+a[ｋ-1]e[ｋ-1]+e[ｋ]) mod M
【００２２】
したがって、受信したベクトルｘのシンドロームｓ（ｘ）は情報に依存せず、それは、付加的誤りベクトルｅにのみ依存する。
【００２３】
本発明による方法およびシステムは、特に、ＮＡＮＤ型フラッシュメモリなどのチャネルに適しており、ｑアレイシンボルエラーを導入する。ｑアレイシンボルのうち１個のみがチャネルにおいて変更された場合を考慮する。このとき、ｅ［ｉ］≠０となるｉが集合｛０．．ｋ｝内にちょうど１個存在する。さらに、ｘ［ｉ］のｊ番目のｑアレイデジット（数値）がｕ［ｉ］のｊ番目のｑアレイデジット（数値）と異なる唯一のｊがある。１個のデジット（数値）は集合｛０．．ｑ−１｝内の数なので、これらのデジット（数値）の間の差異ｄは、
ｄ≠０として
−ｑ＜ｄ＜ｑ（差異が零であれば誤りではない）。このことは、ｅ［ｉ］のとりうる値が、｛ｄ・ｑｊ｜−ｑ＜ｄ＜ｑ，ｄ≠０｝の範囲内にあり得ることを意味する。このことは、いかなる単独のｑアレイシンボル誤りが、次の形式のシンドロームを生成することを意味する。すなわち、
【数２】
2008527890.tif 000004
それゆえ、これらすべてのシンドロームにおけるすべての要素が相互に異なる場合、誤りを復号化することが可能である。したがって、定数ａ［０］，．．．，ａ［ｋ−１］は、要素
ａ［ｉ］・ｄ・ｑｊｍｏｄＭが、ｉ∈｛０，．．．ｋ｝，ｊ∈｛０，．．．，ｎ−１｝，
−ｑ＜ｄ＜ｑ，ｄ≠０において相互に異なる値となるように選択する（ただし、ａ［ｋ］＝１）。
【００２４】
いかなる整数ｍｏｄＭも、集合｛０，．．．，Ｍ−１｝内にあるため、Ｍ個の異なる値のｍｏｄＭが存在する。
また、ｉ∈｛０，．．．ｋ｝，ｊ∈｛０，．．．，ｎ−１｝，−ｑ＜ｄ＜ｑ，ｄ≠０の組み合わせを選択する可能性は、２ｎ（ｋ＋１）（ｑ−１）個存在する。
これらの組み合わせと、誤りがないという付加的可能性とを区別できるようにするために、Ｍは少なくとも２ｎ（ｋ＋１）（ｑ−１）＋１でなければならない。好ましくは、Ｍは、２ｎ（ｋ＋１）（ｑ−１）＋１よりも、かなり大きいものを選択すべきである。適切な定数ａ［０］，．．．，ａ［ｋ−１］は、反復的に選択し、かつ選択した値をランダムに検証することにより発見することができ、そして、このことは、Ｍが大きければ大きいほど、より容易になる。
【００２５】
好適な実施例においては、ｓ（ｅ）と（ｉ，ｊ，ｄ）とを関連付けるテーブルを使用する。例えば、このテーブルは、ｓ（ｅ）のあり得る各値に対応した行を有することができる。この行は、第１フィールドにこの値を格納し、さらに、この行における３個の付加的フィールドに、ｉ，ｊおよびｄの値を格納する。テーブル内のルックアップ（検索）は、任意の適切な方法で行う。明らかに、テーブルは相当大きくなり得るため、実際には起こり得ない「ｓ（ｅ）」の値に対してはテーブルの行を設けないことが好ましい。したがって、無効な行を設けないようにするのが好ましい。結果として、ｓ（ｅ）の実際の値を行番号のインデックスとして使用することはできない。このような状況では、例えばハッシュ法を使用して、または二分探索法によって、効率的に行を見つける技法が、一般に知られている。望ましいと考えられる場合、テーブルは、｛０，．．，Ｍ−１｝の範囲全体のインデックスを付けて使用することができる。
【００２６】
このように、まず、受信したベクトルｘに対してシンドロームを算出する。シンドロームの結果がゼロの場合、誤りはなく、ベクトルｘは実際にコードワードｕである。パリティシンボルｕ［ｋ］を取り除き、ｘ［０］，．．．，ｘ［ｋ−１］＝ｕ［０］，．．．，ｕ［ｋ−１］を出力するだけで十分である。シンドロームの値が０でない場合は、誤りがある。好ましくは、あり得る各シンドロームの結果を、対応する（ｉ，ｊ，ｄ）のセットに関連付ける上述のテーブルＴを使用する。これを、図２Ｂのステップ２７０および図３のステップ３５０に示す。そして、これから、ｉ，ｊおよびｄの値を得る。この情報によって、ｉ番目の情報シンボルｘ［ｉ］におけるｊ番目のｑアレイシンボルを、ｄの値に基づいて修正する。上述のように、ｄは、伝送チャネルにおける誤りによって生じる差異である。ｄを識別したｑアレイシンボルから減算することによって、誤りを訂正する。他の方法、例えばｄを加算して誤りを訂正するように、システムを同様に定義することができることを理解されたい。
【００２７】
当業者は、また、同じ原理を２個以上のｑアレイシンボル誤りに適用できることは容易にわかるであろう。しかしながら、誤りの数とともに、シンドロームの値のテーブルは、指数関数的に大きくなる。したがって、このことは複数のｑアレイシンボル誤りへの実用化を制限する。
【００２８】
[実際の設計例]
本発明による方法およびシステムを、ＮＡＮＤ型のフラッシュメモリ用途にも適した実施例によって、さらに説明する。最近のメモリデバイスは、１６バイトのパリティによって保護される５１２バイトの情報からなるページで構成される。
【００２９】
メモリセルは、ｑ＝４レベルで使用される。誤り訂正方法を実行するために使用するプロセッサは、ｗ＝３２ビットアーキテクチャのＡＲＭ７２０Ｔタイプのプロセッサである。
【００３０】
第１の設計ステップにおいて、メモリページを８個の等しいＥＣＣブロックに分割し、各ブロックが２バイトのパリティで保護された６４バイトの情報を含むようにする。６４バイトは、それぞれｗ＝３２ビットのｋ＝１６ワードに等しい。この例では、最大で１個の４アレイシンボル誤りを訂正するために、コードを使用する。所定の分割によって、全体で訂正することができる誤りの数を増大する。
【００３１】
第２ステップにおいて、モデュラス（係数）をＭ＝６５５２１として選択し、これは、２１６（２パリティバイトの範囲）を超えない最大の素数である。一般に、モデュラスは素数である必要はないが、素数とすることで係数の設計を単純化することができる。
【００３２】
第３のステップにおいて、式（２）のシンドロームのあり得る値が、相互に異なっておりかつ０でないように、係数ａ［０］，．．．，ａ［１５］を、｛１．．Ｍ｝の中から選択する。好ましい実施例において、係数を、ランダム値を試用することによって選択する。この要求を満たす一組の値が見つかると、作業用誤り訂正コードが見つかったことになる。
【００３３】
好ましい実施例において、選択した整数プロセッサによって、比較的速く実行することができる定数を選択する。上述のＡＲＭプロセッサは、この定数が８ビット値であれば（８×３２ビットの乗算を行い）、この定数が３２ビット値である（１６×３２ビットの乗算を行う）場合に比較して、式（１）の乗算をより速く実行することができる。好ましくは、定数Ａの上限境界値からはじめることによって、迅速実行可能な定数を選択する。ここで、初期値はＡ＝Ｍである。限界値Ａについて、一組の定数が見つかると、妥当な回数（例えば１０４）のランダムな試行を行っても解が見つからなくなるまで、限界値Ａを低くする。
【００３４】
上記の技法を使用して、上述の例示システムについて１個の特別解は、次のようになる。すなわち、
a=(26,42,53,55,74,77,99,119,140,149,162,197,201,204,223,233; 1)
このようにして、ａ［０］＝２６，ａ［１］＝４２，等となる。この方法を使用すると、８ビットの係数が、非常に速い乗算を可能にする。
【００３５】
上述の例において、換算は、好ましくはｍｏｄ６５５２１（２１６を超えない最大の素数）で行う。この換算は、また、従来の整数プロセッサ上のソフトウェアで、高速に実行することができる。Ｍ＝２１６−１５＝６５５２１となることが観察される。s（ｘ）の式は、モジュロＭによる換算の前に、範囲｛０，．．，１６×２５５×（２３２−１）＋Ｍ−１｝値を生成し、この値は、｛０，．．，２４４−１｝に含まれる。それゆえ、ｓ（ｘ）は、以下として書くことができる。すなわち、
s(x)=s0+s1 216+s2 232、ここで、s0,s1,s2は{0，..，216-1}
そして、この表現のモジュロＭの換算を、桁送りと加算とを使用して計算する。この記載において、表記法（ｘ＜＜ｋ）は、左にｋビットシフトしたｘを意味し、すなわち、
（ｘ＜＜ｋ）＝ｘ×２κであり、（ｘ＞＞ｋ）は）右にｋビットシフトしたｘを意味する。
【００３６】
次に、換算は、以下の表１の通りに計算することができる。
【表１】
2008527890.tif 000005
これは、全体で４回のシフト演算と、多くとも８回の加算と１回の比較を伴うIF演算を要する。
【００３７】
本発明は、本発明を実施するのに適合したコンピュータプログラム、特にキャリア上のまたはキャリア内のコンピュータプログラムにも及ぶことはいうまでもない。このプログラムは、ソースコード、オブジェクトコード、部分的にコンパイルしたような形式のソースコードとオブジェクトコードの中間物、あるいは、本発明による方法の実現に使用するに適した任意の他の形式であっても良い。キャリアは、プログラムを担持することができるいかなる実体または装置であっても良い。例えば、キャリアには、ＣＤ‐ＲＯＭもしくは半導体ＲＯＭのようなＲＯＭ、またはフロッピー・ディスク（登録商標）もしくはハード・ディスクのような磁気記憶媒体のような記憶媒体も含まれる。さらに、キャリアは、電気的もしくは光学的信号などの送信可能なキャリアであってもよく、これら信号は、電気もしくは光学ケーブルにより、または無線もしくは他の方法で伝送することができる。プログラムがこの種の信号で具現化されるときに、キャリアをそのようなケーブルまたは他の装置もしくは手段によって構成することができる。代案として、キャリアは、関連する方法を実行するのに適合する、または、関連する方法の実施に使用するための、プログラムを組み込んだ集積回路であってもよい。
【００３８】
上述の実施例は、本発明を制限するものではなく、当業者であれば、添付した特許請求の範囲を逸脱することなく、多くの他の実施例を設計できることに留意されたい。請求項において、括弧内のいかなる参照符号も、請求項を制限するものとして解釈すべきではない。動詞「備える」およびその活用形の使用は、請求項内に記載された以外の要素またはステップの存在を除外するものではない。要素の前の冠詞「ａ」または「ａｎ」は、そのような要素が複数存在することを除外しない。本発明は、いくつかの異なった要素から成るハードウェアによって、そして、最適にプログラムされたコンピュータによって実装することができる。いくつかの手段を列挙している装置の請求項において、これらの手段のいくつかは、ハードウェアの単一の同じ部分によって具現化することができる。特定の手段が相互に異なる従属クレームにおいて再引用されるという単なる事実は、これらの手段の組み合わせが有効に使われることができないことを示すものではない。
【図面の簡単な説明】
【００３９】
【図１】本発明による実施例のブロック図である。
【図２】本発明による処理ステップを説明する説明図である。
【図３】データの構造の詳細を示す説明図である。
【図１】
2008527890.tif 000006
【図２Ａ】
2008527890.tif 000007
【図２Ｂ】
2008527890.tif 000008
【図３】
2008527890.tif 000009
【国際調査報告】
2008527890.tif 000010
2008527890.tif 000011