(57)【特許請求の範囲】
【請求項１】
複数のコラムと複数のローとの交差部にデータを格納可能なエントリーを有するルックアップテーブルのルックアップしたエントリーの重複検査方法であって、
コンピュータにより複数の異なる数を前記コラムの中の第１のコラムに含まれる複数のテーブル・エントリー（１２６，１２８，１３０）にそれぞれ格納するとともに、前記異なる数の補数である複数のエラー検出コードを前記コラムの中の第２のコラムに含まれる複数のテーブル・エントリー（１５４，１５６，１５８）に格納し、
前記ローのうちの２つのローに対応する前記異なる数に対するルックアップ結果の論理和を第１の論理回路により第１のコード部とするとともに、前記ローのうちの２つのローに対応する前記エラー検出コードに対するルックアップ結果の論理和を第２の論理回路により第２のコード部とし、
前記第１のコード部と前記第２のコード部のいずれか一方の補数を第３の論理回路により第３のコード部とし、
前記第１のコード部と前記第２のコード部のうち補数を取られなかったコード部を第４の論理回路により第４のコード部とし、
比較手段により前記第３のコードを前記第４のコードと比較し、前記第３のコード部が前記第４のコード部と等しい場合は、前記ルックアップテーブルに二重エントリーが存在しないと判定して、電子的論理設計を継続し、
前記第３のコード部が前記第４のコード部と等しくない場合は、前記ルックアップテーブルに二重エントリーが存在すると判定して、電子的論理設計を中断する、
ことを特徴とする、ルックアップしたエントリーの重複検査方法。
【請求項２】
複数のコラムと複数のローとの交差部にデータを格納可能なエントリーを有するルックアップテーブルのルックアップしたエントリーの重複検査装置であって、
前記ルックアップテーブルは、複数の異なる数がそれぞれ格納された前記コラムの中の第１のコラムに含まれる複数のテーブル・エントリー（１２６，１２８，１３０）と、前記異なる数の補数である複数のエラー検出コードがそれぞれ格納された前記コラムの中の第２のコラムに含まれる複数のテーブル・エントリー（１５４，１５６，１５８）とを備え、
前記装置は、
前記ローのうちの２つのローに対応する前記異なる数に対するルックアップ結果の論理和を第１のコード部とするとともに、前記ローのうちの２つのローに対応する前記エラー検出コードに対するルックアップ結果の論理和を第２のコード部とする第１の論理回路と、
前記第１のコード部と前記第２のコード部のいずれか一方の補数を第３のコード部とする第２の論理回路と、
前記第１のコード部と前記第２のコード部のうち補数を取られなかったコード部を第４のコード部とする第３の論理回路と、
前記第３のコード部が前記第４のコード部と等しい場合は、前記ルックアップテーブルに二重エントリーが存在しないと判定して、電子的論理設計を継続する第４の論理回路と、
前記第３のコード部が前記第４のコード部と等しくない場合は、前記ルックアップテーブルに二重エントリーが存在すると判定して、電子的論理設計を中断する第５の論理回路と、
を備えることを特徴とする、ルックアップしたエントリーの重複検査装置。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明は電子的論理設計に関し、特にマイクロプロセッサにおける電子的論理設計に関し、更に詳細には、ルックアップしたエントリーの重複検出方法および装置に関する。
【背景技術】
【０００２】
発明の背景
ルックアップテーブルはマイクロプロセッサの設計を含む様な分野において一般に使用されている。図１において、従来のルックアップテーブル１１０はいくつかのコラム１２０、１２２、１２４、１５０といくつかのローからなっている。各コラム１２０、１２２、１２４、１５０内のデータは一つのロー内に関連するデータ（例えば、最下段のローではデータ１４４，１４６，１３０，１５８）を配置することによりアレンジできる。１例および図１において、関連するデータ１３０、１４４、１４６、１５８は、他の物理的配置も可能であるが、ローフォーマットに物理的に配置されている。従来のルックアップテーブル１１０においては、１つのコラム１２０内のエントリー１４０、１４２、１４４はテーブル１１０に対するインデックスコラムとして使用される。インデックスコラム１２０内のデータ１４０、１４２、１４４の特定の値が検索され、即ち、「ルックアップ」され、見つかれば、他のコラム内の同一のロー内の他の関連するデータが出力される。しばしば、見つかったロー内のインデックスエントリー１４０、１４２、１４４はそれ自体が出力される。
【０００３】
残念ながら、インデックスデータ１４０、１４２、１４４は、データ１４０、１４２、１４４がルックアップテーブル１１０を代表する物理的格納デバイスに書き込まれる時のデータメモリセル又は電気的インターフェースの障害といった様々な要因によりしばしば損なわれる。これが起きると、誤りデータが格納され、サーチ結果を損う。例えば、データ１４０が１０１の値を持つようにして誤って格納されると、２つのエントリー１４０、１４４が１０１の所望のインデックスエントリーと一致する。
特許文献２２は、ランダム・アクセス・メモリとの関係においてエラーの検出を可能にするエンコーディング・スキームの提供に関係している。このスキームにおいては、２つの異なるチェック・コード・フィールドが（有用な）データと共に、そのデータと同じメモリ・アドレスに格納される。第１のチェック・コード・フィールドはデータの関数として生成され、第２のチェック・コード・フィールドはメモリ・アドレスの関数として生成される。第１のチェック・コード・フィールドは、（有用な）データのビットに基づいて生成された、サム・コードであり得る。また、第２のチェック・コード・フィールドはメモリ・アドレスから生成されたパリティ・ビットか、又はメモリ・アドレスのビットから生成されたサム・コードであり得る。データが読み出されるとき、読み出しに用いられるメモリ・アドレスと、読み出された（有用な）データとに基づき、それら２つのチェック・フィールド（例えば、サム・コード及びパリティ・ビット）が生成され、２つの格納されているチェック・フィールドと比較される。これらの手段によって、データ・エラー、誤ったメモリ・ワード・アクセス・エラー、及び複数メモリ・ワード・アクセス・エラーから得られるエラーが検出可能であると記載されている。
関連出願の相互参照
本願発明の主題は、下記に掲げる出願の主題と関連している。
【０００４】
【特許文献１】米国特許出願番号08/943,911、「テスト記憶装置用２進数を効率的に生成する方法、システムおよび装置」の名称で、Nirmal R. Saxenaによって1995年６月９日に出願
【０００５】
【特許文献２】米国特許出願番号08/488,615、「メモリアドレッシングエラーを検出する方法および装置」の名称で、Nirmal R. Saxenaによって1995年６月９日に出願
【０００６】
【特許文献３】米国特許出願番号08/457,049、「並列データプロセッサにおけるアクティブ命令を回転させる方法および装置」の名称で、Sunil Savkar、Michael C. Shebanow 、Gene W. ShenおよびFarnad Sajjadianによって1995年６月１日に出願
【０００７】
【特許文献４】米国特許出願番号08/456,746、「プログラマブル命令トラップシステムおよび方法」の名称で、Sunil Savkar、 Gene W. Shen 、Farnad SajjadianおよびMichael C. Shebanow によって1995年６月１日に出願
【０００８】
【特許文献５】米国特許出願番号 08/388,602 、「スーパースケーラ  マイクロプロセッサ用命令フロー制御回路」の名称で、Takeshi Kitaharaによって1995年２月14日に出願
【０００９】
【特許文献６】米国特許出願番号 08/388,389 、「格納命令に関して負荷命令を順不同に実行するアドレッシング方法」の名称で、Michael A. Simone およびMichael C. Shebanow によって1995年２月14日に出願
【００１０】
【特許文献７】米国特許出願番号 08/388,606 、「名前を付け替えられたレジスタに結果を効率的に書き込む方法および装置」の名称で、DeForest W. Tovey 、Michael C. Shebanow およびJohn Gmuender によって1995年２月14日に出願
【００１１】
【特許文献８】米国特許出願番号 08/388,364 、「マイクロプロセッサにおける物理レジスタの利用を調整する方法および装置」の名称で、DeForest W. Tovey 、Michael C. Shebanow およびJohn Gmuender によって1995年２月14日に出願
【００１２】
【特許文献９】米国特許出願番号 08/390,885 「精密な状態を保持するため命令状態をトラッキングするプロセッサ構造および方法」の名称で、Gene W. Shen、John Szeto、Niteen A. PatkarおよびMichael C. Shebanow によって1995年２月14日に出願
【００１３】
【特許文献１０】米国特許出願番号 08/397,810 「アドレス変換の高速化のための並列アクセス  マイクロ−ＴＬＢ」の名称で、Chih-Wei David Chang、Kioumars Dawallu、Joel F. Boney 、Ming-Ying LiおよびJen-Hong Charles Chen によって1995年３月３日に出願
【００１４】
【特許文献１１】米国特許出願番号 08/397,809 「コンピュータシステムにおけるアドレス変換用ルックアサイドバッファ」の名称で、Leon Kuo-Liang Peng、Yolin Lin およびChih-Wei David Changによって1995年３月３日に出願
【００１５】
【特許文献１２】米国特許出願番号 08/397,893 、「データプロセッサにおけるプロッセサ資源の再生利用」の名称で、Michael C. Shebanow 、Gene W. Shen、Ravi Swami、Niteen A. Patkarによって1995年３月３日に出願
【００１６】
【特許文献１３】米国特許出願番号 08/397,891 、「実行準備ができたものから命令を選択する方法および装置」の名称で、Michael C. Shebanow 、John Gmuender 、Michael A. Simone 、John R. F. S. Szeto 、Takumi Maruyama および DeForest W. Toveyによって1995年３月３日に出願
【００１７】
【特許文献１４】米国特許出願番号 08/397,911 、「不履行命令の高速ソフトウェア  エミュレーション用ハードウェアサポート」の名称で、Shalesh Thusoo、Farnad Sajjadian、Jaspal KohliおよびNiteen A. Patkarによって1995年３月３日に出願
【００１８】
【特許文献１５】米国特許出願番号 08/398,284 、「制御転送リターンを加速する方法および装置」の名称で、Akiro Katsuno 、Sunil SavkarおよびMichaelC. Shebanow によって1995年３月３日に出願
【００１９】
【特許文献１６】米国特許出願番号 08/398,066 、「フェッチプログラムカウンタの更新方法」の名称で、Akira Katsuno 、Niteen A. Patkar、Sunil SavkarおよびMichael C. Shebanow によって1995年３月３日に出願
【００２０】
【特許文献１７】米国特許出願番号 08/397,910 、「コンピュータシステムにおけるエラーの優先化および処理方法および装置」の名称で、Chih-Wei David Chang、Joel Fredrick Boney およびJaspal Kohliによって1995年３月３日に出願
【特許文献１８】米国特許出願番号 08/398,151 、「制御転送命令の迅速な実行方法および装置」の名称で、Sunil W. Savkar によって1995年３月３日に出願
【００２１】
【特許文献１９】米国特許出願番号 08/397,800 、「マイクロプロセッサにおけるゼロビット状態フラッグの生成方法および装置」の名称で、Michael Simoneによって1995年３月３日に出願
【００２２】
【特許文献２０】米国特許出願番号 08/397,912 、「パイプライン化読取り−修正−書込みアクセスを備えたＥＣＣ保護メモリ編成」の名称で、Chien ChenおよびYuzhi Luによって1995年３月３日に出願
【特許文献２１】米国特許出願番号 08/398,299 、「精密な状態を保持するため命令状態をトラッキングするプロセッサ構造および方法」の名称で、Chien Chen、John R. F. S. Szeto 、Niteen A. Patkar、Michael C. Shebanow 、Hideki Osone、Takumi Maruyama およびMichael A. Simoneによって1995年３月３日に出願
【００２３】
【特許文献２２】米国特許第３９６３９０８号明細書
【発明の開示】
【発明が解決しようとする課題】
【００２４】
サーチメカニズムに依存して、二重エントリーの位置に関連する出力は誤りとなる。誤ったローがフラグされて出力され、又は両ローからのデータの結合が選択されて出力されるからである。
【００２５】
多数の同等インデックスエントリーの検出を可能にする出力回路を設計することは、出力回路に複雑性を加えることになり、それによりシステム性能が劣化し、集積回路上の様々なスペースが必要となる。出力回路の性能に対して重大な劣化をもたらすことなく、又は集積回路上に大きなスペースを必要とすることなく、そのような状態を検出することが望まれる。
【課題を解決するための手段】
【００２６】
発明の要旨
本発明による方法および装置は、複数のコラムと複数のローとの交差部にデータを格納可能なエントリーを有するルックアップテーブルのルックアップしたエントリーの重複検査方法であって、コンピュータにより複数の異なる数をコラムの中の第１のコラムに含まれる複数のテーブル・エントリーにそれぞれ格納するとともに、異なる数の補数である複数のエラー検出コードをコラムの中の第２のコラムに含まれる複数のテーブル・エントリーに格納し、ローのうちの２つのローに対応する異なる数に対するルックアップ結果の論理和を第１の論理回路により第１のコード部とするとともに、ローのうちの２つのローに対応するエラー検出コードに対するルックアップ結果の論理和を第２の論理回路により第２のコード部とし、第１のコード部と第２のコード部のいずれか一方の補数を第３の論理回路により第３のコード部とし、第１のコード部と第２のコード部のうち補数を取られなかったコード部を第４の論理回路により第４のコード部とし、比較手段により第３のコードを第４のコードと比較し、第第３のコード部が第４のコード部と等しい場合は、ルックアップテーブルに二重エントリーが存在しないと判定して、電子的論理設計を継続し、第３のコード部が第４のコード部と等しくない場合は、ルックアップテーブルに二重エントリーが存在すると判定して、電子的論理設計を中断することを特徴とする、ルックアップしたエントリーの重複検査方法および装置である。
【発明を実施するための最良の形態】
【００２７】
好ましい実施例の簡単な記載
図１において、コラムおよびローの他の数を使用できるが、４コラム、３ローのルックアップテーブルが示されている。１実施例においては、非繰り返しコラム１２４として指定されるコラムは数の非繰り返しのセットを含んでいる。数の非繰り返しのセットとは、セットの２つの要素が等しくない数のセットのことをいう。要求はされないが、任意の繰り返し数を持つことが殆ど有り得ない非繰り返しコラムを持つことが有効である。１実施例においては、非繰り返し数は、ロー０から始まる２進フォーマットでのロー番号であり、これらのロー番号１２６、１２８、１３０はＲＯＭに格納され、それによりそれらのロー番号はコラム１２４における繰り返し数を生じ得るエラーにさらされることが極めて少なくなる。ロー番号は図１に示されるように格納されるか、それらは以下に記載のようにローに対するエラーコードの計算の直前に要求に応じて生成される。
【００２８】
第２のコラム１２０は、インデックスコラムとして指定され、「ルックアップ」即ち検索されて１つ以上の特定数に等しいコラム１２０内のエントリーを捜し出すための数のセットを含む。１実施例においては、インデックスコラム１２０は、すべてがユニークで各サーチに対して１つのエントリーのみを生成する数のセットを含むと考えられる。この実施例においては、本発明が用いられてインデックスコラム１２０内の２重のエントリー、即ち、コラム１２０の１つのロー内の数であってそれがコラム１２０の他のロー内で少なくとも１回繰り返されるもの、を検出する。他の実施例においては、本発明は結果的に２つ以上のエントリーを生ずる任意のサーチを検出するために使用される。
【００２９】
１実施例においては、サーチイネーブルコラム１２２が提供されて、特定の値を持つサーチイネーブルコラム１２２内のエントリーと同一のロー内にあるインデックスコラム１２０内のエントリーに対するサーチを制限する。例えば、ロー１および２は値１を持つコラムエントリー１４６，１４８を有するので、これらのローのみがサーチに含まれ、ロー０はスキップされ、即ちサーチされない。サーチイネーブルコラム１２２の使用は本発明によっては要求されない。
【００３０】
本発明においては、いくつかの又はすべてのローのエラー検出コードはそのローに対する非繰り返しコラム１２４のエントリーに基づいて生成され、そのローに結合され、そのエラー検出コードが生成されたローから以下に記載のようにエラーの検出を可能にする。エラー検出コードはコラム１５０内のエントリー１５４，１５６，１５８に格納されるか、又は必要に応じて生成される。
【００３１】
エラー検出コード内のビット数はｌｏｇ２ Ｎ以上である。ここでＮは、少なくとも、非繰り返しコラム１２４内の非繰り返し数１２６、１２８、１３０を表すために要求されるビット数である。１実施例においては、エラー検出コードは、非繰り返しコラム内の“１”といった特定の値に等しいビット数の補数に等しい。２進数の補数は、各オリジナルの“１”を“０”で置き換え、各オリジナルの“０”を“１”で置き換えた２進数に等しい。例えば、１０に等しい非繰り返し数１３０のためのエラーコードを生成するためには、数１０は“１”に等しい１ビットを有する。１は２進数の０１で表され、０１の補数は１０である。
【００３２】
さて図２Ａを参照すると、２ビットワードにおけるセットビットの数の計数の補数を生成する装置の１実施例が示されている。ワード内の各ビット２１０，２１２は排他的ＮＯＲゲート２１４に接続されてその装置の下位出力を生成する。２ビット２１０，２１２は２入力ＮＡＮＤゲート２１８に接続されてその装置の上位出力を生成する。出力２１６，２２０は２つのビット２１０，２１２に対応するローに接続される。図１および図２Ａにおいて、２つのビット２１０，２１２は非繰り返しコラム１２４の単一ロー内のビットに対応している。出力２１６，２２０は、２つのビット２１０，２１２が来た同じロー内のコラム１５０に格納され得る。これに替えて、出力２１６，２２０は、以下に記載のインデックスコラム１２０上のサーチが実行される時又はその近くの時に計算できる。
【００３３】
他の実施例においては、セットビットの数の補数を計算するために、非繰り返しコラムのビットは１つ以上の高速アダーに入力され得る。図２Ｂにおいて、高速アダー２５０、２５２、２５４、２５６が６ビットワード内のセットビットの数の計数の補数を得ることを可能にする接続が示されている。
【００３４】
下位ビットであるビット０はアダーの入力２７１に接続されており、残りのビット１，２，３，４，および５はそれぞれ入力２６８、２６６、２６４、２６３、および２６０に接続されている。キャリー入力２７０は論理０に接続されており、他の方法では出力として使用されない。アダーの出力２８２、２８４、２８６は入力２７１、２６８、２６６、２６４、２６２、２６０におけるセットビットの数の計数を生成する。出力２８２、２８４、２８６は、計数の補数をとって出力２９６、２９８、２９９にエラー検出コードを生成するインバータ２９０、２９３、２９４を用いて反転される。
【００３５】
図２Ｃは本発明による、入力におけるセットビットの数の計数２３０、２３２に等しい２ビット出力２３６、２４０を生成するデバイスの概略図である。
１実施例においては、テーブル１１０に対する従来のサーチ機能が、予め選択された数に一致するインデックスコラム１２０内のエントリーを持つインデックスコラム１２０内のローを探索することにより実行される。図１および図３Ａにおいて、コラム１２０内のエントリーが特定の数に一致するかどうかを判定するための装置が示されている。その特定の数は排他的論理和ゲート３１４に接続された入力３２０に与えられる。コラム１２０の１つのロー３１０内の各ビット３４０、３４２、３４４は排他的論理和ゲート３１４の１つの第２の入力３２２に接続され、その排他的論理和ゲート３１４は、ビット３４０、３４２、３４４が対応する入力３２０に等しい場合にハイを出力する。排他的論理和ゲート３１４は、すべてのビット３４０、３４２、３４４が対応する入力３２０に一致するとハイを出力する出力３１８を有するＡＮＤゲート３１６に接続されている。出力３１８はＡＮＤゲート３１５の第１の入力に接続されている。入力３３０、３３２、３３４はその位置に対応するビット３４０、３４２、３４４を受けるように接続されており、コラム１２０内のロー３１０が入力３２０と一致すると出力ライン３２１上にこのビットが出力される。
【００３６】
図１、図３Ａおよび図３Ｂを参照して、１実施例において、出力３１８はＡＮＤゲート３５０、３５２に接続されており、そのＡＮＤゲート３５０、３５２は、入力３７０、３７２で提供されたコラム１５０からのエラーコードビット３６０、３６２を、非繰り返しコラム１２４の１つ又は複数の選択されたローに対応する出力３８０上にドライブするために接続されている。
【００３７】
１実施例において、選択された１つ又は複数のローは、インデックスコラム１２０内のエントリーで予め選択された数に一致するものを持つすべてのローの論理的ＯＲをとることにより出力される。論理的ＯＲを取る手段、即ち、論理和を取る手段は各ビットの論理和を計算する。例えば、１００と１０１とのＯＲ即ち論理和は１０１である。論理的ＯＲの機能は集積回路内で実現するために効率的であるが、論理的ＯＲを取ることは１つだけの数が期待されている時に２つの数のＯＲが取られたという事実をマスクできる。図１及び図４において、ＯＲゲート４６０、４６２、４６４、４６６、４６８を用いて出力４５０、４５２、４５４、４５６、４５８を生成するための論理的ＯＲをとる入力４４０、４４２、４４４、４４６、４４８のための装置が示されている。ボックス４２０内のコラムは非繰り返しコラム１２０の各エントリー内の個々のビットを表しており、ボックス４２２は図４内の各ボックスが１ビットを保持している場合のエラーコードコラムを表している。このようなＯＲを取る機能は図においては厄介なものであるが、集積回路においては、このような機能は上記のように多数の一致出力エラーをマスクするが極めて効率的である。
【００３８】
選択されたロー又はＯＲが取られたローに対応する非繰り返しコラムエントリー及びエラーコードが出力４５０、４５２、４５４、４５６、４５８に現れた後に、選択された１つ又は複数のローの非繰り返しコラム１２４に対応するＯＲが取られた出力４５０、４５２、４５４を用いて、再計算されたエラーコードが計算される。再計算されたエラーコードはエラーコードコラム１５０に対応するＯＲが取られた出力４５６、４５８と比較される。１つだけのエントリーが出力された場合は、エラーコードコラム１５０に対応する出力４５６、４５８は再計算されたエラーコードに等しくなる筈である。そうでない場合は、そのような同一性は現れない。図２Ａ又は図２Ｂに示した装置又はその装置の組合せは再計算されたエラーコードを計算するために使用される。
【００３９】
図５において、同等性を検出する装置の１実施例が示されている。ＯＲが取られたエラーコード及び再計算されたエラーコードは図５に示した装置を用いてビット法で等価性がテストされる。ＯＲがとられたエラーコードからの下位ビットは排他的論理和ゲートの入力５１０に接続され、上位ビットは排他的論理和ゲートの入力５１４に接続される。再計算されたエラーコードからの下位ビットは排他的論理和ゲートの入力５１２に接続され、上位ビットは排他的論理和ゲートに入力５１６に接続される。１実施例においては、ゲート５２２は２入力ＯＲゲートであり、ＯＲが取られたエラーコードが再計算されたエラーコードに等しくない場合は出力５２４にハイを出力し、上記のような二重選択によるエラーの可能性が存在することを知らせる。
【００４０】
他の実施例においては、ゲート５２２はＮＯＲゲートであり、反対の信号を出力する。他の実施例においては、ゲート５２２はオープンコレクタのＯＲゲートであり、単一の信号を出力する。
【００４１】
図４を参照して、他の実施例においては、再計算されたエラーコードは上記した方法と異なる方法で計算される。再計算されたエラーコードはＯＲされたセットビット４５６、４５８の和である。ＯＲされたエラーコード及び再計算されたエラーコードは、より単純な回路を提供するために、ビット単位で等価性のテストがされ。例えば、非繰り返しコラムエントリーにおいて、図２Ｃの装置が用いられ、これは出力２４０、２３６が図２Ａの出力２２０、２１６から反転されている点を除き、図２Ａと同じである。他の実施例においては、インバータ２９０、２９２、２９４なしで図２Ｂの装置が用いられる。この代わりに、出力２８２、２８４、２８６は出力２９６、２９８、２９９と置き代わる。そのような装置が使用されるとき、ＯＲがとられたエラーコードの各ビットは再計算されたエラーコードの反対の筈であるか、又は多数選択エラーが生じたかである。この状況を検出するために、ゲート５２２が等価性を検出するためのＡＮＤゲート、ＮＡＮＤゲート、又はオープンコレクタバージョンであることを除き、図５の装置が上記のように使用される。
【００４２】
図６Ａにおいて、本発明の方法の１実施例が示されている。ステップ６１０で、２つ以上のローのエラーコードは、非繰り返しコラム内のエントリー内にセットされたビットの数を計算し補数を得ることにより生成される。次いで、ステップ６１２で、その生成されたエラーコードは、そのエラーコードが生成された非繰り返しコラムからのエントリーと関係付けられる。次いで、ステップ６１４で、例えば、予め選択された数に一致している１つのコラム内のデータを含むすべてのローを選択することにより、あるローが選択される。次いで、ステップ６１６で、選択されたロー内の対応するビットは互いに論理的にＯＲが取られる。次いで、ステップ６１８で、非繰り返しコラム内の結果的にＯＲが取られたエラーコードは、非繰り返しコラム内にセットされた論理的にＯＲされたビットの数を計数し、その計数の補数をとることにより再計算される。次いでステップ６２０で、再計算されたエラーコードはコラムの結果的に得られるＯＲされたエラーコードと比較される。次いでステップ６２２で、再計算されたエラーコードがＯＲされたエラーコードに等しい場合は、第１の信号が生成される。再計算されたエラーコードがＯＲされたエラーコードに等しくない場合は、ステップ６２４で、第２の信号が生成される。第１及び第２の信号は多数一致の欠如又は存在を示す。第１の信号及び第２の信号の生成は、等価性又は非等価性が検出される場合にのみ単一の信号の生成で置き換えることができ、そうでない場合には信号は生成されない。
【００４３】
図６Ｂにおいて、本発明の他の方法が示されている。この方法は、ステップ６１９で、再計算されたエラーコードは、セットされたビットの数を計数することにより計算され、ステップ６２１で再計算されたエラーコードとＯＲがとられたエラーコードとをビット単位で非等価性のためにテストすることにより比較６２１が遂行されることを除き、図６Ａと同様に動作する。
【図面の簡単な説明】
【００４４】
【図１】メモリ内に配置された従来のルックアップテーブルの概略ブロック図である。
【図２Ａ】本発明による、入力におけるセットビット数の計数の補数に等しい２ビット出力を生成するデバイスの概略図である。
【図２Ｂ】本発明による、６ビットワード内のセットビットの数の計数の補数を与えるために使用される４つの高速アダーと３つのインバータを示す概略図である。
【図２Ｃ】本発明による、入力におけるセットビットの数の計数に等しい２ビット出力を生成するデバイスの概略図である。
【図３Ａ】第２の入力に等しい第１の入力を出力ラインのセットにドライブする従来の回路の概略図である。
【図３Ｂ】一対のビットを出力ラインのセットにドライブする従来の回路の概略図である。
【図４】グループ当たり３ビットの５つのグループの論理的ＯＲを取る従来の回路の概略図である。
【図５】本発明によるエラー検出回路の概略図である。
【図６Ａ】本発明による方法を示すフローチャートである。
【図６Ｂ】本発明による他の方法を示すフローチャートである。
【図１】
0003996623.tif 000002
【図２Ａ】
0003996623.tif 000003
【図２Ｂ】
0003996623.tif 000004
【図２Ｃ】
0003996623.tif 000005
【図３Ａ】
0003996623.tif 000006
【図３Ｂ】
0003996623.tif 000007
【図４】
0003996623.tif 000008
【図５】
0003996623.tif 000009
【図６Ａ】
0003996623.tif 000010
【図６Ｂ】
0003996623.tif 000011