(57)【要約】【課題】複数ビットの誤り判定処理を並列して行う場合に回路規模の増大を小さく抑えることができる誤り検出訂正回路を提供する。【解決手段】ガロア体ＧＦ（２ｎ）の任意の元を誤り位置探索方程式への代入値として用い、データ列のビット毎に誤りが有るか否かを判定するチェン探索部３３を備えた誤り検出訂正回路であって、チェン探索部３３は、複数の元に対して、ｎ−ｋビットの値を乗じることで第１のビット列ｄｐｊを算出するとともに、ｋビットの値を乗じることで第２のビット列ｄｑｋを算出する回路５２及び５４と、第１のビット列と第２のビット列とを連結して任意の元を算出し、誤り位置探索方程式へ代入する複数のチェン探索回路５７とを備え、複数のチェン探索回路５７は行方向及び列方向にマトリクス状に配置され、第１のビット列が行方向に、第２のビット列が列方向に沿って、それぞれ供給される。【選択図】図３
2014057202.tif 000002
【特許請求の範囲】
【請求項１】
ガロア体ＧＦ（２ｎ）の任意の元を誤り位置探索方程式への代入値として用い、データ列のビット毎に誤りが有るか否かを判定するチェン探索部を備えた誤り検出訂正回路であって、
前記チェン探索部は、
所定の複数の前記元に対して、（ｎ−ｋ）ビットの所定の値を乗じることで第１のビット列を算出するとともに、ｋビットの所定の値を乗じることで第２のビット列を算出する計算回路と、
前記計算回路から入力される前記第１のビット列と前記第２のビット列とを連結して任意の前記元を算出し、前記誤り位置探索方程式へ代入する複数のチェン探索回路と、
を備え、
前記複数のチェン探索回路は行方向及び列方向にマトリクス状に配置され、
前記第１のビット列が、行方向または列方向のいずれか一方に、前記第２のビット列が行方向または列方向の他方に沿って、それぞれ供給される、
ことを特徴とする誤り検出訂正回路。
【請求項２】
前記チェン探索回路が、前記データ列のビット数以上の複数個設けられている
ことを特徴とする請求項１に記載の誤り検出訂正回路。
【請求項３】
請求項１又は２記載の誤り検出訂正回路と、
メモリセルと、
前記メモリセルから読み出した前記データ列を一時保持し、前記誤り検出訂正回路に供給するデータ格納部と
を備えることを特徴とする半導体メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り検出訂正回路及び半導体メモリに関する。
【背景技術】
【０００２】
ＮＡＮＤ  Ｆｌａｓｈ  Ｍｅｍｏｒｙ（ＮＡＮＤ型フラッシュ・メモリ）などの大容量メモリでは、データ保持中などに様々な原因で記憶内容が壊れる可能性がある。また、メモリ容量の大規模化と製造プロセスの微細化が進むとエラー率は上昇する傾向がある。これに対処するために、エラー訂正回路（ＥＣＣ；Ｅｒｒｏｒ  Ｃｈｅｃｋ  ａｎｄ  Ｃｏｒｒｅｃｔｉｏｎ）がＦｌａｓｈ  Ｍｅｍｏｒｙの性能向上のため使用されてきた。ＥＣＣシステムをオンチップで搭載することにより、高信頼性メモリを提供することが可能になる。一方で  ＥＣＣシステムでの訂正処理が終了するまでデータを外部に出力できず、この時間を短縮することが求められる。
【０００３】
これを解決する為に、処理時間の早いＨａｍｍｉｎｇ符号（ハミング符号）の使用及び高次の訂正が出来るＢＣＨ（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍｃｏｄｅ）符号の高速化が検討されている。ＢＣＨ符号は、ガロア体演算を利用したブロック符号の一つである。ＢＣＨ符号や、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ（リード・ソロモン）符号等のブロック符号では、誤り位置探索方程式を用いることで誤り位置を算出することができる。誤り位置の探索は、例えば、誤り位置探索方程式に０以外のガロア体の各元を順次代入し、方程式の根を探索することで行う。この根の探索は、チェン探索（Ｃｈｉｅｎ  ｓｅａｒｃｈ）と呼ばれている。このチェン探索の高速化に係る技術が例えば、特許文献１、特許文献２等に記載されている。
【０００４】
特許文献１、特許文献２等に記載されている技術では、フリップフロップあるいはレジスタ、乗算回路等を用いて誤り位置探索方程式を表すチェン探索回路が構成されている。そして、ビットの位置を示す信号をチェン探索回路に入力することによって、そのビットに誤りが有るか否かを判定している。その際、チェン探索回路を複数設けることで、複数のビットの誤りの有無を並列に判定していた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−４４８５３号公報
【特許文献２】特開２００１−２０３５８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１、特許文献２等に記載されている技術では、並列処理するビット数が増えると、チェン探索回路の個数が増加する。そして、チェン探索回路の個数が増加すると、それに伴いチェン探索回路にビットの位置を示す信号等を供給するための配線の本数も増大する。このため、並列処理するビット数を増やそうとすると、チェン探索回路とその周辺回路とからなるチェン探索部の回路規模が大きくなってしまうという課題があった。
【０００７】
本発明は、上記の課題を考慮してなされたものであり、複数ビットの誤り判定処理を並列して行う場合に回路規模の増大を小さく抑えることができる誤り検出訂正回路及び半導体メモリを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明の誤り検出訂正回路は、ガロア体ＧＦ（２ｎ）の任意の元を誤り位置探索方程式への代入値として用い、データ列のビット毎に誤りが有るか否かを判定するチェン探索部を備えた誤り検出訂正回路であって、前記チェン探索部は、所定の複数の前記元に対して、（ｎ−ｋ）ビットの所定の値を乗じることで第１のビット列を算出するとともに、ｋビットの所定の値を乗じることで第２のビット列を算出する計算回路と、前記計算回路から入力される前記第１のビット列と前記第２のビット列とを連結して任意の前記元を算出し、前記誤り位置探索方程式へ代入する複数のチェン探索回路と、を備え、前記複数のチェン探索回路は行方向及び列方向にマトリクス状に配置され、前記第１のビット列が、行方向または列方向のいずれか一方に、前記第２のビット列が行方向または列方向の他方に沿って、それぞれ供給される、ことを特徴とする。
【０００９】
また、本発明の他の態様は、前記チェン探索回路が、前記データ列のビット数以上の複数個設けられていることを特徴とする。
【００１０】
また、本発明の半導体メモリは、上記の誤り検出訂正回路と、メモリセルと、前記メモリセルから読み出した前記データ列を一時保持し、前記誤り検出訂正回路に供給するデータ格納部とを備えることを特徴とする。
【発明の効果】
【００１１】
本発明では、ガロア体ＧＦ（２ｎ）の任意の元のｎ次ベクトル表示をｎビットのビット列とみなした場合に、当該ビット列に、（ｎ−ｋ）ビットの所定の値を乗じることで第１のビット列を算出するとともに、ｋビットの所定の値を乗じることで第２のビット列を算出する。チェン探索回路は、ビットの位置を示す信号を、第１のビット列と第２のビット列との連結により得る。さらに、マトリックス状に列方向及び行方向に配置されたチェン探索回路に対して共通に、第１、または第２のビット列を与えることができるため、チェン探索回路毎にビットの位置を示す信号を供給するための配線を設ける必要がなくなる。そのため、チェン探索回路へビットの位置を示す信号を供給するための配線の本数を削減でき、チェン探索部の回路規模を小さくできる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態としての不揮発性半導体記憶装置（半導体メモリ）の構成例を説明するためのブロック図である。
【図２】図１に示した誤り検出訂正回路１３の構成例を説明するためのブロック図である。
【図３】図２に示したチェン探索部３３の構成例を説明するためのブロック図である。
【図４】図３に示したＳ  Ｃａｌｃｕｌａｔｏｒ５１の出力信号（ａ）、Ｐ  Ｃａｌｃｕｌａｔｏｒ５２の出力信号（ｂ）及びＱ  Ｃａｌｃｕｌａｔｏｒ５４の出力信号（ｃ）を説明するための説明図である。
【図５】図３に示したチェン探索回路５７の構成を説明するためのブロック図である。
【図６】図５に示した誤り位置探索方程式算出部７２の構成例を説明するためのブロック図である。
【図７】図３に示したチェン探索部３３の処理内容を説明するための図表である。
【図８】図３に示したチェン探索部３３の処理内容を説明するための図表である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の一実施の形態について説明する。図１は、本発明の一実施形態としての不揮発性半導体記憶装置１０であるＮＡＮＤ型フラッシュメモリの構成例を示す概略ブロック図である。不揮発性半導体記憶装置１０は、メモリセルアレイ１１、ページバッファ１２、誤り検出訂正回路１３、バッファ１４、Ｉ／Ｏパッド１５、制御回路１６、アドレスデコーダ１７、及びロウ及びブロックデコーダ１８を含んで構成される。
【００１４】
メモリセルアレイ１１は、複数のスタックゲート構造のトランジスタ、すなわち電気的書き換え可能な不揮発性メモリセル（記憶素子）をカラム方向（列方向）に直列接続して、ビット線毎に設けられたＮＡＮＤセルストリングを、行方向（ビット線の配列方向）に複数個配置したブロックから構成される。このブロックは、ビット線の配線方向に複数個配置される。また、このブロックは、メモリセルのデータの消去単位で設けられている。各ブロックにおいては、同一行に配置された不揮発性メモリ各々のゲートには、ビット線に直行したワード線が接続される。１本のワード線により選択される不揮発性メモリセルの範囲がプログラム及び読み出しの単位となる１ページである。
【００１５】
ページバッファ１２は、ページ単位のデータのプログラム及び読み出しを行うため、ビット線毎に設けられたページバッファ回路から構成されている。このページバッファ１２におけるページバッファ回路各々は、それぞれのビット線に接続され、接続されたビット線の電位を増幅して判定するセンスアンプ回路として用いるラッチ回路を有する。ページバッファ１２（データ格納部）は、不揮発性半導体記憶装置１０のデータ読み出し動作において、メモリセルアレイ１１の１ページ分のメモリセルが記憶するデータ（データ列）からなるセルデータＣｅｌｌ  Ｄａｔａが入力され、このデータを増幅して誤り検出訂正回路１３に対して出力する。一方、ページバッファ１２は、不揮発性半導体記憶装置１０のデータ書込み（プログラム）動作において、誤り検出訂正回路１３から供給されるデータを内部のラッチ回路に格納し、ベリファイ動作を行いつつ、全てのデータを符号データＣｏｄｅ  Ｄａｔａとして１ページ内のメモリセルに書き込む。この符号データＣｏｄｅ  Ｄａｔａには、誤り検出訂正回路１３が生成するパリティデータＰａｒｉｔｙが含まれる。
【００１６】
なお、本実施形態では、誤り検出訂正回路１３が、ＧＦ（２９）のガロア体を利用し、情報データ長２５６ｂｉｔを含むデータ列を訂正単位とし、その中の４ｂｉｔの誤りが訂正可能なＢＣＨ符号を用いることとする。この場合、訂正単位毎のパリティデータのビット長は３６ｂｉｔである。したがって、符号化されたデータ列は、２９２ｂｉｔ＋（他の付加ビットのビット長）のデータ長を有する。本実施形態では、一例として、符号化データ列のデータ長が３２０ｂｉｔであるとする。なお、本実施形態は、ＢＣＨ符号に限定されず、ガロア体演算を利用したブロック符号（ＢＣＨ符号・Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号）に活用することが可能である。
【００１７】
誤り検出訂正回路１３は、詳細については後述するが、不揮発性半導体記憶装置１０のデータ読み出し動作において、ページバッファ１２から読み出されたデータを、訂正単位毎に処理して、誤り位置探索方程式の係数を算出し、内部のラッチに保持する。また、誤り検出訂正回路１３は、読み出し動作において、カラムアドレスにより位置が示されるビットのデータの誤りを訂正し、Ｉ／Ｏパッド１５を介して訂正済データＣｏｒｒｅｃｔｅｄ  Ｄａｔａとして外部へ出力する。なお、Ｉ／Ｏパッド１５と誤り検出訂正回路１３との間に入出力回路を設けて、この入出力回路を介して外部へデータを出力してもよい。
【００１８】
また、誤り検出訂正回路１３は、不揮発性半導体記憶装置１０のデータ書き込み動作において、Ｉ／Ｏパッド１５から入力される情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａを、バッファ１４を介して受け取る。誤り検出訂正回路１３は、受け取った情報データＩｎｆｏｒｍａｔｉｏｎ  ＤａｔａからパリティデータＰａｒｉｔｙを生成するとともに、受け取った情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａ、及びパリティデータＰａｒｉｔｙをページバッファ１２に対して出力する。ページバッファ１２は、これらのデータを符号データＣｏｄｅ  Ｄａｔａとして、選択されているページに接続されるメモリセルに書き込む。
【００１９】
制御回路１６は、各種制御信号が入力され、不揮発性メモリセルに対するデータのプログラム、読み出し、消去などの動作、及びベリファイの動作の制御を行う。例えば、制御信号は、外部クロック信号、チップイネーブル信号／ＣＥ、読み出しイネーブル信号／ＲＥ、プログラムイネーブル信号／ＷＥ、コマンドラッチイネーブル信号ＣＬＥ、アドレスラッチイネーブル信号ＡＬＥ、ライトプロテクト信号／ＷＰなどである。制御回路１６は、これらの制御信号と、Ｉ／Ｏパッド１５から入力されるコマンドデータとが示す動作モードに応じて、各回路に対して内部制御信号を出力する。例えば、制御回路１６は、プログラムイネーブル信号／ＷＥの立ち上がり時にコマンドラッチイネーブル信号ＣＬＥがロウ（Ｌ）レベルからハイ（Ｈ）レベルになることにより、Ｉ／Ｏパッド１５からコマンドデータを取り込み、内部のレジスタに保持する。
【００２０】
アドレスデコーダ１７は、Ｉ／Ｏパッド１５から入力されるアドレス（ロウアドレス、ブロックアドレス、カラムアドレス）を制御回路１６からの内部制御信号に基づいて保持する。また、アドレスデコーダ１７は、保持したアドレスを、制御回路１６からの内部制御信号に基づいて、ロウ及びブロックデコーダ１８、ページバッファ１２、及び誤り検出訂正回路１３へ出力する。例えば、制御回路１６は、プログラムイネーブル信号／ＷＥの立ち上がり時にアドレスラッチイネーブル信号ＡＬＥがロウ（Ｌ）レベルからハイ（Ｈ）レベルになることにより、Ｉ／Ｏパッド１５からアドレスを取り込み、アドレスデコーダ１７の内部レジスタに保持する。
【００２１】
ロウ及びブロックデコーダ１８は、アドレスデコーダ１７が保持し、出力するロウアドレス、及びブロックアドレスに応じて、メモリセルアレイ１１のブロック、及びワード線の選択を行い、１ページ上のメモリセルを選択する。
また、アドレスデコーダ１７は、内部に保持するカラムアドレスに応じて、メモリセルアレイ１１のビット線及びページバッファ１２の選択を行う。
【００２２】
本実施形態において、データ読み出し動作においては、ページバッファ１２内のセルデータＣｅｌｌ  Ｄａｔａが誤り検出訂正回路１３に読み出され、誤り位置探索方程式の係数が訂正単位毎に計算される。そして、訂正単位毎に計算された係数と、誤り位置を表す信号（すなわち、ガロア体ＧＦ（２９）の各元を表すデータ）とに応じて、誤り位置を表す信号によって位置が示されるビットのデータに誤りがあるか否かが検出され、誤りがある場合は訂正されて、訂正済データＣｏｒｒｅｃｔｅｄ  ＤａｔａとしてＩ／Ｏパッド１５から出力される（詳細後述）。
【００２３】
また、データ書き込み動作においては、バッファ１４にいったんページバッファ１２内に格納されたセルデータＣｅｌｌ  Ｄａｔａが読み出される。バッファ１４は、例えばＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）により構成される。
バッファ１４では、セルデータＣｅｌｌ  Ｄａｔａのうち、入力されるカラムアドレスに対応する部分のデータが、Ｉ／Ｏパッド１５からのデータＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａに書き換えられる。また、誤り検出訂正回路１３では、バッファ１４の書き換え後のデータを含む１訂正単位分のデータに対応したパリティデータが算出される。そして、これらのパリティデータを含む符号化されたデータが、符号データＣｏｄｅ  Ｄａｔａとして、ページバッファ１２を介して選択されているページに書き込まれる。
【００２４】
次に、図２は、誤り検出訂正回路１３の詳細な構成例を示す図である。誤り検出訂正回路１３は、データの復号を司るデコーダ部２１と、訂正用パリティデータＰａｒｉｔｙを生成し、訂正用パリティデータＰａｒｉｔｙをセルへの書き込みデータに付加するエンコーダ部２２とを含んで構成される。
このうち、エンコーダ部２２は、パリティ生成回路４１を有する。パリティ生成回路４１は、バッファ１４に書き込まれた情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａを生成多項式で除算して得られるパリティデータＰａｒｉｔｙを生成する。また、パリティ生成回路４１は、情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａに、生成したパリティデータＰａｒｉｔｙを付加して、ページバッファ１２に対して出力する。これらのデータは、不揮発性半導体記憶装置１０のデータ書き込み時において、選択された１ページに書き込まれる符号データＣｏｄｅ  Ｄａｔａとなる。なお、本実施形態では、不揮発性半導体記憶装置１０からのデータ読み出し時において、誤り検出訂正回路１３がレイアウトサイズを縮小する上で効率的な構成を用いてデータ訂正処理を行うことに特徴を有するものであり、以下ではデコーダ部２１について詳細に説明する。
【００２５】
デコーダ部２１は、シンドローム算出回路３１、誤り係数算出回路３２、チェン探索部３３及び誤り訂正回路３４を含んで構成される。シンドローム算出回路３１は、符号データ列Ｃｏｄｅ  Ｄａｔａ  Ｙを訂正単位毎に入力し、この符号データ列を独立な最小多項式で除算することにより複数のシンドロームを計算する。本実施形態においては、４ビットのデータの誤り訂正が可能なＢＣＨ符号で使用される。したがって、独立な最小多項式は、４つである。そのため、シンドローム算出回路３１は、４つのシンドロームＳ１、Ｓ３、Ｓ５、及びＳ７を計算する。
【００２６】
誤り係数算出回路３２は、これらのシンドロームを使用して、訂正単位毎の誤り位置探索方程式Λ（ｘ）の係数ｅ４、ｅ３、ｅ２、ｅ１、及びｅ０を計算する。係数ｅ４、ｅ３、ｅ２、ｅ１、及びｅ０は、図２（ｂ）に示した誤り位置探索方程式Λ（ｘ）＝ｅ４ｘ４＋ｅ３ｘ３＋ｅ２ｘ２＋ｅ１ｘ１＋ｅ０の係数である。この誤り位置探索方程式Λ（ｘ）は、ページバッファ１２から訂正単位毎に読み出されたビットに誤りがあるか否かを探索する際にチェン探索部３３において用いられる。
【００２７】
チェン探索部３３は、誤り係数算出回路３２から入力した係数ｅ４、ｅ３、ｅ２、ｅ１、及びｅ０を入力として、訂正単位毎にエラー検出を行い、エラーが検出された場合に、そのビット位置を表す信号Ｚ［３１９：０］を出力する。信号Ｚ［３１９：０］は、各ビット位置に対応する誤り位置探索方程式の値を表す３２０ビットのデータである。各１ビットの信号Ｚ［０］、Ｚ［１］、…、Ｚ［３１９］がそれぞれ０番目、１番目、…、３１９番目のビット位置のデータの誤りの有無を表す（ここで０番目のビットが最下位ビットである）。本実施形態では、信号Ｚ［ｉ］の値が「１」となるｉビットが誤り、「０」となるｉビットが誤りなしであることを示す。
【００２８】
誤り訂正回路３２は、信号Ｚ［３１９：０］で表される誤りビットが４ビット以内の場合に（すなわちＺ［ｉ］＝１となるｉが４個以内の場合に）、符号データ列Ｃｏｄｅ  Ｄａｔａ  Ｙの中で誤りが検出された位置のビットの値を反転する。
【００２９】
次に、図３を参照して、図２に示したチェン探索部３３の構成例について説明する。図３に示したように、チェン探索部３３は、Ｓ  Ｃａｌｃｕｌａｔｏｒ（Ｓ算出部）５１、Ｐ  Ｃａｌｃｕｌａｔｏｒ（Ｐ算出部）５２、Ｐ  Ｌａｔｃｈ（Ｐラッチ部）５３、Ｑ  Ｃａｌｃｕｌａｔｏｒ（Ｑ算出部）５４、Ｑ  Ｌａｔｃｈ（Ｑラッチ部）５５、及びチェン探索回路群５６を含んでいる。チェン探索回路群５６は、複数のチェン探索回路５７を含んでいる。複数のチェン探索回路５７は、チェン探索回路群５６において行方向及び列方向にマトリクス状に配置されている。この場合、複数のチェン探索回路５７は、１６行３２列で（すなわち縦方向に１６個、横方向に３２個で格子状に並んで）配列されている。ただし、チェン探索回路５７は、行と列のすべての交点あるいは交差点（この場合、１６×３２＝５１２個の点）に設ける必要は無く、符号化データ列のデータ長（すなわち使用しているビット数）に合わせて適宜省略することができる。
【００３０】
各チェン探索回路５７は、図５に示したように構成することができる。図５は、図３に示したチェン探索回路５７の構成例を示したブロック図である。図５に示したチェン探索回路５７は、代入値算出部７１と、誤り位置探索方程式算出部７２とを含んでいる。代入値算出部７１は、Ｐ  Ｌａｔｃｈ５３から供給されたビット列信号ｄｐｊ（ｊ＝０〜３１のいずれか１つ）と、Ｑ  Ｌａｔｃｈ５５から供給されたビット列信号ｄｑｋ（ｋ＝０〜１５のいずれか１つ）とを入力し、両者を加算することで（すなわち、ｄｐｊ＋ｄｑｋを計算して）、図２（ｂ）に示した誤り位置探索方程式Λ（ｘ）のｘに代入するガロア体の元αｉ（ｉ＝０、１、２、…、５１１（＝２９−１）のうちのいずれか１つ）を算出する。
【００３１】
図５に示した誤り位置探索方程式算出部７２は、代入値算出部７１から供給された元αｉと、Ｓ  Ｃａｌｃｕｌａｔｏｒ５１から供給された誤り位置探索方程式の係数ｅ４、ｅ３、ｅ２、ｅ１、及びｅ０とに基づいて、誤り位置探索方程式Λ（ｘ）に元αｉを代入し、誤り位置探索方程式Λ（ｘ）の値を算出する。すなわち、ｘ＝αｉとして、誤り位置探索方程式Λ（ｘ）を算出する。ここで、Ｚ［３１９：０］のｉ番目のビットの値Ｚ［ｉ］は、Λ（αｉ）＝０の場合に「１」、Λ（αｉ）≠０の場合に「０」に設定される。
【００３２】
なお、誤り位置探索方程式算出部７２は、例えば、図６に示したようにして構成することができる。図６は、図５に示した誤り位置探索方程式算出部７２の構成例を示したブロック図である。図６に示した誤り位置探索方程式算出部７２は、ｅ１（αｉ）＋ｅ０算出部８１、ｅ２（αｉ）２算出部８２、ｅ３（αｉ）３算出部８３、ｅ４（αｉ）４算出部８４及びＺ［ｉ］算出部８５を含んでいる。ｅ１（αｉ）＋ｅ０算出部８１は、元αｉ、係数ｅ１及びｅ０を入力し、ｅ１（αｉ）＋ｅ０を算出する。ｅ２（αｉ）２算出部８２は、元αｉ及び係数ｅ２を入力し、ｅ２（αｉ）２を算出する。ｅ３（αｉ）３算出部８３は、元αｉ及び係数ｅ３を入力し、ｅ３（αｉ）３を算出する。ｅ４（αｉ）４算出部８４は、元αｉ及び係数ｅ４を入力し、ｅ４（αｉ）４を算出する。そして、Ｚ［ｉ］算出部８５は、ｅ１（αｉ）＋ｅ０算出部８１、ｅ２（αｉ）２算出部８２、ｅ３（αｉ）３算出部８３及びｅ４（αｉ）４算出部８４の出力を入力し、ｅ４（αｉ）４＋ｅ３（αｉ）３＋ｅ２（αｉ）２＋ｅ１（αｉ）＋ｅ０を算出する。Ｚ［ｉ］算出部８５は、さらに、算出した値が０であるか否かを判定し、判定結果に基づいてＺ［３１９：０］のｉ番目のビットの値Ｚ［ｉ］をΛ（αｉ）＝０の場合に「１」、Λ（αｉ）≠０の場合に「０」に設定して出力する。なお、ｅ２（αｉ）２算出部８２、ｅ３（αｉ）３算出部８３やｅ４（αｉ）４算出部８４は、例えば、複数の乗算器から構成することができる。この場合、１クロック周期で各算出値を求めることができる。
【００３３】
Ｓ  Ｃａｌｃｕｌａｔｏｒ５１は、誤り係数算出回路３２から係数ｅ４、ｅ３、ｅ２、ｅ１、及びｅ０を入力してそのまま各チェン探索回路５７に対して出力する。また、Ｓ  Ｃａｌｃｕｌａｔｏｒ５１は、各チェン探索回路５７がチェン探索の際に誤り位置探索方程式Λ（ｘ）に代入する値を作成する場合に使用されるＧＦ（２９）の元の一部を生成し、信号Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５、Ｓ６、Ｓ７及びＳ８として出力する。
【００３４】
ここで、図７を参照して、Ｓ  Ｃａｌｃｕｌａｔｏｒ５１が出力する信号Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５、Ｓ６、Ｓ７及びＳ８について説明する。図７は、ガロア体ＧＦ（２９）の元の一部を記述した図表である。図７に示したように、各元は、べき表現、多項式表現及びベクトル表現で表すことができる。図７から分かるように、ＧＦ（２９）（ｍ＝９）のガロア体では、べき表現の１（＝α０）、α１、α２、…、αｍ−１（＝α８）の９個の元が、ベクトル表現において９ビットの各ビットのうちのいずれか１つのビットが「１」となる値を有している。ここで、べき表現でα０、α１、α２、…、α８の９個の元のベクトル値は、９’ｂ００００００００１、９’ｂ０００００００１０、９’ｂ００００００１００、９’ｂ０００００１０００、９’ｂ００００１００００、９’ｂ０００１０００００、９’ｂ００１００００００、９’ｂ０１０００００００、及び９’ｂ１００００００００である。したがって、ＧＦ（２９）のすべての元αｉ（ｉ＝０、１、２、…、２ｍ−１（＝５１１））は、α０、α１、α２、…、α８の９個の元の複数の個の組み合わせ（すなわち互いに加算した結果によって）表すことができる。
【００３５】
例えば、誤り位置探索方程式Λ（ｘ）に代入した場合に、ビット９に対応する元α９は、下式にて生成することができる。
【００３６】
α９＝１＋α４
【００３７】
同様に、α１０、…、α５１１のすべての値は、上述した９個の元α０、α１、α２、…、α８を組み合わせることで求められる。
【００３８】
Ｓ  Ｃａｌｃｕｌａｔｏｒ５１は、図４（ａ）に示したように、これらのα０、α１、α２、…、α８の９個の元の値を生成し、信号Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５、Ｓ６、Ｓ７及びＳ８として出力する。信号Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５、Ｓ６、Ｓ７及びＳ８は、それぞれ９ビットの信号である。
【００３９】
本実施形態のチェン探索回路５７は、上述したように、代入値算出部５７によって加算処理により代入値αｉを算出するとともに、誤り位置探索方程式算出部７２によってその値を代入することで位置探索方程式Λ（ｘ）の値を算出する。したがって、各チェン探索回路５７は、仮に９個の元α０、α１、α２、…、α８を表す信号が供給されたとすれば、すべての元α０、…、α５１１のなかから任意の元αｉを求めることができる。よって各チェン探索回路５７は、任意の元α０、…、α５１１に対する誤り位置探索方程式Λ（ｘ）の値を算出することが可能となる。ただし、この場合には、各チェン探索回路５７に対して、９個の元α０、α１、α２、…、α８を表す信号をすべて供給しなければならない。しかしながら、各チェン探索回路５７のすべてが、９個の元α０、α１、α２、…、α８を表す信号すべてを使うわけではない。不要な信号の供給は、不要な配線の設置を意味することになる。そこで、図３を参照して説明した構成では、この不要な配線を少なくするため、９個の元α０、α１、α２、…、α８を表す信号を基底値とし、これらの基底値を２組（Ｐ−Ｐａｒｔと、Ｑ−Ｐａｒｔとする）の信号群に組み分けし、さらに準基底値と呼ぶ値を用いて各組の信号群を３２又は１６に分類した後（すなわち５１２分類した後）、各組１分類の信号を各チェン探索回路５７へ供給している。このようにすることで、各チェン探索回路５７では、所定の各１つの元αｉのみが算出可能となる。しかしながら、仮に９個の元α０、α１、α２、…、α８を表す信号をすべて供給する場合には９ビット×９で８１ビットの信号線が用いられるのに対して、本実施形態では、チェン探索回路５７に対して互いに直交する２個の９ビットの信号線（合計１８ビットの信号線）を用いるだけで任意の元αｉを算出することができる。
【００４０】
準基底値は、図８（ａ）及び（ｂ）に示したように、Ｐ−Ｐａｒｔの５ビット（すなわちＧＦ（２９）の９−４＝５ビット）の値ｐ０〜ｐ３１と、Ｑ−Ｐａｒｔの４ビットの値ｑ０〜ｑ１５とを含んでいる。ここで、Ｐ−Ｐａｒｔは図８（ａ）に示したように、ｘ＝９’ｂ０００００＿００００、９’ｂ００００１＿００００、９’ｂ０００１０＿００００、…、９’ｂ１１１１１＿００００のように、ｘの上位５ｂｉｔに相当する基底値（α４、α５、α６、α７、α８）に対応させた値である。一方、Ｑ−Ｐａｒｔは９ｂｉｔのｘの下位４ｂｉｔに相当する基底値（α０、α１、α２、α３）に対応させた値である。本実施形態では、これらの準基底値を用いて生成した２組のビット列信号ｄｐｊとｄｑｋとを組み合わせることで、各チェン探索回路５７において９個の元α０、α１、α２、…、α８に加え、残りの元α９、…、αｔ−１（ただし、ｔ＝２ｍ）を生成している。２組のビット列信号ｄｐｊとｄｑｋは、Ｐ  Ｃａｌｃｕｌａｔｏｒ５２と、Ｑ  Ｃａｌｃｕｌａｔｏｒ５４とで算出される。
【００４１】
Ｐ  Ｃａｌｃｕｌａｔｏｒ５２は、各９ビットの信号Ｓ４、Ｓ５、Ｓ６、Ｓ７及びＳ８に基づいて、図４（ｂ）に示した計算式を用いて、各９ビットのビット列信号ｄｐ０、ｄｐ１、ｄｐ２、…、ｄｐ３０及びｄｐ３１を生成して出力する。例えば、信号ｄｐ１は、図８（ａ）に示した準基底値ｐ１のビット４（「１」）を信号Ｓ４の各ビットに乗算した結果、ビット５（「０」）を信号Ｓ５の各ビットに乗算した結果、ビット６（「０」）を信号Ｓ６の各ビットに乗算した結果、ビット７（「０」）を信号Ｓ７の各ビットに乗算した結果及びビット８（「０」）を信号Ｓ８の各ビットに乗算した結果を、加算した結果として求められる。また、信号ｄｐ２は、図８（ａ）に示した準基底値ｐ２のビット４（「０」）を信号Ｓ４の各ビットに乗算した結果、ビット５（「１」）を信号Ｓ５の各ビットに乗算した結果、ビット６（「０」）を信号Ｓ６の各ビットに乗算した結果、ビット７（「０」）を信号Ｓ７の各ビットに乗算した結果及びビット８（「０」）を信号Ｓ８の各ビットに乗算した結果を、加算した結果として求められる。Ｐ  Ｃａｌｃｕｌａｔｏｒ５２で算出された信号ｄｐ０、ｄｐ１、ｄｐ２、…、ｄｐ３０及びｄｐ３１は、Ｐ  Ｌａｔｃｈ５３へ入力される。Ｐ  Ｌａｔｃｈ５３は、クロックスキュー調整のため、所定のクロック信号に同期してラッチした信号ｄｐ０、ｄｐ１、ｄｐ２、…、ｄｐ３０及びｄｐ３１を出力する。Ｐ  Ｌａｔｃｈ５３から出力された信号ｄｐ０、ｄｐ１、ｄｐ２、…、ｄｐ３０及びｄｐ３１は、列方向に敷設された各９ビットの３２組の信号線群を介して複数のチェン探索回路５７に供給される。
【００４２】
Ｑ  Ｃａｌｃｕｌａｔｏｒ５４は、各９ビットの信号Ｓ０、Ｓ１、Ｓ２及びＳ３に基づいて、図４（ｂ）に示した計算式に基づいて、各９ビットのビット列信号ｄｑ０、ｄｑ１、ｄｑ２、…、ｄｑ１４及びｄｑ１５を出力する。例えば、信号ｄｑ１は、図８（ｂ）に示した準基底値ｑ１のビット３（「０」）を信号Ｓ３の各ビットに乗算した結果、ビット２（「０」）を信号Ｓ２の各ビットに乗算した結果、ビット１（「０」）を信号Ｓ１の各ビットに乗算した結果、及びビット０（「１」）を信号Ｓ０の各ビットに乗算した結果を、加算した結果として求められる。また、信号ｄｑ２は、図８（ｂ）に示した準基底値ｑ２のビット３（「０」）を信号Ｓ３の各ビットに乗算した結果、ビット２（「０」）を信号Ｓ２の各ビットに乗算した結果、ビット１（「１」）を信号Ｓ１の各ビットに乗算した結果、及びビット０（「０」）を信号Ｓ０の各ビットに乗算した結果を、加算した結果として求められる。Ｑ  Ｃａｌｃｕｌａｔｏｒ５４で算出された信号ｄｑ０、ｄｑ１、ｄｑ２、…、ｄｑ１４及びｄｑ１５は、Ｑ  Ｌａｔｃｈ５５へ入力される。Ｑ  Ｌａｔｃｈ５５は、クロックスキュー調整のため、所定のクロック信号に同期してラッチした信号ｄｑ０、ｄｑ１、ｄｑ２、…、ｄｑ１４及びｄｑ１５を出力する。Ｑ  Ｌａｔｃｈ５５から出力された信号ｄｑ０、ｄｑ１、ｄｑ２、…、ｄｑ１４及びｄｑ１５は、行方向に敷設された各９ビットの１６組の信号線群を介して複数のチェン探索回路５７に供給される。
【００４３】
なお、ビット列信号ｄｐｊやビット列信号ｄｑｋの構成は上記のものに限定されない（ｊ＝０〜３１、ｋ＝０〜１５）。すなわち、ビット列信号ｄｐｊとビット列信号ｄｑｋの配線方向を行と列とで逆にしたり、ビット列信号ｄｐｊやビット列信号ｄｑｋの配線本数を変更したりすることができる。すなわち、本実施形態では、複数のチェン探索回路５７が行方向及び列方向にマトリクス状に配置され、ビット列信号ｄｐｊが、行方向または列方向のいずれか一方に、ビット列信号ｄｑｋが行方向または列方向の他方に沿って、それぞれ供給されるようにしている。
【００４４】
ＧＦ（２ｍ）のガロア体を採用した場合、ｎ個の誤りを訂正する回路は、チェン探索で、誤り位置探索方程式Λ（ｘ）＝ｅｎｘｎ＋…＋ｅ２ｘ２＋ｅ１ｘ＋ｅ０の変数ｘに対し、ＧＦ（２ｍ）の各元αｉ（ｉ＝０、１、２、…、２ｍ−１）を代入し、Λ（ｘ）＝０か否かを判定する。すなわち、元α０、α１、α２、…、αｔ−１（ただし、ｔ＝２ｍ）の各値を代入して誤り位置探索方程式Λ（ｘ）の値を算出する。従来の構成では、誤り位置探索方程式Λ（ｘ）を算出する１つの回路に、順次、各元αｉ（ｉ＝０、１、２、…、２ｍ−１）を代入することで誤り位置探索方程式Λ（ｘ）の値を１サイクルで元１つ分算出していた。これに対し、特許文献１や特許文献２に記載されている構成では、チェン探索を並列して動作させることで、例えば、２つの元に対する値を並列して同時に計算することができる。
【００４５】
一方、上述した本実施形態のチェン探索部３３では、各元αｉ（ｉ＝０、１、２、…、２ｍ−１）の値を、複数のチェン探索回路５７のいずれかに供給している。すなわち、本実施形態によれば、各元αｉ（ｉ＝０、１、２、…、２ｍ−１）を代入した場合の誤り位置探索方程式Λ（ｘ）の値を、複数のチェン探索回路５７を用いて一括して算出することが可能となる。
【００４６】
また、本実施形態では、複数のチェン探索回路５７をマトリクス状に配列し、誤り位置探索方程式Λ（ｘ）に対して代入する複数の値を２組に分割し、各組の値を行方向と列方向との直交する２方向から別々に供給している。そのため、チェン探索回路５７の配置と値の分割とを適切に選択することで、各代入値を供給する配線を直線的に（すなわち最短で）配線することが可能となる。
【００４７】
なお、本発明の実施の形態は上記のものに限定されず、例えば、情報ビット数やパリティビット数を変更したり、ブロック図で示した構成の各ブロックをさらに分割したり、複数のブロックを統合したりする変更を適宜行うことができる。
【００４８】
また、本発明の誤り検出訂正回路の適用範囲は、半導体メモリに限定されない。例えば、種々の記録媒体に情報を記録して読み出す場合等に使用することができる。
【符号の説明】
【００４９】
１０…不揮発性半導体記憶装置、１１…メモリセルアレイ、１２…ページバッファ、１３…誤り検出訂正回路、１４…バッファ、１５…Ｉ／Ｏパッド、１６…制御回路、１７…アドレスデコーダ、１８…ロウ及びブロックデコーダ、２１…デコーダ部、３１…シンドローム算出回路、３２…誤り係数算出回路、３３…チェン探索部、３４…誤り訂正回路、４１…パリティ生成回路、５１…Ｓ  Ｃａｌｃｕｌａｔｏｒ、５２…Ｐ  Ｃａｌｃｕｌａｔｏｒ、５３…Ｐ  Ｌａｔｃｈ、５４…Ｑ  Ｃａｌｃｕｌａｔｏｒ、５５…Ｑ  Ｌａｔｃｈ、５６…チェン探索回路群、５７…チェン探索回路、７１…代入値算出部、７２…誤り位置探索方程式算出部
【図１】
2014057202.tif 000003
【図２】
2014057202.tif 000004
【図３】
2014057202.tif 000005
【図４】
2014057202.tif 000006
【図５】
2014057202.tif 000007
【図６】
2014057202.tif 000008
【図７】
2014057202.tif 000009
【図８】
2014057202.tif 000010