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