(57)【要約】【課題】誤り位置検出多項式を演算するための回路の規模を縮小することができる、誤り検出訂正回路を提供する。【解決手段】本発明の誤り検出訂正回路は、データ列のビット毎に誤りが有るか否かを判定するチェン探索部を備えた誤り検出訂正回路であって、前記チェン探索部は、誤り位置検出多項式の各次数のうち線形性の認められない次数に乗ずる係数を非線形係数とし、前記誤り位置検出多項式を、線形性の認められる次数の項からなる第１の位置方程式と、線形性の認められない次数の項からなる第２の位置方程式とに分割し、前記代入値を、前記第１の位置方程式を前記非線形係数で除算した第３の位置方程式の各次数にそれぞれ代入し、前記第２の位置方程式を前記非線形係数で除算した第４の位置方程式に代入値を代入し、前記第３の位置方程式の結果と前記第４の位置方程式の結果との排他的論理和により、前記ビットに誤りがあるか否かを判定する。【選択図】図９
2014082574.tif 000002
【特許請求の範囲】
【請求項１】
ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）の任意の元を誤り位置検出多項式への代入値として、データ列のビット毎に誤りが有るか否かを判定するチェン探索部を備えた誤り検出訂正回路であって、
前記チェン探索部は、
誤り位置検出多項式の各次数のうち線形性の認められない次数に乗ずる係数を非線形係数とし、
前記誤り位置検出多項式を、線形性の認められる次数の項からなる第１の位置方程式と、線形性の認められない次数の項からなる第２の位置方程式とに分割し、
前記代入値を、前記第１の位置方程式を前記非線形係数で除算した第３の位置方程式の各次数にそれぞれ代入し、前記第２の位置方程式を前記非線形係数で除算した第４の位置方程式に代入値を代入し、前記第３の位置方程式の結果と前記第４の位置方程式の結果との排他的論理和により、前記ビットに誤りがあるか否かを判定する
ことを特徴とする誤り検出訂正回路。
【請求項２】
前記チェン探索部は、
前記ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される（２ｍ−１）個の元を前記第３の位置方程式へ代入して演算を行う際に、
前記（２ｍ−１）個の元のうちから、線形独立なｍ個の元を計算する基底計算部と、
前記（２ｍ−１）個の元のうちから前記ｍ個の元を除いた（２ｍ−１−ｍ）個の元を、それぞれ前記ｍ個の元の組合せとして求める線形展開部と、
を備えることを特徴とする請求項１に記載の誤り検出訂正回路。
【請求項３】
請求項１または請求項２に記載の誤り検出訂正回路を備えるメモリ装置であって、
前記誤り検出訂正回路は、
入力されるデータ列からシンドロームを計算するシンドローム計算部と、
前記シンドロームから前記誤り位置検出多項式の係数を算出する誤り係数計算部と、
前記データ列のデータのビット位置を示す値と、前記係数とを前記誤り位置検出多項式に代入して、前記データ列のビット毎に誤りが有るか否かを示すエラー検出信号を出力するチェン探索部と、
前記エラー検出信号により前記データ列におけるビットのデータの誤りを訂正して出力する誤り訂正部と、
を有することを特徴とするメモリ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り検出訂正回路、及び誤り検出訂正回路を内蔵したメモリ装置に関する。
【背景技術】
【０００２】
電気的書き換え可能な不揮発性半導体記憶装置（ＥＥＰＲＯＭ；Electrically  Erasable  and  Programmable  Read  Only  Memory）の一つとして、ＮＡＮＤ型フラッシュメモリが知られている。ＮＡＮＤ型フラッシュメモリは、複数のメモリセルを直列接続したＮＡＮＤセルユニット（ＮＡＮＤストリング）を用いることにより、小さいチップ面積での大容量記憶を可能としている。
【０００３】
ＮＡＮＤ型フラッシュメモリなどの大容量メモリでは、データ保持中などに様々な原因で記憶内容が壊れる。例えば、多数回の書き換えに伴うトンネル酸化膜の劣化等に起因して、データ保持中に記憶素子（メモリセル）の保持特性が失われ、エラービットの発生率（エラー率）が大きくなる傾向がある。特に、ＮＡＮＤ型フラッシュメモリでは、メモリ容量の大規模化と製造プロセスの微細化が進むとエラー率は上昇する傾向がある。
これに対処するために、誤り検出訂正回路（ＥＣＣ回路）がＮＡＮＤ型フラッシュメモリの性能向上のため使用されてきた。この誤り検出訂正回路をオンチップで搭載することにより、高信頼性メモリを提供することが可能になる。
【０００４】
なお、関連するガロア体演算回路がある（特許文献１を参照）。この特許文献１に記載のガロア体演算回路は、ガロア体ＧＦ（２ｍ）上のｍビットでベクトル表現される２つの元の乗算を行う際、乗算過程での下位ｍビット以外の上位ビットの成分についてそれぞれＥＸＯＲ演算して求め、その出力を、与えられる原始多項式ｆ（Ｘ）により、ｍビットのベクトル表現に変換し、下位ｍビットの成分とＥＸＯＲ演算することにより、乗算されたベクトル出力を得る。これにより、ガロア体上での乗算回路構成の簡略化を図る。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平６−３１４９７９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、ＢＣＨ符号やＲＳ符号で代表される線形ブロック符号を用いたエラー訂正処理において、最も時間がかかるのが、誤り位置検出多項式（エラー位置探索方程式）の零点を求める処理である。図１２は、ガロア体演算回路３４Ｂの構成を示す図である。一般的に上記零点を求める処理は、例えば、図１２に示すガロア体演算回路（４次多項式のガロア体演算回路）３４Ｂにおいて、誤り位置検出多項式Ｐ（Ｘ）の係数ｅ０，ｅ１，ｅ２，ｅ３，ｅ４が確定した後、ガロア体要素（元）Ｘとして、１，α，α２，α３，・・・，αｔ−２、（ただしｔ＝２ｍ）、を順次入力し、Ｐ（Ｘ）の零点を求める。この処理にかかる時間は、多項式の変数Ｘの取りうる値のすべてを一度に計算することで大幅に短縮できる。
【０００７】
図１３は、ガロア体演算回路３４Ｃの構成を示す図である。
例えば、図１３に示すガロア体演算回路３４Ｃのように、各要素１，α，α２，α３，・・・，αｔ−２のそれぞれについての並列演算回路を設け、Ｐ（１），Ｐ（α１），Ｐ（α２），・・・，Ｐ（αｔ−２）、（ただしｔ＝２ｍ）、を同時に演算することにより、誤り位置検出多項式における演算時間を大幅に短縮できる。しかしながら、図１３に示す方法では、誤り位置検出多項式を算出するための回路規模が非常に大きくなり、誤り検出訂正回路をメモリ装置にオンチップで搭載することが困難になる。
【０００８】
そこで本発明が解決しようとする課題は、誤り位置検出多項式を演算するための回路の規模を縮小することができる、誤り検出訂正回路、及びメモリ装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の誤り検出訂正回路は、ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）の任意の元を誤り位置検出多項式への代入値として、データ列のビット毎に誤りが有るか否かを判定するチェン探索部を備えた誤り検出訂正回路であって、前記チェン探索部は、誤り位置検出多項式の各次数のうち線形性の認められない次数に乗ずる係数を非線形係数とし、前記誤り位置検出多項式を、線形性の認められる次数の項からなる第１の位置方程式と、線形性の認められない次数の項からなる第２の位置方程式とに分割し、前記代入値を、前記第１の位置方程式を前記非線形係数で除算した第３の位置方程式の各次数にそれぞれ代入し、前記第２の位置方程式を前記非線形係数で除算した第４の位置方程式に代入値を代入し、前記第３の位置方程式の結果と前記第４の位置方程式の結果との排他的論理和により、前記ビットに誤りがあるか否かを判定することを特徴とする。
【００１０】
また、本発明の誤り検出訂正回路は、前記チェン探索部は、前記ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される（２ｍ−１）個の元を前記第３の位置方程式へ代入して演算を行う際に、前記（２ｍ−１）個の元のうちから、線形独立なｍ個の元を計算する基底計算部と、前記（２ｍ−１）個の元のうちから前記ｍ個の元を除いた（２ｍ−１−ｍ）個の元を、それぞれ前記ｍ個の元の組合せとして求める線形展開部と、を備えることを特徴とする。
【００１１】
また、本発明のメモリ装置は、上記の誤り検出訂正回路を備えるメモリ装置であって、前記誤り検出訂正回路は、入力されるデータ列からシンドロームを計算するシンドローム計算部と、前記シンドロームから前記誤り位置検出多項式の係数を算出する誤り係数計算部と、前記データ列のデータのビット位置を示す値と、前記係数とを前記誤り位置検出多項式に代入して、前記データ列のビット毎に誤りが有るか否かを示すエラー検出信号を出力するチェン探索部と、前記エラー検出信号により前記データ列におけるビットのデータの誤りを訂正して出力する誤り訂正部と、を有することを特徴とする。
【発明の効果】
【００１２】
本発明の誤り検出訂正回路は、誤り位置検出多項式を、誤り位置検出多項式の非線形の項の係数で除算するとともに、この係数で除算した誤り位置検出多項式を、線形項で統合して計算する。
これにより、誤り検出訂正回路において、誤り位置検出多項式を演算するための回路の規模を縮小することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態に係わるメモリ装置の全体構成を示す図である。
【図２】図１のＮＡＮＤ型フラッシュメモリにおける誤り検出訂正回路１３の構成例を示す図である。
【図３】原始多項式Ｆ（Ｘ）を「Ｆ（Ｘ）＝Ｘ４＋Ｘ＋１」としたときのガロア体ＧＦ（２４）の要素１（＝α０），α１，α２，・・・，α１４を表（表１）で示したものである。
【図４】原始多項式Ｆ（Ｘ）を「Ｆ（Ｘ）＝Ｘ３＋Ｘ＋１」としたときのガロア体ＧＦ（２３）の要素１（＝α０），α１，α２，・・・，α６を表（表２）で示したものである。
【図５】誤り位置検出多項式の線形統合の例を示す図である。
【図６】線形関数ｓ（Ｘ）の演算回路の例を示す図である。
【図７】データ長が３００ビットのデータに対して、ガロア体演算回路３００により、誤り位置検出多項式を演算する回路の例である。
【図８】線形関数ｓ’（Ｘ）の演算回路の例を示す図である。
【図９】本発明の実施形態に係わる誤り検出訂正回路１３内のデコーダ部３０の構成を示す図である。
【図１０】訂正ビット数に応じた係数の値を表により示したものである。
【図１１】２つの誤り位置検出多項式（ａ）及び（ｂ）の両方を同一回路で使用することができるガロア体演算回路３４Ａの構成例を示している。
【図１２】ガロア体演算回路３４Ｂの構成を示す図である。
【図１３】ガロア体演算回路３４Ｃの構成を示す図である。
【図１４】行列演算の例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態を添付図面を参照して説明する。
［概要］
従来のガロア体演算回路は、例えば、図１２に示す回路（４次多項式の回路）において、誤り位置検出多項式Ｐ（Ｘ）の係数ｅ０，ｅ１，ｅ２、ｅ３，ｅ４が確定した後、ガロア体要素（元）Ｘとして、１（＝α０），α（＝α１），α２，α３，・・・、を順次に入力し、Ｐ（Ｘ）の零点を求めている。
より具体的には、従来のガロア体多項式の零点を求めるガロア体演算回路３４Ｂでは、第１の手順として、係数ｅｉ（ｉ＝０，１，２，３，４）を計算し、第２の手順として、項ｅｉＸｉを計算し、第３手順として、ｉ＝０，１，２，３，４に対応する各項を足し合わせる。そして、上記第１、第２及び第３の手順を、取り得る全ての要素Ｘ（１，α，α２，α３，・・・）、あるいはその一部に対して行い、多項式Ｐ（Ｘ）の零点を求める。しかしながら、この方法では、ガロア体の要素１，α，α２，α３，・・・を順次入力してＰ（Ｘ）の零点を求めるため、零点を求めるのに非常に長い時間がかかる。
【００１５】
これに対処するために、多項式Ｐ（Ｘ）の零点を一度に求める回路（４次多項式の例）を用いることができる。例えば、図１３に示すガロア体演算回路３４Ｃに示すように、各要素１，α，α２，α３，・・・，αｔ−２、（ただしｔ＝２ｍ）、のそれぞれについての並列演算回路を設け、Ｐ（１），Ｐ（α１），Ｐ（α２），Ｐ（α３），・・・，Ｐ（αｔ−２）を同時に演算することにより、誤り位置検出多項式における演算時間を大幅に短縮できる。しかしながら、この図１３に示す方法では、取りうるすべてのＸに対するＰ（Ｘ）を一括で求めるため、零点を求めるのに時間はかからないが、回路規模が非常に大きくなる。
【００１６】
図１３に示すような回路構成において、各ユニットの各項に対応する部分は定数元を掛ける演算が線形演算であることから行列演算で表される。図１４は、行列演算の例を示す図である。例えば、図１４に示す行列演算の例を参照すると、演算に使用される行列は、ガロア体要素Ｘをベクトルとみなした際、これを他のベクトルに変換する行列である。そして、ガロア体ＧＦ（２ｍ）を採用した場合(ｍはガロア体要素をベクトルで示した場合のバイナリデータのビット数に相当)、行列演算部分に対応する回路は約ｍ（ｍ−１）／２個のＥＸＯＲ素子で構成される。そして、多項式の次数ｎのとき、これら行列演算の結果ｍビットをｎ＋１項分足し合わせるので、これにｍ×ｎ個のＥＸＯＲ素子が必要である。
【００１７】
Ｘが取りうる値の範囲をガロア体全体とすると、図１３のユニット数は２ｍ−１個であり、総計、
（ｎ＋１）×（２ｍ−１）×ｍ（ｍ−１）／２＋ｎ×(２ｍ−１）×ｍ、
となる。
例えば、ｍ＝８、ｎ＝４の場合は、総計約４３８００個のＥＸＯＲ素子が必要になる。このように、各項の演算を２入力の掛け算から行列演算に置き換えたとしても、回路規模が非常に大きくなる。
【００１８】
そこで、本実施形態のガロア体演算回路では、後述するように、例えば、誤り位置検出多項式「Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」を非線形項Ｘ３の係数ｅ３で割り、新たな誤り位置検出多項式「Ｐ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋Ｘ３＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ＋ｅ０／ｅ３」を求める。これより、Ｘ３は各ビット毎に固定値となり、また、ｅ０’は定数となる。
そして、さらに、この新たな誤り位置検出多項式Ｐ’（Ｘ）において、Ｘについての線形項を統合した線形関数「ｓ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ」を生成する。
【００１９】
そして、この線形関数ｓ’（Ｘ）を計算する場合に、後述する基底計算部１０１により、ガロア体ＧＦ（２ｍ）上の線形独立なｍ個の元に対して線形関数ｓ’（Ｘ）を計算し、上記の線形独立なｍ個の元を除いた残りの（２ｍ−１−ｍ）個の元に対する線形関数ｓ’（Ｘ）の計算については、線形展開部１０２により、基底計算部１０１における演算結果を展開（加算）して計算を行う。これにより、線形関数ｓ’（Ｘ）の計算回路が簡略化される。
このように、線形関数ｓ’（Ｘ）の計算回路が簡略化されるとともに、Ｘ３が固定値となるので、誤り検出訂正回路において、誤り位置検出多項式の多項式を演算する回路が簡略化され、その回路規模を縮小することができる。
このため、高速演算で誤り位置検出多項式の零点を求める誤り検出訂正回路を、半導体メモリに搭載可能な回路規模で実現できる。
【００２０】
［メモリ装置の構成］
図１は、本発明の実施形態に係わるメモリ装置の全体構成を示す図であり、メモリ装置として、不揮発性半導体記憶装置１０であるＮＡＮＤ型フラッシュメモリの全体構成を示した図である。
この不揮発性半導体記憶装置１０は、メモリセルアレイ１１、ページバッファ１２、誤り検出訂正回路（ＥＣＣ回路）１３、バッファ１４、Ｉ／Ｏパッド１５、制御回路１６、アドレスデコーダ１７、及びロウ及びブロックデコーダ１８を含んで構成される。
この不揮発性半導体記憶装置１０の構成は、一般的な構成のＮＡＮＤ型フラシュメモリと同様な構成のものであるが、本実施形態では、誤り検出訂正回路１３内に設けられるチェン探索部３３（図２）内のガロア体演算回路（誤り位置検出多項式の演算回路）３４に特徴がある。
【００２１】
以下、不揮発性半導体記憶装置１０の全体の構成について説明する。不揮発性半導体記憶装置１０において、メモリセルアレイ１１は、複数のスタックゲート構造のトランジスタ、すなわち電気的書き換え可能な不揮発性メモリセル（記憶素子）をカラム方向（列方向）に直列接続して、ビット線毎に設けられたＮＡＮＤセルストリングを、行方向（ビット線の配列方向）に複数個配置したブロックから構成される。このブロックは、ビット線の配線方向に複数個配置される。また、このブロックは、メモリセルのデータの消去単位で設けられている。各ブロックにおいては、同一行に配置された不揮発性メモリ各々のゲートには、ビット線に直交したワード線が接続される。
１本のワード線により選択される不揮発性メモリセルの範囲がプログラム及び読み出しの単位となる１ページである。
【００２２】
ページバッファ１２は、ページ単位のデータのプログラム及び読み出しを行うため、ビット線毎に設けられたページバッファ回路から構成されている。このページバッファ１２におけるページバッファ回路各々は、それぞれのビット線に接続され、接続されたビット線の電位を増幅して判定するセンスアンプ回路として用いるラッチ回路を有する。
【００２３】
ページバッファ１２は、不揮発性半導体記憶装置１０のデータ読み出し動作において、メモリセルアレイ１１の１ページ分のメモリセルが記憶するデータ（データビット列）からなるセルデータＣｅｌｌ  Ｄａｔａが入力され、このデータを増幅して誤り検出訂正回路１３に対して出力する。一方、ページバッファ１２は、不揮発性半導体記憶装置１０のデータ書込み（プログラム）動作において、誤り検出訂正回路１３から供給されるデータを内部のラッチ回路に格納し、ベリファイ動作を行いつつ、全てのデータを符号データＣｏｄｅ  Ｄａｔａとして１ページ内のメモリセルに書き込む。
【００２４】
この符号データＣｏｄｅ  Ｄａｔａには、誤り検出訂正回路１３が生成するパリティデータＰａｒｉｔｙが含まれる。
例えば、誤り位置検出多項式Ｐ（Ｘ）を「Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」とし、情報長３００ビツト（ｂｉｔ）に対しＢＣＨ符号を用いて４ビット訂正を行う誤り訂正システムを例に取るとき、３６ビットのパリティビットが用いられる。なお、Ｘは各３００ビットに割り振られた９ビット表記の値である。
【００２５】
誤り検出訂正回路１３は、不揮発性半導体記憶装置１０のデータ読み出し動作において、ページバッファ１２から読み出されたデータを、セクタ毎に処理して、誤り位置検出多項式の係数を算出し、内部にラッチして保持する。また、誤り検出訂正回路１３は、読み出し動作において、カラムアドレスにより位置が示されるビットのデータの誤りを訂正し、Ｉ／Ｏパッド１５を介して訂正済データＣｏｒｒｅｃｔｅｄ  Ｄａｔａとして外部へ出力する。
【００２６】
また、誤り検出訂正回路１３は、不揮発性半導体記憶装置１０のデータ書き込み動作において、Ｉ／Ｏパッド１５から入力される情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａを、バッファ１４を介して受け取る。誤り検出訂正回路１３は、受け取った情報データＩｎｆｏｒｍａｔｉｏｎ  ＤａｔａからパリティデータＰａｒｉｔｙを生成するとともに、受け取った情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａ、及びパリティデータＰａｒｉｔｙをページバッファ１２に対して出力する。ページバッファ１２は、これらのデータを符号データＣｏｄｅ  Ｄａｔａとして、選択されているページに接続されるメモリセルに書き込む。
【００２７】
制御回路１６は、各種制御信号が入力され、不揮発性メモリセルに対するデータのプログラム、読み出し、消去などの動作、及びベリファイの動作の制御を行う。
例えば、制御信号は、外部クロック信号、チップイネーブル信号／ＣＥ、読み出しイネーブル信号／ＲＥ、プログラムイネーブル信号／ＷＥ、コマンドラッチイネーブル信号ＣＬＥ、アドレスラッチイネーブル信号ＡＬＥ、ライトプロテクト信号／ＷＰなどである。制御回路１６は、これらの制御信号と、Ｉ／Ｏパッド１５から入力されるコマンドデータとが示す動作モードに応じて、各回路に対して内部制御信号を出力する。
例えば、制御回路１６は、プログラムイネーブル信号／ＷＥの立ち上がり時にコマンドラッチイネーブル信号ＣＬＥがロウ（Ｌ）レベルからハイ（Ｈ）レベルになることにより、Ｉ／Ｏパッド１５からコマンドデータを取り込み、内部のレジスタに保持する。
【００２８】
アドレスデコーダ１７は、Ｉ／Ｏパッド１５から入力されるアドレス（ロウアドレス、ブロックアドレス、カラムアドレス）を制御回路１６からの内部制御信号に基づいて保持する。また、アドレスデコーダ１７は、保持したアドレスを、制御回路１６からの内部制御信号に基づいて、ロウ及びブロックデコーダ１８、ページバッファ１２、及び誤り検出訂正回路１３へ出力する。
【００２９】
例えば、制御回路１６は、プログラムイネーブル信号／ＷＥの立ち上がり時にアドレスラッチイネーブル信号ＡＬＥがロウ（Ｌ）レベルからハイ（Ｈ）レベルになることにより、Ｉ／Ｏパッド１５からアドレスを取り込み、アドレスデコーダ１７の内部レジスタに保持する。
【００３０】
ロウ及びブロックデコーダ１８は、アドレスデコーダ１７が保持し、出力するロウアドレス、及びブロックアドレスに応じて、メモリセルアレイ１１のブロック、及びワード線の選択を行い、１ページ上のメモリセルを選択する。また、アドレスデコーダ１７は、内部に保持するカラムアドレスに応じて、メモリセルアレイ１１のビット線及びページバッファ１２の選択を行う。
【００３１】
誤り検出訂正回路１３は、不揮発性半導体記憶装置１０のデータ読み出し動作において、ページバッファ１２から読み出されたデータを、セクタ毎に処理して、誤り位置検出多項式の係数を算出する。また、誤り検出訂正回路１３は、読み出し動作において、カラムアドレスにより位置が示されるビット毎のデータの誤りを訂正し、Ｉ／Ｏパッド１５を介して訂正済データＣｏｒｒｅｃｔｅｄ  Ｄａｔａとして外部へ出力する。
【００３２】
また、誤り検出訂正回路１３は、不揮発性半導体記憶装置１０のデータ書き込み動作において、Ｉ／Ｏパッド１５から入力される情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａを、バッファ１４を介して受け取る。誤り検出訂正回路１３は、受け取った情報データＩｎｆｏｒｍａｔｉｏｎ  ＤａｔａからパリティデータＰａｒｉｔｙを生成するとともに、受け取った情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａ、及びパリティデータＰａｒｉｔｙをページバッファ１２に対して出力する。ページバッファ１２は、これらのデータを符号データＣｏｄｅ  Ｄａｔａとして、選択されているページに接続されるメモリセルに書き込む。
【００３３】
図２は、図１のＮＡＮＤ型フラッシュメモリにおける誤り検出訂正回路１３の構成例を示す図である。
図２に示す例は、誤り検出訂正回路１３として、ＢＣＨ符号（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ  ｃｏｄｅ）を用いた誤り検出訂正回路（ＥＣＣ回路）を例である。ＢＣＨ符号は、ガロア体演算を利用したブロック符号である。なお、ＢＣＨ符号の替りに、例えばＨａｍｍｉｎｇ符号（Ｈａｍｍｉｎｇ  ｃｏｄｅ）、リードソロモン符号（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅ）を用いることも可能である。
【００３４】
誤り検出訂正回路１３は、データの復号を司るデコーダ部３０と、訂正用パリティデータＰａｒｉｔｙを生成し、訂正用パリティデータＰａｒｉｔｙをセルへの書き込みデータに付加するエンコーダ部４０とを含んで構成される。
このうち、エンコーダ部４０は、パリティ生成回路４１を有する。パリティ生成回路４１は、バッファ１４に書き込まれた情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａを生成多項式で除算して得られるパリティデータＰａｒｉｔｙを生成する。また、パリティ生成回路４１は、情報データＩｎｆｏｒｍａｔｉｏｎ  Ｄａｔａに、生成したパリティデータＰａｒｉｔｙを付加して、ページバッファ１２に対して出力する。これらのデータは、不揮発性半導体記憶装置１０のデータ書き込み時において、選択された１ページに書き込まれる符号データＣｏｄｅ  Ｄａｔａとなる。
【００３５】
なお、本実施形態では、不揮発性半導体記憶装置１０からのデータ読み出し時において、誤り検出訂正回路１３が高速にデータ訂正処理を行うとともに、この誤り検出訂正回路１３内のチェン探索部３３（より正確にはガロア体演算回路３４）の回路規模を縮小できることに特徴を有するものであり、以下ではデコーダ部３０について詳細に説明する。
【００３６】
デコーダ部３０は、シンドローム計算部３１、誤り係数計算部３２、チェン探索部３３、及び誤り訂正部３５を含んで構成される。また、チェン探索部３３には、ガロア体演算回路３４が含まれる。
シンドローム計算部３１は、不揮発性半導体記憶装置１０のデータ読み出し時に、ページバッファ１２に読み出されたセルデータＣｅｌｌ  Ｄａｔａが、符号データとして入力され、この符号データを独立な最小多項式で除算することによりシンドロームを計算する。４ビットのデータの誤り訂正が可能なＢＣＨ符号で使用される独立な最小多項式は、４つである。シンドローム計算部３１は、これら４つの最小多項式に対応して、４つのシンドローム算出回路３１＿１〜３１＿４を備えている。これらのシンドローム算出回路３１＿１〜３１＿４は、それぞれシンドロームＳ１、Ｓ３、Ｓ５、Ｓ７を計算する。
【００３７】
誤り係数計算部３２は、これらのシンドロームＳ１、Ｓ３、Ｓ５、Ｓ７を使用して、誤り位置検出多項式の係数を計算する。例えば、誤り位置検出多項式が４次の多項式Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ１＋ｅ０である場合に、誤り係数計算部３２は、係数ｅ４、ｅ３、ｅ２、ｅ１、及びｅ０を計算する。そして、チェン探索部３３では、ガロア体演算回路３４により、誤り位置検出多項式Ｐ（Ｘ）を計算する。なお、この誤り位置検出多項式Ｐ（Ｘ）において、変数Ｘには、符号データ、つまりページバッファに格納されたセルデータＣｅｌｌ  Ｄａｔａのビット位置（例えば、ビット線の位置）を示す値（例えば、９ビット表記の値）が入力される。つまり、この誤り位置検出多項式Ｐ（Ｘ）は、ページバッファ１２から読み出されたビットに誤りがあるか否かを探索する際にチェン探索部３３において用いられる。
【００３８】
チェン探索部３３は、３００ビットのデータの各ビットに対して、ガロア体演算回路３４により、誤り位置検出多項式「Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ１＋ｅ０」を計算し、各ビットに対応するエラー検出信号ｂｃｈ［２９９：０］を生成して、このエラー検出信号ｂｃｈ［２９９：０］を誤り訂正部３５に出力する。例えば、チェン探索部３３は、Ｐ（Ｘ）の値が０である場合、検出信号ｂｃｈをＨレベルとして出力する。一方、Ｐ（Ｘ）の値が０でない場合、チェン探索部３３は、検出信号ｂｃｈをＬレベルとして出力する。
【００３９】
誤り訂正部３５は、例えば、エラー検出信号ｂｃｈがＨレベルであれば、対応する位置のビットのデータの論理（０または１）を反転して、訂正済データＣｏｒｒｅｃｔｅｄ  Ｄａｔａの１ビットとして出力する。一方、誤り訂正部３５は、エラー検出信号ｂｃｈがＬレベルであれば、対応する位置のビットのデータの論理をそのまま、つまり訂正しないで訂正済データＣｏｒｒｅｃｔｅｄ  Ｄａｔａの１ビットとして出力する。
【００４０】
上記構成の誤り検出訂正回路１３において、ガロア体演算回路３４は、後述するように、誤り位置検出多項式をＰ（Ｘ）を非線形項（例えば、ｅ３Ｘ３）の係数（例えば、ｅ３）で割る（除算する）ととともに、この係数で割った誤り位置検出多項式の演算を線形項と非線形項とに分けて演算することにより、誤り位置検出多項式の演算回路における回路規模の縮小を図っている。
ここで、最初に、ガロア体と多項式が持つ線形性について説明する。なお、以下の線形性の説明においては、図面の見易さと説明の分かりやすさのために、ガロア体ＧＦ（２ｍ）において、ｍ＝３（或いはｍ＝４）とし、誤り位置検出多項式の次数を４次（ｎ＝４）とした場合を例にとり説明するが、もちろん、次数ｍ及びｎは、誤り検出の対象となるデータのビット長と、誤り訂正ビット数とに応じて任意の値に設定されるものである。
【００４１】
［多項式が持つ線形性とガロア体がもつ線形構造］
ある関数Ｆ（Ｘ）が以下の２条件を満たすとき、Ｆ（Ｘ）はＸに対して線形であるという。
（条件１）Ｆ（Ｘ１＋Ｘ２）＝Ｆ（Ｘ１）＋Ｆ（Ｘ２）
（条件２）Ｆ（ａ・Ｘ１）＝ａ・Ｆ（Ｘ１）
【００４２】
例えば、Ｘがガロア体の要素ならば、Ｆ（Ｘ）＝Ｘ２はＸの線形関数である。なぜならば、Ｘ１，Ｘ２をガロア体の要素、また、ａ＝０，１とした時、
Ｆ（Ｘ１＋Ｘ２）＝（Ｘ１＋Ｘ２）２
＝Ｘ１２＋２Ｘ１・Ｘ２＋Ｘ２２
＝Ｘ１２＋Ｘ２２（∵ガロア体上での加算は排他的論理和であり、１＋１＝２＝０）
＝Ｆ（Ｘ１）＋Ｆ（Ｘ２）
となり、（条件１）を満たす。また、ａは、０あるいは１なので、（条件２）を満たすのは明らかである。同様に、ガロア体上で「１＋１＝０」であることから、Ｘ４，Ｘ８，Ｘ１６，・・・などＸを２のべき乗回だけ乗じる関数はガロア体上の線形関数であることが分かる。
【００４３】
ここで、ガロア体多項式の１次・２次・４次の項に着目し、これらの和を、
「Ｑ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ」、と置く。
このとき、Ｘ，Ｙをガロア体の要素として、
Ｑ（Ｘ＋Ｙ）＝ｅ４（Ｘ＋Ｙ）４＋ｅ２（Ｘ＋Ｙ）２＋ｅ１（Ｘ＋Ｙ）
＝ｅ４（Ｘ４＋Ｙ４）＋ｅ２（Ｘ２＋Ｙ２）＋ｅ１（Ｘ＋Ｙ）
（∵ガロア体上で２＝４＝０）
＝ｅ４Ｘ４＋ｅ４Ｙ４＋ｅ２Ｘ２＋ｅ２Ｙ２＋ｅ１Ｘ＋ｅ１Ｙ
＝（ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ）＋（ｅ４Ｙ４＋ｅ２Ｙ２＋ｅ１Ｙ）
＝Ｑ（Ｘ）＋Ｑ（Ｙ）
となり、上記（条件１）を満たす。また、（条件２）を満たすことは明らかであるので、Ｑ（Ｘ）はＸの線形関数である。
このように、「Ｑ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ」、はＸについて線形関数であることが分かる。
【００４４】
一方、他の項（Ｘ４，Ｘ２，Ｘ以外の項）に関しても、例えば、Ｘ３やＸ５などを変数とみなすことで、線形関数とみなすことが可能である。例えば、３次、６次、１２次の項に着目し、
Ｒ（Ｘ）＝ｅ１２Ｘ１２＋ｅ６Ｘ６＋ｅ３Ｘ３、と置けば、Ｒ（Ｘ）はＸ３の線形関数である。
【００４５】
次に、ガロア体がもつ線形構造について説明する。
図３は、原始多項式Ｆ（Ｘ）を「Ｆ（Ｘ）＝Ｘ４＋Ｘ＋１」としたときのガロア体ＧＦ（２４）の要素１（＝α０），α１，α２，・・・，α１４を表（表１）で示したものである。こここで、１，α，α２，α３の４要素（点線で囲んだ部分）に着目すると、これらは自分以外の要素の和で自分自身が決して表現されない線形独立な組であることが分かる。これらを基底ベクトルであると考えると、他の要素はこの基底ベクトルの線形結合で表現される。すなわち、「α４＋α１＋α０＝０」の関係を用いて、各要素０，α０（＝１），α１，α２，・・・，α１４は、α０，α，α２，α３を要素とする４次元ベクトル（０，０，０，０）〜（１，１，１，１）で表せる。
【００４６】
例えば、α４＝１＋α１、であり、
また、α１２＝α（α１＋α２＋α３）＝α２＋α３＋α４＝１＋α１＋α２＋α３、のように表わされる。
【００４７】
また、ここで、βｉ＝０，１（ｉ＝０，１，２，３）、と仮定すると、任意のガロア体要素は、αｊ＝β３α３＋β２α２＋β１α１＋β０α０，（ｊ＝０，１，２，・・・）と表わすことができ、ここで、（β３，β２，β１，β０）は、αｊに対応するベクトル表現である。
【００４８】
上記Ｑ（Ｘ）に対して、Ｑｊ＝Ｑ（αｊ），（ｊ＝０，１，２，・・・）と書くことにする。Ｑ（Ｘ）に、αｊ＝β３α３＋β２α２＋β１α１＋β０α０を代入すると、
Ｑｊ＝Ｑ（αｊ）・・・（ａ）
＝Ｑ（β３α３＋β２α２＋β１α１＋β０α０）
＝β３Ｑ（α３）＋β２Ｑ（α２）＋β１Ｑ（α１）＋β０Ｑ（α０）
（∵Ｑ（Ｘ）の線形性より）
＝β３Ｑ３＋β２Ｑ２＋β１Ｑ１＋β０Ｑ０・・・（ｂ）
を得る。従来、上記（ａ）式から、「Ｑｊ＝ｅ４α４＋ｅ２α２＋ｅ１α」として、各項を行列演算した結果をさらに加算する必要があったが、本実施形態では上記（ｂ）式を利用し、基底１（＝α０），α１，α２，α３に対応するＱ０，Ｑ１，Ｑ２，Ｑ３をあらかじめ行列演算で求めて、これらの単純加算で他のＱｊを求めることができる。
【００４９】
また、図４は、原始多項式Ｆ（Ｘ）を「Ｆ（Ｘ）＝Ｘ３＋Ｘ＋１」としたときのガロア体ＧＦ（２３）の要素１（＝α０），α１，α２，・・・，α６を表（表２）で示したものである。こここで、１，α，α２の３要素（点線で囲んだ部分）に着目すると、これらは自分以外の要素の和で自分自身が決して表現されない線形独立な組であることが分かる。これらを基底ベクトルであると考えると、他の要素はこの基底ベクトルの線形結合で表現される。すなわち、「α３＋α１＋α０＝０」の関係を用いて、各要素０，α０（＝１），α１，α２，・・・，α６は、α０，α，α２を要素とする３次元ベクトル（０，０，０）〜（１，１，１）で表すことができる。
【００５０】
［誤り位置検出多項式の線形性を利用する例］
上述したように、誤り位置検出多項式において、例えば、「ｓ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ」と置くと、多項式ｓ（Ｘ）はＸについての線形関数になる。この線形関数ｓ（Ｘ）の計算は、上述した多項式とガロア体の線形性を利用することにより、簡略化できる。ここでは、この線形関数ｓ（Ｘ）の演算の簡略化する例について説明する。なお、以下の説明では、図面の見易さと説明の分かり易さのために、ガロア体ＧＦ(２３)を例にとり、線形項を統合して演算する例について説明するが、任意のｍ次のガロア体ＧＦ（２ｍ）についても同様である。
図５は、誤り位置検出多項式の線形統合の例を示す図である。
図５（Ａ）に示すように、誤り位置検出多項式が４次の誤り位置検出多項式「Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」である場合に、図５（Ｂ）に示すように、誤り位置検出多項式Ｐ（Ｘ）の線形項を統合した線形関数「ｓ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ」を生成し、この線形関数ｓ（Ｘ）に対して演算を行う例について説明する。
【００５１】
図６は、線形関数ｓ（Ｘ）の演算回路の例を示す図である。この演算回路２００において、基底計算部２０１内の演算部Ｒ０は、要素Ｘ（１＝α０）に対する誤り位置検出多項式内の線形関数「ｓ（１）＝ｅ４１４＋ｅ２１２＋ｅ１１」を行列演算により算出する。演算部Ｒ１は、要素Ｘ（＝α１＝α）に対する線形関数「ｓ（α）＝ｅ４α４＋ｅ２α２＋ｅ１α」を行列演算により算出する。演算部Ｒ２は、要素Ｘ（＝α２）に対する線形関数「ｓ（α２）＝ｅ４（α２）４＋ｅ２（α２）２＋ｅ１α２」を行列演算により算出する。
【００５２】
そして、線形展開部２１０は、この基底計算部２０１により算出された演算結果ｓ（１），ｓ（α），ｓ（α２）を単純加算で展開して他の出力を得る。
例えば、ｓ（α３）は、図４のガロア体ＧＦ（２３）の表２に示すように、「α３＝α＋１」であるため、上述した線形性により、「Ｓ（α３）＝ｓ（α）＋ｓ（１）」で表すことができる。このため、ｓ（α３）は、ＥＸＯＲ素子（加算器）２１１により、基底計算部２０１の出力ｓ（１）とｓ（α）を加算することにより得られる。
【００５３】
また、ｓ（α４）は、図４のガロア体ＧＦ（２３）の表２に示すように、「α４＝α２＋α」であるため、上述した線形性により、「ｓ（α４）＝ｓ（α２）＋ｓ（α）」で表すことができる。このため、ｓ（α４）は、ＥＸＯＲ素子２１２により、基底計算部２０１の出力ｓ（α）とｓ（α２）を加算することにより得られる。
【００５４】
また、ｓ（α５）は、「α５＝α２＋α＋１」であり、また、「α４＝α２＋α」であるため、「α５＝α４＋１」となる。このため、ｓ（α５）はＥＸＯＲ素子２１３により、基底計算部２０１の出力ｓ（１）と、ＥＸＯＲ素子２１３の出力ｓ（α４）とを加算することにより得られる。
同様にして、ｓ（α６）は、「α６＝α２＋１」であるため、ｓ（α６）は、ＥＸＯＲ素子２１４により、基底計算部２０１の出力ｓ（１）とｓ（α２）とを加算することにより得られる。
【００５５】
このように、ガロア体ＧＦ（２３）の場合に、基底計算部２０１は、３個の線形独立な元（１，α、α２）に対して、この元に対応する３組の線形関数ｓ（１），ｓ（α１），ｓ（α２）を計算する。そして、線形展開部２１０は、線形関数ｓ（α３），ｓ（α４），ｓ（α５），ｓ（α６）を、基底計算部２０１におけるｓ（１），ｓ（α），ｓ（α２）の演算結果を基に、ＥＸＯＲ素子により加算して計算することができる。このように、演算回路２００では、要素Ｘの取りうる値の全組み合わせ数７から基底の個数３を引いた「４個」の誤り位置検出多項式（より正確には、線形関数ｓ（Ｘ））に対して、行列演算を単純加算に置き換えることで、回路規模を縮小することができる。
【００５６】
なお、図６に示す回路例では、３個の線形独立な基底の組として、図４の表２に示すように、ベクトル表現（００１），（０１０），（１００）の基底が用いられているが、必ずしも、このような１ビットのみが１となるベクトルを基底に選ぶ必要はなく、線形独立なベクトルの組でありさえすれば、どのような組み合わせであってもよい。
【００５７】
このように、演算回路２００では、誤り位置検出多項式において、同一の線形空間を構成する項を線形関数ｓ（Ｘ）として統合し、この統合した線形関数に対して、基底計算部２０１と線形展開部２１０とにより演算を行う。これにより、演算回路２００では、誤り位置検出多項式を演算する際に必要になる演算素子の規模を縮小することができる。
【００５８】
また、例えば、図７は、データ長が３００ビットのデータに対して、ガロア体演算回路３００により、誤り位置検出多項式を演算する回路の例である。
なお、このガロア体演算回路３００は、誤り位置検出多項式において線形項を統合する例を参考として示したものであり、本実施形態の誤り検出訂正回路１３において実際に使用されるガロア体演算回路３４は、後述するように、さらに誤り位置検出多項式を非線形の項の係数で割る処理が加わるものである。つまり、本実施形態の誤り検出訂正回路１３は、図７に示すガロア体演算回路３００をさらに改良した構成のガロア体演算回路３４を使用するものである。
【００５９】
図７に示す回路３００において、非線形部の演算回路（ＳＲＣ０）３０１は、「ｅ３Ｘ３＋ｅ０」を演算し、各ビット毎の演算結果ｉ［２９９：０］を出力する。また、線形部分の演算回路（ＳＲＣ１）３０２は、線形関数「ｓ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ」を演算し、各ビット毎の演算結果ｊ［２９９：０］を出力する。そして、加算回路３０３は、各ビット毎の演算結果の加算（ｚ０＝ｉ０＾ｊ０、・・・，ｚ２９９＝ｉ２９９＾ｊ２９９）を行い、演算結果ｂｃｈ［２９９：０］を出力する。本実施形態において、上術した「＾」は、排他的論理和演算を示す。
この回路の線形部分の演算回路３０２において、線形関数「ｓ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ」を演算する際に、図６に示した回路と同様に、基底計算部と線形展開部とを用いて線形関数ｓ（Ｘ）の演算を行うことにより、線形関数ｓ（Ｘ）を演算する際に必要になる回路の回路規模（演算素子の数）を縮小することができる
【００６０】
［誤り位置検出多項式を非線形項の係数で割る場合の例］
上述したように、ガロア体演算回路では、誤り位置検出多項式の線形項を統合することにより回路規模を縮小することができるが、本実施形態の誤り検出訂正回路では、さらに回路規模を縮小することができる。つまり、誤り位置検出多項式（例えば、Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０）を、非線形項の係数（例えば、ｅ３Ｘ３の係数ｅ３）で割る（除算する）ことにより、新たな誤り位置検出多項式を生成し、この新たな誤り位置検出多項式における線形項を統合して演算を行うことにより、さらに回路規模を縮小することができる。
【００６１】
以下、誤り位置検出多項式を非線形項の係数で除算する例について説明する。なお、以下の説明では、ガロア体ＧＦ（２３）の場合について説明する。
【００６２】
誤り位置検出多項式Ｐ（Ｘ）、非線形項の係数ｅ３で割ると誤り方程式は、
Ｐ’（Ｘ）＝ｓ’（Ｘ）＋Ｘ３+ｅ０’、
ここで、
ｓ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ、
＝（ｅ４’）Ｘ４＋（ｅ２’）Ｘ２＋（ｅ１’）Ｘ、
ｅ４’＝ｅ４／ｅ３、ｅ２’＝ｅ２／ｅ３、ｅ１’＝ｅ１／ｅ３、
ｅ０’＝ｅ０／ｅ３、である。
【００６３】
これにより、Ｐ’（Ｘ）の線形項を線形関数ｓ’（Ｘ）で統合して計算するととともに、Ｘ３の項がビット毎の固定値となり、また、ｅ０’は定数であるので、誤り位置検出多項式の多項式を演算する回路を１つで済ませることができる。このため、ガロア体演算回路の回路規模をさらに縮小することができる。
【００６４】
図８は、線形関数ｓ’（Ｘ）の演算回路の例を示す図であり、図６に示す回路と同様な回路である。この演算回路２００’において、基底計算部２０１’内の演算部Ｒ０は、要素Ｘ（１＝α０）に対する誤り位置検出多項式内の線形関数「ｓ’（１＝α０）＝ｅ４’１４＋ｅ２’１２＋ｅ１’１」を行列演算により算出する。演算部Ｒ１は、要素Ｘ（＝α１＝α）に対する線形関数「ｓ’（α）＝ｅ４’α４＋ｅ２’α２＋ｅ１’α」を行列演算により算出する。演算部Ｒ２は、要素Ｘ（＝α２）に対する線形関数「ｓ’（α２）＝ｅ４’（α２）４＋ｅ２’（α２）２＋ｅ１’（α２）」を行列演算により算出する。
そして、線形展開部２１０’は、この基底計算部２０１’により算出された演算結果ｓ’（１），ｓ’（α），ｓ’（α２）を、ＥＸＯＲ素子２１１〜２１４により単純加算で展開して他の出力を得る。
【００６５】
このように、図８に示す演算回路２００’では、誤り位置検出多項式Ｐ（Ｘ）を、非線形項の係数（例えば、ｅ３Ｘ３の係数ｅ３）で割って、新たな誤り位置検出多項式Ｐ’（Ｘ）を生成し、Ｘ３の項を固定値とする。そして、演算回路２００では、新たな誤り位置検出多項式Ｐ’（Ｘ）の線形項を統合して線形関数ｓ’（Ｘ）を生成し、この線形関数ｓ’（Ｘ）を基底計算部２０１’と線形展開部２１０’とを用いて演算する。これにより、ガロア体演算回路の回路規模を、さらに縮小することができる。
【００６６】
［本発明の実施形態に係わる誤り検出訂正回路１３の構成例］
以上、誤り位置検出多項式を演算する際に、誤り位置検出多項式を、非線形項の係数（例えば、ｅ３Ｘ３の係数ｅ３）で割り、新たな誤り位置検出多項式生成し、この新たな誤り位置検出多項式の線形項を統合して演算を行う場合の例と効果について説明した。
本実施形態における誤り検出訂正回路１３は、上述の誤り位置検出多項式を非線形項の係数で割る機能と、誤り位置検出多項式の線形項を統合して演算を行う機能の両方を有するチェン探索部３３（より正確にはガロア体演算回路３４）を備える。以下、本実施形態に係わる誤り検出訂正回路１３のチェン探索部３３の構成例について説明する。
【００６７】
図９は、本発明の実施形態に係わる誤り検出訂正回路１３内のデコーダ部３０の構成を示す図である。この図９に示す回路は、例えば、３００ビット（情報データ長２６４ビット＋パリティ３６ビット）をデータの訂正単位とし、その中の４ビットの誤りが訂正可能なＢＣＨ符号を用いた誤り検出訂正回路１３の例である。
この図９に示すデコーダ部３０では、チェン探索部３３内のガロア体演算回路３４において、誤り位置検出多項式Ｐ（Ｘ）を演算する際に、この誤り位置検出多項式Ｐ（Ｘ）を、非線形項の係数（ｅ３Ｘ３の係数ｅ３）で割る（除算する）ことにより、新たな誤り位置検出多項式Ｐ’（Ｘ）を生成し、この新たな誤り位置検出多項式Ｐ’（Ｘ）の線形項を統合して演算を行うものである。
【００６８】
この図９に示すデコーダ部３０において、チェン探索部３３内のガロア体演算回路３４は、誤り位置検出多項式Ｐ（Ｘ）として、例えば、
Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ１＋ｅ０、を演算する。
ここで、Ｘは、例えば、各３００ビットに割り振られた９ビット表記の値である。
【００６９】
また、このデコーダ部３０において、シンドローム計算回路３１は、３００ビットの情報データと所定の独立な最小多項式とを基にして、シンドロームＳ１，Ｓ３，Ｓ５，Ｓ７を生成する。また、誤り係数計算部３２は、シンドロームＳ１，Ｓ３，Ｓ５，Ｓ７を基にして誤り位置検出多項式の係数計算を行う。チェン探索部３３は、ガロア体演算回路３４により、誤り位置検出多項式Ｐ（Ｘ）の演算を行い、３００ビットの情報データにおけるデータの誤り位置を求める。
【００７０】
ここで、誤り位置検出多項式において、Ｘ，Ｘ２，Ｘ４，Ｘ８，Ｘ１６，・・・の項は、ガロア体の中で線形性が認められ、誤り位置検出多項式Ｐ（Ｘ）は、
Ｐ（Ｘ）＝ｓ（Ｘ）＋ｅ３Ｘ３＋ｅ０、と変形することができる。
ここで、ｓ（Ｘ）は線形関数であり、ｓ（Ｘ）＝ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ、である。
【００７１】
そして、誤り位置検出多項式Ｐ（Ｘ）、非線形項の係数ｅ３で割ると誤り方程式は、
Ｐ’（Ｘ）＝ｓ’（Ｘ）＋Ｘ３＋ｅ０’、
ここで、
ｓ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ、
ｅ０’＝ｅ０／ｅ３、である。
【００７２】
これにより、ｅ０’は全ビットに対して固定値、Ｘ３は、各ビット毎に固定値になるので、計算に必要な回路は、線形関数ｓ’（Ｘ）の項だけになる。
そして、「ｓ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ」は、Ｘについての線形関数であるので、ガロア体演算回路３４において、上述した図７に示した回路と同様な構成の回路により、基底計算部１０１と線形展開部１０２とを用いて演算することができる。
つまり、ガロア体演算回路３４内の線形部分の演算回路（ＳＲＣ）１００において、基底計算部１０１は、要素Ｘのうちの基底となる要素に対する線形関数ｓ’（Ｘ）を行列演算で計算し、線形展開部１０２は、基底計算部１０１の計算結果を展開（加算）して、基底を除く他の要素Ｘに対する線形関数の出力を得る。そして、ビット毎に固定値であるＸ３の値と、定数であるｅ０’とを、ｓ’（Ｘ）の計算値に加算することにより、誤り位置検出多項式の演算結果ｂｃｈ［２９９：０］が得られる。
【００７３】
このように、誤り位置検出多項式Ｐ（Ｘ）を非線形項の係数ｅ３で割ることで、Ｘ３は、各ビット毎に固定値、ｅ０’は全ビットに対して固定値となる。そして、この線形関数「ｓ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ」に対して、基底計算部１０１と線形展開部１０２とを用いて演算を行うことにより、ガロア体演算回路３４において、多項式の計算部分を線形部分の演算回路１００の１つにすることができる。これにより、ガロア体演算回路３４において、誤り位置検出多項式を演算する際に必要となる素子数を減らすことができる。
【００７４】
ところで、上述したように、誤り位置検出多項式を非線形係数ｅ３で割ることにより、ガロア体演算回路の回路規模を減らすことができる。図１０は、訂正ビット数に応じた係数の値を表により示したものである。図１０の表３（訂正ビット数に応じた係数の値）に示すように、通常の訂正条件の他にイレギュラーな条件（ｅ３＝０になる条件）が存在する。
つまり、この図１０の表に示すように、４ビット訂正回路における「１，３，４ビット訂正時」及び「２ビット訂正時」において、誤り係数ｅ４，ｅ３，ｅ２，ｅ１，ｅ０の生成条件が異なる。例えば、４ビット訂正回路における「１，３，４ビット訂正時」において、基底となるシンドロームＳ１が「Ｓ１＝０」または「Ｓ１≠０」のケースで、誤り係数ｅ４，ｅ３，ｅ２，ｅ１，ｅ０の生成条件が異なる。この例では、「１，３，４ビット訂正時」においてシンドロームＳ１が０になる時に、誤り係数計算部３２は、係数ｅ３が０になるようにして、誤り係数ｅ４，ｅ３，ｅ２，ｅ１，ｅ０を生成する。
【００７５】
このように、シンドロームＳ１が「Ｓ１＝０」または「Ｓ１≠０」のケースで、誤り係数ｅ４，ｅ３，ｅ２，ｅ１，ｅ０が分かれる条件を、一つの回路で満たすためには、訂正条件により誤り位置検出多項式を使い分けることが必要になる。
例えば、１，３，４ビット訂正時においてシンドローム「Ｓ１≠０（ｅ３≠０）」の時には、
誤り位置検出多項式Ｐ’（Ｘ）＝ｓ’（Ｘ）＋Ｘ３＋ｅ０’・・・・（ａ）、
を使用し、
また、１，３，４ビット訂正時においてシンドローム「Ｓ１＝０」及び２ビット訂正の時には、
誤り位置検出多項式Ｐ（Ｘ）＝ｓ（Ｘ）＋ｅ０・・・（ｂ）、
を使用する。
【００７６】
図１１は、２つの誤り位置検出多項式（ａ）及び（ｂ）の両方を同一回路で使用することができるガロア体演算回路３４Ａの構成例を示している。この図１１に示すガロア体演算回路３４Ａは、演算部（ＳＲＣ）４００により、多項式「ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１’Ｘ＋ｅ０’」を演算する。
この多項式「ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１’Ｘ＋ｅ０’」において、ｅ４’は、ｅ４／ｅ３を示し、ｅ２’は、ｅ２／ｅ３を示し、ｅ０’は、ｅ０／ｅ３を示している。
【００７７】
そして、演算部４００は、誤り検出対象となるデータの各３００ビットに対応して、多項式「ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１’Ｘ＋ｅ０’」を計算し、その計算結果ｚ０［８：０］〜ｚ２９９［８：０］を、対応する各ビット用回路４１０＿１〜４１０＿２９９に出力する。
【００７８】
なお、イレギュラーな条件（ｅ３＝０になる条件）の場合には、「ｅ４’，ｅ２’，ｅ１’，ｅ０’」を、各係数をｅ３で割らない元の値「ｅ４，ｅ２，ｅ１，ｅ０」に代えて、「ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」を計算し、その計算結果ｚ０［８：０］〜ｚ２９９［８：０］を、対応する各ビット用回路４１０＿１〜４１０＿２９９に出力する。
【００７９】
また、この演算部（ＳＲＣ）４００は、上述した基底計算部１０１と線形展開部１０２とを有しており、多項式「ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１’Ｘ＋ｅ０’」または多項式「ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」を演算する際に、線形項を統合して計算するように構成されている。
なお、以下の説明において、例えば、ｚ０［８：０］を示す場合に、ビット構成を示す記号［８：０］の部分を省略し、単にｚ０と記すことがある（他の信号ｈ１、ｈ２等についても同様）。
【００８０】
そして、ビット用回路４１０＿０〜４１０＿２９９には、信号ａｎｏ、信号ｚ０〜ｚ２９９、信号Ｘ３が入力される。
ビット用回路４１０＿０〜４１０＿２９９に入力される信号ａｎｏは、「シンドロームＳ１＝０」又は「２ビット訂正」時であることを示す信号であり、後述する式「ｈ１＝ｚ０」を選択するか、式「ｈ２＝ｚ０＾Ｘ３、（＾は排他的論理和を意味する）」を選択するかのトリガとなる信号である。例えば、信号ａｎｏがＬレベルの場合に、ｈ１が選択され、信号ａｎｏがＨレベルの場合に、ｈ２が選択される。
【００８１】
また、ビット用回路４１０＿０〜４１０＿２９９に入力される信号ｚ０〜ｚ２９９は、上述のように、演算部４００から出力される信号であり、多項式「ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１Ｘ＋ｅ０’」の計算値（９ビット信号）か、または多項式「ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」の計算値（９ビット信号）である。また、信号Ｘ３は、Ｘ３の計算値であり、例えば、信号ｚ０に対応するＸ３の値は、９ビット表記で「９’ｂ０００００＿０００１」となり、信号ｚ２９９に対応するＸ３の値は、９ビット表記で「９’ｂ１００１０＿１００１」となる。
【００８２】
そして、ビット用回路４１０＿０〜４１０＿２９９内において計算される式ｈ１は、Ｘ３（固定値）を組み込まない場合（ｅ３＝０の場合）における「ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ０」の値であり、ｈ２は、Ｘ３（固定値）を組み込む場合（ｅ３≠０の場合）における（ｅ４’Ｘ４＋Ｘ３＋ｅ２’Ｘ２＋ｅ０’」の値を示している。
例えば、ビット用回路４１０＿０において、「ｈ１＝ｚ０」であり、「ｈ２＝ｚ０＾９’０００００＿０００１」となる。
【００８３】
また、式「ｚ１＝〜（ｈ１［０］｜・・・・・｜ｈ１［８］）」において、ｚ１は、ｈ１［０］〜ｈ１「８」の各ビットのオア（ＯＲ）をとり、そのオアした信号を反転した信号である。また、式「ｚ２＝〜（ｈ２［０］｜・・・・・｜ｈ２［８］）」において、ｚ２は、ｈ２［０］〜ｈ２「８」の各ビットのオア（ＯＲ）をとり、そのオアした信号を反転した信号である。すなわち、ｚ１及びｚ２は、対応するビットに誤りがある場合に、１（Ｈレベル）となり、誤りがない場合に、０（Ｌレベル）となる。
【００８４】
また、式「ｂｃｈ［ｉ］＝ａｎｏ？ｚ１:ｚ２；」、（ｉ＝０〜２９９）。は、信号ａｎｏが「Ｘ３を組み込まないことを示す場合（ｅ３＝０の場合）」に、ｂｃｈ［ｉ］としてｚ１を選択し、信号ａｎｏが「Ｘ３を組み込むことを示す場合（ｅ３≠０の場合）」に、ｂｃｈ［ｉ］としてｚ２を選択することを示している。
【００８５】
このように、図１１に示すガロア体演算回路３４Ａでは、通常の訂正条件（ｅ３≠０になる条件）の場合と、イレギュラーな条件（ｅ３＝０になる条件）の場合とに応じて、誤り位置検出多項式を使い分けて演算を行うことができる。また、ガロア体演算回路３４Ａでは、通常の訂正条件（ｅ３≠０になる条件）の場合は、誤り位置検出多項式を非線形係数ｅ３で割り、ささらに線形項を統合することで、演算回路の回路規模を縮小することができる。
また、イレギュラーな条件（ｅ３＝０になる条件）の場合には、Ｘ３の項を無視するとともに、元の誤り位置検出多項式（係数ｅ３で割らない誤り位置検出多項式）の線形項を統合して計算することで、演算回路の回路規模を減らすことができる。
【００８６】
なお、上述した実施形態では、４ビット訂正用の誤り検出訂正回路１３を例にして説明を行ったが、４ビット訂正用の誤り検出訂正回路だけに留まらず、その他のビット数の誤り検出訂正回路に関しても、本実施形態の誤り検出訂正回路は適用可能である。
【００８７】
以上説明したように、本実施形態では、誤り位置検出多項式を非線形係数で割るとともに、誤り位置検出多項式の線形項を統合することにより、チェン探索部３３（より正確にはガロア体演算回路３４）の回路規模を小さくすることができる。これにより、高速演算が可能なチェン探索部３３を有する誤り検出訂正回路１３を、不揮発性半導体記憶装置１０に搭載することが可能となる。
【００８８】
以上本発明の実施形態について説明したが、ここで、本発明と上述した実施形態との対応関係について補足して説明する。すなわち、上記実施形態において、本発明におけるメモリ装置は、図１に示す不揮発性半導体記憶装置（ＮＡＮＤ型フラシュメモリＥＥＰＲＯＭ）１０が対応する。また、本発明における誤り検出訂正回路は、図２に示す誤り検出訂正回路１３が対応し、本発明におけるチェン探索部は、チェン探索部３３が対応する。また、本発明における基底計算部は、例えば、図２に示すガロア体演算回路３４内の基底計算部１０１が対応し、本発明における線形展開部は、線形展開部１０２が対応する。
また、本発明におけるシンドローム計算部は、図２に示すデコーダ部３０内のシンドローム計算部３１が対応し、本発明における誤り係数計算部は、誤り係数計算部３２が対応し、本発明における誤り訂正部は、誤り訂正部３５が対応する。
【００８９】
そして、上記実施形態において、誤り検出訂正回路１３は、ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）の任意の元を誤り位置検出多項式（例えば、Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０）への代入値（Ｘ）として、データ列のビット毎に誤りが有るか否かを判定するチェン探索部３３を備えた誤り検出訂正回路１３であって、チェン探索部３３は、誤り位置検出多項式の各次数のうち線形性の認められない次数（Ｘ３）に乗ずる係数（ｅ３）を非線形係数とし、誤り位置検出多項式を、線形性の認められる次数を含む第１の位置方程式（ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ）と、線形性の認められない次数を含む第２の位置方程式（ｅ３Ｘ３＋ｅ０）とし、上記代入値を、第１の位置方程式（ｅ４Ｘ４＋ｅ２Ｘ２＋ｅ１Ｘ）を上記非線形係数（ｅ３）で除算した第３の位置方程式（ｓ’Ｘ）の各次数にそれぞれ代入し、第２の位置方程式（ｅ３Ｘ３＋ｅ０）を上記非線形係数（ｅ３）で除算した第４の位置方程式（Ｘ３＋ｅ０’）に代入値を代入し、第３の位置方程式（ｓ’Ｘ）の結果と第４の位置方程式（Ｘ３＋ｅ０’）の結果との排他的論理和により、ビットに誤りがあるか否かを判定する。
このような構成の誤り検出訂正回路１３では、チェン探索部３３（より正確にはガロア体演算回路３４）において、例えば、誤り位置検出多項式「Ｐ（Ｘ）＝ｅ４Ｘ４＋ｅ３Ｘ３＋ｅ２Ｘ２＋ｅ１Ｘ＋ｅ０」を非線形項Ｘ３の係数ｅ３で割り、新たな誤り位置検出多項式「Ｐ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋Ｘ３＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ＋ｅ０／ｅ３」を求める。これより、Ｘ３の項はビット毎の固定値となり、また、ｅ０’は定数となる。
そして、さらに、この新たな誤り位置検出多項式Ｐ’（Ｘ）において、Ｘについての線形項を統合した線形関数「ｓ’（Ｘ）＝（ｅ４／ｅ３）Ｘ４＋（ｅ２／ｅ３）Ｘ２＋（ｅ１／ｅ３）Ｘ」を生成する。そして、この線形関数ｓ’（Ｘ）を計算する場合に、基底計算部１０１により、ガロア体ＧＦ（２ｍ）上の線形独立なｍ個の元に対して線形関数「ｓ’（Ｘ）＝ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１’Ｘ」を計算し、線形独立なｍ個の元を除いた残りの（２ｍ−１−ｍ）個の元に対する線形関数ｓ’（Ｘ）の計算については、線形展開部１０２により、基底計算部１０１における演算結果を加算して計算を行う。これにより、線形関数ｓ’（Ｘ）の計算回路が簡略化される。
このように、線形関数ｓ’（Ｘ）の計算回路が簡略化されるとともに、Ｘ３の項が固定値となるので、誤り位置検出多項式の多項式を演算する回路を簡略化することができ、誤り検出訂正回路１３において、誤り位置検出多項式の演算回路の回路規模を縮小することができる。このため、高速演算で誤り位置検出多項式の零点を求める誤り検出訂正回路１３を、半導体メモリ（不揮発性半導体記憶装置１０）に搭載可能な回路規模で実現できる。
【００９０】
また、上記実施形態において、チェン探索部３３は、ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される（２ｍ−１）個の元を前記第３の位置方程式（ｓ’Ｘ）へ代入して演算を行う際に、（２ｍ−１）個の元のうちから、線形独立なｍ個の元を計算する基底計算部１０１と、（２ｍ−１）個の元のうちから上記ｍ個の元を除いた（２ｍ−１−ｍ）個の元を、それぞれ上記ｍ個の元の組合せとして求める線形展開部１０２と、を備える。
このような構成の誤り検出訂正回路１３であれば、チェン探索部３３は、基底計算部１０１と線形展開部１０２とを有している。基底計算部１０１は、ガロア体ＧＦ（２ｍ）上の線形独立なｍ個の元に対して線形関数「ｓ’（Ｘ）＝ｅ４’Ｘ４＋ｅ２’Ｘ２＋ｅ１’Ｘ」を計算する。そして、線形展開部１０２は、線形独立なｍ個の元を除いた残りの（２ｍ−１−ｍ）個の元に対する線形関数ｓ’（Ｘ）の計算について、基底計算部１０１における演算結果を展開（加算）して計算を行う。
これにより、誤り検出訂正回路１３は、チェン探索部３３において、線形項を統合した線形関数ｓ’（Ｘ）を計算する場合に、この線形関数ｓ’（Ｘ）を計算する際に必要となる回路の回路規模を縮小することができる。
【００９１】
また、上記実施形態において、メモリ装置（不揮発性半導体記憶装置１０）は、上記の誤り検出訂正回路１３を備えるメモリ装置（不揮発性半導体記憶装置１０）であって、誤り検出訂正回路１３は、入力されるデータ列からシンドロームを計算するシンドローム計算部３１と、シンドロームから誤り位置検出多項式の係数を算出する誤り係数計算部３２と、データ列のデータのビット位置を示す値と、上記係数とを誤り位置検出多項式に代入して、データ列のビット毎に誤りが有るか否かを示すエラー検出信号を出力するチェン探索部３３と、エラー検出信号によりデータ列におけるビットのデータの誤りを訂正して出力する誤り訂正部３５と、を有する。
このような構成のメモリ装置（不揮発性半導体記憶装置１０）では、チェン探索部３３において、誤り位置検出多項式を演算する際に、誤り位置検出多項式Ｐ（Ｘ）を非線形項Ｘ３の係数ｅ３で割り、新たな誤り位置検出多項式Ｐ’（Ｘ）を求める。そして、さらに、この新たな誤り位置検出多項式Ｐ’（Ｘ）において、Ｘについての線形項を統合した線形関数ｓ’（Ｘ）を生成して計算する。
これにより、メモリ装置（不揮発性半導体記憶装置１０）に搭載する誤り検出訂正回路１３の回路規模を縮小することができる。このため、メモリ装置（不揮発性半導体記憶装置１０）は、高速演算が可能な誤り検出訂正回路１３をオンチップで搭載することができる。
【００９２】
以上、この発明の実施形態を、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００９３】
１０…不揮発性半導体記憶装置、１１…メモリセルアレイ、１２…        ページバッファ、１３…誤り検出訂正回路、１４…バッファ、１５…Ｉ／Ｏパッド、１６…制御回路、１７…アドレスデコーダ、１８…ロウ及びブロックデコーダ、３０…デコーダ部、３１…シンドローム計算部、３２…誤り係数計算部、３３…チェン探索部、３４，３４Ａ…ガロア体演算回路、３５…誤り訂正部、４０…エンコーダ部、４１…パリティ生成回路、１００…線形部分の演算回路、１０１…基底計算部、１０２…線形展開部
【図１】
2014082574.tif 000003
【図２】
2014082574.tif 000004
【図３】
2014082574.tif 000005
【図４】
2014082574.tif 000006
【図５】
2014082574.tif 000007
【図６】
2014082574.tif 000008
【図７】
2014082574.tif 000009
【図８】
2014082574.tif 000010
【図９】
2014082574.tif 000011
【図１０】
2014082574.tif 000012
【図１１】
2014082574.tif 000013
【図１２】
2014082574.tif 000014
【図１３】
2014082574.tif 000015
【図１４】
2014082574.tif 000016