(57)【要約】【課題】１個の論理関数メモリを用いて構成された、高速演算が可能なルックアップテーブル・カスケード論理回路を提供する。【解決手段】分解関数ｆｋの関数値が分解関数ルックアップテーブルＴｋとして格納された論理関数メモリ２と、入力ラインの一部に入力変数Ｘが入力され、他の一部は論理関数メモリ２の出力端子に接続され、出力ラインは論理関数メモリ２の入力端子に接続され、両ラインのスイッチ回路を備えた接続回路６と、スイッチ回路の切換情報を、接続情報テーブルＣｋとして記憶する接続メモリ７と、分解関数ｆｋの演算制御を、演算段数ｋの昇順に逐次行う演算制御手段１１とを具備した。【選択図】          図１
2004258799.tif 000002
【特許請求の範囲】
【請求項１】
入力変数Ｘ＝（ｘ１，…，ｘｎ）を有する目的論理関数ｆ（Ｘ）を関数分解して得られる分解関数｛ｆｉ；ｉ＝１，…，ｐ｝を、逐次計算することにより、目的論理関数ｆ（Ｘ）の演算を行うルックアップテーブル・カスケード論理回路であって、
複数の入力端子と複数の出力端子とを有し、前記分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）に対応する領域番号ｐｋにより指定されるアドレス領域に、前記分解関数ｆｋの関数値が分解関数ルックアップテーブルとして格納された論理関数メモリと、
複数の入力ラインと複数の出力ラインとを備え、前記入力ラインの一部には前記入力変数Ｘが入力され、前記入力ラインの他の一部は前記論理関数メモリの出力端子に接続され、前記出力ラインは前記論理関数メモリの入力端子に接続されており、前記各入力ラインと前記各出力ラインとの接続を切り換えるスイッチ回路を具備している接続回路と、
前記各分解関数ｆｋに対して、前記接続回路の入力ラインに入力される入力変数Ｘ、及び論理関数メモリの出力端子から出力される分解関数ｆｋ−１の出力変数Ｙｋの接続関係を、前記分解関数ルックアップテーブルを参照するために前記論理関数メモリの入力端子に入力する入力変数の順序に整合するように、前記接続回路内のスイッチ回路を切り換えるための情報を、接続情報テーブルとして記憶する接続メモリと、
前記論理関数メモリに対し前記領域番号ｐｋを指定して前記分解関数ルックアップテーブルを参照可能にするとともに、前記接続メモリに記憶された接続情報テーブルに従って前記接続回路内のスイッチ回路の切換を行い、前記論理関数メモリの出力端子から前記分解関数ｆｋの関数値を出力させる一連の制御を、演算段数ｋの昇順に逐次行う演算制御手段と、
を備えていることを特徴とするルックアップテーブル・カスケード論理回路。
【請求項２】
前記入力変数Ｘの一部を選択して出力端子から出力する入力変数選択回路を備え、
前記接続回路の前記入力ラインの一部は、前記入力変数選択回路の出力端子に接続されており、
前記演算制御手段は、前記分解関数ｆｋの演算を行う際には、前記入力変数選択回路に対し、少なくとも入力変数Ｘのうち、前記分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）の演算に使用される入力変数Ｘｋ（Ｘｋ∈Ｘ）を選択させるように制御すること
を特徴とする請求項１記載のルックアップテーブル・カスケード論理回路。
【請求項３】
前記出力回路は、ｗチャンネル１出力（ｗ≧２）のマルチプレクサを多段にカスケード接続し、各段において、出力を取り出せるように構成したことを特徴とする請求項１又は２記載のルックアップテーブル・カスケード論理回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム可能な論理回路に係り、特に、目的論理関数を関数分解して得られる分解関数を、逐次計算することにより、目的論理関数の演算を行うルックアップテーブル・カスケード論理回路に関する。
【０００２】
【従来の技術】
従来より、回路構成をプログラムすることが可能な論理回路として、フィールド・プログラマブル・ゲートアレイ（以下、「ＦＰＧＡ」という。）が知られている。ＦＰＧＡは、多くの論理セルがアレイ状に配列され、これらの論理セルのデータ及び論理セル間を接続する配線を自由に変更できるように構成される。ＦＰＧＡはハードウェア的に演算を行うことから、マイクロ・プロセッサ（以下、「ＭＰＵ」という。）により論理関数の演算を実行する場合に比べると、実行速度が速いという特徴を有する。そのため、近年では各種電子回路に多く使用されるようになってきている。その一方、ＦＰＧＡは、物理的な配線の引き回しをプログラムにより変更することから、配線遅延を考慮した設計が必要であり、設計に長時間を要する。また、論理セル間の配線の引き回しの仕方により演算時間が変わるため、設計時において演算時間の予測が困難である。
【０００３】
そこで、ＦＰＧＡの上記のような欠点をカバーするプログラム可能な論理回路として、ルックアップテーブル・カスケード論理回路が提案されている（非特許文献１参照）。以下、ルックアップテーブル・カスケード論理回路について簡単に説明する。
【０００４】
図１４はルックアップテーブル・カスケード論理回路の原理を表す図である。
【０００５】
まず、演算を行う論理関数を目的論理関数ｆと呼ぶことにする。また、目的論理関数の入力変数をＸ＝（ｘ１，ｘ２，…，ｘｎ）で表し、Ｘの変数の集合を｛Ｘ｝で表す。更に、Ｘの変数の個数を｜Ｘ｜で表す。
【０００６】
このとき、目的論理関数ｆは、二分決定グラフ（以下、「ＢＤＤ」という。）を用いた関数分解手法等を利用して、図１４に示すように、ｐ個の論理関数に分解することができる。以下、目的論理関数ｆを分解して得られる論理関数を分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）という。図１４において、Ｘ１，…，Ｘｐは入力変数Ｘを分割したものであり、｛Ｘ１｝∪…∪｛Ｘｐ｝＝｛Ｘ｝、｛Ｘｉ｝∩｛Ｘｊ｝＝φ（ｉ≠ｊ、ｉ，ｊ∈｛１，…，ｐ｝）である。ｊ段目（ｊ∈｛１，…，ｐ−１｝）の分解関数ｆｊの出力変数Ｙｊ＝（ｙｊ，１，…，ｙｊ，ｕｊ）は、ｊ＋１段目の分解関数ｆｊ＋１に入力される。ここで、ｕｊは、分解関数ｆｊの出力変数Ｙｊの個数｜Ｙｊ｜を表す。
【０００７】
また、｜Ｘｉ｜＝ｎｉ（ｉ∈｛１，…，ｐ｝）とすると、ｎ１＝ｓ（ｓは分解関数ｆｉの入力変数の数）、ｎｉ＝ｓ−ｕｉ−１（１＜ｉ＜ｐ）、ｎｐ＝ｓ−ｕｐ−１−ｔ（０≦ｔ≦ｓ−２）となるように関数分解することができる。
【０００８】
このように、目的論理関数ｆをｐ−１個のｓ入力の分解関数ｆｊ（ｊ∈｛１，…，ｐ−１｝）と１個のｓ−ｔ入力の分解関数ｆｐとに分解する。そして、各分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）を、分解関数ｆｋの真理値表からなる分解関数ルックアップテーブルＴｋとして構成する。それぞれの分解関数ルックアップテーブルＴｋは、ｓ入力ｕｋ出力の論理関数メモリを用いて実現できる。
【０００９】
ルックアップテーブル・カスケード論理回路は、目的論理関数ｆの入出力数が大きい場合には、多数のルックアップテーブルをカスケード接続することとなるため、最適化されたＦＰＧＡに比べて演算速度は劣る。しかし、ルックアップテーブル・カスケード論理回路は、論理関数メモリを用いて演算をハードウェア的に行うために、ＭＰＵに比べ演算速度の高速化が期待できる。そして、ルックアップテーブルの段数によって一義的に演算速度が決まることから、設計時に目的論理関数の演算時間の予測も容易である。また、隣接するルックアップテーブルの間でのみ配線を行えばよいため、配線遅延を考慮する必要がなく、設計も容易となる。
【００１０】
【非特許文献１】
笹尾勤，松浦宗寛，井口幸洋，“多出力関数のカスケード実現と再構成可能ハードウェアによる実現”，電子情報通信学会ＦＴＳ研究会，  ＦＴＳ２００１−８，  ｐｐ．  ５７−６４，  三重大学（２００１−０４）．
【非特許文献２】
Ｔ．  Ｓａｓａｏ，  Ｍ．  Ｍａｔｓｕｕｒａ，  ａｎｄ  Ｙ．  Ｉｇｕｃｈｉ，  ”Ａ  ｃａｓｃａｄｅ  ｒｅａｌｉｚａｔｉｏｎ  ｏｆ  ｍｕｌｔｉｐｌｅ−ｏｕｔｐｕｔ  ｆｕｎｃｔｉｏｎ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ｈａｒｄｗａｒｅ，”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｌｏｇｉｃ  ａｎｄ  Ｓｙｎｔｈｅｓｉｓ  （ＩＷＬＳ０１），  Ｌａｋｅ  Ｔａｈｏｅ，  ＣＡ，  Ｊｕｎｅ  １２−１５，  ２００１．  ｐｐ．２２５−２３０．
【００１１】
【発明が解決しようとする課題】
上記のルックアップテーブル・カスケード論理回路を実現する場合、単純に考えるとｐ個の論理関数メモリをカスケード接続すればよい。しかしながら、これを１個の論理関数メモリを用いて実現しようとした場合、分解関数ｆｋの演算を行うときには、外部から入力変数Ｘｋを論理関数メモリに入力すると共に、論理関数メモリから出力される前段の分解関数ｆｋ−１の出力変数Ｙｋ−１を再度論理関数メモリに入力する必要がある。
【００１２】
上記非特許文献１には、１個の論理関数メモリを用いて実現されたルックアップテーブル・カスケード論理回路として、シーケンサを用いて論理関数メモリの入出力の接続を切り換える構成のルックアップテーブル・カスケード論理回路のアーキテクチャが示されている。しかしながら、シーケンサを用いた場合、入出力の接続切り換えに時間がかかるため、高速なルックアップテーブル・カスケード論理回路の実現が困難である。
【００１３】
そこで、本発明の解決すべき課題は、１個の論理関数メモリを用いて構成された、高速演算が可能なルックアップテーブル・カスケード論理回路を提供することにある。
【００１４】
【課題を解決するための手段】
本発明に係るルックアップテーブル・カスケード論理回路は、入力変数Ｘ＝（ｘ１，…，ｘｎ）を有する目的論理関数ｆ（Ｘ）を関数分解して得られる分解関数｛ｆｉ；ｉ＝１，…，ｐ｝を、逐次計算することにより、目的論理関数ｆ（Ｘ）の演算を行うルックアップテーブル・カスケード論理回路であって、複数の入力端子と複数の出力端子とを有し、前記分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）に対応する領域番号ｐｋにより指定されるアドレス領域に、前記分解関数ｆｋの関数値が分解関数ルックアップテーブルとして格納された論理関数メモリと、複数の入力ラインと複数の出力ラインとを備え、前記入力ラインの一部には前記入力変数Ｘが入力され、前記入力ラインの他の一部は前記論理関数メモリの出力端子に接続され、前記出力ラインは前記論理関数メモリの入力端子に接続されており、前記各入力ラインと前記各出力ラインとの接続を切り換えるスイッチ回路を具備している接続回路と、前記各分解関数ｆｋに対して、前記接続回路の入力ラインに入力される入力変数Ｘ、及び論理関数メモリの出力端子から出力される分解関数ｆｋ−１の出力変数Ｙｋの接続関係を、前記分解関数ルックアップテーブルを参照するために前記論理関数メモリの入力端子に入力する入力変数の順序に整合するように、前記接続回路内のスイッチ回路を切り換えるための情報を、接続情報テーブルとして記憶する接続メモリと、前記論理関数メモリに対し前記領域番号ｐｋを指定して前記分解関数ルックアップテーブルを参照可能にするとともに、前記接続メモリに記憶された接続情報テーブルに従って前記接続回路内のスイッチ回路の切換を行い、前記論理関数メモリの出力端子から前記分解関数ｆｋの関数値を出力させる一連の制御を、演算段数ｋの昇順に逐次行う演算制御手段と、を備えていることを特徴とする。
【００１５】
この構成によれば、分解関数ｆｋの演算を行う場合、演算制御手段は、前記論理関数メモリに対し前記領域番号ｐｋを指定して前記分解関数ルックアップテーブルを参照可能にする。それとともに、接続メモリに記憶された接続情報テーブルに従って接続回路内のスイッチ回路の切換を行う。これにより、接続回路の出力ラインからは、分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）の演算に使用される変数Ｘｋ（Ｘｋ∈Ｘ）又は変数Ｙｋが出力される。論理関数メモリは、出力ラインから入力される変数Ｘｋ（Ｘｋ∈Ｘ）又は変数Ｙｋの値を参照して、分解関数ルックアップテーブルから分解関数ｆｋの関数値を出力する。
【００１６】
演算制御手段は、このような演算をｋ＝１からｐまで繰り返すことにより、目的論理関数ｆを演算することができる。
【００１７】
ここで、接続回路内のスイッチ回路の切換は接続メモリに記憶された接続情報テーブルに従って行われる。これにより、接続回路内のスイッチ回路の切換動作は短時間で行われる。そのため、目的論理関数ｆの演算速度を高速化することが可能となる。
【００１８】
また、目的論理関数のプログラムは、論理関数メモリ、接続メモリに対して分解関数ルックアップテーブル、接続情報テーブルを書き込むだけでよいため、設計が極めて簡単となる。また、配線は固定されているため、ＦＰＧＡのように、物理的な配線の引き回しの設計を必要がなく、設計時に配線遅延の考慮は不要である。従って、効率的な論理演算回路の設計ができる。更に、分解関数ｆｋの数が決まれば、演算時間も一意的に決まることから、設計時に演算時間の予測が容易にできる。
【００１９】
尚、上記「接続回路」としては、クロスバスイッチ、マルチプレクサ、バレル・シフタ等を使用することができる。
【００２０】
また、本発明に係るルックアップテーブル・カスケード論理回路においては、更に、前記入力変数Ｘの一部を選択して出力端子から出力する入力変数選択回路を備え、前記接続回路の前記入力ラインの一部は、前記入力変数選択回路の出力端子に接続されており、前記演算制御手段は、前記分解関数ｆｋの演算を行う際には、前記入力変数選択回路に対し、少なくとも入力変数Ｘのうち、前記分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）の演算に使用される入力変数Ｘｋ（Ｘｋ∈Ｘ）を選択させるように制御する構成とすることができる。
【００２１】
この構成によれば、入力変数選択回路により、入力変数Ｘの一部を選択して接続回路の入力ラインに入力することで、接続回路の入力ラインの本数を減らすことができる。そのため、入力ラインと出力ラインとの交点数が減少する。従って、接続回路を小型化することができる。また、接続情報テーブルＣｋが小さくなる。従って、接続メモリのメモリ容量を減少させることも可能となり、回路が小型化される。
【００２２】
また、本発明に係るルックアップテーブル・カスケード論理回路においては、前記出力回路は、ｗチャンネル１出力（ｗ≧２）のマルチプレクサを多段にカスケード接続し、各段において、出力を取り出せるように構成することができる。
【００２３】
この構成により、多出力論理関数の演算を行う場合、複数の出力を取り出すことが可能となり、多出力論理関数の演算を複数の出力に関して同時に行うことが可能となる。従って、多出力論理関数の演算速度の向上を図ることができる。
【００２４】
【発明の実施の形態】
以下、本発明の一実施形態について、図面を参照しながら説明する。
【００２５】
（実施形態１）
図１は本発明の実施形態１に係るルックアップテーブル・カスケード論理回路のブロック図である。
【００２６】
本発明の実施形態１に係るルックアップテーブル・カスケード論理回路１は、論理関数メモリ２、入力変数レジスタ３、入力変数選択回路４、入力選択メモリ５、接続回路６、接続メモリ７、出力回路８、出力選択メモリ９、出力レジスタ１０、及び演算制御部１１を備えている。
【００２７】
論理関数メモリ２は、目的論理関数ｆを関数分解して得られるｐ個の分解関数ｆｋ（ｋ∈｛１，…，ｐ｝）の関数値が、ルックアップテーブルＴｋとして記憶されている。この論理関数メモリ２は、複数の入力端子と複数の出力端子を備えており、入力端子から入力される入力変数により指定されるルックアップテーブルＴｋ内の関数値を、出力端子から出力する。
【００２８】
入力変数レジスタ３には、目的関数ｆの入力変数Ｘ＝（ｘ１，…，ｘｎ）が記憶される。入力変数選択回路４は、入力変数レジスタ３内に格納された入力変数Ｘのうちｍ個の入力変数（ｘｄｋ，…，ｘｄｋ＋ｍ−１）を選択して出力端子に出力する。入力選択メモリ５は、入力変数選択回路４に対し、入力変数Ｘの選択範囲を指定する入力選択データｄｋ（ｋ∈｛１，…，ｐ｝）を出力する。
【００２９】
接続回路６は、複数の入力ライン、複数の出力ライン、これらの入力ラインと出力ラインとの接続を行うためのスイッチ回路、及び各スイッチ回路の切換制御をするための複数の接続制御ラインを備えている。接続回路６の入力ラインのうちのｍ本は、入力変数選択回路４のｍ個の出力端子にそれぞれ接続されている。また、接続回路６の入力ラインの残りのものは、論理関数メモリ２の出力端子に接続されている。また、接続回路６の各出力ラインは、論理関数メモリ２の入力端子に接続されている。接続メモリ７は、各出力端子が接続回路６の各接続制御ラインに接続されている。そして、接続回路６内の各スイッチ回路を切り換えるための情報が、接続情報テーブルＣｋ（ｋ∈｛１，…，ｐ｝）として格納されている。
【００３０】
出力回路８は、複数の入力ラインと１本の出力ラインとを備えており、各入力ラインは、論理関数メモリ２の各出力端子に接続されている。出力回路８は、これらの入力ラインから入力されるデータから、１つを選択して出力ラインに出力する。また、出力選択メモリ９には、出力回路８が選択すべき入力ラインの情報である出力選択データが記憶されている。出力回路８は、この出力選択メモリ９に記憶された出力選択データに基づいて、データの選択を行う。出力レジスタ１０は、出力回路８の出力ラインに接続されており、出力回路８から出力される目的論理関数ｆの演算結果のデータを記憶する。
尚、本実施形態では、出力回路８の出力ラインを１本の場合について説明するが、本発明においては出力回路８の出力ラインの本数は２本以上であってもよい。
【００３１】
演算制御部１１は、論理関数メモリ２の入出力、入力選択メモリ５のデータ出力、接続メモリ７のデータ出力、及び出力選択メモリ９のデータ出力の制御を行うことによって、ルックアップテーブル・カスケード論理回路１の演算制御を行う。
【００３２】
図２は入力変数選択回路の回路構成図である。
【００３３】
図２において、本実施形態の入力変数選択回路４は、バレル・シフタ回路により構成されている。入力変数選択回路４は、各入力端子ｉｎ（０１）〜ｉｎ（１６）と出力端子ｏｕｔ（０１）〜ｏｕｔ（０８）を有する。入力変数選択回路４の入力端子ｉｎ（０１）〜ｉｎ（１６）は、入力レジスタ３の出力側に接続される。また、入力変数選択回路４の出力端子ｏｕｔ（０１）〜ｏｕｔ（０８）は、接続回路６の入力ラインに接続される。尚、図２では、入力変数選択回路４の入力は１６ビット、出力は８ビットの例を示しているが、本発明では入力変数選択回路４の入出力のビット数はこれに限られるものではない。
【００３４】
入力変数選択回路４は、入力端子ｉｎ（０１）〜ｉｎ（１６）の側から、８ビット・シフタ回路１５、４ビット・シフタ回路１６、２ビット・シフタ回路１７、及び１ビット・シフタ回路１８が直列接続された構成からなる。各シフタ回路１５，１６，１７，１８は、それぞれ制御ラインｓｈｆ４，ｓｈｆ３，ｓｈｆ２，ｓｈｆ１により制御される。各制御ラインｓｈｆ４〜ｓｈｆ１は、入力選択メモリ５に接続されている。そして、入力選択メモリ５から各制御ラインｓｈｆ４〜ｓｈｆ１に０が入力された場合、各シフタ回路１５〜１８は入出力ラインのシフトを行わない。一方、各制御ラインｓｈｆ４〜ｓｈｆ１に１が入力された場合、各シフタ回路１５〜１８は入出力ラインのシフトを行う。
【００３５】
尚、実際には、図２のようにシフタ回路を多段に接続すると、信号振幅が減衰する。従って、図２では省略しているが、実際には、減衰が大きい場合、シフタ回路の数段ごとに増幅器（バッファ）を挿入しておくことが必要となる。
【００３６】
図３は接続回路周辺の回路構成を表す図である。
【００３７】
図３において、入力変数選択回路４、接続回路６、及び接続メモリ７は、図１と同様のものであるため、同一の符号を付して説明は省略する。
【００３８】
本実施形態においては、接続回路６はクロスバスイッチとして構成されている。すなわち、接続回路６は、入力ラインｉ１〜ｉ１６と出力ラインｏ１〜ｏ８とが格子状に配列され、各入力ラインと各出力ラインとの交点は、パストランジスタからなるスイッチ回路を介して接続されている。
【００３９】
入力ラインｉ１〜ｉ８は、入力変数選択回路４の出力端子に接続されており、入力ラインｉ９〜ｉ１６は、論理関数メモリ２の出力端子に接続されている。また、出力ラインｏ１〜ｏ８は、論理関数メモリ２の入力端子に接続されている。Ｎｃ＝１６×８個のパストランジスタのゲートは、それぞれ、Ｎｃ個の接続メモリ７の出力端子に接続されている。そして、各パストランジスタは、接続メモリ７の出力端子に現れる出力値によって同時に切換が行われる。
【００４０】
尚、本実施形態においては、一例として、接続回路６の入力ライン本数は１６本、出力ライン本数は８本としたが、本発明では、接続回路６の入出力ラインの本数はこれらの数に限るものではない。
【００４１】
図４は接続メモリの構成を表すブロック図である。
【００４２】
図４において、接続メモリ７の内部には、ｐ個のメモリアレイＣＭ１〜ＣＭｐが備えられている。各メモリアレイＣＭ１〜ＣＭｐには、接続回路６内のＮｃ個のパストランジスタのオン／オフ情報をビットマップで表した接続情報テーブルＣ１〜Ｃｐが記憶されている。これらのメモリアレイＣＭ１〜ＣＭｐのＮｃ個の出力端子は、接続回路６内の各パストランジスタのゲートに接続されている。
【００４３】
また、接続メモリ７の内部には、ページデコーダ２１が設けられている。ページデコーダ２１は、演算制御部１１から入力される段数指定ｋに従って、ｋ番目のメモリアレイＣＭｋを選択する。ページデコーダ２１により選択されたメモリアレイＣＭｋは、Ｎｃビットの接続情報テーブルＣｋを出力端子に出力する。
【００４４】
図５は論理関数メモリの構成を表すブロック図である。
【００４５】
図５において、論理関数メモリ２は、内部にｐページからなるメモリアレイＦＭ１〜ＦＭｐを備えている。これらのメモリアレイＦＭ１〜ＦＭｐには、分解関数ｆ１〜ｆｐの関数値が分解関数ルックアップテーブルＴ１〜Ｔｐとして記憶されている。
【００４６】
また、論理関数メモリ２は、ページデコーダ２２を有している。ページデコーダ２２は、演算制御部１１から入力される領域選択番号ｐｋに基づいて、メモリアレイＦＭｋを選択する。更に、論理関数メモリ２は、アドレスデコーダ２３を有している。アドレスデコーダ２３は、Ｎｉｎ＝８個の入力端子から入力される変数（Ｘｋ，Ｙｋ）に基づき、メモリアレイＦＭｋ内のアドレスを選択する。この選択されたアドレスのメモリセルには、分解関数ｆｋの関数値ｆｋ（Ｘｋ，Ｙｋ）が格納されている。メモリアレイＦＭｋは、ページデコーダ２２及びアドレスデコーダ２３によりメモリセルのアドレスが指定されると、当該メモリセル内に記憶されているデータを、出力変数Ｙｋ＋１＝（ｙｋ＋１，１，…ｙｋ＋１，｜Ｙｋ＋１｜）として、出力端子に出力する。
【００４７】
尚、本実施形態においては、一例として、論理関数メモリ２の入出力のビット数は８ビットとしたが、本発明では、論理関数メモリ２の入出力のビット数はこれらの数に限るものではない。
【００４８】
以上のように構成された本実施形態に係るルックアップテーブル・カスケード論理回路において、以下その動作を説明する。
【００４９】
図６は本実施形態に係るルックアップテーブル・カスケード論理回路の動作を表すフローチャートである。
【００５０】
まず、目的関数ｆの演算が開始されると、演算制御部１１は、演算段数を表すカウンタｋを１に設定する（Ｓ１）。そして、演算制御部１１は、接続メモリ７のページデコーダ２１に対してｋページの選択を指示する。ページデコーダ２１は、接続メモリ７の指示に従って、ｋページのメモリアレイＣＭｋを選択する。選択されたメモリアレイＣＭｋは、その内部に記憶された接続情報テーブルＣｋを出力端子から出力する。それに伴い、接続情報テーブルＣｋのビットマップに従って接続回路６内の各スイッチ回路が切り換えられ、接続回路６の入力ラインと出力ラインとの接続がなされる（Ｓ２）。
【００５１】
また、接続回路６の接続設定とともに、演算制御部１１は、入力選択メモリ５に対して、ｋ段目の入力選択データｄｋの出力を指示する。ここで、入力選択データｄｋは、出力ラインに対する入力ラインのシフト量を２進表示した値からなるデータである。入力選択メモリ５はこの指示を受けて、入力変数選択回路４の制御ラインｓｈｆ１〜ｓｈｆ４に対し、入力選択データｄｋを出力する。これにより、入力変数選択回路４の出力端子には、入力変数｛ｘｄｋ，ｘｄｋ＋１，…，ｘｄｋ＋ｍ−１｝（本実施形態では、ｍ＝８としているが、一般にはｍの値はこれに限られない。）が出力される（Ｓ３）。すなわち、入力変数｛ｘｄｋ，ｘｄｋ＋１，…，ｘｄｋ＋ｍ−１｝が接続回路６のｍ本の入力ラインに入力される。一方、接続回路６の他の入力ラインには、論理関数メモリ２の出力ラインからの出力変数Ｙｋ＝（ｙｋ，１，ｙｋ，２，…，ｙｋ，｜Ｙｋ｜）が入力されている。尚、ｋ＝１のときには、Ｙ１はどんな値であってもよい。ｋ＝１のときは、論理関数メモリ２からの出力は使用しないからである。
【００５２】
このとき、接続回路６内の各スイッチ回路によって、入力ラインと出力ラインとは、接続情報テーブルＣｋのビットマップに従って接続されている。そのため、接続回路６の出力ラインには、Ｘｋ＝（ｘｄｋ，ｘｄｋ＋１，…，ｘｄｋ＋｜Ｘｋ｜−１）及びＹｋ（以下、出力ラインに出力されるＹｋを「中間変数」と呼ぶ。）が出力される。
【００５３】
次に、演算制御部１１は、論理関数メモリ２内のページデコーダ２２に領域選択番号ｐｋを出力する。ページデコーダ２２は、領域選択番号ｐｋに基づいて、メモリアレイＦＭｋを選択する（Ｓ４）。これにより、分解関数ｆｋに対する分解関数ルックアップテーブルＴｋが選択されたこととなる。
【００５４】
このとき、論理関数メモリ２の入力端子には、接続回路６の出力ラインから、入力変数Ｘｋ及び中間変数Ｙｋが入力されている。従って、アドレスデコーダ２３は、変数（Ｘｋ，Ｙｋ）に基づき、メモリアレイＦＭｋ内のメモリセルを選択する（Ｓ５）。
【００５５】
メモリアレイＦＭｋは、アドレスデコーダ２３によりメモリセルが選択されると、当該メモリセル内に格納された関数値ｆｋ（Ｘｋ，Ｙｋ）を、論理関数メモリ２の出力端子に出力する（Ｓ６）。
【００５６】
そして、演算制御部１１は、カウンタｋの値をインクリメントした後（Ｓ７）、カウンタｋの値がｐ以下であれば（Ｓ８）、上記ステップＳ２〜Ｓ８の動作を繰り返す。
【００５７】
ステップＳ８において、カウンタｋの値がｐを超えた場合、演算制御部１１は、出力選択メモリ９に対して出力指示を与える。出力選択メモリ９は、出力指示が与えられると、出力回路８に対して、論理関数メモリ２の出力端子の選択信号を出力する（Ｓ９）。そして、出力回路８は、当該選択信号に従って、論理関数メモリ２の出力端子の一つから出力される出力変数を、出力レジスタ１０へ出力する（Ｓ１０）。以上の動作によって、入力変数Ｘに対する目的関数ｆの演算結果ｆ（Ｘ）が出力レジスタ１０に得られる。
【００５８】
以上のように、本実施形態のルックアップテーブル・カスケード論理回路によれば、前段の分解関数の演算から次段の分解関数の演算への入力変数及び中間変数の受け渡しに、接続回路６及び接続メモリ７を使用して、予め用意された接続情報テーブル｛Ｃ１，…，Ｃｐ｝を参照して接続切換を行うことで、接続切換を高速化することが可能となる。
【００５９】
また、各段の分解関数間の変数の受け渡し順序は、接続メモリ７内の接続情報テーブルの内容を書き換えるだけで、容易に変更することができる。すなわち、分解関数の演算部分と、各分解関数間の変数の受け渡し及び新たな入力変数の入力部分との双方を、論理関数メモリ２及び接続メモリ７内に分解関数ルックアップテーブル及び接続情報テーブルを書き込み、入力選択メモリ５及び出力選択メモリ９に入力選択データ及び出力選択データを書き込むだけで容易にプログラムすることが可能となる。
【００６０】
次に、上記演算動作をより分かりやすく説明するために、具体的な例を用いてルックアップテーブル・カスケード論理回路の具体的な動作を説明する。
【００６１】
（例）５変数多数決論理関数
ここでは、簡単な論理関数として、５変数多数決論理関数の演算を例にとってルックアップテーブル・カスケード論理回路１の動作を説明する。
【００６２】
５変数多数決関数とは、５つの２進数からなる入力変数Ｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）をもち、そのうちの３つ以上の値が１のときにのみ、出力が１となるような関数をいう。５変数多数決関数を論理式により表すと、下式のような１０個の積項により表される。
【数１】
2004258799.tif 000003
【００６３】
また、５変数多数決関数ｆをＢＤＤで表すと、図７〜図９のようになる。図７〜図９において、ｘ１〜ｘ５の符号が記入された円は、非終端節点を表し、入力変数に対応する。また、０，１の符号が記載された四角形は終端節点を表し、論理関数値ｆ（Ｘ）に対応する。また、各節点間を結ぶ線は枝（エッジ）と呼ばれる。各枝のうち、点線で表されたものは、入力変数の値が０の枝、実線で表されたものは入力変数の値が１の枝を表す。
【００６４】
図７は、目的論理関数である５変数多数決関数ｆを、変数の順序を（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）に固定して、冗長な節点の削除と同形な部分グラフの共有を可能な限り行った、既約順序付二分決定グラフ（以下、「ＲＯＢＤＤ」という。）である。以下、このＲＯＢＤＤを、ルックアップテーブル・カスケード論理回路を用いて構成する場合について説明する。
【００６５】
まず、図７のＲＯＢＤＤを適当な位置で上下に分割する。この場合、分割した上側のＢＤＤの入力変数の数は、論理関数メモリの入力端子の数以下とする。ここでは、入力変数ｘ３と入力変数ｘ４との間で分割することとし、分割した上側のＢＤＤの入力変数Ｘ１＝（ｘ１，ｘ２，ｘ３）は３個とする。図８は分割されたＢＤＤを表す。図８において、Ｌ１は分割線を表す。分割線Ｌ１の上のＢＤＤで表される分解関数を、分解関数ｆ１＝ｆ１（Ｘ１）と呼ぶことにする。
【００６６】
ここで、一般に、変数ｘｋと変数ｘｋ＋１の間の分割線を横切る枝の個数を「ＢＤＤのレベルｋにおける幅」とよび、μｋで表す。但し、同一の節点に接続している枝は１つと数えるものとする。
【００６７】
分割線Ｌ１におけるＢＤＤの幅はμ３＝４であり、分割線Ｌ１の上側のＢＤＤの出力値は、
【数２】
2004258799.tif 000004
の出力変数Ｙ２＝（ｙ２，１，ｙ２，２）により表すことができる。図８においては、Ｘ１＝（０，０，０）に対する出力変数の値をＹ２＝（０，０）、Ｘ１＝（０，０，１），（０，１，０），（１，０，０）に対する出力変数の値をＹ２＝（０，１）、Ｘ１＝（０，１，１），（１，０，１），（１，１，０）に対する出力変数の値をＹ２＝（１，０）、Ｘ１＝（１，１，１）に対する出力変数の値をＹ２＝（１，１）のように割り当てている。尚、出力変数Ｙ２に対する値の割り当て方法は自由であり、この例に限られるものではない。
【００６８】
次に、分割線Ｌ１の下側のＢＤＤを、変数ｘ４と変数ｘ５との間で更に分割する。図９は更に分割されたＢＤＤを表す。図９において、Ｌ２は２回目の分割における分割線、Ｌ３は最後の分割線（出力）を表す。この場合、分割線Ｌｋ−１とＬｋの間のＢＤＤの入力変数Ｘｋの変数の個数ｎｋ＝｜Ｘｋ｜と、分割線Ｌｋ−１の上のＢＤＤの出力変数の個数ｍｋ＝｜Ｙｋ｜との和ｎｋ＋ｍｋが、論理関数メモリの入力端子の数以下となるようにＢＤＤを分割する。
【００６９】
分割線Ｌ２におけるＢＤＤの幅はμ４＝３であり、分割線Ｌ２の上側のＢＤＤの出力値は、
【数３】
2004258799.tif 000005
の出力変数Ｙ３＝（ｙ３，１，ｙ３，２）により表すことができる。図９においては、（Ｘ２，Ｙ２）＝（ｘ４，ｙ２，１，ｙ２，２）＝（０，０，０），（１，０，０），（０，０，１）に対する出力変数の値をＹ３＝（０，０）、（Ｘ２，Ｙ２）＝（１，０，１），（０，１，０）に対する出力変数の値をＹ３＝（１，０）、（Ｘ２，Ｙ２）＝（１，１，０），（０，１，１），（１，１，１）に対する出力変数の値をＹ３＝（１，１）のように割り当てている。
【００７０】
分割線Ｌ３におけるＢＤＤの幅はμ５＝２であり、分割線Ｌ３の上側のＢＤＤの出力値は、
【数４】
2004258799.tif 000006
の出力変数Ｙ４＝（ｙ４，１）により表すことができる。出力変数Ｙ４の値として、（Ｘ３，Ｙ３）＝（ｘ５，ｙ３，１，ｙ３，２）＝（０，０，０），（１，０，０），（０，１，０）に対する出力変数の値をＹ４＝（０）、（Ｘ３，Ｙ３）＝（１，１，０），（０，１，１），（１，１，１）に対する出力変数の値をＹ４＝（１）のように割り当てる。このように出力変数Ｙ４の値を割り当てることによって、出力変数Ｙ４に目的論理関数である５変数多数決関数ｆの値が出力される。尚、ここで、分割線Ｌ２の上の分割されたＢＤＤにより表される分解関数を分解関数ｆ２＝ｆ２（Ｘ２，Ｙ２）と呼び、分割線Ｌ２の下の分割されたＢＤＤにより表される分解関数を分解関数ｆ３＝ｆ３（Ｘ３，Ｙ３）と呼ぶことにする。
【００７１】
以上の分割の結果、５変数多数決関数ｆは、３つの分解関数ｆ１，ｆ２，ｆ３に関数分解される。これらの分解関数を分解関数ルックアップテーブルＴ１，Ｔ２，Ｔ３により表す。ここで、分解関数ｆｋの分解関数ルックアップテーブルＴｋとは、２ｎｋ行２ｍｋ列の表であって、各行が入力値Ｘｋの値に対応し、各列が出力変数ｙｉ（ｉ∈｛１，…，｜Ｙｋ｜｝）の値に対応する表をいう。
【００７２】
分解関数ｆ１，ｆ２，ｆ３の真理値表、及び分解関数ｆ１，ｆ２，ｆ３を表す分解関数ルックアップテーブルＴ１，Ｔ２，Ｔ３は、それぞれ、以下のようになる。
【表１】
2004258799.tif 000007
【表２】
2004258799.tif 000008
【表３】
2004258799.tif 000009
【数５】
2004258799.tif 000010
【００７３】
これらの分解関数ルックアップテーブルを用いれば、５変数多数決関数ｆは、以下の参照演算により計算できる。
【数６】
2004258799.tif 000011
ここで、参照演算子Ｔｋ［Ａ］は、分解関数ルックアップテーブルＴｋの各行のうち、入力変数Ａで特定される行の値（一般にベクトル値）を返す演算子である。
【００７４】
上式において、参照演算は論理関数メモリ２を使用してハードウェア的に行うことができる。すなわち、論理関数メモリ２のｋページに、分解関数ルックアップテーブルＴｋを格納する。このとき、ｋ＝１のときは、入力変数Ｘ１＝（ｘ１，ｘ２，ｘ３）で指定されるアドレスに、その入力変数に対応する関数値Ｙ２＝ｆ１（Ｘ１）を記憶しておく。ｋ＝２のときは、入力変数と中間変数の組（Ｘ２，Ｙ２）＝（ｘ４，ｙ２，１，ｙ２，２）で指定されるアドレスに、その入力変数に対応する関数値Ｙ３＝ｆ２（Ｘ２，Ｙ２）を記憶しておく。ｋ＝３のときは、入力変数と中間変数の組（Ｘ３，Ｙ３）＝（ｘ５，ｙ３，１，ｙ３，２）で指定されるアドレスに、その入力変数に対応する関数値Ｙ４＝ｆ３（Ｘ３，Ｙ３）を記憶しておく。これにより、論理関数メモリ２の入力端子に入力変数又は中間変数を入力し、それらの変数で指定されるアドレスの値を読み出せば、参照演算の結果をすぐに得ることができる。これを模式図で表すと、図１０のようなルックアップテーブル・カスケードとなる。
【００７５】
分解関数の参照演算を行うためには、当該参照演算で使用する入力変数又は中間変数を、所定の順序で論理関数メモリ２の入力端子に入力する必要がある。このときの入力変数及び中間変数の順序の入れ替えは、接続回路６及び接続メモリ７により行われる。
【００７６】
この例の場合、接続メモリ７の１〜３ページには、下式で表される接続情報テーブルＣ１，Ｃ２，Ｃ３が記憶されている。
【数７】
2004258799.tif 000012
【数８】
2004258799.tif 000013
【００７７】
各行及び各列の接続情報テーブルの値は、図３の接続回路６内の各列及び各行のスイッチ回路のオン／オフ情報に対応している。１がオン、０がオフを表す。例えば、接続情報テーブルＣ２は、図３の（ｉ１，ｏ１），（ｉ９，ｏ２），（ｉ１０，ｏ３）の各交点のスイッチ回路をオン状態とし、他のスイッチ回路をオフ状態とすることを意味する。
【００７８】
入力選択メモリ５には、入力変数選択回路４の各演算段におけるシフト値として、ｄ１＝（００００）２，ｄ２＝（００１１）２，ｄ２＝（０１００）２が記憶されている。また、出力選択メモリ９には、最終段の出力変数Ｙ４の出力される出力端子の番号１が記憶されている。
【００７９】
次に、上記ルックアップテーブル・カスケード論理回路１による５変数多数決関数ｆの演算動作について具体的に説明する。
【００８０】
まず、演算制御部１１は、入力選択メモリ５に記憶されたシフト値ｄ１＝（００００）２を入力変数選択回路４の制御ラインｓｈｆ４〜ｓｈｆ１に設定する。入力変数選択回路４は、制御ラインｓｈｆ４〜ｓｈｆ１にｄ１＝（００００）２が設定されると、ｉｎ（０１）〜ｉｎ（０８）をｏｕｔ（０１）〜ｏｕｔ（０８）に接続する。これにより、ｏｕｔ（０１）〜ｏｕｔ（０５）には、それぞれ入力変数ｘ１〜ｘ５の値が出力され、これが接続回路６の入力ラインｉ１〜ｉ５に入力される。
【００８１】
次に、演算制御部１１は、図４の接続メモリ７の段数指定に１ページ目を表す値（０００００）２を設定する。これにより、接続メモリ７の出力端子には、メモリアレイＣＭ１に格納された接続情報テーブルＣ１の値が設定される。接続回路６内のスイッチ回路は、この接続メモリ７の出力に従ってオン／オフ状態が切り換えられる。具体的には、接続回路６の（ｉ１，ｏ１），（ｉ２，ｏ２），（ｉ３，ｏ３）の交点のスイッチ回路がオン状態となり、それ以外のスイッチ回路がオフ状態となる。これにより、出力ラインｏ１，ｏ２，ｏ３には、それぞれ入力変数ｘ１，ｘ２，ｘ３の値が出力される。すなわち、接続回路６は、以下の行列演算を行う。
【数９】
2004258799.tif 000014
【００８２】
次に、演算制御部１１は、論理関数メモリ２に対して、読み出しページ番号ｐｋ＝１を設定する。論理演算メモリ２は、１ページ目のメモリアレイＦＭ１にアクセスし、接続回路６から入力される入力変数Ｘ１＝（ｘ１，ｘ２，ｘ３）で指定されるアドレスに記憶された分解関数ｆ１の関数値Ｙ２＝（ｙ２，１，ｙ２，２）を出力端子から出力する。すなわち、論理演算メモリ２の出力端子（ｙ１，…，ｙ８）には、（ｙ２，１，ｙ２，２，０，…，０）が出力される。これにより、論理関数メモリ２は、以下の参照演算を行ったことになる。
【数１０】
2004258799.tif 000015
【００８３】
次に、演算制御部１１は、入力選択メモリ５に記憶されたシフト値ｄ２＝（００１１）２を入力変数選択回路４の制御ラインｓｈｆ４〜ｓｈｆ１に設定し、入力変数選択回路４は、ｉｎ（０４）〜ｉｎ（１１）をｏｕｔ（０１）〜ｏｕｔ（０８）に接続する。これにより、ｏｕｔ（０１），ｏｕｔ（０２）には、それぞれ入力変数ｘ４，ｘ５の値が出力され、これが接続回路６の入力ラインｉ１，ｉ２に入力される。
【００８４】
次に、演算制御部１１は、図４の接続メモリ７の段数指定に２ページ目を表す値（００００１）２を設定する。これにより、接続メモリ７の出力端子には、メモリアレイＣＭ２に格納された接続情報テーブルＣ２の値が設定される。すなわち、接続回路６の（ｉ１，ｏ１），（ｉ９，ｏ２），（ｉ１０，ｏ３）の交点のスイッチ回路がオン状態となり、それ以外のスイッチ回路がオフ状態となる。そして、出力ラインｏ１，ｏ２，ｏ３には、それぞれ入力変数ｘ４，及び中間変数ｙ２，１，ｙ２，２の値が出力される。すなわち、接続回路６は、以下の行列演算を行う。
【数１１】
2004258799.tif 000016
【００８５】
次に、演算制御部１１は、論理関数メモリ２に対して、読み出しページ番号ｐｋ＝２を設定する。論理演算メモリ２は、２ページ目のメモリアレイＦＭ２にアクセスし、接続回路６から入力される変数（Ｘ２，Ｙ２）＝（ｘ４，ｙ２，１，ｙ２，２）で指定されるアドレスに記憶された分解関数ｆ２の関数値Ｙ３＝（ｙ３，１，ｙ３，２）を出力端子から出力する。すなわち、論理演算メモリ２の出力端子（ｙ１，…，ｙ８）には、（ｙ３，１，ｙ３，２，０，…，０）が出力される。これにより、論理関数メモリ２は、以下の参照演算を行ったことになる。
【数１２】
2004258799.tif 000017
【００８６】
次に、演算制御部１１は、入力選択メモリ５に記憶されたシフト値ｄ３＝（０１００）２を入力変数選択回路４の制御ラインｓｈｆ４〜ｓｈｆ１に設定し、入力変数選択回路４は、ｉｎ（０５）〜ｉｎ（１２）をｏｕｔ（０１）〜ｏｕｔ（０８）に接続する。これにより、ｏｕｔ（０１）には、入力変数ｘ５の値が出力され、これが接続回路６の入力ラインｉ１に入力される。
【００８７】
次に、演算制御部１１は、図４の接続メモリ７の段数指定に３ページ目を表す値（０００１０）２を設定する。これにより、接続メモリ７の出力端子には、メモリアレイＣＭ３に格納された接続情報テーブルＣ３の値が設定される。すなわち、接続回路６の（ｉ１，ｏ１），（ｉ９，ｏ２），（ｉ１０，ｏ３）の交点のスイッチ回路がオン状態となり、それ以外のスイッチ回路がオフ状態となる。そして、出力ラインｏ１，ｏ２，ｏ３には、それぞれ入力変数ｘ５，及び中間変数ｙ３，１，ｙ３，２の値が出力される。すなわち、接続回路６は、以下の行列演算を行う。
【数１３】
2004258799.tif 000018
【００８８】
次に、演算制御部１１は、論理関数メモリ２に対して、読み出しページ番号ｐｋ＝３を設定する。論理演算メモリ２は、３ページ目のメモリアレイＦＭ３にアクセスし、接続回路６から入力される変数（Ｘ３，Ｙ３）＝（ｘ５，ｙ３，１，ｙ３，２）で指定されるアドレスに記憶された分解関数ｆ３の関数値Ｙ４＝（ｙ４，１）を出力端子から出力する。すなわち、論理演算メモリ２の出力端子（ｙ１，…，ｙ８）には、（ｙ４，１，０，…，０）が出力される。これにより、論理関数メモリ２は、以下の参照演算を行ったことになる。
【数１４】
2004258799.tif 000019
【００８９】
最後に、演算制御部１１は、出力選択メモリ９に記憶された、出力選択データ（すなわち、出力変数Ｙ４の出力される出力端子の番号１）を出力回路８に設定する。そして、出力回路８は出力端子ｙ１を選択し、ｙ１に出力された関数値Ｙ４の値を出力レジスタ１０に出力する。これにより、５変数多数決関数ｆの演算がされたことになる。
【００９０】
（実施形態２）
図１１は本発明の実施形態２に係るルックアップテーブル・カスケード論理回路の接続回路の構成を示す図である。尚、本実施形態においては、ルックアップテーブル・カスケード論理回路の全体構成は図１と同様であるため説明は省略する。
【００９１】
本実施形態のルックアップテーブル・カスケード論理回路は、接続回路６’が、各出力ラインｏ１〜ｏｍｏ（ｍｏは出力ラインの本数）に対して、総ての入力ラインｉ１〜ｉｍｉ（ｍｉは入力ラインの本数）のうちの１本を選択して当該出力ラインとの接続を行うマルチプレクサＭＵＸ１〜ＭＵＸ８を備えていることを特徴とする。そして、接続メモリ７’は、各マルチプレクサＭＵＸ１〜ＭＵＸ８の接続制御ラインに接続されている。それぞれのマルチプレクサの接続制御ラインの数ｎｃｈは、
【数１５】
2004258799.tif 000020
なので、接続回路６’に必要な接続制御ラインの総数は、
【数１６】
2004258799.tif 000021
となる。実施形態１では、接続回路６としてクロスバスイッチを使用したが、実施形態１の場合、接続回路６に必要な接続制御ラインの総数Ｎｃｈは、ｍｉ×ｍｏ本である。従って、例えば、ｍｉ＝１６，ｍｏ＝８とすると、Ｎｃｈ＝１２８本となる。また、接続メモリ７の出力端子は、少なくとも接続回路６の接続制御ラインの総数Ｎｃｈだけ必要なので、接続メモリ７の回路サイズがかなり大きくなる。また、接続メモリ７の出力端子の数に比例して、接続情報テーブル｛Ｃ１，…，Ｃｐ｝のサイズも大きくなるため、接続メモリ７もかなり大きなメモリ容量が必要とされる。それに対し、本実施形態では、接続回路６’にマルチプレクサＭＵＸ１〜ＭＵＸ８を使用することで、接続回路６’に必要な接続制御ラインの総数Ｎｃｈを、上記実施形態１の場合よりも大幅に削減することができる。例えば、ｍｉ＝１６，ｍｏ＝８とすると、Ｎｃｈ＝８×ｌｏｇ２１６＝３２本となる。そのため、接続メモリ７’の出力端子数も少なくなる。従って、上記実施形態１のものに比べて接続回路６’を小型化することができるとともに、メモリ７’のメモリ容量も小さくすることが可能となる。
【００９２】
（実施形態３）
図１２は本発明の実施形態２に係るルックアップテーブル・カスケード論理回路の出力回路の構成を示す図である。尚、本実施形態においては、ルックアップテーブル・カスケード論理回路の全体構成は図１と同様であるため説明は省略する。
【００９３】
本実施形態のルックアップテーブル・カスケード論理回路は、出力回路８’が、図１２に示したように、２チャンネル１出力のマルチプレクサ（以下、「ＭＵＸ」という。）３１〜４４を多段にカスケード接続し、各段において、出力を取り出せるように構成したことを特徴とする。
【００９４】
出力回路８’の入力ラインｙ１〜ｙ８は、論理関数メモリ２の各出力端子に接続される。この入力ラインｙ１〜ｙ８から、出力変数Ｙｋ（ｋ∈｛１，…，ｐ｝）の値が入力される。出力回路８’の出力ラインｆ（１）〜ｆ（８）からは、入力ラインｙ１〜ｙ８のうち選択されたものに出力された出力変数Ｙｋの値（ｙｋ，１，…，ｙｋ，｜Ｙｋ｜）が出力される。
【００９５】
入力ラインｙ１，ｙ２、入力ラインｙ３，ｙ４、入力ラインｙ５，ｙ６、及び入力ラインｙ７，ｙ８は、それぞれＭＵＸ３１、ＭＵＸ３２、ＭＵＸ３３、及びＭＵＸ３４の入力側に接続されている。ＭＵＸ３１，３２、及びＭＵＸ３３，３４の出力は、それぞれＭＵＸ３５、及びＭＵＸ３６の入力側に接続されている。ＭＵＸ３５，３６の出力は、ＭＵＸ３７の入力に接続されている。
【００９６】
ＭＵＸ３１〜３４は、共通の切換制御ラインＦ１により切換制御がされる。すなわち、Ｆ１が“０”のときはＭＵＸ３１，３２，３３，３４は、それぞれ、入力ラインｙ１，ｙ３，ｙ５，ｙ７を選択し、Ｆ１が“１”のときはＭＵＸ３１，３２，３３，３４は、それぞれ、入力ラインｙ２，ｙ４，ｙ６，ｙ８を選択する。
【００９７】
ＭＵＸ３５，３６は、共通の切換制御ラインＦ２により切換制御がされる。すなわち、Ｆ２が“０”のときはＭＵＸ３５，３６は、それぞれ、ＭＵＸ３１，３３を選択し、Ｆ２が“１”のときはＭＵＸ３５，３６は、それぞれ、ＭＵＸ３２，３４を選択する。
【００９８】
また、ＭＵＸ３７は、切換制御ラインＦ３により切換制御がされる。すなわち、Ｆ３が“０”のときはＭＵＸ３７は、ＭＵＸ３５を選択し、Ｆ３が“１”のときはＭＵＸ３７は、それぞれ、ＭＵＸ３６を選択する。
【００９９】
ＭＵＸ３１〜３４によって、８本の入力ラインｙ１〜ｙ８のうち４本が選択される。ＭＵＸ３１〜３６によって、８本の入力ラインｙ１〜ｙ８のうち２本が選択される。更に、ＭＵＸ３１〜３６によって、８本の入力ラインｙ１〜ｙ８のうち１本が選択される。このようにして、８本の入力ラインｙ１〜ｙ８のうち、８本、４本、２本、又は１本の出力ラインを選択して、目的関数ｆの演算結果ｆ（Ｘ）として出力させることが可能となる。
【０１００】
尚、実際の回路においては、ＬＳＩに組み込まれた場合に出力ピンの本数を極力減らす必要があるため、出力回路８’の出力ラインの数を減らす必要がある。そこで、ＭＵＸ３８〜４４によって、各本数の選択がされたときの出力を共通の出力ラインｆ（１）〜ｆ（８）を通して出力するようにされている。ＭＵＸ３８〜４４は、共通の切換制御ラインＳｅｌｅｃｔによって切換制御がされる。
【０１０１】
ＭＵＸ３８は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ１を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３１の出力を選択し、選択したラインの信号値を出力ラインｆ（１）に出力する。ＭＵＸ３９は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ３を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３２の出力を選択し、選択したラインの信号値を出力ラインｆ（３）に出力する。ＭＵＸ４０は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ５を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３３の出力を選択し、選択したラインの信号値を出力ラインｆ（５）に出力する。ＭＵＸ４１は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ７を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３４の出力を選択し、選択したラインの信号値を出力ラインｆ（７）に出力する。
【０１０２】
ＭＵＸ４２は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ２を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３５の出力を選択し、選択したラインの信号値を出力ラインｆ（２）に出力する。ＭＵＸ４３は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ４を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３７の出力を選択し、選択したラインの信号値を出力ラインｆ（４）に出力する。ＭＵＸ４４は、Ｓｅｌｅｃｔが“０”のとき入力ラインｙ６を選択し、Ｓｅｌｅｃｔが“１”のときＭＵＸ３６の出力を選択し、選択したラインの信号値を出力ラインｆ（６）に出力する。また、出力ラインｆ（８）は、入力ラインｙ８に直結されている。
【０１０３】
目的関数ｆの演算結果ｆ（Ｘ）のビット数（出力の本数）が８のときは、Ｓｅｌｅｃｔを“０”とする。これにより、出力ラインｆ（１）〜ｆ（８）には、論理関数メモリ２から入力ラインｙ１〜ｙ８に入力される出力変数Ｙｐ＝（ｙｐ，１，…，ｙｐ，８）の値が出力される。出力の本数が４のときは、Ｓｅｌｅｃｔを“１”とし、Ｆ１に“０”又は“１”を設定する。これにより、出力ラインｆ（１），ｆ（３），ｆ（５），ｆ（７）には、論理関数メモリ２から入力ラインｙ１〜ｙ８のうち４本に入力される出力変数Ｙｐ＝（ｙｐ，１，…，ｙｐ，４）の値が出力される。出力の本数が２のときは、Ｓｅｌｅｃｔを“１”とし、Ｆ１、Ｆ２に“０”又は“１”を設定する。これにより、出力ラインｆ（２），ｆ（６）には、論理関数メモリ２から、入力ラインｙ１〜ｙ８のうち２本に入力される出力変数Ｙｐ＝（ｙｐ，１，ｙｐ，２）の値が出力される。出力の本数が１のときは、Ｓｅｌｅｃｔを“１”とし、Ｆ１，Ｆ２，Ｆ３に“０”又は“１”を設定する。これにより、出力ラインｆ（４）には、論理関数メモリ２から、入力ラインｙ１〜ｙ８のうち１本に入力される出力変数Ｙｐ＝（ｙｐ，１）の値が出力される。
【０１０４】
尚、切換制御ラインＦ１〜Ｆ３及びＳｅｌｅｃｔの設定値は、あらかじめ出力選択メモリ９に記憶される。そして、演算制御部１１の制御によって、各切換制御ラインＦ１〜Ｆ３及びＳｅｌｅｃｔに設定される。
【０１０５】
このように、本実施形態によれば、多出力論理関数の演算を行う場合、複数の出力を取り出すことが可能となる。そのため、多出力論理関数の演算を複数の出力に関して同時に行うことが可能となる。従って、多出力論理関数の演算速度の向上を図ることができる。
【０１０６】
また、目的関数ｆの演算が最後まで終了するのを待たず、分解関数ｆｋを任意の段まで計算した途中の演算結果を、自由に取り出すことも可能となる。
【０１０７】
尚、本実施形態では、出力回路８’内のマルチプレクサは２チャンネル１出力のものを使用しているが、一般に、ｗチャンネル１出力（ｗ≧２）のマルチプレクサを使用することが可能である。
【０１０８】
（実施形態４）
図１３は実施形態４に係るルックアップテーブル・カスケード論理回路の接続回路の構成を示す図である。尚、本実施形態においては、ルックアップテーブル・カスケード論理回路の全体構成は図１と同様であるため説明は省略する。
【０１０９】
本実施形態のルックアップテーブル・カスケード論理回路は、接続回路６”が、入力ラインを出力ラインに対して自在にシフトさせて接続するシフタ回路からなることを特徴とする。
【０１１０】
図１３では、シフタ回路として、図２と同様のバレル・シフタ回路を使用して構成した例を示している。入力ラインｉ１〜ｉ１６の側から、８ビット・シフタ回路５１、４ビット・シフタ回路５２、２ビット・シフタ回路５３、及び１ビット・シフタ回路５４が、それぞれ直列に接続されている。
【０１１１】
入力ラインｉ１〜ｉ８は、入力変数選択回路４の出力端子に接続されており、入力ラインｉ９〜ｉ１６は、論理関数メモリ２の出力端子に接続されている。入力ラインｉ８，ｉ７，…の順に、入力変数ｘｄｋ，ｘｄｋ＋１，…が入力される。また、入力ラインｉ９，ｉ１０，…の順に、前段ｋ−１の出力変数ｙｋ，１，ｙｋ，２，…が入力される。
【０１１２】
各シフタ回路５１〜５４のシフトのオン／オフは、各シフタ回路５１〜５４に１本づつ設けられた接続制御ライン５５〜５８により制御される。そして、接続制御ライン５５〜５８は、接続メモリ７”の出力端子に接続されている。従って、接続メモリ７”の出力端子から出力される接続情報テーブルＣｋ（ｋ∈｛１，…，ｐ｝）の値に従って、各シフタ回路５１〜５４のシフト量が制御される。
【０１１３】
これらのシフタ回路５１〜５４により、出力ラインｏ１〜ｏ８は、ａｋビットだけシフトされて、入力ラインｉ８＋ａｋ〜ｉ１＋ａｋに接続される。
【０１１４】
このように、接続回路６”にシフタ回路を利用することにより、接続の切換を制御する接続制御ラインは、
【数１７】
2004258799.tif 000022
だけあれば充分である。但し、Ｎｉｎは、入力ラインの本数、Ｎｏｕｔは出力ラインの本数である。例えば、図１３の例のように、Ｎｉｎ＝１６、Ｎｏｕｔ＝８の場合には、接続制御ラインは４本あれば充分である。従って、接続情報テーブルＣｋ（ｋ∈｛１，…，ｐ｝）は、接続制御ラインの本数と同じビット数で充分となり、接続メモリ７”の記憶容量を少なくすることができる。また、接続メモリ７”の出力端子数を大幅に減少させることができることから、接続回路６”及び接続メモリ７”の回路を小型化することができる。
【０１１５】
尚、実際には、図１３のようにシフタ回路を多段に接続すると、信号振幅が減衰する。従って、図１３では省略しているが、実際には、減衰が大きい場合、シフタ回路の数段ごとに増幅器（バッファ）を挿入しておくことが必要となる。
【０１１６】
【発明の効果】
以上のように、本発明に係るルックアップテーブル・カスケード論理回路によれば、接続回路内のスイッチ回路の切換を、接続メモリに記憶された接続情報テーブルＣｋにより行うことで、接続回路内のスイッチ回路の切換動作を短時間で行うことができる。そのため、目的論理関数ｆの演算速度を高速化することが可能となる。
【０１１７】
また、目的論理関数のプログラムは、論理関数メモリ、接続メモリに対して分解関数ルックアップテーブル、接続情報テーブルを書き込むだけでよいため、設計が極めて簡単となる。
【０１１８】
また、回路内の配線は固定されているため、設計時に配線遅延の考慮は不要である。従って、効率的な論理演算回路の設計ができる。
【０１１９】
更に、分解関数ｆｋの数が決まれば、演算時間も一意的に決まることから、設計時に演算時間の予測が容易となる。
【０１２０】
また、入力変数選択回路によって、入力変数Ｘの一部を選択して接続回路の入力ラインに入力することにより、接続回路や接続メモリを小型化することができる。
【０１２１】
出力回路を、ｗチャンネル１出力（ｗ≧２）のマルチプレクサを多段にカスケード接続し、各段において出力を取り出せるように構成することで、多出力論理関数の演算を複数の出力に関して同時に行い、多出力論理関数の演算速度の向上を図ることができる。
【図面の簡単な説明】
【図１】本発明の実施形態１に係るルックアップテーブル・カスケード論理回路のブロック図である。
【図２】入力変数選択回路の回路構成図である。
【図３】接続回路周辺の回路構成を表す図である。
【図４】接続メモリの構成を表すブロック図である。
【図５】論理関数メモリの構成を表すブロック図である。
【図６】本実施形態に係るルックアップテーブル・カスケード論理回路の動作を表すフローチャートである。
【図７】５変数多数決関数のＢＤＤである。
【図８】分割された５変数多数決関数のＢＤＤである。
【図９】分割された５変数多数決関数のＢＤＤである。
【図１０】５変数多数決関数のルックアップテーブル・カスケードの模式図である。
【図１１】本発明の実施形態２に係るルックアップテーブル・カスケード論理回路の接続回路の構成を示す図である。
【図１２】本発明の実施形態２に係るルックアップテーブル・カスケード論理回路の出力回路の構成を示す図である。
【図１３】実施形態４に係るルックアップテーブル・カスケード論理回路の接続回路の構成を示す図である。
【図１４】ルックアップテーブル・カスケード論理回路の原理を表す図である。
【符号の説明】
１  ルックアップテーブル・カスケード論理回路
２  論理関数メモリ
３  入力変数レジスタ
４  入力変数選択回路
５  入力選択メモリ
６，６’，６”  接続回路
７，７’，７”  接続メモリ
８，８’  出力回路
９  出力選択メモリ
１０  出力レジスタ
１１  演算制御部
１５，５１  ８ビット・シフタ回路
１６，５２  ４ビット・シフタ回路
１７，５３  ２ビット・シフタ回路
１８，５４  １ビット・シフタ回路
２１，２２  ページデコーダ
２３  アドレスデコーダ
３１〜４４  マルチプレクサ
５５〜５８  接続制御ライン
【図１】
2004258799.tif 000023
【図２】
2004258799.tif 000024
【図３】
2004258799.tif 000025
【図４】
2004258799.tif 000026
【図５】
2004258799.tif 000027
【図６】
2004258799.tif 000028
【図７】
2004258799.tif 000029
【図８】
2004258799.tif 000030
【図９】
2004258799.tif 000031
【図１０】
2004258799.tif 000032
【図１１】
2004258799.tif 000033
【図１２】
2004258799.tif 000034
【図１３】
2004258799.tif 000035
【図１４】
2004258799.tif 000036