(57)【特許請求の範囲】
【請求項１】
メモリセルを含むメモリ回路と、
前記メモリセル内に記憶するために与えられるデータビットを受け取るように動作する制御回路であって、前記メモリセルのサブセットは所定の縮退故障を有する、制御回路と、
を含む、データ記憶システムであって、
前記制御回路は、前記メモリセル内の前記所定の縮退故障の対応するもののビット位置に基づき、前記所定の縮退故障のそれぞれについて二項係数を計算するように動作し、前記制御回路は前記二項係数を合計し、組合せ数体系を用いて符号化された数を生成するように動作し、
前記制御回路は、前記符号化された数を示す１組の第１の冗長ビットを生成するように動作し、前記１組の第１の冗長ビットは、前記データビットを再生成するために前記メモリセルから読み取られるビットを復号するために使用される、
データ記憶システム。
【請求項２】
前記制御回路は、前記データビットのどれがその対応する所定の縮退故障のデジタル値に一致するのか、および前記データビットのどれがその対応する所定の縮退故障と異なるデジタル値を有するのかを示す、１組の第２の冗長ビットを生成するように動作する、
請求項１に記載のデータ記憶システム。
【請求項３】
前記１組の第１の冗長ビットおよび前記１組の第２の冗長ビットを前記データビットに関連させるように動作し、前記１組の第１の冗長ビットおよび前記１組の第２の冗長ビットを用いて前記メモリセルから読み取られる前記ビットを復号し、前記データビットを再生成するように動作する、
請求項２に記載のデータ記憶システム。
【請求項４】
前記メモリ回路が相変化メモリ回路である、
請求項１に記載のデータ記憶システム。
【請求項５】
前記制御回路が、前記二項係数のそれぞれを、１組のｎ要素から選択可能なｊ要素の組合せの数と等しくさせるように動作し、ｎは前記メモリセル内の前記所定の縮退故障の前記対応するものの前記ビット位置に等しい整数であり、ｊは、前記所定の縮退故障の前記対応するものを一意に識別する指数である、
請求項１に記載のデータ記憶システム。
【請求項６】
メモリセルを含むメモリ回路と、
前記メモリセルから読み取られるデータビットを受け取るように動作する制御回路であって、前記データビットに関連する冗長ビットを受け取るように動作する、制御回路と、
を含む、データ記憶システムであって、
前記制御回路は、前記冗長ビットの第１のサブセットによって示される符号化された数を識別するように動作し、前記制御回路は、組合せ数体系内の前記符号化された数を用いて計算される組合せに基づき、前記メモリセル内の１組の縮退故障のビット位置を求めるように動作し、前記制御回路は、前記１組の縮退故障の前記ビット位置および前記冗長ビットの第２のサブセットを用いて前記データビットのデジタル値を調節し、訂正されたデータビットを生成するように動作する、
データ記憶システム。
【請求項７】
前記冗長ビットの前記第２のサブセットは、前記１組の縮退故障を有する前記メモリセル内に記憶するために与えられた１組のビットのどれが、前記縮退故障の対応するもののデジタル値に一致したかを示す、
請求項６に記載のデータ記憶システム。
【請求項８】
前記制御回路が、１組のｃｊ要素から選択可能なｊ要素の第１の組合せに基づき、前記縮退故障の最初のもののビット位置を求めるように動作し、前記第１の組合せが前記符号化された数以下であるようにｃｊは最大値を有し、ｊは前記データビットの数に前記メモリセル内の前記縮退故障のビット誤り率を掛けた値に等しく、ｃｊは前記縮退故障の前記最初のものの前記ビット位置に等しい、
請求項７に記載のデータ記憶システム。
【請求項９】
前記制御回路が、１組のｃｊ−１要素から選択可能なｊ−１要素の第２の組合せに基づき、前記縮退故障の第２のもののビット位置を求めるように動作し、前記第２の組合せが前記符号化された数から前記第１の組合せを引いた値以下であるようにｃｊ−１は最大値を有し、ｃｊ−１は前記縮退故障の前記第２のものの前記ビット位置に等しい、
請求項８に記載のデータ記憶システム。
【請求項１０】
前記制御回路が、１組のｃｊ−２要素から選択可能なｊ−２要素の第３の組合せに基づき、前記縮退故障の第３のもののビット位置を求めるように動作し、前記第３の組合せが前記符号化された数から前記第１の組合せおよび前記第２の組合せを引いた値以下であるようにｃｊ−２は最大値を有し、ｃｊ−２は前記縮退故障の前記第３のものの前記ビット位置に等しい、
請求項９に記載のデータ記憶システム。
【請求項１１】
メモリ回路のメモリセル内に記憶するために与えられるデータビットを制御回路で受け取るステップであって、前記メモリセルのサブセットは所定の縮退故障を有するステップと、
前記制御回路を使い、前記メモリセル内の前記所定の縮退故障の対応するもののビット位置に基づき、前記所定の縮退故障のそれぞれについて二項係数を計算するステップと、
前記制御回路を使い、前記所定の縮退故障について計算された前記二項係数を合計し、組合せ数体系内の符号化された数を生成するステップと、
前記制御回路を使い、前記符号化された数を示す１組の第１の冗長ビットを生成するステップであって、前記１組の第１の冗長ビットは、前記データビットを再生成するために前記メモリセルから読み取られるビットを復号するために使用されるステップと、
を含む、方法。
【請求項１２】
前記データビットのどれがその対応する所定の縮退故障のデジタル値に一致するのか、および前記データビットのどれがその対応する所定の縮退故障と異なるデジタル値を有するのかを示す、１組の第２の冗長ビットを生成するステップ、
をさらに含む、請求項１１に記載の方法。
【請求項１３】
前記１組の第１の冗長ビットおよび前記１組の第２の冗長ビットを前記データビットに関連させるステップと、
前記１組の第１の冗長ビットおよび前記１組の第２の冗長ビットを用いて前記メモリセルから読み取られる前記ビットを復号し、前記データビットを再生成するステップと、
をさらに含む、請求項１２に記載の方法。
【請求項１４】
前記メモリ回路が相変化メモリ回路である、
請求項１１に記載の方法。
【請求項１５】
前記制御回路を使い、前記メモリセル内の前記所定の縮退故障の対応するもののビット位置に基づき、前記所定の縮退故障のそれぞれについて二項係数を計算するステップが、前記二項係数のそれぞれを、１組のｎ要素から選択可能なｊ要素の組合せの数と等しくさせるステップをさらに含み、ｎは前記メモリセル内の前記所定の縮退故障の前記対応するものの前記ビット位置に等しい整数であり、ｊは、前記所定の縮退故障の前記対応するものを一意に識別する指数である、
請求項１１に記載の方法。
【請求項１６】
メモリ回路のメモリセルから読み取られるデータビットを制御回路で受け取るステップと、
前記データビットに関連する冗長ビットを前記制御回路で受け取るステップと、
前記制御回路を使い、前記冗長ビットの第１のサブセットによって示される符号化された数を識別するステップと、
組合せ数体系内の前記符号化された数に基づき前記制御回路によって計算される組合せを使い、前記メモリセル内の１組の縮退故障のビット位置を求めるステップと、
前記１組の縮退故障の前記ビット位置および前記冗長ビットの第２のサブセットを用いて前記データビットのデジタル値を調節し、訂正されたデータビットを生成するステップと、
を含む、方法。
【請求項１７】
前記冗長ビットの前記第２のサブセットは、前記１組の縮退故障を有する前記メモリセル内に記憶するために与えられた１組のビットのどれが、前記縮退故障の対応するもののデジタル値に一致したかを示す、
請求項１６に記載の方法。
【請求項１８】
組合せ数体系内の前記符号化された数に基づき前記制御回路によって計算される組合せを使い、前記メモリセル内の１組の縮退故障のビット位置を求めるステップが、
１組のｃｊ要素から選択可能なｊ要素の第１の組合せに基づき、前記縮退故障の最初のもののビット位置を求めるステップをさらに含み、前記第１の組合せが前記符号化された数以下であるようにｃｊは最大値を有し、ｊは前記データビットの数に前記メモリセル内の前記縮退故障のビット誤り率を掛けた値に等しく、ｃｊは前記縮退故障の前記最初のものの前記ビット位置に等しい、
請求項１７に記載の方法。
【請求項１９】
組合せ数体系内の前記符号化された数に基づき前記制御回路によって計算される組合せを使い、前記メモリセル内の１組の縮退故障のビット位置を求めるステップが、
１組のｃｊ−１要素から選択可能なｊ−１要素の第２の組合せに基づき、前記縮退故障の第２のもののビット位置を求めるステップをさらに含み、前記第２の組合せが前記符号化された数から前記第１の組合せを引いた値以下であるようにｃｊ−１は最大値を有し、ｃｊ−１は前記縮退故障の前記第２のものの前記ビット位置に等しい、
請求項１８に記載の方法。
【請求項２０】
組合せ数体系内の前記符号化された数に基づき前記制御回路によって計算される組合せを使い、前記メモリセル内の１組の縮退故障のビット位置を求めるステップが、
１組のｃｊ−２要素から選択可能なｊ−２要素の第３の組合せに基づき、前記縮退故障の第３のもののビット位置を求めるステップをさらに含み、前記第３の組合せが前記符号化された数から前記第１の組合せおよび前記第２の組合せを引いた値以下であるようにｃｊ−２は最大値を有し、ｃｊ−２は前記縮退故障の前記第３のものの前記ビット位置に等しい、
請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、データ記憶システムに関し、より詳細には、組合せ数体系（combinatorial  number  system）を用いて符号化および復号するための方法に関する。
【背景技術】
【０００２】
多くのデータ通信システムは、データ内の誤りを検出し訂正するために、誤り訂正符号器および復号器を使用する。データ通信システムは、例えば約１×１０−４の率で生成されるランダム誤りを訂正することができる。約１×１０−４の誤り率を防ぐために、誤り訂正符号器は、その入力ビットよりも約１０％多いビットを有する符号化ビットを生成する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
相変化メモリ（ＰＣＭ：ｐｈａｓｅ  ｃｈａｎｇｅ  ｍｅｍｏｒｙ）は、不揮発性メモリの類である。ＰＣＭデバイスには、従来の不揮発性フラッシュメモリに勝る多くの利点がある。しかしＰＣＭデバイスは、劣化によって引き起こされる多数の誤りを発生させることがある。例えば、ＰＣＭデバイスは、１×１０−２以上の率で誤りを発生させることがある。
【０００４】
耐久性の限度において、不揮発性メモリデバイスの誤り率は劣化によって左右される。劣化によって引き起こされる誤りは、データ通信システム内で一般的なランダム誤りとは異なる特性および統計を有する縮退故障を含む。
【課題を解決するための手段】
【０００５】
一部の実施形態によれば、データ記憶システムが、メモリセルを有するメモリ回路および制御回路を含む。制御回路は、メモリセル内に記憶するために与えられるデータビットを受け取るように動作する。メモリセルのサブセットが所定の縮退故障を有する。制御回路は、メモリセル内の所定の縮退故障の対応するもののビット位置に基づき、所定の縮退故障のそれぞれについて二項係数を計算するように動作する。制御回路はそれらの二項係数を合計し、組合せ数体系を用いて符号化された数を生成するように動作する。制御回路は、符号化された数を示す１組の第１の冗長ビットを生成するように動作する。１組の第１の冗長ビットは、データビットを再生成するためにメモリセルから読み取られるビットを復号するために使用される。
【０００６】
以下の詳細な説明および添付図面を検討することにより、本発明の様々な目的、特徴、および利点が明らかになる。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態によるデータ記憶システムの一例を示す。
【図２】本発明の一実施形態による、縮退故障を有するメモリ回路内のメモリセルによって引き起こされる誤りを訂正するための冗長ビットを生成する操作の例を示す流れ図である。
【図３】本発明の一実施形態による、冗長ビットを使用してメモリ回路のメモリセル内の縮退故障によって引き起こされるデータビット内の誤りを訂正するための操作の例を示す流れ図である。
【図４】本発明の一実施形態による、冗長ビットのサブセットによって示される符号化された数を用いて、メモリセル内の所定の縮退故障のビット位置を求めるために復号器によって使用される操作の例を示す流れ図である。
【図５】本発明の一実施形態による、本明細書に記載の符号化および復号方法とともに使用可能なデータビットおよびメモリセルの例を示す。
【発明を実施するための形態】
【０００８】
本明細書に記載の一部の実施形態によれば、書込み操作中、メモリ回路のメモリセル内に記憶するためにデータビットが与えられる。符号器が、メモリセル内の所定の縮退故障に基づいてデータビットのための冗長ビットを生成する。次いで、データビットがメモリセル内に記憶される。読取操作中にデータビットがメモリセルから読み取られた後、復号器が冗長ビットを使用して所定の縮退故障によって引き起こされるデータビット内の誤りを訂正する。メモリ回路は、例えば縮退故障を有する（例えばカルコゲナイドガラスを用いた）相変化メモリ回路や別の種類のメモリ回路とすることができる。本明細書に記載のデータビットは、例えばユーザ生成ビット、ソフトウェアコードを表すビット、および他の任意のデジタル値を含むことができる。
【０００９】
縮退故障を有するメモリセルとは、単一のデジタル値しか記憶できないメモリセルである。１の縮退故障値を有するメモリセルは論理ハイのデジタル値しか記憶できず、０の縮退故障値を有するメモリセルは論理ローのデジタル値しか記憶できない。したがって、１の縮退故障値を有するメモリセルからは論理ハイのデジタル値しか読み取ることができず（すなわち１の状態が続き）、０の縮退故障値を有するメモリセルからは論理ローのデジタル値しか読み取ることができない（すなわち０の状態が続く）。縮退故障を有するメモリセルは、経時的に変わらない縮退故障値を概して有する。
【００１０】
メモリ回路内のメモリセルの一部が縮退故障を有する場合、縮退故障のデジタル値および縮退故障を有するメモリセルのアドレスが符号化プロセスの前に求められ、符号器に与えられる。符号器は、これらの所定の縮退故障のデジタル値およびアドレスを用いて冗長ビットを生成する。データビットはメモリ回路のメモリセル内に記憶される。冗長ビットは、データビットと同じメモリ回路内に記憶されても、別のメモリ回路内に記憶されてもよい。
【００１１】
その後、データビットおよび冗長ビットがメモリから読み取られ、復号器に与えられる。復号器は、冗長ビットを用いて所定の縮退故障によって引き起こされるデータビット内の誤りを訂正する。復号器は、メモリセル内の所定の縮退故障によって引き起こされる誤りをデータビットに含まなくさせる。
【００１２】
本明細書に記載する方法は、マルチレベルメモリセルに直接適用することができる。マルチレベルメモリセルは、１メモリセル当たり複数のビットを記憶することができる。例えば、メモリセルが２ビット保持して動けなくなる場合、それらの２ビットの値は固定され、それらを２つの別個の縮退故障位置として扱うことができる。縮退故障の一方の位置が分かっているので、他方の縮退故障の位置も分かる。その結果、同じ縮退故障誤り率について、マルチレベルメモリセルでは、単一レベルメモリセルで生成される冗長ビットよりも少ない冗長ビットが生成され得る。単一レベルメモリセルは、１メモリセル当たり１ビットしか記憶しない。冗長ビットの数は、例えば１メモリセル当たりのビット数に等しいだけ少ないものとすることができる。
【００１３】
図１は、本発明の一実施形態によるデータ記憶システム１００の一例を示す。データ記憶システム１００は、制御回路１０１、メモリ回路１０２、およびメモリ回路１０３を含む。制御回路１０１は、例えばメモリコントローラ回路、プロセッサ回路、またはメモリ回路１０２〜１０３内に記憶するための冗長ビットを生成する他の任意の種類の制御回路とすることができる。制御回路１０１は、メモリ回路１０２〜１０３との間でデータビットをやり取りすることができる。データビットは、メモリ回路１０２〜１０３の一方または両方の中に記憶される。冗長ビットは、メモリ回路１０２〜１０３の一方または両方の中に記憶されてもよい。データビットおよび冗長ビットは、１つまたは複数のオンチップもしくは外部バスにより、または他の種類の信号線により、制御回路１０１とメモリ回路１０２〜１０３との間で伝送される。制御回路１０１、メモリ回路１０２、およびメモリ回路１０３は、同じ集積回路内にあっても、別の集積回路内にあってもよい。したがってシステム１００は、回路１０１〜１０３を含む単一集積回路デバイスとすることができる。あるいはシステム１００は、３つの別個の集積回路デバイス１０１〜１０３を含んでもよい。
【００１４】
図２は、本発明の一実施形態による、縮退故障を有するメモリ回路内のメモリセルによって引き起こされる誤りを訂正するための冗長ビットを生成する操作の例を示す流れ図である。メモリ回路内のメモリセルのそれぞれは、少なくとも１つのデジタル値を記憶する。メモリセルの１つまたは複数が縮退故障を有する。縮退故障を有するメモリセルのアドレスおよび縮退故障のデジタル値が図２の操作を行う前に求められ、符号器に与えられる。例えば、どのメモリセルが１組の所定の縮退故障を発生させる縮退故障の挙動に一致する誤りを示すのかを判定するために、再三の読取操作および書込み操作を実行することができる。図２の操作は、例えば制御回路１０１内の符号器（例えばファームウェア）によって実行されてもよい。
【００１５】
操作２０１で、符号器が、メモリ回路内に記憶するために与えられるｋの数のデータビットを受け取る。ｋは正の整数である。データビットを記憶するために、メモリ回路内の１組のメモリセルが識別される。データビットを記憶するために識別されるメモリセルは、典型的にはメモリ回路内のメモリセルの総数のサブセットである。例えば、データビットを記憶するために識別されるメモリセルは、メモリ回路内のメモリセルの１ページに対応してもよい。データビットのそれぞれは、メモリ回路の対応するメモリセル内に記憶するために与えられる。データビットの１つまたは複数が、所定の縮退故障を有する対応するメモリセル内に記憶するために与えられる。
【００１６】
操作２０２で、符号器が、データビットを記憶するために識別されるメモリセル内の所定の縮退故障のそれぞれについて二項係数を計算する。データビットを記憶するために識別されるメモリセル内の所定の縮退故障のビット位置は、ｃ１，ｃ２，．．．ｃｓで表現され、ｓはデータビットを記憶するために識別されるメモリセル内の所定の縮退故障の数である。ビット位置ｃ１，ｃ２，．．．ｃｓは、０≦ｃ１＜ｃ２＜．．．＜ｃｓが成立するような狭義単調増加する正の整数である。
【００１７】
多数のメモリセル内に記憶するためにデータビットが与えられる一実施形態では、数ｓが、データビット数ｋにメモリセル内の縮退故障のビット誤り率αを乗じた値に等しい（またはほぼ等しい）（すなわちｓ＝α×ｋ＝αｋ）。この実施形態では、所定の縮退故障の数がｓ＝αｋを下回る場合、符号器は、縮退故障を有さないメモリセルの一部を、任意の縮退故障値を伴う所定の縮退故障を有するものとして扱い、これにより所定の縮退故障を有するものとして符号器によって扱われるメモリセルの総数がｓに等しくなる。単一レベルメモリセルでは、数ｋは、データビットを記憶するために識別されるメモリセルの数にも等しい。
【００１８】
操作２０２内で符号器が所定の縮退故障ごとに計算する二項係数は、
【数１】
0005646723.tif 000002
に等しく、ｎはメモリセル内の対応する所定の縮退故障のビット位置ｃ１，ｃ２，．．．ｃｓに等しい整数であり、ｊは、対応する所定の縮退故障を一意に識別する指数である。指数ｊは、所定の縮退故障のそれぞれを一意に識別するために１からｓまで連続的に変化する正の整数であり、ｊ≦ｎが成立する。二項係数
【数２】
0005646723.tif 000003
は、１組のｎ要素から選択可能なｊ要素の組合せの数に等しい。二項係数
【数３】
0005646723.tif 000004
は、ｎの要素を有する組の中のｊの組合せの数に等しく、ｊの組合せのそれぞれの中のｊの要素の順序は関係なく、ｊの組合せのそれぞれにおいてｊの要素の複数の繰返しはない。したがって、各組合せは、順序を無視して１組のｎの要素からｊの要素を選択することができる方法である。メモリセル内の所定の縮退故障ごとに二項係数を計算するための手法を、以下の等式（１）に示す公式によって与え、ただしｊ≦ｎが成立する。
【数４】
0005646723.tif 000005
【００１９】
符号器は、対応する所定の縮退故障のビット位置ｎを用いて１からｓまでの正の整数ｊごとに二項係数を計算し、ｓ数の二項係数を生成する。データビットを記憶するために識別されるメモリ回路のメモリセル内のｓ数の所定の縮退故障のｓ数の二項係数は、等式（２）に示すように書くことができる。
【数５】
0005646723.tif 000006
【００２０】
ある正の整数ｓのコンビナデッィックスとも呼ばれる組合せ数体系は、狭義単調増加する数列０≦ｃ１＜ｃ２＜．．．＜ｃｓとして表される、１組の数とその１組の数のｓの組合せとの間の対応である。一実施形態によれば、組合せ数体系は、データビットを記憶するために識別されるメモリセル内の所定の縮退故障のビット位置を示すために使用される。この実施形態では、組合せ数体系は、数列
【数６】
0005646723.tif 000007
に対する
【数７】
0005646723.tif 000008
数の組合せの全単射であり、ただしｋはデータビットの数であり、ｓはデータビットを記憶するために識別されるメモリセル内の所定の縮退故障の数である。この全単射を使い、データビットを記憶するために識別されるメモリセル内の所定の縮退故障の可能なビット位置の全てを正確にマップすることができる。
【００２１】
組Ｓのｓの組合せは、ｓの個別要素を有するＳのサブセットである。組合せ数体系は、それぞれ１つの数により、ｋ要素からなる組Ｓの可能な全てのｓの組合せの表現を与える。任意のｋについて、｛０，１，．．．，ｋ−１｝をかかる組として選び、所与のｓの組合せＣの表現は、（ｋが十分大きくなければならないが）ｋの値とは無関係であることを定めることができる。ｋを増加させることによりＣをより大きい組のサブセットとみなすことは、Ｃを表す数を変えない。
【００２２】
ｓの組合せＣに対し、ｓ次の組合せ数体系内で関連する数Ｎは、所与のオーダリング内でＣより真に小さいｓの組合せの数である。この数Ｎは、以下のようにｃｓ＞．．．ｃ２＞ｃ１の状態で、Ｃ＝｛ｃｓ，．．．，ｃ２，ｃ１｝から計算することができる。オーダリングの定義から、Ｃより真に小さいｓの組合せＳごとに一意の指数ｉがあることになり、ｃｉはＳにないのに対し、ｃｓ，．．．，ｃｉ＋１はＳ内にあり、ｃｉを上回る他のいかなる値もＳ内にない。したがって、それらのｓの組合せＳは、ｉの可能な値１，２，．．．，ｓに応じてグループ分けすることができ、各グループは別々にカウントされる。所与のｉの値について、ｃｓ，．．．，ｃｉ＋１はＳ内に含まれ、Ｓの残りのｉ要素はｃｉより真に小さい自然数から選択される。そのような任意の選択は、Ｃより真に小さいｓの組合せＳをもたらす。可能な選択の数は
【数８】
0005646723.tif 000009
であり、これはグループｉ内の組合せの数である。Ｃより真に小さいｓの組合せの総数Ｎは、
【数９】
0005646723.tif 000010
に等しくなる。これは、ｓの組合せの順序付きリスト内のＣの（０から始まる）指数である。
【００２３】
操作２０３で、符号器が、等式（３）に示す組合せ数体系を用いて等式（２）内のｓ数の二項係数を合計することにより、符号化された数Ｎを計算する。等式（３）では、ｃ１，ｃ２，ｃ３，．．．ｃｓは、データビットを記憶するために識別されるメモリセル内のｓ数の所定の縮退故障のビット位置である。
【数１０】
0005646723.tif 000011
【００２４】
したがって、符号化された数Ｎは、データビットを記憶するために識別されるメモリセル内の所定の縮退故障のｓ数の二項係数の和に等しい。操作２０３では、符号器が、メモリセル内に記憶されるデータビットのための１組の第１の冗長ビットとして符号化された数Ｎの２進表現を生成する。
【００２５】
操作２０４で、符号器は、所定の縮退故障を有するメモリセル内に記憶されるデータビットのどれが、その対応する所定の縮退故障と同じデジタル値を有するのか、および所定の縮退故障を有するメモリセル内に記憶されるデータビットのどれが、その対応する所定の縮退故障と異なるデジタル値を有するのかを示すｓ数の冗長ビットを生成する。一例として、操作２０４で生成されるｓ数の冗長ビットは、そのメモリセル内に記憶されるデータビットのデジタル値にｉ番目の縮退故障が一致する場合、そのｉ番目のビット位置内に０を有することができ、そのメモリセル内に記憶されるデータビットのデジタル値にｉ番目の縮退故障が一致しない場合、そのｉ番目のビット位置内に１を有することができる。
【００２６】
図２の実施形態では、符号器が、等式（３）から計算される符号化された数Ｎを示す１組の冗長ビットと、所定の縮退故障を有するメモリセル内に記憶されるデータビットのどれが、それらの縮退故障の対応するもののデジタル値に一致するのかを示す別の組の冗長ビットとを生成する。以下の等式（４）は、符号器が操作２０３〜２０４内で生成する冗長ビットの数Ｒを示し、ただしｓ＝αｋが成立する。以下の等式（５）および（６）は、符号器が操作２０３〜２０４内で生成する冗長ビットの最大数Ｒを示す。
【数１１】
0005646723.tif 000012
【００２７】
データビットは、データビットを記憶するために識別されるメモリセル内に記憶される。データビットは、図２の操作前の、その操作中の、またはその操作後の書込み操作中にメモリセル内に記憶される。冗長ビットはメモリ内に記憶され、データビットに関連付けられる。冗長ビットは、データビットと同じメモリ回路内に記憶されても、別のメモリ回路内に記憶されてもよい。メモリセルのデータビットにアクセスする読取操作中、冗長ビットがメモリから読み出され、メモリセル内の所定の縮退故障によって引き起こされるデータビット内の誤りを訂正するために使用される。
【００２８】
図３は、本発明の一実施形態による、冗長ビットを使用してメモリ回路のメモリセル内の縮退故障によって引き起こされるデータビット内の誤りを訂正するための操作の例を示す流れ図である。読取操作中にデータビットがメモリ回路のメモリセルから読み取られ、復号器に与えられる。データビットに関連する冗長ビットがメモリから読み取られ、復号器に与えられる。冗長ビットは図２の操作を用いて符号器によって生成され、データビットに関連付けられる。復号器は、データビットに関連する冗長ビットを用いてメモリセル内の所定の縮退故障によって引き起こされるデータビット内の誤りを訂正する。
【００２９】
操作３０１で、復号器は、読取操作中にメモリセルから読み取られたｋの数のデータビットを受け取る。復号器は、この読取操作中に冗長ビットも受け取る。冗長ビットは、データビットと同じメモリ回路から、または別のメモリ回路から読み取られる。
【００３０】
操作３０２で、復号器は、符号化された数Ｎとして冗長ビットの１つのサブセットを識別し、所定の縮退故障を有するメモリセル内に記憶されていた元のデータビットのどれが、それらの縮退故障の対応するもののデジタル値に一致したかを示す冗長ビットの別のサブセットを識別する。一例として、符号器は、所定の縮退故障を有するメモリセル内に記憶されていた元のデータビットのどれが、それらの縮退故障の対応するもののデジタル値に一致したかを最初のｓ数の冗長ビットに示させ、符号化された数Ｎを残りの冗長ビットに示させることができる。この例では、復号器は、所定の縮退故障を有するメモリセル内に記憶されていた元のデータビットのどれが、それらの縮退故障の対応するもののデジタル値に一致したかを示すために最初のｓ数の冗長ビットを使用し、符号化された数Ｎの２進値として残りの冗長ビットを使用する。この例では、復号器がビット誤り率αを受け取りまたは記憶し、等式ｓ＝αｋを使ってｓを計算する。
【００３１】
操作３０３で、復号器は、冗長ビットのサブセットによって示される符号化された数Ｎを用いて、メモリセル内の所定の縮退故障のそれぞれのビット位置を求める。上記で説明し等式（３）に示したように、Ｎは、データビットを記憶したメモリセル内の所定の縮退故障のｓ数の二項係数の和に等しい。図４に関して以下に記載するように、復号器は、例えば符号化された数Ｎを使い、所定の縮退故障のビット位置を求めることができる。
【００３２】
操作３０４で、復号器は、操作３０３で生成された所定の縮退故障のビット位置および残りの冗長ビットを使用し、メモリセルから読み取られるデータビットのデジタル値を調節して、訂正されたデータビットを生成する。残りの冗長ビットは、所定の縮退故障を有するメモリセル内に記憶されていた元のデータビットのどれが、それらの縮退故障の対応するもののデジタル値に一致したかを示す。復号器は、残りの冗長ビットのデジタル値に基づいて、所定の縮退故障を有するメモリセルから読み取られたデータビットの１つまたは複数のデジタル値を調節することができる。
【００３３】
一例として、残りの冗長ビットは、そのメモリセル内に記憶されていた元のデータビットのデジタル値にｉ番目の所定の縮退故障が一致する場合、そのｉ番目のビット位置内に０を有し、そのメモリセル内に記憶されていた元のデータビットのデジタル値にｉ番目の所定の縮退故障が一致しない場合、そのｉ番目のビット位置内に１を有する。復号器は操作３０３の結果に基づき、データビットのどれが所定の縮退故障を有するメモリセルから読み取られたかを判定する。復号器は、所定の縮退故障を有するメモリセルから読み取られたデータビットのそれぞれを、そのメモリセル内に記憶される元のデータビットがそのメモリセルの縮退故障のデジタル値に一致しなかったことを残りの冗長ビットの対応するものが示す場合に反転させ、訂正されたデータビットの対応するものを生成する。復号器は、訂正されたデータビットの対応するものを生成するために、メモリセルから読み取られる残りのデータビットを反転させない。
【００３４】
図４は、本発明の一実施形態による、冗長ビットのサブセットによって示される符号化された数Ｎを用いて、メモリセル内の所定の縮退故障のビット位置を求めるために復号器によって使用される操作の例を示す流れ図である。図４の実施形態では、ｊは正の整数に等しい可変指数であり、Ｍは正の整数に等しい可変パラメータである。操作４０１において、指数ｊは縮退故障の数ｓに等しく、パラメータＭは、操作３０２で明らかにされた冗長ビットのサブセットによって示される符号化された数Ｎに等しい。復号器は、符号化された数Ｎに対応するｊの組合せを検出する。ｃｊがその最大の要素である、最も小さい組合せは
【数１２】
0005646723.tif 000013
である。したがってｃｊは、
【数１３】
0005646723.tif 000014
が成立する最も大きい正の整数である。操作４０１では、整数
【数１４】
0005646723.tif 000015
を所与として、復号器は
【数１５】
0005646723.tif 000016
が成立するようにｃｊが最大だと見出し、ただしＭは組合せ数体系内の符号化された数Ｎに等しい。復号器は、メモリセル内の第１の所定の縮退故障のビット位置として値ｃｊを選択する。
【００３５】
ｊ＞１が成立する場合、ｊの組合せの残りの要素が、ｊ−１次の組合せ数体系内の数
【数１６】
0005646723.tif 000017
に対応するｊ−１の組合せを形成する。復号器は、Ｍとｊの代わりに、
【数１７】
0005646723.tif 000018
およびｊ−１のそれぞれを用いて同じ操作を繰り返すことにより、ｊの組合せの残りの要素を見つける。とりわけ操作４０２では、復号器は
【数１８】
0005646723.tif 000019
が成立するようにｃｊ−１が最大だと見出す。操作４０２の最初の反復では、指数ｊはｓに等しく、パラメータＭは符号化された数Ｎに等しい。復号器は、メモリセル内の第２の所定の縮退故障のビット位置として値ｃｊ−１を選択する。
【００３６】
次いで復号器は、決定操作４０３で、ｊ＞２が成立するかどうかを判定する。操作４０３でｊ＝２が成立する場合、その復号プロセスは終了する。操作４０３でｊ＞２が成立する場合、操作４０４で復号器がｊから１を引き（すなわちｊ＝ｊ−１）、操作４０２〜４０４の次の反復のための指数ｊの新たな値を生成する。復号器は、操作４０４の各反復内でｊの値を１ずつ減少させる。さらに操作４０４では、復号器は、Ｍから
【数１９】
0005646723.tif 000020
を引き
【数２０】
0005646723.tif 000021
操作４０２〜４０４の次の反復のためのパラメータＭの新たな値を生成する。次いで復号器は、操作４０４で計算したｊおよびＭの新たな値を用いて操作４０２〜４０３を繰り返し、メモリセル内の次の所定の縮退故障のビット位置を求める。復号器は、データビットがそこから読み取られたメモリセル内のｓ数の所定の縮退故障のビット位置ｃ１，ｃ２，．．．，ｃｓ−１，ｃｓのそれぞれを求めるために、操作４０２〜４０４の反復を実行し続ける。
【００３７】
図５は、本発明の一実施形態による、本明細書に記載の符号化および復号方法とともに使用可能なデータビットおよびメモリセルの例を示す。図５内に示し、図５に関して説明する値は解説目的で与える例に過ぎず、限定的であることを意図しない。
【００３８】
図５は、ビット位置０〜２４にあるメモリ回路内の２５個の単一レベルメモリセルを示す。図を簡単にするために、図５ではこの２５個のメモリセルを四角形として示す。図５は、ビット位置０〜２４内にある１組の例示的な２５個のデータビットも示す。図５内に示す２５個のデータビットは、２５個のメモリセル内に記憶するために与えられる。データビットのそれぞれは、そのデータビットと同じビット位置を有する対応するメモリセル内に記憶するために与えられる。例えば、図５に示すビット位置０にある最も左のデータビットは、図５に示すビット位置０にある対応する最も左のメモリセル内に記憶するために与えられる。
【００３９】
図５に示すメモリセルの一部は縮退故障を有する。０の縮退故障を有するメモリセルは、図５内でＳ０によって識別される。ビット位置３、６、および１７にあるメモリセルは０の縮退故障を有する。１の縮退故障を有するメモリセルは、図５内でＳ１によって識別される。ビット位置８および１３にあるメモリセルは１の縮退故障を有する。
【００４０】
操作２０２で、符号器が、図５に示すメモリセル内のビット位置３、６、８、１３、および１７にある縮退故障のそれぞれの二項係数を計算する。図５のメモリセル内の５つの縮退故障の５つの二項係数は、３、１５、５６、７１５、および６１８８の数にそれぞれ等しい
【数２１】
0005646723.tif 000022
である。
【００４１】
操作２０３で、符号器が、操作２０２で計算された５つの二項係数を合計することにより、メモリセル内の５つの縮退故障のビット位置３、６、８、１３、および１７に対応する符号化された数Ｎを計算する。この例では、符号化された数Ｎは６９７７に等しい。次いで符号器は、６９７７の２進値を示す１組の冗長ビットを生成する。
【００４２】
操作２０４で、符号器は、縮退故障を有するメモリセル内に記憶されるデータビットのどれが、その対応する縮退故障と同じデジタル値を有するのか、および縮退故障を有するメモリセル内に記憶されるデータビットのどれが、その対応する縮退故障と異なるデジタル値を有するのかを示す１組の５つの冗長ビットを生成する。操作２０４で、符号器は、ビット位置３および１３にあるデータビットがその対応する縮退故障と同じデジタル値を有し、ビット位置６、８、および１７にあるデータビットがその対応する縮退故障とは異なるデジタル値を有すると判定する。
【００４３】
符号器は、０１１０１に等しい１組の５つの冗長ビットを生成する。この冗長ビットの組のｉ番目のビット位置内の各０は、そのメモリセル内に記憶されるデータビットのデジタル値にｉ番目の縮退故障が一致することを示す。この冗長ビットの組のｉ番目のビット位置内の各１は、そのメモリセル内に記憶されるデータビットのデジタル値にｉ番目の縮退故障が一致しないことを示す。冗長ビット０１１０１は、図５に示すビット位置３、６、８、１３、および１７それぞれのメモリセルの縮退故障に対応する。
【００４４】
読取操作中にデータビットがメモリセルから読み取られた後、データビットおよび冗長ビットが復号器に与えられる。操作３０２で、復号器は、符号化された数Ｎとして冗長ビットの１つのサブセットを識別する。復号器はさらに、縮退故障の対応するもののデジタル値に一致した縮退故障を有するメモリセル内に元のデータビットのどれが記憶されていたかを示す、冗長ビットの別のサブセットを識別する。
【００４５】
操作３０３で、復号器は、図４の操作を用いて符号化された数Ｎを復号する。まず、この例では指数ｊは５に等しい。操作４０１で、復号器は
【数２２】
0005646723.tif 000023
が成立するようにｃ５の最大値を求める。こうして、復号器はｃ５が１７に等しいと決定する。操作４０２で、復号器は、
【数２３】
0005646723.tif 000024
が成立するようにｃ４の最大値を求める。こうして、復号器はｃ４が１３に等しいと決定する。
【００４６】
操作４０４の最初の反復でｊの値を１減らし、ｊを４に等しくさせた後、復号器は、操作４０２の２回目の反復で
【数２４】
0005646723.tif 000025
が成立するようにｃ３の最大値を求める。こうして、復号器はｃ３が８に等しいと決定する。操作４０４の２回目の反復でｊの値を１減らし、ｊを３に等しくさせた後、復号器は、操作４０２の３回目の反復で
【数２５】
0005646723.tif 000026
が成立するようにｃ２の最大値を求める。こうして、復号器はｃ２が６に等しいと決定する。操作４０４の３回目の反復でｊの値を１減らし、ｊを２に等しくさせた後、復号器は、操作４０２の４回目の反復で
【数２６】
0005646723.tif 000027
が成立するようにｃ１の最大値を求める。こうして、復号器はｃ１が３に等しいと決定する。操作４０３の次の反復では指数ｊは２に等しく、その後復号プロセスは終了する。復号器は、縮退故障のビット位置ｃ５、ｃ４、ｃ３、ｃ２、およびｃ１のビット位置がそれぞれ１７、１３、８、６、および３であると決定する。
【００４７】
本発明の実施形態は、例えばハードウェア、ソフトウェア、およびプログラム命令を含むコンピュータ可読媒体の１つまたは組合せを用いて実施することができる。本発明の実施形態は、コンピュータ上で実行可能な非一時的コンピュータ可読媒体上に記憶されるプログラムコードとして実施することができる。本発明の実施形態によって実施されるソフトウェアおよび本発明の結果は、半導体メモリ、相変化メモリ、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）や他の媒体などのコンピュータ可読媒体上に記憶することができる。本発明の結果は、プロセッサによって実行されまたは処理されること、利用者に表示されること、ネットワークを介して信号内で伝送されることなど、様々な目的で使用することができる。本発明の実施形態は、ネットワークを介して接続されるいくつかのコンピュータシステムに分散処理に影響を及ぼさせる、非一時的コンピュータ可読媒体上に記憶されるコンピュータ可読プログラムコードユニットとして実施することもできる。
【００４８】
本発明の例示的実施形態についての上記の説明は、解説および説明目的で提示した。上記の説明は網羅的であることも、本明細書で開示した例に本発明を限定することも意図しない。一部の例では、記載した他の特徴を対応して使用することなしに、本発明の特徴を使用することができる。上記の教示に照らし、本発明の範囲から逸脱することなく多くの修正形態、代替形態、および改変形態が可能である。
【符号の説明】
【００４９】
１００  データ記憶システム
１０１  制御回路
１０２  メモリ回路
１０３  メモリ回路
【図１】
0005646723.tif 000028
【図２】
0005646723.tif 000029
【図３】
0005646723.tif 000030
【図４】
0005646723.tif 000031
【図５】
0005646723.tif 000032