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