(57)【要約】  エンコーダおよびエンコード方法が提供される。本発明のエンコードシステムは、Ｃビット（Ｃは「０」よりも大きい整数）の入力ビット列をエンコードしてＣビットの第１ビット列を生成する第１エンコーダと、前記第１ビット列を受信し、前記受信した第１ビット列のデータをシャッフルして第２ビット列を生成する第２エンコーダとを具備する。第１ビット列に対するデータシャッフルは、第２ビット列のエラー分布を調整する。エンコード方法は、入力ビット列をエンコードしてＣビットの第１ビット列を生成するステップと、前記第１ビット列を受信し、前記受信した第１ビット列のデータをシャッフルして第２ビット列を生成するステップとを有する。第２ビット列に対するエラー分布は、前記データシャッフルに基づいて調整される。
2011503955.tif 000002
【特許請求の範囲】
【請求項１】
入力ビット列をエンコードしてＣビット（Ｃは「０」よりも大きい整数）の第１ビット列を生成する第１エンコーダと、
前記第１ビット列を受信し、前記受信した第１ビット列のデータをシャッフルして第２ビット列を生成する第２エンコーダと、を具備し、
ここで、前記第２ビット列のエラー分布は、前記データシャッフルに基づいて調整されることを特徴とするエンコードシステム。
【請求項２】
前記第２エンコーダは、前記受信したＣビットの第１ビット列に冗長情報を付加することを特徴とする請求項１に記載のエンコードシステム。
【請求項３】
前記第２エンコーダは、前記冗長情報を前記受信したＣビットの第１ビット列に付加し、生成行列に基づいて前記受信した第１ビット列のデータをシャッフルすることを特徴とする請求項１に記載のエンコードシステム。
【請求項４】
前記第２エンコーダは、
前記第１ビット列を受信し、Ｃ×Ａビット列（Ａは「０」よりも大きい整数）を生成するように信号処理を行う直列／並列信号処理部と、
前記Ｃ×Ａビット列を格納するバッファと、
第２ビット列を生成するように前記格納されたＣ×Ａビット列を多重化するマルチプレクサと、
を具備することを特徴とする請求項1に記載のエンコードシステム。
【請求項５】
前記第２ビット列を受信し、第３ビット列を生成するように前記受信した第２ビット列をランダム化する第３エンコーダをさらに具備することを特徴とする請求項１に記載のエンコードシステム。
【請求項６】
前記第３エンコーダは、
前記第２ビット列を受信し、第３ビット列を生成するようにモジュロ加算を行うモジュロ加算器と、
前記第３ビット列を受信し、ランダム化多項式の係数によって前記第３ビット列を乗算する複数の乗算器と、
前記複数の乗算器の結果値を格納する第１および第２レジスタと、
を具備することを特徴とする請求項５に記載のエンコードシステム。
【請求項７】
前記第３エンコーダは、前記第３ビット列を生成するようにランダム化多項式に基づいて前記受信した第２ビット列をランダム化し、
ここで、前記ランダム化多項式は、ｆ（Ｘ）＝ｆ０＋ｆ１Ｘ＋ｆ２Ｘ２＋・・・＋ｆｎＸｎを含み、ｆ０、ｆ１、・・・、ｆｎは前記ランダム化多項式の係数であることを特徴とする請求項５に記載のエンコードシステム。
【請求項８】
複数のマルチビットセルを含むページアレイに前記第２ビット列をプログラミングするプログラミング部をさらに具備し、
前記各マルチビットセルは、Ｍビットのデータ（Ｍは「０」よりも大きい整数）を格納することを特徴とする請求項１に記載のエンコードシステム。
【請求項９】
複数のマルチビットセルを含むページアレイに前記第２ビット列をプログラミングするプログラミング部をさらに具備し、
前記各マルチビットセルはＬビットのデータを格納し、
前記第２エンコーダは、Ｋ個のワード線に接続するマルチビットセルに格納されるＭ個の前記第２ビット列を生成し、
ここで、Ｍ＝Ｌ×Ｋの関係式が成立し、Ｍ、Ｌ、Ｋは「０」よりも大きい整数であることを特徴とする請求項１に記載のエンコードシステム。
【請求項１０】
前記第２ビット列のｉ番目の要素Ｓｉは、前記第１ビット列のｊ番目の要素Ｂ［ｊ］から、ｊ＝（ｉ×Ｃ＋Ｄ）ｍｏｄ（Ｍ×Ｃ）およびＳｉ＝Ｂ［ｊ］によって得られ、
ここで、Ｄはシャッフル過程のオフセットであり、ｍｏｄはモジュロ演算を示すことを特徴とする請求項１に記載のエンコードシステム。
【請求項１１】
前記第２ビット列のｉ番目の要素Ｓｉは前記オフセットＤのｉを調整することによって得られることを特徴とする請求項１０に記載のエンコードシステム。
【請求項１２】
エラー制御コードをエンコードおよびデコードするためのシステムにおいて、
第１ビット列を生成するように入力ビット列をエンコードするエラー制御コード（ＥＣＣ）エンコーダと、
前記第１ビット列を受信し、第２ビット列を生成するように前記受信した第１ビット列のデータをシャッフルするシャッフラと、
前記第２ビット列を受信し、第３ビット列を生成するように前記受信した第２ビット列をランダム化するランダマイザと、
前記第３ビット列を受信し、第４ビット列を生成するように前記第３ビット列を変換するメモリチャネルと、
前記第４ビット列を受信し、第５ビット列を生成するように前記第４ビット列をデランダマイズするデランダマイザと、
前記第５ビット列を受信し、第６ビット列を生成するように前記第５ビット列をデシャッフルするデシャッフラと、
前記第６ビット列を受信し、第７ビット列を生成するように前記受信した第６ビット列をデコードするＥＣＣデコーダと、
を具備することを特徴とするエラー制御コードをエンコードおよびデコードするためのシステム。
【請求項１３】
前記ＥＣＣデコーダは、前記第６ビット列に含まれたエラーが前記システムの最大エラー訂正性能よりも少ない場合に、前記第６ビット列におけるエラーを訂正するエラー制御コードをエンコードおよびデコードすることを特徴とする請求項１２に記載のシステム。
【請求項１４】
前記ＥＣＣデコーダは、前記第６ビット列のエラーを訂正し、エラーの無い第７ビット列を生成するエラー制御コードをエンコードおよびデコードすることを特徴とする請求項１２に記載のシステム。
【請求項１５】
入力ビット列を第１エンコードしてＣビット（Ｃは「０」よりも大きい整数）の第１ビット列を生成するステップと、
前記第１ビット列を受信し、前記受信した第１ビット列のデータをシャッフルして第２ビット列を生成するステップと、
を有することを特徴とするエンコード方法。
【請求項１６】
前記第２ビット列を受信し、前記受信した第２ビット列をランダム化して第３ビット列を生成するステップをさらに有することを特徴とする請求項１５に記載のエンコード方法。
【請求項１７】
複数のマルチビットセルを含むページアレイに前記第２ビット列をプログラミングするステップをさらに有し、
前記１つのマルチビットセルは、Ｍビットのデータを格納することを特徴とする請求項１５に記載のエンコード方法。
【請求項１８】
前記第２ビット列のｉ番目の要素Ｓｉは、前記第１ビット列のｊ番目の要素Ｂ［ｊ］から、ｊ＝（ｉ×Ｃ＋Ｄ）ｍｏｄ（Ｍ×Ｃ）およびＳｉ＝Ｂ［ｊ］によって得られ、
ここで、Ｄはシャッフル過程のオフセットであり、ｍｏｄはモジュロ演算を示すことを特徴とする請求項１５に記載のエンコード方法。
【請求項１９】
前記第２ビット列のｉ番目の要素Ｓｉは、前記オフセットＤのｉを調整することによって得られることを特徴とする請求項１８に記載のエンコード方法。
【請求項２０】
請求項１５に記載の方法を実行するためのプログラムが記録されていることを特徴とするコンピュータで読出し可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エラー制御コードに関し、特に、チャネルでのエラー訂正能力を向上させるためのエンコード方法およびエンコーダに関する。
【背景技術】
【０００２】
一般的に、情報を送信する経路をチャネルと呼ぶことができる。情報は、有無線通信手段によってチャネルに送信することができる。さらに、チャネルは、半導体記憶装置に情報を格納し、格納された情報を半導体記憶装置から読み出す過程であると言ってもよい。例えば、チャネルは、半導体記憶装置が情報を格納した瞬間から格納された情報を半導体記憶装置から読み出すまでの時間的な経過であってもよく、半導体記憶装置が情報を格納し、格納された情報を半導体記憶装置から読み出す物理的な経路であってもよい。
チャネルを経由して情報が送信されるとき、送信された情報は破損して多くのエラーを含むことがある。もし、送信された情報のうち、エラーの数が予め決められたエラーの数を超過すれば、デコーダは最初の送信情報を復元できないこともある。
【０００３】
近年、破損した情報からエラーを検出したり、最初の送信から破損した情報を減らす分野に対する研究が着実に進められている。情報を送信する前に、最初の情報にエラー制御コードを付加して送信情報を生成する過程をエラー制御コードエンコードといい、送信情報を受信した後、受信した送信情報からエラー制御コードを分離して最初の情報を復元する過程をエラー制御コードデコードという。
送信情報に対するチャネルの特性に応じて、チャネルで発生するエラーの比率が相対的に大きいこともある。エラーの比率が大きければ大きいほど、このようなエラーを克服して所望の性能を達成するためのエラー制御コードエンコードおよびデコードを実現するためのハードウェアの複雑度は増加する。
それだけでなく、チャネルがマルチビットメモリ装置である場合、チャネルの特性上、発生するエラーの数が増加する傾向にある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、上述したような従来技術の問題を解決するために案出されたものであり、データシャッフル（ｄａｔａ  ｓｈｕｆｆｌｉｎｇ）および／またはランダム化（ｒａｎｄｏｍｉｚｉｎｇ）の過程でエラーが特定データの領域で集中的に発生するのを防止することにより、マルチビットメモリ装置のチャネルにおけるエラー訂正性能を向上させるための装置および方法を提供する。
【課題を解決するための手段】
【０００５】
本発明の一態様によれば、エラー制御コードのエンコードのためのエンコードシステムは、Ｃビット（Ｃは「０」よりも大きい整数）の入力ビット列をエンコードして第１ビット列を生成する第１エンコーダと、前記第１ビット列を受信し、前記受信した第１ビット列のデータをシャッフルして第２ビット列を生成する第２エンコーダとを具備することを特徴とする。ここで、前記第２ビット列のエラー分布は、前記データシャッフルに基づいて調整することができる。
【０００６】
本発明の他の態様によれば、エラー制御コードをエンコードおよびデコードするためのシステムは、第１ビット列を生成するように入力ビット列をエンコードするエラー制御コード（ＥＣＣ）エンコーダと、前記第１ビット列を受信し、第２ビット列を生成するように前記受信した第１ビット列のデータをシャッフルするシャッフラと、前記第２ビット列を受信し、第３ビット列を生成するように前記受信した第２ビット列をランダム化するランダマイザと、前記第３ビット列を受信し、第４ビット列を生成するように前記第３ビット列を変換するメモリチャネルと、前記第４ビット列を受信し、第５ビット列を生成するように前記第４ビット列をデランダマイズするデランダマイザと、前記第５ビット列を受信し、第６ビット列を生成するように前記第５ビット列をデシャッフルするデシャッフラと、前記第６ビット列を受信し、第７ビット列を生成するように前記受信した第６ビット列をデコードするＥＣＣデコーダと、を具備することを特徴とする。
【０００７】
また、本発明の更なる態様によるエンコード方法は、Ｃビット（Ｃは「０」よりも大きい整数）の入力ビット列を第１エンコードしてＣビットの第１ビット列を生成するステップと、前記第１ビット列を受信し、前記受信した第１ビット列のデータをシャッフルして第２ビット列を生成するステップと、を有することを特徴とする。
【図面の簡単な説明】
【０００８】
【図１】本発明の一実施形態に係るエンコーダを示す図である。
【図２】本発明の他の実施形態に係るエンコーダを示す図である。
【図３】図１のエンコーダがエラー訂正可能性を高める過程を示す図である。
【図４】本発明の一実施形態に係るＥＣＣエンコーダおよびＥＣＣデコーダを備えるシステムを示す図である。
【図５】第１ビット列の一例を示す図である。
【図６】第２エンコーダが第２ビット列を生成する過程の一実施形態を示す図である。
【図７】第２エンコーダが第２ビット列を生成する過程の他の実施形態を示す図である。
【図８】本発明の他の実施形態に係る第２エンコーダを示す図である。
【図９】本発明の更なる実施形態に係る第３エンコーダを示す図である。
【図１０】本発明の一実施形態に係るエンコード方法を示す動作フローチャートである。
【発明を実施するための形態】
【０００９】
以下、本発明に係る好適な実施形態を添付の図面を参照して詳細に説明する。しかしながら、本発明が実施形態によって制限されたり限定されることはない。各図面に提示された同じ参照符号は同じ部材を示す。
【００１０】
図１は、本発明の一実施形態に係るエンコーダ１００を示す図である。
図１を参照すれば、エンコーダ１００は、第１エンコーダ１１０、第２エンコーダ１２０を備える。
第１エンコーダ１１０は、Ｎビットの入力ビット列をエンコードしてＣビットの第１ビット列を生成する。ＣおよびＮは、「０」よりも大きい整数であってもよい。生成された第１ビット列は、Ｃビットコードワード（ｃｏｄｅｗｏｒｄ）を含んでもよい。ここで、Ｃ＞Ｎであり、冗長ビット（ｒｅｄｕｎｄａｎｔ  ｂｉｔｓ）（Ｃ−Ｎ）は入力ビット列に割当てられてもよい。
【００１１】
第２エンコーダ１２０は、第１エンコーダ１１０からＭ個の第１ビット列を受信する。第２エンコーダ１２０は、Ｍ個の第２ビット列を生成するため、受信したＭ個の第１ビット列のデータをシャッフルする。Ｍは、「０」よりも大きい整数であってもよい。第２エンコーダ１２０は、また、受信したＭ個の第１ビット列にパリティ（ｐａｒｉｔｙ）を付加してもよい。例えば、第２エンコーダ１２０は、Ｐビットの付加情報またはパリティをＣビットの第１ビット列に付加してもよい。第２エンコーダ１２０は、（Ｃ＋Ｐ）ビットの第２ビット列を生成するためにＣビットの第１ビット列をエンコードしてもよい。
第２エンコーダ１２０は、また、Ｍ個の第１ビット列をエンコードし、各第１ビット列はＣビットを構成してもよい。第２エンコーダ１２０は、Ｍ個の第２ビット列を生成するためにＭ×Ｃビット列のデータビットをシャッフルしてもよい。したがって、第２エンコーダ１２０は、Ｍ×Ｃビット情報を同時にエンコードしてもよい。
【００１２】
エンコードシステム１００は、プログラミング部１３０をさらに備えてもよい。プログラミング部１３０は、ページアレイ１４０で第２ビット列をプログラムしてもよい。ここで、ページアレイ１４０は、Ｃビットのマルチビットセルを含んでもよい。各第２ビット列は、Ｃビットおよび１つのマルチビットセルでプログラムされた１ビットデータを含んでもよい。プログラミング部１３０は、ページプログラミング動作をＭ回行ってもよく、そうすることによって、各マルチビットセルにＭビットデータを格納してもよい。
それだけではなく、プログラミング部１３０は、ページプログラミング動作をＬ回行ってもよく、そうすることによって、各マルチビットセルにＬビットデータを格納してもよい。ここで、Ｌは「０」よりも大きい整数である。第２エンコーダ１２０は、Ｋワード線に接続されたマルチビットセルに格納された（Ｌ×Ｋ）第１ビット列を受信してもよい。ここで、Ｍ＝Ｌ×Ｋである。Ｍ、ＬおよびＫは「０」よりも大きい整数を示す。第２エンコーダ１２０は、Ｍ個の第２ビット列を生成するためにＭ個の第１ビット列のデータをシャッフルしてもよい。
【００１３】
実施形態によっては、１つのページアレイは、Ｃ個のマルチビットセルを含んでもよく、エンコードシステム１００は、Ｎビットコードワードをエンコードしてもよい。例えば、Ｃ＝１０２４であり、かつＮ＝１００であれば、エンコードシステム１００は、入力ビット列を１００ビットのコードワードの単位に分け、各コードワードに対してエンコードを行ってもよい。エンコードシステム１００は、１つのページアレイに対して１０回のエンコードプロセスを行ってもよく、残りの２４マルチビットセルに対しは予め決定した値をプログラムしてもよい。
【００１４】
第２エンコーダ１２０がＭ個の第１ビット列をエンコードしてＭ個の第２ビット列を生成する過程を、生成行列（ｇｅｎｅｒａｔｏｒ  ｍａｔｒｉｘ）Ｇを用いて下記の数式１〜数式３のように表すことができる。
（数式１）
ｖ＝［Ｂ［０］Ｂ［１］・・・Ｂ［Ｃ−１］Ｂ［Ｃ］・・・Ｂ［（Ｍ−１）Ｃ−１］］
ｖは、Ｍ個の第１ビット列を１つの行ベクトルに表したものである。
（数式２）
ｗ＝［Ｓ［０］Ｓ［１］・・・Ｓ［Ｃ＋Ｐ−１］Ｓ［Ｃ＋Ｐ］・・・Ｓ［（Ｍ−１）（Ｃ＋Ｐ）−１］］
ｗは、Ｍ個の第２ビット列を１つの行ベクトルに表したものである。
（数式３）
ｗ＝ｖ×Ｇ
生成行列Ｇは、ＭＣ×Ｍ（Ｃ＋Ｐ）行列であり、第１ビット列の行ベクトルｖとＧとが乗算されて第２ビット列の行ベクトルｗが生成される。
簡単なＧの例として、Ｍ＝２、Ｃ＝２、Ｐ＝１である場合、下記の数式４のように表すことができる。
【００１５】
【数１】
2011503955.tif 000003
【００１６】
Ｇは、第１ビット列に対するデータシャッフルおよびパリティ追加に対応する生成行列である。
実施形態によっては、Ｐ＝０である場合、Ｇは、第１ビット列に対するパリティの追加なしでデータシャッフルのみを行ってもよい。
実施形態によっては、第１ビット列のコードワードを構成するビット数と１つのページアレイに含まれるマルチビットセルの数とが異なってもよい。下記の本明細書では、簡単な説明のために第１ビット列のコードワードのビット数および１つのページアレイに含まれるマルチビットセルの数をすべてＣと仮定する。
【００１７】
図２は、本発明の他の実施形態に係るエンコードシステム２００のブロックダイアグラムである。
図２を参照すれば、エンコードシステム２００は、第１エンコーダ２１０、第２エンコーダ２２０、および第３エンコーダ２３０を備える。
第１エンコーダ２１０および第２エンコーダ２２０は、図１の第１エンコーダ１１０および第２エンコーダ１２０と同じ方式で実行してもよい。したがって、第１デコーダ２１０および第２デコーダ２２０に対する動作および詳細な説明は省略することにする。
第３エンコーダ２３０は、第２エンコーダ２２０から第２ビット列を受信し、第３ビット列を生成するために受信したビット列をランダム化する。第３エンコーダ２３０は、ランダム化多項式（ｒａｎｄｏｍｉｚｅｒ  ｐｏｌｙｎｏｍｉａｌ）ｆ（Ｘ）を用いて第２ビット列をランダム化する。ランダム化多項式ｆ（Ｘ）を用いて第２ビット列をランダム化する過程は、図９を参照して説明することにする。
【００１８】
図３は、図１のエンコーダ１００がエラー訂正可能性高める過程を示す図である。
図３を参照すれば、横軸はページ別のエラー個数を示し、縦軸は該当するページの数を示す。
１つのページアレイはＣ個のマルチビットセルを含む。マルチビットセルそれぞれはＭビットのデータを格納するため、１つのページアレイはＣ×Ｍビットのデータを格納する。
１つのページは、ページアレイに同時にプログラミングされるＣビットのデータを指す。１つのページをページアレイにプログラミングする動作をページプログラミング動作という。
本実施形態では、説明を単純化する目的で、第２ビット列は１つのページに対応すると仮定する。ここで、他のビット列（例えば、第１、第３、第４、第５ビット列など）は１つのページアレイでプログラムされてもよい。ページアレイで１つのページがプログラムされた後、マルチビットメモリ装置はページアレイから格納されたページを読出してもよい。
【００１９】
マルチビットメモリ装置は、読出したページがプログラミングされたページと一致するか否かを確認するため、ページにエラー制御コード（ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｃｏｄｅｓ、ＥＣＣ）を挿入する。
マルチビットメモリ装置は、予め決定したＥＣＣの規則にしたがって読出したページにエラーがあるか否かを判定する。
ＥＣＣの種類に応じて、マルチビットメモリ装置は、読出したページに何個のエラーがあるかを判定してもよい。
ＥＣＣの種類に応じて、マルチビットメモリ装置は、読出したページに最大エラー訂正能力よりも多くないエラーがあれば、ページのエラーを訂正してもよい。
マルチビットメモリ装置が読出したページに最大エラー訂正能力よりも多くないエラーがあって、マルチビットメモリ装置がページのエラーを訂正してもよい場合、エラー訂正可能性があるといえる。
【００２０】
図３を参照すれば、第１分布３１０は、第１ビット列のエラー個数に対応するページの分布を示す。
第２分布３５０は、第２ビット列のエラー個数に対応するページの分布を示す。
エラー個数３３０およびエラー個数３７０は、各第１ビット列および第２ビット列のエラー個数の平均値を示す。
エラー個数３４０およびエラー個数３８０は、マルチビットメモリ装置の最大エラー訂正能力を示す。
第３分布３２０は、第１ビット列に対してマルチビットメモリ装置がエラーを訂正することができないページ数を示す。
第４分布３６０は、第２ビット列に対してマルチビットメモリ装置がエラーを訂正することができないページ数を示す。
【００２１】
第２エンコーダ１２０は、データシャッフルによってページ単位のエラー分布を調整し、それによってエラー訂正性能以内のエラー比率を有するようにする。
図１の第２エンコーダ１２０は、第１ビット列に対してライン３３０によって表れるエラー個数よりも多いエラーを有するページと、ライン３３０によって表れるエラー個数よりも少ないエラーを有するページのデータとをシャッフルする。第２エンコーダ１２０は、ページ当りエラー比率を均等化（ｅｑｕａｌｉｚｅ）する。
図３を参照すれば、第４分布３６０が第３分布３２０よりも極めて小さいことが分かる。
第２エンコーダ１２０は、ページ別のエラー個数の分布を調整し、エラー訂正可能性を高める。
第２エンコーダ１２０は、データシャッフルによってエラーが特定データの領域で集中的に発生することを防止する。また、第２エンコーダ１２０は、各ページ当りエラー比率を均等化する。
例えば、図３を参照すれば、第４分布３６０は、第３分布３２０よりも小さいことが分かり、これはエラー訂正可能性が高くなったことを示す。
【００２２】
図４は、本発明の一実施形態に係るＥＣＣエンコーダおよびＥＣＣデコーダを備えるシステム４００を示す図である。
図４を参照すれば、システム４００は、ＥＣＣエンコーダ４１０、シャッフラ（ｓｈｕｆｆｌｅｒ）４２０、ランダマイザ（ｒａｎｄｏｍｉｚｅｒ）４３０、メモリチャネル４４０、デランダマイザ（ｄｅ−ｒａｎｄｏｍｉｚｅｒ）４５０、デシャッフラ（ｄｅ−ｓｈｕｆｆｌｅｒ）４６０、およびＥＣＣデコーダ４７０を備える。
ＥＣＣエンコーダ４１０は、入力ビット列を受信し、受信した入力ビット列をＥＣＣエンコードして第１ビット列を生成する。シャッフラ４２０は、Ｍ個の第１ビット列を受信し、受信したＭ個の第１ビット列をシャッフルしてＭ個の第２ビット列を生成する。
ランダマイザ４３０は、第２ビット列を受信し、受信した第２ビット列をランダム化して第３ビット列を生成する。
第３ビット列は、メモリチャネル４４０に送信され、メモリチャネル４４０によって第４ビット列に変換される。
メモリチャネル４４０は、メモリ装置にデータが格納された後のデータが読み出されるまでの時間的な経過であってもよく、メモリチャネル４４０は、メモリ装置にデータが格納されてデータが読み出される過程であってもよい。
第４ビット列および第３ビット列の差が第４ビット列のエラーである。
【００２３】
デランダマイザ４５０は、第４ビット列を受信し、受信した第４ビット列をデランダマイズ（ｄｅ−ｒａｎｄｏｍｉｚｅ）して第５ビット列を生成する。
このとき、デランダマイズ過程は、ランダム化過程を逆に行う過程である。
デシャッフラ４６０は、第５ビット列を受信し、受信した第５ビット列をデシャッフルして第６ビット列を生成する。
このとき、デシャッフル過程は、データシャッフル過程を逆に行う過程である。
ＥＣＣデコーダ４７０は、第６ビット列を受信し、受信した第６ビット列をＥＣＣデコードして第７ビット列を生成する。
ＥＣＣデコーダ４７０は、第６ビット列に含まれたエラーが最大エラー訂正能力よりも大きくなければ、第６ビット列に含まれたエラーを訂正する。ＥＣＣデコーダ４７０は、第６ビット列に含まれたエラーを訂正してエラーの無い第７ビット列を生成する。
再び図１を参照すれば、第２エンコーダ１２０は、第１ビット列のデータをシャッフルして第２ビット列を生成する。
【００２４】
第２エンコーダ１２０が第２ビット列を生成する過程は、図５および図６によって説明する。
図５は、第１ビット列の一例を示す図である。
図５を参照すれば、Ｒ個の第１ビット列が示される。Ｒは「０」よりも大きい整数である。第１ビット列は、ビット列５１０、ビット列５２０、およびビット列５３０を備える。
ビット列５１０は、Ｂ［０］〜Ｂ［Ｃ−１］を含むＣビットのビット列である。
ビット列５２０は、Ｂ［Ｃ］〜Ｂ［２Ｃ−１］を含むＣビットのビット列である。
ビット列５３０は、Ｂ［Ｃ（Ｒ−１）＋（Ｃ−１）］を含むＣビットのビット列である。
【００２５】
図６は、第２エンコーダ１２０が第２ビット列を生成する過程の一実施形態を示す図である。
図６を参照すれば、生成された第２ビット列はビット列６１０およびビット列６２０である。
第２ビット列のｉ番目の要素Ｓｉは、第１ビット列のｊ番目の要素Ｂ［ｊ］から下記の数式６によって得てもよい。
（数式６）
ｊ＝（ｉ×Ｃ＋Ｄ）ｍｏｄ（Ｍ×Ｃ）
Ｓｉ＝Ｂ［ｊ］
ここで、Ｄはデータシャッフル過程のオフセットである。
Ａ  ｍｏｄ  Ｂは、ＡをＢに分けた残りを意味するモジュロ（ｍｏｄｕｌｏ）演算である。
【００２６】
本発明の一実施形態に係る図６を参照すれば、Ｍ＝２である場合のデータシャッフル過程が示される。
本発明の一実施形態によれば、Ｄはデータシャッフル過程においてｉの値によって調整される。
本実施形態では、０以上（Ｍ−１）以下であるｉに対しては、Ｄ＝０が割当てられ、Ｍ以上（２Ｍ−１）以下のｉに対してはＤ＝１が割当てられる。
Ｓ０に対しては、ｊ＝０  ｍｏｄ  ２Ｃ＝０であるため、Ｓ０＝Ｂ［０］の関係式が成立する。
Ｓ１に対しては、ｊ＝Ｃ  ｍｏｄ  ２Ｃ＝Ｃであるため、Ｓ１＝Ｂ［Ｃ］の関係式が成立する。
第２エンコーダ１２０は、Ｓ０およびＳ１を含むビット列６１０を生成する。
Ｓ２に対しては、ｊ＝１  ｍｏｄ  ２Ｃ＝１であるため、Ｓ２＝Ｂ［１］の関係式が成立する。
Ｓ３に対しては、ｊ＝（Ｃ＋１）  ｍｏｄ  ２Ｃ＝Ｃ＋１であるため、Ｓ２＝Ｂ［Ｃ＋１］の関係式が成立する。
第２エンコーダ１２０は、Ｓ２およびＳ３を含むビット列６２０を生成する。
【００２７】
図７は、第２エンコーダ１２０が第２ビット列を生成する過程の他の実施形態を示す図である。
図７を参照すれば、生成された第２ビット列はビット列７１０およびビット列７２０である。
本発明の一実施形態によれば、０以上（Ｍ−１）以下であるｉに対してはＤ＝０が割当てられ、Ｍ以上（２Ｍ−１）以下であるｉに対してはＤ＝１が割当てられる。
Ｓ０に対しては、ｊ＝０  ｍｏｄ  （Ｍ×Ｃ）＝０であるため、Ｓ０＝Ｂ［０］の関係式が成立する。
Ｓ１に対しては、ｊ＝Ｃ  ｍｏｄ  （Ｍ×Ｃ）＝Ｃであるため、Ｓ１＝Ｂ［Ｃ］の関係式が成立する。
Ｓ２に対しては、ｊ＝２Ｃ  ｍｏｄ  （Ｍ×Ｃ）＝２Ｃであるため、Ｓ２＝Ｂ［２Ｃ］の関係式が成立する。
Ｓ３に対しては、ｊ＝３Ｃ  ｍｏｄ  （Ｍ×Ｃ）＝３Ｃであるため、Ｓ３＝Ｂ［３Ｃ］の関係式が成立する。
Ｓ（Ｍ−１）に対しては、ｊ＝｛（Ｍ−１）×Ｃ｝ｍｏｄ（Ｍ×Ｃ）＝（Ｍ−１）×Ｃであるため、Ｓ（Ｍ−１）＝Ｂ［（Ｍ−１）Ｃ］の関係式が成立する。
第２エンコーダ１２０は、Ｓ０、Ｓ１、Ｓ２、Ｓ３およびＳ（Ｍ−１）を含むビット列７１０を生成する。
【００２８】
Ｓ（Ｍ）に対しては、ｊ＝（Ｍ×Ｃ＋１）ｍｏｄ（Ｍ×Ｃ）＝１であるため、Ｓ（Ｍ）＝Ｂ［１］の関係式が成立する。
Ｓ（Ｍ＋１）に対しては、ｊ＝｛（Ｍ＋１）×Ｃ＋１｝ｍｏｄ（Ｍ×Ｃ）＝Ｃ＋１であるため、Ｓ（Ｍ＋１）＝Ｂ［Ｃ＋１］の関係式が成立する。
Ｓ（Ｍ＋２）に対しては、ｊ＝｛（Ｍ＋２）×Ｃ＋１｝ｍｏｄ（Ｍ×Ｃ）＝２Ｃ＋１であるため、Ｓ（Ｍ＋２）＝Ｂ［２Ｃ＋１］の関係式が成立する。
Ｓ（Ｍ＋３）に対しては、ｊ＝｛（Ｍ＋３）×Ｃ＋１｝ｍｏｄ（Ｍ×Ｃ）＝３Ｃ＋１であるため、Ｓ（Ｍ＋３）＝Ｂ［３Ｃ＋１］の関係式が成立する。
Ｓ（２Ｍ−１）に対しては、ｊ＝｛（２Ｍ−１）×Ｃ｝ｍｏｄ（Ｍ×Ｃ）＝（Ｍ−１）Ｃ＋１であるため、Ｓ（２Ｍ−１）＝Ｂ［（Ｍ−１）Ｃ＋１］の関係式が成立する。
第２エンコーダ１２０は、Ｓ（Ｍ）、Ｓ（Ｍ＋１）、Ｓ（Ｍ＋２）、Ｓ（Ｍ＋３）およびＳ（２Ｍ−１）を含むビット列７２０を生成する。
【００２９】
実施形態によっては、第２エンコーダ１２０は、Ｓ０、Ｓ１、…Ｓ（Ｃ−１）までＣビットを含むビット列を第２ビット列に生成してもよい。もし、ＣがＭよりも極めて大きい場合であれば、第２エンコーダ１２０は、Ｓ０、Ｓ１、Ｓ（Ｍ−１）、Ｓ（Ｍ）、Ｓ（Ｍ＋１）、…、Ｓ（２Ｍ）、…、Ｓ（３Ｍ）、…、Ｓ（Ｃ−１）を含むＣビットの第２ビット列を生成してもよい。
実施形態によっては、第２エンコーダ１２０は、１つのページアレイ（図示せず）のマルチビットセルに格納されるデータをシャッフルしてもよい。
このとき、各マルチビットセルはＭビットのデータを格納してもよく、１つのページアレイはＭ×Ｃビットのデータを格納してもよい。
１つのページアレイには、Ｍ番目のページプログラミング動作が行われてデータが格納されてもよい。
他の実施形態によっては、第２エンコーダ１２０は、Ｋ個のページアレイのマルチビットセルに格納されるデータをシャッフルしてもよい。
このとき、各マルチビットセルはＬビットのデータを格納してもよく、１つのページアレイはＬ×Ｃビットのデータを格納してもよい。
１つのページアレイには、Ｌ番目のページプログラミング動作が行われてデータが格納されてもよい。
このとき、Ｍ、Ｌ、Ｋの間にはＭ＝Ｌ×Ｋの関係式が成立し、Ｍ、ＬおよびＫは「０」よりも大きい整数である。
【００３０】
図８は、本発明の他の実施形態に係る第２エンコーダ８００を示す図である。
図８を参照すれば、第２エンコーダ８００は、直列／並列信号処理部８１０、バッファ８２０、およびマルチプレクサ８３０を備える。
直列／並列信号処理部８１０は、Ａ個の第１ビット列を受信し、受信した入力ビット列に対する直列／並列信号処理を行ってＣ×Ａビットのビット列を生成する。
バッファ８２０は、Ｃ×Ａビットのビット列を格納し、マルチプレクサ８３０で格納されたビット列を伝達する。
マルチプレクサ８３０は、Ａ対１の多重化を行う。マルチプレクサは、Ｃ×Ａビットのビット列を多重化してＣビットの第２ビット列を生成する。
【００３１】
図９は、本発明のさらに別の実施形態に係る第３エンコーダ９００を示す図である。ランダム化動作は、第３エンコーダ９００によって行われてもよい。ランダム化動作は、ランダム化多項式ｆ（Ｘ）＝ｆ０＋ｆ１Ｘ＋ｆ２Ｘ２＋・・・＋ｆｎＸｎを含み、ここで、ｆ０、ｆ１、・・・、ｆｎは多項式の係数である。
図９を参照すれば、第３エンコーダ９００は、第１および第２レジスタ９１０、９２０と、第１モジュロ加算器９４０と、複数の乗算器９５０、９６０、９７０とを備える。
モジュロ加算器９４０は、第２ビット列を受信し、受信した第２ビット列に対するモジュロ加算を行って第３ビット列を生成する。
モジュロ加算器９４０の出力は、乗算器９７０に伝達される。乗算器９７０は、係数ｆ２をビット列に乗算して乗算器９５０および乗算器９６０に伝達する。乗算器９５０は、係数ｆ０をビット列に乗算して第１レジスタ９１０に伝達する。乗算器９６０は、係数ｆ１をビット列に乗算してモジュロ加算器９３０に伝達する。
モジュロ加算器９３０は、第１レジスタ９１０および乗算器９６０の出力を合算して第２レジスタ９２０に伝達する。第２レジスタ９２０の結果は、第３ビット列を生成するために第２ビット列に加えられる。
【００３２】
図１０は、本発明の一実施形態に係るエンコード方法を示した動作フローチャートである。
図１０を参照すれば、エンコード方法は、Ｃビットの入力ビット列をエンコードしてＣビットの第１ビット列を生成する（Ｓ１０１０）。
エンコード方法は、第１ビット列をＭ個受信する（Ｓ１０２０）。
エンコード方法は、受信したＭ個の第１ビット列のデータをシャッフルしてＭ個の第２ビット列を生成する（Ｓ１０３０）。
エンコード方法は、第２ビット列を受信する（Ｓ１０４０）。
エンコード方法は、受信した第２ビット列をランダム化して第３ビット列を生成する（Ｓ１０５０）。
実施形態によっては、エンコード方法はＣ個のマルチビットセルを含むページアレイに第２ビット列をプログラミングしてもよい。
このとき、１つのマルチビットセルはＭビットのデータを格納してもよい。
実施形態によっては、第２ビット列のｉ番目の要素Ｓｉは、第１ビット列のｊ番目の要素Ｂ［ｊ］から下記の数式７によって得られる。
（数式７）
ｊ＝（ｉ×Ｃ＋Ｄ）ｍｏｄ（Ｍ×Ｃ）
Ｓｉ＝Ｂ［ｊ］
ここで、Ｄはデータシャッフル過程のオフセットである。
Ａ  ｍｏｄ  ＢはＡをＢに分けた残りを意味するモジュロ演算である。
【００３３】
なお、本発明に係るエンコード方法は、コンピュータにより実現される多様な動作を実行するためのプログラム命令を含むコンピュータ読取可能な記録媒体を含む。当該記録媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むこともでき、記録媒体およびプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知であり使用可能なものであってもよい。コンピュータ読取可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、フロプティカルディスクのような磁気−光媒体、およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を格納して実行するように特別に構成されたハードウェア装置が含まれる。また、記録媒体は、プログラム命令、データ構造などを格納する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体でもある。プログラム命令の例としては、コンパイラによって生成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行され得る高級言語コードを含む。上述したハードウェア装置は、本発明の動作を行うため１つ以上のソフトウェアモジュールとして作動するよう構成され、その逆も同様である。
【００３４】
本発明に係るフラッシュメモリ装置および／またはメモリコントローラは、多様な形態のパッケージを用いて実現されてもよい。例えば、本発明に係るフラッシュメモリ装置および／またはメモリコントローラは、例えば、ＰｏＰｓ（Ｐａｃｋａｇｅ  ｏｎ  Ｐａｃｋａｇｅｓ）、Ｂａｌｌ  Ｇｒｉｄ  Ａｒｒａｙｓ（ＢＧＡｓ）、Ｃｈｉｐ  Ｓｃａｌｅ  Ｐａｃｋａｇｅｓ（ＣＳＰｓ）、Ｐｌａｓｔｉｃ  Ｌｅａｄｅｄ  Ｃｈｉｐ  Ｃａｒｒｉｅｒ（ＰＬＣＣ）、Ｐｌａｓｔｉｃ  Ｄｕａｌ  Ｉｎ−Ｌｉｎｅ  Ｐａｃｋａｇｅ（ＰＤＩＰ）、Ｄｉｅ  ｉｎ  Ｗａｆｆｌｅ  Ｐａｃｋ、Ｄｉｅ  ｉｎ  Ｗａｆｅｒ  Ｆｏｒｍ、Ｃｈｉｐ  Ｏｎ  Ｂｏａｒｄ（ＣＯＢ）、Ｃｅｒａｍｉｃ  Ｄｕａｌ  Ｉｎ−Ｌｉｎｅ  Ｐａｃｋａｇｅ（ＣＥＲＤＩＰ）、Ｐｌａｓｔｉｃ  Ｍｅｔｒｉｃ  Ｑｕａｄ  Ｆｌａｔ  Ｐａｃｋ（ＭＱＦＰ）、Ｑｕａｄ  Ｆｌａｔｐａｃｋ（ＱＦＰ）、Ｓｍａｌｌ  Ｏｕｔｌｉｎｅ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ（ＳＯＩＣ）、Ｓｈｒｉｎｋ  Ｓｍａｌｌ  Ｏｕｔｌｉｎｅ  Ｐａｃｋａｇｅ（ＳＳＯＰ）、Ｔｈｉｎ  Ｓｍａｌｌ  Ｏｕｔｌｉｎｅ（ＴＳＯＰ）、Ｔｈｉｎ  Ｑｕａｄ  Ｆｌａｔｐａｃｋ（ＴＱＦＰ）、Ｓｙｓｔｅｍ  Ｉｎ  Ｐａｃｋａｇｅ（ＳＩＰ）、Ｍｕｌｔｉ  Ｃｈｉｐ  Ｐａｃｋａｇｅ（ＭＣＰ）、Ｗａｆｅｒ−ｌｅｖｅｌ  Ｆａｂｒｉｃａｔｅｄ  Ｐａｃｋａｇｅ（ＷＦＰ）、およびＷａｆｅｒ−Ｌｅｖｅｌ  Ｐｒｏｃｅｓｓｅｄ  Ｓｔａｃｋ  Ｐａｃｋａｇｅ（ＷＳＰ）などのようなパッケージを用いて実現されてもよい。
【００３５】
フラッシュメモリ装置とメモリコントローラは、メモリカードを構成してもよい。このような場合、メモリコントローラは、例えば、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ（ＵＳＢ）、Ｍｕｌｔｉ  Ｍｅｄｉａ  Ｃａｒｄ（ＭＭＣ）、Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ−Ｅｘｐｒｅｓｓ（ＰＣＩ−Ｅ）、Ｓｅｒｉａｌ  Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ａｔｔａｃｈｍｅｎｔ（ＳＡＴＡ）、Ｐａｒａｌｌｅｌ  ＡＴＡ（ＰＡＴＡ）、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ（ＳＣＳＩ）、Ｅｎｈａｎｃｅｄ  Ｓｍａｌｌ  Ｄｅｖｉｃｅ  Ｉｎｔｅｒｆａｃｅ（ＥＳＤＩ）、およびＩｎｔｅｇｒａｔｅｄ  Ｄｒｉｖｅ  Ｅｌｅｃｔｒｏｎｉｃｓ（ＩＤＥ）などのような多様なインタフェースプロトコルのうちの１つによって外部（例えば、ホスト）と通信するよう構成してもよい。
フラッシュメモリ装置は、電力が遮断されても格納されたデータを維持できる不揮発性メモリ装置である。携帯電話、ＰＤＡデジタルカメラ、携帯ゲーム機、およびＭＰ３プレイヤのようなモバイル装置の使用の増加によって、フラッシュメモリ装置はデータストレージだけでなく、コードストレージとしてより幅広く用いられてもよい。フラッシュメモリ装置は、また、ＨＤＴＶ、ＤＶＤ、ルータ、およびＧＰＳのようなホームアプリケーションに用いられてもよい。
【００３６】
本発明に係るコンピュータシステムは、バスに電気的に接続されたマイクロプロセッサ、ユーザインタフェース、ベースバンドチップセットのようなモデム、メモリコントローラ、およびフラッシュメモリ装置を備える。フラッシュメモリ装置には、マイクロプロセッサによって処理された／処理されるＮ−ビットデータ（Ｎは１またはそれより大きい整数）がメモリコントローラによって格納されるであろう。本発明に係るコンピュータシステムがモバイル装置である場合、コンピュータシステムの動作電圧を供給するためのバッテリが追加的に提供されるであろう。
本発明に係るコンピュータシステムには、応用チップセット、カメライメージプロセッサ（Ｃａｍｅｒａ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｏｒ：ＣＩＳ）、モバイルＤＲＡＭなどがさらに提供されることは、この分野における通常の知識を習得した者に自明である。メモリコントローラとフラッシュメモリ装置は、例えば、データを格納するために不揮発性メモリを用いるＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ／Ｄｉｓｋ）を構成してもよい。
【００３７】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当の技術分野において熟練した当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明を多様に修正および変更させることができることを理解することができるであろう。すなわち、本発明の技術的範囲は、特許請求の範囲に基づいて定められ、発明を実施するための最良の形態により限定されるものではない。
【符号の説明】
【００３８】
１００  エンコーダ
１１０  第１エンコーダ
１２０  第２エンコーダ
１３０  プログラミング部
１４０  ページアレイ
２００  エンコードシステム
２１０  第１エンコーダ
２２０  第２エンコーダ
２３０  第３エンコーダ
４００  システム
４１０  ＥＣＣエンコーダ
４２０  シャッフラ
４３０  ランダマイザ
４４０  メモリチャネル
４５０  デランダマイザ
４６０  デシャッフラ
４７０  ＥＣＣでコード
８００  第２エンコーダ
８１０  直列／並列信号処理部
８２０  バッファ
８３０  マルチプレクサ
９００  第３エンコーダ
９１０  第１レジスタ
９２０  第２レジスタ
９３０，９４０  モジュロ加算器
９５０，９６０，９７０  乗算器
【図１】
2011503955.tif 000004
【図２】
2011503955.tif 000005
【図３】
2011503955.tif 000006
【図４】
2011503955.tif 000007
【図５】
2011503955.tif 000008
【図６】
2011503955.tif 000009
【図７】
2011503955.tif 000010
【図８】
2011503955.tif 000011
【図９】
2011503955.tif 000012
【図１０】
2011503955.tif 000013
【国際調査報告】
2011503955.tif 000014
2011503955.tif 000015