(57)【要約】【課題】ランダムエラー及び塊エラーに対応するＥＣＣシステムを搭載可能に構成されたメモリシステムを提供する。【解決手段】メモリシステムは、一括処理するバイナリデータＤをｈビットでδ桁のシンボルに分割し、これをｋ桁のｐ進数（ｐは３以上の素数）のデータ語に変換するｐ進数変換部と、このデータ語からｎ桁のｈビットで表示可能な桁の数をもつコード語からなる素数ｐの剰余体ＺｐよりなるコードＣを生成するエンコード部と、Ｃを書き込みデータとして記憶するメモリ部と、メモリ部から読み出された読み出しデータＹからシンドロームＳを生成し、Ｓを用いた演算により読み出しＹをエラー訂正してＣを再生するエラー訂正部と、再生されたＣを逆変換してｐ進数のデータ語を再生するデコード部と、再生されたデータ語を２進数に変換してＤを再生するバイナリ変換部とを備える。【選択図】図１
2011198253.tif 000002
【特許請求の範囲】
【請求項１】
一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の素数）のデータ語に変換するｐ進数変換部と、
前記ｐ進数変換部でｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなる素数ｐの剰余体ＺｐよりなるコードＣを生成するエンコード部と、
前記エンコード部で生成されたＺｐのコードＣを書き込みデータとして記憶するメモリ部と、
前記メモリ部から読み出された読み出しデータＹからシンドロームＳを生成し、生成されたシンドロームＳを用いた演算により前記読み出しデータＹをエラー訂正してＺｐのコードＣを再生するエラー訂正部と、
前記エラー訂正部で再生されたＺｐのコードＣを逆変換してｐ進数のデータ語を再生するデコード部と、
前記デコード部で再生されたデータ語を２進数に変換してバイナリデータＤを再生するバイナリ変換部と
を備えたことを特徴とするメモリシステム。
【請求項２】
一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の素数）のデータ語に変換し、
前記ｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなる素数ｐの剰余体ＺｐよりなるコードＣを生成し、
前記生成されたＺｐのコードＣを書き込みデータとしてメモリ部に記憶し、
前記メモリ部から読み出された読み出しデータＹからシンドロームＳを生成し、生成されたシンドロームＳを用いた演算により前記読み出しデータＹをエラー訂正してＺｐのコードＣを再生し、
前記再生されたＺｐのコードＣを逆変換してｐ進数のデータ語を再生し、
前記再生されたデータ語を２進数に変換してバイナリデータＤを再生する
ことを特徴とするメモリシステムのデータ書き込み・読み出し方法。
【請求項３】
一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の整数）のデータ語に変換するｐ進数変換部と、
前記ｐ進数変換部でｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなるコードＣを生成するエンコード部と、
複数のメモリセルを有し、少なくとも１又は複数のメモリセルでｐ段階の物理量レベルを設定可能で、前記物理量レベルによって前記エンコード部で生成されたコードＣを前記ｈビットのコード語の桁の数を書き込みデータとして記憶するメモリ部と、
前記メモリ部から読み出された読み出しデータＹから前記ｈビットのコード語の桁の数のエラー訂正を行うエラー訂正部と、
前記エラー訂正部でエラー訂正されたコードＣを逆変換してｐ進数のデータ語を再生するデコード部と、
前記デコード部で再生されたデータ語を２進数に変換してバイナリデータＤを再生するバイナリ変換部と
を備えたことを特徴とするメモリシステム。
【請求項４】
一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の整数）のデータ語に変換し、
前記ｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなるコードＣを生成し、
複数のメモリセルを有し、少なくとも１又は複数のメモリセルでｐ段階の物理量レベルを設定可能なメモリ部に対し、前記物理量レベルによって前記生成されたコードＣを前記ｈビットのコード語の桁の数を書き込みデータとして記憶し、
前記メモリ部から読み出された読み出しデータＹから前記ｈビットのコード語単位のエラー訂正を行い、
前記エラー訂正されたコードＣを逆変換してｐ進数のデータ語を再生し、
前記再生されたデータ語を２進数に変換してバイナリデータＤを再生する
ことを特徴とするメモリシステムのデータ書き込み・読み出し方法。
【請求項５】
前記メモリ部は、少なくとも２ｈ−２段階の物理量レベルに設定可能な複数のメモリセルを有し、
（１）２つのメモリセルの両方を最小近辺の物理量レベルに設定したときのデータを０に対応させ、
（２）２つのメモリセルの両方を最大近辺の物理量レベルに設定したときのデータを−（ｐ−１）／２又は（ｐ−１）／２に対応させ、
（３）２つのメモリセルのうちの一方のメモリセルを最小の物理量レベルに設定したときの他方のメモリセルの物理量レベルを−１〜−２ｈ−２＋１のデータに対応させ、
（４）２つのメモリセルのうちの前記他方のメモリセルを最小の物理量レベルに設定したときの前記一方のメモリセルの物理量レベルを１〜２ｈ−２−１のデータに対応させ、
（５）２つのメモリセルのうちの前記一方のメモリセルを最大の物理量レベルに設定したときの前記他方のメモリセルの物理量レベルを２ｈ−２〜（ｐ−１）／２−１のデータに対応させ、
（６）２つのメモリセルのうちの前記他方のメモリセルを最大の物理量レベルに設定したときの前記一方のメモリセルの物理量レベルを−２ｈ−２〜−（ｐ−１）／２＋１のデータに対応させる
ことを特徴とする請求項１又は３記載のメモリシステム。
【請求項６】
前記エラー訂正部は、
訂正可能なエラーのリー・メトリックの和の最大値をε＝γ−１として、前記シンドロームＳの成分Ｓ０、Ｓ１、…、Ｓγ−１について、予め定めた要素η＝ｕＳ０となるｕを求め、新たなシンドロームＳを
［数１］
2011198253.tif 000050
によって生成し、
前記演算に、多項式Ψ（ｘ）を
［数２］
2011198253.tif 000051
によって生成して用いる
ことを特徴とする請求項１、３及び５のいずれか１項記載のメモリシステム。
【請求項７】
２ｈ−１≦ｎ≦２（２ｈ−１−１）、訂正可能なエラーのリー・メトリックの和の最大値をεとした場合、δ＋ε＋２＋κ＝ｎ（κ＝０〜１０の整数）なる関係がある
ことを特徴とする請求項１、３、５及び６のいずれか１項記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリシステムに関し、特にＥＣＣシステムによりエラー検出訂正を行うメモリシステムに関する。
【背景技術】
【０００２】
メモリシステムの大容量化に伴い、メモリセルの微細化、１セル当たりの記憶ビット数の増加、メモリセルアレイの三次元構造化が進められている。しかし、メモリシステムでは、容量が大きいほど記憶データにエラーが生じ易くなる。そこで、オンチップＥＣＣ（Error Correcting Code）システムを備えたメモリシステムも多数提案されている（例えば、特許文献１）。このＥＣＣシステムで扱うのはランダムなビットエラーであった（以下、単に「ランダムエラー」と呼ぶ）。この場合、メモリセルへのデータ書き込み等において生じるランダムなビットエラーには対応することができる。しかし、高密度な三次元化されたメモリセルでは、このようなランダムなビットエラーのみならず、製造の際に生じる欠陥等に起因し、所定の領域で集中的にビットエラーが生じることがある（以下、「塊エラー」と呼ぶ）。このような塊エラーに対し、上記ＥＣＣシステムでは対応することができない。また、他のオンチップＥＣＣシステムもいくつか提案されてはいるが（特許文献２など）、これらオンチップＥＣＣシステムは、ランダムエラー及び塊エラー双方に十分に対応しているとは言い難い。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−１８１４３９号
【特許文献２】ＷＯ２００８−０９９７２３号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、ランダムエラー及び塊エラー双方に対応したエラー検出訂正を行うメモリシステム及びこのメモリシステムのデータ書き込み・読み出し方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一態様に係るメモリシステムは、一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の素数）のデータ語に変換するｐ進数変換部と、前記ｐ進数変換部でｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなる素数ｐの剰余体ＺｐよりなるコードＣを生成するエンコード部と、前記エンコード部で生成されたＺｐのコードＣを書き込みデータとして記憶するメモリ部と、前記メモリ部から読み出された読み出しデータＹからシンドロームＳを生成し、生成されたシンドロームＳを用いた演算により前記読み出しデータＹをエラー訂正してＺｐのコードＣを再生するエラー訂正部と、前記エラー訂正部で再生されたＺｐのコードＣを逆変換してｐ進数のデータ語を再生するデコード部と、前記デコード部で再生されたデータ語を２進数に変換してバイナリデータＤを再生するバイナリ変換部とを備えたことを特徴とする。
【０００６】
本発明の一態様に係るメモリシステムのデータ書き込み・読み出し方法は、一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の素数）のデータ語に変換し、前記ｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなる素数ｐの剰余体ＺｐよりなるコードＣを生成し、前記生成されたＺｐのコードＣを書き込みデータとしてメモリ部に記憶し、前記メモリ部から読み出された読み出しデータＹからシンドロームＳを生成し、生成されたシンドロームＳを用いた演算により前記読み出しデータＹをエラー訂正してＺｐのコードＣを再生し、前記再生されたＺｐのコードＣを逆変換してｐ進数のデータ語を再生し、前記再生されたデータ語を２進数に変換してバイナリデータＤを再生することを特徴とする。
【０００７】
本発明の他の一態様に係るメモリシステムは、一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の整数）のデータ語に変換するｐ進数変換部と、前記ｐ進数変換部でｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなるコードＣを生成するエンコード部と、複数のメモリセルを有し、少なくとも１又は複数のメモリセルでｐ段階の物理量レベルを設定可能で、前記物理量レベルによって前記エンコード部で生成されたコードＣを前記ｈビットのコード語の桁の数を書き込みデータとして記憶するメモリ部と、前記メモリ部から読み出された読み出しデータＹから前記ｈビットのコード語の桁の数のエラー訂正を行うエラー訂正部と、前記エラー訂正部でエラー訂正されたコードＣを逆変換してｐ進数のデータ語を再生するデコード部と、前記デコード部で再生されたデータ語を２進数に変換してバイナリデータＤを再生するバイナリ変換部とを備えたことを特徴とする。
【０００８】
本発明の他の一態様に係るメモリシステムのデータ書き込み・読み出し方法は、一括処理するバイナリデータＤをｈビット（ｈは整数）でδ桁（δは整数）のシンボルに分割し、これをｋ桁（ｋは整数）のｐ進数（ｐは３以上の整数）のデータ語に変換し、前記ｐ進数に変換されたデータ語からｎ桁（ｎ＝ｐ−１）のｈビットで表示可能な桁の数をもつコード語からなるコードＣを生成し、複数のメモリセルを有し、少なくとも１又は複数のメモリセルでｐ段階の物理量レベルを設定可能なメモリ部に対し、前記物理量レベルによって前記生成されたコードＣを前記ｈビットのコード語の桁の数を書き込みデータとして記憶し、前記メモリ部から読み出された読み出しデータＹから前記ｈビットのコード語の桁の数のエラー訂正を行い、前記エラー訂正されたコードＣを逆変換してｐ進数のデータ語を再生し、前記再生されたデータ語を２進数に変換してバイナリデータＤを再生することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ランダムエラー及び塊エラー双方に対応したエラー検出訂正を行うメモリシステム及びこのメモリシステムのデータ書き込み・読み出し方法を提供することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の第１の実施形態に係るメモリシステムのブロック図である。
【図２】本メモリシステムにおけるデータ書き込みのフローを示す図である。
【図３Ａ】本メモリシステムにおけるデータ読み出しのフローを示す図である。
【図３Ｂ】本メモリシステムにおけるデータ読み出しのフローを示す図である。
【図４Ａ】本メモリシステムにおけるデータからコードへの変換の概略を説明する図である。
【図４Ｂ】本メモリシステムにおけるデータからコードへの変換の概略を説明する図である。
【図５】本メモリシステムにおけるビットエラーとシンボルとの関係を示す図である。
【図６】本メモリシステムにおいて１つのシンボルを２つの多レベルセルで記録する場合のレベルとシンボル値との関係を示す図である。
【図７】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図８Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図８Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図９Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図９Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１０Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１０Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１１Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１１Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１２Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録する場合であって最大値を持つシンボルを記録する際のルールを示す図である。
【図１２Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録する場合であって最小値を持つシンボルを記録する際のルールを示す図である。
【図１３Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１３Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１４Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１４Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１５Ａ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１５Ｂ】本メモリシステムにおいて１つのシンボルを２つの多レベルのメモリセルで記録した場合に生じるエラーを示す図である。
【図１６】本メモリシステムにおけるメモリセルのレベル数と冗長度等との関係を示す図である。
【図１７】本発明の第２の実施形態に係るメモリシステムにおいて２シンボルのエラーを訂正可能にした場合の処理単位と冗長度等との関係を示す図である。
【図１８】本メモリシステムにおいて３シンボルのエラーを訂正可能にした場合の処理単位と冗長度等との関係を示す図である。
【図１９】本メモリシステムにおいて４シンボルのエラーを訂正可能にした場合の処理単位と冗長度等との関係を示す図である。
【図２０】本メモリシステムにおいて６シンボルのエラーを訂正可能にした場合の処理単位と冗長度等との関係を示す図である。
【図２１】本メモリシステムにおいて７シンボルのエラーを訂正可能にした場合の処理単位と冗長度等との関係を示す図である。
【図２２】本メモリシステムにおいて８シンボルのエラーを訂正可能にした場合の処理単位と冗長度等との関係を示す図である。
【図２３】本発明の実施形態に係るメモリシステムのＥＣＣシステムと他のＥＣＣシステムとのエラー訂正能力を比較する図である。
【発明を実施するための形態】
【００１１】
［第１の実施形態］
以下、本発明の第１の実施形態について説明する。
【００１２】
メモリシステムの大容量化のために、メモリセルの微細化、セルアレイの三次元構造化、メモリセルの多値記憶化を進めた場合、メモリシステムに生じる不良も様々である。
【００１３】
例えば、メモリセル等の構造に不具合があった場合、不良が、所定のメモリセルに限定して生じることは少なく、ある一定の範囲の複数のメモリセルにまとまって生じることが多い。一方、メモリセルの動作が不安定になった場合などは、不良が広い範囲に分布する。そのため、このようなメモリシステムには、塊エラー及びランダムエラーの双方を検出・訂正可能なＥＣＣシステムが必要となる。
【００１４】
その点、従来からあるリード・ソロモン（Reed-Solomon）符号（以下、「ＲＳ符号」と呼ぶ）によるＥＣＣシステム（以下、「ＲＳ−ＥＣＣシステム」と呼ぶ）では、塊エラーを検出・訂正することはできても、多様なランダムエラーを検出・訂正することは困難である。
【００１５】
また、ＲＳ−ＥＣＣシステムの他、２の累乗を基本とするガロア体であるＧＦ（２ｎ）を利用したＢＣＨ符号によるＥＣＣシステムも存在する（以下、「２ｎ−ＢＣＨ−ＥＣＣシステム」と呼ぶ）。ＢＣＨ−ＥＣＣシステムによれば、塊エラー及びランダムエラーの双方を検出・訂正することができる。しかし、ＥＣＣの処理のため、データのコード化に際して冗長なビットを付加するため、実際のデータよりも少なくとも１ビット分の余計な処理が必要となる。すなわち、２ｎビットのデータを扱うために、ＧＦ（２ｎ＋１）を用いるため、これは実際のデータ量の２倍のデータの演算を要することを意味する。特に、一括して扱うデータが大きくなる大容量のメモリシステムにおいては演算量が膨大となるため、回路規模が大きくなると共に処理時間も大きくなる。
【００１６】
そこで、本実施形態では、２ｎ−ＢＣＨ−ＥＣＣシステムに替わるＥＣＣシステムとして素数ｐを基本とするガロア体であるＧＦ（ｐ）、すなわち既約剰余類Ｚｐを利用したリー・メトリックコード（Lee Metric Code）によるＥＣＣシステムを提案する（以下、「ｐ−ＬＭ−ＥＣＣシステム」）。このｐ−ＬＭ−ＥＣＣシステムは、データをシンボル化してシンボルとしてのエラーの訂正を行うもので、その意味でＲＳ−ＥＣＣシステムに近い方式を採っている。以下では、具体例としてランダムな２つのシンボルエラーを訂正可能なｐ−ＬＭ−ＥＣＣシステムについて説明する。
【００１７】
ここで、改めてＧＦ（２ｎ）を利用した場合の問題点を挙げつつ本実施形態のｐ−ＬＭ−ＥＣＣシステムの構築の方向性について説明する。ここでは、一般的な処理を行う２ｎ−ＢＣＨ−ＥＣＣシステムと、オンチップ用に高速化な処理を実現するＧＦ（２ｎ）を利用したＲＳ符号によるＥＣＣシステム（以下、「２ｎ−ＲＳ−ＥＣＣシステム」と呼ぶ）の問題点を説明する。
【００１８】
これら２つのＥＣＣシステムは、エラーに対するシンドロームの生成処理については共通するものの、このシンドロームを如何に処理するかが相違している。
【００１９】
シンドロームの処理は、第１のステップである解探索多項式Λ（ｘ）の構築と、第２のステップであるΛ（ｘ）＝０の根の探索の２つのステップに分かれる。
【００２０】
２ｎ−ＢＣＨ−ＥＣＣシステムでは、第１のステップに際し、シンドロームから得られた量をもとにして、反復法を用いて「キー」と呼ばれる一連の条件式を満足するような解探索多項式Λ（ｘ）を求める。反復法としては、ユークリッド法やＢＭ（Berlekamp-Massey）法といった確立したアルゴリズムが用いられている。続く第２のステップでは、解探索多項式Λ（ｘ）に利用されるガロア体の各要素を逐次代入していき、Λ（ｘ）＝０を満足するガロア体の要素を求める。このアルゴリズムはチェーン・サーチ（Chain Search）法として確立したものである。このように、２ｎ−ＢＣＨ−ＥＣＣシステムの場合、第１のステップでは、解探索多項式Λ（ｘ）が得られるまでの反復に時間を要するが、膨大な時間を要するものではない。そのため、小規模回路を反復利用することで実現することができる。一方、第２のステップでは、小規模回路で実現できるものの、ガロア体の全要素をスキャンするため膨大な処理時間が必要となる。以上から、２ｎ−ＢＣＨ−ＥＣＣシステムによれば、一括処理するデータが大きい場合、第２のステップにおける処理時間がボトルネックとなり、リアルタイムのデータアクセスを実現することはできない。
【００２１】
２ｎ−ＲＳ−ＥＣＣシステムでは、第１のステップに際し、反復法を用いずに解探索多項式Λ（ｘ）の係数を直接求めている。そのため回路規模は大きくなるものの、解探索多項式Λ（ｘ）を得るための処理時間を短縮することができる。更に、第２のステップでは、予めΛ（ｘ）＝０を満足するガロア体の要素をデコーダとして求めておくことでマッチング・バイ・デコーダによって解を求めている。そのためガロア体の要素数に依らず高速に処理することができる。しかし、デコーダの回路規模はガロア体の要素数に比例して大きくなるため、回路規模は膨大になる。以上から、オンチップ用に高速な処理を実現する２ｎ−ＲＳ−ＥＣＣシステムは、回路規模が大きくなるため、処理速度を優先するような特定用途のメモリシステム以外では利用が困難である。
【００２２】
以上の問題点を考慮し、改良したものが今回提案するｐ−ＬＳ−ＥＣＣシステムである。このｐ−ＬＳ−ＥＣＣシステムは、塊エラー及びランダムエラーの双方に対する検知・訂正ができ、更に、オンチップＥＣＣシステムとして耐え得る回路規模且つ処理速度を実現するものである。
【００２３】
［メモリシステムの概要］
ここでは、本実施形態に係るメモリシステムの概要を説明する。
【００２４】
図１は、本メモリシステムのブロック図である。また、図２は、本メモリシステムにおけるデータ書き込みのフローを示す図であり、図３Ａ、図３Ｂは、本システムにおけるデータ読み出しを示す図である。
【００２５】
本メモリシステムは、大別してメモリ部１００とＥＣＣシステム２００とを備える。
【００２６】
メモリ部１００は、フラッシュメモリ、ＰＲＡＭ、ＲｅＲＡＭ等の大容量記憶メモリである。ＥＣＣシステム２００は、メモリ部１００へのデータ書き込み側に、ｐ進数変換部２０１及びエンコード部２０２を備え、メモリ部１００からのデータ読み出し側に、エラー訂正部（２０３〜２０６）、デコード部２０７及びバイナリ変換部２０８を備えている。エラー訂正部（２０３〜２０６）は、シンドローム生成部２０３、解探索多項式生成部２０４、ハッセ（Hasse）微分多項式生成部２０５及びコード復元部２０６からなる。なお、ＥＣＣシステム２００は、メモリ部１００と同一チップ上に搭載されていても、メモリ部１００とは別チップとして設けられていても良い。
【００２７】
このようなメモリシステムへのデータの書き込みは、次のように行われる。先ず、外部から入力されたデータＤをｐ進数変換部２０１でｈビット毎に区切って２ｈ進数表現（ｈは整数）へ変換し（図２のＳ１）、ｐ進数表現（ｐは３以上の素数）のデータ語Ｄ（ｈ）に変換する（図２のＳ２）。
【００２８】
続いて、エンコード部２０２で、このデータ語Ｄ（ｈ）に生成行列Ｇを作用させてリー・メトリックコードＣを生成する（図２のＳ３）。
【００２９】
最後に、メモリ部１００にリー・メトリックコードＣを記録保持する（図２のＳ４）。
【００３０】
データの読み出しは、次のように行われる。先ず、メモリ部１００からエラーを含むコードＹを読み出す（図３ＡのＳ５）。この読み出したコードＹにシンドローム生成部２０３でシンドローム行列Ｈを作用させてシンドロームＳを生成する（図３ＡのＳ６）。
【００３１】
続いて、解探索多項式生成部２０４で、このシンドロームＳから解探索多項式Ψ（ｘ）の係数を求め、解探索多項式Ψ（ｘ）を生成する（図３ＡのＳ７）。
【００３２】
続いて、求めた解探索多項式Ψ（ｘ）の係数が所定の条件を満たす場合（図３ＡのＳ８）、ハッセ微分多項式生成部２０５で、解を求めるためのハッセ微分多項式［Ψ（ｘ）］［ｉ］を生成し（図３ＡのＳ９）、これらの根ｒとその根の多重度ｎを算出する（図３ＢのＳ１０）。
【００３３】
続いて、コード復元部２０６で、この算出された根ｒとその根の多重度ｎを用いてコードＹに含まれるエラーの位置とエラー量を割り出してコードＣを復元する（図３ＢのＳ１１）。
【００３４】
続いて、デコード部２０７で、復元されたコードＣに対して生成行列Ｇの逆変換を行いｐ進数表現のデータ語Ｄ（ｈ）を再生する（図３ＢのＳ１２）。
【００３５】
最後に、バイナリ変換部２０８で、ｐ進数表現のデータ語Ｄ（ｈ）を２ｈ進数表現に変換した後、バイナリデータＤとして外部に出力する（図３ＢのＳ１３）。
【００３６】
以下において、以上の各処理を詳細に説明する。
【００３７】
［コードＣへの変換］
ここでは、外部から入力されたデータＤからメモリ部１００に記録するコードＣへの変換の原理を説明する。
【００３８】
先ず、データＤからコードＣへの変換方法の必要性について説明する。
【００３９】
ＧＦ（ｐ）を用いる場合、素数ｐは２の累乗で表せないため、ＧＦ（２ｎ）を用いる場合と異なり、データＤのビットパターンの全てをそのままコードＣとして用いることはできない。そこでデータＤのビットパターンとＧＦ（ｐ）の要素とを１対１で対応づける変換が必要となる。
【００４０】
ＧＦ（ｐ）の要素は０からｐ−１の整数であり、これら要素は全てｈビットのバイナリで表現できるものとする。この場合、ｈビットの全ビットパターンが使われないため、データＤのｈビットをそのままＧＦ（ｐ）の要素として扱うことはできない。
【００４１】
図４Ａに示すように、メモリシステムに与えられるひとまとまりのデータＤをｈビットずつに区切り（以下、データにおけるｈビット毎のまとまりを「データ語シンボル」と呼ぶ）、ｎ個の集まり、すなわち２ｈ進数表現でｎ桁のデータＤ＝（ｄ１，ｄ２，…，ｄｎ）として見ると、各桁には、ｈビットの全ビットパターンのうち、２ｈ−１以下の範囲のビットパターンが出現する。一方、図４Ｂに示すように、ｎ語長のＧＦ（ｐ）のコードＣ＝（ｃ１，ｃ２，…，ｃｎ）には、ｃｊ＜ｐ＜２ｈが成立するようなｈビットと素数ｐの関係があるため、ｈビットの全ビットパターンは出現しない。
【００４２】
そこで、データＤとコードＣとを１対１に対応づける変換が必要となるが、これは２ｈ進数表現からｐ進数表現への変換に相当する。
【００４３】
次に、ｐ進数表現への変換に用いる素数ｐの選択方法について説明する。
【００４４】
ＥＣＣシステムで一括処理するデータＤのビット数をＭ＝δｈとする。このＭビットのデータＤを、δ桁の２ｈ進数表現に変換する場合、数１に示すように１つのデータ語Ｄ（ｈ）として見ることができる。
【００４５】
［数１］
2011198253.tif 000003
【００４６】
ここで、ｄδ−１、ｄδ−２、…、ｄ１、ｄ０は、データ語シンボルが表す２ｈ進数表現の値（以下、シンボルが表わす値を「シンボル値」と呼ぶ）である。なお、最高桁δ−１のシンボル値ｄδ−１は非ゼロ値であることに注意する。
【００４７】
続いて、ｐ進数変換する際に次の条件を設定する。すなわち、データ語Ｄ（ｈ）で表現できる数の最大値と最小値を、ｈビットの２進数表現からｐ進数表現にした場合の桁数の増加を最大１桁とし、δ＋１桁とする。したがって、ｐ進数表現におけるデータ語Ｄ（ｈ）は数２に示すδ＋１桁のデータとなる。
【００４８】
［数２］
2011198253.tif 000004
【００４９】
ここで、ａδ、ａδ−１、…、ａ１、ａ０は、２進数表現のシンボル値である。なお、最高桁δと次の桁δ−１のシンボル値であるａδとａδ−１は同時にゼロ値になることはない。
【００５０】
続いて、データ語Ｄ（ｈ）の形式が普遍的に構成できるδとｈとの関係を求める。すなわち、最低でもδ桁の表現がｈの選択によって可能な条件を求める。ここで、データ語Ｄ（ｈ）の最小数Ｄｍｉｎ（ｈ）と最大数Ｄｍａｘ（ｈ）は数３のようになる。
【００５１】
［数３］
2011198253.tif 000005
【００５２】
したがって、Ｄｍｉｎ（ｈ）−１は、δ−１桁となるためデータ語Ｄ（ｈ）の形式でなくなってしまう。そこで、ｈ−１ビットのまとまり、すなわち２ｈ−１進数表現と比較するとＤｍｉｎ（ｈ）−１≧Ｄｍａｘ（ｈ−１）が成立すると、データ語Ｄ（ｈ）の表現でも桁数δが低下することはない。つまり、δとｈとの関係は数４のようになる。
【００５３】
［数４］
2011198253.tif 000006
【００５４】
続いて、ｐ進数表現にする際の桁数の増加が最大１桁となる条件を求める。ここで、最大値Ｄｍａｘ（ｈ）をｐδやｐδ＋１を法としてみると数５のようになる。
【００５５】
［数５］
2011198253.tif 000007
【００５６】
ここで、数５の各辺は整数で表すことができるので、（ｐ）δ＜（２ｈ）δ且つ（２ｈ）δ≦（ｐ）δ＋１が成立する。したがって、素数ｐは以下の数６のような範囲となる。
【００５７】
［数６］
2011198253.tif 000008
【００５８】
さらに、δ／（δ＋１）＝（１−１／δ）／（１＋（１／δ）２）＜１−１／δ＜１−１／ｈ（ｈ≦δ）とｐは素数であることから、素数ｐの選択条件の１つは数７のように表すことができる。また、このとき、δ桁のｐ進数の最小値ｐδ−１に対して、ｐδ−１＜（２ｈ）δ−１＝Ｄｍｉｎ（ｈ）となることから、ｐ進数はδ−１桁以下になることはない。
【００５９】
［数７］
2011198253.tif 000009
【００６０】
続いて、数７で得られた素数ｐの選択条件に、更に、リー・メトリックコードの成立条件を付加する。
【００６１】
データ語Ｄ（ｈ）のｐ進数表現においては、ＧＦ（ｐ）のリー・メトリックコードを用いると、コードＣの語長をｎ（すなわちＣ＝（ｃ１，ｃ２，…，ｃｎ））、このうちダミーの語長をκ、データの語長をｋとし、訂正可能なエラーのリー・メトリックの和の最大値をε＝γ−１とすると、δ＋１個のシンボル値に対して数８のような条件を持つコードＣを生成することができる。
【００６２】
［数８］
2011198253.tif 000010
【００６３】
ここで、ｄＬ（Ｃ）はコード語間の最小リー距離を示す。
【００６４】
続いて、ＥＣＣシステムが一括に処理するデータＤのビット数はＭなので、このデータＤを適当なｈビットずつのまとまりで考えてδ桁の数と見ると、δ＋１桁以下のｐ進数に変換することができる。すなわちδ＋１がリー・メトリックコードでのデータの語長に相当することになる。つまり、δ＋１≦ｋでなければリー・メトリックコードを作ることができない。このことから素数ｐの選択をδ＋１＋κ＝ｋとなるように語長κを定め、語長κのコード語には固定した値（例えば、０）を与えて処理するので、δ＋１＋κ＝ｋ、ｋ＝ｐ−ε−２から、素数ｐの選択条件の１つは数９のようになる。
【００６５】
［数９］
2011198253.tif 000011
【００６６】
以上をまとめると、ＥＣＣシステムに要求される訂正可能なエラーのリー・メトリックの和の最大値をε、一括処理するデータＤのデータ長をＭビットとした場合、δｈ≧Ｍ、δ＋ε＋３＋κ＝ｐ（０≦κ）から、素数ｐの選択条件は、数１０のようになる。
【００６７】
［数１０］
2011198253.tif 000012
【００６８】
さらに、選択すべき素数ｐは、数１０に示す条件を満たす素数ｐのうちダミーの語長κが最小になるもの、つまり、κ＝ｐ−δ−ε−３を最小にする素数ｐとなる。なお、δはＭ／ｈ以上の最小の整数である。
【００６９】
このとき、ＧＦ（ｐ）上のコードＣとしての冗長語長γは、γ＝ε＋１＝ｎ−ｋ＝ｎ−（κ＋δ＋１）から、データ語Ｄ（ｈ）の桁数から見た冗長語長（ｎ−δ）は、ｎ−δ＝κ＋１＋γとなる。したがって、データ語Ｄ（ｈ）から見た冗長ビット長は、数１１のようになる。
【００７０】
［数１１］
2011198253.tif 000013
【００７１】
つまり、数１０を満たす素数ｐのうち語長κが最小になる素数ｐを選択することで、冗長語長ｎ−δを最も減少させることができる。
【００７２】
次に、入力されたデータＤをリー・メトリックコードＣへ変換する方法について説明するが、その前に本実施形態で使用するリー・メトリックコードについて説明する。以下において、コードを構成する各桁を「コード語シンボル」と呼ぶものとする。
【００７３】
コード語シンボルｃは、数１２に示す整数となる。
【００７４】
［数１２］
2011198253.tif 000014
【００７５】
これら整数のリー・メトリックを｜ｃ｜とし、全てのリー・メトリック｜ｃ｜をｐ／２以下の整数で表すとリー・メトリック｜ｃ｜の定義は数１３のようになる。
【００７６】
［数１３］
2011198253.tif 000015
【００７７】
コードＣは、ｎ＝ｐ−１個のコード語シンボルｃの並びと考えられるため、図４Ｂにも示したようにＣ＝（ｃ１，ｃ２，…，ｃｎ）で表すことができ、コードＣの計量ｗ（Ｃ）は数１４のように各コード語シンボルｃのリー・メトリック｜ｃ｜の和として定義される。
【００７８】
［数１４］
2011198253.tif 000016
【００７９】
また、コード間の距離はコードに対応する各コード語シンボルの差のリー・メトリックの和で定義される。ここで２つのコードＣとＹの差（リー距離）ｄＬ（Ｃ，Ｙ）は数１５のようになる。
【００８０】
［数１５］
2011198253.tif 000017
【００８１】
さらに、コードＣの最小リー距離は、数１６に示すようにコードＣの計量ｗ（Ｃ）の最小の計量で定義される。
【００８２】
［数１６］
2011198253.tif 000018
【００８３】
このとき、リー・メトリックコードは、数１７に示す生成行列Ｇ及びシンドローム行列Ｈを持ったコード間の最小距離が２γであり、且つ、γ−１以下のリー・メトリックのエラー訂正が可能なコードである。
【００８４】
［数１７］
2011198253.tif 000019
【００８５】
ここで、コードＣのシンボル数をｎ、データ語Ｄのシンボル数をｋとすると、γ＝ｎ−ｋであり、γはコードＣに含まれる冗長なシンボル数を表している。
【００８６】
次に、メモリシステムに入力されたデータＤを上記リー・メトリックコードＣにエンコードする方法について説明する。
【００８７】
先ず、ＥＣＣシステムが一括処理するＭ＝δｈビットのバイナリであるデータＤをδ＋１桁のｐ進数表現に変換する。その際、予め設定したγに対してκ桁だけ不足している場合、κ桁は例えば０に固定しておく。このように得られたｋ桁の数は、ＧＦ（ｐ）の要素ｘとなる。
【００８８】
続いて、データ語Ｘ（Ｘ＝（ｘ１，ｘ２，…，ｘｋ））として、演算Ｃ＝ＸＧを実行し、コードＣを得る。
【００８９】
最後は、この得られたコードＣを構成するコード語シンボルｃｉを数１８に示すｈビットのバイナリ表現のデータとしてメモリセルに記憶する。
【００９０】
［数１８］
2011198253.tif 000020
【００９１】
［コードＹのエラー訂正］
ここでは、エラーを含むコードＹのエラー訂正の原理について説明する。
【００９２】
先ず、本メモリシステムにおけるコードＹのエラー訂正を説明する前に、比較例となるエラー訂正について説明する。
【００９３】
メモリセルに記録されたコードＣのバイナリデータは、ｈビットからなるコード語シンボルがｎ個集まったものであり、ビット毎に様々な擾乱を受けて変化を起こす。そのため、本来記憶されるべきコード語シンボルｃから意図しない異なるコード語シンボルｙに変化してしまう。このコード語シンボルｙからなるコードＹからコードＣを復元するのがエラー訂正である。
【００９４】
エラー訂正の前には、シンドロームＳを求める必要がある。
【００９５】
変化後のコード語シンボルｙからなるコードＹは、数１９のように表すことができる。
【００９６】
［数１９］
2011198253.tif 000021
【００９７】
ここで、ｅｉは、各コード語シンボルｃｉのエラー量を表す。
【００９８】
シンドロームＳはシンドローム行列Ｈを利用したＳ＝ＹＨｔの演算をして数２０に示す要素Ｓ０、Ｓ１、…、Ｓγ−１として求まる。
【００９９】
［数２０］
2011198253.tif 000022
【０１００】
ここで、ＨｔはＨの転置行列である。生成行列Ｇとシンドローム行列Ｈの構成がＧＨｔ＝０（ｍｏｄ  ｐ）となるように構成されていることにより、Ｙ＝Ｃ＋ＥとおくとＳ＝ＥＨｔとなる。またＥ＝（ｅ１，ｅ２，…，ｅｎ）とすると、シンドロームＳ０は各コード語シンボルのエラーの総和になっていることが分かる。これらのシンドロームＳが唯一のエラーの情報であり、これらシンドロームＳを基にして以下のように、正しいコードＣの復元を行う。
【０１０１】
次に、デコードの原理をエラーの状況が予め分かっているものとして説明する。ｎ（＝ｐ−１）個のエラーコード語シンボルを二つの組Ｊ＋とＪ−に、数２１のように分類する。
【０１０２】
［数２１］
2011198253.tif 000023
【０１０３】
すなわち、エラーコード語シンボルのエラー量がｅｊ＜ｐ／２の場合、コード語シンボルｃｊの位置ｊの集まりであるＪ＋と、エラーコード語シンボルのエラー量がｅｊ＞ｐ／２の場合のコード語シンボルｃｊの位置ｊの集まりであるＪ−とに分類される。ＧＦ（ｐ）上の多項式Λ（ｘ）、Ｖ（ｘ）をこれらの組を基に数２２のように構成する。
【０１０４】
［数２２］
2011198253.tif 000024
【０１０５】
このように、多項式Λ（ｘ）はＪ＋のエラーコード語シンボルの位置ｊの逆数を根として持ち、そのコード語シンボルのリー・メトリックｅｊを根の多重度として持つ多項式となる。一方、多項式Ｖ（ｘ）はＪ−のエラーコード語シンボルの位置ｊの逆数を根として持ち、そのコード語シンボルのリー・メトリックｐ−ｅｊを根の多重度として持つ多項式となる。デコードは、最終的にこれらの多項式をシンドロームＳｌの情報のみから構成して解くことによってエラーの情報を得る過程となる。つまり、これら多項式Λ（ｘ）、Ｖ（ｘ）とシンドロームＳｌとの関係を求める必要がある。
【０１０６】
続いて、数２３に示すように各シンドロームＳｌをその次数の係数に持つ級数多項式で構成すると、コード語シンボルのエラー量ｅｊ、位置ｊとその値を持つ有理多項式で表される。
【０１０７】
［数２３］
2011198253.tif 000025
【０１０８】
数２３から、多項式Λ（ｘ）、Ｖ（ｘ）、シンドロームＳ（ｘ）の間には数２４に示す関係式が成立する。
【０１０９】
［数２４］
2011198253.tif 000026
【０１１０】
続いて、数２４に示す関係式を利用して、シンドロームＳ（ｘ）から多項式Λ（ｘ）、Ｖ（ｘ）を求める。
【０１１１】
シンドロームＳ（ｘ）から、数２５に示す次数がγ−１以下の多項式Ψ（ｘ）を求める。
【０１１２】
［数２５］
2011198253.tif 000027
【０１１３】
多項式Ψ（ｘ）の展開式において、数２５に示す式の両辺の同次次数の係数の比較から、係数ψｊは、シンドロームＳｉと既に求まっている係数ψｊ−１とを用いて反復法で求めることができる。シンドロームＳ１〜Ｓγ−１から多項式Ψ（ｘ）の係数ψ０〜ψγ−１を求めた結果を数２６に示す。
【０１１４】
［数２６］
2011198253.tif 000028
【０１１５】
この多項式Ψ（ｘ）はΛ（ｘ）／Ｖ（ｘ）に等価な多項式であるが、多項式Λ（ｘ）、Ｖ（ｘ）には、数２７に示すキー条件がある。そのため、ｘγと多項式Ψ（ｘ）に対してユークリッドの反復法で定数倍を除いて求めることができる。
【０１１６】
［数２７］
2011198253.tif 000029
【０１１７】
したがって、シンドロームＳ１〜Ｓγ−１から多項式Ψ（ｘ）が構成できれば、反復法の停止条件としてシンドロームＳ０を用いて多項式Λ（ｘ）、Ｖ（ｘ）が求まる。すなわち、反復法によって（Ｓ０，Ψ（ｘ））の組から求めた多項式Λ（ｘ）、Ｖ（ｘ）は、エラーコード語シンボルの位置ｊとエラー量ｅｊを表している。
【０１１８】
続いて、ユークリッドの反復法について説明する。ここでは、合同式Ｖ（ｘ）Ψ（ｘ）≡Λ（ｘ）（ｍｏｄ  ｘγ）を停止条件ｄｅｇ  Λ（ｘ）−ｄｅｇ  Ｖ（ｘ）≡Ｓ０（ｍｏｄ  ｐ）で求める反復法について説明する。
【０１１９】
ユークリッドの反復法は、関数ｆ０、ｆ１、…、ｆｎを多項式の割り算を用いて順に求めて行く方法である。これらの量の間には数２８に示す関係がある。
【０１２０】
［数２８］
2011198253.tif 000030
【０１２１】
ここで、数２９の示すように、特に割り算の過程で得られる商多項式ｋｎからｐｎやｑｎを逐次導入することによって、これらの多項式が簡単な関係を満足することから、ｆｎをｆ０、ｆ１、ｐｎ−１、及びｑｎ−１で表すことができる。そこでｆ０＝ｘγ、ｆ１＝Ψ（ｘ）とおいてｘγでの合同式を作ると、反復の停止条件はｄｅｇ  ｆｎ−ｄｅｇ  ｐｎ−１≡Ｓ０（ｍｏｄ  ｐ）となる。この停止条件を満たすｎについてｄｅｇ  ｆｎ＋ｄｅｇ  ｐｎ−１＜γならλ（ｘ）＝ｆｎ、Ｖ（ｘ）＝ｐｎ−１とおくことができる。
【０１２２】
続いて、Λ（ｘ）＝０、Ｖ（ｘ）＝０となる解探索を行う。
【０１２３】
数２２に示す多項式Λ（ｘ）、Ｖ（ｘ）は、ｆ（ｘ）＝Λ（ｘ）（又はＶ（ｘ））とすると、数２９に示す多項式となっている。
【０１２４】
［数２９］
2011198253.tif 000031
【０１２５】
解探索には、このｆ（ｘ）のｘにＺｐの要素１、…、ｐ−１を順次代入していき、素数ｐを法としてｆ（ｘ）＝０となるｘをｒとする。つまり、ｆ（ｒ）＝０（ｍｏｄ  ｐ）となる根ｒを求める。根ｒが求まると、この根ｒのＧＦ（ｐ）での逆元、つまりｒ−１がエラーコード語シンボルの位置ｊとなり（ｊ＝ｒ−１）、根ｒの多重度ｅがエラーコード語シンボルのリー・メトリックｅｊとなる。
【０１２６】
ここで、根ｒの多重度の探索について説明する。根ｒの多重度ｅの探索には、先ず、多項式Λ（ｘ）、Ｖ（ｘ）の係数と二項係数から数３０に示すハッセ微分多項式を求める。
【０１２７】
［数３０］
2011198253.tif 000032
【０１２８】
続いて、この数３０に示すハッセ微分多項式に根を代入していき、最初にゼロにならない微分の階数をｅとする。この階数ｅが根ｒの多重度である。
【０１２９】
［数３１］
2011198253.tif 000033
【０１３０】
次に、本発明の実施形態におけるコードＹのエラー訂正について説明する。
【０１３１】
これまでに説明した従来の解探索多項式の構成法では、ユークリッドの反復法を用いていたため、多項式の除算が必要となり、計算過程は煩雑になる。さらに、求めた多項式から得られるエラー量は多項式の次数によって制限されたものに限られるため、シンドロームから反復法によって得た多項式に対してエラー量が固定されていた。そこで本実施形態では、解探索多項式の構成方法を簡略化した上で、さらにエラー探索の自由度を向上させた方法を利用する。
【０１３２】
従来の方法では、シンドロームＳ０の値が解を求める際の停止条件であった。そのため、エラーの状況によってはシンドロームＳ０が停止条件を満たさず、解を得られない場合が発生する。本実施形態ではこのようなこのようなエラー状況でも解を得られるように、各コード語シンボルに生じたエラーを一括して変換する。有限体の固定した要素に対して全ての要素との積を作ると有限体の全ての要素が改めて得られことを利用して、予め定めた要素ηに対してｕＳ０≡ηなるｕを求める。メモリに記憶されたエラーを含むコードＹにこのｕを掛けてシンドロームを求めると、数３２に示すようにｕＳ０、ｕＳ１、…、ｕＳγ−１を得る。
【０１３３】
［数３２］
2011198253.tif 000034
【０１３４】
ここで、変換されたエラーの総和がηになっていることに注意する。本実施形態におけるデコードの原理は、エラーのコードＥに替えてｕＥを扱うことが従来の方法におけるデコードの原理との差異点となる。この差異点によって、従来の方法における多項式Λ（ｘ）、Ｖ（ｘ）の求め方を以下のように簡略化することができる。
【０１３５】
以下において、この本実施形態におけるエラー訂正方法を「シンドローム変換法」と呼ぶことにする。
【０１３６】
先ず、シンドロームＳ（ｘ）から多項式Λ（ｘ）、Ｖ（ｘ）を導出する方法について説明する。
【０１３７】
シンドロームＳ（ｘ）から多項式Ψ（ｘ）を構成する点については、シンドローム変換法においても従来の方法と同様である。但し、使用するシンドロームがｕＳとなっている点が異なる。つまり、シンドローム変換法で次数γ−１以下の多項式Ψ（ｘ）を求めると数３３のようになる。
【０１３８】
［数３３］
2011198253.tif 000035
【０１３９】
したがって、多項式Ψ（ｘ）の係数ψ０〜ψγ−１を求めた結果は数３４のようになる。
【０１４０】
［数３４］
2011198253.tif 000036
【０１４１】
解探索多項式のキー条件を数３５に示す。なお、これらキー条件を満足する多項式λ（ｘ）、ｖ（ｘ）は、定数を除いて、それぞれ解探索多項式Λ（ｘ）、Ｖ（ｘ）に一致する。
【０１４２】
［数３５］
2011198253.tif 000037
【０１４３】
数３５に示す通り、シンドローム変換法における解探索多項式のキー条件は、次数に関するシンドロームＳ０で規定された条件が、予め決めたηで規定されている点において従来の方法と異なる。このように条件を予め決めたηにすることによって、多項式の次数に関する条件ｄｅｇ  λ（ｘ）−ｄｅｇ  ｖ（ｘ）＝η、ｄｅｇ  λ（ｘ）+ｄｅｇ  ｖ（ｘ）≦γ−１から０≦２ｄｅｇ  ｖ（ｘ）≦γ−１−ηであるため、γ‐１‐η≦１ならｄｅｇｖ（ｘ）＝０になることが分かる。すなわちγ−１≧η≧γ−２の範囲でηを設定することによって、ユークリッドの反復法を用いることなく解探索多項式を導出し得る。実際に、条件ｄｅｇ  Ψ（ｘ）＝ηの場合、多項式Ψ（ｘ）は全てのキー条件を満たす唯一の解探索多項式になる。この方法は、全てのエラーコード語シンボルに対し、その位置ｊを集合Ｊ＋に集める変換を施すことに相当する。換言すれば、エラーの総和Ｓ０が素数ｐの倍数以外の場合、そのエラーの総和Ｓ０をγ−１又はγ−２になるように変換させることで、エラー修正ができる可能性があることを示す。但し、あくまで可能性であり、エラー修正には、全てのエラーがＪ＋に集められ、且つ、シンドロームｕＳから求めた多項式Ψ（ｘ）の次数がηに等しいことが条件となる。
【０１４４】
シンドローム変換法によれば、後述するように、１シンボルのエラーについては、どのようなエラーにも対応することができる。また、２シンボルのエラーについても、シンドロームＳを循環的に用いることで、どのようなエラーにも対応することができる。
【０１４５】
次に、解探索では、Λ（ｘ）＝Ψ（ｘ）、Ｖ（ｘ）＝１とおいて、従来の方法と同様、Ｚｐの要素から解を見つける。但し、シンドローム変換法では、得られた根の多重度は、ｕとの積となっているため、エラーを得る際には、多重度にｕ−１を掛ける必要がある。
【０１４６】
シンドローム変換法では、γに基づいてηを設定する。そのため、η＝γ−１とη=γ−２の場合があるが、以下の説明では、η＝γ−１のみを考える。
【０１４７】
次に、エラーの計量を変換して解探索多項式を求める方法について、シンドローム変換法を用いた場合、根の数（エラーが生じたコード語シンボルの数）に対してどの様なエラーが探索できるかを検討する。
【０１４８】
第１のケースとして、解探索多項式から得られる根が１根の場合について説明する。
【０１４９】
根をｊ−１とすると、エラーが発生したコード語シンボルの位置はｊであり、実際のエラー量はｅｊとなる。この場合、根の多重度は、適当なｕを乗じて変換すれば、エラー量ｅｊに拠らず、必ずｕｅｊ＝ηとなる。したがって、１シンボルのエラーを完全に解として得ることができる。
【０１５０】
第２のケースとして、解探索多項式から得られる根が２根の場合について説明する。
【０１５１】
根をｉ−１とｊ−１とするとエラーコード語シンボルの位置はｉとｊであり、それらの実際のエラー量はｅｉとｅｊである（Ｅ＝（０，…，ｅｉ，…，ｅｊ，…，０）、ｎ＝ｐ−１）。この場合、適当なｕを掛けて変換しこれらが各々ｐ／２以下でＪ＋にまとまれば、数３６に示す多項式Ψ(x)が構成できるため、多項式Ψ（ｘ）からエラー量を求めることができる。
【０１５２】
［数３６］
2011198253.tif 000038
【０１５３】
ここで、適当なｕを掛けてエラー量を変換し、これらがＪ＋にまとまるにはエラー量ｅｉとｅｊが一定の関係を持つ必要がある。それには、両者が等しければ十分であり、これによってｕによる変換でいかなるエラー量もη（η＝γ−１）にすることができるどの様なエラー量もηにすることができる。したがって、２シンボルのエラーを完全に解として得ることができる。
【０１５４】
次に、２シンボルのエラー量を等しくする変換方法について詳述する。
【０１５５】
エラーが生じた２つのコード語シンボルのコードＹにおける位置をｉ、ｊとし、それぞれにエラー量をｅｉ、ｅｊとする。この場合、シンドロームＳ０は、Ｓ０＝ｅｉ＋ｅｊとなる。一般的には、シンドロームＳｍは、Ｓｍ＝ｉｍｅｉ＋ｊｍｅｊとなる。つまり、適当なｍを選択することで、ｉｍｅｉ≡ｊｍｅｊとすることができる。
【０１５６】
ここで、ＧＦ（ｐ）の原始根と指数表示を用いてｅｉ＝α（ｅｉ）、ｅｊ＝α（ｅｊ）、ｉ＝α（ｉ）、ｊ＝α（ｊ）とすると、ｍ（ｉ）＋（ｅｉ）≡ｍ（ｊ）＋（ｅｊ）が成立する。したがって、ｍは、ｍ≡−｛（ｅｊ）−（ｅｉ）｝／｛（ｊ）−（ｉ）｝によって求めることができる。
【０１５７】
以上から、シンドロームの系列（Ｓｍ，Ｓｍ＋１，…，Ｓｍ＋γ）を用いて、ｕＳｍ＝ηとなる係数ｕを求めれば良い。
【０１５８】
しかし、ｍは当初不明であるため、２つのコード語シンボルの様々なエラーに対応するには、次のような変換方法を用いる。最初に、ｍを０からｐ−２までスキャンし、各ｍに対する係数ｕをｕ＝ηＳｍ−1によって算出する。これによって、（ｕＳｍ，ｕＳｍ＋１，…，ｕＳｍ＋η）を求めることができる。次に、これら（ｕＳｍ，ｕＳｍ＋１，…，ｕＳｍ＋η）から多項式Ψ（ｘ）を構成する。最後に、構成された多項式Ψ（ｘ）のうち、ｄｅｇ  Ψ（ｘ）＝ηを満たすｍを抽出する。以上によって抽出されたｍを選択することによって、２つのコード語シンボルの変換後のエラー量ｕｅｉ、ｕｅｊを等しくすることが可能である。
【０１５９】
第３のケースとして、解探索多項式から得られる根が３根以上の場合について説明する。
【０１６０】
多項式Ψ（ｘ）から得られる根が３根以上の場合、解を得るには、全ての根のエラー量を変換してＪ＋に属するようにする事が条件であり、この条件を具備することで、多項式Ψ（ｘ）がη次の多項式として構成される。しかし、根が３つ以上の場合、様々なエラーに対応するための単純な変換方法を構成することは困難である。
【０１６１】
そこで、根が３根以上の場合には、全ての根のエラー量が変換後にＪ＋にまとまる場合を増やす変換方法を用いる。この変換方法は、各ｍについて、η＝γ−１とη＝γ−２に対して、２根以下の場合と同様の変換方法を適用するものである。すなわち、ｍを０からｐ−２まで順次増加させながら、Ｓｍ≠０の場合に以下を行う。最初にη＝γ−１で、次にη＝γ−２で、係数ｑを係数ｑ≡ηＳｍ−１によって算出する。これによって、各ηに対して、（ｑＳｍ，ｑＳｍ＋１，…，ｑＳｍ＋γ−１）を求めることができる。次に、これら（ｑＳｍ，ｑＳｍ＋１，…，ｑＳｍ＋γ−１）から多項式Ψ（ｘ）を構成する。このように構成された多項式Ψ（ｘ）のうち、ｄｅｇ  Ψ（ｘ）＝ηを満たす多項式Ψ（ｘ）がある場合、多項式Λ（ｘ）から解が得られる。一方、全ての多項式Ψ（ｘ）がｄｅｇ  Ψ（ｘ）≠ηである場合、解けないエラー分布であるため、解無しとして終了となる。
【０１６２】
この解法の中には２根や１根の解法も含まれており、根が２つ以下の場合には全てのエラーを求めることができる。一方、３つ以上の場合、エラー量の分布が狭い等の特殊な条件の下、エラーを求めることができる。具体的には、全てのエラーのエラー量が等しいか、又は１つのエラーを除くその他のエラー量が等しい場合、全てのコード語シンボルのエラーを求めることができる。特に、全てのエラーコード語シンボルのエラー量が等しい場合には、最大ηシンボルのエラーを求めることが可能である。
【０１６３】
なお、η＝γ−１とη＝γ−２を用いることで、３つ以上のエラーコード語シンボルのエラー分布をＪ＋にまとめられるケースが増えることは確かだが、どのようなエラー分布の場合に解として得ることができるかは明確ではない。ただ、コード語間の最小リー・メトリックは２γであるので、エラーがγ−１以下なら、解からエラーの訂正は可能である。
【０１６４】
［メモリシステムへの応用］
ここでは、以上説明したコードＣへの変換及びコードＹのエラー訂正の原理を実際のメモリシステムに応用する場合について説明する。
【０１６５】
ここでは、ｐ−ＬＭ−ＥＣＣシステムの具体的なメモリシステムへの応用例について説明する。
【０１６６】
先ず、訂正可能な場合におけるエラーシンボル数とエラー量との関係について説明する。ここでは、メモリセルがビット単位で情報を記憶する場合の塊エラーとビットエラーとの関係について説明する。
【０１６７】
コードＣは、メモリセル内では、バイナリとして記憶されるため、エラービットの位置によってはコードのエラーＥが異なってくる。リー・メトリックコードが扱うのは塊エラーであるため、ビットエラーとして対応できるものは制限される。具体的には、データ語シンボルをｈビットのバイナリで表すため、２０の位置の１ビットエラーは、±１のエラー量となり（Ｚｐでは、１又はｐ−１）、２ｈ−１の位置の１ビットエラーは、±２ｈ−１（ｍｏｄ  ｐ）のエラー量となる。したがって、全てのビットエラーのパターンに対応するには、コード語シンボルの全てのエラー量に対応する必要がある。
【０１６８】
上述のように、本実施形態の解探索方法を用いると、エラーコード語シンボルが２つまでの場合、如何なるエラー量であってもエラーの解を求めることができる。つまり、ビットエラーが塊で生じている場合でも、この塊が２つ以下の場合には確実に対応することができる。
【０１６９】
コードＣは、コード語シンボルｃを、図５に示すように、バイナリに変換してやることで、様々に構成されたメモリシステムでも記憶することができる。但し、本実施形態の場合、エラー訂正方法の特徴を考慮すると、物理量レベル（以下、単に「レベル」と呼ぶ）によって多値を記憶するメモリセルを用いて構成されたメモリシステムが望ましい。この場合、メモリセルのレベルの順位と、シンボル値の大きさとを対応させたデータ記憶が可能であり、エラーによるリー・メトリックの変動を小さくすることができる。これは、エラーの多くは、正しいレベルから、このレベルの近傍に移動することで生じるためである。
【０１７０】
次に、多値記憶メモリセルを用いたメモリシステムについて、メモリセルのレベルに対するシンボル値の割り付け方について説明する。
【０１７１】
フラッシュメモリ、ＰＲＡＭ、ＲｅＲＡＭ等のメモリセルは、物理量レベルをデータの量と対応させることで多値を記憶することができる。この場合、通常、レベルはそれほど大きくは変動しないため、エラーが生じた場合であっても、数レベル程度の小さいエラーになる。
【０１７２】
本実施形態のようにＧＦ（ｐ）を利用する場合は、シンボル値をレベルの大きさに対応させると都合が良い。但し、２メモリセルで多レベルを構成し、Ｚｐの代表元ｑの採り方を−２／ｐ＜ｑ＜ｐ／２として考える。素数ｐを大きくすることで、冗長シンボルのコード全体に対する割合を減らせるので、できるだけレベル数を増やして素数ｐの値を大きく採れるようにするためである。
【０１７３】
以下において、２つのメモリセルＭＣ１、ＭＣ２のレベルに対するシンボル値−（ｐ−１）／〜（ｐ−１）／２の割り付け方の一例について説明する。ここでは、メモリセルＭＣ１、ＭＣ２はそれぞれ２ｈ−２のレベル数を持つものとする。
【０１７４】
先ず、シンボル値０の割り付けた方について説明する。
【０１７５】
シンボル値０の割り付けに関し、以下の２つのルールを定める。
【０１７６】
（ルール１）  メモリセルＭＣ１、ＭＣ２のレベルが共に最下位レベルにある場合、シンボル値は０である。
【０１７７】
（ルール２）  メモリセルＭＣ１、ＭＣ２のレベルが共に２番目に低いレベルにある場合、シンボル値は０である。
【０１７８】
シンボル値０の場合、原則としてルール１に基づいて記録するが、エラーが生じた結果レベルがシフトしてしまった場合を考慮してルール２も定めている。
【０１７９】
次に、シンボル値０以外の割り付け方について説明する。
【０１８０】
シンボル値１〜（ｐ−１）／２は、図６に示すように、メモリセルＭＣ１の２番目に低いレベルからメモリセルＭＣ２の最上位レベルにかけて割り付けられている。なお、メモリセルＭＣ１の最上位レベル及びメモリセルＭＣ２の最下位レベルは、シンボル値２ｈ−２−１となり、便宜上、同じシンボル値が割り付けられていることに注意する。
【０１８１】
シンボル値−（ｐ−１）／２〜−1は、メモリセルＭＣ２の２番目に低いレベルからメモリセルＭＣ１の最上位レベルにかけて割り付けられている。これは、図６に示すシンボル値を絶対値とする負数とした上で、メモリセルＭＣ１、ＭＣ２の役割を交換したものである。
便宜上、同じシンボル値が割り付けられていることに注意する。なお、メモリセルＭＣ２の最上位レベル及びメモリセルＭＣ１の最下位レベルは、シンボル値−２ｈ−２＋１となり、便宜上、同じシンボル値が割り付けられていることに注意する。
【０１８２】
但し、上記の通り、メモリセルＭＣ１、ＭＣ２の各レベルには２つのシンボル値が割り付けられているため、いずれのシンボル値を採用するかについて以下のルールを定める。
【０１８３】
（ルール３）  シンボル値が１〜２ｈ−２−１の場合、メモリセルＭＣ２を最下位レベルにする。実際のシンボル値はメモリセルＭＣ１によって表す。
【０１８４】
（ルール４）  シンボル値が２ｈ−２〜（ｐ−１）／２の場合、メモリセルＭＣ１を最上位レベルにする。実際のシンボル値はメモリセルＭＣ２によって表す。
【０１８５】
（ルール５）  シンボル値が−２ｈ−２＋１〜−１の場合、メモリセルＭＣ１を最下位レベルにする。実際のシンボル値はメモリセルＭＣ２によって表す。
【０１８６】
（ルール６）  シンボル値が−（ｐ−１）／２〜−２ｈ−２の場合、メモリセルＭＣ２を最上位レベルにする。実際のシンボル値はメモリセルＭＣ１によって表す。
【０１８７】
メモリセルＭＣのレベルとシンボル値との対応は、実際にはメモリシステム上でコード語シンボルをバイナリ表現に変えて、さらにメモリシステムへの読み出し書き込み回路でメモリセルＭＣのレベルに対応付けるための変換をする入出力システムによって実行される。
【０１８８】
また、２つのメモリセルＭＣ１、ＭＣ２を用いるため、これらメモリセルＭＣ１、ＭＣ２を多値の相補対として構成し、読み出しや書き込みのときに相互に参照メモリセルとして用いることもできる。このように、メモリセルＭＣのレベルにさらに参照レベルの考え方を導入する等については、本発明の本質ではないため説明は割愛するが、メモリセルのレベルとシンボル値の関連付けについては容易に拡張できるものである。
【０１８９】
次に、以上のようにシンボル値の割り付けを前提に、いくつかのエラー発生パターンを検証していく。ここで扱うエラーは、レベルが上又は下に一つだけシフトするものであり、コードの読み書きの際や、記憶状態の劣化によって生じるエラーを想定している。なお、図７〜図１１において、太い実線のレベルは、正しい状態のレベルを示し、細い実線は、エラーが生じた場合のレベルを示している。
【０１９０】
図７は、シンボル値０を記録した場合に生じるエラーを示す図である。
【０１９１】
ルール１から、シンボル値０は、メモリセルＭＣ１、ＭＣ２が共に最下位レベルの状態に割り当てられている。したがって、メモリセルＭＣ１のみにエラーが生じた場合、図７上図に示す通り、エラー発生後のシンボル値は１となる。この場合、エラー量は＋１となる。また、メモリセルＭＣ２のみにエラーが生じた場合、図７上図に示す通り、エラー発生後のシンボル値は−１となる。この場合、エラー量は−１となる。一方、メモリセルＭＣ１、ＭＣ２双方にエラーが生じた場合には、図７下図に示す通り、ルール２からシンボル値０として読み出すことになる。以上から、シンボル値が０の場合に生じるエラーは、エラー量±１の範囲で収まる。
【０１９２】
図８Ａは、一般的なシンボル値であるシンボル値６を記録した場合に生じるエラーを示す図である。
【０１９３】
メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は５又は７となる。この場合、エラー量は±１となる。メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ２のみを考えた場合、２ｈ−２となる。しかし、メモリセルＭＣ１が中間レベルであるため、メモリセルＭＣ１が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ２が示す６になる。この場合、エラー量は０となる。また、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合でも、メモリセルＭＣ２のシンボル値は無視されるため、エラー量は±１となる。以上から、シンボル値が６の場合に生じるエラーは、エラー量±１の範囲で収まる。
【０１９４】
図８Ｂは、一般的なシンボル値であるシンボル値−６を記録した場合に生じるエラーを示す図である。
【０１９５】
メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は−５又は−７となる。この場合、エラー量は±１となる。メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ１のみを考えた場合、−２ｈ−２となる。しかし、メモリセルＭＣ２が中間レベルであるため、メモリセルＭＣ１が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ２が示す−６になる。この場合、エラー量は０となる。また、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合でも、メモリセルＭＣ１のシンボル値は無視されるため、エラー量は±１となる。以上から、シンボル値−６を記録した場合に生じるエラーは、エラー量±１の範囲で収まる。
【０１９６】
図９Ａは、一般的なシンボル値であるシンボル値２ｈ−２＋４を記録した場合に生じるエラーを示す図である。
【０１９７】
メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は２ｈ−２＋３又は２ｈ−２＋５となる。この場合、エラー量は±１となる。メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ１のみを考えた場合、２ｈ−２−２となる。しかし、メモリセルＭＣ２が中間レベルであるため、メモリセルＭＣ１が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ２が示す２ｈ−２＋４になる。この場合、エラー量は０となる。また、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合でも、メモリセルＭＣ１のシンボル値は無視されるため、エラー量は±１となる。以上から、シンボル値２ｈ−２＋４を記録した場合に生じるエラーは、エラー量±１の範囲で収まる。
【０１９８】
図９Ｂは、一般的なシンボル値であるシンボル値−２ｈ−２−４を記録した場合に生じるエラーを示す図である。
【０１９９】
メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は２ｈ−２−３又は２ｈ−２−５となる。この場合、エラー量は±１となる。メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ２のみを考えた場合、−２ｈ−２＋２となる。しかし、メモリセルＭＣ１が中間レベルであるため、メモリセルＭＣ２が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ２が示す−２ｈ−２＋２になる。この場合、エラー量は０となる。また、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合でも、メモリセルＭＣ１のシンボル値は無視されるため、エラー量は±１となる。以上から、シンボル値−２ｈ−２＋２を記録した場合に生じるエラーは、エラー量±１の範囲で収まる。
【０２００】
図１０Ａは、メモリセルＭＣ１、ＭＣ２の境界辺りに割り付けられたシンボル値２ｈ−２を記録した場合に生じるエラーを示す図である。
【０２０１】
メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は２ｈ−２＋１又は２ｈ−２−１となる。この場合、エラー量は±１となる。メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ１のみを考えた場合、２ｈ−２―２となる。しかし、メモリセルＭＣ２が中間レベルであるため、メモリセルＭＣ１が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ２が示す２ｈ−２になる。この場合、エラー量は０となる。一方、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合であって、メモリセルＭＣ２が最下位レベルにある場合、エラー発生後のシンボル値は２ｈ−２−２となる。この場合、エラー量は−２となる。以上から、シンボル値２ｈ−２を記録した場合に生じるエラーは、エラー量−２〜＋１の範囲となる。
【０２０２】
図１０Ｂは、メモリセルＭＣ１、ＭＣ２の境界辺りに割り付けられたシンボル値−２ｈ−２を記録した場合に生じるエラーを示す図である。
【０２０３】
メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は−２ｈ−２−１又は−２ｈ−２＋１となる。この場合、エラー量は±１となる。メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ２のみを考えた場合、−２ｈ−２＋２となる。しかし、メモリセルＭＣ１が中間レベルであるため、メモリセルＭＣ２が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ１が示す−２ｈ−２になる。この場合、エラー量は０となる。一方、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合であって、メモリセルＭＣ１が最下位レベルにある場合、エラー発生後のシンボル値は−２ｈ−２＋２となる。この場合、エラー量は＋２となる。以上から、シンボル値−２ｈ−２を記録した場合に生じるエラーは、エラー量−１〜＋２の範囲となる。
【０２０４】
図１１Ａは、メモリセルＭＣ１、ＭＣ２の境界辺りに割り付けられたシンボル値２ｈ−２−２を記録した場合に生じるエラーを示す図である。
【０２０５】
メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は２ｈ−２−１又は２ｈ−２−３となる。この場合、エラー量は±１となる。メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ２のみを考えた場合、２ｈ−２となる。しかし、メモリセルＭＣ１が中間レベルであるため、メモリセルＭＣ２が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ１が示す２ｈ−２−２になる。この場合、エラー量は０となる。一方、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合であって、メモリセルＭＣ１が最上位レベルにある場合、エラー発生後のシンボル値は２ｈ−２となる。この場合、エラー量は＋２となる。以上から、シンボル値２ｈ−２−２を記録した場合に生じるエラーは、エラー量−１〜＋２の範囲となる。
【０２０６】
図１１Ｂは、メモリセルＭＣ１、ＭＣ２の境界辺りに割り付けられたシンボル値−２ｈ−２＋２を記録した場合に生じるエラーを示す図である。
【０２０７】
メモリセルＭＣ２にのみエラーが生じた場合、エラー発生後のシンボル値は−２ｈ−２＋１又は−２ｈ−２＋３となる。この場合、エラー量は±１となる。メモリセルＭＣ１にのみエラーが生じた場合、エラー発生後のシンボル値は、メモリセルＭＣ１のみを考えた場合、−２ｈ−２となる。しかし、メモリセルＭＣ２が中間レベルであるため、メモリセルＭＣ１が示すシンボル値は無視される。したがって、シンボル値は、メモリセルＭＣ２が示す−２ｈ−２＋２になる。この場合、エラー量は０となる。一方、メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合であって、メモリセルＭＣ２が最上位レベルにある場合、エラー発生後のシンボル値は−２ｈ−２となる。この場合、エラー量は−２となる。以上から、シンボル値−２ｈ−２＋２を記録した場合に生じるエラーは、エラー量−２〜＋１の範囲となる。
【０２０８】
ここで、メモリセルＭＣ１、ＭＣ２に対するシンボル値（Ｚｐの要素）のうち最小値及び最大値の割り付けについて言及しておく。シンボル値のうち最小値及び最大値の割り付けは、メモリセルＭＣ１、ＭＣ２に設定できるレベルによっては不定になることがある。すなわち、シンボル値（ｐ−１）／２、−（ｐ−１）／２がそれぞれメモリセルＭＣ１、ＭＣ２の最上位レベルに割り付けられて、メモリセルＭＣ１、メモリセルＭＣ２が共に最上位レベルにある場合、シンボル値が（ｐ−１）／２、−（ｐ−１）／２のいずれであるかを一意に決めることができない。
【０２０９】
そこで、シンボル値（ｐ−１）／２、−（ｐ−１）／２をメモリセルのレベル数に依らず、図１２Ａ、図１２Ｂのように割り当てる。すなわち、シンボル値（ｐ−１）／２、−（ｐ−１）／２の割り当てルールは以下のようになる。
【０２１０】
（ルール７）  メモリセルＭＣ１、ＭＣ２が共に最上位レベルにある場合、シンボル値として最大値（ｐ−１）／２を割り当てる。
【０２１１】
（ルール８）  メモリセルＭＣ１、ＭＣ２が共に２番目に高いレベルにある場合、シンボル値として最小値−（ｐ−１）／２を割り当てる。
【０２１２】
ところで、メモリセルＭＣ１、ＭＣ２のレベル数とシンボル数の選択によっては、最上位レベルにシンボル値を割り当てることができない場合もある。そこで、レベルに対するシンボル値の割り付けルールとして更にルールを定める。
【０２１３】
（ルール９）  メモリセルＭＣ１のレベルが最上位レベルであり、且つ、メモリセルＭＣ２のレベルが（ｐ−１）／２−１以上のシンボル値に割り当てられているレベル以上、最上位レベルより下のレベルである場合、シンボル値を（ｐ−１）／２−１とする。
【０２１４】
（ルール１０）  メモリセルＭＣ２のレベルが最上位レベルであり、且つ、メモリセルＭＣ１のレベルが−（ｐ−１）／２＋１以上のシンボル値に割り当てられているレベル以上、最上位レベルより下のレベルである場合、シンボル値を−（ｐ−１）／２＋１とする。
【０２１５】
（ルール１１）  メモリセルＭＣ１、ＭＣ２が共に３番目に高いレベルの状態を−（ｐ−１）／２とする。
【０２１６】
このようにシンボル値の最小値及び最大値をメモリセルＭＣ１、ＭＣ２のレベルに割り当てることで、シンボル値の最小値及び最大値が不定になることはない。
【０２１７】
以下において、メモリセルＭＣ１、ＭＣ２には、シンボル数よりも多いレベル数を有しており、シンボル値±（ｐ−１）／２−１に割り当てられたレベルと最上位レベルとの間に２つ以上のレベルを有しているものとする。
【０２１８】
図１３Ａは、シンボル値（ｐ−１）／２を記録した場合に生じるエラーを示す図である。なお、シンボル値が（ｐ−１）／２の場合、ルール７から、メモリセルＭＣ１、ＭＣ２が共に最上位レベルとなる。
【０２１９】
メモリセルＭＣ１にのみエラーが生じた場合、メモリセルＭＣ１のレベルは、２番目に高いレベルとなっている。したがって、ルール６から、シンボル値は−（ｐ−１）／２＋１となる。この場合のエラー量は、｛−（ｐ−１）／２＋１｝−（ｐ−１）／２＝−ｐ＋２≡２となる。メモリセルＭＣ２にのみエラーが生じた場合、メモリセルＭＣ２のレベルは、２番目に高いレベルとなっている。したがって、ルール４から、シンボル値は（ｐ−１）／２−１となる。この場合のエラー量は、−１となる。メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合、ルール８から、シンボル値は−（ｐ−１）／２となる。この場合のエラー量は、−（ｐ−１）／２−（ｐ−１）／２＝−ｐ＋１≡１となる。以上から、シンボル値（ｐ−１）／２を記録した場合に生じるエラーは、エラー量−１〜＋２の範囲となる。
【０２２０】
図１３Ｂは、シンボル値が−（ｐ−１）／２を記録した場合に生じるエラーを示す図である。なお、シンボル値が−（ｐ−１）／２の場合、ルール８から、メモリセルＭＣ１、ＭＣ２が共に２番目に高いレベルとなる。
【０２２１】
メモリセルＭＣ１にエラーが生じ、最上位レベルになっている場合について検討する。メモリセルＭＣ２にエラーが生じ、最上位レベルになっている場合、ルール７から、シンボル値は（ｐ−１）／２となる。この場合のエラー量は−１となる。メモリセルＭＣ２にエラーが生じなかった場合、ルール９から、シンボル値は（ｐ−１）／２−１となる。この場合のエラー量は−２となる。メモリセルＭＣ２にエラーが生じ、３番目に高いレベルになっている場合、ルール９から、シンボル値は（ｐ−１）／２−１となる。この場合のエラー量は−２となる。
【０２２２】
メモリセルＭＣ１にエラーが生じなかった場合について検討する。メモリセルＭＣ２にエラーが生じ、最上位レベルになっている場合、ルール１０から、シンボル値は−（ｐ−１）／２＋１となる。この場合のエラー量は＋１となる。メモリセルＭＣ２にエラーが生じ、３番目に高いレベルになっている場合、（ｐ−１）／２−１となる。この場合のエラー量は−２となる。
【０２２３】
メモリセルＭＣ１にエラーが生じ、３番目に高いレベルになっている場合について検討する。メモリセルＭＣ２にエラーが生じ、最上位レベルになっている場合、シンボル値は−（ｐ−１）／２＋１となる。この場合のエラー量は＋１となる。メモリセルＭＣ２にエラーが生じなかった場合、シンボル値は−（ｐ−１）／２＋１となる。この場合のエラー量は＋１となる。メモリセルＭＣ２にエラーが生じ、３番目に高いレベルになっている場合、ルール１１から、シンボル値は−（ｐ−１）／２となる。この場合エラーは生じていない。
【０２２４】
以上から、シンボル値−（ｐ−１）／２を記録した場合に生じるエラーは、エラー量−２〜＋１の範囲となる。
【０２２５】
図１４Ａ、図１４Ｂは、メモリセルＭＣ１、ＭＣ２のレベル数がＺｐの要素数よりも多い場合で、シンボル値（ｐ−１）／２−１、−（ｐ−１）／２＋１が割り当てられているレベルと、メモリセルＭＣ２、ＭＣ１の最上位レベルとの間に１つのレベルを有する場合について示している。
【０２２６】
このような割り付けの場合、シンボル値が（ｐ−１）／２、−（ｐ−１）／２の場合に生じるエラーの状態は図１３Ａ、図１３Ｂに示す場合と全く同じになる。これは、３番目に高いレベルになっている場合、ルール１１から、シンボル値が図１３Ａ、図１３Ｂに示す場合と同じになるからである。したがって、ここでは、シンボル値が（ｐ−１）／２−１、−（ｐ−１）／２＋１の場合に生じるエラーについて検討する。
【０２２７】
図１４Ａは、シンボル値（ｐ−１）／２−１を記録した場合に生じるエラーを示す図である。なお、シンボル値が（ｐ−１）／２−１の場合、正しくは、メモリセルＭＣ１が最上位レベル、メモリセルＭＣ２が３番目に高いレベルとなる。
【０２２８】
メモリセルＭＣ１にのみエラーが生じた場合、メモリセルＭＣ２が中間レベルであるため、エラーは生じない。一方、メモリセルＭＣ２にのみエラーが生じ、２番目に高いレベル、４番目に高いレベルになっている場合、シンボル値はそれぞれ（ｐ−１）／２−１、（ｐ−１）／２−２となる。この場合のエラー量は、それぞれ０、−１となる。
【０２２９】
メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合、シンボル値は−（ｐ−１）／２、（ｐ−１）／２−２となる。この場合のエラー量はそれぞれ２、−１となる。
【０２３０】
以上から、シンボル値（ｐ−１）／２−１を記録した場合に生じるエラーは、エラー量−１〜＋２の範囲となる。
【０２３１】
図１４Ｂは、シンボル値−（ｐ−１）／２＋１を記録した場合に生じるエラーを示す図である。なお、シンボル値が−（ｐ−１）／２＋１の場合、正しくは、メモリセルＭＣ１が３番目に高いレベル、メモリセルＭＣ２が最上位レベルとなる。
【０２３２】
メモリセルＭＣ１にのみエラーが生じ、２番目に高いレベル、４番目に高いレベルになっている場合、シンボル値はそれぞれ−（ｐ−１）／２＋１、−（ｐ−１）／２＋２となる。この場合のエラー量はそれぞれ０、＋１となる。
【０２３３】
メモリセルＭＣ２にのみエラーが生じた場合、メモリセルＭＣ１が中間レベルにあるため、エラーは生じない。
【０２３４】
メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合、シンボル値は−（ｐ−１）／２、−（ｐ−１）／２＋２となる。この場合のエラー量はそれぞれ−１、＋１となる。
【０２３５】
以上から、シンボル値−（ｐ−１）／２＋１を記録した場合に生じるエラーは、エラー量±１の範囲となる。
【０２３６】
図１５Ａ、図１５Ｂは、メモリセルＭＣ１、ＭＣ２のレベル数がＺｐの要素数と合致した場合で、シンボル値（ｐ−１）／２−１、−（ｐ−１）／２＋１が割り当てられているレベルと、メモリセルＭＣ２、ＭＣ１の最上位レベルとの間に無駄なラベルが一つもない場合について示している。
【０２３７】
このような割り付けの場合、シンボル値（ｐ−１）／２、−（ｐ−１）／２を記録した場合に生じるエラーの状態は図１３Ａ、図１３Ｂに示す場合と全く同じになる。これは、３番目に高いレベルになっている場合、ルール１１から、シンボル値が図１３Ａ、図１３Ｂに示す場合と同じになるからである。したがって、ここでは、シンボル値（ｐ−１）／２−１、−（ｐ−１）／２＋１を記録した場合に生じるエラーについて検討する。
【０２３８】
図１５Ａは、シンボル値（ｐ−１）／２−１を記録した場合に生じるエラーを示す図である。なお、シンボル値（ｐ−１）／２−１の場合、正しくは、メモリセルＭＣ１が最上位レベル、メモリセルＭＣ２が２番目に高いレベルとなる。
【０２３９】
メモリセルＭＣ１にのみエラーが生じた場合、シンボル値は−（ｐ−１）／２となる。この場合のエラー量は＋２となる。
【０２４０】
メモリセルＭＣ２にのみエラーが生じた場合、シンボル値は（ｐ−１）／２、（ｐ−１）／２−２となる。この場合のエラー量はそれぞれ＋１、−１となる。
【０２４１】
メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合、シンボル値は−（ｐ−１）／２＋１、（ｐ−１）／２−２となる。この場合のエラー量はそれぞれ３、−１となる。
【０２４２】
以上から、シンボル値（ｐ−１）／２−１を記録した場合に生じるエラーは、エラー量−１〜＋３の範囲となる。
【０２４３】
図１５Ｂは、シンボル値−（ｐ−１）／２＋１を記録した場合に生じるエラーを示す図である。なお、シンボル値が−（ｐ−１）／２＋１の場合、正しくは、メモリセルＭＣ１が２番目に高いレベル、メモリセルＭＣ２が最上位レベルとなる。
【０２４４】
メモリセルＭＣ１にのみエラーが生じた場合、シンボル値は＋（ｐ−１）／２、−（ｐ−１）／２＋２となる。この場合のエラー量はそれぞれ−２、＋１となる。
【０２４５】
メモリセルＭＣ２にのみエラーが生じた場合、シンボル値は−（ｐ−１）／２となる。この場合のエラー量は−１となる。
【０２４６】
メモリセルＭＣ１、ＭＣ２に共にエラーが生じた場合、シンボル値は＋（ｐ−１）／２−１、−（ｐ−１）／２＋２となる。この場合のエラー量はそれぞれ−３、＋１となる。
【０２４７】
以上から、シンボル値−（ｐ−１）／２＋１を記録した場合に生じるエラーは、エラー量−３〜＋１の範囲となる。
【０２４８】
これまで見てきたように多レベルのメモリセルを用いた上記実施例では、エラー量は最大±３である。したがって、リー・メトリックが３のエラーに対応できれば、レベルの誤書き込みも含めて、レベルの誤認識のエラーに対応することができる。さらに、シンドローム変換法を使用すれば２つのコード語シンボルのエラーまでは完全に解を求めることができる。換言すれば、シンドローム変換法によって、２つのコード語シンボルを構成する４つのメモリセルの全部又は一部に不良がある場合でも対応することができる。
【０２４９】
そこで、このように多レベルのメモリセルをコード語シンボルの記憶に利用するために、ビットストリングとしてメモリシステムに入力されたデータをメモリセルのレベルに割り付ける方法を簡単に説明する。以下に説明する方法では、バイナリデータとしてのコード語シンボルをメモリシステムに保存する場合と同じ変換をする。
【０２５０】
メモリシステムにバイナリのビットストリングで入ってくるデータをｈビットずつの塊としてみて、それぞれを２ｈ進数の各桁の数と考える。桁数をδとすると数３７のようなデータ語Ｄ（ｈ）となる。ここで、ｄδ−１、ｄδ−２、…、ｄ１、ｄ０はｈビットからなる単位データである。
【０２５１】
［数３７］
2011198253.tif 000039
【０２５２】
続いて、数３７に示すデータ語Ｄ（ｈ）を、数３８のようなｐ進数のデータ語Ｄ（ｈ）に変換する。ここで、ａδ、ａδ−１、…、ａ１、ａ０はｈビットの塊が表わすｐ進数表示のデータコードＸである。
【０２５３】
［数３８］
2011198253.tif 000040
【０２５４】
先に説明したように適当に素数ｐを選択すればこのときの桁数はδ＋１に抑えられる。しかし、多レベルのメモリセルを使用するときはレベル数を無闇には増やせないため、レベル数とそれに適合する素数ｐを予め決めておく。その上で条件に合うデータ語Ｄ（ｈ）を決めることになる。すなわち、メモリセルのレベル数から一括処理するデータのビット数Ｍを決めることになる。後に具体例でこの決め方を説明する。
【０２５５】
続いて、データコードＸと生成行列ＧからＣ＝ＸＧとして、ｐ−１個のコード語シンボルを作ることによって入力データがコードＣになる。このコードＣの各コード語シンボルは表現の代表元を−ｐ／２からｐ／２の整数で表すことによって、２ｈ−２個の多レベルを有するメモリセルで構成されたメモリシステムに保存する。
【０２５６】
次に、具体例によって説明する。ｐ−ＬＭ−ＥＣＣシステムで一括処理するデータのビット数Ｍ、単位データのビット数ｈと訂正可能なエラーのリー・メトリックの和の最大値εとの間にはｐ≧Ｍ／ｈ＋ε＋３なる関係が成立することは上述の通りである。また素数ｐは、２ｈ−１＜ｐ＜２ｈの範囲で選択することも上述の通りである。
【０２５７】
そこで、メモリセルのレベル数として、１メモリセル当たり８レベルが取れるとする。この場合、ｈ＝５であり、素数ｐの候補は１７、１９、２３、２９、３１のいずれかである。２つのメモリセルを用いる方法では３２個のコード語シンボルを扱うことができるため、３２を超えない条件を満たす素数ｐとして３１を選択する。
【０２５８】
εを２にすると、Ｍ≦１３０になる。バイト単位でデータを扱うとして、１６バイトに相当する１２８ビットのデータに対して一括にＥＣＣ処理を行う場合、Ｍ＝１２８でδ＝２６となる。したがって、メモリシステム内部で値を０と置くダミーのシンボル数κはκ＝ｐ−δ−ε−３＝３１−２６−２−３から０となる。データから見て余分に必要となるシンボル数である冗長シンボル数（ｎ−δ）は（ｎ−δ）＝ｐ−１−δ＝３１−１−２６から４となる。その結果、メモリシステムとしての冗長率は、データの桁数と余分に増加した桁数との比として、４／２６＝２／１３となる。これはエラー訂正を可能にするために余分に必要なメモリセルの増加率とみなせる。
【０２５９】
なお、ここで説明した多値レベルのメモリセルを２つ用いて、メモリセル１つ当たりのレベル数の４倍弱のシンボル数を記憶する方法は、ＥＣＣを用いない場合でも有効である。ビットデータをｐ進数で表し、各桁の数をＺｐの要素としてレベルに対応させればよいので、桁数δの２倍がＭビットを記憶する多値レベルのメモリセルの数にほぼ等しい。一方、従来の多値レベルのメモリセルの使用方法を用いると２ｈ−２のレベルのメモリセルは、（ｈ−２）ビットの記憶ができるので、Ｍビットの記憶にはＭ／（ｈ−２）＝ｈδ／（ｈ−２）＝δ（１−２／ｈ）−１のメモリセル数で良い。
【０２６０】
従って、本実施形態におけるｐ−ＬＭ−ＥＣＣシステムでは、Ｍビットはｎシンボルからなるコードで記憶され、１シンボル当たり２メモリセル用いるため、２ｎ＝２（ｐ−１）のメモリセルが必要となる。そこで、実質的な冗長度、すなわちデータ記憶の何倍の容量が必要となるかは２（ｐ−１）／δ（１−２／ｈ）−１である。具体的には、ｈ＝５の場合、ｐ＝３１でδ＝２６なので、実質冗長度は６０／４３＝１．４０となる。ε＝２であるため、最大２対のメモリセルのエラー訂正ができる。
【０２６１】
次の具体例として、１メモリセル当たりのレベル数を８、εを４とした場合について説明する。なお、この具体例の場合、最大４対のメモリセルのエラー訂正が可能である。
【０２６２】
先ず、この場合における本実施形態に係るメモリシステムの冗長率を示す。ｈ＝５とすると、素数ｐとして例えば３１を選択することができる。ε＝４からＭ≦１２０となるため、一括処理するデータのビット数Ｍとして、例えばＭ＝１２０（１５バイト）を設定する。この場合、δ＝２４となり、ダミーのシンボル数κはκ＝ｐ−δ−ε−３＝３１−２４−４−３から０となる。したがって、冗長シンボル数（ｎ−δ）は（ｎ−δ）＝ｐ−１−δ＝３１−１−２４から６となる。以上から、本メモリシステムの冗長率は、６／２４＝３／１２となる。
【０２６３】
続いて、ＥＣＣシステムを使用しない従来のメモリシステムに対する冗長度を示す。従来のメモリシステムの場合、１２０ビットのデータ記憶に用いるレベル数８（３ビット）のメモリセルの数は４０となる。これに対し、本実施形態の場合、メモリセルの数は６０となる。以上から、従来のメモリシステムに対する冗長度は、６０／４０＝１．５となる。
【０２６４】
次の具体例として、１メモリセル当たりのレベル数を１６、εを４とした場合について説明する。なお、この具体例の場合、最大４対のメモリセルのエラー訂正が可能である。
【０２６５】
先ず、この場合における本実施形態に係るメモリシステムの冗長率を示す。ｈ＝６とすると、素数ｐとして例えば６１を選択することができる。ε＝４からＭ≦３２４となるため、一括処理するデータのビット数Ｍとして、例えばＭ＝３２４（４０．５バイト）を設定する。この場合、δ＝５４となり、ダミーのシンボル数κはκ＝ｐ−δ−ε−３＝６１−５４−４−３から０となる。したがって、冗長シンボル数（ｎ−δ）は（ｎ−δ）＝ｐ−１−δ＝６１−１−５４から６となる。以上から、本メモリシステムの冗長率は、６／５４＝１／１９となる。
【０２６６】
続いて、ＥＣＣシステムを使用しない従来のメモリシステムに対する冗長度を示す。従来のメモリシステムの場合、１２０ビットのデータ記憶に用いるレベル数１６（４ビット）のメモリセルの数は８１となる。これに対し、本実施形態の場合、メモリセルの数は１２０となる。以上から、従来のメモリシステムに対する冗長度は、１２０／８１≒１．４８となる。
【０２６７】
以上、３つの具体例を通して、１シンボルを多レベルのメモリセル２つで記憶する場合の冗長度を見てきたが、１メモリセルのレベル数、選択する素数ｐ、及び訂正可能なリー・メトリックの和の最大値εと、最低救済率、一括処理するデータのビット数の最大値Ｍｍａｘ、一括処理するデータのビット数Ｍ、単位データ数δ、従来のメモリシステムで必要なメモリセル数、及び従来のメモリシステムに対する冗長度との関係をまとめた表を図１６に示す。図１６において、最大救済率については、エラー量に依らずｎ＝ｐ−１から最低でも２つのコード語シンボルを訂正できるため、２／（ｐ−１）としている。
【０２６８】
図１６の下線で示すように、例えば、従来のメモリシステムに対する冗長度を１．５以下にすることを条件とした場合、レベル数８以上でε=４以下を選択できることが分かる。但し、εが小さい場合他のコードを正しいとして訂正する誤訂正も増えるため、冗長度が許す限りはεをできるだけ大きくすることが望ましい。また、図１６から、レベル数２、すなわち単ビットのメモリセルにも適用することは現実的ではないことが分かる。
【０２６９】
［第２の実施形態］
次に、本発明の第２の実施形態として、単レベルのメモリセルを用いたメモリシステムに応用した場合について説明する。
【０２７０】
この場合、メモリセルのレベル数に拘束されないため、一括処理するデータを大きくすることができ、冗長度を非常に小さくできる。
【０２７１】
エンコードの手順は、多レベルのメモリセルを用いた場合と同様であるが、先ず、一括処理するデータのビット数Ｍを決定してから、素数ｐの選択を行う。
【０２７２】
具体例として、Ｍ＝４０９６（５１２バイト）とした場合の素数ｐの選択例を説明する。ここでは、εを４とする。この場合、γ＝ε＋１＝５となる。
【０２７３】
先ず、単位データのビット数をｈ＝８と仮定する。この場合、上述した素数ｐの選択条件によれば、素数ｐの選択範囲は、２ｈ−１＜ｐ＜２ｈから１２８＜ｐ＜２５６となる。しかし、この場合、ｐ≧Ｍ／ｈ＋ε＋３＋κから少なくともｐ≧４０９６／８＋４＋３＝５１９を具備する必要があるため、素数ｐを選択することはできない。
【０２７４】
そこで、単位データのビット数をｈ＝９とする。この場合、素数ｐの選択範囲は、２５６＜ｐ＜５１２、且つ、ｐ≧４０９６／９＋４＋３＝４６２．１となる。したがって、素数ｐを４６３＜ｐ＜５１２の範囲から選択することができる。そこで、ダミーシンボル数κが最小となるよう、この範囲内の素数４６７、４７９、４８７、４９１、４９９、５０３、５０９から、最小の４６７を素数ｐとして選択する。
【０２７５】
素数をｐ＝４６７とした場合、一括処理する単位データ数はδ＝４５６であり、冗長ビット数は、ｈ（γ＋１＋κ）＝９（４＋２＋４）＝９０となる。その結果、ＥＣＣシステムを使用しない従来のメモリシステムに対する冗長度は、（４０９６＋９０）／４０９６＝１．０２となり、多レベルのメモリセルを用いた場合よりも小さい。しかし、一方では、最低救済率は２／４６６＝１／２３３となり、多レベルのメモリセルに比べて１桁程度小さくなってしまう。
【０２７６】
以下、単レベルのメモリセルを用いたメモリセルシステムにおいて、いくつかの条件設定に対する冗長度を評価する。
【０２７７】
図１７〜図２２に示す表は、訂正可能なエラーのリー・メトリックの和の最大値ε、及び一括処理するデータのビット数Ｍと、単位データ数δ、δ＋ε＋３（素数ｐの選択条件）、２ｈ−１＜ｐ＜２ｈ（素数ｐの選択条件）、ダミーシンボル数κ、及び冗長度を示す冗長ビット数ｈ（ｐ−１−δ）との関係を示している。一括処理するデータのビット数Ｍは、２５６、５１２、１０２４、２０４８、４０９６としている。
【０２７８】
なお、比較例として、ＧＦ（２ｎ）の要素数と、このＧＦ（２ｎ）を利用したＲＳ−ＥＣＣシステムにおける冗長ビット数も併せて示している。ここで示す要素（シンボル）数及び冗長ビット数は、素数ｐに対して決定する単位データのビット数ｈのまとまりを１シンボルとして算出している。
【０２７９】
図１７は、２つのコード語シンボルのエラーを訂正可能にした場合（ε＝２）の表である。なお、図１７に示すＲＳ−ＥＣＣシステムは、２シンボルまでのエラー訂正を可能とするものである。
【０２８０】
素数ｐの選択範囲は、一括処理するデータのビット数Ｍによって制限されるため、Ｍ＝２５６（３２バイト）ではｐ＝５３、Ｍ＝５１２（６４バイト）ではｐ＝７９、Ｍ＝１０２４（１２８バイト）ではｐ＝１３７、Ｍ＝４０９６（５１２バイト）ではｐ＝４６１となっている。また、Ｍ＝２０４８（２５６バイト）では素数ｐを選択することができない。
【０２８１】
２つのコード語シンボルに生じたエラーについては、比較例となるＲＳ−ＥＣＣシステムでも訂正することができる。したがって、冗長ビット数を小さくできない場合、本実施形態におけるｐ−ＬＭ−ＥＣＣシステムを適用してもあまり意味がない。
【０２８２】
図１７に示す通り、ε＝２の場合、ｐ−ＬＭ−ＥＣＣシステムの冗長ビット数は、ＲＳ−ＥＣＣシステムの冗長ビット数よりも小さくなることはない。したがって、ε＝２の場合、ＲＳ−ＥＣＣシステムとの比較において有利な点はない。
【０２８３】
図１８は、３つのコード語シンボルのエラーを訂正可能にした場合（ε＝３）の表である。なお、図１８に示すＲＳ−ＥＣＣシステムは、３シンボルまでのエラー訂正を可能とするものである。
【０２８４】
ε＝３の場合、図１８に示すε＝２の場合に対し、Ｍ＝５１２（６４バイト）における素数がｐ＝８３、Ｍ＝４０９６（５１２バイト）における素数がｐ＝４６３となる点において異なる。
【０２８５】
この場合も、ＲＳ−ＥＣＣシステムの冗長ビット数よりも小さくなることはなく、ＲＳ−ＥＣＣシステムとの比較において有利な点はない。
【０２８６】
図１９は、４つのコード語シンボルのエラーを訂正可能にした場合（ε＝４）の表である。なお、図１９に示すＲＳ−ＥＣＣシステムは、４シンボルまでのエラー訂正を可能とするものである。
【０２８７】
ε＝４の場合、図１８に示すε＝３の場合に対し、Ｍ＝４０９６（５１２バイト）における素数がｐ＝４６７となる点において異なる。
【０２８８】
この場合も、ＲＳ−ＥＣＣシステムの冗長ビット数よりも小さくなることはなく、ＲＳ−ＥＣＣシステムとの比較において有利な点はない。
【０２８９】
図２０は、６つのコード語シンボルのエラーを訂正可能にした場合（ε＝６）の表である。なお、図２０に示すＲＳ−ＥＣＣシステムは、６シンボルまでのエラー訂正を可能とするものである。
【０２９０】
ε＝６の場合、図１９に示すε＝４の場合と選択する素数ｐは変わらない。
【０２９１】
ｐ−ＬＭ−ＥＣＣシステムを用いた場合、６シンボルのエラー訂正を可能に構成されたＲＳ−ＥＣＣシステムの冗長ビット数よりも小さくすることができ有利である。但し、ｐ−ＬＭ−ＥＣＣシステムでは、全てのエラーバターンを訂正できない事を考慮する必要がある。しかし、エラーが生じたシンボル数が２つ以内の場合、完全にエラーの解を求めることができ、さらに、エラーが生じたシンボル数が３つ以上であっても、訂正可能なリー・メトリックの和が６以内であればエラー訂正可能である。したがって、エラーが生じたシンボル数が６つまでならある程度エラー訂正が可能である。以上の点からε＝６の場合、ｐ−ＬＭ−ＥＣＣシステムの適用は有効である。
【０２９２】
図２１は、７つのコード語シンボルのエラーを訂正可能にした場合（ε＝７）の表である。なお、図２１に示すＲＳ−ＥＣＣシステムは、７シンボルまでのエラー訂正を可能とするものである。
【０２９３】
ε＝７の場合、図２０に示すε＝６の場合に対し、Ｍ＝２５６（３２バイト）における素数がｐ＝５９、Ｍ＝５１２（６４バイト）における素数がｐ＝８９、Ｍ＝１０２４（１２８バイト）における素数がｐ＝１３９となる点において異なる。
【０２９４】
ｐ−ＬＭ−ＥＣＣシステムを用いた場合、７シンボルのエラー訂正を可能に構成されたＲＳ−ＥＣＣシステムの冗長ビット数よりも小さくすることができ有利である。この場合でも、全てのエラーバターンに対応することはできないが、２シンボルまでのエラーを完全に解を求めることができる点、最大７シンボルのエラー訂正が可能である点から、有効である。
【０２９５】
図２２は、８つのコード語シンボルのエラーを訂正可能にした場合（ε＝８）の表である。なお、図２２示すＲＳ−ＥＣＣシステムは、８シンボルまでのエラー訂正を可能とするものである。
【０２９６】
ε＝８の場合、図２１に示すε＝７の場合と選択する素数ｐは変わらない。
【０２９７】
ｐ−ＬＭ−ＥＣＣシステムを用いた場合、８シンボルのエラー訂正を可能に構成されたＲＳ−ＥＣＣシステムの冗長ビット数よりも小さくすることができる。この場合でも、全てのエラーバターンに対応することはできないが、２シンボルまでのエラーを完全に解を求めることができる点、最大８シンボルのエラー訂正が可能である点から有効である。
【０２９８】
以上、図１７〜図２２に示すように、ｐ−ＬＭ−ＥＣＣシステムがＲＳ−ＥＣＣシステムに対して有利性を発揮できるのは以下の場合である。つまり、一括処理するデータのビット数がＭ＝４０９６（５１２バイト）の場合、ε＝４〜８では、選択できる素数はｐ＝４６７と変わらず、冗長ビット数も９０となる。したがって、ε＝８とすることが望ましい。同様に、Ｍ＝１０２４（１２８バイト）ではε＝６、Ｍ＝５１２（６４バイト）ではε＝６、Ｍ＝２５６（３２バイト）ではε＝６とすることで、ＲＳ−ＥＣＣシステムに対する有利性を発揮できる。
【０２９９】
［まとめ］
ここでは、改めて上記実施形態におけるｐ−ＬＭ−ＥＣＣシステムの、エンコード手順、デコード手順、及びシステム構成をまとめる。
【０３００】
エンコード手順を図２を用いてまとめる。図２において、Ｚｐを決める素数ｐ、１シンボルにおけるエラー量が１の場合の訂正可能なシンボル数ε（＝γ−１）、シンボルのバイナリ表現の桁数ｈ、及び一括処理するデータのビット数Ｍ（＝δｈ）は既に決まっているものとする。また、ｎ＝ｐ−１、ｋ＝ｎ−γなる関係があるものとする。
【０３０１】
エンコードの手順は、以下の通り、２つの段階に大別できる。
【０３０２】
（手順１）  先ず、外部からメモリシステムに入力されたバイナリデータをｈビットずつまとめ、数３８に示す２ｈ進数表現のδ桁のデータ語Ｄ（ｈ）に変換する（図２のＳ１）。
【０３０３】
［数３９］
2011198253.tif 000041
【０３０４】
続いて、数３９で示すデータ語Ｄ（ｈ）を、更に、数４０に示すｐ進数表現のδ＋１桁のデータ語Ｄ（ｈ）に変換する（図２のＳ２）。
【０３０５】
［数４０］
2011198253.tif 000042
【０３０６】
（手順２）  先ず、手順１によって得られたＺｐの要素ａ０〜ａδにゼロをκ個だけ追加し、数４１に示すデータＤのｋ個の要素ａ０〜ａｋ−１とする。
【０３０７】
［数４１］
2011198253.tif 000043
【０３０８】
続いて、このデータＤに生成行列Ｇを乗じてコードＣのｎ個のコード語シンボルｃ１〜ｃｎを得る（図２のＳ３）。各コード語シンボルの値は数４２に示す通りである。
【０３０９】
［数４２］
2011198253.tif 000044
【０３１０】
最後に、このコード語シンボルｃｊをメモリセルに記憶する（図２のＳ４）。
【０３１１】
エンコード手順を図３Ａ、図３Ｂを用いてまとめる。
【０３１２】
デコードの手順は、以下の通り以下の通り、７つの手順に大別できる。なお、以下において手順の番号は、エンコードの手順を含めた通し番号となる。また、以下に示す手順３及び手順４は、Ｚｐの各要素（ｍ＝０〜ｐ−２）に対して繰り返すことに注意されたい。
【０３１３】
（手順３）  メモリセルから読み出したコードＹを読み出す（図３ＡのＳ５）。コードＹは数４３に示す構成となっている。ここで、ｅｊは、コードＹの位置ｊにあるコード語シンボルのエラーのリー・メトリックを示す。
【０３１４】
［数４３］
2011198253.tif 000045
【０３１５】
続いて、コードＹを構成するｎ個のコード語シンボルの値ｙｊ（ｊ＝１〜ｎ）にｊｍを掛けて、ｊｍｙｊをＺｐの数として計算する。シンボル値ｙｊは多レベルのメモリセルの場合、レベルから求めることができる。また、一般のバイナリメモリならバイナリデータから得られる数である。コードＹにシンドローム行列Ｈの転置行列を乗じて数４４に示すように、シンドロームＳｍ〜Ｓｍ＋εからなるシンドローム系列Ｓ（＝ＹＨＴ）を得る（図３ＡのＳ６）。
【０３１６】
［数４４］
2011198253.tif 000046
【０３１７】
（手順４）  先ず、訂正可能なシンボル数の上限ε（＝γ−１）に対して、ｑ＝εＳｍ−１を計算し、手順３で求めたシンドロームＳｌからｑＳｍ〜ｑＳｍ＋εを求める。続いて、このｑＳｍ〜ｑＳｍ＋εから数４５に示す解探索多項式Ψ（ｘ）の係数ψｊを順次計算する（図３ＡのＳ７）。
【０３１８】
［数４５］
2011198253.tif 000047
【０３１９】
ここで、ｘεの係数であるψε≠0なら、手順５に進み解を得る。一方、ψε＝０なら、解無しとして処理を終了するか、訂正の可能性をさらに探索すべくη＝ε−１として、ｑ＝ηＳｍ−１を計算し、手順４を繰り返し、ｘηの係数であるψη≠０なら、手順５に進み解を得る。一方、ψη＝０なら、解無しとして処理を終了する。この手順４で処理できなくなった場合、対応できないエラー分布であるため、解無しとしてエラー訂正を中止する。
【０３２０】
（手順５）  手順４でψε≠０となって解を得られることが分かった場合、手順５、手順６で解を得る。先ず手順５では解の多重度を得るために、数４６に示すハッセ微分多項式［Ψ（ｘ）］［ｉ］を求める。手順４で得られた係数ψｊに対して、一連の２項係数を乗じることで掛けることでハッセ微分多項式の係数が得られる（図３ＡのＳ９）。
【０３２１】
［数４６］
2011198253.tif 000048
【０３２２】
（手順６）  得られたハッセ微分多項式に対して、Ｚｐの要素１〜ｐ−１を代入して、０次微分多項式（＝Ψ（ｘ））がゼロとなる要素ｒを全て求める。続いて、数４７に示すように、各ｒに対してｎ−１次微分多項式はゼロであるが、ｎ次微分多項式はゼロでない次数ｎを求める（図３ＢのＳ１０）。
【０３２３】
［数４７］
2011198253.tif 000049
【０３２４】
得られたｒは、エラーが生じたコードのコード語シンボルの位置の逆元であり、それに対応するｎは、生じたエラー量から変換された量となる。
【０３２５】
（手順７）  手順７では、解の多重度ｎからエラー量を変換で求める。エラーのあるコード語シンボルの位置はｔ＝ｒ−１となり、解を得るための多項式を得るために行なった変換の逆変換をｎに施すことになる。ｑｔｍｅｔ＝ｎの関係があるので、ｅｔ＝（ｑｔｍ）−１ｎとすればｎから本来のエラー量ｅｔを得ることができる。このエラー量ｅｔをメモリセルから読み出したコードＹのシンボル値ｙｔから引いて、訂正されたコードＣのシンボル値ｃｔを得る（図３ＢのＳ１１）。
【０３２６】
ここまでで、メモリセルに記憶された正しいコードＣが得られたので、手順８、手順９によって、メモリシステムに入力されたバイナリデータを求める。
【０３２７】
（手順８）  手順７によってエラー訂正されたコードＣと生成行列Ｇから、ＸＧ＝Ｃなる多元連立一次方程式を介して、ｋ個のＧＦ（ｐ）の要素ａ０〜ａｋ−１を求める。このうちκ個の要素は、ダミー要素（０）であるため実質δ＋１のＧＦ（ｐ）の要素ａ０〜ａδが得られたことになる。得られた要素ａ０〜ａδから、δ＋１桁のｐ進数表現のデータ語Ｄ（ｈ）を作る（図３ＢのＳ１２）
（手順９）  最後に、このデータ語Ｄ（ｈ）をδ桁の２ｈ進数表現に変換し、各桁の数字をバイナリ表現にする。以上によってメモリシステムに入力されたバイナリデータの復元が完了する（図３ＢのＳ１３）。
【０３２８】
次に、メモリシステムの構成を図１を用いてまとめる。
【０３２９】
メモリシステムは、大別してメモリ部１００とｐ−ＬＭ−ＥＣＣシステム２００とを備える。
【０３３０】
外部から入力されたバイナリ表現のデータＤは、ｐ進数変換部２０１に入力される。ｐ進数変換部は、このデータＤをδ桁のｐ進数表現のデータ語Ｄ（ｈ）に変換する。
【０３３１】
ｐ進数変換部２０１から出力されたデータ語Ｄ（ｈ）は、エンコード部２０２に入力される。エンコード部２０２は、このデータ語Ｄ（ｈ）に生成行列Ｇを作用させてＧＦ（ｐ）の要素からなるコードＣを生成する。エンコード部２０２から出力されたコードＣは、フラッシュメモリ、ＰＲＡＭ、ＲｅＲＡＭ等からなるメモリ部１００に入力され記憶される。
【０３３２】
メモリ部１００から読み出されたコードＹ（エラーを含むコードＣ）は、シンドローム生成部２０３に入力される。シンドローム生成部２０３は、ｍ＝０とした上で、このコードＹに対してシンドローム行列Ｈと、メモリ部１００から読み出されたコードＹのコード語シンボルの位置を示す数のｍ乗とを乗じる処理を対角行列を用いて行いシンドロームＳを生成する。ここで、シンドロームＳがゼロの場合、コードＹはエラーを含まないため、コードＹはそのままコードＣとしてデコード部２０７で処理される。一方、シンドロームＳがゼロでない場合、エラー訂正をするために解探索多項式生成部２０４に処理が移る。
【０３３３】
解探索多項式生成部２０４は、シンドローム生成部２０３から出力されたシンドロームＳから解探索多項式Ψ（ｘ）を生成する。そのη＝γ−１次の次数の係数がゼロでない場合、解を求めるためハッセ微分多項式生成部２０５に処理が移る。一方、η次の次数の係数がゼロの場合、必要に応じてηから１を減じた新たなηに対して解探索多項式Ψ（ｘ）を求めるべく解探索多項式生成部２０４に再び処理が移る。これでも尚、η次の係数がゼロの場合、更にｍに１を加えて新たなシンドロームＳを求めるべくシンドローム生成部２０３に処理が移る。この一連の処理を、解探索多項式Ψ（ｘ）のη次の係数がゼロになるまで繰り返す。η＝γ−２、ｍ＝ｐ−２まで繰り返しても、解探索多項式Ψ（ｘ）のη次の係数がゼロであった場合、エラー訂正は不可能であるため、外部にエラー信号ＮＧを出力する。なお、エラー訂正が可能な場合であっても、全てのｍについて一連の処理を繰り返して訂正されたコードを求めると一致しないコードが得られる場合がある。この場合は誤訂正の判定ができ、得られたコードの中に正しいコードがある、いわゆるリストエラー訂正となる。
【０３３４】
ハッセ微分多項式生成部２０５は、η次の係数が非ゼロの解探索多項式Ψ（ｘ）からハッセ微分多項式を求め、これらの根ｒとその根の多重度ｎをＧＦ（ｐ）の中から抽出する。
【０３３５】
コード復元部２０６は、ハッセ微分多項式生成部２０５で抽出された根ｒを用いてｔ＝ｒ−１からコードＹにおけるエラーシンボルの位置を求めると共に、多重度ｎを用いてエラー量ｅｔを求める。そして、この結果からコードＣを復元する。
【０３３６】
コード復元部２０６で復元されたコードＣは、デコード部２０７に入力される。デコード部２０７は、このコードＣに対して生成行列Ｇの逆変換を行いｐ進数表現のデータ語Ｄ（ｈ）を再生する。
【０３３７】
デコード部で再生されたｐ進数表現のデータ語Ｄ（ｈ）は、バイナリ変換部２０８に入力される。バイナリ変換部２０８は、このｐ進数表現のデータ語Ｄ（ｈ）を２ｈ進数表現のデータ語Ｄ（ｈ）への変換を介してバイナリデータＤを生成する。最後にバイナリデータＤは読み出しデータとして外部に出力される。
【０３３８】
なお、図２１では、メモリシステムにｐ−ＬＭ−ＥＣＣシステムに内蔵されている場合を示したが、ｐ−ＬＭ−ＥＣＣシステムは、メモリシステムの外部にあっても良い。
【０３３９】
最後に、本発明の実施形態に係るメモリシステムで採用するシンドローム変換方式のエラー訂正能力を改めて説明する。ここでは、最大４シンボルの訂正が可能なｐ−ＬＭ−ＥＣＣシステムのエラー訂正能力について、２シンボルの訂正が可能なＲＳ−ＥＣＣシステム、及びランダムな４ビットのエラー訂正が可能な２ｎ−ＢＣＨ−ＥＣＣシステムとの比較により検討する。
【０３４０】
図２３は、これら３つのＥＣＣシステムのエラー訂正の可否をまとめた表である。表の「エラー」列にある四角形はシンボルを、この四角形の中にある黒点は、エラーが生じたビットをそれぞれイメージしたものである。なお、１シンボルは８ビットで構成されている。
【０３４１】
ＲＳ−ＥＣＣシステムを用いた場合、どの様なエラーであっても２シンボルまでの訂正が可能である。しかし、図２３に示す通り、エラーのビット数が少なくても、これが３以上のシンボルに亘る場合には一切訂正することができない。
【０３４２】
２ｎ−ＢＣＨ−ＥＣＣシステムを用いた場合、４ビットまでなら、どの様なエラーが生じても訂正することができる。しかし、エラーが５ビット以上ある場合には、それが例え１シンボルに収まっていてもエラー訂正することはできない。
【０３４３】
本発明の実施形態に係るｐ−ＬＭ−ＥＣＣシステムを用いた場合、２シンボルに収まるエラーであれば、どの様なエラーであっても訂正することができる。さらに、３以上のシンボルに広がるエラーであっても、そのエラー内容が各シンボルで類似している場合、最大４シンボルまで訂正することができる。ｐ−ＬＭ−ＥＣＣシステムの場合、４シンボルに亘るエラーを完全に訂正することはできないが、ＲＳ−ＥＣＣシステムに比べて、冗長度が低い点で有効である。
【０３４４】
以上から分かるように、ＲＳ−ＥＣＣシステムは塊エラーの訂正が得意である一方、ランダムエラーの訂正が不得意である。また、２ｎ−ＢＣＨ−ＥＣＣシステムはランダムエラーの訂正が得意である一方、塊エラーの訂正が不得意である。したがって、ＲＳ−ＥＣＣシステム、２ｎ−ＢＣＨ−ＥＣＣシステムでは、メモリシステムの微細化によってランダムエラー及び塊エラーが併発する場合に対応することが困難である。その点、その点、本発明の実施形態に係るｐ−ＬＭ−ＥＣＣシステムは、このような塊エラー及びランダムエラーに対応することができるため、微細化されたメモリシステムに最適である。
【０３４５】
［その他］
以上、発明の実施の形態を説明したが、本発明はこれらに限定されるものではなく、発明の趣旨を逸脱しない範囲内において、種々の変更、追加等が可能である。
【０３４６】
本発明の実施形態は、３以上のレベル数を有するメモリセルを用いたメモリシステムであれば適用することができる。例えば、フラッシュメモリ、ＤＲＡＭ、ＰＲＡＭ、ＲｅＲＡＭなどを用いたメモリシステムに適用することが可能である。
【符号の説明】
【０３４７】
１００・・・メモリ部、２００・・・ＥＣＣシステム、２０１・・・ｐ進数変換部、２０２・・・エンコード部、２０３・・・シンドローム生成部、２０４・・・解探索多項式生成部、２０５・・・ハッセ微分多項式生成、２０６・・・コード復元部、２０７・・・デコード部、２０８・・・バイナリ変換部。
【図１】
2011198253.tif 000052
【図２】
2011198253.tif 000053
【図３Ａ】
2011198253.tif 000054
【図３Ｂ】
2011198253.tif 000055
【図４Ａ】
2011198253.tif 000056
【図４Ｂ】
2011198253.tif 000057
【図５】
2011198253.tif 000058
【図６】
2011198253.tif 000059
【図７】
2011198253.tif 000060
【図８Ａ】
2011198253.tif 000061
【図８Ｂ】
2011198253.tif 000062
【図９Ａ】
2011198253.tif 000063
【図９Ｂ】
2011198253.tif 000064
【図１０Ａ】
2011198253.tif 000065
【図１０Ｂ】
2011198253.tif 000066
【図１１Ａ】
2011198253.tif 000067
【図１１Ｂ】
2011198253.tif 000068
【図１２Ａ】
2011198253.tif 000069
【図１２Ｂ】
2011198253.tif 000070
【図１３Ａ】
2011198253.tif 000071
【図１３Ｂ】
2011198253.tif 000072
【図１４Ａ】
2011198253.tif 000073
【図１４Ｂ】
2011198253.tif 000074
【図１５Ａ】
2011198253.tif 000075
【図１５Ｂ】
2011198253.tif 000076
【図１６】
2011198253.tif 000077
【図１７】
2011198253.tif 000078
【図１８】
2011198253.tif 000079
【図１９】
2011198253.tif 000080
【図２０】
2011198253.tif 000081
【図２１】
2011198253.tif 000082
【図２２】
2011198253.tif 000083
【図２３】
2011198253.tif 000084