(57)【特許請求の範囲】
【請求項１】
複数の入力ビットを記憶する方法であって、
（ａ）前記複数の入力ビットの複数のビットシーケンスをメモリセルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記入力ビットの複数のビットシーケンスを対応する前記複数のプログラム状態に写像するステップと、
（ｂ）前記メモリセルを前記対応するプログラム状態にプログラムするステップと
を含む、方法。
【請求項２】
前記メモリセルはフラッシュメモリセルであり、前記状態は閾値電圧状態である、請求項１に記載の方法。
【請求項３】
（ｃ）前記メモリセルを読み取るステップであって、それにより、読み取り状態値を得る、読み取るステップと、
（ｄ）前記読み取り状態値を複数の出力ビットに変換するステップと
をさらに含む、請求項１に記載の方法。
【請求項４】
前記変換することは最尤復号化を含むステップにより行われる、請求項３に記載の方法。
【請求項５】
前記変換することは、
（ｉ）前記読み取り状態値を複数のソフトビット推定に写像すること、及び
（ｉｉ）前記ソフトビット推定を復号化すること
を含むステップにより行われる、請求項３に記載の方法。
【請求項６】
前記写像することは、前記入力ビットを複数の入力符号語として符号化することを含み、
前記変換することは、
（ｉ）前記読み取り状態値を複数の出力符号語に写像することであって、前記各出力符号語は前記入力符号語のうちの１つに一意に対応する、写像すること、及び
（ｉｉ）前記出力符号語を順次復号化することであって、最初の前記出力符号語に続く前記各出力符号語の復号化は、少なくとも部分的に、少なくとも１つの先行する前記出力符号語の前記復号化の結果に基づく、復号化すること
を含むステップにより行われる、請求項３に記載の方法。
【請求項７】
複数の入力ビットを記憶する方法であって、
（ａ）前記入力ビットの複数のビットシーケンスを複数のメモリセルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記入力ビットの複数のビットシーケンスを対応する前記複数のプログラム状態に写像するステップと、
（ｂ）前記複数のメモリセルを前記対応するプログラム状態にプログラムするステップと
を含む、方法。
【請求項８】
前記メモリセルはフラッシュメモリセルであり、前記状態は閾値電圧状態である、請求項７に記載の方法。
【請求項９】
（ｃ）前記メモリセルを読み取るステップであって、それにより、読み取り状態値を得る、読み取るステップと、
（ｄ）前記読み取り状態値を複数の出力ビットに変換するステップと
をさらに含む、請求項７に記載の方法。
【請求項１０】
前記変換することは最尤復号化を含むステップにより行われる、請求項９に記載の方法。
【請求項１１】
前記変換することは、
（ｉ）前記読み取り状態値を複数のソフトビット推定に写像すること、及び
（ｉｉ）前記ソフトビット推定を復号化すること
を含むステップにより行われる、請求項９に記載の方法。
【請求項１２】
前記写像することは、前記入力ビットを複数の入力符号語として符号化することを含み、前記変換することは、
（ｉ）前記読み取り状態値を複数の出力符号語に写像することであって、前記各出力符号語は前記入力符号語のうちの１つに一意に対応する、写像すること、及び
（ｉｉ）前記出力符号語を順次復号化することであって、最初の前記出力符号語に続く前記各出力符号語の復号化は、少なくとも部分的に、少なくとも１つの先行する前記出力符号語の前記復号化の結果に基づく、復号化すること
を含むステップにより行われる、請求項９に記載の方法。
【請求項１３】
（ａ）セルと、
（ｂ）コントローラであって、
（ｉ）複数のビットシーケンスを前記セルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記複数のビットシーケンスを対応する前記複数のプログラム状態に写像すること、及び
（ｉｉ）前記セルを前記対応するプログラム状態にプログラムすること
により前記複数のビットを前記セルに記憶するように動作可能なコントローラと
を備えるメモリ装置。
【請求項１４】
複数のビットを記憶するシステムであって、
（ａ）セルを含むメモリ装置と、
（ｂ）プロセッサであって、
（ｉ）複数のビットシーケンスを前記セルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記複数のビットシーケンスを対応する前記複数のプログラム状態に写像し、
（ｉｉ）前記複数のセルを前記対応するプログラム状態にプログラムする
ように動作可能なプロセッサと
を備える、システム。
【請求項１５】
（ａ）複数のセルと、
（ｂ）コントローラであって、
（ｉ）複数のビットシーケンスを前記複数のセルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記複数のビットシーケンスを対応する前記複数のプログラム状態に写像し、
（ｉｉ）前記複数のセルを前記対応するプログラム状態にプログラムすること
により前記複数のビットを前記セルに記憶するように動作可能なコントローラと
を備える、メモリ装置。
【請求項１６】
複数のビットを記憶するシステムであって、
（ａ）複数のセルを含むメモリ装置と、
（ｂ）プロセッサであって、
（ｉ）前記複数のビットからの複数のビットシーケンスを前記複数のセルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記複数のビットシーケンスを対応する前記複数のプログラム状態に写像し、
（ｉｉ）前記複数のセルを前記対応するプログラム状態にプログラムする
ように動作可能なプロセッサと
を備える、システム。
【請求項１７】
Ｎ＞１であるＮ個のビットを記憶する方法であって、
（ａ）メモリセルを含むメモリ装置を、前記メモリセルを選択的にＭ＜２ＮであるＭ個のプログラム状態にするように構成するステップと、
（ｂ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択するステップと、
（ｃ）前記メモリセルを前記選択されたプログラム状態にプログラムするステップと
を含む、方法。
【請求項１８】
Ｎ＞１であるＮ個のビットを記憶する方法であって、
（ａ）複数のメモリセルを含むメモリ装置を、前記メモリセルを選択的にＭ＜２ＮであるＭ個のプログラム状態にするように構成するステップと、
（ｂ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択するステップと、
（ｃ）前記複数のメモリセルを前記選択されたプログラム状態にプログラムするステップと
を含む、方法。
【請求項１９】
Ｎ＞１であるＮ個のビットを記憶するメモリ装置であって、
（ａ）セルと、
（ｂ）コントローラであって、
（ｉ）前記セルを選択的にＭ＜２ＮであるＭ個のプログラム状態にすること、及び
（ｉｉ）
（Ａ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択すること、及び
（Ｂ）前記セルを前記選択されたプログラム状態にプログラムすること
により前記ビットを前記セルに記憶すること
を行うように動作可能なコントローラと
を備える、装置。
【請求項２０】
Ｎ＞１であるＮ個のビットを記憶するシステムであって、
（ａ）セルを含むメモリ装置と、
（ｂ）プロセッサであって、
（ｉ）前記セルを選択的にＭ＜２ＮであるＭ個のプログラム状態にすること、及び
（ｉｉ）
（Ａ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択すること、及び
（Ｂ）前記セルを前記選択されたプログラム状態にプログラムすること
により前記ビットを前記セルに記憶すること
を行うように動作可能なプロセッサと
を備える、システム。
【請求項２１】
Ｎ＞１であるＮ個のビットを記憶するメモリ装置であって、
（ａ）複数のセルと、
（ｂ）コントローラであって、
（ｉ）前記セルを選択的にＭ＜２ＮであるＭ個のプログラム状態にすること、及び
（ｉｉ）
（Ａ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択すること、及び
（Ｂ）前記複数のセルを前記選択されたプログラム状態にプログラムすること
により前記ビットを前記複数のセルに記憶すること
を行うように動作可能なコントローラと
を備える、装置。
【請求項２２】
Ｎ＞１であるＮ個のビットを記憶するシステムであって、
（ａ）複数のセルを含むメモリ装置と、
（ｂ）プロセッサであって、
（ｉ）前記セルを選択的にＭ＜２ＮであるＭ個のプログラム状態にすること、及び
（ｉｉ）
（Ａ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択すること、及び
（Ｂ）前記複数のセルを前記選択されたプログラム状態にプログラムすること
により前記ビットを前記複数のセルに記憶すること
を行うように動作可能なプロセッサと
を備える、システム。
【請求項２３】
複数の入力ビットを記憶するためのプログラムが格納されているコンピュータ可読記憶媒体であって、
前記プログラムは、コンピュータに少なくとも、
（ａ）前記入力ビットの複数のビットシーケンスを、メモリセルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記入力ビットの複数のビットシーケンスを対応する前記複数のプログラム状態に写像する動作と、
（ｂ）前記メモリセルを前記対応するプログラム状態にプログラムする動作と
を実行させる、コンピュータ可読記憶媒体。
【請求項２４】
複数の入力ビットを記憶するためのプログラムが格納されているコンピュータ可読記憶媒体であって、
前記プログラムは、コンピュータに少なくとも、
（ａ）前記複数の入力ビットの複数のビットシーケンスを、複数のメモリセルの複数のプログラム状態の少なくとも１つに多対１対応させ、前記入力ビットの複数のビットシーケンスを対応する前記複数のプログラム状態に写像する動作と、
（ｂ）前記複数のメモリセルを前記対応するプログラム状態にプログラムする動作と
を実行させる、コンピュータ可読記憶媒体。
【請求項２５】
コンピュータ可読記憶媒体であって、前記コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、前記コンピュータ可読コードは、メモリセルを含み、前記メモリセルを選択的にＭ＜２ＮであるＭ個のプログラム状態にするように構成されるメモリ装置にＮ＞１であるＮ個のビットを記憶するためのコンピュータ可読コードであり、前記コンピュータ可読コードは、
（ａ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択するためのプログラムコードと、
（ｂ）前記メモリセルを前記選択されたプログラム状態にプログラムするためのプログラムコードと
を含む、コンピュータ可読記憶媒体。
【請求項２６】
コンピュータ可読記憶媒体であって、前記コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、前記コンピュータ可読コードは、複数のメモリセルを含み、前記メモリセルを選択的にＭ＜２ＮであるＭ個のプログラム状態にするように構成されるメモリ装置にＮ＞１であるＮ個のビットを記憶するためのコンピュータ可読コードであり、前記コンピュータ可読コードは、
（ａ）複数のプログラム状態の少なくとも１つを前記Ｎ個のビットの値を表す複数のビットシーケンスに対応させ、前記ビットを表すものとして前記プログラム状態のうちの１つを選択するためのプログラムコードと、
（ｂ）前記複数のメモリセルを前記選択されたプログラム状態にプログラムするためのプログラムコードと
を含む、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチビットセルフラッシュメモリに関する。
【背景技術】
【０００２】
マルチビットセル（ＭＢＰＣ：Ｍｕｌｔｉ−Ｂｉｔ−Ｐｅｒ−Ｃｅｌｌ）フラッシュメモリ装置１０の簡略ブロック図を図１に示す。特に、図１に示すフラッシュメモリ装置１０の２つの構成要素は、フラッシュコントローラ１２及びフラッシュメモリセルアレイ１８である。
【０００３】
フラッシュコントローラ１２は、２つのブロック、すなわち、ユーザがフラッシュメモリセルアレイ１８に記憶したい情報ビットストリームを、フラッシュメモリセルアレイ１８のセル内にプログラムすべき状態又は電圧レベルのストリームに変換するエンコーダブロック１４及びフラッシュセルアレイ１８から読み取られたセルの状態又は電圧レベルのストリームを、フラッシュセルアレイ１８に記憶された情報ビットストリームに変換するデコーダブロック１６を含む。
【０００４】
ＭＢＰＣフラッシュシステムのコストは、主に、所与の量の情報を記憶するために必要なフラッシュメモリセルアレイのサイズ、すなわち、所与の量の情報を記憶するために必要なフラッシュセルの数により影響を受ける。フラッシュセル１個当たりの情報ビット数（ＩＢＰＣと略される）をフラッシュメモリの費用効率の正規化された測定基準として使用することが好都合である。
ＩＢＰＣ＝（フラッシュメモリに記憶される情報ビット数）÷（フラッシュメモリのセル数）
【０００５】
ＭＢＰＣフラッシュシステムのＩＢＰＣは、単にフラッシュセル内にプログラムすることができる状態数又は電圧レベル数を増やすだけで増大させることができると主張する人がいるかもしれない。しかし、公正な比較には、ＭＢＰＣフラッシュの信頼性及びＭＢＰＣフラッシュの性能も考慮すべきである。
【０００６】
フラッシュの信頼性の主な基準は、記憶された情報を高い確率で、すなわち、無視できるビットエラーレートで復元するコントローラの能力である。フラッシュセル内にプログラムされた状態又は電圧レベルは、フラッシュセルから読み取られる状態又は電圧レベルに常に等しい訳ではない。これは、フラッシュセル内に記憶された電荷を変更させるフラッシュセルアレイ内部で発生する物理的なプロセスを原因とする。これらの有害な物理的プロセスは、フラッシュセルに記憶された情報を破壊する。通常、フラッシュの信頼性は、時間及びフラッシュセル摩耗レベルの関数である。フラッシュの信頼性は、主に、以下の要因によって決まる。
１．データ保持力：データをフラッシュセルに記憶することができ、なお且つ高い信頼性で復元することができる予想時間量
２．プログラム／消去サイクル数：信頼性のあるデータの記憶を可能にしながら、フラッシュセルをプログラムし、消去することができる予想回数
【０００７】
フラッシュの性能の主な基準は、毎秒当たりの情報ビット数で測定されるフラッシュの読み／書きスループット、すなわち、データをフラッシュメモリに書き込み、データをフラッシュメモリから読み取るスループットである。
【０００８】
不都合なことに、各フラッシュセルにプログラムすることができる電圧レベル数の増大は、フラッシュメモリの信頼性及びフラッシュメモリの性能の両方に対して負の影響を有する。例えば、電圧レベル数が増大するにつれて、フラッシュメモリの予想データ保持力が低減するとともに、利用可能なプログラム／消去サイクル予想回数が低減し、その結果としてフラッシュメモリの信頼性が低下する。さらに、フラッシュメモリの読み／書きスループットは、フラッシュセル電圧レベル数の増大に伴って遅くなる。したがって、フラッシュメモリコスト（フラッシュメモリのＩＢＰＣ）とフラッシュメモリの信頼性及び性能との間にはトレードオフがある。明らかなことに、このトレードオフの最適化が望まれる。これは、フラッシュコントローラの適切な設計を通して行うことができる。
【０００９】
単純な従来技術によるフラッシュコントローラは、ｋ個の情報ビットを各フラッシュセルのｑ＝２ｋ個の状態からの状態又は電圧レベルに直接写像するために、全単射写像、すなわち、１対１上への写像を使用する。セルに書き込める状態数を少数のｑ個のみにすることにより、状態から遷移するセルの確率が無視できるものなり、信頼性のあるフラッシュメモリ装置が提供される。このようなフラッシュメモリ装置は、ビットが全単射写像を通してセル状態に直接写像されるため、セルに２のべき乗である状態数ｑしか使用できないことに留意する。
【００１０】
２００５年１月２５日にパーク（Ｐａｒｋ）に付与され、「ＮＯＮＶＯＬＡＴＩＬＥ  ＳＥＭＩＣＯＮＤＵＣＴＯＲ  ＭＥＭＯＲＹ  ＨＡＶＩＮＧ  ＴＨＲＥＥ＿ＬＥＶＥＬ  ＭＥＭＯＲＹ  ＣＥＬＬＳ  ＡＮＤ  ＰＲＯＧＲＡＭ  ＡＮＤ  ＲＥＡＤ  ＭＡＰＰＩＮＧ  ＣＩＲＣＵＩＴＳ  ＴＨＥＲＥＦＯＲ」という名称の米国特許第６，８４７，５５０号明細書（以下、「パーク（Ｐａｒｋ）’５５０号」とする）には、情報ビットから１つ又は複数のフラッシュセルの状態への１対１であるが１対１上ではない非全単射写像を使用して、フラッシュコストと信頼性とをトレードオフする方法が記載されている。非全単射写像を使用することにより、２のべき乗ではないセル状態数を使用することができる。パーク（Ｐａｒｋ）’５５０に述べられている例では、３状態セルが使用されている。これは、４状態セルに基づくフラッシュメモリ装置と比較して高いフラッシュ信頼性を提供し（状態間遷移の確率がより低いことによる）、かつ２状態セルに基づくフラッシュメモリ装置と比較して低いコストを提供する。
【００１１】
２００２年１０月２２日にバン（Ｂａｎ）等に発行され、「ＭＥＴＨＯＤ  ＦＯＲ  ＩＮＣＲＥＡＳＩＮＧ  ＩＮＦＯＲＭＡＴＩＯＮ  ＣＯＮＴＥＮＴ  ＩＮ  Ａ  ＣＯＭＰＵＴＥＲ  ＭＥＭＯＲＹ」という名称の米国特許第６，４６９，９３１号明細書（以下、「バン（Ｂａｎ）’９３１号」とする）は、フラッシュメモリ装置の信頼性を維持しながらフラッシュメモリ装置のコストを低減する全般的な枠組みを提供する。これは、Ｋ個の情報ビットの大きなブロックを、ｑ個の状態を有するＭ個のセルの大きなブロックに写像することにより行われる。エンコーダブロック（例えば、図１のエンコーダブロック１４）は、ベクトル空間２ｋからの点をベクトル空間ｑＭ内の点上に写像する、誤り訂正符号（ＥＣＣ）としても既知の写像関数を実施する。この写像は全射ではない。すなわち、セル状態のすべての構成が使用される訳ではない（２Ｋ＜ｑＭ）。デコーダブロック（例えば、図１のデコーダブロック１６）は、Ｍ個の読み取られたセル状態をまとめて復号化し、フラッシュメモリに記憶されたセル状態の正当である可能性の最も高い構成を判断し、次に、この構成がＫ個の記憶された情報ビットの復元に使用される。情報理論及び符号化理論（Ｒ．ギャラガー（Ｇａｌｌａｇｈｅｒ）、Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ａｎｄ  Ｒｅｌｉａｂｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ、ワイリー（Ｗｉｌｅｙ）、ニューヨーク（Ｎｅｗ  Ｙｏｒｋ）、ＮＹ  ＵＳＡ、１９７１年）から、情報ビットブロックが写像される可能なセル状態構成空間の次元を増大することにより、情報のより効率的な記憶が可能なことが周知である。この方法は、良好な写像関数又はＥＣＣが使用される場合、フラッシュメモリが状態の正当なある構成から別の構成に遷移する確率を適宜低く保ちながら、より多数の情報ビットを所与の数のフラッシュメモリセルにわたって写像することができる。しかし、写像関数が高いＩＢＰＣを提供するだけでは十分ではない。写像関数は、エンコーダ及びデコーダの各ブロックの複雑性の低い実施も可能にすべきである。符号化理論（Ｓ．リン（Ｌｉｎ）及びＤ．Ｊ．コステロ（Ｃｏｓｔｅｌｌｏ）、Ｅｒｒｏｒ  Ｃｏｎｔｒｏｌ  Ｃｏｄｉｎｇ：Ｆｕｎｄａｍｅｎｔａｌｓ  ａｎｄ  Ａｐｐｌｉｃｔｉｏｎｓ、プレンティスホール（Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ）、イングルウッドクリフ（Ｅｎｇｌｅｗｏｏｄ  Ｃｌｉｆｆｓ）、ＮＪ、ＵＳＡ、１９８３年）は、このような良好なＥＣＣを設計する理論的な基礎を提供する。
【００１２】
バン（Ｂａｎ）’９３１号において提供される例では、情報ビットをセル状態の構成に写像するために、直接写像関数が使用される。この方法は、高いエンコーダ複雑性を招く。図２に示すより一般的な複雑性の低い手法は、エンコーダブロック１４を２つの部分、すなわち、１）Ｎ−Ｋ個の冗長ビットを追加することによりＫ個の情報ビットをＮ個の符号化ビットに写像するバイナリＥＣＣエンコーダブロック２０、及び２）各Ｎ／Ｍ個のビットをセルのｑ＝２Ｎ／Ｍ個の状態のうちの１つに写像することにより、Ｎ個の符号化ビットをＭ個のセルに写像する１次元全単射写像関数を実施する簡易マッパブロック２２に分けることである。
【００１３】
デコーダブロック１６も２つの部分、すなわち、１）読み取られた各セル状態をＮ／Ｍビットに写像することにより、読み取られたＭ個のセル状態をＮビットに写像する１次元全単射写像関数を実施する簡易デマッパブロック２４、及び２）デマッパ２４から受け取ったＮ個の「ノイジー（ｎｏｉｓｙ）」ビットを復号化し、Ｋ個の情報ビットの推定を生成するＥＣＣデコーダブロック２６に分けられる。最適なデコーダ２６は、与えられたＮ個の「ノイジー」ビットに対して最も確率の高いＫ個の情報ビットを返す。
【発明の開示】
【課題を解決するための手段】
【００１４】
本発明のフラッシュコントローラは、ＥＣＣと低次元非全単射写像との組み合わせを使用して、フラッシュのコスト、信頼性、及び性能の間での最適なトレードオフを実現する複雑性の低い解決策を提供する。さらに、本発明のフラッシュコントローラは、フラッシュシステムの設計に非常に高い柔軟性を提供し、フラッシュセルにおいて、必ずしも２のべき乗である必要はない任意の数の状態又は電圧レベルをサポートする。ＥＣＣと非全単射マッパとの組み合わせにより、所与のＭＢＰＣフラッシュ技術及び所与の性能、コスト、及び／又は信頼性の各要件に対して複雑性の低い最適な解決策を設計することができる。より具体的には、
・所与のフラッシュ信頼性の場合に、本発明のフラッシュコントローラは、従来技術によるコントローラと比較してより低いフラッシュコスト及び／又はより高いフラッシュ性能を提供する。
・所与のフラッシュコストの場合に、本発明のフラッシュコントローラは、従来技術によるコントローラと比較してより良いフラッシュ信頼性及び／又はより高いフラッシュ性能を提供する。
・所与のフラッシュ性能の場合に、本発明のフラッシュコントローラは、従来技術によるコントローラと比較してより低いフラッシュコスト及び／又はより良いフラッシュ信頼性を提供する。
【００１５】
本発明のコントローラは、非全単射マッパ、すなわち、写像が１対１ではないか、全射ではないか、又は１対１でもなければ全射でもないマッパを使用する。さらに、写像は低次元であるが、必ずしも１次元である必要はない。すなわち、写像は、必ずしも単一のセルのみに対して実行する必要はなく、いくつかのセルに対して実行することができる。非全単射写像により、セルにおいて２のべき乗ではない数の電圧レベルを使用することができる。非全単射写像により、セルのプログラムされる状態又は電圧レベルにわたって同じではない確率にすることも可能になる。追加の自由度を使用して、フラッシュメモリ装置の特徴を最適化することができる。
【００１６】
ｆが本発明により使用される非全単射写像関数を示すものとする。ｆは、長さｋのバイナリシーケンスを長さｍのｑ元シーケンスへの写像である。すなわち、ｆ：２ｋ→ｑｍである。ｆは非全単射であるため、２ｋ≠ｑｍである。したがって、ｆが１対１ではない（が、全射である）場合、２ｋ＞ｑｍであり、ｆが全射ではない（が、１対１である）場合、２ｋ＜ｑｍである。本明細書では、長さｍのｑ元シーケンスを構成（ｃｏｎｆｉｇｕｒａｔｉｏｎ）と呼ぶ。構成は、ｑ個の状態を有するｍ個のセルに記憶又はプログラムされる。本明細書では、ｆにより写像された構成を正当な構成（ｌｅｇｉｔｉｍａｔｅ  ｃｏｎｆｉｇｕｒａｔｉｏｎ）と呼ぶ。
【００１７】
以下の説明では、ある状態から別の状態への望ましくない遷移の確率の尺度を使用する必要がある。フラッシュメモリセルでは、２つの状態の閾値電圧範囲が共に近いほど、２つの状態間での遷移確率は高くなる場合が典型的である。したがって、本明細書では、用語「隣接状態」を、閾値電圧軸上で隣接する状態を指すために使用する。換言すれば、２つの状態は、閾値電圧がこれら２つの状態の閾値電圧間にあるセルの他の状態がない場合のみ、互いに隣接する。この定義は、隣接性を反射関係として解釈することも暗に示し、Ｓ１がＳ２に隣接する場合、Ｓ２はＳ１に隣接する。
【００１８】
上記考察では、フラッシュメモリセルが、セルのすべての状態が閾値電圧レベルでのみ異なる「導電性浮遊ゲート」型のものであると仮定していることに留意する。非導電性浮遊ゲートを使用するフラッシュメモリ技術があり、例は、イスラエル、ネタニヤフ（Ｎｅｔａｎｙａｈ）に所在のサイファンセミコンダクターズ（Ｓａｉｆｕｎ  Ｓｅｍｉｃｏｎｄｕｃｔｏｒｓ）からのＮＲＯＭメモリ及び米国カリフォルニア州サニーベール（Ｓｕｎｎｙｖａｌｅ）に所在のスパンション社（Ｓｐａｎｓｉｏｎ  Ｉｎｃ．）からのミラービット（ＭｉｒｒｏｒＢｉｔ）メモリである。このようなフラッシュメモリでは、セルの状態は、一緒になってセルの状態を表すゲート内の複数の場所に存在する電荷に起因する閾値電圧の複数（通常は２つ）の値の組み合わせに対応する。本発明では、このようなフラッシュセルは、各電荷がそれぞれの「隣接状態」の概念で別個の閾値電圧を定義する別個の複数のセルとしてみなされる。したがって、例えば、ゲートの２つの両端部に２つの電荷を有し、各電荷を４つの異なる状態にする（ひいては、セルへの４ビット記憶をサポートする）ことが可能なＮＲＯＭセルは、本発明では、それぞれが２ビットを記憶可能な２個のセルに等しいとみなされる。
【００１９】
本明細書では、２つの構成Ｑ１及びＱ２は、これら２つの構成が単一のセルの状態のみで異なり、セルの２つの異なる状態が隣接する場合に隣接構成であると言う。換言すれば、２つの構成は、一方の構成ではｉ番目のセルの状態がＳ１であり、他方の構成ではｉ番目のセルの状態がＳ２であり、かつ状態Ｓ２が状態Ｓ１に隣接するようにｉ番目のセルの状態のみが異なる場合に隣接する。
【００２０】
１対１の写像ｆが、任意の２つの正当な隣接する構成Ｑ１及びＱ２に対して、バイナリシーケンスｆ−１（Ｑ１）及びｆ−１（Ｑ２）が単一ビットにおいてのみ異なる場合、一般化グレイ写像であると言う。
【００２１】
本発明のいくつかの実施形態では、一般化グレイ写像はビットエラーレートを最小に抑えるため、コントローラにおいて一般化グレイ写像を使用することが望ましい。フラッシュメモリ内のセルの状態で起こり得る遷移は少数の誤りビットを発生させるが、これら誤りビットはＥＣＣにより高い確率で修正することが可能である。
【００２２】
本発明の一実施形態によれば、コントローラは１対１ではない写像を利用する。予想ビットエラーレートを最小に抑える写像を使用することが望ましい。非全単射写像を適切なＥＣＣと組み合わせることにより、フラッシュ装置のコストと、信頼性と、性能とのトレードオフを最適化することができる。
【００２３】
本発明の別の実施形態によれば、コントローラは全射ではない一般化グレイ写像を利用する。非全単射写像を適切なＥＣＣと組み合わせることにより、フラッシュ装置のコストと、信頼性と、性能とのトレードオフを最適化することができる。
【００２４】
本発明の別の実施形態によれば、コントローラは１対１でもなければ全射でもない写像を利用する。非全単射写像を適切なＥＣＣと組み合わせることにより、フラッシュ装置のコストと、信頼性と、性能とのトレードオフを最適化することができる。
【００２５】
従来技術によるコントローラは、１次元全単射マッパ、すなわち、単一セルの可能なすべての電圧レベルへのバイナリシーケンスの１対１の写像を使用するマッパを使用する。したがって、従来技術によるコントローラは、２のべき乗であるプログラミング電圧レベル数しか使用することができない。さらに、従来技術によるコントローラは、ランダムデータがフラッシュメモリに書き込まれる場合、セル電圧レベルにわたって等しい確率を利用する。換言すれば、フラッシュメモリに書き込まれた各情報ビットが０である確率又は１である確率が等しいと仮定すると、フラッシュコントローラによりフラッシュセルにあらゆる電圧レベルがプログラムされる確率も同様に確からしい。
【００２６】
従来技術によるコントローラと異なり、本発明のコントローラは非全単射マッパ、すなわち、写像が１対１ではないか、全射ではないか、又は１対１でもなければ全射でもないマッパを使用する。さらに、写像は低次元であるが、必ずしも１次元である必要はない。すなわち、写像は、必ずしも単一のセルのみに対して実行する必要はなく、いくつかのセルに対して実行することができる。非全単射写像により、セルにおいて２のべき乗ではない数の電圧レベルを使用することができる。非全単射写像により、セルのプログラムされる状態又は電圧レベルにわたって同じではない確率にすることも可能になる。追加の自由度を使用して、フラッシュメモリ装置の特徴を最適化することができる。
【００２７】
全射ではない写像はパーク（Ｐａｒｋ）’５５０号でも使用される。しかし、パーク（Ｐａｒｋ）’５５０号において使用される写像は一般化グレイ写像ではない。
【００２８】
したがって、本発明によれば、複数の入力ビットを記憶する方法であって、（ａ）多対１写像を使用して入力ビットをメモリセルの対応するプログラム状態に写像するステップと、（ｂ）メモリセルを対応するプログラム状態にプログラムするステップとを含む、方法が提供される。
【００２９】
さらに、本発明によれば、複数の入力ビットを記憶する方法であって、（ａ）多対１写像を使用して入力ビットを複数のメモリセルの対応するプログラム状態に写像するステップと、（ｂ）メモリセルを対応するプログラム状態にプログラムするステップとを含む、方法が提供される。
【００３０】
さらに、本発明によれば、複数の入力ビットを記憶する方法であって、（ａ）写像を使用して入力ビットを少なくとも１つのメモリセルの対応するプログラム状態に写像するステップであって、写像は、（ｉ）中への写像、及び（ｉｉ）一般化グレイ写像である、写像するステップと、（ｂ）少なくとも１つのメモリセルを対応するプログラム状態にプログラムするステップとを含む、方法が提供される。
【００３１】
さらに、本発明によれば、メモリ装置であって、（ａ）セルと、（ｂ）コントローラであって、（ｉ）多対１写像を使用してビットをセルの対応するプログラム状態に写像すること、及び（ｉｉ）セルを対応するプログラム状態にプログラムすることにより複数のビットをセルに記憶するように動作可能なコントローラとを含む、メモリ装置が提供される。
【００３２】
さらに、本発明によれば、複数のビットを記憶するシステムであって、（ａ）セルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）多対１写像を使用してビットをセルの対応するプログラム状態に写像し、（ｉｉ）セルを対応するプログラム状態にプログラムするように動作可能なプロセッサとを含む、システムが提供される。
【００３３】
さらに、本発明によれば、メモリ装置であって、（ａ）複数のセルと、（ｂ）コントローラであって、（ｉ）多対１写像を使用してビットをセルの対応するプログラム状態に写像し、（ｉｉ）セルを対応するプログラム状態にプログラムすることにより複数のビットをセルに記憶するように動作可能なコントローラとを含む、メモリ装置が提供される。
【００３４】
さらに、本発明によれば、複数のビットを記憶するシステムであって、（ａ）複数のセルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）多対１写像を使用してビットをセルの対応するプログラム状態に写像し、（ｉｉ）セルを対応するプログラム状態にプログラムするように動作可能なプロセッサとを含む、システムが提供される。
【００３５】
さらに、本発明によれば、メモリ装置であって、（ａ）少なくとも１つのセルと、（ｂ）コントローラであって、（ｉ）写像を使用してビットを少なくとも１つのセルの対応するプログラム状態に写像することであって、写像は、（Ａ）中への写像、及び（Ｂ）一般化グレイ写像である、写像すること、及び（ｉｉ）少なくとも１つのセルを対応するプログラム状態にプログラムすることにより複数のビットを少なくとも１つのセルに記憶するように動作可能なコントローラとを含む、メモリ装置が提供される。
【００３６】
さらに、本発明によれば、複数のビットを記憶するシステムであって、（ａ）少なくとも１つのセルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）写像を使用してビットを少なくとも１つのセルの対応するプログラム状態に写像することであって、写像は、（Ａ）中への写像、及び（Ｂ）一般化グレイ写像である、写像すること、及び（ｉｉ）少なくとも１つのセルを対応するプログラム状態にプログラムすることを行うように動作可能なプロセッサとを含む、システムが提供される。
【００３７】
さらに、本発明によれば、Ｎ＞１個のビットを記憶する方法であって、（ａ）メモリセルを含むメモリ装置を、メモリセルを選択的にＭ＜２Ｎ個のプログラム状態にするように構成するステップと、（ｂ）ビットを表すものとしてプログラム状態のうちの１つを選択するステップと、（ｃ）メモリセルを選択されたプログラム状態にプログラムするステップとを含む、方法が提供される。
【００３８】
さらに、本発明によれば、Ｎ＞１個のビットを記憶する方法であって、（ａ）複数のメモリセルを含むメモリ装置を、メモリセルを選択的にＭ＜２Ｎ個のプログラム状態にするように構成するステップと、（ｂ）ビットを表すものとしてプログラム状態のうちの１つを選択するステップと、（ｃ）メモリセルを選択されたプログラム状態にプログラムするステップとを含む、方法が提供される。
【００３９】
さらに、本発明によれば、２つの複数ビットを記憶する方法であって、各複数ビットは異なる二進整数をそれぞれ表し、方法は、（ａ）各複数ビットを各メモリセルの対応するプログラム状態に写像するステップと、（ｂ）各メモリセルを対応するプログラム状態にプログラムするステップであって、プログラム状態は同一である、プログラムするステップとを含む、方法が提供される。
【００４０】
さらに、本発明によれば、２つの複数ビットを記憶する方法であって、各複数ビットは異なる二進整数をそれぞれ表し、方法は、（ａ）各複数ビットを各複数メモリセルの対応するプログラム状態に写像するステップと、（ｂ）各複数メモリセルを対応するプログラム状態にプログラムするステップであって、プログラム状態は同一である、プログラムするステップとを含む、方法が提供される。
【００４１】
さらに、本発明によれば、Ｎ＞１個のビットを記憶する方法であって、（ａ）少なくとも１つのメモリセルを含むメモリ装置を、少なくとも１つのメモリセルを選択的にＭ＞２Ｎ個のプログラム状態にするように構成するステップと、（ｂ）一般化グレイ写像に従ってビットを表すものとしてプログラム状態のうちの１つを選択するステップと、（ｃ）少なくとも１つのメモリセルを選択されたプログラム状態にプログラムするステップであって、プログラム状態のうちの少なくとも１つは選択から除外される、プログラムするステップとを含む、方法が提供される。
【００４２】
さらに、本発明によれば、Ｎ＞１個のビットを記憶するメモリ装置であって、（ａ）セルと、（ｂ）コントローラであって、（ｉ）セルを選択的にＭ＜２Ｎ個のプログラム状態にすること、及び（ｉｉ）（Ａ）ビットを表すものとしてプログラム状態のうちの１つを選択すること、及び（Ｂ）セルを選択されたプログラム状態にプログラムすること、によりビットをセルに記憶することを行うように動作可能なコントローラとを含む、メモリ装置が提供される。
【００４３】
さらに、本発明によれば、Ｎ＞１個のビットを記憶するシステムであって、（ａ）セルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）セルを選択的にＭ＜２Ｎ個のプログラム状態にすること、及び（ｉｉ）（Ａ）ビットを表すものとしてプログラム状態のうちの１つを選択すること、及び（Ｂ）セルを選択されたプログラム状態にプログラムすること、によりビットをセルに記憶することを行うように動作可能なプロセッサとを含む、システムが提供される。
【００４４】
さらに、本発明によれば、Ｎ＞１個のビットを記憶するメモリ装置であって、（ａ）複数のセルと、（ｂ）コントローラであって、（ｉ）セルを選択的にＭ＜２Ｎ個のプログラム状態にすること、及び（ｉｉ）（Ａ）ビットを表すものとしてプログラム状態のうちの１つを選択すること、及び（Ｂ）セルを選択されたプログラム状態にプログラムすること、によりビットをセルに記憶することを行うように動作可能なコントローラとを含む、メモリ装置が提供される。
【００４５】
さらに、本発明によれば、Ｎ＞１個のビットを記憶するシステムであって、（ａ）複数のセルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）セルを選択的にＭ＜２Ｎ個のプログラム状態にすること、及び（ｉｉ）（Ａ）ビットを表すものとしてプログラム状態のうちの１つを選択すること、及び（Ｂ）セルを選択されたプログラム状態にプログラムすること、によりビットをセルに記憶することを行うように動作可能なプロセッサとを含む、システムが提供される。
【００４６】
さらに、本発明によれば、メモリ装置であって、（ａ）２つのセルと、（ｂ）コントローラであって、（ｉ）各複数ビットをセルのそれぞれ１つの対応するプログラム状態に写像すること、及び（ｉｉ）各セルを対応するプログラム状態にプログラムすることにより２つの複数ビットを記憶するように動作可能なコントローラとを含み、各複数ビットは異なる二進整数をそれぞれ表し、プログラム状態は同一である、メモリ装置が提供される。
【００４７】
さらに、本発明によれば、２つの複数ビットを記憶するシステムであって、各複数ビットは異なる二進整数をそれぞれ表し、システムは、（ａ）２つのセルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）各複数ビットをセルのそれぞれ１つの対応するプログラム状態に写像すること、及び（ｉｉ）各セルを対応するプログラム状態にプログラムすることを行うように動作可能であり、プログラム状態は同一である、プロセッサとを含む、システムが提供される。
【００４８】
さらに、本発明によれば、メモリ装置であって、（ａ）２つの複数セルと、（ｂ）コントローラであって、（ｉ）各複数ビットを複数セルのそれぞれ１つの対応するプログラム状態に写像すること、及び（ｉｉ）各複数セルを対応するプログラム状態にプログラムすることにより２つの複数ビットを記憶するように動作可能なコントローラとを含み、各複数ビットは異なる二進整数をそれぞれ表し、プログラム状態は同一である、メモリ装置が提供される。
【００４９】
さらに、本発明によれば、２つの複数ビットを記憶するシステムであって、各複数ビットは異なる二進整数をそれぞれ表し、システムは、（ａ）２つの複数セルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）各複数ビットを複数セルのそれぞれ１つの対応するプログラム状態に写像すること、及び（ｉｉ）各複数セルを対応するプログラム状態にプログラムすることを行うように動作可能なコントローラとを含み、プログラム状態は同一である、システムが提供される。
【００５０】
さらに、本発明によれば、Ｎ＞１個のビットを記憶するメモリ装置であって、（ａ）少なくとも１つのセルと、（ｂ）コントローラであって、（ｉ）少なくとも１つのセルを選択的にＭ＞２Ｎ個のプログラム状態にすること、（ｉｉ）一般化グレイ写像に従ってビットを表すものとしてプログラム状態のうちの１つを選択すること、及び（ｉｉｉ）少なくとも１つのセルを選択されたプログラム状態にプログラムすることを行うように動作可能なコントローラとを含み、プログラム状態のうちの少なくとも１つは、選択することから除外される、メモリ装置が提供される。
【００５１】
さらに、本発明によれば、Ｎ＞１個のビットを記憶するシステムであって、（ａ）少なくとも１つのセルを含むメモリ装置と、（ｂ）プロセッサであって、（ｉ）少なくとも１つのセルを選択的にＭ＞２Ｎ個のプログラム状態にすること、（ｉｉ）一般化グレイ写像に従ってビットを表すものとしてプログラム状態のうちの１つを選択すること、及び（ｉｉｉ）少なくとも１つのセルを選択されたプログラム状態にプログラムすることを行うように動作可能なプロセッサとを含み、プログラム状態のうちの少なくとも１つは、選択することから除外される、システムが提供される。
【００５２】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化される、複数の入力ビットを記憶するためのコンピュータ可読コードを有し、コンピュータ可読コードは、（ａ）多対１写像を使用して入力ビットをメモリセルの対応するプログラム状態に写像するためのプログラムコードと、（ｂ）メモリセルを対応するプログラム状態にプログラムするためのプログラムコードとを含む、コンピュータ可読記憶媒体が提供される。
【００５３】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化される、複数の入力ビットを記憶するためのコンピュータ可読コードを有し、コンピュータ可読コードは、（ａ）多対１写像を使用して入力ビットを複数のメモリセルの対応するプログラム状態に写像するためのプログラムコードと、（ｂ）メモリセルを対応するプログラム状態にプログラムするためのプログラムコードとを含む、コンピュータ可読記憶媒体が提供される。
【００５４】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化される、複数の入力ビットを記憶するためのコンピュータ可読コードを有し、コンピュータ可読コードは、（ａ）写像を使用して入力ビットを少なくとも１つのメモリセルの対応するプログラム状態に写像するためのプログラムコードであって、写像は、（ｉ）中への写像、及び（ｉｉ）一般化グレイ写像である、写像するためのプログラムコードと、（ｂ）少なくとも１つのメモリセルを対応するプログラム状態にプログラムするためのプログラムコードとを含む、コンピュータ可読記憶媒体が提供される。
【００５５】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、コンピュータ可読コードは、メモリセルを含み、メモリセルを選択的にＭ＜２Ｎ個のプログラム状態にするように構成されるメモリ装置にＮ＞１個のビットを記憶するためのコンピュータ可読コードであり、コンピュータ可読コードは、（ａ）ビットを表すものとしてプログラム状態のうちの１つを選択するためのプログラムコードと、（ｂ）メモリセルを選択されたプログラム状態にプログラムするためのプログラムコードとを含む、コンピュータ可読記憶媒体が提供される。
【００５６】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、コンピュータ可読コードは、複数のメモリセルを含み、メモリセルを選択的にＭ＜２Ｎ個のプログラム状態にするように構成されるメモリ装置にＮ＞１個のビットを記憶するためのコンピュータ可読コードであり、コンピュータ可読コードは、（ａ）ビットを表すものとしてプログラム状態のうちの１つを選択するためのプログラムコードと、（ｂ）メモリセルを選択されたプログラム状態にプログラムするためのプログラムコードとを含む、コンピュータ可読記憶媒体が提供される。
【００５７】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、コンピュータ可読コードは２つの複数ビットを記憶するためのコンピュータ可読コードであり、各複数ビットは異なる二進整数をそれぞれ表し、コンピュータ可読コードは、（ａ）各複数ビットを各メモリセルの対応するプログラム状態に写像するためのプログラムコードと、（ｂ）各メモリセルを対応するプログラム状態にプログラムするためのプログラムコードとを含み、プログラム状態は同一である、コンピュータ可読記憶媒体が提供される。
【００５８】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、コンピュータ可読コードは２つの複数ビットを記憶するためのコンピュータ可読コードであり、各複数ビットは異なる二進整数をそれぞれ表し、コンピュータ可読コードは、（ａ）各複数ビットを各複数メモリセルの対応するプログラム状態に写像するためのプログラムコードと、（ｂ）各複数メモリセルを対応するプログラム状態にプログラムするためのプログラムコードとを含み、プログラム状態は同一である、コンピュータ可読記憶媒体が提供される。
【００５９】
さらに、本発明によれば、コンピュータ可読記憶媒体であって、コンピュータ可読記憶媒体において具体化されるコンピュータ可読コードを有し、コンピュータ可読コードは、少なくとも１つのメモリセルを含み、少なくとも１つのメモリセルを選択的にＭ＞２Ｎ個のプログラム状態にするように構成されるメモリ装置にＮ＞１個のビットを記憶するためのコンピュータ可読コードであり、コンピュータ可読コードは、（ａ）一般化グレイ写像に従ってビットを表すものとしてプログラム状態のうちの１つを選択するためのプログラムコードと、（ｂ）少なくとも１つのメモリセルを選択されたプログラム状態にプログラムするためのプログラムコードとを含み、プログラム状態のうちの少なくとも１つは、選択することから除外される、コンピュータ可読記憶媒体が提供される。
【００６０】
本発明の第１の基本的な方法は、複数の入力ビットを記憶する方法である。多対１写像が、入力ビットをメモリセルの対応するプログラム状態に写像するために使用される。次に、メモリセルはその対応するプログラム状態にプログラムされる。従来、データをフラッシュメモリセルに書き込むことは、セルを「プログラムする」ことと呼ばれている。本発明の主に対象とする用途はフラッシュメモリであるため、本明細書では、１つ又は複数のセルを「プログラム」するという用語を、データをセルに書き込むことを意味するために使用するが、本発明の範囲はフラッシュメモリのみならずメモリ全般を含む。
【００６１】
好ましくは、写像は、入力ビットを１つ又は複数の符号語として符号化すること、及び、次に、符号語をメモリセルの対応するプログラム状態に写像することを含むステップにより行われる。符号化は系統的符号化であってもよく、又は非系統的符号化であってもよい。
【００６２】
好ましくは、メモリセルはフラッシュメモリセルであり、プログラム状態はセルの閾値電圧状態である。すなわち、セルは、セルの閾値電圧をそのセルに定義された閾値電圧範囲セットのうちの１つに設定することによりプログラムされる。
【００６３】
好ましくは、本方法は、メモリセルを読み取ることであって、それにより、読み取り状態値を得る、読み取ること、及び、次に、読み取り状態値を複数の出力ビットに変換することを含む。読み取り状態値が必ずしもプログラム状態の値と同じである必要はないことに留意する。読み取り値状態値を出力ビットに変換する最も好ましい一方法は、最尤復号化を含む。読み取り状態値を出力ビットに変換する別の最も好ましい方法は、読み取り状態値を複数のソフトビット推定に写像すること、及び、次に、ソフトビット推定を復号化することを含む。
【００６４】
別法として、写像は、入力ビットを複数の入力符号語として符号化することを含む。読み取り状態値を出力ビットに変換するシーケンスは、読み取り状態値を複数の出力符号語に写像することを含み、各出力符号語は、入力符号語のうちの１つに一意に対応する。換言すれば、入力符号語と出力符号語との間に１：１の対応がある。次に、出力語が順次復号化され、最初の出力符号語に続く各出力符号語の復号化は、少なくとも部分的に、少なくとも１つの先行符号語の復号化結果に基づく。この最も好ましい実施形態の一例を付録Ｅにおいて後述する。
【００６５】
本発明の第２の基本的な方法は、複数の入力ビットを記憶する方法である。多対１写像が、入力ビットを複数のメモリセルの対応するプログラム状態に写像するために使用される。このプログラム状態が、一緒に考慮されるセルの集合状態であることに留意する。次に、メモリセルはその対応するプログラム状態にプログラムされる。
【００６６】
好ましくは、写像は、入力ビットを１つ又は複数の符号語として符号化すること、及び、次に、符号語をメモリセルの対応するプログラム状態に写像することを含むステップにより行われる。符号化は系統的符号化であってもよく、又は非系統的符号化であってもよい。
【００６７】
好ましくは、メモリセルはフラッシュメモリセルであり、プログラム状態はセルの閾値電圧状態である。すなわち、セルは、セルの閾値電圧をそのセルに定義された集合的な閾値電圧範囲セットのうちの１つに設定することによりプログラムされる。
【００６８】
好ましくは、本方法は、メモリセルを読み取ることであって、それにより、読み取り状態値を得る、読み取ること、及び、次に、読み取り状態値を複数の出力ビットに変換することを含む。読み取り値状態値を出力ビットに変換する最も好ましい一方法は、最尤復号化を含む。読み取り状態値を出力ビットに変換する別の最も好ましい方法は、読み取り状態値を複数のソフトビット推定に写像すること、及び、次に、ソフトビット推定を復号化することを含む。
【００６９】
別法として、写像は、入力ビットを複数の入力符号語として符号化することを含む。読み取り状態値を出力ビットに変換するシーケンスは、読み取り状態値を複数の出力符号語に写像することを含み、各出力符号語は、入力符号語のうちの１つに一意に対応する。換言すれば、入力符号語と出力符号語との間に１：１の対応がある。次に、出力語が順次復号化され、最初の出力符号語に続く各出力符号語の復号化は、少なくとも部分的に、少なくとも１つの先行符号語の復号化結果に基づく。この最も好ましい実施形態の一例を付録Ｅにおいて後述する。
【００７０】
本発明の第３の基本的な方法は、複数の入力ビットを記憶する方法である。入力ビットは、中への写像であり、かつ一般化グレイ写像の両方である写像を使用して、１つ又は複数のメモリセル（好ましくは２個以上のメモリセル）に写像される。写像が「中への」写像であることは、写像が１対１であるが、可能なプログラム状態のうちの１つ又は複数が写像されずに残ることを意味する。次に、メモリセルはその対応するプログラム状態にプログラムされる。
【００７１】
好ましくは、メモリセルはフラッシュメモリセルであり、プログラム状態はそのセルの閾値電圧状態である。
【００７２】
好ましくは、本方法は、メモリセルを読み取ることであって、それにより、読み取り状態値を得る、読み取ること、及び、次に、読み取り状態値を複数の出力ビットに変換することを含む。読み取り値状態値を出力ビットに変換する最も好ましい一方法は、最尤復号化を含む。読み取り状態値を出力ビットに変換する別の最も好ましい方法は、読み取り状態値を複数のソフトビット推定に写像すること、及び、次に、ソフトビット推定を復号化することを含む。
【００７３】
別法として、写像は、入力ビットを複数の入力符号語として符号化することを含む。読み取り状態値を出力ビットに変換するシーケンスは、読み取り状態値を複数の出力符号語に写像することを含み、各出力符号語は、入力符号語のうちの１つに一意に対応する。換言すれば、入力符号語と出力符号語との間に１：１の対応がある。次に、出力語が順次復号化され、最初の出力符号語に続く各出力符号語の復号化は、少なくとも部分的に、少なくとも１つの先行符号語の復号化結果に基づく。この最も好ましい実施形態の一例を付録Ｅにおいて後述する。
【００７４】
本発明の第４の方法は、Ｎ＞１個のビットを記憶する方法である。メモリセルを含むメモリ装置が、メモリセルを選択的にＭ＞２Ｎ個の状態にするように構成される。プログラム状態のうちの１つが、ビットを表すものとして選択され、メモリセルは、選択されたプログラム状態にプログラムされる。
【００７５】
本発明の第５の方法は、Ｎ＞１個のビットを記憶する方法である。複数のメモリセルを含むメモリ装置が、メモリセルを選択的にＭ＞２Ｎ個の状態にするように構成される。プログラム状態のうちの１つが、ビットを表すものとして選択され、メモリセルは、選択されたプログラム状態にプログラムされる。
【００７６】
本発明の第６の方法は、２つの異なる各二進整数を表す２つの複数ビットを記憶する方法である。各複数ビットは、各メモリセルの対応するプログラム状態に写像され、各メモリセルは対応するプログラム状態にプログラムされる。２つのプログラム状態は同一である。例えば、以下の表２では、整数３の二進表現である複数ビット１１及び整数２の二進表現である複数ビット１０は両方とも、電圧レベル２に写像される。
【００７７】
本発明の第７の方法は、２つの異なる二進整数をそれぞれ表す２つの複数ビットを記憶する方法である。各複数ビットは、各複数メモリセルの対応するプログラム状態に写像され、各複数メモリセルは対応するプログラム状態にプログラムされる。２つのプログラム状態は同一である。
【００７８】
本発明の第８の方法は、Ｎ＞１個のビットを記憶する方法である。１つ又は複数のメモリセルを含むメモリ装置が、メモリセルを選択的にＭ＞２Ｎ個のプログラム状態にするように構成される。プログラム状態のうちの１つが、一般化グレイ写像に従ってビットを表すものとして選択される。セルは選択されたプログラム状態にプログラムされる。プログラム状態のうちの少なくとも１つは、選択することから除外される。例えば、以下の表６では、「１，１」電圧レベルが選択することから除外される。
【００７９】
本発明の範囲は、これら方法を実施するメモリ装置及びシステムも含む。第６及び第７の方法を実施するメモリ装置及びシステムでは、２つの複数ビットが順次記憶される場合、両方の複数ビットの記憶に同じセル（第６の方法）又は同じ複数セル（第７の方法）を使用できることに留意する。２つの複数ビットが同時に記憶される場合、２つのセル（第６の方法）又は２つの複数セル（第７の方法）は異なるものでなければならない。
【００８０】
本発明の範囲は、本発明の方法を実施するためのコンピュータ可読コードが具体化されたコンピュータ可読記憶媒体も含む。
【００８１】
本発明を本明細書において添付図面を参照しながら単なる例として説明する。
【発明を実施するための最良の形態】
【００８２】
本発明によるフラッシュメモリコントローラの原理及び動作は、図面及び添付の説明を参照することでよりよく理解することができる。
【００８３】
所与のフラッシュ技術及び所与のフラッシュ信頼性要件に関して、所与のフラッシュコントローラが所与のサイズのフラッシュメモリに記憶することができるビット数には上限がある。すなわち、フラッシュ装置の達成可能なＩＢＰＣには上限がある。本明細書では、フラッシュ装置のＩＢＰＣに対するこの上限を装置のフラッシュ容量と呼ぶ。
【００８４】
所与のフラッシュ信頼性の場合のフラッシュ容量は、フラッシュ技術の物理モデルが分かっている場合、情報理論からツールを使用して計算することができる。より具体的には、所与の電圧レベルがセルにプログラムされたと仮定して、各電圧レベルを読み取る確率を知る必要がある。フラッシュメモリの容量を計算する方法は、付録Ａに述べられている。さらに、情報理論は、コントローラの複雑性が制限されない場合、フラッシュ容量を達成できることも保証する。これは、フラッシュデータを保護するために長さを増大させたランダムＥＣＣを使用することによって行うことができる。フラッシュコントローラを使用したこのようなコードの符号化及び復号化の複雑性は、極めて高い。しかし、符号化及び復号化の複雑性の低い実用的な符号化技法を使用することにより、フラッシュ容量に近づくことができる。こういった理由により、各種フラッシュ装置の効率及び最適性を比較するためにフラッシュ容量を使用する。
【００８５】
情報理論の考慮事項に基づいて、所与のフラッシュ技術及びフラッシュ信頼性に関して、使用すべき最適な電圧プログラムレベルがあることが分かる。さらに、電圧レベルにわたって使用すべき最適な確率分布がある。この電圧レベル数及びレベルにわたる確率分布の場合、フラッシュ容量は最大化される。したがって、この電圧レベル数を使用することにより、所与のフラッシュ信頼性に対してフラッシュコストが最小化されるため、この電圧レベル数をフラッシュメモリ装置に使用することが望ましい。通常、最適な数の電圧レベルは２のべき乗ではなく、電圧レベルにわたる最適な分布は均等ではない。
【００８６】
別法として、より多くの電圧レベルを使用しても、無視できるフラッシュ容量の増大しか提供されないような最小数の電圧レベルが存在する場合があり得る。この場合には、最小数の電圧レベルを使用することにより、フラッシュコストとフラッシュ性能に対する信頼性との最良のトレードオフが提供される。換言すれば、最小数の電圧レベルを使用することにより、同じフラッシュコスト及び信頼性を維持しながら、フラッシュの書き込み／読み取りスループットが最大化される。
【００８７】
例えば、フラッシュメモリの以下の簡易化されたモデルを考える。Ｘが、フラッシュセルのプログラム電圧レベルを示すものとし、Ｙが、フラッシュセルの読み取り電圧レベルを示すものとする。プログラム電圧レベル及び読み取り電圧レベルが互いに同一であり、かつ一定（経時変化しない）であると仮定する。フラッシュセルが電圧窓１［ボルト］に制限されるものと仮定する。さらに、Ｙ＝Ｘ＋Ｎであると仮定する。式中、Ｎは加法性白色ガウス雑音（フラッシュセル内の物理プロセスをモデリングする）である。雑音Ｎは、期待値μ＝０及び標準偏差σ＝１５０［ｍＶ］で正規分布する確率変数である。経時変化しないこの簡易化されたフラッシュモデル下では、データ保持及びプログラム／消去サイクルに意味がないため、信頼性の高い記憶、すなわち無視できるビットエラーレートを可能にする、達成可能なＩＢＰＣに対する上限としてフラッシュ容量を定義する。
【００８８】
フラッシュコントローラがプログラム電圧レベルにわたって等しい確率を利用する（すなわち、フラッシュに書き込まれる情報がランダムならば、セル内の各電圧レベルが同様に確かにプログラムされる）と仮定すると、
・２つのプログラム電圧レベルを使用すると、フラッシュ容量は各セル当たり０．９９４６情報ビット（ＩＢＰＣ＝０．９９４６）になり、
・３つのプログラム電圧レベルを使用すると、フラッシュ容量は各セル当たり１．２１６９情報ビット（ＩＢＰＣ＝１．２１６９）になり、
・４つのプログラム電圧レベルを使用すると、フラッシュ容量は各セル当たり１．１６１２情報ビット（ＩＢＰＣ＝１．１６１２）になる。
【００８９】
ここで図面に戻ると、図３は対応する閾値電圧分布の略図である。図３において、横軸は閾値電圧である。図３の容量がどのように計算されるかの詳細な説明については、付録Ａを参照のこと。
【００９０】
コントローラが電圧レベルにわたって不均等な分布を利用する場合、さらに高いフラッシュ容量を達成することができる。簡易化されたモデルのフラッシュメモリの容量は、３つのプログラム電圧レベルが使用される場合、かつ中間の電圧レベルが確率２８％でプログラムされ、２つの両外側の電圧レベルがそれぞれ確率３６％でプログラムされる場合に最大化される。この場合、フラッシュ容量は各セル当たり１．２２４５情報ビット（ＩＢＰＣ＝１．２２４５）である。これに対する直観的な説明は、中間プログラム電圧レベルが誤って読み取られる（すなわち、プログラムレベルと異なる読み取りレベルで読み取られる）可能性が、両外側の電圧レベルと比較して２倍であることである。したがって、中間レベルのプログラム確率を低減することにより、全体の電圧レベルエラー確率が低減される。セル電圧レベルにわたって不均等な確率を利用するためには、フラッシュコントローラはいくつかの冗長ビットを追加する必要がある。しかし、エラー確率の低減により、フラッシュメモリ内に情報を信頼的に記憶できるようにするためにコントローラが必要とする冗長ビット数は少なくなる。全体的に見れば、冗長ビットの総数（不均等な確率を利用するために使用される冗長ビット及びエラーからデータを保護するために使用される冗長ビット）は低減され、その結果としてフラッシュ容量が高くなる。
【００９１】
簡易化モデルの文脈の中では、本発明のフラッシュコントローラは、３つの電圧レベルを使用できるようにし、電圧レベルにわたって最適な確率分布を利用することができる。本発明が、確率の等しい４つの電圧レベルを使用する従来技術によるコントローラと比較して得るものは、以下である。
１．フラッシュコストの低減が得られる。同量の情報を記憶する場合、フラッシュサイズは５．１７％低減される（ＩＢＰＣ従来技術によるコントローラ／ＩＢＰＣ本発明＝１．１６１２／１．２２４５＝０．９４８３）。
２．フラッシュ性能の改良が得られる。４つではなく３つのプログラム電圧レベルを使用することにより、読み／書きフラッシュスループットが高くなる。
【００９２】
図４は、４つの等確率プログラム電圧レベルを使用する従来技術によるフラッシュメモリ装置１０の一実施態様を示す。フラッシュコントローラ１２は、以下のブロックを含む。
１．誤り訂正符号（ＥＣＣ）レイヤ：
・ＥＣＣエンコーダ２０：情報ビットストリームを符号化ビットストリームに符号化する。ＥＣＣのレートは、符号化ビットに対する情報ビットの比である。例えば、２元線形ブロック符号に基づくＥＣＣは、情報ビットＫ個のブロックを符号化ビットＮ個のブロックに写像する。但し、Ｎ＞Ｋである。ＥＣＣレートはＲ＝Ｋ／Ｎである。図４に示す例では、２元線形ブロック符号が使用されるものと仮定している。
・ＥＣＣデコーダ２６：「ノイジー」符号化ビットストリームを復号化し、情報ビットストリームの推定を生成する。「ノイジー」符号化ビットストリームは、元のシンボル（又は２元符号の場合にはビット）のうちのいくつかが異なるシンボルに反転した元の符号化ビットストリームである。例えば、２元線形ブロック符号用のデコーダ２６は、符号化ビットＮ個の「ノイジー」ブロック（別称「ノイジー」符号語）を受け取り、「ノイジー」ブロックを復号化し、情報ビットＫ個のブロックの推定を生成する。符号化ビットの「ソフト」推定がデコーダ２６に提供され、「ソフト」復号化が実行される場合、改良された修正能力のデコーダ２６を実現することができる。「ソフト」復号化は、デコーダ２６が復号化プロセスにおいてビットが誤っている確率についての情報を利用する場合に実行することができる。ビットｂの「ソフト」推定は、様々な方法で提供することができる。２つの一般的な方法は、１）フラッシュメモリから電圧レベルｙが読み取られる場合、ビットｂが１である先験的確率を提供し、Ｐｒ（ｂ＝１｜ｙ）であり、２）フラッシュメモリから電圧レベルｙが読み取られる場合、ビットｂの先験的多数尤度比（ＬＬＲ）を提供し、ＬＬＲ＝ｌｏｇ（Ｐｒ（ｂ＝０｜ｙ）／Ｐｒ（ｂ＝１｜ｙ））である。先験的ＬＬＲの計算の仕方の説明が、付録Ｃに提供される。図４に示す例では、「ソフト」デコーダ２６が使用され、フラッシュ容量がそれに従って計算されるものと仮定される。
２．マッピング／デマッピングレイヤ：
・マッパ２２：符号化ビットストリームを、フラッシュセルにプログラムされるべき電圧レベルストリームに写像する。従来技術によれば、マッパ２２は全単射写像関数、すなわち、１対１（単射）であり、かつ上への（全射）写像の関数を利用する。全単射関数、単射関数、及び全射関数の正式な定義については付録Ｂを参照のこと。
・デマッパ２４：フラッシュセルアレイ１８から読み取られた電圧レベルストリームをビットストリームに、又は「ソフト」デコーダが使用される場合にはビットの「ソフト」推定ストリームに写像する。実際には、デマッパ２４は必要不可欠なものではない。デマッパが使用されるものもあれば、後述するように読み取り電圧レベルに対して直接動作するものもある、様々な符号化方式を使用することができる。図４に示す例では、デマッパ２４が使用される方式及び使用されない方式の両方を示す。
【００９３】
表１は、図４のコントローラ１２により使用されるビットシーケンスから電圧レベルへの写像を示す。
【００９４】
【表１】
0005534675.tif 000002
【００９５】
理論上のフラッシュ容量に近づくために、最適な符号化方式を使用すべきである。２つのこのような符号化方式は、以下である。
１．最適な最尤（ＭＬ）復号化を使用する単一レベル符号化（ＳＬＣ：Ｓｉｎｇｌｅ−Ｌｅｖｅｌ  Ｃｏｄｉｎｇ）：この方式では、情報ビットストリーム全体が単一の符号により符号化され、最適なＭＬデコーダを使用して復号化される。ＭＬデコーダは、フラッシュセルアレイから読み取られた電圧レベルから直接、最も可能性の高い情報ビットストリームを計算する。最適なデコーダは、通常、高い複雑性を発生させる。最適なＳＬＣ方式の詳細な説明を付録Ｄに提供する。最適なＳＬＣ符号化方式は、図４において、デマッパ２４を迂回する矢印として表される。
２．マルチステージ復号化（ＭＳＤ）を使用するマルチレベル符号化（ＭＬＣ）：この方式では、情報ビットストリームがいくつかのストリームに分けられ、各ビットストリームは異なる符号を使用して符号化される。復号化はステージで実行され、各ステージにおいて、単一の符号化ビットストリームが、デマッパにより提供される「ソフト」ビット推定に対して動作する「ソフト」デコーダを使用して復号化される。各符号化ビットストリームの復号化結果は、次の符号化ビットストリームの「ソフト」ビットストリームを計算するためにデマッパにより使用される。最適なＭＬＣ／ＭＳＤ方式の詳細な説明を付録Ｅに提供する。
【００９６】
最適未満の復号化に基づくＳＬＣ方式を使用することが非常に一般的である。最適未満の復号化は、フラッシュセルアレイから読み取られた電圧レベルに対して直接動作せずに、むしろ、デマッパにより提供される「ソフト」ビット推定に対して動作する。デマッパの推定は一次統計にのみ基づくため、いくらかの情報が失われ、復号化は最適ではない。しかし、このような方式はより低い実施複雑性を必要とし、多くの場合、一般化グレイ写像を見つけて使用することができるため、生じる性能損失はごくわずかである。最適未満ＳＬＣ方式の詳細な説明を付録Ｄに提供する。このような最適未満のＳＬＣ方式は、図４において、フラッシュセルアレイ１８からデマッパ２４への矢印及びデマッパ２４からＥＣＣデコーダ２６への矢印として表される。
【００９７】
本明細書では、フラッシュメモリ装置のコストをメモリ装置の容量により、すなわち、達成可能なフラッシュメモリ装置のＩＢＰＣにより測定する。図４に示す例では、従来技術による最適な符号化方式に基づくフラッシュメモリ装置の容量は、１．１６１２ＩＢＰＣである（付録Ａ参照）。このフラッシュ容量に近づくために、レート１．１６１２／２＝０．５８０６の良好なＥＣＣを使用すべきである。
【００９８】
図５は、本発明のＭＢＰＣフラッシュメモリ装置１１０の簡略ブロック図である。特に、フラッシュメモリ装置１１０は、本発明により修正された図４のフラッシュメモリ装置１０である。フラッシュメモリ装置１０のように、フラッシュメモリ装置１１０は、フラッシュコントローラ１１２及び装置１０から引き継いだフラッシュセルアレイ１８を含む。フラッシュコントローラ１１２は、エンコーダ１１４及びデコーダ１１６を含む。エンコーダ１１４は、装置１０のＥＣＣエンコーダブロック２０及び本発明のマッパブロック１２２を含む。デコーダ１１６は、本発明のデマッパブロック１２４及び本発明のＥＣＣデコーダブロック１２６を含む。従来技術によるマッパブロック２２と異なり、本発明のマッパブロック１２２は、全単射関数ではない写像関数を利用する。本発明の写像関数は、後述する本発明の第１の実施形態では１対１（単射）ではなく、又は後述する本発明の第２の実施形態では上への写像（全射）ではない。これにより、あらゆる任意の（必ずしも２のべき乗である必要がない）数の電圧レベルを使用し、プログラム電圧レベルにわたってあらゆる任意の確率分布を使用するフラッシュメモリ装置の設計が可能になる。フラッシュメモリ装置１１０を設計する際のこの追加の自由度により、フラッシュコストと、信頼性と、性能との間でより良いトレードオフを提供するより効率的なフラッシュメモリ装置の設計が可能になる。さらに、後述した本発明の第２の実施形態では、一般化グレイ写像が使用される。これは、ＥＣＣデコーダ１２６の入力において予想されるビットエラーレートを低減する。これにより、フラッシュメモリ装置１１０の効率の無視できる損失で、すなわち、フラッシュメモリ装置１１０の容量の無視できる低減で、最適未満ＳＬＣ符号化方式を使用するコントローラ１１２の非常に単純な実施が可能になる。後述する本発明の第１の実施形態では、ＥＣＣデコーダ１２６の入力において予想されるビットエラーレートを最小化する写像も使用する。
【００９９】
表２及び表３は、３つのみのプログラムレベルが使用される本発明の第１の実施形態の一例の写像関数及びソフトデマッピングを示す。写像関数は１対１ではない（単射ではない）。ＥＣＣの使用により、写像が１対１でなくとも情報ビットを復元することができる。例えば、「ソフト」でマッパ及び「ソフト」デコーダを使用するＳＬＣ符号化方式が使用される場合、表３に示すように、電圧レベル２が読み取られるとき、デマッパ１２４は電圧レベル２に写像されたビットの先験的推定を提供する。最初のビットは、ＬＬＲ１＝ｌｏｇ（Ｐｒ（ｂ１＝０｜ｙ）／Ｐｒ（ｂ１＝１｜ｙ））＝−５．３によって表されるように、高い確率で１である。２番目のビットの場合、１である確率又は０である確率がほぼ等しい。実際には、電圧レベル２を読み取る場合、プログラムレベルが２又は０であるよりも２又は１である確率がわずかに高いため、２番目のビットが１である可能性がわずかに高い。すなわち、
Ｐｒ（プログラムレベル＝２又は１｜読み取りレベル＝２）
＞Ｐｒ（プログラムレベル＝２又は０｜読み取りレベル＝２）
である。フラッシュモデルに基づいて厳密な確率を計算すると、
ＬＬＲ２＝ｌｏｇ（Ｐｒ（ｂ２＝０｜ｙ）／Ｐｒ（ｂ２＝１｜ｙ））＝−０．１
が得られる。ＬＬＲがどのように計算されるかのさらなる詳細については、付録Ｃを参照のこと。ソフトデコーダは、これら「ソフト」ビット推定をすべて考慮し、フラッシュアレイ１８に記憶された確率が最も高い情報ビットストリームを返す。
【０１００】
表２の写像の結果として、３つのプログラム電圧レベルにわたっての確率分布は［０．２５  ０．２５  ０．５］になる。表２の写像関数及び表３のソフトデマッピングを使用し、最適符号化方式に基づくフラッシュメモリ装置１１０の容量は１．１６６ＩＢＰＣである（付録Ａ参照）。このフラッシュ容量に近づくためには、レート１．１６６／２＝０．５８３の良好なＥＣＣを使用すべきである。容量は、図４のフラッシュメモリ装置１０の容量にかなり似ている。しかし、フラッシュメモリ装置１１０のこの例は、従来技術によるフラッシュメモリ装置１０の４つの電圧レベルと比較して３つのみの電圧レベルを使用し、その結果として、読み／書きスループットが高くなる。
【０１０１】
【表２】
0005534675.tif 000003
【０１０２】
【表３】
0005534675.tif 000004
【０１０３】
表４及び表５は、３つのプログラムレベルが使用される本発明の第１の実施形態の別の例の写像関数及びソフトデマッピングを示す。写像関数は１対１ではない（単射ではない）。この写像関数の結果として、３つのプログラム電圧レベルにわたっての確率分布は［０．３７５  ０．２５  ０．３７５］になる。表４の写像関数及び表５のソフトデマッピングを使用し、最適符号化方式に基づくフラッシュメモリ装置１１０の容量は、１．２２２４ＩＢＰＣである（付録Ａ参照）。このフラッシュ容量に近づくためには、レート１．２２２４／３＝０．４０７５の容量に近づくＥＣＣを使用すべきである。この最適符号化方式に基づくフラッシュメモリ装置１１０の容量は、図４の従来技術によるフラッシュメモリ装置１０の容量よりも高く、その結果として、フラッシュコストが約５％低くなる。さらに、フラッシュメモリ装置１１０のこの例は、従来技術によるフラッシュメモリ装置１０の４つの電圧レベルと比較して３つのみの電圧レベルを使用し、その結果として、読み／書きスループットが高くなる。
【０１０４】
【表４】
0005534675.tif 000005
【０１０５】
【表５】
0005534675.tif 000006
【０１０６】
表６及び表７は、３つのプログラムレベルが使用される本発明の第２の実施形態の写像関数及びソフトデマッピングを示す。符号化ビット３個の各シーケンスが、２つのフラッシュセルにプログラムされる２つのプログラム電圧レベルに写像される。したがって、表６の写像関数は全射ではない。表６の写像関数及び表７のソフトデマッピングを使用し、最適符号化方式に基づくフラッシュメモリ装置１１０の容量は、１．１９８７ＩＢＰＣである（付録Ａ参照）。最適符号化方式及び最適未満符号化方式を使用してこのフラッシュ容量に近づくためには、レート１．１９８７／（３ビット／２セル）＝０．７９９１の容量に近づくＥＣＣを使用すべきである。この最適符号化方式に基づくフラッシュメモリ装置１１０の容量は、図４の従来技術によるフラッシュメモリ装置１０の容量よりも高く、その結果として、フラッシュコストが約３．１％低くなる。さらに、フラッシュメモリ装置１１０のこの実施形態は、従来技術によるフラッシュメモリ装置１０の４つの電圧レベルと比較して３つのみの電圧レベルを使用し、その結果として、読み／書きスループットが高くなる。
【０１０７】
【表６】
0005534675.tif 000007
【０１０８】
【表７】
0005534675.tif 000008
【０１０９】
図６は、ホスト６０に結合された本発明のフラッシュメモリ装置５０の高位ブロック図である。図６は、バン（Ｂａｎ）の米国特許第５，４０４，４８５号明細書の図１の改変であり、この特許を、その内容全体を本願明細書に記載したものとして参照により本明細書に援用する。フラッシュメモリ装置５０は、フラッシュメモリ５４、コントローラ５２、及びランダムアクセスメモリ（ＲＡＭ）５６を含む。コントローラ５２は、米国特許第５，４０４，４８５号明細書の「フラッシュ制御機構１４」に対応し、米国特許第５，４０４，４８５号明細書に記載のように、ＲＡＭ５６の助けによりフラッシュメモリ５４を管理する。フラッシュメモリ５４は、米国特許第６，５２２，５８０号明細書又は米国特許第６，６４３，１８８号明細書に記載のように、データ、すなわちフラッシュメモリ５４の各セル当たり２つ以上のビットを符号化する。コントローラ５２は、ＥＣＣ符号化及び復号化、ならびに非全単射写像及びデマッピングも上述したように実行する。
【０１１０】
図７は、本発明の代替のデータ記憶システム８０の高位部分ブロック図である。データ記憶システム８０は、プロセッサ８２及び４つのメモリ装置、すなわち、ＲＡＭ８４、ブートＲＯＭ８６、大容量記憶装置（ハードディスク）８８、及びフラッシュメモリ装置７０を含み、これらはすべて共通のバス９０を介して通信する。フラッシュメモリ装置５０のように、フラッシュメモリ装置７０はフラッシュメモリ７２を含む。フラッシュメモリ装置５０と異なり、フラッシュメモリ装置７０はそれ自体のコントローラ及びＲＡＭを有さない。それに代えて、プロセッサ８２が、例えば、イスラエル、クファルサバ（ＫｆａｒＳａｂａ）に所在のエムシステムズ社（ｍｓｙｓｔｅｍｓ  Ｌｔｄ．）のトゥルーＦＦＳ（ＴｒｕｅＦＦＳ）（商標）ドライバのような、米国特許第５，４０４，４８５号明細書の方法を実施するソフトウェアドライバを実行することにより、コントローラ５２をエミュレートする。フラッシュメモリ７２は、米国特許第６，５２２，５８０号明細書又は米国特許第６，６４３，１８８号明細書に記載のように、データ、すなわち、フラッシュメモリ７２の各セル当たり２つ以上のビットを符号化する。プロセッサ８２は、ＥＣＣ符号化及び復号化、ならびに非全単射写像及びデマッピングも上述したように実行する。フラッシュメモリ装置７０は、プロセッサ８２がフラッシュメモリ７２と通信できるようにするバスインタフェース７８も含む。
【０１１１】
本発明のＥＣＣ符号は、「系統的」であってもよく、又は「非系統的」であってもよい。系統的な誤り訂正符号化は、元のデータビットが符号化プロセスにより保存され、記憶されたビット内で識別可能なことを特徴とする。換言すれば、誤り訂正メカニズムは元のデータビットをとり、いくつかのパリティビットを加え、データビット及びパリティビットの両方を記憶する。後に、記憶されたビットを読み取る際に、データビット及びパリティビットの両方が読み取られ、パリティビットにより、読み取られたデータビットの誤りを訂正することができ、それにより、元のデータビットを生成する。
【０１１２】
非系統的な誤り訂正符号では、元のデータビットは保存されず、記憶されない。それに代えて、符号化プロセスは、元のデータビットを、時に「保護データビット」と呼ばれることがあるより大きなビット群に変換し、これが記憶される。系統的な誤り符号のデータビット及び関連するパリティビットの集まりのように、非系統的誤り符号の保護データビットは、本明細書では、元のデータビットに対応する符号語とみなされる。記憶された保護データビットを読み取る際に、保護データビットに誤りがある場合であっても、元のデータビットが再生成される。非系統的な符号の決定的な特徴は、元の特定のデータビットと記憶される特定のビットとの間に直接の対応性がないことである。元のデータビットは複数の記憶ビットに「拡散」され、複数の記憶ビットの組み合わせのみが元のビットの値を伝える。
【０１１３】
プロセッサ８２がフラッシュメモリ７２を管理するために実行するソフトウェアドライバのコードは、大容量記憶装置８８に記憶され、実行のためにＲＡＭ８４に転送される。したがって、大容量記憶装置８８は、本発明の原理によるフラッシュメモリ７２を管理するためのコンピュータ可読コードが具体化されるコンピュータ可読コード記憶媒体の一例である。
【０１１４】
本発明を限られた数の実施形態に関連して説明したが、本発明の多くの変形、変更、及び他の用途を行い得ることが理解されるであろう。
【０１１５】
＜付録Ａ：フラッシュ容量の計算＞
Ｘがプログラム電圧レベルを示すものとする。Ｙが読み取り電圧レベルを示すものとする。Ｐ（Ｘ）が、プログラム電圧レベルＸの確率を示すものとする。Ｐ（Ｙ｜Ｘ）が、電圧レベルＸがプログラムされた場合に電圧レベルＹを読み取る確率を示すものとする。そうすると、フラッシュ容量は、
【数１】
0005534675.tif 000009
により与えられる。
【０１１６】
フラッシュメモリの容量を計算する２つの例を次に提供する。
【０１１７】
＜例１：図４のフラッシュメモリ１０の容量の計算＞
プログラム電圧レベル及び読み取り電圧レベルは：
Ｘ＝Ｙ＝［０  ０．３３３  ０．６６６  １］［Ｖｏｌｔｓ］
であり、
フラッシュメモリは、標準偏差σ＝１５０［ｍＶ］を有する加法的白色ガウス雑音を受け、
各プログラムレベルは等しい確率：
Ｐ（Ｘｉ）＝０．２５    ｉ＝１，２，３，４
でプログラムされ、
遷移確率は以下：
【数２】
0005534675.tif 000010
のように計算され、式中、
【数３】
0005534675.tif 000011
である。
そうすると、フラッシュ容量は：
【数４】
0005534675.tif 000012
により与えられる。
【０１１８】
＜例２：表４及び表５の実施形態である図５のフラッシュメモリ１１０の容量の計算＞
プログラム電圧レベル及び読み取り電圧レベルは：
Ｘ＝Ｙ＝［０  ０．５  １］［Ｖｏｌｔｓ］
であり、
フラッシュメモリは、標準偏差σ＝１５０［ｍＶ］を有する加法的白色ガウス雑音を受け、
非全単射写像は、プログラム電圧レベルにわたって以下の非均等分布を発生させ：
Ｐ（Ｘ）＝［０．３７５  ０．２５  ０３７５］
遷移確率は以下：
【数５】
0005534675.tif 000013
のように計算される。
そうすると、フラッシュ容量は：
【数６】
0005534675.tif 000014
により与えられる。
【０１１９】
＜付録Ｂ：正式な関数関連定義＞
定義（１対１）：関数ｆは、ｆ（ｘ）＝ｆ（ｙ）がｘ＝ｙを暗に意味する場合のみ、１対１の写像（単射）であると言える。その他の場合、関数は多対１の写像である：ｘ≠ｙであり、かつｆ（ｘ）＝ｆ（ｙ）であるような少なくとも１つの引数対（ｘ，ｙ）が存在する。
【０１２０】
定義（上へ）：集合Ａから集合Ｂへの関数ｆは、Ｂのあらゆる要素ｙについて、ｆ（ｘ）＝ｙのような要素ｘがＡに存在する場合のみ、上への写像（全射）と言える。すなわち、ｆは、ｆ（Ａ）＝Ｂの場合のみ、上への写像である。その他の場合、関数は中への写像である：ｆにより写像されないＢの少なくとも１つの要素ｙが存在する。
【０１２１】
定義（全単射）：関数は、上への写像かつ１対１の写像の場合に全単射と呼ばれる。
【０１２２】
＜付録Ｃ：対数尤度比（ＬＬＲ）の計算＞
ｆ：２ｍ→［１，２，・・・，Ｍ］が、それぞれの長さがｍのバイナリシーケンスｂをセルのＭ個の可能な状態からのプログラムセル状態Ｘにマッチングする写像関数を示すものとする。そうすると、ビットｉの対数尤度比（ＬＬＲ）は、
【数７】
0005534675.tif 000015
により与えられる。式中、
【数８】
0005534675.tif 000016
のような
【数９】
0005534675.tif 000017
のような、であり、
【数１０】
0005534675.tif 000018
は、ｉ番目のビットが０及び１にそれぞれ等しい長さｍのバイナリシーケンスの集合を示す。確率Ｐｒ（Ｙ｜Ｘ）は付録Ａに述べられるように計算される。ビットが等しい先験的確率を有する（すなわち、ビットが０である確率と１である確率が等しい）ものと仮定することに留意する。
【０１２３】
＜付録Ｄ：単一レベル符号化（ＳＬＣ）に基づく符号化方式＞
参考文献：Ｕ．ワッシュマン（Ｗａｃｈｓｍａｎｎ）、Ｒ．Ｆ．Ｈ．フィッシャー（Ｆｉｓｃｈｅｒ）、及びＪ．Ｂ．フーバー（Ｈｕｂｅｒ）、“Ｍｕｌｔｉｌｅｖｅｌ  ｃｏｄｅｓ：ｔｈｅｏｒｅｔｉｃａｌ  ｃｏｎｃｅｐｔｓ  ａｎｄ  ｐｒａｃｔｉｃａｌ  ｄｅｓｉｇｎ  ｒｕｌｅｓ”、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  第４５巻  第５号  １３６１−１３９１頁（１９９９年）
単一レベル符号化方式では、情報ビットストリームｉが単一の符号を使用して符号化される。符号化ビットは、フラッシュメモリのプログラム電圧レベルに写像される。読み取られた電圧レベルは、次に、復号化されて、元の情報ビットストリームが復元される。図４のフラッシュメモリ１０及び図５のフラッシュメモリ１１０は、単一レベル符号化方式を使用する。
【０１２４】
ｉがフラッシュメモリに記憶された情報ビットストリームを示すものとする。Ｙが読み取り電圧レベルのシーケンスを示すものとする。さらに、あらゆる情報ビットストリームが等しい先験的確率を有するものと仮定する。最適最尤（ＭＬ）復号化は：
【数１１】
0005534675.tif 000019
が与えられる。
【０１２５】
ＭＬ復号化は、通常、非常に高い復号化複雑性を発生させる。したがって、最適未満復号化アルゴリズムを使用することが非常に一般的である。例えば、複雑性の低い反復復号化アルゴリズムは、ＭＬ復号化に非常に近い性能を有することができる（Ｙ．ナナ（Ｎａｎａ）、Ｅ．シャロン（Ｓｈａｒｏｎ）、及びＳ．リッツィン（Ｌｉｔｓｙｎ）、“Ｉｍｐｒｏｖｅｄ  ｄｅｃｏｄｉｎｇ  ｏｆ  ＬＤＰＣ  ｃｏｄｅｄ  ｍｏｄｕｌａｔｉｏｎｓ”、ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｌｅｔｔｅｒｓ  第１０巻  第５号  ３７５−３７７頁（２００６年））。
【０１２６】
デコーダが読み取り電圧レベルに対して直接動作せずに、むしろ、デマッパにより生成されるＬＬＲ等の記憶ビットの「ソフト」推定に対して動作する場合、復号化方式の追加の簡易化を得ることができる。この方式は、デマッパが記憶ビットの一次統計のみを抽出し、同じセル状態に写像されるビット間の統計学的従属性を無視するため、最適ではない。通常、一般化グレイ写像が使用される場合、性能損失は非常に小さい（Ｇ．カイレ（Ｃａｉｒｅ）、Ｇ．タリコ（Ｔａｒｉｃｃｏ）、及びＥ．ビグリーリ（Ｂｉｇｌｉｅｒｉ）、“Ｂｉｔ  Ｉｎｔｅｒｌｅａｖｅｄ  ｃｏｄｅｄ  ｍｏｄｕｌａｔｉｏｎ”、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  第４４巻  第３号  ９２７−９４６頁（１９９８年））。
【０１２７】
＜付録Ｅ：マルチステージ復号化（ＭＳＤ）と共にマルチレベル符号化（ＭＬＣ）に基づく符号化方式＞
参考文献：Ｕ．ワッシュマン（Ｗａｃｈｓｍａｎｎ）、Ｒ．Ｆ．Ｈ．フィッシャー（Ｆｉｓｃｈｅｒ）、及びＪ．Ｂ．フーバー（Ｈｕｂｅｒ）、“Ｍｕｌｔｉｌｅｖｅｌ  ｃｏｄｅｓ：ｔｈｅｏｒｅｔｉｃａｌ  ｃｏｎｃｅｐｔｓ  ａｎｄ  ｐｒａｃｔｉｃａｌ  ｄｅｓｉｇｎ  ｒｕｌｅｓ”、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  第４５巻  第５号  １３６１−１３９１頁（１９９９年）
この方式では、情報ビットストリームはｍ個のストリームに分けられ、各ビットストリームは異なる符号を使用して符号化される。次に、マッパがｍ個の符号化ビットストリームを使用して、プログラム電圧レベルストリームを生成する。各符号化ビットストリームから１つずつの各ｍビットが、プログラム電圧レベルに写像される。
【０１２８】
図８は、従来技術の、又は本発明によるＭＬＣ／ＭＳＤフラッシュメモリ２１０の簡略ブロック図である。フラッシュメモリ２１０は、ＭＬＣ／ＭＳＤコントローラ２１２及び図４及び図５のフラッシュメモリセルアレイ１８と同一のフラッシュメモリセルアレイ２１４を含む。コントローラ２１２は、入力情報ビットストリームをｍ個の内部入力ビットストリームに並列化する並列器（直列／並列）２１６、各内部入力ビットストリームを符号化するｍ個のＥＣＣエンコーダ２１８、符号化ビットストリームをフラッシュセルアレイ２１４をプログラムするプログラム電圧レベルに写像するマッパ２２０、読み取り電圧レベルをｍ個の内部出力ビットストリームにデマッピングするデマッパ、各内部出力ビットストリームを後述するように復号化するｍ個のＥＣＣデコーダ２２４、及び復号化ビットストリームを直列化する直列器（並列／直列）２２６を含む。
【０１２９】
フラッシュセルアレイ２１４が読み取られると、記憶された情報を復元するために、復号化が実行される。復号化はステージで実行される。各ステージにおいて、単一の符号化ビットストリームが、デマッパ２２２により提供される「ソフト」ビット推定に対して動作する各「ソフト」デコーダ２２４を使用して復号化される。各符号化ビットストリームの復号化結果（ｍ番目のビットストリームを除く）がデマッパ２２２にフィードバックされ、次の符号化ビットストリームの「ソフト」ビット推定を計算するためにデマッパにより使用され、ｍ個すべての情報ビットストリームが復元されるまで同様である。
【０１３０】
ＭＬＣ／ＭＳＤ方式は、方式の最適性を保ちながら、読み取り電圧レベルに対して直接動作するのではなく、デマッパ出力に対して動作する複雑性の低いデコーダを使用することができる。しかし、ＭＬＣ／ＭＳＤはいくつかの実用面での欠点を有する。例えば、ＭＬＣ／ＭＳＤは、方式を設計するためにフラッシュモデルの物理モデルをよく知る必要があるとともに、ＭＬＣ／ＭＳＤは物理モデルの不完全な知識に敏感である。すなわち、ＭＬＣ／ＭＳＤはＳＬＣ方式よりも堅牢性が低い。さらに、ＭＬＣ／ＭＳＤは、特に、方式がフラッシュ物理モデルの不完全な知識に基づいて設計される場合、異なる復号化ステージ間でのエラー伝搬を受ける。さらに、符号化方式が特定のブロックサイズに制限される場合、情報ビットストリームをいくつかのブロックに分けるＭＬＣ／ＭＳＤ方式は、ＳＬＣ方式のＥＣＣよりも短いＥＣＣに基づく。ＥＣＣの性能は、コード長が増大するにつれて向上するため、ＭＬＣ／ＭＳＤ方式の性能は、ＳＬＣ方式と比較して実用面で劣る。
【図面の簡単な説明】
【０１３１】
【図１】従来技術によるＭＢＰＣフラッシュメモリ装置の簡略ブロック図である。
【図２】図１の従来技術によるＭＢＰＣフラッシュメモリ装置の一変形の簡略ブロック図である。
【図３】対応する容量が記された様々な閾値電圧分布の略図である。
【図４】図３の３番目の閾値電圧分布に特化された図２である。
【図５】本発明のＭＢＰＣフラッシュメモリ装置の簡略ブロック図である。
【図６】ホストに結合された本発明のフラッシュメモリ装置の高位ブロック図である。
【図７】本発明のデータ記憶システムの高位部分ブロック図である。
【図８】マルチレベル符号化及びマルチステージ復号化を使用するフラッシュメモリの簡略ブロック図である。
【図１】
0005534675.tif 000020
【図２】
0005534675.tif 000021
【図３】
0005534675.tif 000022
【図４】
0005534675.tif 000023
【図５】
0005534675.tif 000024
【図６】
0005534675.tif 000025
【図７】
0005534675.tif 000026
【図８】
0005534675.tif 000027