(57)【要約】【課題】  縮退故障を有するメモリセルに対応するためのデータ符号化及び復号化を提供する。【解決手段】  データ記憶システムは、メモリセルを含むメモリ回路と、メモリセル内に記憶するために与えられるデータビットを受け取るように動作可能な制御回路とを含む。制御回路は、第１のマトリックスを受け取るように動作可能である。第１のマトリックスの各行は、データビットの固有の１つに対応する。制御回路は、縮退故障を有するメモリセルの部分集合内に記憶するために与えられる、データビットに対応する第１のマトリックスの行のみを有する第２のマトリックスを生成するように動作可能である。制御回路は、第２のマトリックスの線形独立の列を有する第３のマトリックスを生成するように動作可能である。制御回路は、第３のマトリックスを用いて、符号化されたデータビット及び冗長ビットを生成する目的で、データビットを符号化するように動作可能である。【選択図】図１
2014078945.tif 000002
【特許請求の範囲】
【請求項１】
データ記憶システムであって、
メモリセルを含むメモリ回路と、
前記メモリセル内に記憶するために与えられるデータビットを受け取るように動作可能な制御回路と、
を含み、
前記制御回路が、第１のマトリックスを受け取るように動作可能であり、前記第１のマトリックスの各行が前記データビットの固有の１つに対応し、前記制御回路が、縮退故障を有する前記メモリセルの部分集合内に記憶するために与えられる、前記データビットに対応する前記第１のマトリックスの行のみを有する第２のマトリックスを生成するように動作可能であり、前記制御回路が、前記第２のマトリックスの線形独立の列を有する第３のマトリックスを生成するように動作可能であり、かつ
前記制御回路が、前記第３のマトリックスを用いて、符号化されたデータビット及び冗長ビットを生成する目的で前記データビットを符号化するように動作可能である、
データ記憶システム。
【請求項２】
前記制御回路が、縮退故障を有する前記メモリセルのうちの対応する１つの中に記憶するために与えられる、前記データビットの各々を、前記縮退故障の値と比較するように動作可能であり、かつ前記制御回路が、前記メモリセルのうちの対応する１つの、前記縮退故障の値と異なる値を有する前記データビットの各々を識別し、前記メモリセルのうちの対応する１つの、前記縮退故障の値と同じデジタル値を有する前記データビットの各々を識別する、第１のベクトルを生成するように動作可能である、
請求項１に記載のデータ記憶システム。
【請求項３】
前記制御回路が、第４のマトリックスを生成する目的で前記第３のマトリックスを反転させるように動作可能であり、前記制御回路が、第２のベクトルを生成する目的で、前記第１のベクトルと前記第４のマトリックスとの乗算をするように動作可能であり、前記メモリ回路が、前記メモリセル内に前記符号化されたデータビットを記憶するように動作可能である、
請求項２に記載のデータ記憶システム。
【請求項４】
前記制御回路が、前記第２のベクトルと、前記第３のマトリックス内にある前記第２のマトリックスの線形独立である列とを、前記冗長ビットに示させるように動作可能である、
請求項３に記載のデータ記憶システム。
【請求項５】
前記第３のマトリックス内にある前記第２のマトリックスの線形独立である列が列番を有し、前記制御回路が、前記第３のマトリックス内にある前記第２のマトリックスの線形独立である列と同じ列番を有する、前記第１のマトリックスからの列のみを有する、第５のマトリックスを生成するように動作可能である、
請求項３に記載のデータ記憶システム。
【請求項６】
前記制御回路が、第３のベクトルを生成するために、前記第２のベクトルと前記第５のマトリックスとの乗算をするように動作可能であり、かつ前記制御回路が、前記符号化されたデータビットを生成する目的で前記データビットに前記第３のベクトルを適用するように動作可能である、
請求項５に記載のデータ記憶システム。
【請求項７】
前記メモリ回路が、縮退故障を有する数ｓのメモリセルを含み、前記第１のマトリックスの数ｓの行の任意の部分集合が線形独立である、
請求項１に記載のデータ記憶システム。
【請求項８】
前記第１のマトリックスが、ＢＣＨ符号のパリティ検査行列を転置することによって生成される、
請求項１に記載のデータ記憶システム。
【請求項９】
データ記憶システムであって、
メモリセルを含むメモリ回路と、
前記メモリセルから読み取られる符号化されたデータビットを受け取るように動作可能である制御回路と、
を含み、
前記制御回路が、冗長ビットを受け取るように動作可能であり、
前記制御回路が、第１のマトリックスを受け取るように動作可能であり、
前記制御回路が、前記冗長ビットの第１の部分集合に基づき選ばれた前記第１のマトリックスからの列の部分集合を有する、第２のマトリックスを生成するように動作可能であり、
前記制御回路が、前記冗長ビットの第２の部分集合に基づき、第１のベクトルを生成するように動作可能であり、
前記制御回路が、前記第１のベクトル及び前記第２のマトリックスに基づき、第２のベクトルを生成するように動作可能であり、かつ
前記制御回路が、データビットを生成するために前記第２のベクトルを符号化されたデータビットに適用するように動作可能である、
データ記憶システム。
【請求項１０】
前記制御回路が、前記第２のマトリックスと前記第１のベクトルとを乗算することにより、前記第２のベクトルを生成するように動作可能である、
請求項９に記載のデータ記憶システム。
【請求項１１】
前記制御回路が、前記データビットの対応する１つを生成するために、２を法とする加算を用いて前記第２のベクトルの対応する値に前記符号化されたデータビットの各々を加えるように動作可能であり、前記第１のマトリックスがＢＣＨ符号のパリティ検査行列を転置することにより生成される、
請求項１０に記載のデータ記憶システム。
【請求項１２】
前記制御回路及び前記メモリ回路が１つの集積回路内にある、
請求項９に記載のデータ記憶システム。
【請求項１３】
前記制御回路が第１の集積回路内にあり、前記メモリ回路が第２の集積回路内にある、
請求項９に記載のデータ記憶システム。
【請求項１４】
データ記憶システム用の方法であって、
メモリ回路のメモリセル内に記憶するために与えられるデータビットを受け取るステップと、
前記第１のマトリックスの各行が、前記データビットの異なる１つ１つに対応する第１のマトリックスを受け取るステップと、
制御回路を用いて、縮退故障を有するメモリセルの部分集合内に記憶するために与えられる前記データビットに対応する、前記第１のマトリックスの行のみを有する第２のマトリックスを生成するステップと、
前記制御回路を用いて、前記第２のマトリックスの線形独立である列を有する、第３のマトリックスを生成するステップと、
前記制御回路を用いて、前記第３のマトリックスに基づき符号化されたデータビット及び冗長ビットを生成するために、前記データビットを符号化するステップと、
を含む方法。
【請求項１５】
前記制御回路を用いて、縮退故障を有する前記メモリセルのうちの対応する１つの中に記憶するために与えられる前記データビットを、前記縮退故障の値と比較するステップと、
前記制御回路を用いて、前記メモリセルのうちの対応する１つの、前記縮退故障の値と異なる値を有する前記データビットの各々を識別し、かつ前記メモリセルのうちの対応する１つの、前記縮退故障の値と同じ値を有する前記データビットの各々を識別する、第１のベクトルを生成するステップと、
をさらに含む、
請求項１４に記載の方法。
【請求項１６】
前記制御回路を用いて第４のマトリックスを生成するために、前記第３のマトリックスを反転させるステップと、
前記制御回路を用いて第２のベクトルを生成するために、前記第１のベクトルと、前記第４のマトリックスとを乗算するステップと、
をさらに含む、
請求項１５に記載の方法。
【請求項１７】
前記制御回路を用いて、前記第３のマトリックスに基づき、符号化されたデータビット及び冗長ビット生成するために、前記データビットを符号化するステップが、前記第２のベクトル、及び前記第３のマトリックス内にある前記第２のマトリックスの、前記線形独立である列を、前記冗長ビットに示させるステップをさらに含む、
請求項１６に記載の方法。
【請求項１８】
前記第３のマトリックス内にある前記第２のマトリックスの、前記線形独立である列が列番を有し、前記方法が、
前記制御回路を用いて、前記第３のマトリックス内にある前記第２のマトリックスの、前記線形独立の列と同じ列番を有する、前記第１のマトリックスからの列の部分集合を有する第５のマトリックスを生成するステップ、
をさらに含む、
請求項１６に記載の方法。
【請求項１９】
前記制御回路を用いて、第３のベクトルを生成するために、前記第２のベクトルと前記第５のマトリックスとを乗算することをさらに含み、かつ
前記制御回路を用いて、前記第３のマトリックスに基づき符号化されたデータビット及び冗長ビットを生成するために、前記データビットを符号化することが、前記符号化されたデータビットを生成するために、前記第３のベクトルを前記データビットに適用する、
請求項１８に記載のデータ記憶システム。
【請求項２０】
データ記憶システム用の方法であって、
メモリ回路のメモリセルから読み取られる、符号化されたデータビットを受け取るステップと、
冗長ビットを受け取るステップと、
第１のマトリックスを受け取るステップと、
制御回路を用いて、前記冗長ビットの第１の部分集合に基づいて選ばれた、前記第１のマトリックスからの列の部分集合を有する、第２のマトリックスを生成するステップと、
前記制御回路を用いて、前記冗長ビットの第２の部分集合に基づいて第１のベクトルを生成するステップと、
前記制御回路を用いて、前記第１のベクトル及び前記第２のマトリックスに基づき第２のベクトルを生成するステップと、
前記制御回路を用いて、データビットを生成するために、前記第２のベクトルを前記符号化されたデータビットに適用するステップと、
を含む方法。
【請求項２１】
前記第１のベクトル及び前記第２のマトリックスに基づき第２のベクトルを生成するステップが、前記第２のマトリックスと前記第１のベクトルとを乗算することにより、前記第２のベクトルを生成するステップをさらに含む、
請求項２０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示はデータ記憶システムに関し、とりわけ、縮退故障を有するメモリセルに対応するためのデータ符号化及び復号化のための技術に関する。
【背景技術】
【０００２】
多くのデータ通信システムは、データ内のエラーを検出及び修正するために、エラー修正符号器及び復号器を用いる。データ通信システムは、例えばおよそ１×１０−４の割合で発生するランダムエラーを修正する。およそ１×１０−４のエラー率に対して保護するために、エラー修正符号器は、その入力ビットよりも約１０％大きいビットを有する、符号化されたビットを生成する。
【０００３】
相変化メモリ（ＰＣＭ）は、不揮発性メモリの部類である。ＰＣＭ素子は、伝統的な不揮発性フラッシュメモリよりも多くの利点を有する。しかしながら、ＰＣＭ素子は劣化により引き起こされる多数のエラーを発生し得る。例えば、１つのＰＣＭ素子は１×１０−２以上の割合でエラーを発生し得る。
【０００４】
耐久の限界においては、不揮発性メモリ素子におけるエラー率は劣化によって支配される。劣化により生じるエラーは、データ通信システムにおいて一般的なランダムエラーとは異なる統計値を有する、縮退故障を含む。
【発明の概要】
【課題を解決するための手段】
【０００５】
幾つかの実施形態によれば、データ記憶システムはメモリセル及び制御回路を有するメモリ回路を含む。制御回路はメモリセル内に記憶するために与えられるデータビットを受け取るように動作可能である。制御回路は第１のマトリックスを受け取るように動作可能である。第１のマトリックスの各行は、データビットの固有の１つに対応する。制御回路は、縮退故障を有するメモリセルの部分集合内に記憶するために与えられるデータビットに対応する、第１のマトリックスの行のみを有する第２のマトリックスを生成するように動作可能である。制御回路は、第２のマトリックスの線形独立の列を有する、第３のマトリックスを生成するように動作可能である。制御回路は、第３のマトリックスを用いて符号化されたデータビット及び冗長ビットを生成する目的でデータビットを符号化するように動作可能である。
【０００６】
幾つかの実施形態によれば、制御回路はメモリセルから読み取られる符号化されたデータビットを受け取るように動作可能であり、かつ制御回路は冗長ビットを受け取るように動作可能である。制御回路は、第１のマトリックスを受け取るように動作可能である。制御回路は、冗長ビットの第１の部分集合に基づいて選ばれる、第１のマトリックスからの列の部分集合を有する第２のマトリックスを生成するように動作可能である。制御回路は、冗長ビットの第２の部分集合に基づき第１のベクトルを生成するように動作可能である。制御回路は、第１のベクトルと第２のマトリックスに基づき第２のベクトルを生成するように動作可能である。制御回路は、データビットを生成するため、第２のベクトルを符号化されたデータビットに適用するように動作可能である。
【０００７】
本発明の様々な目的、特徴、及び利点は、以下の詳細記述及び添付図を考慮した上で明らかになるであろう。
【図面の簡単な説明】
【０００８】
【図１】本発明の一実施形態による、データ記憶システムの一例を説明している。
【図２】本発明の一実施形態による、縮退故障を有するメモリセルに対応する目的で符号化されたデータビット及び冗長ビットを生成するための、データビットを符号化する操作の例を説明するフローチャートである。
【図３】本発明の一実施形態による、縮退故障を有するメモリセルに対応する目的で符号化されたデータビット及び冗長ビットを生成するための、データビットを符号化するより詳細な操作の例を説明するフローチャートである。
【図４】本発明の一実施形態による、冗長ビットを用いてデータビットを再生する目的で、図２及び／又は図３の操作により生成される、符号化されたデータビットを復号するための操作例を説明するフローチャートである。
【図５Ａ】本発明の実施形態による、例示的符号化マトリックスを用いて、図３の符号化操作が如何にしてデータビットの一つの例示的集合に対して加えられ得るかの例を説明している。
【図５Ｂ】本発明の実施形態による、例示的符号化マトリックスを用いて、図３の符号化操作が如何にしてデータビットの一つの例示的集合に対して加えられ得るかの例を説明している。
【図５Ｃ】本発明の実施形態による、例示的符号化マトリックスを用いて、図３の符号化操作が如何にしてデータビットの一つの例示的集合に対して加えられ得るかの例を説明している。
【図５Ｄ】本発明の実施形態による、例示的符号化マトリックスを用いて、図３の符号化操作が如何にしてデータビットの一つの例示的集合に対して加えられ得るかの例を説明している。
【図５Ｅ】本発明の実施形態による、例示的符号化マトリックスを用いて、図３の符号化操作が如何にしてデータビットの一つの例示的集合に対して加えられ得るかの例を説明している。
【発明を実施するための形態】
【０００９】
ここに記述されている幾つかの実施形態によれば、符号化されたデータビット及び冗長ビットを生成するため、符号器は入力データビットを符号化する。符号器によって生成される符号化されたデータビットは、メモリ回路のメモリセル内に記憶される。符号化されたデータビットは、縮退故障を有するメモリ回路内のメモリセルに対応する。メモリ回路は例えば、縮退故障を有する（例えば、カルコゲナイド・ガラスを用いる）相変化メモリ回路、又は別のタイプのメモリ回路であり得る。
【００１０】
縮退故障を有するメモリセルは、単一のデジタル値のみを記憶できるメモリセルである。１である縮退故障値を有するメモリセルは、高いデジタル論理値のみを記憶でき、０である縮退故障値を有するメモリセルは、低いデジタル論理値のみを記憶できる。従って、１である縮退故障値（すなわち、１縮退故障）を有するメモリセルからは、高いデジタル論理値のみ読み取ることができ、０である縮退故障値（すなわち、０縮退故障）を有するメモリセルからは、低いデジタル論理値のみ読み取ることができる。縮退故障を有するメモリセルは、一般に時間と共に安定な縮退故障値を有する。
【００１１】
メモリ回路内の幾つかのメモリセルが縮退故障を有する場合、縮退故障のデジタル値及び、縮退故障を有するメモリセルのアドレスは、符号化プロセスの前に決定され、符号器に提供される。符号器は、縮退故障のデジタル値とアドレスを用いて、符号化されたデータビット及び冗長ビットを生成する。符号化されたデータビットは、メモリ回路のメモリセル内に記憶される。冗長ビットは、符号化されたデータビットと同じメモリ回路内又は別のメモリ回路内に記憶され得る。
【００１２】
それに続いて、符号化されたデータビット及び冗長ビットはメモリから読み取られ、復号器に提供される。復号器はデータビットを再生するために、冗長ビットを用いて符号化されたデータビットを復号する。復号器によって再生されたデータビットは、メモリ回路内における既知の縮退故障によって引き起こされたエラーを含まない。
【００１３】
ここに記述されている技術は、複数レベルのメモリセルに直接適用可能である。複数レベルのメモリセルは、メモリセル当たり１ビットよりも多いビットを記憶できる。例えば、メモリが２ビットを保持し、それが縮退された場合、それら２ビットの値は固定され、それらは２つの別々の縮退故障位置として扱うことができる。縮退故障のうちの１つの位置が既知であるため、もう１つの縮退故障の位置もまた知られる。結果として、同じ縮退故障エラー率に対して、単一レベルのメモリセルに対して生成される冗長ビットよりも少ない冗長ビットが、複数レベルのメモリセルに対して生成され得る。冗長ビットの数は、例えばメモリセル当たりのビット数に等しい係数分だけ少なくなり得る。
【００１４】
図１は本発明の実施形態による、データ記憶システム１００の一例を説明している。データ記憶システム１００は、制御回路１０１、メモリ回路１０２、及びメモリ回路１０３を含む。制御回路１０１は、例えば、メモリ回路１０２〜１０３内に記憶するためのデータビットを符号化及び／又は復号する、メモリ制御回路、プロセッサ回路、又は任意の別のタイプの制御回路であってもよい。制御回路１０１は、符号化されたデータビットをメモリ回路１０２〜１０３に提供し、そこから符号化されたデータビットを受け取る。符号化されたデータビットは、メモリ回路１０２〜１０３の一方又は両方の中に記憶される。冗長ビットは、メモリ回路１０２〜１０３の一方又は両方の中に記憶され得る。符号化されたデータビット及び冗長ビットは、１つ以上のオンチップ・バス又は外部バスを通じて、或いは別のタイプの信号線を介して制御回路１０１とメモリ回路１０２〜１０３との間で伝送される。制御回路１０１、メモリ回路１０２、及びメモリ回路１０３は同一の集積回路内又は別々の集積回路内にあってもよい。従ってシステム１００は、回路１０１〜１０３を含む単一の集積回路素子であり得る。代わりに、システム１００は３つの別個の集積回路素子１０１〜１０３を含み得る。
【００１５】
図２は本発明の一実施形態による、縮退故障を有するメモリ回路内のメモリセルに対応するための符号化されたデータビット及び冗長ビットを生成する目的の、データビットを符号化する操作の例を説明するフローチャートである。メモリ回路内のメモリセルの各々は、少なくとも１つのデジタル値を記憶する。符号化されたデータビットはメモリ回路におけるメモリセル内に記憶される。メモリセルの１つ以上は縮退故障を有する。縮退故障を有するメモリセルのアドレス、及び縮退故障のデジタル値は、図２の操作を行う前に知られ、符号器に提供される。例えば、繰り返しの読み取り及び書き込み操作が、縮退故障の挙動と一致するエラーをどのメモリセルが表わすかを決定するために行われ得る。図２の操作により生成される符号化されたデータビットは、元のデータビットの代わりにメモリセル内に記憶される。図２の操作は、例えば制御回路１０１内において符号器によって行われ得る。
【００１６】
最初に、符号器はメモリ回路のメモリセル内に記憶するために与えられるデータビットを受け取る。データビットの各々は、メモリ回路の対応するメモリセル内に記憶するために与えられる。データビットの１つ以上は、既知の縮退故障を有する、対応するメモリセル内に記憶するために与えられる。
【００１７】
操作２０１において、符号器は第１のマトリックスを受け取る。第１のマトリックスの各行はデータビットのうちの固有の１つに対応する。操作２０２において、符号器は、縮退故障を有するメモリセル内に記憶するために与えられるデータビットに対応する、第１のマトリックスの行のみを有する第２のマトリックスを生成する。操作２０３において、符号器は第２のマトリックスの線形独立である複数の列を有する、第３のマトリックスを生成する。操作２０４において、符号器は符号化されたデータビット及び冗長ビットを生成するために、第３のマトリックスを用いてデータビットを符号化する。
【００１８】
それらの対応する縮退故障に適合しないデータビットのデジタル値は、符号化されたデータビットの対応するものを生成するために反転させられる。それらの対応する縮退故障に適合するデータビットのデジタル値は、符号化されたデータビットの対応するものを生成するためには反転させられない。様々な実施形態によれば、冗長ビットは以下に述べるように、インデックス内にインデックス・ビットを含み得る。
【００１９】
それに続いて、符号化されたデータビットはメモリ回路内における、それらの対応するメモリセル内に記憶される。冗長ビットもまたメモリ内に記憶される。符号化されたデータビット及び冗長ビットは、同じメモリ回路内か、異なるメモリ回路内に記憶され得る。例えば、符号化されたデータビットはメモリ回路１０２内に記憶され、冗長ビットはメモリ回路１０３内に記憶され得る。
【００２０】
図３は本発明の一実施形態による、縮退故障を有するメモリセルに対応するための符号化されたデータビット及び冗長ビットを生成する目的の、データビットを符号化するより詳細な操作の例を説明するフローチャートである。符号化されたデータビットは、メモリ回路のメモリセル内に記憶される。メモリセルの１つ以上は縮退故障を有する。縮退故障を有するメモリセルのアドレス、及び縮退故障のデジタル値は、図３に示される操作を行う前に知られ、符号器に提供される。図３の操作により生成される符号化されたデータビットは、入力データビットの代わりにメモリセル内に記憶される。図３の操作は、例えば制御回路１０１によって行われ得る。
【００２１】
最初に、データビットはメモリ回路のメモリセル内に記憶するために与えられる。データビットの各々は、メモリ回路の対応するメモリセル内に記憶するために与えられる。データビットの部分集合は、既知の縮退故障を有する対応するメモリセル内に記憶するために与えられる。部分集合は１つ以上のデータビットを含み得る。
【００２２】
データビットを符号化するプロセスの前に、データビットの各々に対して異なる行を有するマトリックスＭが生成される。マトリックスＭの各行は、データビットのうちの固有の１つに対応する。数ｓの縮退故障を有するメモリセル内に記憶するために与えられる、データビットの数ｋに対して、マトリックスＭは数ｋの行を有し、かつマトリックスＭの数ｓの行の任意の部分集合は線形独立であり、ここでｓは正の整数ｋよりも小さい正の整数である。マトリックスＭは、数ｋのメモリセルの中に記憶される符号化されたデータビットを生成するように、データビットを符号化するために用いることができ、ここで数ｓの縮退故障はメモリセル内の任意の位置にある。
【００２３】
一例として、マトリックスＭはパリティ検査符号のようなブロック符号を用いて生成され得る。より具体的な例によれば、マトリックスＭはＢＣＨ符号のパリティ検査行列の転置を行なうことにより生成され、ここでＢＣＨはＢｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍに該当する。数ｓの縮退故障を有するメモリセル内に記憶するために与えられる数ｋのデータビット（ここでｓ＜ｋ）に対して、次のようにｋに等しいブロックの大きさを有するＢＣＨ符号が生成され得る。ｍ＞２、かつｔ＜２ｍ−１と仮定すると、ＢＣＨ符号はブロックの長さがｎ＝２ｍ−１であるように作ることができ、パリティ検査ビットの数はｍ×ｔ以下であり、最小の距離は少なくとも２ｔ＋１であり、それはまたパリティ検査行列の任意の２ｔ列が線形独立であることを意味する。従って、ＢＣＨ符号はブロックの長さｋ＝２ｌｏｇ２（ｋ＋１）−１（それゆえｍ＝ｌｏｇ２（ｋ＋１））、及び最小距離ｓ＋１（それゆえ２ｔ＋１＝ｓ＋１、従ってｔ＝ｓ／２）と共に生成される。パラメータｎ＝ｋ及びｔ＝ｓ／２を伴うＢＣＨ符号の、結果的に生じるパリティ検査行列Ｍｐは、２ｔ＝ｓ列の任意の部分集合が線形独立であるという特性と共に、多くてもｍ×ｔ＝（ｓ／２）ｌｏｇ２（ｋ＋１）行及び数ｋの列を有する。簡単化のために、ｌｏｇ２ｋがｌｏｇ２（ｋ＋１）の代わりに用いられている。パリティ検査行列Ｍｐの転置はマトリックスＭである。従って、この例において、マトリックスＭはパリティ検査行列Ｍｐの転置である。上述のパリティ検査ビットの数は、パリティ検査行列Ｍｐの行の数に相当し、従って転置行列Ｍにおける列の数となる。
【００２４】
図３は操作３０１〜３０９を説明している。操作３０１において、符号器は、マトリックスＭｓを生成するために、縮退故障を有するメモリセル内に記憶するために与えられるデータビットに対応する、マトリックスＭの数ｓの行を選択する。操作３０１において用いられるマトリックスＭは、上述のようなＢＣＨ符号のパリティ検査行列から生成されるマトリックスか、又はマトリックスＭのｓ個の行のいずれも線形独立であることを確実にする、任意の方法により生成されるマトリックスである。縮退故障を有するメモリセル内に記憶するために与えられるデータビットのうちの１つに対応する、マトリックスＭの各行は、マトリックスＭｓの行として含まれる。既知の縮退故障を有さないメモリセル内に記憶するために与えられるデータビットに対応する、マトリックスＭの行は、マトリックスＭｓに含まれない。従って、ＢＣＨ符号が用いられる場合、マトリックスＭｓは数ｓの行と、数（ｓｌｏｇ２（ｋ＋１））／２の列を有する。ｓ行のマトリックスＭｓは構造により線形独立であると保証されているため、マトリックスＭｓは最大階数を有する。
【００２５】
操作３０２において、符号器は、完全に反転可能な正方行列Ｍ’ｓを生成するために、線形独立であるマトリックスＭｓの数ｓの列を選択する。マトリックスＭｓの各列は固有の列番により識別される。正方行列Ｍ’ｓを生成するために操作３０２で選択されるマトリックスＭｓの数ｓの列の列番は、列番ｂ１，ｂ２，．．．ｂｓと呼ばれる。符号器は、マトリックスＭ’ｓが列番ｂ１，ｂ２，．．．ｂｓによって示されるマトリックスＭｓの数ｓの列のみを有するようにさせる。操作３０２において生成される正方行列Ｍ’ｓは、数ｓの行と数ｓの列を有する。また、マトリックスＭ’ｓは線形独立の列を伴う最大階数を有し、それゆえ、マトリックスＭ’ｓは完全に反転可能である。一つの実施形態において、符号器は、正方行列Ｍ’ｓを生成するためにマトリックスＭｓの低減された行の階段形を用いる。Ｍｓを行の階段形へと転換することは、行操作のシーケンスを用いることにより行われる。
【００２６】
データビットの部分集合は、既知の縮退故障を有する、対応するメモリセル内に記憶するために与えられる。符号器は、部分集合内のどのデータビットが、それらの対応する縮退故障と同じデジタル値を有し、部分集合内のどのデータビットが、それらの対応する縮退故障と異なるデジタル値を有するかを決定するために、データビットの部分集合を、それらの対応する縮退故障のデジタル値と比較する。図３の操作３０３において、符号器はそれらの対応する縮退故障と同じデジタル値を有する部分集合内のデータビットと、それらの対応する縮退故障と異なるデジタル値を有する部分集合内のデータビットとを識別する、ベクトルＵを生成する。ベクトルＵは、数ｓの値を有する１×ｓのベクトルである。ベクトルＵは、ｉ番目の縮退故障がその対応するデータビットのデジタル値に適合する場合に、そのｉ番目の位置において０を有し、ｉ番目の縮退故障がその対応するデータビットのデジタル値に適合しない場合に、そのｉ番目の位置において１を有する。
【００２７】
操作３０４において、符号器は方程式Ｍ’ｓ×Ｖ＝Ｕを解くことによりベクトルＶを生成する。この方程式は、マトリックスＭ’ｓが完全に反転可能であるため解を有する。符号器はマトリックスＭ’ｓを反転させ、次にベクトルＶを生成するために、操作３０３で生成されたベクトルＵと、マトリックスＭ’ｓの反転との乗算をする。ベクトルＶは数ｓの値を有するｓ×１のベクトルである。
【００２８】
操作３０５において、符号器はベクトルＶと、マトリックスＭ’ｓを生成するために操作３０２において選ばれたマトリックスＭｓの列とを示す、インデックス・ビットを生成する。インデックス・ビットは冗長ビットである。インデックス・ビットは、操作３０８において生成される符号化されたデータビットと関連するインデックスとして提供される。インデックス・ビットは、データビットを再生するために、符号化されたデータビットを復号するための復号器によって使用される。
【００２９】
操作３０５の一実施形態において、符号器は、マトリックスＭ’ｓを生成するために操作３０２において選択された、マトリックスＭｓの数ｓの列番ｂ１，ｂ２，．．．ｂｓの各々を識別するため、固有の２進数を生成する。これらの２進数は、操作３０５において生成されたインデックス・ビットの第１の部分集合として提供される。従って、この実施形態において、インデックス・ビットの第１の部分集合は、マトリックスＭ’ｓを生成するために操作３０２において選択された、マトリックスＭｓの列番ｂ１，ｂ２，．．．ｂｓの各々を識別する。マトリックスＭ’ｓを生成するために用いられた、マトリックスＭｓの列番ｂ１，ｂ２，．．．ｂｓを識別する２進数を示すために用いられるインデックス・ビットの数は、方程式（１）において以下で表わされる。
【数１】
2014078945.tif 000003
【００３０】
方程式（１）は、（ｓｌｏｇ２ｋ）／２＜ｋである限り、ｋ個のビット位置の中から数ｓの縮退故障の正確なビット位置を記録するインデックスよりも小さい、インデックス・ビットに等しい。
【００３１】
操作３０５において、符号器はベクトルＶの値を示す数ｓのインデックス・ビットもまた生成する。ベクトルＶの値を示す数ｓのインデックス・ビットは、操作３０５において生成されたインデックス・ビットの第２の部分集合である。操作３０５において生成されたインデックス・ビットの総数は、方程式（２）において以下で表わされる。
インデックス・ビットの総数＝２ｓ＋ｓｌｏｇ２ｌｏｇ２ｋ  （２）
【００３２】
操作３０５の別の実施形態によれば、符号器は、マトリックスＭ’ｓを生成するために操作３０２において選ばれなかったマトリックスＭｓの（（ｓｌｏｇ２ｋ）／２−ｓ）の列番の各々を識別するために、固有の２進数を生成する。これらの２進数は、操作３０５において生成されたインデックス・ビットの第１の部分集合として提供される。この実施形態において、インデックス・ビットの第１の部分集合は、操作３０２においてマトリックスＭ’ｓを生成するために選ばれなかったマトリックスＭｓの列番の各々を識別する。復号器は、マトリックスＭ’ｓを生成するために選ばれなかったマトリックスＭｓの列番を示すインデックス内の２進数に基づいて、マトリックスＭ’ｓを生成するために選ばれたマトリックスＭｓの列を推測する。この実施形態において、符号器は、操作３０５におけるベクトルＶの値を示す数ｓのインデックス・ビットもまた生成する。
【００３３】
部分集合内のデータビットが、それらの対応する縮退故障のデジタル値に適合するか、又は適合しないかに対して、インデックス・ビット内のベクトルＶのみが依存する。残りのインデックス・ビットは、対応するメモリセル内の縮退故障の位置のみに依存する。同じメモリセルに対して異なるデータビットの集合を符号化するとき、数ｓのインデックス・ビットのみが変化する。残りのインデックス・ビットは、同じメモリセルに対して異なるデータビットの集合を符号化するとき、同じままで留まる。
【００３４】
マトリックスＭの各々の列は、固有の列番により識別される。マトリックスＭの複数の列は、マトリックスＭｓの対応する列を識別する同じ複数の列番によって識別される。操作３０６において、符号器は、操作３０２においてマトリックスＭ’ｓを生成するために、マトリックスＭｓから選ばれた同じ列番ｂ１，ｂ２，．．．ｂｓを有する、マトリックスＭからの数ｓの列を選択することにより、マトリックスＭの部分行列Ｇを生成する。部分行列Ｇは数ｋの行と数ｓの列を有する。符号器は、操作３０２においてマトリックスＭ’ｓを生成するために、マトリックスＭｓから選ばれた列番ｂ１，ｂ２，．．．ｂｓを有する、マトリックスＭからの数ｓの列を、部分行列Ｇに持たせる。
【００３５】
操作３０７において、符号器はＧ倍の部分行列ベクトルＶ（すなわち、Ｗ＝Ｇ×Ｖ）に等しいベクトルＷを計算する。ベクトルＷは、ｋの値を有するｋ×１のベクトルであり、ここでｋはデータビットの数である。操作３０８において、符号化されたデータビットを生成するために、符号器はベクトルＷをデータビットに適用する。操作３０８において、符号器は１に等しい、ベクトルＷにおいて対応するｉ番目の値を有する、ｉ番目のデータビットの各々を反転させることにより、かつ０に等しい、ベクトルＷにおいて対応するｉ番目の値を有する、ｉ番目のデータビットの各々を反転させないことにより、符号化されたデータビットを生成する。Ｍ’ｓ×Ｖ＝Ｕであるため、縮退故障を有するメモリセル内に記憶するために与えられる符号化されたデータビットの部分集合は、それらの対応する縮退故障と同じデジタル値を有する。操作３０９において、符号器は、メモリ回路の対応するメモリセル内への記憶用に、符号化されたデータビットを提供する。
【００３６】
図３に関連して上記に示され説明されている操作の幾つかは、図３に示される順序とは異なる順序で行われ得る。例えば、操作３０６は操作３０４〜３０５に先立って行われ得る。
【００３７】
図４は、本発明の一実施形態による、冗長ビットを用いてデータビットを再生するために、図２及び／又は図３の操作により生成される、符号化されたデータビットを復号化するための操作例を説明するフローチャートである。最初に、符号化されたデータビットはメモリ回路のメモリセルから読み取られる。符号化されたデータビット及びインデックス・ビット（すなわち、冗長ビット）は、次に制御回路１０１のような制御回路において、復号器に提供される。
【００３８】
操作４０１において、復号器はマトリックスＭを受け取る。操作４０１におけるマトリックスＭは、図３の操作において符号化されたデータビットを生成するために用いられた、同じマトリックスＭである。マトリックスＭの数ｓの行の任意の部分集合は、線形独立である。操作４０２において、復号器は、インデックス・ビットの第１の部分集合に基づいて選択されたマトリックスＭからの列を有する、マトリックスＭの部分行列のマトリックスＧを生成する。
【００３９】
図３における操作３０５の第１の実施形態に関して上記で議論したように、インデックス・ビットの第１の部分集合は、マトリックスＭ’ｓを生成するために操作３０２において選ばれた、マトリックスＭｓの数ｓの列番ｂ１，ｂ２，．．．ｂｓの各々を識別する。図３における操作３０５の第２の実施形態に関して上記で議論したように、インデックス・ビットの第１の部分集合は、マトリックスＭ’ｓを生成するために操作３０２において選ばれなかった、マトリックスＭｓの列番の各々を識別する。
【００４０】
操作３０５の第１の実施形態において、復号器は、操作３０５でインデックス・ビットの第１の部分集合により示される、列番ｂ１，ｂ２，．．．ｂｓを有するマトリックスＭからの数ｓの列を、部分行列Ｇに持たせる。操作３０５の第２の実施形態において、復号器は、操作３０５でインデックス・ビットの第１の部分集合により示されない、列番ｂ１，ｂ２，．．．ｂｓを有するマトリックスＭからの数ｓの列を、部分行列Ｇに持たせる。部分行列Ｇは、数ｋの行及び数ｓの列を有する。
【００４１】
図３における操作３０５に関して上記で議論したように、インデックス・ビットの第２の部分集合はベクトルＶの数ｓの値を示す。インデックス・ビットの第２の部分集合は、数ｓのビットを有する。操作４０３において、復号器はインデックス・ビットの第２の部分集合からベクトルＶを生成する。操作４０４において、復号器はベクトルＶ及びマトリックスＧに基づき、ベクトルＷを生成する。復号器は方程式Ｗ＝Ｇ×Ｖを解くことにより、ベクトルＷを計算する。
【００４２】
操作４０５において、復号器はデータビットを再生するために、符号化されたデータビットにベクトルＷを適用する。操作４０５において、復号器は１に等しい、ベクトルＷ内の対応するｉ番目の値を有するｉ番目の符号化されたデータビットの各々を反転させることにより、かつ０に等しい、ベクトルＷ内の対応するｉ番目の値を有するｉ番目の符号化されたデータビットの各々を反転させないことにより、データビットを再生する。
【００４３】
図５Ａ〜５Ｅは、本発明の実施形態による例示的符号化マトリックスを用いて、図３の符号化操作が如何にしてデータビットの一つの例示的集合に対して加えられ得るかの例を説明している。図５Ａは、０〜７の番号が付けられたビット位置を有する、８つのデータビットの例示的集合を説明している。８つのデータビットは、図５Ａに示すようなメモリ回路の８つの対応するメモリセル内に記憶するために与えられる。２、４、及び７のビット位置に対応するメモリセルは縮退故障を有する。２及び４のビット位置にあるメモリセルは、図５Ａ内のＳ０によって示されるように０縮退故障であり、７のビット位置にあるメモリセルは、図５Ａ内のＳ１によって示されるように１縮退故障である。
【００４４】
図５Ｂは４つの例示的な符号化マトリックスＭ、Ｍｓ、Ｍ’ｓ、及びＧを説明している。図５Ｂの例におけるマトリックスＭは８行と４列を有する。マトリックスＭの８つの行は、図５Ｂにおいて行０〜７と呼ばれる。マトリックスＭの８行の各々は、８つのデータビットの異なる１つに対応する。８つのデータビットは、対応する２、４、及び７のビット位置において３つの縮退故障を有するメモリセル内に記憶するために与えられるため、符号器は、操作３０１において縮退故障を有するメモリセルに対応するマトリックスＭの行２、４、及び７だけをマトリックスＭｓに持たせる。マトリックスＭのその他の行は、マトリックスＭｓには加えられない。マトリックスＭｓは３行と４列を有する。各々のマトリックスＭとＭｓにおける４列は、列０、１、２、及び３であり、それらは図５Ｂ内でそれぞれ列番００、０１、１０、及び１１として２値で呼ばれる。
【００４５】
列番１１、１０、及び００によって示されるマトリックスＭｓの列は線形独立である。列番０１は列番１１及び００の線形結合である。従って、符号器は図５Ｂに示すように、列番１１、１０、及び００を有するマトリックスＭｓの３列を、マトリックスＭ’ｓに持たせる。マトリックスＭｓ及びマトリックスＭ’ｓの列番１１、１０、及び００はそれぞれ、操作３０２で選択される列番ｂ１、ｂ２、及びｂ３である。正方行列Ｍ’ｓは３行と３列を有する。マトリックスＭｓの列番０１はマトリックスＭ’ｓには加えられない。
【００４６】
操作３０６において、符号器は上述のようにマトリックスＭの部分行列Ｇを生成する。部分行列ＧはマトリックスＭの８行すべてを有するが、しかし部分行列Ｇは図５Ｂに示すように、列番１１、１０、及び００を有するマトリックスＭの３列だけしか有さない。部分行列Ｇは、操作３０２においてマトリックスＭ’ｓを生成するためにマトリックスＭｓから選ばれた、同じ列番１１、１０、及び００（すなわちｂ１、ｂ２、及びｂ３）を有するマトリックスＭの列のみを有する。
【００４７】
操作３０３において、符号器は上述のようにベクトルＵを生成する。２のビット位置に対応するメモリセルの縮退故障は、図５Ａに示すような２のビット位置におけるデータビットと同じデジタル値を有するため、ベクトルＵの最初の値は図５Ｃに示すように０である。４、及び７のビット位置に対応するメモリセルの縮退故障は、図５Ａに示すような４、及び７のビット位置におけるデータビットとは異なるデジタル値をそれぞれ有するため、ベクトルＵの第２と第３の値は図５Ｃに示すように１である。
【００４８】
図５Ｃは、方程式Ｍ’ｓ×Ｖ＝Ｕを解くことによりベクトルＶを生成するための、操作３０４を行なう符号器の一例を説明している。符号器はマトリックスＭ’ｓを反転させ、次にベクトルＶを生成するためにベクトルＵと、マトリックスＭ’ｓの反転との乗算をする。ベクトルＶは図５Ｃの例において３×１のベクトルである。
【００４９】
図５Ｄは、方程式Ｗ＝Ｇ×Ｖを解くことによりベクトルＷを生成するための、操作３０７を行なう符号器の一例を説明している。図５Ｄの例において、ベクトルＷは８つの値を有する１×８のベクトルである。符号器がベクトルＷを計算した後、符号器は図５Ｅに示す符号化されたデータビットを生成するために、ベクトルＷをデータビットに適用する。符号器は例えば、符号化されたデータビットを生成するために、ベクトルＷのｉ番目の値の各ペア及び対応するｉ番目のデータビットに対して、２を法とする加算を行なうことにより、ベクトルＷをデータビットに適用し得る。
【００５０】
図５Ｅはまた符号化されたデータビットに対するインデックス・ビットを説明している。最初の２つのインデックス・ビットは、操作３０５の第２の実施形態に関して上述したように、マトリックスＭ’ｓに移されなかったマトリックスＭｓの列の、列番０１を示す。復号器は、操作３０２においてマトリックスＭ’ｓに移されなかったマトリックスＭｓの列の、列番０１を示す最初の２つのインデックス・ビットに基づいて、マトリックスＭ’ｓを生成するために用いられたマトリックスＭｓの３列を推測する。次の３つのインデックス・ビットは、ベクトルＶの値１０１を示す。
【００５１】
別の実施形態によれば、インデックス内のインデックス・ビットの数は、データビットの数ｋが非常に大きい場合に減らされ得る。この実施形態は漸近的改善と呼ばれる。この実施形態において、メモリ回路の対応するメモリセル内への記憶用にデータビットのブロックが提供される。ｔが正の整数である幾つかのパラメータｔに関して、データビットのブロックはｓ／ｔの数の部分的ブロックへと分割され、ここでｓはメモリ回路の対応するメモリセル内における縮退故障の数である。データビットの部分的ブロックの各々は、メモリセルの部分集合に対応する。メモリセルの各部分集合は、縮退故障を有する全く同じ数ｔのメモリセルを有する。仮にａ１，ａ２，．．．，ａｓ／ｔをデータビットのｓ／ｔの数の部分的ブロック内のデータビット数としよう。部分的ブロックの各々は異なる数のデータビットを有し得る。代わりに、部分的ブロックの幾つか又は全ては、同じ数のデータビットを有し得る。
【００５２】
部分的ブロック内にａ１，ａ２，．．．，ａｓ／ｔの数のデータビットを記憶するために、符号器は
【数２】
2014078945.tif 000004
に等しい数のインデックス・ビットを生成し、ここでｋはデータビットのブロック内の、データビットの全数である。データビットの部分的ブロックの各々に対して、符号器は、２ｔ＋ｔｌｏｇ２ｌｏｇ２ａｉに等しいインデックス内のインデックス・ビット数を生成する、図３に関して上述された線形代数的技法を用いる。この実施形態に関して符号器により生成されるインデックス・ビットの総数は、方程式（３）
【数３】
2014078945.tif 000005
において表わされる。
【００５３】
関数ｌｏｇ２ｌｏｇ２ｘは凹関数である。方程式（３）は、部分的ブロックの各々が同じビット数を有するというように、方程式（３）内の全てのａｉ’ｓが等しいとき、その最大値にある。下記の方程式（４）は、部分的ブロックの各々が同じビット数を有するとき、この実施形態に関して符号器により生成されるインデックス・ビットの総数を表わす。
【数４】
2014078945.tif 000006
【００５４】
この実施形態におけるインデックス内のインデックス・ビットの数は、パラメータｔに関して最小化され得る。ｑ＝ｋ／ｓである場合、ｔ＝（ｌｏｇ２ｑ）２は本実施形態におけるインデックス内のインデックス・ビットの数を最小化する。このｔの値に関して、インデックス内のインデックス・ビットの総数は、方程式（５）において以下に表わされる。
【数５】
2014078945.tif 000007
【００５５】
方程式（５）の第２項は、ほぼｓｌｏｇ２ｌｏｇ２ｑである。方程式（５）の残りの項の各々は、ｑ＞３である場合はｓよりも小さい。従って、方程式（５）は方程式（６）において以下に表わされるように単純化されることができる。以下の方程式（６）は、この近似によるインデックス・ビットの最大数を表わす。
インデックス・ビットの最大数＝３ｓ＋ｓｌｏｇ２ｌｏｇ２ｑ  （６）
【００５６】
本発明の実施形態は、例えばハードウェア、ソフトウェア、及びプログラム命令を含むコンピュータで読み取り可能な媒体の１つ、又は組合せを用いて実行され得る。本発明の実施形態は、コンピュータ上で動作可能な、持続性のコンピュータで読み取り可能な媒体上に記憶されたプログラム・コードの通りに具現化され得る。本発明の実施形態により実行されるソフトウェア及び本発明の結果は、半導体メモリ、相変化メモリ、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）、又はその他の媒体のようなコンピュータで読み取り可能な媒体上に記憶され得る。本発明の結果は、プロセッサによって実行又は処理され、ユーザーに対して表示され、ネットワークをわたって信号で伝送される、等のような様々な目的のために用いられ得る。本発明の実施形態は、ネットワークを通じて接続された多くのコンピュータシステムに分散処理を波及させるための、持続性のコンピュータで読み取り可能な媒体上に記憶された、コンピュータで可読のプログラム・コードユニットとしてもまた具現化され得る。
【００５７】
本発明の例示的実施形態の、先の記述は例証及び説明の目的で提示されている。先の記述は、余す所がないようには意図されておらず、又は本発明をここに開示されている例へと制限するようには意図されていない。場合によって、本発明の特徴は、記述されているような別の特徴の対応する用途無しに採用され得る。多くの変更、置き換え、及び変動が、本発明の範囲から逸脱することなく、上記の教示を踏まえて可能である。
【符号の説明】
【００５８】
１００  データ記憶システム
１０１  制御回路
１０２  メモリ回路
１０３  メモリ回路
【図１】
2014078945.tif 000008
【図２】
2014078945.tif 000009
【図３】
2014078945.tif 000010
【図４】
2014078945.tif 000011
【図５Ａ】
2014078945.tif 000012
【図５Ｂ】
2014078945.tif 000013
【図５Ｃ】
2014078945.tif 000014
【図５Ｄ】
2014078945.tif 000015
【図５Ｅ】
2014078945.tif 000016