(57)【特許請求の範囲】
【請求項１】
エラー検出訂正回路が搭載された半導体記憶装置において、
前記エラー検出訂正回路は、複数ビットのエラー訂正が可能な巡回符号を用いたものであって、エラー訂正可能な最大ビット数対応の次数を持つ情報多項式の中から、情報ビットとして利用する次数が、シンドローム多項式の計算規模が可及的に小さくなるように選択されている
ことを特徴とする半導体記憶装置。
【請求項２】
前記エラー検出訂正回路は、ガロア体ＧＦ（２ｍ）によるｔ（≧２）ビットエラー訂正ＢＣＨ符号を用いるものであり、その使用ビット長の中から、複数のシンドローム多項式の計算に用いる既約剰余多項式の係数“１”の総和が少ない順に並べた次数から、所定個数の次数が情報ビット用として選択される
ことを特徴とする請求項１記載の半導体記憶装置。
【請求項３】
前記エラー検出訂正回路は、ガロア体ＧＦ（２８）による２ビットエラー訂正ＢＣＨ符号を用いるものであり、その使用ビット長２５５の中から、二つのシンドローム多項式の計算に用いる既約剰余多項式の係数“１”の総和が少ない順に並べた１４４の次数が、１６個の検査ビット用及び１２８個の情報ビット用として選択される
ことを特徴とする請求項１記載の半導体記憶装置。
【請求項４】
前記エラー検出訂正回路の中のエラー位置検索回路は、
シンドローム多項式Ｓ１（ｘ），Ｓ３（ｘ）の係数データが出力される第１のデータバスと、
第１のデータバスの係数データにより１４４個が選択され、エラービット対応の剰余ｐｎ（ｘ）とシンドローム多項式Ｓ１（ｘ），Ｓ３（ｘ）との間で選択された１４４の要素に対応するｐｎ（ｘ）Ｓ１（ｘ）なる第１の演算と、シンドローム多項式のみの演算である（Ｓ１（ｘ））２＋Ｓ３（ｘ３）／Ｓ１（ｘ）なる第２の演算とが同時並行して行われる２５５個の演算部と、
これらの演算部のうち第２の演算の演算結果を出力する第２のデータバスと、
第２のデータバス上のデータと前記演算部の第１の演算の演算結果との間で和演算を行う１４４個のパリティチェック部と、
これらのパリティチェック部の演算結果とｐ２ｎ（ｘ）とを比較して一致するエラービット位置ｎを求めるデコード部とを有する
ことを特徴とする請求項３記載の半導体記憶装置。
【請求項５】
前記エラー検出訂正回路の中のエラー訂正回路は、
前記エラー位置検索回路の中の各第１の演算の演算結果と第２のデータバス上の係数Ｓ１（ｘ）２とＳ３（ｘ）／Ｓ１（ｘ）との間の和演算を行う３ビットパリティチェック回路と、
この３ビットパリティチェック回路の演算結果に応じて読み出しデータビットを反転させる反転回路とを有する
ことを特徴とする請求項４記載の半導体記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、半導体記憶装置に係り、特にオンチップのエラー検出訂正システムに関する。
【背景技術】
【０００２】
電気的書き換え可能な不揮発性半導体メモリであるフラッシュメモリは、書き換え回数の増加に従ってエラー率が大きくなる。特に、大容量化と微細化が進むと、エラー率は上昇する。このため、フラッシュメモリチップ内に或いはこれを制御するメモリコントローラにＥＣＣ（Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅ）回路を搭載することが行われる（例えば、特許文献１参照）。
【０００３】
フラッシュメモリを利用するホストデバイス側で、フラッシュメモリで生じたエラーを検出し訂正するＥＣＣシステムを持つようにすると、エラー率が増えた場合にホストデバイスの負荷が大きいものとなる。例えば、２ビットエラー訂正可能なＥＣＣシステムは、計算規模が大きなものとなることが知られている（例えば、特許文献２参照）。
【０００４】
従ってホストデバイスの負荷増大を抑えると共にエラー率増大に対処するためには、フラッシュメモリ内に２ビットエラー訂正可能なＥＣＣシステムを搭載することが望まれる。その場合に要求されることは、ＥＣＣシステムの演算速度を高速化し、フラッシュメモリの読み出しや書き込み速度の犠牲を抑えることである。
【特許文献１】特開２０００−１７３２８９号公報
【特許文献２】特開２００４−１５２３００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
この発明は、高速演算可能なエラー検出訂正回路を搭載した半導体記憶装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
この発明の一態様による半導体記憶装置は、エラー検出訂正回路が搭載され、前記エラー検出訂正回路は、複数ビットのエラー訂正が可能な巡回符号を用いたものであって、エラー訂正可能な最大ビット数対応の次数を持つ情報多項式の中から、情報ビットとして利用する次数が、シンドローム多項式の計算規模が可及的に小さくなるように選択されている。
【発明の効果】
【０００７】
この発明によると、高速演算可能なエラー検出訂正回路を搭載した半導体記憶装置を提供することができる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照して、この発明の実施の形態を説明する。
【０００９】
図１は、一実施の形態によるフラッシュメモリの要部構成を示す図である。このフラッシュメモリは、４つのセルアレイ１即ち、Ｔ−ｃｅｌｌアレイ（０−１），Ｃ−ｃｅｌｌアレイ（０−２），Ｔ−ｃｅｌｌアレイ（０−３）及びＣ−ｃｅｌｌアレイ（０−４）により一つのバンクＢＮＫ０を構成し、残りの４つのセルアレイ１即ち、Ｔ−ｃｅｌｌアレイ（１−１），Ｃ−ｃｅｌｌアレイ（１−２），Ｔ−ｃｅｌｌアレイ（１−３）及びＣ−ｃｅｌｌアレイ（１−４）により、もう一つのバンクＢＮＫ１を構成している。
【００１０】
各セルアレイ１には、ワード線選択を行うロウデコーダ（ＲＤＥＣ）３が配置され、また隣接するＴ−ｃｅｌｌアレイとＣ−ｃｅｌｌアレイとが共有するセンスアンプ回路（ＳＡ）２を持つ。Ｔ−ｃｅｌｌアレイとＣ−ｃｅｌｌアレイは、詳細は後述するが、それぞれ複数の情報セルＴ−ｃｅｌｌとＣ−ｃｅｌｌを有し、それぞれ少なくとも一つずつの参照セルＲ−ｃｅｌｌを有する。
【００１１】
情報セルＴ−ｃｅｌｌ，Ｃ−ｃｅｌｌと参照セルＲ−ｃｅｌｌとは同じメモリセル構造を有する。そして、Ｔ−ｃｅｌｌアレイから情報セルＴ−ｃｅｌｌが選択されたときに、これと対をなすＣ−ｃｅｌｌアレイからは参照セルＲ−ｃｅｌｌが選択される。同様に、Ｃ−ｃｅｌｌアレイから情報セルＣ−ｃｅｌｌが選択されたときに、これと対をなすＴ−ｃｅｌｌアレイからは参照セルＲ−ｃｅｌｌが選択される。
【００１２】
上下に４つずつ分けられたセルアレイ１の読み出し／書き込みデータは、データバス５，６を介し入出力バッファ７を介して、センスアンプ回路２と外部入出力端子との間で転送される。上下に４つずつ分けられたセルフアレイ１の間に、読み出しデータのエラー検出訂正回路であるＥＣＣ回路８が設けられている。
【００１３】
図２は、センスアンプ回路２を共有するＴ−ｃｅｌｌアレイとＣ−ｃｅｌｌアレイの具体構成を示している。Ｔ−ｃｅｌｌアレイには、一つのビット線ＢＬに、複数の情報セルＮＡＮＤストリング，Ｔ−ＮＡＮＤと、少なくとも一つの参照セルＮＡＮＤストリングＲ−ＮＡＮＤとが接続されている。Ｔ−ｃｅｌｌアレイには、Ｔ−ｃｅｌｌアレイ側のビット線ＢＬと対をなすビット線ＢＢＬに、複数の情報セルＮＡＮＤストリング，Ｃ−ＮＡＮＤと、少なくとも一つの参照セルＮＡＮＤストリングＲ−ＮＡＮＤとが接続されている。
【００１４】
センスアンプ回路２は、ビット線対ＢＬ，ＢＢＬのセル電流差を検出してデータをセンスする、電流検出型のセンスユニットＳＡＵを配置して構成される。図では、一対のビット線ＢＬ，ＢＢＬに一つずつセンスユニットＳＡＵを配置した場合を示しているが、通常は複数対のビット線で一つのセンスユニットを共有する方式が用いられる。
【００１５】
情報セルＮＡＮＤストリングＴ−ＮＡＮＤ，Ｃ−ＮＡＮＤ及び参照セルＮＡＮＤストリングＲ−ＮＡＮＤは、ビット線と直交する方向に複数個配列されて、セルブロックを構成する。セルブロックには共通に、ワード線ＴＷＬ，ＣＷＬ，ＲＷＬが配設される。
【００１６】
図３は、センスユニットＳＡＵに接続される情報セルＮＡＮＤストリングＴ−ＮＡＮＤ（またはＣ−ＮＡＮＤ）と参照セルＮＡＮＤストリングＲ−ＮＡＮＤの具体構成を示している。それぞれ、複数個の直列接続された、電気的書き換え可能な不揮発性メモリセルＭ０−Ｍ３１と、選択ゲートトランジスタＳＧ１，ＳＧ２とを有する。同じ不揮発性メモリセルＭ０−Ｍ３１を用いているが、情報セルＮＡＮＤストリングＴ−ＮＡＮＤ（またはＣ−ＮＡＮＤ）ではこれらが情報セルＴ−ｃｅｌｌ（またはＣ−ｃｅｌｌ）として、また参照セルＮＡＮＤストリングＲ−ＮＡＮＤでは参照セルＲ−ｃｅｌｌとして用いられる。
【００１７】
センスユニットＳＡＵは、データセンス時、情報セルＮＡＮＤストリングＴ−ＮＡＮＤ（またはＣ−ＮＡＮＤ）と参照セルＮＡＮＤストリングＲ−ＮＡＮＤ内の対応するセルが同時に選択され、それらのセル電流Ｉｃと参照電流Ｉｒの差を検出して、データセンスを行う。
【００１８】
図４は、４値記憶を行う場合のメモリセルのデータレベル（しきい値レベル）分布を示している。情報セルＴ−ｃｅｌｌ，Ｃ−ｃｅｌｌには、４つのデータレベルＬ０，Ｌ１，Ｌ２，Ｌ３のいずれか一つが書かれる。参照セルＲ−ｃｅｌｌには、例えばデータレベルＬ０とＬ１の間に設定された参照レベルＬｒが書かれる。
【００１９】
４つのデータレベルＬ０−Ｌ３のビット割付は、情報セルＴ−ｃｅｌｌとＣ−ｃｅｌｌの間で異なる。例えば、４値データを上位ビットＨＢと下位ビットＬＢで（ＨＢ，ＬＢ）で表すものとして、Ｔ−ｃｅｌｌアレイ側の情報セルＴ−ｃｅｌｌでは、Ｌ０＝（１，０），Ｌ１＝（１，１），Ｌ２＝（０，１），Ｌ３＝（０，０）とされ、Ｃ−ｃｅｌｌアレイ側の情報セルＣ−ｃｅｌｌでは、Ｌ０＝（０，０），Ｌ１＝（０，１），Ｌ２＝（１，１），Ｌ３＝（１，０）とされる。
【００２０】
図４には、読み出し時、情報セルＴ−ｃｅｌｌ，Ｃ−ｃｅｌｌに読み出すべきデータに応じて与えられる読み出し電圧Ｒ１，Ｒ２，Ｒ３及び参照セルＲ−ｃｅｌｌに与えられる読み出し電圧Ｒｒを示している。また、書き込み時、情報セルＴ−ｃｅｌｌ，Ｃ−ｃｅｌｌに書き込むべきデータに応じて与えられる書き込みベリファイ電圧Ｐ１，Ｐ２，Ｐ３及び参照セルＲ−ｃｅｌｌに与えられる書き込みベリファイ電圧Ｐｒを示している。
【００２１】
この実施の形態では、二つの５１２ＭｂｉｔのバンクＢＮＫ０，ＢＮＫ１を用いて、１Ｇｂｉｔメモリを構成する場合のＥＣＣ回路８の搭載方法とそのアクセスモードについて説明する。
【００２２】
ここで想定しているメモリは、×１６ＩＯ構成であって、各バンクのページアドレスは独立に設定できるが、アドレス発生は全バンクに共通であり、ページアドレスをどのバンクに適用するのかを指定することによって、各バンクに割り付けるものとする。従って、バンク間でインターリーブしてページアドレスを利用する。
【００２３】
１バンク当たり１０２４ｋページである。各バンクの１６ＩＯに共通のページ長は３２ビットで、このうち８ビットがパラレルに出力できるとする。ページ長は１回のワード線アドレスの設定とセンス動作で読み出せる１ＩＯあたり、バンクあたりの最長データ長である。
【００２４】
このような構成ではセンスアンプ回路２からの1回のデータ転送で１２８ビットのデータが外部に出力される。すなわち構成上２のべき乗のデータが転送される。
【００２５】
このようなフラッシュメモリに搭載するＥＣＣ回路８として、２ビットのエラーが訂正可能なＢＣＨ（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ）符号即ち、２重エラー訂正ＢＣＨ符号を導入する。以下、この符号を２ＥＣ−ＢＣＨ符号という。２ビットエラー訂正を可能とするためには、異なる根をもつ連立方程式が必要である。２ＥＣ−ＢＣＨコードは、以下に述べるように、二つの原始多項式の積で表されるコード生成多項式を持つ巡回符号である。
【００２６】
使用するビット長は２ｎ−１であり、情報として利用できるデータビットは２ｎ−１−２ｎである。２ｍビットのデータを扱うにはｎ＝ｍ＋１とすることになり、必要な量の２倍に近いデータ長を用いなければならない。
【００２７】
図１のメモリ構成で、１２８ビットの情報データの２ビットエラー訂正を行なうのに必要な２ＥＣ−ＢＣＨコードは、ガロア体ＧＦ（２８）であり、使用するビット長は２８−１＝２５５であり、エラーの検査ビットとして１６ビットが必要である。従って、１２８ビットデータ長に１６ビットの検査ビットを加えた１４４ビットが必須となるが、残りの１１１ビットが余分になる。このとき図１に示すように例えば各バンクを２分した上下セルからのデータバス５は、各々７２ＤＱ線となり、トータル１４４ビットのデータを一括転送することになる。
【００２８】
必要のない余分な１１１ビットの扱いと、ＢＣＨ符号の内でどのように情報ビット選択するかでＥＣＣシステムの効率が変わるので、最適なＥＣＣシステムを構成する方法を検討しなければならない。
【００２９】
必要なビット数は不良セルの置き換えのリダンダンシーをも含めて考えれば１２８ビットより多くなることもあるが、ここで検討する１２８ビットデータ長の場合から容易に拡張可能である。
（データのエンコーディング）
ガロア体ＧＦ（２８）上の２ＥＣ−ＢＣＨについて概要を説明する。ＧＦ（２５６）の原始根をαとすると、これを根とする対応するＧＦ（２）上の８次の原始多項式ｍ１（ｘ）は、数１のように表される。即ち、αのべき乗とｍ１（ｘ）によるｘのべき乗の既約多項式がお互いに対応するＧＦ（２５６）の要素となる。
【００３０】
また、αの３乗を根とする８次の既約多項式として、ｍ１（ｘ）と互いに素な数１に示す多項式ｍ３（ｘ）を用いる。
【００３１】
【数１】
0004791831.tif 000002
これらの二つの原始多項式をもとに、２ビットエラー訂正可能なＥＣＣが構成される。書き込むべきデータに検査ビットを付加してエンコードするには、コード生成多項式として、数２のようなｍ１（ｘ）とｍ３（ｘ）の積多項式ｇ（ｘ）を作る。
【００３２】
【数２】
0004791831.tif 000003
２ビットエラー訂正が可能な、情報ビットとして利用できる最大ビット数は、２８−１＝２５５から検査ビット数１６を引いた２３９ビットである。これらを、ビット位置１６から２５４の係数をａ１６〜ａ２５４として、数３のような２３８次の情報多項式ｆ（ｘ）を作る。
【００３３】
【数３】
0004791831.tif 000004
実際にはデータとして用いるのは、２３９ビット中例えば１２８ビットであり、このとき１１１ビットの係数は“０” に固定して対応する次数の項がない情報多項式となる。２３９の項数の情報多項式ｆ（ｘ）のうち、その係数を“０”に固定する１１１項として、どの次数を選ぶかによって、後述するデコード時のシンドローム計算の計算量が異なるのでこの選択のしかたが重要となる。これは後に説明する。
【００３４】
情報多項式ｆ（ｘ）から、検査ビット１６ビットを含むデータ多項式ｆ（ｘ）ｘ１６を作る。このデータ多項式から検査ビットを作るには、データ多項式ｆ（ｘ）ｘ１６をコード生成多項式ｇ（ｘ）で割った、数４のような１５次の剰余多項式ｒ（ｘ）を求める。
【００３５】
【数４】
0004791831.tif 000005
この剰余多項式ｒ（ｘ）の係数ｂ１５〜ｂ０を検査ビットとして用いる。すなわち、２３９から選ばれた１２８の係数ａｉ（１２８）〜ａｉ（１）を“情報ビット”とし、ｂ１５〜ｂ０の１６ビットを“検査ビット”として、下記数５に示す計１４４ビットがメモリに記憶させる“データビット”となる。
【００３６】
【数５】
0004791831.tif 000006
ここで、ａｉ（ｋ）は、メモリに外部から書き込むデータであり、このデータをもとに、チップ内部のＥＣＣシステムで検査ビットｂｊが作られ、これが同時にセルアレイに書き込まれることになる。
（データのデコーディング）
次に、セルアレイから読み出した１４４ビットのデータからエラーを検出し、２ビットのエラーまでを訂正する方法について説明する。
【００３７】
ｆ（ｘ）ｘ１６なる２５４次のデータ多項式の係数をメモリに記憶させてエラーが生じたとすれば、そのエラーも２５４次多項式で表される。このエラー多項式をｅ（ｘ）とすれば、メモリから読み出したデータは、数６のような構造の多項式ν（ｘ）になる。
【００３８】
【数６】
0004791831.tif 000007
この数６のエラー多項式ｅ（ｘ）の係数が“１”の項がエラーとなる。即ち、ｅ（ｘ）を検出することがエラー検出と訂正を行なうことに相当する。
【００３９】
第一段階として、読み出しデータ多項式ν（ｘ）を原始多項式ｍ１（ｘ），ｍ３（ｘ）で割って各々の剰余をＳ１（ｘ），Ｓ３（ｘ）とする。数７に示すように、これは、ｅ（ｘ）をｍ１（ｘ），ｍ３（ｘ）で割った剰余に等しいことは、ν（ｘ）の構造から明らかである。
【００４０】
【数７】
0004791831.tif 000008
この剰余Ｓ１（ｘ）とＳ３（ｘ）をシンドローム（syndrome）多項式という。
【００４１】
２ビットのエラーがｉとｊビットにあるとすれば、ｅ（ｘ）＝ｘｉ＋ｘｊである。ＧＦ（２５６）の要素であるｍ１（ｘ）に関する既約剰余多項式の計算でｉとｊを求める。即ち、ｘｎ≡ｐｎ（ｘ）ｍｏｄ ｍ１（ｘ）としたとき、数８に示すように、エラーの次数の対応する剰余ｐｉ（ｘ），ｐｊ（ｘ）のそれぞれをＸ１，Ｘ２とし、シンドローム多項式Ｓ１（ｘ），Ｓ３（ｘ）に対してＳ１（ｘ）とＳ３（ｘ３）に対応する剰余ｐσ1（ｘ），ｐσ3（ｘ）のそれぞれをＳ１とＳ３とする。
【００４２】
【数８】
0004791831.tif 000009
ｍ３（ｘ３）がαを根として持ち、ｍ１（ｘ）で割り切れることから、次の数９の関係式が得られる。
【００４３】
【数９】
0004791831.tif 000010
第二段階として未知数Ｘ１とＸ２を根とする多項式ΛＲ（ｘ）を考えると、数１０のように、積Ｘ１Ｘ２がＳ１とＳ３で表現できるので、係数がsyndrome多項式から計算できる。
【００４４】
【数１０】
0004791831.tif 000011
第三段階としてΛＲ（ｘ）のＧＦ（２５６）での根となる既約多項式ｐｎ（ｘ）を見つければ、Ｘ１，Ｘ２＝ｐｎ（ｘ）からエラービット位置ｉやｊがｐｎ（ｘ）のｎとして求められる。即ち、ΛＲ（ｘ）≡０ ｍｏｄ ｍ１（ｘ）を、ｎ＝０〜２５４で探索してヒットしたｎがエラービットとなる。
【００４５】
下記数１１に示すように、1ビットエラーの時は、Ｘ１＝Ｓ１，Ｘ１３＝Ｓ３＝Ｓ１３となり、エラー位置がＳ１からわかる。エラーがないときにはＳ１＝Ｓ３≡０（ｍｏｄ ｍ１（ｘ））となる。３ビット以上のエラーでその位置が計算出来ないときにはＳ１，Ｓ３の一方のみが０（ｍｏｄ ｍ１（ｘ））となる。
【００４６】
【数１１】
0004791831.tif 000012
具体的な計算を行なう際に必要となるものをまとめると、次の通りである。
【００４７】
エンコードでは、最高２５４次のデータ多項式ｆ（ｘ）ｘ１６からデータビットとして選ばれた１２８個の項のコード生成多項式ｇ（ｘ）による剰余多項式ｒ（ｘ）の係数の表（剰余テーブル）が必要である。検査ビットの計算にはデータビットで選ばれた項に対応するこの係数を選び、“０”または“１”の２元符号を用いたＧＦ（２）上での加算をおこなう。
【００４８】
デコードでは、syndrome多項式Ｓ１（ｘ）及びＳ３（ｘ３）の計算を行なう際に、２５４次から０次までのｍ１（ｘ）による剰余ｐｎ（ｘ）の係数の表（剰余テーブル）が必要でこれから検査ビットと同様にして計算を行なう。
【００４９】
ＧＦ（２５６）を用いた２ＥＣ−ＢＣＨで使用可能なデータビット２３９を全て使用しないメモリシステムで、ＥＣＣでの計算時間を少なくするためには、情報多項式の中から実際に使用する項（次数）を選択するための具体的な選択方法が必要である。特にシンドロームの計算は剰余を効率的に求められるような項（次数）の選択をしなければならない。
【００５０】
まず剰余の計算の具体的な方法を説明する。
【００５１】
ＧＦ（２）上での計算では掛け算、割り算とも多項式の係数の足し算すなわち“１”の数の偶奇判定で行なわれる。関係する項の係数“１”の数が偶数なら“０”、奇数なら“１”が演算結果となるパリティチェックが基本の計算回路となる。
【００５２】
構成の単純な４ビットのパリティチェック回路（ＰＣ）を図５Ａに示し、その回路記号を図５Ｂに示す。いろいろな構成のパリティチェックが可能な回路は工夫が可能であるが、ここでは簡単のためにパリティチェックのロジックをそのままトランジスタで表現した回路を示す。
【００５３】
このパリティチェック回路は、4ビットａ，ｂ，ｃ，ｄとその相補信号／ａ，／ｂ，／ｃ，／ｄを入力として、偶数個の“１”が入力にあるとき端子ＥＰに“０”を出力する上段回路４０１と、奇数個の“１”が入力にあるとき端子ＯＰに“０”を出力する下段回路４０２とから構成されている。回路４０１，４０２はいずれも、電源Ｖｄｄと接地Ｖｓｓとの間に、４ビットが入力される４つのＰＭＯＳトランジスタと４つのＮＭＯＳトランジスタが直列接続されたゲートを８個並列接続して構成されている。
【００５４】
即ち上段回路４０１は、“１”入力が０，２，４個のいずれかのときに、Ｖｓｓ側のＮＭＯＳトランジスタが導通して、ＥＰ＝“０”となる。下段回路４０２は、“１”入力が１個又は３個のいずれかのときに、Ｖｓｓ側のＮＭＯＳトランジスタが導通して、ＯＰ＝“０”となる。
【００５５】
このパリティチェック回路では、４ビットのパリティチェックをインバータ１段相当の遅延時間で計算できる。
【００５６】
このようなパリティチェック回路を用いて、ＧＦ（２５６）の多項式のＧＦ（２）上での積の計算法を、図６に示す。ＧＦ（２５６）の多項式の演算は、原始多項式が８次であるから、全て７次多項式ｐｎ（ｘ）間の演算となり、四則演算結果は全てどれかの多項式ｐｎ（ｘ）になる。｛ｐｎ（ｘ）｝−１なる除算は、ｐｎ（ｘ）２５５−ｎ（ｘ）の積になる。
【００５７】
ｐｎ（ｘ）のｍ次の項の係数をＰｎｍと表して、下記数１２の７次多項式ｐｉ（ｘ），ｐｊ（ｘ）の積は、図６のように計算される。係数Ｐｎｍは無論“０”か“１”である。
【００５８】
【数１２】
0004791831.tif 000013
ｘｎ≡ｐｎ（ｘ）（ｍｏｄ ｍ１（ｘ））であるので、１４次の項は掛けるｐｊ（ｘ）の7つ先にｐｊ＋７（ｘ）が出てくる、という規則を使うと、多項式ｐｉ（ｘ）とｐｊ（ｘ）の積は、図６に示すように、各多項式の係数間の掛け算と和演算（＝パリティチェック)とで可能となる。
【００５９】
すなわち、１か０との掛け算を行なったものを7から０の各次数ごとに和であるパリティチェックを行い、その結果がｐｉ（ｘ）ｐｊ（ｘ）の各次数の係数になる。掛けるｐｊ（ｘ）については７つ先までの多項式の係数が必要となる。
【００６０】
回路としてはパリティチェック回路のみでよく、掛けるｐｊ（ｘ）からｐｊ＋７（ｘ）の係数に固有の入力を行なう回路をもうけることになる。これは係数Ｐｊｍ＝０のパリティチェックはないからである。パリティチェック回路は、図７に示すように、４ビットパリティチェック回路のほか、必要な入力数に応じて、３ビットパリティチェック回路、２ビットパリティチェック回路等を用いることができる。
【００６１】
このような演算方法をエンコードで検査ビットを生成する際に応用する。次にこれを説明する。
【００６２】
検査ビットの計算は、コード生成多項式ｇ（ｘ）で情報データから作られたデータ多項式ｆ（ｘ）ｘ１６を割って剰余多項式ｒ（ｘ）を求めることによって得られる。この演算を行うためには単項のｘｉをｇ（ｘ）で割った１５次の剰余多項式ｒｉ（ｘ）の係数を予め求めておき、この係数をｐｎ（ｘ）の積の場合と同じように用いる。ｒｉ（ｘ）の係数をＲｉｍ（ｍ＝０〜１５）とし、情報ビットとしてのｆ（ｘ）ｘ１６のｘｉの係数をａｉとする。
【００６３】
具体的な計算は、データビットをａ１６〜ａ２５４としたとき、このうちの１１１ビット分を後のシンドローム計算が少なくなるように選んで“０”に固定してから、図８に示すように、データ多項式の係数ａｉと剰余多項式の係数Ｒｉｍの掛け算と、同じ次数の項の係数の和演算（パリティチェック）によって行なわれる。すなわちデータビットaｉが“１”である次数の剰余ｒｉ（ｘ）の係数Ｒｉｍを各ｍごとにＧＦ（２）上での和すなわちパリティチェックを行い、結果を検査ビットｂｍとする。
【００６４】
次に、１１１ビットの“０”に固定するビット位置の選択を行なう際に必要となるデコードでの計算法を説明する。
【００６５】
まず、メモリセルから読み出したデータｄｉを係数とする多項式ν（ｘ）のｍ１（ｘ）での剰余を求めるのがシンドローム多項式Ｓ１（ｘ）の計算である。この演算は、図９に示すように、ｘｉ（ｉ＝２５４〜０）のｍ１（ｘ）による剰余ｐｉ（ｘ）の係数Ｐｉｍ（ｍ＝０〜７）とｄｉの積と、その結果の和（パリティチェック）とにより行なわれる。すなわち、ｄｉが“１”であるｐｉ（ｘ）のｍ次の係数Ｐｉｍのパリティチェックの結果をシンドローム多項式Ｓ１（ｘ）のｍ次の係数とする。
【００６６】
この計算では、ｄｉが“０”であるところと、Ｐｉｍが“０”であるときは計算を行なわないので、２３９の情報ビット全てを使用しない場合に使用しないビットの選択が計算量を決めることになる。
【００６７】
次にもう一つのシンドローム多項式Ｓ３（ｘ）に関連する計算法を説明する。
シンドローム多項式Ｓ３（ｘ）に関連してエラー位置ｊの検索に必要なのは多項式Ｓ３（ｘ３）である。Ｓ３（ｘ）自体は、ν（ｘ）のｍ３（ｘ）での剰余である。ν（ｘ３）とＳ３（ｘ３）との間には、ｘｉのｍ１（ｘ）による剰余多項式ｐｉ（ｘ）の係数をＰｉｍ（ｍ＝０〜７）とし、ｘｉの係数をｄｉとして、次の数１３のような関係がある。
【００６８】
【数１３】
0004791831.tif 000014
以上の数１３から、Ｓ３（ｘ３）はν（ｘ）の係数ｄｉと剰余ｐ３ｉ（ｘ）によって計算できる。従って必要なのは、ｘｉのｍ１（ｘ）でのｐｉ（ｘ）の係数Ｐｉｍであり、具体的な計算法は、図１０のようになる。
【００６９】
この計算でもｄｉが“０”であるところと、Ｐ３ｉｍが“０”であるときは計算を行なわないので、２３９の情報ビット全てを使用しない場合に使用しないビットの選択が計算量を決めることになる。デコードではシンドローム多項式の計算の後エラー位置を検索する演算などを行なうので、計算時間を短くするためにも計算量を出来るだけ少なくしたい。これは、２３８次の情報多項式ｆ（ｘ）の中から、例えば最適な１２８個の項（次数）の選択を行なうことにより可能となる。次にこの選択の方法について説明する。
【００７０】
シンドローム多項式Ｓ１（ｘ）とＳ３（ｘ３）は同時に並列に計算を行なう。各多項式の各次数の係数の計算は“１”のパリティチェックであるのでどの次数の係数の計算もバラツキなくほぼ同じ時間で行なわれれば計算量は減る。
【００７１】
そのための選択の一つの方法は、シンドローム計算に用いられる７次の剰余多項式ｐｎ（ｘ）とｐ３ｎ（ｘ）の係数が“１”の総和を、各ｎについて求め、総和の数の少ない方から必要なデータビット数だけのｎを選択する。この際最初の１６個は検査ビットとしてｘ０〜ｘ１５の係数を使うので固定し、１７個目以降の選択に係数の“１”の総和の昇順選択をする。
【００７２】
また、同じ総和の数のグループ内で選択が終了する際には、係数“１”がｐｎ（ｘ）とｐ３ｎ（ｘ）内で各次数の項の間に均等に分布するｎを基準に同じ次数項での“１”の重なりが少ない順に選択する。すなわち基準となるｎのｐｎ（ｘ），ｐ３ｎ（ｘ）の係数“１”の次数での項の係数の総和が少ない順に選択する。
【００７３】
このような選択方法で選んだ２５４次のデータ多項式ｆ（ｘ）ｘ１６で１４４ビットデータを扱う場合に使用する、１４４個の次数ｎを、図１１に示す。
【００７４】
この選択方法は必ずしもパリティチェックを行なう多項式の各次数の係数“１”の数の最大のものを最も少なくするとは限らないが、全ての組合せの中から計算ステップが最小となるものを探索する様な大規模な計算を必要としないでシンドローム計算回路規模を減らしかつ、シンドローム計算のステップ数を減らす簡便な方法ではある。
【００７５】
シンドローム計算を最適にするように選んだ次数を用いてエンコードを行なう際には、対応する次数の剰余多項式ｒｎ（ｘ）の係数が必要になるので、これを図１２Ａ及び図１２Ｂに示す。
【００７６】
図１２Ａ及び図１２Ｂは、データ多項式ｆ（ｘ）ｘ１６をコード生成多項式ｇ（ｘ）で割った１５次の剰余多項式の係数である。ｘ０からｘ１５までは情報ビット多項式にはないので実際には使用しない。また０次から３次、４次から７次、８次から１１次、１２次から１５次の係数を１６進表示したものも併せて示した。
【００７７】
これらの剰余多項式ｒｎ（ｘ）の係数表から選択してデータビットとして使用する１２８個のｘｎに対応するものについての各係数をまとめたものを、図１３に示す。即ち図１３は、ｇ（ｘ）の剰余ｒｎ（ｘ）であって、選択されたｘｎの剰余ｒｎ（ｘ）の各次数での係数が“１”であるｎの表である。
【００７８】
例えば、ｘ１５の係数が“１”であるｒｎ（ｘ）の次数ｎは、図１３のｍ＝１５の列の係数“１”の数が１から６２の欄に書かれている１７，１８，２２，…，２４５，２４９，２５０である。チェックビットのｘ１５の係数に相当するｂ１５は情報データ多項式ｆ（ｘ）ｘ１６の中のこの選択されたｎ次の項の係数のパリティチェックの結果として得られる。
【００７９】
このようにして、図１３の表から行なう検査ビットの計算回路例を図１４に示す。ｘｍのｍ＝１１，５，２は図１３の表からパリティチェックするビット数が最大７２個であるので、図１４ではこの場合を例として示す。ｘｎのｇ（ｘ）による剰余多項式ｒｎ（ｘ）のｍ次項の係数Ｐｎｍが“０”でない次数ｎは表にしてあるので、各ｍについて表からｎを選択し、ａｎと／ａｎを用いてパリティチェックを行なう。
【００８０】
入力の数が４の剰余系のいずれに属するかによって用いるパリティチェック回路（ＰＣ）を組合せる。すなわち、４で割り切れれば4ビットＰＣのみで、１が余れば５ビットＰＣを加え、２が余れば２ビットＰＣを加え、３が余れば３ビットＰＣを加える。
【００８１】
ｍ＝１１，５，２の例では７２入力である。このとき検査ビット計算回路は図１４に示すように、３段のパリティチェック回路により構成することができる。初段は、１８個の４ビットＰＣで構成する。２段目は１８入力となるので、４個の４ビットＰＣと１個の２ビットＰＣを用いて構成する。３段目は５入力となるので１個の５ビットＰＣで構成する。３段目のパリティチェック回路の出力が検査ビットｂｍ，／ｂｍとなる。
【００８２】
検査ビットの計算の場合と同様の計算をシンドローム計算でも行なうので次にこれを説明する。
【００８３】
図１５はシンドローム多項式Ｓ１（ｘ）の計算で使用する７次の剰余多項式ｐｎ（ｘ）の選択されたｎでの各次数の係数“１”のｎの表である。例えばｘ７の係数が“１”であるｐｎ（ｘ）の次数ｎは、表のｍ＝７の列の係数“１”の数が1から５６の欄に書かれている７，１１，１２，…，２３７，２４２，２４５である。Ｓ１（ｘ）のｘ７の係数はデータ多項式ν（ｘ）の中のこの選択されたｎ次の項の係数のパリティチェックの結果として得られる。
【００８４】
このようにして、図１５の表から行なうシンドロームＳ１（ｘ）の計算回路例を図１６に示す。ｍ＝６，２の場合に、図１５からパリティチェックするビット数が最大６６個となるので、図１６ではこの場合を例として示す。ｘｎのｍ１（ｘ）の剰余多項式ｐｎ（ｘ）のｍ次項の係数Ｐｎｍが“０”でない次数ｎは表にしてあるので、各ｍについて表からｎを選択し、データビットｄｎと／ｄｎを用いてパリティチェックを行なう。
【００８５】
入力の数が４の剰余系のいずれに属するかによって用いるパリティチェッカ（ＰＣ）を組合せる。すなわち４で割り切れれば４ビットＰＣのみで、1が余れば５ビットＰＣを加え、２が余れば２ビットＰＣを加え、３が余れば３ビットＰＣを加える。
【００８６】
ｍ＝６，２の例では６６入力であるので、この場合も３段のパリティチェック回路で構成する。初段は、４ビットＰＣを１６個と２ビットＰＣ1個で構成する。２段目は１７入力となるから、４ビットＰＣを３個と５ビットＰＣを１個で構成する。３段目は４入力となるので4ビットＰＣ一つでよい。３段目出力が、係数（ｓ１）ｍとなる。
【００８７】
シンドローム多項式Ｓ３（ｘ３）の計算にも同様であり、次にこれを説明する。
【００８８】
図１７は、シンドローム多項式Ｓ３（ｘ３）の計算で使用するｘ３ｎのｍ１（ｘ）での剰余ｐ３ｎ（ｘ）の選択されたｎでの各次数の係数“１”の次数ｎの表である。
【００８９】
例えば、ｘ７の係数が“１”であるｐ３ｎ（ｘ）の次数ｎは、表のｍ＝７の列の係数“１”の数が１から５８の欄に書かれている４，８，１４，…，２４１，２４２，２４９である。Ｓ３（ｘ３）のｘ７の係数に相当する（ｓ３）７はデータ多項式ν（ｘ）の中のこの選択されたｎ次の項の係数のパリティチェックの結果として得られる。
【００９０】
その計算回路例を図１８に示す。図１７から、ｘｍのｍ＝５がパリティチェックするビット数が最大７３個であるので、図１８はこの場合を例として示す。ｘ３ｎのｍ１（ｘ）の剰余多項式ｐ３ｎ（ｘ）のｍ次項の係数Ｐ３ｎｍが“０”でないｎは表にしてあるので、各ｍについて表からｎを選択し、ｄｎと／ｄｎを用いてパリティチェックを行なう。
【００９１】
入力の数が４の剰余系のいずれに属するかによって用いるパリティチェッカを組合せる。すなわち４で割り切れれば4ビットＰＣのみで、１が余れば５ビットＰＣを加え、２が余れば２ビットＰＣを加え、３が余れば３ビットＰＣを加える。
【００９２】
ｍ＝５の例では７３入力であるので、この場合も３段のパリティチェック回路で構成する。初段は、４ビットＰＣを１７個と５ビットＰＣを１個で構成する。２段目は１８入力となるので、４ビットＰＣを４個と２ビットＰＣを１個とで構成する。３段目は５入力となるので５ビットＰＣを１個で構成できる。３段目出力が、係数（ｓ３）ｍ，／（ｓ３）ｍとなる。
【００９３】
次に、デコードで必要となる剰余多項式ｐｎ（ｘ）の係数を図１９に示す。図ではｘｎのｍ１（ｘ）の剰余であるｐｎ（ｘ）の各次数の係数の“０”，“１”と、０〜３次及び４〜７次の係数をそれぞれ１６進表示で表したものを、各次数ｎについて示した。この表を用いて先に説明したようにデータビットとして使用する１２８＋１６の次数ｎを選択する。
【００９４】
次にエラー位置を検索する回路システムについて説明する。
【００９５】
エラー位置検索は、数１０の多項式ΛＲ（ｘ）を少し書き換えた、次の数１４を満たすｐｎ（ｘ）を求めることである。
【００９６】
【数１４】
0004791831.tif 000015
言い換えれば、エラー位置検索計算システムは、多項式（ｐｎ）Ｓ１（ｘ）＋（Ｓ１（ｘ））２＋Ｓ３（ｘ３）／Ｓ１（ｘ）の係数と、ｐ２ｎの係数の比較を行い、等しくなるｎを見つけることを目的とする。
【００９７】
図２０はその様なエラー位置検索計算システムの概要である。各ｐｎ（ｘ）（ｎ＝０〜２５４）に対応する２５５個の演算部２０１を持つ。これらの演算部２０１の演算結果と（ｐｎ（ｘ））２＝ｐ２ｎ（ｘ）の係数を比較して一致したｎの位置を見つけると、この位置がエラーのデータビット位置となる。
【００９８】
２５５個の演算部２０１は、実際にデータビットとして利用する選択された１４４ビットの第１の演算部分Ｄ−ｐａｒｔ（数１４の右辺第２項、第３項及び第４項対応部分）と、シンドローム多項式のみが関係する第２の演算部分Ｓ−ｐａｒｔ（数１４の右辺第３項及び第４項対応部分）に分かれる。
【００９９】
シンドローム多項式の係数データ（ｓ１）ｍ，／（ｓ１）ｍ，（ｓ３）ｍ，／（ｓ３）ｍは、データバス２０２に出力され、ここから演算部２０１に供給される。演算部２０１は、第１の演算部分Ｄ−ｐａｒｔと第２の演算部分Ｓ−ｐａｒｔに共通に、シンドローム多項式の係数によって演算部を選択するためのデコーダ部“ｄｅｃ．”を持つ。デコーダ部“ｄｅｃ．”は、各ｐｎ（ｘ）の位置に対してｐ２ｎ（ｘ）の係数に相当するＳ１（ｘ）の係数で選択される（ｎ／２）デコーダと、ｐ２５５−ｎ（ｘ）の係数に相当するＳ１（ｘ）の係数で選択される（−ｎ）デコーダを持つ。
【０１００】
演算部２０１はまた、（ｎ／２）デコーダによって選ばれる（ｐｎ（ｘ））２＝ｐ２ｎ（ｘ）の係数を発生させる部分と、（−ｎ）デコーダによって選ばれるシンドローム多項式Ｓ３（ｘ３）とｐｎ（ｘ）を掛けた多項式の係数を発生するパリティチェック部とを持っている。これらの部分がデコーダで選ばれて（Ｓ１（ｘ））２とＳ３（ｘ３）／Ｓ１（ｘ）をそれぞれ各ｐａｒｔの共通データバス２０３へ出力する。
【０１０１】
第１の演算部分Ｄ−ｐａｒｔは更に加えて、ｐｎ（ｘ）とＳ１（ｘ）の積の多項式の係数を発生するパリティチェック部を持つ。このパリティチェック部は全ての第１の演算部分Ｄ−ｐａｒｔで同時に演算が行なわれる。更にこのパリティチェック演算結果と、各ｐａｒｔ共通のデータバス２０３の（Ｓ１（ｘ））２とＳ３（ｘ３）／Ｓ１（ｘ）とのパリティチェックを行うパリティチェック部２０４が、各第１の演算部分Ｄ−ｐａｒｔに付属する。
【０１０２】
これらのパリティチェック部２０４の演算結果は、ｐｎ（ｘ）の位置のｐ２ｎ（ｘ）の係数に相当するデコードを行なう（２ｎ）デコーダ部２０５を選択するようになっている。これにより選択されたｐｎ（ｘ）がエラーのビット位置に対応する選択された項ｘｎであり、１４４ビットのデータ位置ｋとｎの対応でエラーを特定することができる。
【０１０３】
図２１は、図２０の演算部２０１のうち、シンドローム多項式（Ｓ１（ｘ））２，Ｓ３（ｘ３）／Ｓ１（ｘ）にのみ関係する第２の演算部分Ｓ−ｐａｒｔの計算回路の詳細を、ｐｉ（ｘ）位置について示している。Ｓ１（ｘ）の係数をデコードしてこの第２の演算部分Ｓ−ｐａｒｔを選択するデコーダとして、係数がｐｉ（ｘ）の係数と同じときに選択されるデコーダ２１１（(i) decoder）と、ｐ２５５−ｉ（ｘ）の係数と同じ時に選択されるデコーダ２１２（(255-i) decoder）とを持っている。
【０１０４】
デコーダ２１１の出力はｐ２ｉ（ｘ）の係数Ｐ２ｉｍ（ｍ＝０〜７）を発生するラッチ２１３の出力スイッチ２１４につながり、この第２の演算部分Ｓ−ｐａｒｔが選択されれば、その係数をバス２０３の（Ｓ１）２側に出力する。デコーダ２１２の出力は、Ｓ３（ｘ３）の係数を取り込むスイッチ２１５，２１６と、これらの係数のパリティチェックを行なうパリティチェック回路２１８の出力をバス２０３のＳ３／Ｓ１側に出力するスイッチ２１７につながる。
【０１０５】
パリティチェック回路２１８は、係数（ｓ３）ｋと係数Ｐｉ＋ｋｍを掛けて、ｋ＝０〜７の和を求めるものである。即ち、Ｐｉ＋ｋｍが“１”である係数（ｓ３）ｋのパリティチェックを行い、その結果が係数（ｓ３／ｓ１）ｍ（ｍ＝０〜７）となる。このパリティチェック結果は、スイッチ２１５，２１６，２１７がオンになることで、バス２０３のＳ３／Ｓ１側に出力される。
【０１０６】
パリティチェック回路２１８の構成は先に示した計算回路例のようにいろいろな種類の回路を組み合わせて、例えば最大２段で構成される。
【０１０７】
図２２は、第１の演算部分Ｄ−ｐａｒｔの詳細を、ｐｊ（ｘ）位置について示している。ここでは、第２の演算部分Ｓ−ｐａｒｔと同じくシンドローム多項式のみに関連した計算に加えて、第１の演算部分Ｄ−ｐａｒｔに特有の計算を行う。即ちデコーダ２１１，２１２、ラッチ２１３、スイッチ２１５−２１７、パリティチェック回路２１８は、図２１に示した第２の演算部分Ｓ−ｐａｒｔと同じである。
【０１０８】
第２の演算部分Ｄ−ｐａｒｔに特有の演算は、Ｓ１（ｘ）の係数を取り込み、これらの係数のパリティチェックを行なうパリティチェック回路２１９の部分である。このパリティチェック回路２１９は、係数（ｓ１）ｋと係数Ｐｊ＋ｋｍを掛けてｋ＝０〜７の和を求めるものである。即ち、Ｐｊ＋ｋｍが“１”である（ｓ１）ｋのパリティチェックを行い、その結果がｐｊ（ｘ）Ｓ１（ｘ）の係数（ｐｊＳ１）ｍ（ｍ＝０〜７）となる。このパリティチェック回路２１９の構成も、先に示した計算回路例のようにいろいろな種類の回路を組み合わせて、最大２段で構成される。
【０１０９】
図２３は、上述した第１及び第２の演算部分Ｄ−ｐａｒｔ，Ｓ−ｐａｒｔの出力の演算をしてエラー訂正を行なうエラー訂正回路の構成である。ここでは、各第１の演算部分Ｄ−ｐａｒｔに付随して多項式ｐｎ（ｘ）Ｓ１（ｘ）＋（Ｓ１（ｘ））２＋Ｓ３（ｘ３）／Ｓ１（ｘ）を計算し、その計算結果をｐ２ｎ（ｘ）と比較して、データのエラー訂正を行う。具体的に図２３は、データの実際のビット位置ｋに対応する第１の演算部分Ｄ−ｐａｒｔであるｐｊ（ｋ）（ｘ）について示している。
【０１１０】
ｐｊ（ｘ）Ｓ１（ｘ）＋（Ｓ１（ｘ））２＋Ｓ３（ｘ３）／Ｓ１（ｘ）なる多項式係数の計算は、パリティチェック回路２２１で行う。即ちここで、第１の演算部分Ｄ−ｐａｒｔからの係数（ｐｊＳ１）ｍと、共通バス２０３上の係数（（Ｓ１）２）ｍと、共通バス２０３上の係数（Ｓ３／Ｓ１）ｍの３ビットパリティチェックを、ｍ＝０〜７の各ｍについて行う。
【０１１１】
その計算結果は、ｐ２ｊ（ｋ）（ｘ）の係数と一致するときに選択されるデコーダ２２２（(2j) decoder）に入力される。このデコーダ２２２は、ＮＯＲ回路Ｇ１とＮＡＮＤ回路Ｇ２とで構成され、互いに相補的な出力を出す。すなわち、係数が“一致”とデコードされれば、ＮＯＲ回路Ｇ１からは“１” 、ＮＡＮＤ回路Ｇ２からは“０” が出力される。一致しなければ、これらの逆データが出力される。
【０１１２】
このデコーダ２２２の出力は、データビットｄｋとのＸＯＲ回路である２ビットパリティチェック回路（データ反転回路）２２３に入る。この２ビットパリティチェック回路２２３は、図２４に示すように、２ビット入力が一致の場合にＥＰ＝“０”を出力する回路である。従って、デコーダ２２２が一致信号を出せば、データビットｄｋの反転が出力され、不一致ならデータビットｄｋがそのまま出力される。
【０１１３】
エラーが３ビット以上あれば訂正は不可能である。これを判断するために判定回路２２４が設けられている。ここでは、シンドローム多項式Ｓ１（ｘ）とＳ３（ｘ３）の一方のみが、ｍｏｄ ｍ１（ｘ）で０であれば、３ビット以上のエラーが有ることになる、という事実を利用する。具体的には、ｍ＝０〜７の範囲で係数（ｓ１）ｍ＝０，（ｓ３）ｍ＝０をそれぞれ判定するためにＮＯＲ回路Ｇ３，Ｇ４を用い、その判定結果を２ビットパリティチェック回路２２５で計算する。
【０１１４】
パリティチェックの結果が“１”であれば、訂正不能（non correctable）であることを示す。このパリティチェック回路２２５の“１”出力は、デコーダ２２２を非活性にしてデータ訂正をしないような制御信号として用いられる。
【０１１５】
ここまで、２ビットエラーまで訂正可能な２ＥＣ−ＢＣＨコードを説明したが、より一般的に、ｔ≧２として、ｔ重エラー訂正ＢＣＨ符号を用いることができる。この場合、ガロア体ＧＦ（２ｍ）のｔ個の元α，α３，…，α２ｔ−１をコードの根に持つＢＣＨ符号となる。
【０１１６】
この発明は、上記実施の形態で説明したフラッシュメモリの他、如何なる半導体メモリにも適用可能である。
【０１１７】
例えば図２５は、通常のＮＡＮＤ型フラッシュメモリのメモリコア回路構成を示している。このメモリコア回路は、セルアレイ１ａ、センスアンプ回路２ａ及びロウデコーダ３ａを有する。セルアレイ１ａは、直列接続されたメモリセルＭ０−Ｍ３１を有するＮＡＮＤセルユニット（ＮＡＮＤストリング）を配列して構成されている。ＮＡＮＤセルユニットＮＵの一端は選択ゲートトランジスタＳ１を介してビット線ＢＬｅ（ＢＬｏ）に、他端は選択ゲートトランジスタＳ２を介して共通ソース線ＣＥＬＳＲＣに接続されている。
【０１１８】
メモリセルの制御ゲートは、ワード線ＷＬ０−ＷＬ３１に接続され、選択ゲートトランジスタＳ１，Ｓ２のゲートは選択ゲート線ＳＧＤ，ＳＧＳに接続されている。ワード線ＷＬ０−ＷＬ３１と選択ゲート線ＳＧＤ，ＳＧＳを選択駆動するのがロウデコーダ３ａである。
【０１１９】
センスアンプ回路２ａは、同時書き込み及び読み出しを行う１ページ分のセンスユニットＳＡを有する。各センスユニットＳＡには、ビット線選択回路４により、隣接するビット線ＢＬｅ，ＢＬｏのいずれかが選択されて接続される。これにより、一つのワード線ＷＬｉと複数の偶数番ビット線ＢＬｅ（或いは複数の奇数番ビット線ＢＬｏ）により同時に選択されるメモリセルの集合が、同時に書き込み／読み出しが行われる１ページ（１セクタ）となる。非選択側のビット線は所定電位を与えたシールド線として利用することにより、選択ビット線間の干渉を防止することができる。
【０１２０】
ワード線ＷＬ０−ＷＬ３１を共有するＮＡＮＤセルユニットの集合は、データ消去の単位とするブロックを構成し、図のようにビット線の方向に複数のブロックＢＬＫ０−ＢＬＫｎが配置される。
【０１２１】
この様なコア回路を持つＮＡＮＤ型フラッシュメモリにおいても、微細化や多値化が進むと、２ビット以上のエラー訂正をチップ内で実現する必要性が増える。この発明のエラー訂正システムは、エラー検出訂正の計算規模を抑えて高速演算可能としており、従ってこの様なメモリに適用して有効である。
【図面の簡単な説明】
【０１２２】
【図１】この発明の実施の形態によるフラッシュメモリの要部構成を示す図である。
【図２】同フラッシュメモリのセルアレイの具体的構成を示す図である。
【図３】同セルアレイの更に具体的な構成を示す図である。
【図４】同フラッシュメモリのデータレベル関係を示す図である。
【図５Ａ】ＥＣＣ回路に用いられる“１”の偶奇判定を行う４ビットパリティチェック回路を示す図である。
【図５Ｂ】同パリティチェック回路の記号を示す図である。
【図６】ＧＦ（２）上での多項式の積演算の方法を示す図である。
【図７】その積演算に用いられるパリティチェック回路を示す図である。
【図８】ＥＣＣ回路のエンコードにおける検査ビット計算法を示す図である。
【図９】ＥＣＣ回路のデコードにおけるシンドローム多項式Ｓ１（ｘ）の計算法を示す図である。
【図１０】同じくシンドローム多項式Ｓ３（ｘ３）の計算法を示す図である。
【図１１】情報多項式のうち、データビットに使用するために選択された１４４個の次数を示す図である。
【図１２Ａ】データ多項式をコード生成多項式で割った１５次の剰余多項式の係数表（一部）である。
【図１２Ｂ】データ多項式をコード生成多項式で割った１５次の剰余多項式の係数表（残部）である。
【図１３】同１５次の剰余多項式の各次数の係数が“１”であるｎの表である。
【図１４】検査ビットの計算に用いられるパリティチェック回路構成を示す図である。
【図１５】シンドローム多項式Ｓ１（ｘ）の計算で使用する剰余多項式ｐｎ（ｘ）の選択されたｎでの各次数の係数“１”のｎの表である。
【図１６】シンドローム多項式Ｓ１（ｘ）の計算回路例である。
【図１７】シンドローム多項式Ｓ３（ｘ３）の計算で使用する剰余多項式ｐ３ｎ（ｘ）の選択されたｎでの各次数の係数“１”のｎの表である。
【図１８】シンドローム多項式Ｓ３（ｘ３）の計算回路例である。
【図１９】デコードで必要となる剰余多項式ｐｎ（ｘ）の係数表である。
【図２０】ＥＣＣ回路のエラー位置検索回路を示す図である。
【図２１】同エラー位置検索回路のＳ−ｐａｒｔ部の構成を示す図である。
【図２２】同エラー位置検索回路のＤ−ｐａｒｔ部の構成を示す図である。
【図２３】同エラー位置検索回路に付属するエラー訂正回路の構成を示す図である。
【図２４】同エラー訂正回路に用いられる２ビットパリティチェック回路を示す図である。
【図２５】この発明が適用されるＮＡＮＤ型フラッシュメモリのコア回路構成を示す図である。
【符号の説明】
【０１２３】
１，１ａ…セルアレイ、２，２ａ…センスアンプ回路、３，３ａ…ロウデコーダ、５，６…データバス、７…ＩＯバッファ、８…ＥＣＣ回路、２０１…演算部、２０２，２０３…データバス、２０４…パリティチェック部、２０５…デコーダ部、２１１，２１２…デコーダ、２１３…係数ラッチ、２１４−２１７…スイッチ、２１８，２１９…パリティチェック回路、２２１…３ビットパリティチェック回路、２２２…デコーダ、２２３…２ビットパリティチェック回路（データ反転回路）、２２４…判定回路。
【図１】
0004791831.tif 000016
【図２】
0004791831.tif 000017
【図３】
0004791831.tif 000018
【図４】
0004791831.tif 000019
【図５Ａ】
0004791831.tif 000020
【図５Ｂ】
0004791831.tif 000021
【図６】
0004791831.tif 000022
【図７】
0004791831.tif 000023
【図８】
0004791831.tif 000024
【図９】
0004791831.tif 000025
【図１０】
0004791831.tif 000026
【図１１】
0004791831.tif 000027
【図１２Ａ】
0004791831.tif 000028
【図１２Ｂ】
0004791831.tif 000029
【図１３】
0004791831.tif 000030
【図１４】
0004791831.tif 000031
【図１５】
0004791831.tif 000032
【図１６】
0004791831.tif 000033
【図１７】
0004791831.tif 000034
【図１８】
0004791831.tif 000035
【図１９】
0004791831.tif 000036
【図２０】
0004791831.tif 000037
【図２１】
0004791831.tif 000038
【図２２】
0004791831.tif 000039
【図２３】
0004791831.tif 000040
【図２４】
0004791831.tif 000041
【図２５】
0004791831.tif 000042