(57)【要約】      （修正有）【課題】スループットを低下させることなく異なる符号率の誤り訂正符号を生成する。【解決手段】メモリシステムは、不揮発性メモリと、不揮発性メモリへの書き込み対象であるユーザデータに含まれる複数のシンボルのうち少なくとも１つのシンボルを情報シンボルとして、第１の成分符号と第１の成分符号と異なる第２の成分符号とを含む複数の成分符号を生成する符号化器と、複数の成分符号を不揮発性メモリへ書き込むメモリインタフェースとを備える。符号化器は、複数の成分符号それぞれに対応するパリティを生成する複数の符号化器と、ユーザデータの第１シンボル列を第１シンボル列よりも短い第１シンボル長の複数のチャンクに分割し、分割された複数のチャンクの各々を複数の符号化器のうちの少なくとも異なる２つに入力する第１分配部とを備える。メモリインタフェースは、第１シンボル列及び第１シンボルに対応するパリティを不揮発性メモリに書き込む。【選択図】図５
2019057096.tif 000002
【特許請求の範囲】
【請求項１】
不揮発性メモリと、
前記不揮発性メモリへの書き込み対象であるユーザデータに含まれる複数のシンボルのうち少なくとも１つのシンボルを情報シンボルとして、第１の成分符号と前記第１の成分符号と異なる第２の成分符号とを含む複数の成分符号を生成する符号化器と、
前記複数の成分符号を前記不揮発性メモリへ書き込むメモリインタフェースと、
を備えるメモリシステムであって、
前記符号化器は、
前記複数の成分符号それぞれに対応するパリティを生成する複数の符号化器と、
前記ユーザデータの第１シンボル列を前記第１シンボル列よりも短い第１シンボル長の複数のチャンクに分割し、分割された前記複数のチャンクの各々を前記複数の符号化器のうちの少なくとも異なる２つに入力する第１分配部と、
を備え、
前記メモリインタフェースは、前記第１シンボル列及び前記第１シンボルに対応するパリティを前記不揮発性メモリに書き込む
メモリシステム。
【請求項２】
前記第１の成分符号は、第１の次元の成分符号であり、
前記第２の成分符号は、前記第１の次元とは異なる第２の次元の成分符号であり、
前記複数の符号化器は、前記第１の次元の成分符号のパリティを生成する１つ以上の第１符号化器と、前記第２の次元の成分符号のパリティを生成する１つ以上の第２符号化器とを含み、
前記第１分配部は、前記チャンクを、前記１つ以上の第１符号化器のいずれかと、前記１つ以上の第２符号化器のいずれかとにそれぞれ入力する
請求項１に記載のメモリシステム。
【請求項３】
前記複数の成分符号における少なくとも２つの組合せには、前記第１シンボル列における少なくとも１つのシンボルを多重に保護する有効な組合せと、前記第１シンボル列におけるシンボルを多重には保護しない無効な組合せとが存在し、
前記第１分配部は、前記チャンクの数が前記複数の成分符号の前記有効な組合せの数以下である場合、前記複数のチャンクのうち１のチャンクを入力する前記成分符号の符号化器の組合せが、他のチャンクを入力する前記成分符号の符号化器の組合せと重複しないように、前記複数のチャンクそれぞれの入力先となる符号化器の組合せを決定する
請求項１に記載のメモリシステム。
【請求項４】
前記複数の成分符号における少なくとも２つの組合せには、前記第１シンボル列における少なくとも１つのシンボルを多重に保護する有効な組合せと、前記第１シンボル列におけるシンボルを多重には保護しない無効な組合せとが存在し、
前記第１分配部は、前記チャンクの数が前記複数の成分符号の前記有効な組合せの数よりも大きい場合、前記有効な組合せの全通りに対して前記複数のチャンクのうちの一部のチャンクの入力先を割り当てた後、残りのチャンクに対しては既に前記入力先として割り当てられた組合せと重複する組合せを入力先として決定する請求項１に記載のメモリシステム。
【請求項５】
前記複数の成分符号における少なくとも２つの組合せには、前記第１シンボル列における少なくとも１つのシンボルを多重に保護する有効な組合せと、前記第１シンボル列におけるシンボルを多重には保護しない無効な組合せとが存在し、
前記第１分配部は、前記チャンクの数が前記複数の成分符号の前記有効な組合せの数よりも大きい場合、前記有効な組合せそれぞれに入力されるチャンクの数の差が所定の閾値以下となるように、前記複数のチャンクそれぞれの入力先となる符号化器の組合せを決定する請求項３に記載のメモリシステム。
【請求項６】
前記第１分配部は、前記チャンクの数が前記第１の次元の成分符号の符号化器の数より大きい場合、前記複数の第１の次元の成分符号の符号化器それぞれに入力されるチャンクの数の差が所定の閾値以下となるように、前記複数のチャンクそれぞれの入力先となる第１の次元の成分符号の符号化器を決定する請求項２に記載のメモリシステム。
【請求項７】
前記第１分配部は、前記チャンクの数が前記第２の次元の成分符号の符号化器の数より大きい場合、前記複数の第２の次元の成分符号の符号化器それぞれに入力されるチャンクの数の差が所定の閾値以下となるように、前記複数のチャンクそれぞれの入力先となる第２の次元の成分符号の符号化器を決定する請求項２に記載のメモリシステム。
【請求項８】
前記第１分配部は、
前記複数のチャンクを前記第１シンボル列の配列に従って順番に前記複数の第１の次元の成分符号の符号化器のいずれかに入力する第１巡回セレクタと、
前記複数のチャンクを前記第１シンボル列の配列に従って順番に前記複数の第２の次元の成分符号の符号化器のいずれかに入力する第２巡回セレクタと、
を備え、
前記第１分配部は、前記第１の次元の成分符号の数と同数のサイクル数の第１周期を前記第１巡回セレクタに設定するとともに、前記第２の次元の成分符号の数と同数のサイクル数の第２周期を前記第２巡回セレクタに設定し、
前記第１巡回セレクタは、前記第１周期の前記サイクル数と同数の前記第１符号化器に前記複数のチャンクを分散して入力し、
前記第２巡回セレクタは、前記第２周期の前記サイクル数と同数の前記第２符号化器に前記複数のチャンクを分散して入力する
請求項２に記載のメモリシステム。
【請求項９】
前記第１分配部は、前記複数のチャンクと前記複数の成分符号それぞれのパリティとが入力されるセレクタをさらに備え、
前記セレクタは、前記複数の成分符号における第３の成分符号のパリティを計算した後、前記第３の成分符号の前記パリティを、パリティの計算が未だ済んでいない第４の成分符号の符号化器に入力する
請求項２に記載のメモリシステム。
【請求項１０】
前記第１分配部は、前記第１シンボル長以上であって前記第１シンボル列よりも短い第２シンボル長の第２シンボル列を単位として前記ユーザデータを入力し、前記第２シンボル列を前記１つ以上のチャンクに分割する請求項１に記載のメモリシステム。
【請求項１１】
前記第１の成分符号の第１シンドロームを計算する第１シンドローム計算器と、
前記第２の成分符号の第２シンドロームを計算する第２シンドローム計算器と、
前記メモリインタフェースが前記不揮発性メモリから読み出した第３シンボル列を前記第１分配部と同じ前記第１シンボル長の複数のチャンクに分割し、当該分割により生成された前記複数のチャンクのうち前記ユーザデータに対応するチャンク及び前記第１パリティに対応するチャンクを前記第１シンドローム計算器に入力し、前記読出し対象のユーザデータに対応する前記チャンク及び前記第２パリティに対応するチャンクを前記第２シンドローム計算器に入力する第２分配部と、
前記第１シンドローム計算器で計算された前記第１シンドローム及び前記第２シンドローム計算器で計算された前記第２シンドロームを保持するシンドロームメモリと、
前記シンドロームメモリに保持された前記第１シンドローム及び前記第２シンドロームを復号することで、前記シンボル列におけるエラーシンボルを検出し、検出した前記エラーシンボルを訂正するシンドローム復号器と、
を備える請求項１に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下の実施形態は、一般的に、メモリシステムに関する。
【背景技術】
【０００２】
メモリシステムでは、一般に、記憶するデータを保護するために、誤り訂正符号化されたデータが記憶される。このため、メモリシステムに記憶されたデータを読み出す際には、誤り訂正符号化されたデータに対する復号が行われる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−６５９６９号公報
【特許文献２】米国特許出願公開第２００７／０１９５８９４号明細書
【特許文献３】特開２００４−２８８２８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、スループットを低下させることなく異なる符号率の誤り訂正符号を生成することが可能なメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
実施形態によれば、メモリシステムは、不揮発性メモリと、前記不揮発性メモリへの書き込み対象であるユーザデータに含まれる複数のシンボルのうち少なくとも１つのシンボルを情報シンボルとして、第１の成分符号と前記第１の成分符号と異なる第２の成分符号とを含む複数の成分符号を生成する符号化器と、前記複数の成分符号を前記不揮発性メモリへ書き込むメモリインタフェースと、を備えるメモリシステムであって、前記符号化器は、前記複数の成分符号それぞれに対応するパリティを生成する複数の符号化器と、前記ユーザデータの第１シンボル列を前記第１シンボル列よりも短い第１シンボル長の複数のチャンクに分割し、分割された前記複数のチャンクの各々を前記複数の符号化器のうちの少なくとも異なる２つに入力する第１分配部とを備え、前記メモリインタフェースは、前記第１シンボル列及び前記第１シンボルに対応するパリティを前記不揮発性メモリに書き込む。
【図面の簡単な説明】
【０００６】
【図１】図１は、データを誤り訂正符号で保護する動作の一般的な流れを説明するための図である。
【図２】図２は、２次元の成分符号で構成された積符号の一例を示す図である。
【図３】図３は、図２に例示した積符号を生成するように構成された符号化部の一例を示すブロック図である。
【図４】図４は、２次元の積符号の他の一例を示す図である。
【図５】図５は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。
【図６】図６は、第１の実施形態に係る符号化部の概略構成例を示すブロック図である。
【図７】図７は、第１の実施形態によって生成される多次元の誤り訂正符号の例であって、次元１の成分符号の数が５で且つ次元２の成分符号の数が２の積符号の例を示す図である。
【図８】図８は、第１の実施形態によって生成される多次元の誤り訂正符号の例であって、次元１の成分符号の数が５で且つ次元２の成分符号の数が１の積符号の例を示す図である。
【図９】図９は、第１の実施形態によって生成される多次元の誤り訂正符号の例であって、次元１の成分符号の数が５で且つ次元２の成分符号の数が２の積符号の他の例を示す図である。
【図１０】図１０は、第２の実施形態に係る符号化部の概略構成例を示すブロック図である。
【図１１】図１１は、第２の実施形態によって生成される多次元の誤り訂正符号の一例を示す図である。
【図１２】図１２は、第３の実施形態に係る復号部の概略構成例を示すブロック図である。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態に係るメモリシステムを詳細に説明する。なお、以下の実施形態により本発明が限定されるものではない。
【０００８】
近年、ＮＡＮＤ型フラッシュメモリなどの不揮発性メモリを利用したメモリシステムは、その高速性という特長を生かし、様々な場所で用いられている。しかしながら、不揮発性メモリから読み出したデータには、不揮発性メモリに記録されてからの時間経過や読み出し・書き込みの際に生じるノイズ等に起因するエラーが含まれる可能性がある。そのため、一般には、不揮発性メモリに記録するデータに対して誤り訂正符号を用いた符号化処理が実行され、読出し時にはその誤り訂正符号を用いた復号処理が実行されることで、読み出したデータに含まれているエラーが除去される。
【０００９】
図１は、データを誤り訂正符号で保護する動作の一般的な流れを説明するための図である。なお、本説明におけるユーザとは、例えばパーソナルコンピュータ、サーバ装置、ポータブルな情報機器、デジタルスチルカメラ等の情報処理装置（ホストともいう）であってよい。
【００１０】
ユーザ９３１は、書込み対象のデータ（以下、書込みデータという）をメモリシステム９００に対して送信する。メモリシステム９００は、ユーザ９３１から受け取った書込みデータを符号化部９４１を用いて符号化し、これにより生成された符号化データ（符号語）を不揮発性メモリ９２０に書き込む。したがって、不揮発性メモリ９２０に書き込まれる符号化データには、基本的にはエラーが含まれていない。
【００１１】
不揮発性メモリ９２０に格納されている符号化データは、例えばユーザ９３２からの読出し要求に応じて読み出される。ここで、読み出された符号化データにはエラーが含まれている可能性がある。そこで、読み出された符号化データに含まれるエラーを復号部９４２を用いて除去しつつ復号を実行することで、オリジナルの符号化データが復元される。その後、オリジナルの符号化データもしくは復元された符号化前の書き込みデータがユーザ９３２へ送信される。なお、読出し要求を発行したユーザ９３２は、書込み要求を発行したユーザ９３１と同一のユーザであってもよいし、別のユーザであってもよい。
【００１２】
このようなメモリシステムに実装される誤り訂正機能には、積符号などの多次元の誤り訂正符号を適用することができる。ここで、多次元の誤り訂正符号とは、誤り訂正符号の少なくとも一つ以上の構成単位であるシンボルが、複数のより小規模な成分符号によって多重に保護されているものを指す。また、１シンボルは、例えば１ビット（二元体（binary field）の元（element））、又は、二元体以外の有限体（finite field）などのアルファベットの元で構成される。
【００１３】
図２は、２次元の成分符号で構成された積符号の一例を示す図である。図２に示す積符号１００では、全てのシンボルが行方向（次元１と称される）および列方向（次元２と称される）の成分符号によって二重に保護されている。なお、多次元の誤り訂正符号としてはこれに限らず、例えば一般化ＬＤＰＣ符号（Generalized Low Density Parity Check Code）などであってもよい。一般化ＬＤＰＣ符号を含む一般の多次元の誤り訂正符号では、シンボルごとに保護の多重度が異なっていてもよく、また、成分符号を次元１と次元２のようにグループ分けすることができないが、このような符号構成に対しても本技術は適用することが可能である。
【００１４】
図２に例示する積符号１００は、ｄ００〜ｄ１９の２０個の情報ビットと、ｒ００〜ｒ４１及びｃ００〜ｃ１１の１４個のパリティとから構成されている。以下、任意の情報ビットをｄｋと記し、次元１のｉ番目の成分符号におけるｊ番目のパリティをｒｉｊと記し、次元２のｉ番目の成分符号におけるｊ番目のパリティをｃｉｊと記す。また、図２に示す積符号１００は、５つの次元１の成分符号１０１〜１０５と、２つの次元２の成分符号１１１及び１１２とを備える。次元１の各成分符号１０１〜１０５それぞれは、４つの情報ビットと、２つのパリティを含んでいる。次元２の各成分符号１１１及び１１２それぞれは、１０個の情報ビットと、２つのパリティとを含んでいる。
【００１５】
図３は、図２に例示した積符号を生成するように構成された符号化部の一例を示すブロック図である。図３に示すように、符号化部９４１は、積符号１００を効率的に符号化するために、１サイクルにユーザデータにおける４つの情報ビットを入力し、入力された４つの情報ビットに対して、次元１方向の符号化及び次元２方向の符号化を同時に実行するように構成されている。１サイクルごとにユーザ９３１から入力された４つの情報ビットは、入力ビット毎に用意された４つのバッファ９０１〜９０４に一時保持された後、次元１符号化器９１１と２つの次元２符号化器９２１及び９２２とにそれぞれ入力される。その際、４つの情報ビットのうち前半の２つは次元２符号化器９２１に入力され、後半の２つは次元２符号化器９２２に入力される。
【００１６】
次元１符号化器９１１は、ｃ番目のサイクルでは、ｃ番目の次元１の成分符号のパリティを生成して出力する。２つの次元２符号化器９２１及び９２２は、全ての情報ビットが入力された後に、次元２の成分符号に対するパリティをそれぞれ生成する。次元１符号化器９１１で生成された次元１のパリティと、次元２符号化器９２１及び９２２で生成されたパリティとは、ユーザ９３１から入力されたユーザデータと連接される。これにより、符号語（符号化データ）が生成される。生成された符号語は、不揮発性メモリ９２０に書き込まれる。
【００１７】
このような構成において、バッファと次元２符号化器とを結ぶ配線の数は、各次元の成分符号の数に依存する。したがって、成分符号の数を変更して多次元の誤り訂正符号の符号化率を変更するには、バッファと次元２符号化器とを結ぶ配線を変更する必要がある。これは、符号化率を変更するには、異なる符号化部を用いなければならないことを意味しており、符号化部の汎用性を妨げる要因となっていた。
【００１８】
また、図３に示す符号化部９４１を異なる構造の誤り訂正符号に適用した場合、スループットが低下してしまう場合がある。図４は、２次元の積符号の他の一例を示す図である。図４に示す積符号２００は、ｄ００〜ｄ０９の１０個の情報ビットと、ｒ００〜ｒ４１及びｃ００〜ｃ０１の１２個のパリティと、１０個のダミービット（０ビット）から構成されている。また、積符号２００は、５つの次元１の成分符号２０１〜２０５と、１つの次元２の成分符号２１１とを備える。次元１の各成分符号２０１〜２０５それぞれは、２つの情報ビットと、２つのダミービットと、２つのパリティを含んでいる。次元２の各成分符号２１１は、１０個の情報ビットと、２つのパリティを含んでいる。
【００１９】
図４に例示するように、２列に並んだ情報ビットの右側に２列のダミービットを埋め込むことで、図２に例示した積符号１００と同様に、図３に示す符号化部９４１を用いて積符号２００を符号化することが可能である。しかしながら、この場合、１サイクルに符号化部９４１に入力される情報ビットの数が、図２に例示する積符号１００の場合の半分（２ビット）となるため、符号化部９４１のスループットが半分に低下してしまう。このように、同一の符号化部を用いて異なる符号化率の符号化を実行するとスループットが低下してしまう場合がある。
【００２０】
そこで、以下の実施形態では、スループットを低下させることなく異なる符号化率の符号化が可能なメモリシステムについて、例を挙げて説明する。なお、以下の実施形態では、誤り訂正符号として、２次元の積符号を例示するが、これに限定されず、上述したような誤り訂正符号の少なくとも一つ以上の構成単位であるシンボルが複数のより小規模な成分符号によって多重に保護される多次元の誤り訂正符号を用いることが可能である。
【００２１】
（第１の実施形態）
まず、第１の実施形態に係るメモリシステムについて、図面を参照して詳細に説明する。図５は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。図５に示すように、メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とを備える。メモリシステム１は、ホスト３０と接続可能であり、図５ではホスト３０と接続された状態が示されている。ホスト３０は、例えば、パーソナルコンピュータ、携帯端末などの電子機器であってよい。
【００２２】
不揮発性メモリ２０は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤ型フラッシュメモリ（以下、単にＮＡＮＤメモリという）である。以下の説明では、不揮発性メモリ２０としてＮＡＮＤメモリが用いられた場合を例示するが、不揮発性メモリ２０として３次元構造フラッシュメモリ、ＲｅＲＡＭ（Resistance Random Access Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）等のＮＡＮＤメモリ以外の記憶装置を用いることも可能である。また、不揮発性メモリ２０が半導体メモリであることは必須ではなく、半導体メモリ以外の種々の記憶媒体に対して本実施形態を適用することも可能である。
【００２３】
メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とが１つのパッケージとして構成されるメモリカード等であってもよいし、ＳＳＤ（Solid State Drive）等であってもよい。
【００２４】
メモリコントローラ１０は、ホスト３０からの書込み要求に従って不揮発性メモリ２０への書込みを制御する。また、ホスト３０からの読出し要求に従って不揮発性メモリ２０からの読み出しを制御する。メモリコントローラ１０は、ホストＩ／Ｆ（ホストインタフェース）１５、メモリＩ／Ｆ（メモリインタフェース）１３、制御部１１、符号化／復号部（コーデック）１４およびデータバッファ１２を備える。ホストＩ／Ｆ１５、メモリＩ／Ｆ１３、制御部１１、符号化／復号部１４およびデータバッファ１２は、内部バス１６で相互に接続されている。
【００２５】
ホストＩ／Ｆ１５は、ホスト３０との間のインタフェース規格に従った処理を実施し、ホスト３０から受信した命令、書込み対象のユーザデータなどを内部バス１６に出力する。また、ホストＩ／Ｆ１５は、不揮発性メモリ２０から読み出されて復元されたユーザデータ、制御部１１からの応答などをホスト３０へ送信する。
【００２６】
メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０への書込み処理を行う。また、メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０からの読み出し処理を行う。
【００２７】
制御部１１は、メモリシステム１の各構成要素を統括的に制御する。制御部１１は、ホスト３０からホストＩ／Ｆ１５経由で命令を受けた場合に、その命令に従った制御を行う。例えば、制御部１１は、ホスト３０からの命令に従って、不揮発性メモリ２０へのユーザデータおよびパリティの書き込みをメモリＩ／Ｆ１３へ指示する。また、制御部１１は、ホスト３０からの命令に従って、不揮発性メモリ２０からのユーザデータおよびパリティの読み出しをメモリＩ／Ｆ１３へ指示する。
【００２８】
また、制御部１１は、ホスト３０から書込み要求を受信した場合、データバッファ１２に蓄積されるユーザデータに対して、不揮発性メモリ２０上の格納領域（メモリ領域）を決定する。すなわち、制御部１１は、ユーザデータの書込み先を管理する。ホスト３０から受信したユーザデータの論理アドレスと該ユーザデータが格納された不揮発性メモリ２０上の格納領域を示す物理アドレスとの対応はアドレス変換テーブルとして格納される。
【００２９】
また、制御部１１は、ホスト３０から読出し要求を受信した場合、読出し要求により指定された論理アドレスを上述のアドレス変換テーブルを用いて物理アドレスに変換し、該物理アドレスからの読み出しをメモリＩ／Ｆ１３へ指示する。
【００３０】
ＮＡＮＤメモリでは、一般に、ページと呼ばれるデータ単位で、書き込みおよび読み出しが行われ、ブロックと呼ばれるデータ単位で消去が行われる。本実施形態では、この同一のワード線に接続される複数のメモリセルをメモリセルグループと呼ぶ。メモリセルがシングルレベルセル（ＳＬＣ）である場合は、１つのメモリセルグループが１ページに対応する。メモリセルがマルチレベルセル（ＭＬＣ）である場合は、１つのメモリセルグループが複数ページに対応する。また、各メモリセルはワード線に接続するとともにビット線にも接続される。したがって、各メモリセルは、ワード線を識別するアドレスとビット線を識別するアドレスとで識別することが可能である。
【００３１】
データバッファ１２は、メモリコントローラ１０がホスト３０から受信したユーザデータを不揮発性メモリ２０へ記憶するまでに一時格納する。また、データバッファ１２は、不揮発性メモリ２０から読み出したユーザデータをホスト３０へ送信するまでに一時格納する。データバッファ１２には、例えば、ＳＲＡＭ（Static Random Access Memory）やＤＲＡＭ（Dynamic Random Access Memory）などの汎用メモリを用いることができる。
【００３２】
ホスト３０から送信されるユーザデータは、内部バス１６に転送されてデータバッファ１２に一旦格納される。符号化／復号部１４は、不揮発性メモリ２０に格納されるユーザデータを符号化して符号語を生成する。また、符号化／復号部１４は、不揮発性メモリ２０から読み出された受信語を復号してユーザデータを復元する。そこで符号化／復号部１４は、符号化部（Encoder）１７と復号部（Decoder）１８を備える。なお、符号化／復号部１４により符号化されるデータには、ユーザデータ以外にも、メモリコントローラ１０内部で用いる制御データ等が含まれてもよい。
【００３３】
次に、本実施形態の書込み処理について説明する。制御部１１は、不揮発性メモリ２０への書込み時に、ユーザデータの符号化を符号化部１７に指示する。その際、制御部１１は、不揮発性メモリ２０における符号語の格納場所（格納アドレス）を決定し、決定した格納場所もメモリＩ／Ｆ１３へ指示する。
【００３４】
符号化部１７は、制御部１１からの指示に基づいて、データバッファ１２上のユーザデータを符号化して符号語を生成する。符号化方式としては、例えば、ＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号やＲＳ（リード・ソロモン）符号を用いた符号化方式を採用することができる。符号化部１７により生成される符号語は、後述において図７〜図９を用いて例示するような多次元の誤り訂正符号である。メモリＩ／Ｆ１３は、制御部１１から指示された不揮発性メモリ２０上の格納場所へ符号語を格納する制御を行う。
【００３５】
次に、本実施形態の不揮発性メモリ２０からの読出し時の処理について説明する。制御部１１は、不揮発性メモリ２０からの読出し時に、不揮発性メモリ２０上のアドレスを指定してメモリＩ／Ｆ１３へ読み出しを指示する。また、制御部１１は、復号部１８へ復号の開始を指示する。メモリＩ／Ｆ１３は、制御部１１の指示に従って、不揮発性メモリ２０の指定されたアドレスから受信語を読み出し、読み出した受信語を復号部１８に入力する。復号部１８は、この不揮発性メモリ２０から読み出された受信語を復号する。
【００３６】
つづいて、図５に示す符号化部１７のより詳細な構成について、図面を参照して詳細に説明する。図６は、本実施形態に係る符号化部の概略構成例を示すブロック図である。なお、図６では、説明の明確化のため、メモリコントローラ１０における他の構成が省略されている。
【００３７】
図６に示すように、符号化部１７は、データバッファ１２から１サイクルごとに入力された情報ビットを分配する分配部１７０と、次元１の成分符号の数（５つ）と同数の次元１符号化器１７３ａ〜１７３ｅと、次元２の成分符号の数（２つ）と同数の次元２符号化器１７４ａ及び１７４ｂと、それぞれの次元に設けられたセレクタ１７５及び１７６とを備える。また、分配部１７０は、それぞれの次元に設けられた巡回セレクタ１７１及び１７２を備える。
【００３８】
ホスト３０から書込み対象として書込み要求とともに入力されたユーザデータは、上述したように、データバッファ１２に一時格納される。符号化部１７へは、データバッファ１２に格納されているユーザデータが、１サイクルにつき４つの情報ビットずつ入力される。
【００３９】
符号化部１７に入力された４つの情報ビットは、メモリＩ／Ｆ１３を介して不揮発性メモリ２０に書き込まれるとともに、分配部１７０に入力される。分配部１７０は、４つの情報ビットを１又は数ビット（本例では２ビット）ずつの複数（本例では２つ）のグループ（以下、チャンクという）に分割し、これにより生成された複数のチャンクを各次元の巡回セレクタ１７１及び１７２にそれぞれ順次入力する。
【００４０】
次元１の巡回セレクタ１７１は、順次入力された複数のチャンクを、この順番通りで且つ設定された周期に従って、次元１符号化器１７３ａ〜１７３ｅのいずれかに入力する。例えば次元１の成分符号の数が５であり、５つの次元１符号化器１７３ａ〜１７３ｅを使用する場合、巡回セレクタ１７１の周期は５サイクルに設定される。なお、巡回セレクタ１７１及び１７２に対する周期の設定は、分配部１７０が行なってもよい。
【００４１】
次元１符号化器１７３ａ〜１７３ｅは、データバッファ１２に格納されているユーザデータの全ての情報ビットが分配部１７０を介して次元１符号化器１７３ａ〜１７３ｅに分配されると、それぞれに入力された複数のチャンクを符号化することで次元１のパリティを生成し、生成した次元１のパリティを次元１のセレクタ１７５へ出力する。例えばｄ００及びｄ０１の情報ビットよりなるチャンクとｄ１０及びｄ１１の情報ビットよりなるチャンクとの２つのチャンクが次元１符号化器１７３ａに順次入力された場合、次元１符号化器１７３ａは、ｄ００、ｄ０１、ｄ１０及びｄ１１の情報ビットからパリティｒ００及びｒ０１とを生成し、生成したパリティｒ００及びｒ０１をセレクタ１７５へ出力する。次元１符号化器１７３ｂ〜１７３ｅについても同様に、順次入力された２つのチャンクからパリティｒ１０〜ｒ４１を生成してセレクタ１７５へ出力する。
【００４２】
一方、巡回セレクタ１７２は、順次入力された複数のチャンクを、この順番通りに所定の周期に従って、次元２符号化器１７４ａ及び１７４ｂのいずれかに入力する。例えば次元２の成分符号の数が２であり、２つの次元２符号化器１７４ａ及び１７４ｂを使用する場合、巡回セレクタ１７２の周期は２サイクルに設定される。その場合、分配部１７０に１サイクルで入力された情報ビットは２つのチャンクに分割され、１番目のチャンクが１番目の次元２符号化器１７４ａに入力されるとともに、２番目のチャンクが２番目の次元２符号化器１７４ｂに入力される。
【００４３】
次元２符号化器１７４ａ及び１７４ｂは、データバッファ１２に格納されているユーザデータの全ての情報ビットが分配部１７０を介して次元２符号化器１７４ａ又は１７４ｂに分配されると、それぞれに入力された情報ビットに対する符号化を実行して次元２のパリティを生成し、生成したパリティを次元２のセレクタ１７６へ出力する。例えば次元２符号化器１７４ａは、ユーザデータの全ての情報ビットｄ００〜ｄ１９の分配部１７０による分配が完了すると、入力された情報ビットｄ００、ｄ０１、ｄ０４、ｄ０５、ｄ０８、ｄ０９、ｄ１２、ｄ１３、ｄ１６及びｄ１７を符号化してパリティｃ００及びｃ０１を生成し、生成したパリティｃ００及びｃ０１をセレクタ１７６へ出力する。同様に、次元２符号化器１７４ｂは、ユーザデータの全ての情報ビットｄ００〜ｄ１９の分配部１７０による分配が完了すると、入力された情報ビットｄ０２、ｄ０３、ｄ０６、ｄ０７、ｄ１０、ｄ１１、ｄ１４、ｄ１５、ｄ１８及びｄ１９を符号化してパリティｃ１０及びパリティｃ１１を生成し、生成したパリティｃ１０及びｃ１１をセレクタ１７６へ出力する。
【００４４】
次元１のセレクタ１７５は、次元１符号化器１７３ａ〜１７３ｅそれぞれから次元１のパリティｒ００〜ｒ４１が入力されると、この入力されたパリティｒ００〜ｒ４１をメモリＩ／Ｆ１３に入力する。これに対し、メモリＩ／Ｆ１３は、入力された次元１のパリティｒ００〜ｒ４１を不揮発性メモリ２０に書き込む。次元２のセレクタ１７６も同様に、次元２符号化器１７４ａ及び１７４ｂそれぞれから次元２のパリティｃ００〜ｃ１１が入力されると、この入力されたパリティｃ００〜ｃ１１をメモリＩ／Ｆ１３に入力する。メモリＩ／Ｆ１３は、入力された次元２のパリティｃ００〜ｃ１１を不揮発性メモリ２０に書き込む。これにより、不揮発性メモリ２０内には、例えば後述において図７を用いて説明する積符号３００が書き込まれる。
【００４５】
図７は、符号化部１７によって生成される多次元の誤り訂正符号の例であって、次元１の成分符号の数が５で且つ次元２の成分符号の数が２の積符号の例を示す図である。図７に示す積符号３００は、図２に示す積符号１００と同様に、ｄ００〜ｄ１９の合計２０個の情報ビットと、ｒ００〜ｒ４１及びＣ００〜Ｃ１１の合計１４個のパリティとから構成されている。ただし、積符号３００では、情報ビットの並びが、ユーザデータにおける情報ビットの並びと一致していない。
【００４６】
このような積符号３００を生成する場合、符号化部１７における次元１の巡回セレクタ１７１の周期が５サイクルに設定され、次元２の巡回セレクタ１７２の周期が２サイクルに設定される。分配部１７０は、１サイクルごとに入力される４つの情報ビットを、それぞれ２つの情報ビットよりなる２つのチャンクに分割し、これにより生成された２つのチャンクを巡回セレクタ１７１及び１７２それぞれに順次入力する。
【００４７】
積符号３００の生成動作をより詳細に説明すると、符号化部１７には、ｄ００〜ｄ１９の合計２０個の情報ビットが１サイクルにつき４つの情報ビットずつ入力される。入力された情報ビットは、メモリＩ／Ｆ１３を介して不揮発性メモリ２０に順次書き込まれるとともに、符号化部１７内の分配部１７０に入力される。
【００４８】
分配部１７０は、まず、４つの情報ビットｄ００〜ｄ０３が入力されると、この情報ビットｄ００〜ｄ０３を分割して２つのチャンク（ｄ００，ｄ０１）及び（ｄ０２，ｄ０３）を生成し、これらを巡回セレクタ１７１及び１７２それぞれに入力する。以降、同様に動作することで、チャンク（ｄ０４，ｄ０５）及び（ｄ０６，ｄ０７）、（ｄ０８，ｄ０９）及び（ｄ１０，ｄ１１）、（ｄ１２，ｄ１３）及び（ｄ１４，ｄ１５）、（ｄ１６，ｄ１７）及び（ｄ１８，ｄ１９）を順次生成する。
【００４９】
次元１の巡回セレクタ１７１は、順番に入力されたチャンク（ｄ００，ｄ０１）〜（ｄ１８，ｄ１９）のうち、１番目のチャンク（ｄ００，ｄ０１）を１番目の次元１符号化器１７３ａに入力し、２番目のチャンク（ｄ０２，ｄ０３）を２番目の次元１符号化器１７３ｂに入力し、３番目のチャンク（ｄ０４，ｄ０５）を３番目の次元１符号化器１７３ｃに入力し、４番目のチャンク（ｄ０６，ｄ０７）を４番目の次元１符号化器１７３ｄに入力し、５番目のチャンク（ｄ０８，ｄ０９）を５番目の次元１符号化器１７３ｅに入力する。また、巡回セレクタ１７１に設定された周期は５サイクルである。したがって、巡回セレクタ１７１は、６番目以降のチャンクについては、６番目のチャンク（ｄ１０，ｄ１１）を１番目の次元１符号化器１７３ａに入力し、７番目のチャンク（ｄ１２，ｄ１３）を２番目の次元１符号化器１７３ｂに入力し、８番目のチャンク（ｄ１４，ｄ１５）を３番目の次元１符号化器１７３ｃに入力し、９番目のチャンク（ｄ１６，ｄ１７）を４番目の次元１符号化器１７３ｄに入力し、１０番目のチャンク（ｄ１８，ｄ１９）を５番目の次元１符号化器１７３ｅに入力する。
【００５０】
一方、次元２の巡回セレクタ１７２は、順番に入力されたチャンク（ｄ００，ｄ０１）〜（ｄ１８，ｄ１９）を次元２符号化器１７４ａ及び１７４ｂに交互に入力する。したがって、次元２符号化器１７４ａには、チャンク（ｄ００，ｄ０１）、（ｄ０４，ｄ０５）、（ｄ０８，ｄ０９）、（ｄ１２，ｄ１３）及び（ｄ１６，ｄ１７）が入力され、次元２符号化器１７４ｂには、チャンク（ｄ０２，ｄ０３）、（ｄ０６，ｄ０７）、（ｄ１０，ｄ１１）、（ｄ１４，ｄ１５）及び（ｄ１８，ｄ１９）が入力される。
【００５１】
ここで、各チャンクが入力される次元１符号化器１７３ａ〜１７３ｅと次元２符号化器１７４ａ及び１７４ｂとの組合せを整理すると、チャンク（ｄ００，ｄ０１）は次元１符号化器１７３ａと次元２符号化器１７４ａとの組合せに入力され、チャンク（ｄ０２，ｄ０３）は次元１符号化器１７３ｂと次元２符号化器１７４ｂとの組合せに入力され、チャンク（ｄ０４，ｄ０５）は次元１符号化器１７３ｃと次元２符号化器１７４ａとの組合せに入力され、チャンク（ｄ０６，ｄ０７）は次元１符号化器１７３ｄと次元２符号化器１７４ｂとの組合せに入力され、チャンク（ｄ０８，ｄ０９）は次元１符号化器１７３ｅと次元２符号化器１７４ａとの組合せに入力され、チャンク（ｄ１０，ｄ１１）は次元１符号化器１７３ａと次元２符号化器１７４ｂとの組合せに入力され、チャンク（ｄ１２，ｄ１３）は次元１符号化器１７３ｂと次元２符号化器１７４ａとの組合せに入力され、チャンク（ｄ１４，ｄ１５）は次元１符号化器１７３ｃと次元２符号化器１７４ｂとの組合せに入力され、チャンク（ｄ１６，ｄ１７）は次元１符号化器１７３ｄと次元２符号化器１７４ａとの組合せに入力され、チャンク（ｄ１８，ｄ１９）は次元１符号化器１７３ｅと次元２符号化器１７４ｂとの組合せに入力されている。
【００５２】
このように本実施形態では、ユーザデータから生成されるチャンクの数（１０）が次元１符号化器１７３ａ〜１７３ｅの数（５）と次元２符号化器１７４ａ及び１７４ｂの数（２）とを掛け合わせた数（１０＝５×２）以下である場合、分配部１７０は、あるチャンクを入力する次元１符号化器と次元２符号化器との組合せが、他のチャンクを入力する次元１符号化器と次元２符号化器との組合せと重複しないように、各チャンクの入力先となる次元１符号化器と次元２符号化器との組合せを決定する。言い換えれば、分配部１７０は、あるチャンクを入力する各次元の符号化器の組合せが、他のチャンクを入力する各次元の符号化器の組合せと重複しないように、次元１の巡回セレクタ１７１に設定する周期のサイクル数と次元２の巡回セレクタ１７２に設定する周期のサイクル数とを決定する。
【００５３】
次元１符号化器１７３ａ〜１７３ｅは、データバッファ１２に格納されているユーザデータの全ての情報ビットが分配部１７０を介して次元１符号化器１７３ａ〜１７３ｅに分配されると、それぞれ入力されたチャンクに対して符号化を実行することで次元１のパリティを生成する。例えば次元１符号化器１７３ａは、入力されたチャンク（ｄ００，ｄ０１）及び（ｄ１０，ｄ１１）に対して符号化を実行することでパリティｒ００及びパリティｒ０１を生成する。その後、次元１符号化器１７３ａ〜１７３ｅは、生成したパリティｒ００〜ｒ４１をセレクタ１７５へ出力する。
【００５４】
次元２符号化器１７４ａ及び１７４ｂも同様に、データバッファ１２に格納されているユーザデータの全ての情報ビットが分配部１７０を介して次元２符号化器１７４ａ及び１７４ｂに分配されると、それぞれ入力されたチャンクに対して符号化を実行することで次元２のパリティを生成する。例えば次元２符号化器１７４ａは、入力されたチャンク（ｄ００、ｄ０１）、（ｄ０４、ｄ０５）、（ｄ０８、ｄ０９）、（ｄ１２、ｄ１３）及び（ｄ１６及びｄ１７）を符号化することで次元２のパリティｃ００及びパリティｃ０１を生成する。その後、次元２符号化器１７４ａ及び１７４ｂは、生成したパリティｃ００〜ｃ１１をセレクタ１７６へ出力する。
【００５５】
セレクタ１７５及び１７６に入力された次元１のパリティｒ００〜ｒ４１及び次元２のパリティｃ００〜ｃ１１は、順次、メモリＩ／Ｆ１３を介して不揮発性メモリ２０に書き込まれる。これにより、不揮発性メモリ２０内には、図７に示す積符号３００が格納される。
【００５６】
図８は、次元１の成分符号の数が4で且つ次元２の成分符号の数が１の積符号の例を示す図である。図８に示す積符号４００は、ｄ００〜ｄ０７の合計８つの情報ビットと、ｒ００〜ｒ３１及びＣ００〜Ｃ０１の合計１０個のパリティとから構成されている。
【００５７】
このような積符号４００を生成する場合、符号化部１７における次元１の巡回セレクタ１７１の周期が４サイクルに設定され、次元２の巡回セレクタ１７２の周期が１サイクルに設定される。また、符号化部１７には１サイクルに４つの情報ビットが入力される。分配部１７０は、入力された４つの情報ビットを分割して２つのチャンクを生成し、生成した２つのチャンクを巡回セレクタ１７１及び１７２にそれぞれ入力する。次元１の巡回セレクタ１７１は、１サイクルごとに入力された２つのチャンクを順番に次元１符号化器１７３ａ〜１７３ｅに入力する。一方、次元２の巡回セレクタ１７２は、１サイクルごとに入力された２つのチャンクの両方を１サイクルで１列目の次元２符号化器１７４ａに入力し、２列目の次元２符号化器１７４ｂには入力しない。
【００５８】
このように、本実施形態に係る符号化部１７は、巡回セレクタ１７１及び／又は１７２の周期を変更することで、異なる符号化率で異なる符号構造の多次元の誤り訂正符号に対しても、その構成を変更せず且つスループットを落とさずに適用することが可能である。
【００５９】
図９は、次元１の成分符号の数が５で且つ次元２の成分符号の数が２の積符号の他の例を示す図である。図９に示す積符号５００は、ｄ００〜ｄ３９の合計４０個の情報ビットと、ｒ００〜ｒ４１及びＣ００〜Ｃ１１の合計１４個のパリティとから構成されている。また、積符号５００では、情報ビットの並びが、ユーザデータにおける情報ビットの並びと一致していない。
【００６０】
このような積符号５００を生成する場合も、図７に例示した積符号３００を生成する場合と同様に、符号化部１７における次元１の巡回セレクタ１７１の周期が５サイクルに設定され、次元２の巡回セレクタ１７２の周期が２サイクルに設定される。また、符号化部１７には、１サイクルに４つの情報ビットが入力される。分配部１７０は、１サイクルで入力された４つの情報ビットを、それぞれ２つの情報ビットよりなる２つのチャンクに分割し、これにより生成された２つのチャンクを巡回セレクタ１７１及び１７２それぞれに順次入力する。
【００６１】
ここで、次元１の巡回セレクタ１７１の周期（５サイクル）と次元２の巡回セレクタ１７２の周期（２サイクル）とを掛け合わせた値は１０である。したがって、分配部１７０においてｉ番目に生成されたチャンク及びｉ＋１０番目に生成されたチャンクは、次元１符号化器１７３ａ〜１７３ｅ及び次元２符号化器１７４ａ及び１７４ｂの組合せのうち、同じ組合せの次元１符号化器及び次元２符号化器に入力される。例えば、１番目のチャンク（ｄ００，ｄ０１）と１１番目のチャンク（ｄ２０，ｄ２１）とはともに、同じ組合せである次元１符号化器１７３ａ及び次元２符号化器１７４ａにそれぞれ入力される。
【００６２】
このように、本実施形態に係る符号化部１７は、複数のチャンクに対して次元１符号化器及び次元２符号化器の同じ組合せを割り当てることを許容している。言い換えれば、多次元の誤り訂正符号を構成する複数の成分符号における少なくとも２つの組合せには、保護対象であるユーザデータにおける少なくとも１つのシンボルを多重に保護する有効な組合せと、前記第１シンボル列におけるシンボルを多重には保護しない無効な組合せとが存在する。そこで分配部１７０は、ユーザデータから生成されるチャンクの数が多次元の誤り訂正符号を構成する複数の成分符号の有効な組合せの数よりも大きい場合には、有効な組合せの全通りに対して複数のチャンクのうちの一部のチャンクの入力先を割り当てた後、残りのチャンクに対しては既に入力先として割り当てられた組合せと重複する組合せを入力先として決定する。このように構成することで、次元１符号化器と次元２符号化器との組合せの数よりも大きな数のチャンクが生成される場合でも、その構成を変更せず且つスループットを落とさずに、異なる符号化率で異なる符号構造の多次元の誤り訂正符号を生成することが可能となる。
【００６３】
ただし、複数のチャンクに対して次元１符号化器及び次元２符号化器の同じ組合せを割り当てることを許容する場合でも、分配部１７０は、チャンクの数が次元１符号化器１７３ａ〜１７３ｅの数より大きければ、次元１符号化器１７３ａ〜１７３ｅそれぞれに入力されるチャンクの数が均等又はその差が予め設定しておいた所定の閾値（例えば１又は２）以下となるように、各チャンクの入力先となる次元１符号化器を決定する。同様に、分配部１７０は、チャンクの数が次元２符号化器１７４ａ及び１７４ｂの数より大きければ、次元１符号化器１７４ａ及び１７４ｂそれぞれに入力されるチャンクの数が均等又はその差が予め設定しておいた所定の閾値（例えば１又は２）以下となるように、各チャンクの入力先となる次元２符号化器を決定する。
【００６４】
以上のように、本実施形態では、長いシンボル長のユーザデータが比較的短いシンボル長の断片（チャンク）に断片化される。個々のチャンクは、１又は数個のシンボルで構成される。比較的小さなチャンクを複数の成分符号に分散し、且つ、適切に設計された巡回ルールに従うことにより、様々な符号構造の多次元の誤り訂正符号を、その構成を変更せず且つスループットを落とさずに符号化することが可能なメモリシステムを実現することができる。
【００６５】
また、例えば図７に例示した積符号３００や図９に例示した積符号５００のように、生成される多次元の誤り訂正符号における情報ビットの並びが元のユーザデータにおける情報ビットの並びとは異なる並びとなるように符号化が実行されるため、インターリーバなどのビット配列を組み換える機能を別途搭載することなく、バーストエラーに対しても高い訂正能力を発揮することが可能なメモリシステムを実現することが可能である。
【００６６】
（第２の実施形態）
つぎに、第２の実施形態に係るメモリシステムについて、図面を参照して詳細に説明する。本実施形態に係るメモリシステムの概略構成は、第１の実施形態において図５を用いて説明したメモリシステム１と同様であってよいため、ここでは重複する説明を省略する。ただし、第２の実施形態では、符号化／復号部１４における符号化部１７が、以下で説明する符号化部に置き換えられる。
【００６７】
図１０は、第２の実施形態に係る符号化部の概略構成例を示すブロック図である。なお、図１０では、説明の明確化のため、メモリコントローラ１０における他の構成が省略されている。
【００６８】
図１０に示すように、符号化部２７は、第１の実施形態において図６を用いて説明した符号化部１７と同様の構成において、分配部１７０がセレクタ２７１をさらに備える。また、都合上、３列目の次元２符号化器１７４ｃが追加されている。
【００６９】
セレクタ２７１には、分配部１７０が入力された情報ビットから生成したチャンクが入力されるとともに、次元１のセレクタ１７５から出力された次元１のパリティがチャンクとして入力される。また、セレクタ２７１の出力は、巡回セレクタ１７２に入力される。
【００７０】
セレクタ２７１は、データバッファ１２から情報ビットが入力されている期間は、分配部１７０で生成された情報ビットのチャンクを巡回セレクタ１７２に入力する。したがって、この期間の符号化部２７の動作は、第１の実施形態において例示した符号化部１７の動作と同様である。
【００７１】
一方、次元１のセレクタ１７５から次元１符号化器１７３ａ〜１７３ｅのいずれかで生成されたパリティが出力された場合、セレクタ２７１は、次元１のセレクタ１７５から入力されたパリティをチャンクとして次元２の巡回セレクタ１７２に入力する。
【００７２】
次元２の巡回セレクタ１７２は、セレクタ２７１から入力されたパリティのチャンクに対しても、情報ビットのチャンクと同様に振る舞う。したがって、巡回セレクタ１７２は、順次入力された複数のチャンクを、この順番通りに所定の周期に従って、次元２符号化器１７４ａ〜１７４ｃのいずれかに入力する。
【００７３】
次元２符号化器１７４ａ〜１７４ｃは、データバッファ１２に格納されているユーザデータの全ての情報ビット及び次元１符号化器１７３ａ〜１７３ｅで生成された全てのパリティが分配部１７０を介して次元２符号化器１７４ａ〜１７４ｃに分配されると、それぞれに入力された情報ビット及びパリティに対する符号化を実行して次元２のパリティを生成し、生成したパリティを次元２のセレクタ１７６へ出力する。その後の動作は、第１の実施形態と同様であるため、ここでは詳細な説明を省略する。
【００７４】
図１１は、図１０に示す符号化部２７により生成された積符号の一例を示す図である。図１１に示すように、積符号６００は、ｄ００〜ｄ１９の合計２０個の情報ビットと、ｒ００〜ｒ４１及びＣ００〜Ｃ２１の合計１６個のパリティとから構成されている。
【００７５】
このような積符号６００を生成する場合、符号化部２７における次元１の巡回セレクタ１７１の周期が５サイクルに設定され、次元２の巡回セレクタ１７２の周期が３サイクルに設定される。分配部１７０は、１サイクルで入力された４つの情報ビットを、それぞれ２つの情報ビットよりなる２つのチャンクに分割し、これにより生成された２つのチャンクを巡回セレクタ１７１及び１７２それぞれに順次入力する。
【００７６】
分配部１７０は、入力された情報ビットｄ００〜ｄ１９から生成した全てのチャンク（ｄ００、ｄ０１）、（ｄ０２、ｄ０３）、（ｄ０４、ｄ０５）、…、（ｄ１８、ｄ１９）を次元１符号化器１７３ａ〜１７３ｅ及び次元２符号化器１７４ａ〜１７４ｃに分配すると、つづいて、次元１のセレクタ１７５からセレクタ２７１に入力された次元１のパリティのチャンク（ｒ００、ｒ０１）、…、（ｒ４０、ｒ４１）を、順番に次元２の巡回セレクタ１７２に入力する。次元２の巡回セレクタ１７２は、入力された次元１のパリティのチャンクを、入力された順番且つ設定された周期に従って、次元２符号化器１７４ａ〜１７４ｃのいずれかに入力する。
【００７７】
図１０及び図１１に示す例では、次元１符号化器１７３ａで生成された１行目のパリティよりなるチャンク（ｒ００、ｒ０１）及び次元１符号化器１７３ｄで生成された４行目のパリティよりなるチャンク（ｒ３０、ｒ３１）が２列目の次元２符号化器１７４ｂに入力され、次元１符号化器１７３ｂで生成された２行目のパリティよりなるチャンク（ｒ１０、ｒ１１）及び次元１符号化器１７３ｅで生成された５行目のパリティよりなるチャンク（ｒ４０、ｒ４１）が３列目の次元２符号化器１７４ｃに入力され、次元１符号化器１７３ｃで生成された３行目のパリティよりなるチャンク（ｒ２０、ｒ２１）が１列目の次元２符号化器１７４ａに入力される。
【００７８】
次元２符号化器１７４ａ〜１７４ｃは、それぞれに入力された情報ビット及びパリティに対する符号化を実行して次元２のパリティＣ００〜Ｃ２１を生成し、生成したパリティＣ００〜Ｃ２１を次元２のセレクタ１７６へ出力する。
【００７９】
このように、本実施形態に係る符号化部２７は、一方の次元に対して生成されたパリティを他方の次元の符号化器に入力する構成を備えることで、一方の次元に対して生成されたパリティを保護の対象として、他方の次元のパリティを生成することが可能となる。その結果、より強力にユーザデータを保護することが可能となる。
【００８０】
その他の構成、動作及び効果は、上述した第１の実施形態と同様であるため、ここでは詳細な説明を省略する。
【００８１】
（第３の実施形態）
つぎに、第３の実施形態に係るメモリシステムについて、図面を参照して詳細に説明する。本実施形態では、上述した実施形態における復号部１８のより詳細な構成例について、図面を参照して詳細に説明する。なお、本実施形態に係るメモリシステムの概略構成は、第１の実施形態において図５を用いて説明したメモリシステム１と同様であってよいため、ここでは重複する説明を省略する。
【００８２】
図１２は、本実施形態に係る復号部１８の概略構成例を示すブロック図である。なお、図１２では、説明の明確化のため、メモリコントローラ１０における他の構成が省略されている。
【００８３】
図１２に示すように、復号部１８は、入力された情報ビットを分配する分配部１８０と、次元１の成分符号の数（５つ）と同数の次元１シンドローム計算器１８３ａ〜１８３ｅと、次元２の成分符号の数（２つ）と同数の次元２シンドローム計算器１８４ａ及び１８４ｂと、それぞれの次元に設けられたセレクタ１８５及び１８６と、シンドロームメモリ１８７と、シンドローム復号器１８８と、データメモリ１８９とを備える。また、分配部１８０は、符号化部１７／２７の分配部１７０と同様に、それぞれの次元に設けられた巡回セレクタ１８１及び１８２を備える。
【００８４】
不揮発性メモリ２０からメモリＩ／Ｆ１３によって読み出された受信語は、直接又は符号化／復号部１４内の内部メモリに一時バッファされた後、１サイクルに４ビットずつ、復号部１８に入力される。読み出された受信語には、読出し対象のユーザデータに対応する情報ビットｄｋと、次元１のパリティｒｉｊと、次元２のパリティｃｉｊとが含まれる。
【００８５】
復号部１８に入力された４ビットのデータは、データメモリ１８９に蓄積されるとともに、分配部１８０に入力される。分配部１８０は、４ビットのデータを１又は数ビット（本例では２ビット）ずつの複数（本例では２つ）のチャンクに分割し、これにより生成された複数のチャンクを各次元の巡回セレクタ１８１及び１８２にそれぞれ順次入力する。その際、分配部１８０は、情報ビットで構成されたチャンクを次元１の巡回セレクタ１８１と次元２の巡回セレクタ１８２との両方に入力し。次元１のパリティで構成されたチャンクを次元１の巡回セレクタ１８１に入力し、次元２のパリティで構成されたチャンクを次元２の巡回セレクタ１８２に入力する。
【００８６】
次元１の巡回セレクタ１８１は、順次入力された情報ビットのチャンク及び次元１のパリティのチャンクを、この順番通りで且つ設定された周期に従って、次元１シンドローム計算器１８３ａ〜１８３ｅのいずれかに入力する。例えば次元１の成分符号の数が５であり、５つの次元１シンドローム計算器１８３ａ〜１８３ｅを使用する場合、巡回セレクタ１８１の周期は５サイクルに設定される。それにより、１行目の成分符号が１行目の次元１シンドローム計算器１８３ａに入力され、２行目の成分符号が２行目の次元１シンドローム計算器１８３ｂに入力され、３行目の成分符号が３行目の次元１シンドローム計算器１８３ｃに入力され、４行目の成分符号が４行目の次元１シンドローム計算器１８３ｄに入力され、５行目の成分符号が５行目の次元１シンドローム計算器１８３ｅに入力される。なお、巡回セレクタ１８１及び１８２に対する周期の設定は、分配部１８０が行なってもよい。
【００８７】
それぞれ対応する成分符号が入力された次元１シンドローム計算器１８３ａ〜１８３ｅは、入力された成分符号のシンドロームをそれぞれ計算し、計算された各成分符号のシンドロームを次元１のセレクタ１８５へ出力する。次元１のセレクタ１８５は、入力された各成分符号のシンドロームをシンドロームメモリ１８７へ入力する。これにより、シンドロームメモリ１８７に次元１の各成分符号に関するシンドロームが記録される。
【００８８】
一方、次元２の巡回セレクタ１８２は、順次入力された情報ビットのチャンク及び次元２のパリティのチャンクを、この順番通りで且つ設定された周期に従って、次元２シンドローム計算器１８４ａ又は１８４ｂに入力する。例えば次元２の成分符号の数が２であり、２つの次元２シンドローム計算器１８４ａ及び１８４ｂを使用する場合、巡回セレクタ１８２の周期は２サイクルに設定される。それにより、１列目の成分符号が１列目の次元２シンドローム計算器１８４ａに入力され、２列目の成分符号が２列目の次元２シンドローム計算器１８４ｂに入力される。
【００８９】
それぞれ対応する成分符号が入力された次元２シンドローム計算器１８４ａ及び１８４ｂは、入力された成分符号のシンドロームをそれぞれ計算し、計算された各成分符号のシンドロームを次元２のセレクタ１８６へ出力する。次元２のセレクタ１８６は、入力された各成分符号のシンドロームをシンドロームメモリ１８７へ入力する。これにより、シンドロームメモリ１８７に次元２の各成分符号に関するシンドロームが記録される。
【００９０】
なお、巡回セレクタ１８１及び１８２には、第１又は第２の実施形態において例示した符号化部１７／２７における分配部１７０の巡回セレクタ１７１及び１７２に対して読出し対象のユーザデータを符号化する際に設定した周期と同じ周期が設定されればよい。
【００９１】
以上のようにして、不揮発性メモリ２０から受信語の全てのビットが読み出されて復号部１８に入力されることで、データメモリ１８９内に受信語全体が蓄積されるとともに、シンドロームメモリ１８７内に次元１及び次元２の全ての成分符号についてのシンドロームが格納されると、シンドローム復号器１８８は、データメモリ１８９内の受信語（符号語）における１つ以上のエラービットを見つけ出し、見つけ出されたデータメモリ１８９内のエラービットに対する誤り訂正を実行する。また、シンドローム復号器１８８は、誤り訂正したビットに対するシンドロームメモリ１８７内のシンドロームを、誤り訂正後のビットに基づいて修正する。
【００９２】
その後、シンドローム復号器１８８によってデータメモリ１８９内の符号語における全てのエラービットが訂正されると、データメモリ１８９内には、ホスト３０から書込み対象として送られてきたユーザデータが復元される。復元されたユーザデータは、例えばデータメモリ１８９から読み出されてデータバッファ１２に一旦格納された後、読出し要求下であるホスト３０へホストＩ／Ｆ１５を介して送信される。
【００９３】
以上のように、本実施形態に係る復号部１８によれば、第１及び第２の実施形態に係る符号化部１７及び２７で符号化された種々の多次元の誤り訂正符号（例えば図２、図４、図７〜図９、図１１参照）を復号することが可能である。すなわち、本実施形態によれば、異なる符号化率で異なる符号構造の多次元の誤り訂正符号を、その構成を変更せず且つスループットを落とさずに復号することが可能な復号部１８を実現することができる。また、本実施形態によれば、バーストエラーに対しても高い訂正能力を発揮することが可能なメモリシステムを実現することが可能である。
【００９４】
その他の構成、動作及び効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【００９５】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９６】
１…メモリシステム、１０…メモリコントローラ、１１…制御部、１２…データバッファ、１３…メモリＩ／Ｆ、１４…符号化／復号部、１５…ホストＩ／Ｆ、１６…内部バス、１７，２７…符号化部、１８…復号部、２０…不揮発性メモリ、３０…ホスト、１７０，１８０…分配部、１７１，１７２，１８１，１８２…巡回セレクタ、１７３ａ〜１７３ｅ…次元１符号化器、１７４ａ〜１７４ｃ…次元２符号化器、１７５，１７６，１８５，１８６，２７１…セレクタ、１８３ａ〜１８３ｅ…次元１シンドローム計算器、１８４ａ，１８４ｂ…次元２シンドローム計算器、１８７…シンドロームメモリ、１８８…シンドローム復号器、１８９…データメモリ。
【図１】
2019057096.tif 000003
【図２】
2019057096.tif 000004
【図３】
2019057096.tif 000005
【図４】
2019057096.tif 000006
【図５】
2019057096.tif 000007
【図６】
2019057096.tif 000008
【図７】
2019057096.tif 000009
【図８】
2019057096.tif 000010
【図９】
2019057096.tif 000011
【図１０】
2019057096.tif 000012
【図１１】
2019057096.tif 000013
【図１２】
2019057096.tif 000014