JP4011015B2 - Ｌｕｔ符号化方法及びｌｕｔ符号化装置並びにｌｕｔカスケード論理回路 - Google Patents

Description

本発明は、ＬＵＴ（Look-Up Table）カスケード論理回路において、目的論理関数の演算速度を高速化することを可能とするＬＵＴ符号化技術に関するものである。

従来、ソフトウェア的に自由に論理関数の組み換えが可能で、かつ、論理関数の演算処理をＭＰＵに比べて高速に行うことが可能な技術として、ルックアップテーブル・カスケード論理回路（以下、「ＬＵＴカスケード論理回路」という。）が知られている（例えば、非特許文献１，２参照）。

図１８は論理関数の二分決定グラフ（ＢＤＤ : Binary decision diagrams）を表す図、図１９はＬＵＴカスケード論理回路の構成を表す図である。ＬＵＴカスケード論理回路では、演算を行う論理関数（以下、「目的論理関数」という。）をs個の部分グラフ（sub graph）に分割する。そして、各部分グラフのそれぞれを真理値表（truth table）で表しＬＵＴを作成する。そして、図１９のようにＬＵＴをカスケード接続する。各ＬＵＴは、論理関数メモリに格納され、論理関数メモリのアクセスにより各部分グラフの演算は行われる。

図１８，図１９において、X₁,…,X_sは入力変数組を表している。μ₁,…,μ_s-1は、ＢＤＤの切断線を横切る有向枝（directed edge）の数を表す。但し、同一の節点（node）を終点（end node）とする有向枝は１本として数える。u₁,…,u_s-1は、前段のＬＵＴから後段のＬＵＴに入力される中間変数の数を表す。一般に、中間変数の数u₁,…,u_s-1は、（数１）により表される。

従来のＬＵＴカスケード論理回路では、最前段のＬＵＴから順にメモリアクセスによる参照演算を行ってゆき、最終段のＬＵＴによる演算の結果として得られる出力値ｆを、目的論理関数による演算値として得る。

このように、目的論理関数の演算を複数段のＬＵＴのメモリアクセスによる参照演算で行うことによって、通常のＭＰＵ（Micro Processing Unit）に比べて高速に論理演算を行うことが可能となる。
笹尾勤，松浦宗寛，井口幸洋，"多出力関数のカスケード実現と再構成可能ハードウェアによる実現"，電子情報通信学会FTS研究会, FTS2001-8, pp. 57-64, 三重大学(2001-04)． T. Sasao, M. Matsuura, and Y. Iguchi, "A cascade realization of multiple-output function for reconfigurable hardware," International Workshop on Logic and Synthesis (IWLS01), Lake Tahoe, CA, June 12-15, 2001. pp.225-230.

上記従来のカスケード論理回路では、目的論理関数の演算結果を得るためには、必ずｓ回のメモリアクセスによる参照演算が必要とされる。従って、１回の参照演算を行うために要する時間をＴ_ａとすると、ｓ個のＬＵＴにより表される目的論理関数の演算を実行するためには、必ず少なくともｓ・Ｔ_ａの時間を要する。ところで、Ｔ_ａは、半導体メモリのアクセス時間により決定される量であり、物理的に決定する。従って、回路的に演算速度の高速化を図るためにはｓの値を小さくする必要がある。しかし、ｓを小さくすると、各ＬＵＴに入力される入力変数の個数と、各ＬＵＴから出力される中間変数の個数（レイル数 : number of rails）が増大する。入力変数の個数やレイル数が１増えると、必要なメモリ容量は２倍に増加する。故に、ｓを小さくすると、論理関数メモリに必要とされるメモリ容量が２の冪乗に比例して増大することとなるため、目的論理関数の変数の個数が大きい場合にはｓを小さくすることにも限界がある。従って、従来のＬＵＴカスケード論理回路では、回路の物理的制約とメモリ容量の制約とから高速化には限界があった。

ところで、ＬＵＴカスケード論理回路は、メモリのみを使用して安価に構成することができ、かつ、ＭＰＵに比べて高速な演算が可能であることを最大の利点とする。しかしながら、近年はＭＰＵが広範な分野で用いられるようになったことから、ＭＰＵの単価自体が低廉化してきている。従って、ＬＵＴカスケード論理回路の優位性をより大きなものとする為には、ＬＵＴカスケード論理回路の更なる高速化を図っていくことが要求される。

そこで、本発明の目的は、上記従来のＬＵＴカスケード論理回路を改良し、メモリ容量を大規模化することなくして従来よりも高速な論理演算を可能とするＬＵＴカスケード論理回路及びそのＬＵＴ符号化技術を提供することにある。

本発明に係るＬＵＴ符号化方法の第１の構成は、演算を行う対象となる目的論理関数を表す二分決定グラフ（ＢＤＤ）を適所で分割して得られる各部分グラフを真理値表で表したものであるＬＵＴ（Look-Up Table）が、直列に順序づけて接続されており、最前段のＬＵＴ以外のＬＵＴの入力の一部は、当該ＬＵＴの前段のＬＵＴの出力が入力される構成からなるＬＵＴカスケードにおいて、各ＬＵＴの出力値に符号の割り当てを行うＬＵＴ符号化方法であって、前記二分決定グラフの終端節点（terminal node）に対応する前記ＬＵＴの出力値に対しては、その終端節点の値に対応して決められた特定の符号を割り当てることを特徴とする。

この方法により符号化されたＬＵＴカスケードの各ＬＵＴによる演算を進めていったときに、二分決定グラフの終端節点に達すると、その節点値に対応して割り当てられた特定の符号が出力される。そのため、終端節点に達したことを検出することが可能となる。そして、終端節点に達したことが検出された場合、それ以降の段のＬＵＴによる演算を打ち切ることによって、目的論理関数の演算速度を速めることが可能となる。

ここで、「終端節点」とは、ＢＤＤの節点のうち子節点を有しない節点をいう。「終端節点の値に対応して決められた特定の符号を割り当てる」方法としては、例えば、ある段のＬＵＴのレイル数が４であった場合、ＢＤＤの終端節点の値が０の場合は「００００」、ＢＤＤの終端節点の値が１の場合は「１１１１」のように符号を割り当てる等、その符号から終端節点であることを識別することが可能な割り当て方法が採られる。

本発明に係るＬＵＴ符号化方法の第２の構成は、前記第１の構成において、前記ＬＵＴカスケードは、最終段のＬＵＴが１ビットの出力変数を出力するＬＵＴカスケードであって、前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その終端節点の値が０の場合には前記ＬＵＴの出力値として全ビットが０（又は全ビットが１）の符号を割り当て、その終端節点の値が１の場合には前記ＬＵＴの出力値として全ビットが１又は全ビットが０の符号を割り当てることを特徴とする。

この構成によれば、この方法で符号化されたＬＵＴカスケードの各ＬＵＴによる演算を進めていったときに、ＬＵＴの出力値において全ビットが０又は全ビットが１であることを検出することにより、終端節点に達したことを検出することが可能となる。そして、この検出は、ＡＮＤゲート及びＮＯＲゲートを用いた簡単な回路構成で行うことが可能である。

本発明に係るＬＵＴ符号化方法の第３の構成は、前記第１の構成において、前記ＬＵＴカスケードは、最終段のＬＵＴが２ビット以上の出力変数を出力するＬＵＴカスケードであって、前記二分決定グラフの終端節点に対応する前記ＬＵＴカスケードのｉ段目のＬＵＴの出力値に対しては、当該ｉ段目のＬＵＴに対して決められている所定の閾値以下又は以上となるように符号を割り当てることを特徴とする。

この構成によれば、この方法で符号化されたＬＵＴカスケードの各ＬＵＴによる演算を進めていったときに、各段のＬＵＴの出力値において所定の閾値以下又は以上であることを検出することにより、終端節点に達したことを検出することが可能となる。そして、この検出は、コンパレータを用いた簡単な回路構成で行うことが可能である。

本発明に係るＬＵＴ符号化装置の第１の構成は、演算を行う対象となる目的論理関数を表す二分決定グラフを適所で分割して得られる各部分グラフを真理値表で表したものであるＬＵＴが、直列に順序づけて接続されており、最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部は、当該ＬＵＴの前段のＬＵＴの出力が入力される構成からなるＬＵＴカスケードにおいて、各ＬＵＴの出力値に符号の割り当てを行うＬＵＴ符号化装置であって、前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その節点の値に対応して決められた特定の符号を割り当てる符号化手段を備えていることを特徴とする。

これにより、ＬＵＴ符号化装置により目的論理関数を符号化した場合、終端節点に対しては、符号化手段によりある決められた特定の符号が割り当てられるように符号化がなされる。従って、この符号化されたＬＵＴを使用してＬＵＴカスケードの演算を行う場合、最終段のＬＵＴに到達する前に終端節点を表す特定の符号が検出されたときに、その段階でＬＵＴカスケードの演算を打ち切り、その特定の符号が表す終端節点の値を出力すれば、演算速度を向上させることが可能となる。

本発明に係るＬＵＴ符号化装置の第２の構成は、前記第１の構成において、前記ＬＵＴカスケードは、最終段のＬＵＴが１ビットの出力変数を出力するＬＵＴカスケードであって、前記符号化手段は、前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その終端節点の値が０の場合には前記ＬＵＴの出力値として全ビットが０（又は全ビットが１）の符号を割り当て、その終端節点の値が１の場合には前記ＬＵＴの出力値として全ビットが１（又は全ビットが０）の符号を割り当てることを特徴とする。

本発明に係るＬＵＴ符号化装置の第３の構成は、前記第１の構成において、前記ＬＵＴカスケードは、最終段のＬＵＴが２ビット以上の出力変数を出力するＬＵＴカスケードであって、前記符号化手段は、前記二分決定グラフの終端節点に対応する前記ＬＵＴカスケードのｉ段目のＬＵＴの出力値に対しては、当該ｉ段目のＬＵＴに対して決められている所定の閾値以下又は以上となるように符号を割り当てることを特徴とする。

本発明に係るＬＵＴカスケード論理回路の第１の構成は、演算を行う対象となる目的論理関数を表す二分決定グラフを適所で分割して得られる各部分グラフを真理値表により表したものであるＬＵＴが格納された論理関数メモリと、最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部を、当該ＬＵＴの前段のＬＵＴの出力に接続する接続回路と、を備えたＬＵＴカスケード論理回路であって、前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値は、その終端節点の値に対応して決められた特定の符号を割り当てられており最終段以外の前記ＬＵＴの出力値が前記特定の符号であった場合、当該特定の符号に対応する節点値を出力するとともに、当該ＬＵＴよりも後段のＬＵＴによる論理演算を打ち切る演算制御手段を備えていることを特徴とする。

入力変数を各ＬＵＴに入力しながら、最前段のＬＵＴから最後段のＬＵＴにかけて、順次、前段ＬＵＴの出力及び外部入力変数を入力し後段のＬＵＴに出力するというメモリアクセス動作を繰り返していくことにより、目的関数の演算が行われる。このとき、演算制御手段は、途中の段のＬＵＴの出力値が、終端節点を表す特定の符号であることを検出すると、その符号に対応する節点値を出力する。それとともに、それ以降のＬＵＴによる演算を打ち切って演算を終了する。これにより、目的関数による演算値が得られるまでの時間を短縮することができる。

本発明に係るＬＵＴカスケード論理回路の第２の構成は、前記第１の構成において、前記論理関数メモリに格納された最終段のＬＵＴは、１ビットの出力変数を出力するＬＵＴであって、演算制御手段は、前記ＬＵＴの出力値の全ビットが０（又は全ビットが１）であることを検出する終端判定器と、前記終端判定器が、最終段以外の前記ＬＵＴの出力値において、全ビットが０（又は全ビットが１）であることを検出したときに、その出力値に応じて節点値を出力する出力回路と、を備えていることを特徴とする。

この構成により、演算制御手段は、終端判定器が最終段以外の前記ＬＵＴの出力値において、全ビットが０又は全ビットが１であることを検出したときに、出力回路がその出力値に応じて節点値を出力する。これにより、ＬＵＴカスケードの最終段に到達していない段階でも、終端節点に達すれば演算結果を得ることができる。従って、従来よりも高速な論理演算が可能となる。また、終端判定器は、ＡＮＤゲート及びＮＯＲゲートを用いた簡単な回路で構成することができる。

本発明に係るＬＵＴカスケード論理回路の第３の構成は、前記第１の構成において、前記論理関数メモリに格納された最終段のＬＵＴは、２ビット以上の出力変数を出力するＬＵＴであって、演算制御手段は、最終段以外の各段の前記ＬＵＴに対して終端判定値が格納された終端判定値メモリと、各段の前記ＬＵＴの出力値が、その段に対する前記終端判定値以下又は以上であることを検出する終端判定器と、前記終端判定器が、最終段以外の前記ＬＵＴの出力値が、その段に対する前記終端判定値以下又は以上であることを検出したときに、その出力値に応じて節点値を出力する出力回路と、を備えていることを特徴とする。

この構成により、演算制御手段は、終端判定器が最終段以外の前記ＬＵＴの出力値において、その段に対する前記終端判定値以下又は以上であることを検出したときに、出力回路がその出力値に応じて節点値を出力する。これにより、ＬＵＴカスケードの最終段に到達していない段階でも、終端節点に達すれば演算結果を得ることができる。従って、従来よりも高速な論理演算が可能となる。また、終端判定器は、コンパレータを用いた簡単な回路で構成することができる。

上述のように、本発明に係るＬＵＴ符号化方法によれば、ＬＵＴカスケードの各ＬＵＴによる演算を進めていったときに、二分決定グラフの終端節点に達したことの検出が可能となる。そして、終端節点に達したことが検出された場合、それ以降の段のＬＵＴによる演算を打ち切ることによって、目的論理関数の演算速度を速めることが可能となる。

また、本発明に係るＬＵＴカスケード論理回路によれば、演算制御手段が、途中の段のＬＵＴの出力値が、終端節点を表す特定の符号であることを検出すると、その符号に対応する節点値を出力するとともに、それ以降のＬＵＴによる演算を打ち切って演算を終了することにより、目的関数による演算値が得られるまでの時間を短縮することができる。従って、ＬＵＴカスケード論理回路の演算速度の高速化を図ることが可能となる。

以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。

本実施例では、出力変数が１ビットである共有二分決定グラフ（Shared Binary Decision Diagram．以下、「ＳＢＤＤ」という。）に対して、ＬＵＴカスケード論理回路の演算速度を高速化するための符号化方法を示す。

図１は本発明の実施例１に係るＬＵＴ符号化装置の構成を表すブロック図である。本実施例に係るＬＵＴ符号化装置は、論理仕様記憶手段１、ＲＯＢＤＤ生成手段２、ＲＯＢＤＤ記憶手段３、ＢＤＤ分割手段４、符号化手段５、及びＬＵＴ記憶手段６を備えている。

論理仕様記憶手段１は、目的論理関数を表す論理仕様を記憶する。ＲＯＢＤＤ生成手段２は、論理仕様記憶手段１に記憶された目的論理関数を表す論理仕様から、ＢＤＤを生成するとともにそのＢＤＤを既約化し、既約順序付二分決定グラフ（Reduced Ordered Binary Decision Diagram。以下、「ＲＯＢＤＤ」という。）を生成してＲＯＢＤＤ記憶手段３に格納する。ＢＤＤ分割手段４は、ＲＯＢＤＤ記憶手段３に格納されたＲＯＢＤＤを、所定の大きさの部分グラフに分割する。符号化手段５は、ＢＤＤ分割手段４が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。

以上のように構成された本実施例に係るＬＵＴ符号化装置について、以下その動作を説明する。

図２は本発明の実施例１に係るＬＵＴ符号化方法を表すフローチャートである。まず、ＲＯＢＤＤ生成手段２は、論理仕様記憶手段１に格納された論理仕様を読み出して、ＢＤＤを生成しながらこれを既約化してＲＯＢＤＤを生成し、これをＲＯＢＤＤ記憶手段３に格納する（Ｓ１）。ここで、ＢＤＤの「既約化」とは、展開する変数の順序を固定して、冗長な節点の削除と同型な部分グラフの共有を可能な限り行うことをいう。

〔例１．１〕
例えば、目的論理関数ｆが（数２）のような関数であったとする。

（数２）を表す２分決定木（BDT : Binary Decision Tree）は図３のようになる。図３において「○」が非終端節点（non-terminal node）を表し、「□」が終端節点を表す。また、各非終端節点を始節点とする有向枝のうち、実線で表されたものは、非終端節点における入力が「１」に対応する有向枝、点線で表されたものは、非終端節点における入力が「０」に対応する有向枝を表している。

図３のＢＤＴは、目的論理関数ｆを展開する変数の順序を固定し、冗長な節点の削除と同型な部分グラフの共有を可能な限り行うことにより、図４に示したＲＯＢＤＤに変形することができる。ＲＯＢＤＤ生成手段２は、目的論理関数の論理仕様から、図３に示したＢＤＴを生成しながら、同時に図３のＢＤＴを既約化し、図４のようなＲＯＢＤＤを生成する。そして、このＲＯＢＤＤは、ＲＯＢＤＤ記憶手段３に（表１）のようなＲＯＢＤＤテーブルとして格納される。

（表１）において、「アドレス」は、ＲＯＢＤＤの節点のデータが格納されたメモリ内のアドレスを表す。「index」は、各節点の節点ラベル（vertex Label）に対応した符号を表す。（表１）では、節点ラベル「Ａ」に対して「００１」、節点ラベル「Ｂ」に対して「０１０」、節点ラベル「Ｃ」に対して「０１１」の符号が付されている。また、終端節点に対しては、符号「０００」が付されている。「０枝」と「１枝」の欄には、各節点を始節点（initial vertex）とする入力「０」に対応する有向枝の終点のアドレス又は入力「０」に対応する有向枝の終点のアドレスが格納されている。但し、終端節点に対しては、それを始節点とする有向枝は存在しないので、当該終端節点の値に対応する適当な値（（表１）では、節点値１の終端節点に対しては「１１１１」、節点値０の終端節点に対しては「００００」）が割り当てられる。
（例終わり）

次に、ＢＤＤ分割手段４は、ＲＯＢＤＤ記憶手段３に格納されたＲＯＢＤＤを、所定の大きさのｓ個の部分グラフに分割する（Ｓ２）。ここで、「所定の大きさの部分グラフ」とは、各部分グラフを符号化してＬＵＴを作成した場合に、作成されるＬＵＴが、ＬＵＴを格納するメモリの入力数以下の入力数となる程度の大きさの部分グラフをいう。

〔例１．２〕
図５（ａ）のようなＲＯＢＤＤを持つ論理関数を考える。ＬＵＴを格納するメモリのアドレスの入力数が３であるとした場合、ＢＤＤ分割手段４は、図５（ｂ）の一点鎖線で示した位置でＲＯＢＤＤを分割する。これにより、図５（ａ）のＲＯＢＤＤを４個の３入力ＬＵＴにより実現することができる。図５（ｂ）において「○」が非終端節点を表し、「□」が終端節点を表す。また、各非終端節点を始節点とする有向枝のうち、実線で表されたものは非終端節点における入力が「１」に対応する有向枝、点線で表されたものは非終端節点における入力が「０」に対応する有向枝を表している。
（例終わり）

次に、符号化手段５は、ＢＤＤ分割手段４が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。この符号化処理は、以下のようにして行われる。

まず、符号化手段５は、作成するＬＵＴの段数を表す内部変数ｉを０として（Ｓ３）、ＢＤＤ分割手段４が生成したｉ番目の部分グラフの出力数ｕ（ｉ）を計算する（Ｓ４）。ここで、部分グラフの出力数ｕ（ｉ）は（数１）により計算することができる。例えば、図５（ｂ）に示したＲＯＢＤＤを分割して得られる各部分グラフの出力数は２となる。

次に、符号化手段５は、ｉ番目の部分グラフの出力のうち、終端節点に対しては、その終端節点の値に対応して決められた特定の符号を割り当てる。本実施例においては、符号化手段５は、節点値０の終端節点に対しては「０…０」、節点値１の終端節点に対しては「１…１」の符号を割り当てる（Ｓ５）。また、符号化手段５は、ｉ番目の部分グラフの出力の非終端節点に対して、上記終端節点に割り当てた符号以外の符号を割り当てる（Ｓ６）。そして、符号化手段５は、以上の符号割り当てにより、ｉ番目のＬＵＴを生成し、これをＬＵＴ記憶手段６に格納する（Ｓ７）。

以上のステップＳ５〜Ｓ８までの動作を、ｉを１ずつ繰り上げながら、ｉがｓ−１となるまで繰り返す（Ｓ８）。ｉがｓ−１となるまでステップＳ４〜Ｓ７の動作を行ってｓ個のＬＵＴを生成した時点で、ＬＵＴ符号化装置は動作を終了する。

〔例１．３〕
図５（ｂ）に示したようなＲＯＢＤＤの部分グラフを符号化手段５により符号化することによって、図６に示したようなＬＵＴカスケードが生成され、ＬＵＴ記憶手段６に格納される。図６において、各ＬＵＴの出力値（y_2i+1，y_2i）には、値が０の終端節点に対して「００」又は「０」が、値が１の終端節点に対して「１１」又は「１」が割り当てられる。図５（ｂ）のＲＯＢＤＤから符号化により作成されたＬＵＴの例を（表２）に示す。尚、（表２）において、「x」はドント・ケアを表す。

このような符号化により生成された各ＬＵＴにより、図６のようなＬＵＴカスケードを構成した場合、各段のＬＵＴの出力値が総て０又は総て１である場合には、終端節点であることを識別することが可能となる。従って、各段のＬＵＴの出力値を監視し、総て０の出力を検出した時点でｆ＝０を出力して計算を終了し、又は、総て１の出力を検出した時点でｆ＝１を出力して計算を終了する。これにより、従来は４回のメモリアクセスを必要としたＬＵＴカスケード論理回路による演算を、平均２．３７５回のメモリアクセスにより行うことが可能となる。
（例終わり）

本実施例においては、出力変数が複数ビットである多端子二分決定グラフ（Multi-Terminal BDD．以下、「ＭＴＢＤＤ」という。）に対して、ＬＵＴカスケード論理回路の演算速度を高速化するための符号化方法について説明する。

図７は本発明の実施例２に係るＬＵＴ符号化装置の構成を表すブロック図である。図７において、論理仕様記憶手段１及びＬＵＴ記憶手段６は、図１と同様のものであるため、同符号を付して説明は省略する。本実施例に係るＬＵＴ符号化装置は、更に、ＭＴＢＤＤ生成手段９、ＭＴＢＤＤ記憶手段１０、ＢＤＤ分割手段１１、及び符号化手段１２を備えている。

ＭＴＢＤＤ生成手段９は、論理仕様記憶手段１に記憶された目的論理関数を表す論理仕様からＭＴＢＤＤを生成してＭＴＢＤＤ記憶手段１０に格納する。ＢＤＤ分割手段１１は、ＭＴＢＤＤ記憶手段１０に格納されたＭＴＢＤＤを、所定の大きさの部分グラフに分割する。符号化手段１２は、ＢＤＤ分割手段１１が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。

以上のように構成された本実施例に係るＬＵＴ符号化装置について、以下その動作を説明する。

図８は本発明の実施例２に係るＬＵＴ符号化方法を表すフローチャートである。まず、ＭＴＢＤＤ生成手段９は、論理仕様記憶手段１に格納された論理仕様を読み出してＭＴＢＤＤを生成し、これをＭＴＢＤＤ記憶手段１０に格納する（Ｓ１１）。続いて、ＢＤＤ分割手段１１は、ＭＴＢＤＤ記憶手段１０に格納されたＭＴＢＤＤを、所定の大きさのｓ個の部分グラフに分割する（Ｓ１２）。

〔例２．１〕
例えば、目的論理関数が、入力変数A＝（a₃ a₂ a₁ a₀），B＝（b₃ b₂ b₁ b₀）の大小を比較する４ビット比較器であるとする。４ビット比較器は、例えば、（数３）により表される。

ＭＴＢＤＤ生成手段９は、（数３）で表される論理仕様から図９に示すようなＭＴＢＤＤを生成し、ＭＴＢＤＤ記憶手段１０に格納する。図９において、ＭＴＢＤＤは２ビットの出力変数Ｆを出力する。Ａ＞Ｂの場合にはＦ＝（００）、Ａ＝Ｂの場合にはＦ＝（１１）、Ａ＜Ｂの場合にはＦ＝（０１）が出力される。入力変数Ａ，Ｂの比較は、上位ビットから比較することにより行われる。すなわち、まず、a₃，b₃を比較してa₃＞b₃ならばA＞B、a₃＜b₃ならばA＜Bと決定する。a₃＝b₃のときは、次の下位ビットa₂，b₂を比較する。a₂＞b₂ならばA＞B、a₂＜b₂ならばA＜Bと決定する。a₂＝b₂のときは、次の下位ビットa₁，b₁を比較する。以下同様に比較演算を行い、入力変数AとBの比較が行われる。

そして、ＢＤＤ分割手段１１は、このＭＴＢＤＤを、例えば、図９の一点鎖線の箇所において分割し、３個の部分グラフを生成する。図９では、４入力のＬＵＴにより構成されるようにＭＴＢＤＤの分割を行ったものである。一般に、ＬＵＴの入力変数の数が指定された数以下となるように、ＭＴＢＤＤの分割が行われる。
（例終わり）

次に、符号化手段１２は、ＢＤＤ分割手段１１が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。この符号化処理は、以下のようにして行われる。

まず、符号化手段１２は、内部変数ｉを０として（Ｓ１３）、ＢＤＤ分割手段１１が生成するｉ番目の部分グラフの出力数ｕ（ｉ）を計算する（Ｓ１４）。ここで、部分グラフの出力数ｕ（ｉ）は（数１）により計算される。例えば、図９に示したＭＴＢＤＤを分割して得られる各部分グラフの出力数は２となる。

次に、符号化手段１２は、ｉ番目の部分グラフの出力のうち、終端節点に対しては、その終端節点の値に対応して決められた特定の符号を割り当てる。本実施例においては、符号化手段１２は、ｉ番目の部分グラフの出力（y_u(i)，y_u(i)-1，…，y₀）のうち終端節点に対しては、２進数（y_u(i)，y_u(i)-1，…，y₀）₂が所定の閾値t_i以下となるように符号の割り当てを行う（Ｓ１５）。これにより、ｉ番目の部分グラフの出力から得られる２進数（y_u(i)，y_u(i)-1，…，y₀）₂と閾値t_iとを比較することにより、（y_u(i)，y_u(i)-1，…，y₀）₂≦t_iであれば終端節点であることを判別することが可能となる。

尚、終端節点に対する符号の割り当て方法はこの方法に限られるものではなく、終端節点であることが識別できる符号であれば、どのような符号の割り当て方を用いてもよい。

また、符号化手段１２は、ｉ番目の部分グラフの出力の非終端節点に対して、上記終端節点に割り当てた符号以外の符号を割り当てる（Ｓ１６）。そして、符号化手段１２は、以上の符号割り当てにより、ｉ番目のＬＵＴを生成し、これをＬＵＴ記憶手段６に格納する（Ｓ１７）。

以上のステップＳ１４〜Ｓ１７までの動作を、ｉを１ずつ繰り上げながら、ｉがｓ−１となるまで繰り返す（Ｓ１８）。ｉがｓ−１となるまでステップＳ１４〜Ｓ１７の動作を行ってｓ個のＬＵＴを生成した時点で、ＬＵＴ符号化装置は動作を終了する。

〔例２．２〕
図９に示したようなＭＴＢＤＤの部分グラフを符号化手段１２により符号化することによって、図１０（ａ）に示したようなＬＵＴカスケードが生成され、ＬＵＴ記憶手段６に格納される。図１０（ａ）において、ＬＵＴ_０，ＬＵＴ_１の出力値には、Ａ＞Ｂの終端節点に対して符号「００」が、Ａ＜Ｂの終端節点に対して符号「０１」が割り当てられる。終端節点以外の節点に対しては、符号「１１」又は符号「１０」の何れかを割り当てることができる。また、最終段のＬＵＴ_２の出力値には、Ａ＞Ｂの終端節点に対して符号「００」が、Ａ＜Ｂの終端節点に対して符号「０１」が、Ａ＝Ｂの終端節点に対して符号「１１」又は符号「１０」が割り当てられる。

図９のＭＴＢＤＤから符号化により作成されたＬＵＴの例を（表３）に示す。（表３）では、ＬＵＴ_０，ＬＵＴ_１の出力値のうち終端節点以外の節点に対しては符号「１１」を割り当てて符号化を行っている。また、ＬＵＴ_２の出力は総て終端節点なので、符号「００」、「０１」、「１１」を割り当てて符号化を行っている。尚、「ｘ」は、ドント・ケアを表す。

このような符号化を行うことによって、ＬＵＴ_０又はＬＵＴ_１による演算が終了した時点で、ＬＵＴの出力値（ｙ_2i，ｙ_2i+1）を２進数で表した値（ｙ_2iｙ_2i+1）₂が（０１）_２以下であれば、終端節点に達したものと判定することが可能である。従って、ＬＵＴ_０又はＬＵＴ_１の出力値から終端節点に達したことが検出されると、出力値（ｙ_2i，ｙ_2i+1）を出力F＝（F₀，F₁）として出力し、演算を終了することが可能となる。これにより、従来は３回のメモリアクセスを必要としたＬＵＴカスケード論理回路による演算を、平均１．３７５回のメモリアクセスにより行うことが可能となる。
（例終わり）

本実施例においては、実施例１又は実施例２で説明したＬＵＴ符号化方法によって符号化されたＬＵＴカスケードを用いて、目的論理関数の演算を行うＬＵＴカスケード論理回路について説明する。

図１１は本発明の実施例３に係るＬＵＴカスケード論理回路の構成を表すブロック図である。本実施例に係るＬＵＴカスケード論理回路は、論理関数メモリ２１、入力変数レジスタ２２、入力変数選択回路２３、入力選択メモリ２４、接続回路２５、接続メモリ２６、出力デコーダ２７、出力レジスタ２９、及び演算制御部３０を備えている。

論理関数メモリ２１は、目的論理関数に基づいて、上記実施例１，２において説明した符号化方法によって生成された複数のＬＵＴが記憶されている。この論理関数メモリ２１には、通常のＳＲＡＭ（Static Random Access Memory）等が使用される。

論理関数メモリ２１は、メモリのｉページ目（ｉ＝０，１，…）にｉ段目のＬＵＴ（以下、「ＬＵＴ_ｉ」と表す。）が格納されている。従って、論理関数メモリ２１のｉページを読み出すことにより、ＬＵＴ_ｉにアクセスすることが可能となる。

〔例３．１〕
例えば、目的論理関数が、図１０（ａ）に示したような３つのＬＵＴ（ＬＵＴ_０，ＬＵＴ_１，ＬＵＴ_２）からなるＬＵＴカスケードにより表される場合、図１０（ｂ）に示したように、ＬＵＴ_０は論理関数メモリ２１の０ページ目に、ＬＵＴ_１は論理関数メモリ２１の１ページ目に、ＬＵＴ_２は論理関数メモリ２１の２ページ目に、それぞれ格納される。これにより、例えば、ＬＵＴ_１を読み出す場合には、論理関数メモリ２１の１ページにアクセスすればよいことになる。
（例終わり）

論理関数メモリ２１は、u+mビットのアドレス入力端子A₀〜A_u+m-1、uビットのデータ出力端子D₀〜D_u-1、及び、アドレス・ストローブ（address strobe）端子(AS)nを備えている。尚、「( )n」の記号は負論理であることを表す。アドレス・ストローブ端子(AS)nには、外部から入力されるクロックCLKが入力される。論理関数メモリ２１は、アドレス・ストローブ端子(AS)nから入力されるクロックの立ち下がりにおいて、アドレス入力端子A₀〜A_u+m-1に入力されているアドレス値を、内部のアドレス・レジスタにラッチする。そして、アドレス・レジスタにラッチされたアドレス値が示すアドレスに格納されたデータの値を、データ出力端子D₀〜D_u-1から出力する。

入力変数レジスタ２２は、ＬＵＴカスケードの各段のＬＵＴに対して入力する入力変数を一時的に記憶するレジスタである。入力変数レジスタ２２には、外部からのデータ入力（Data input）の他に、制御信号として、データ・ストローブ信号(DS)nが入力される。入力変数レジスタ２２は、データ・ストローブ信号(DS)nの立ち下がりにおいて、外部からのデータ入力（Data input）をラッチする。

入力変数選択回路２３は、入力変数レジスタ２２が出力する入力変数から、ＬＵＴカスケードの各段で使用する入力変数を選択する回路である。入力変数選択回路２３としては、クロスバ・スイッチ、マルチプレクサ、シフタ等が使用される。また、入力選択メモリ２４には、ＬＵＴカスケードの各ＬＵＴに対応して、当該ＬＵＴにおいて使用する入力変数の選択に関する情報が格納されている。入力変数選択回路２３のデータ入力端子は、入力変数レジスタ２２の出力端子に接続されている。入力変数選択回路２３の選択制御入力端子は、ｍ_iビットの入力選択メモリ２４の出力端子に接続されている。

接続回路２５は、ＬＵＴカスケードの各ＬＵＴで使用する変数を選択して論理関数メモリ２１のアドレス入力端子に接続するための切換回路である。また、接続メモリ２６には、ＬＵＴカスケードの各ＬＵＴに対応して、当該ＬＵＴで使用する変数（入力変数及び中間変数）を論理関数メモリ２１に接続するための接続切換信号が格納されている。

接続回路２５は、入力端子X₀〜X_u-1,Y₀〜Y_u-1、出力端子W₀〜W_u-1、及び切換制御入力端子C₀〜C_u-1を備えている。入力端子Y₀〜Y_u-1は、入力変数選択回路２３の各出力端子に接続されている。入力端子X₀〜X_u-1は、論理関数メモリ２１の各出力端子D₀〜D_u-1に接続されている。出力端子W₀〜W_u-1は、論理関数メモリ２１のアドレス入力端子A₀〜A_u-1に接続されている。また、切換制御入力端子C₀〜C_u-1は、接続メモリ２６の各出力端子に接続されている。接続回路２５は、入力端子X₀〜X_u-1,Y₀〜Y_u-1と出力端子W₀〜W_u-1との接続を、切換制御入力端子C₀〜C_u-1から入力される接続切換信号INSELに従って切り換える。

尚、論理関数メモリ２１のアドレス入力端子A_u〜A_u+m-1には、演算制御部３０から出力されるｍビットのページ・カウント信号CNTの出力線が接続されている。

出力デコーダ２７は、符号化された論理関数メモリ２１の出力値を復号して、ＬＵＴカスケードの出力変数f₀〜f_n-1を出力するための回路である。出力デコーダ２７は、ＬＵＴカスケードの各段のＬＵＴの出力に対する復号テーブルが格納されたメモリにより構成されている。出力デコーダ２７は、u+mビットの入力端子A₀〜A_u+m-1と、nビットの出力端子D₀〜D_n-1とを備えている。出力デコーダ２７のデータ入力端子A₀〜A_u-1は、それぞれ論理関数メモリ２１の出力端子D₀〜D_u-1に接続されている。また、出力デコーダ２７のデータ入力端子A_u〜A_u+m-1には、後述のページ・カウンタ３５が出力するページ・カウント信号CNTが入力される。このページ・カウント信号CNTによって、復号テーブルが選択される。そして、データ入力端子A₀〜A_u-1から入力されるＬＵＴ出力値d₀〜d_u-1に対応する復号テーブルの値が、出力デコーダ２７の出力端子D₀〜D_n-1から、出力変数f₀〜f_n-1として出力される。

出力レジスタ２９は、出力デコーダ２７から出力されるＬＵＴカスケードの出力変数f₀〜f_n-1をラッチして記憶するレジスタである。出力レジスタ２９は、後段の回路との同期をとるためのバッファとしての役割を有する。出力レジスタ２９は、nビットのデータ入力端子Di₀〜Di_n-1、nビットのデータ出力端子Do₀〜Do_n-1、クロック入力端子CLK、チップ・セレクト端子CE、及びリセット端子(R)nを備えている。リセット端子(R)nには、外部からのリセット信号(RST)nが入力される。このリセット端子(R)nに０が入力されると、出力レジスタ２９は、ラッチした値をすべて０として、データ出力端子Do₀〜Do_n-1の出力値を０とする。チップ・セレクト端子CEには、後述の演算制御部３０が出力するアウトプット・イネーブル信号(OE)nが入力される。クロック入力端子CLKには、外部からのクロックCLKが入力される。リセット端子(R)nに０が入力された状態であっても、チップ・セレクト端子CEの入力値が１のときには、出力レジスタ２９は、データ入力端子Di₀〜Di_n-1からの入力を受け付けない。一方、チップ・セレクト端子CEの入力値が０のときには、出力レジスタ２９は、クロックCLKの立ち上がりにおいて、データ入力端子Di₀〜Di_n-1からの入力をラッチする。そして、ラッチしたデータを、データ出力端子Do₀〜Do_n-1から出力する。

演算制御部３０は、ＬＵＴカスケード論理回路全体の演算動作の制御を行う。演算制御部３０の詳細については後で詳述する。

図１２は図１１の入力変数選択回路の構成の一例を示す図である。図１２においては、入力変数選択回路２３は循環的なバレルシフタにより構成している。ここでは、一例として、入力変数選択回路２３は１７入力８出力としているが、入出力数はこれに限られるものではない。

入力変数選択回路２３は、入力側から、８ビットの循環的なバレルシフタ２３−３、４ビットの循環的なバレルシフタ２３−２、２ビットの循環的なバレルシフタ２３−１、１ビットの循環的なバレルシフタ２３−０が直列に接続された構成からなる。バレルシフタ２３−３の各入力パッドIn₀〜In₁₆には、入力変数レジスタ２２の各出力端子が接続される。また、バレルシフタ２３−０の各入力パッドOut₀〜Out₇には、接続回路２５の入力端子の一部が接続される。各バレルシフタ２３−０〜２３−３は、入力選択メモリ２４から入力される４ビットの選択信号INSEL（INSEL₀〜INSEL₃）により任意ビット数の循環的なシフトを行う。これにより、入力変数レジスタ２２の各出力端子の一部と接続回路２５の入力端子の一部との接続位置を自由に変更することが可能である。

図１３は図１１の接続回路の構成の一例を示す図である。図１３（ａ）は接続回路２５の全体構成を表している。図１３（ａ）において、接続回路２５の変数入力端子X₀〜X_u-1は、それぞれ、論理関数メモリ２１のｕ本の出力端子D₀〜D_u-1に接続される。また、接続回路２５の変数入力端子Y₀〜Y_u-1は、入力変数選択回路２３のｕ本の出力端子x₀〜x_u-1に接続される。また、接続回路２５の選択入力端子C₀〜C_u-1は、接続メモリ２６のｕ本の出力端子CNSET₀〜CNSET_u-1に接続される。一方、接続回路２５の変数出力端子W₀〜W_u-1は、それぞれ、論理関数メモリ２１のｕ本のアドレス入力端子A₀〜A_u-1に接続される。

接続回路２５の変数入力端子X_i，Y_i及び変数出力端子W_i（ｉ∈{0,1,…,u-1}）の交点には、切換回路２５ａが設けられている。選択入力端子C_iには、これらの各切換回路２５ａを制御するための信号が入力される。

切換回路２５ａは、具体的には、図１３（ｂ）に示したような論理回路により構成されている。図１３（ｂ）の切換回路２５ａは、入力X_i，Y_i，C_iに対して、出力W_iは（数４）のようになる。

すなわち、接続メモリ２６から選択入力端子C_iに入力される接続切換信号CNSET_iが論理０の場合には、W_i=Y_iとなり、入力変数選択回路２３の出力端子x_iが論理関数メモリ２１の入力端子A_iに接続される。これにより、ＬＵＴカスケードの次段のＬＵＴに入力変数x_iを直接入力することができる。

一方、接続メモリ２６から選択入力端子C_iに入力される接続切換信号CNSET_iが論理１の場合には、W_i=X_iとなり、入力変数選択回路２３の出力端子x_iが論理関数メモリ２１の入力端子A_iに接続される。これにより、ＬＵＴカスケードの前段のＬＵＴの出力である中間変数を後段のＬＵＴの入力変数として転送することができる。

図１４は図１１の演算制御部の構成を表すブロック図である。本実施例に係る演算制御部３０は、ページ・カウンタ３５、終端判定値メモリ３６、終端節点判定器３７、ＡＮＤ回路３８、及びビジー生成回路３９を備えている。

ページ・カウンタ３５は、外部から入力されるクロックCLKを計数し、その計数値をｍビットのページ・カウント信号CNTとして出力するカウンタである。このページ・カウント信号CNTは、ＬＵＴカスケードのうち、次に演算を行うＬＵＴの段数に対応している。ページ・カウンタ３５は、クロック入力端子CLK、リセット入力端子(R)n、及びmビットのデータ出力端子Q₀〜Q_m-1を備えている。クロック入力端子CLKには、外部からのクロックCLKが入力される。ページ・カウンタ３５は、クロックCLKの立ち上がりをカウントして、データ出力端子Q₀〜Q_m-1から、ページ・カウント信号CNTとして出力する。リセット入力端子(R)nは、ＡＮＤ回路３８の出力端子に接続されている。リセット入力端子(R)nが０のとき、ページ・カウンタ３５は、ページ・カウント信号CNTを強制的に０クリアする。

終端判定値メモリ３６には、各ページ・カウント信号CNTに対して、そのページ・カウント信号CNTに対応する段のＬＵＴの出力が終端節点であるか否かを判定するための判定値が記憶されている。この終端判定値メモリ３６は、mビットのアドレス入力端子Di₀〜Di_m-1、uビットのデータ出力端子Do₀〜Do_u-1、及びアドレス・ストローブ端子(AS)nを備えている。アドレス入力端子 Di₀〜Di_m-1には、ページ・カウンタ３５が出力するページ・カウント信号CNTが入力される。アドレス・ストローブ端子(AS)nには、クロックCLKが入力される。終端判定値メモリ３６は、クロックCLKの立ち下がりで、ページ・カウント信号CNTをラッチする。そして、ラッチされたページ・カウント信号CNTの値で指定されるアドレスに格納されている判定値を、終端判定閾値th₀〜th_u-1として、データ出力端子Do₀〜Do_u-1から出力する。

終端節点判定器３７は、デジタル・コンパレータ４０、Ｔフリップ・フロップ４１、Ｄフリップ・フロップ４２、及びＯＲ回路４３により構成されている。この終端節点判定器３７は、終端判定値メモリ３６から出力される判定値と、論理関数メモリ２１の出力値とを比較する。そして、終端節点に達したか否かを判定し、その判定値をアウトプット・イネーブル信号(OE)nとして出力する。終端節点に達した場合には、アウトプット・イネーブル信号(OE)nとして０を出力し、達していない場合には１を出力する。

デジタル・コンパレータ４０は、uビットの入力端子A、uビットの入力端子B、及び１ビットの出力端子(A<B)を備えている。入力端子Aには、終端判定閾値th₀〜th_u-1が入力される。入力端子Bには、論理関数メモリ２１から、ＬＵＴ出力値d₀〜d_u-1が入力される。デジタル・コンパレータ４０は、入力端子A,Bから入力されるデータを比較して、A<Bの場合には１を出力し、A≧Bの場合には０を出力する。デジタル・コンパレータ４０の出力値は、ＯＲ回路４３において、Ｄフリップ・フロップ４２の出力値(Q)nとＯＲ演算がされた後、アウトプット・イネーブル信号(OE)nとして出力される。

尚、終端節点判定器３７内部の、Ｔフリップ・フロップ４１、Ｄフリップ・フロップ４２、及びＯＲ回路４３により構成される回路は、回路がリセット信号(RST)nによりリセットされた直後に生じる、論理関数メモリ２１の出力データの不定期間において、アウトプット・イネーブル信号(OE)nが不定とならないように補償するための回路である。詳細な動作については、後述する。

ＡＮＤ回路３８は、ページ・カウンタ３５のリセット信号を生成するための回路である。ＡＮＤ回路３８は、終端節点判定器３７の出力するアウトプット・イネーブル信号(OE)nと、リセット信号(RST)nと、Ｄフリップ・フロップ４２の出力QとのＡＮＤ演算を行い、その論理値をページ・カウンタ３５のリセット端子(R)nに入力する。

ビジー生成回路３９は、入力回路４４、Ｄフリップ・フロップ４５、ＡＮＤ回路４６、及びＯＲ回路４７により構成されている。ビジー生成回路３９は、各時刻で演算処理中であることを表すビジー信号BUSYを生成する回路である。ビジー信号BUSYはクロックCLKに同期して出力される。ビジー信号BUSYは、リセット信号(RST)nが０（有効）となった直後から演算処理が終了するまでの期間、及びデータ・ストローブ信号(DS)nが０（有効）となった直後から演算処理が終了するまでの期間に１（有効）となり、それ以外の期間は０（無効）となる。ビジー生成回路３９の動作については、後で詳述する。

図１４は、実施例２で説明したＬＵＴ符号化方法により符号化されたＬＵＴカスケードを演算するための回路構成を示したものである。従って、終端判定値メモリ３６には、実施例２で説明した終端節点を判定するための閾値が記憶されている。

尚、実施例１で説明したＬＵＴ符号化方法により符号化されたＬＵＴカスケードを演算する場合、この構成は簡略化することができる。すなわち、終端判定値メモリ３６は不要となり、終端節点判定器３７のデジタル・コンパレータ４０の代わりに、論理関数メモリ２１の出力値が総て０か、総て１かを判定するためのＮＯＲゲート及びＡＮＤゲートを用いた回路を使用すればよい。

以上のように構成された本実施例に係るＬＵＴカスケード論理回路について、以下その動作を説明する。

図１５は図１１及び図１４の各端子の出力値を表すタイムチャート、図１６は図１４の各出力値を表すタイムチャートである。初期値として、データ・ストローブ信号(DS)nは１（無効）に設定されており、外部データ入力信号（Data input）には、最初の論理演算において使用する各入力変数の値が設定されている。また、リセット信号(RST)nには１（無効）が設定されている。以下、時間を追って、ＬＵＴカスケード論理回路の動作を説明する。

尚、図１５の例においては、論理関数メモリ２１の入力数は６ビット（入力変数４ビット＋ページ番号２ビット）、出力数は４ビットとした。また、論理関数メモリ２１には図１７に示したような、４つのＬＵＴを格納して演算を実行している。尚、図１７において、「ｘ」はドント・ケアを表す。

〔１〕リセットからリセット直後の演算処理動作
（１）時刻t₀
まず、時刻t₀においてリセット信号(RST)nが０（有効）とされる。リセット信号(RST)nが０となると、出力レジスタ２９がリセットされ、出力レジスタ２９のnビットの出力値（Data OUT）はすべて０となる。また、演算制御部３０のＡＮＤ回路３８には、リセット信号(RST)n、アウトプット・イネーブル信号(OE)n、及びＤフリップ・フロップ４２の出力Qが入力されている。従って、リセット信号(RST)nが０となると、ＡＮＤ回路３８は０を出力する。これにより、ページ・カウンタ３５が出力するページ・カウント信号CNTの値が０クリアされる。そして、入力選択メモリ２４、接続メモリ２６、出力デコーダ２７、及び終端判定値メモリ３６の出力ページ数が０ページに設定される。

入力選択メモリ２４は、０ページに格納されたm_iビットの選択信号INSELを出力する。ここで、選択信号INSELは、入力変数選択回路２３において、入力変数レジスタ２２の出力のうちの一部を選択して接続回路２５に出力するための選択情報を有するバイナリ信号である。また、接続メモリ２６は、０ページに格納された接続回路２５の接続切換信号CNSETを出力する。ここで、接続切換信号CNSETは、接続回路２５の2u個の入力端子X₀〜X_u-1, Y₀〜Y_u-1から入力される入力信号のうち、u個の出力端子W₀〜W_u-1から出力する信号を選択するための選択情報を有するuビットのバイナリ信号である。また、終端判定値メモリ３６は、０ページに格納されたuビットの終端判定閾値th₀〜th_u-1を出力する。

選択信号INSELが制定されると、その選択信号INSELに従って、入力変数選択回路２３が切り換わる。しかしながら、この時点では、入力変数レジスタ２２の出力は不定である。従って、入力変数選択回路２３の出力値であるuビットの入力変数信号x₀〜x_u-1の値も不定である。また、接続切換信号CNSETが制定されると、接続回路２５の接続状態が切り換わる。しかしながら、この時点では、入力変数信号x₀〜x_u-1の値も論理関数メモリ２１の出力値（「ＬＵＴ出力値」という。）d₀〜d_u-1も不定である。従って、接続回路２５のuビットの出力値（「ＬＵＴ変数値」という。）a₀〜a_u-1も不定である。更に、終端判定閾値th₀〜th_u-1が制定されると、デジタル・コンパレータ４０の出力値(A<B)も切り換わる。しかしながら、この時点では、ＬＵＴ出力値d₀〜d_u-1は不定である。従って、デジタル・コンパレータ４０の出力値(A<B)も不定である。

一方、時刻t₀において、リセット信号(RST)nが０（有効）とされると、終端節点判定器３７内のＤフリップ・フロップ４２のリセット端子(R)nの入力値が０（有効）となる。これに伴って、Ｄフリップ・フロップ４２の出力Qは０となり、出力(Q)nは１となる。また、リセット信号(RST)nが０（有効）とされると、Ｔフリップ・フロップ４１のセット端子(S)nの入力値が０（有効）となる。また、Ｔフリップ・フロップ４１のリセット端子Rには、Ｄフリップ・フロップ４２の出力Qが入力されているので、このリセット端子Rの入力値は０（無効）となる。従って、Ｔフリップ・フロップ４１の出力(Q)nは０に設定される。

Ｄフリップ・フロップ４２の出力(Q)nが１となると、ＯＲ回路４３は、デジタル・コンパレータ４０の出力値(A<B)とＤフリップ・フロップ４２の出力(Q)nとのＯＲ演算を行う。従って、デジタル・コンパレータ４０の出力値(A<B)が不定であるが、Ｄフリップ・フロップ４２の出力(Q)nが１なので、ＯＲ回路４３の出力値は１となる。すなわち、アウトプット・イネーブル信号(OE)nは１（無効）に設定される。これにより、出力信号（Data OUT）として不定な値が出力されることが防止される。

一方、時刻t₀において、リセット信号(RST)nが０（有効）とされると、ビジー生成回路３９内のＤフリップ・フロップ４５のリセット端子(R)nの入力値が０となる。従って、Ｄフリップ・フロップ４５はリセットされて、出力Qは０となる。

また、ビジー生成回路３９内のＯＲ回路４７には、ビジー生成回路３９内のＤフリップ・フロップ４５の出力Qと、終端節点判定器３７内のＤフリップ・フロップ４２の出力(Q)nとが入力される。そして、両者のＯＲ論理を、ビジー信号BUSYとして出力する。上述のように、時刻t₀で、Ｄフリップ・フロップ４２の出力(Q)nは１に設定される。従って、ＯＲ回路４７は、ビジー信号（BUSY）として１（有効）を出力する。このように、リセット直後の不定な状態において、Ｄフリップ・フロップ４２の出力(Q)nを使ってビジー信号BUSYを１（有効）としておくことで、誤った出力値（Data OUT）が出力されることが防止される。

（２）時刻t₁
時刻t₁において、リセット信号(RST)nは１（無効）となる。このとき、終端節点判定器３７のＴフリップ・フロップ４１の出力(Q)nは０に、Ｄフリップ・フロップ４２の出力(Q)nは１に、ビジー生成回路３９のＤフリップ・フロップ４５の出力Qは０に、それぞれラッチされた状態で保持される。従って、アウトプット・イネーブル信号(OE)nは１（無効）に、ビジー信号BUSYは１に保持される。

また、終端節点判定器３７のＴフリップ・フロップ４１のセット端子(S)nの入力値は１（無効）となり、Ｔフリップ・フロップ４１はトリガ入力の受け付けが可能となる。また、終端節点判定器３７のＤフリップ・フロップ４２のリセット端子(R)nの入力値は１（無効）となり、Ｄフリップ・フロップ４２は、クロックCLKの立ち下がりにおいてデータ入力の受け付けが可能となる。

一方、ＡＮＤ回路３８の入力のうち、Ｄフリップ・フロップ４２の出力Qの値は０である。従って、ＡＮＤ回路３８の出力は０に保持される。そして、ページ・カウンタ３５は、リセット状態に保持される。

（３）時刻t₂
時刻t₂において、データ・ストローブ信号(DS)nが０となる。このデータ・ストローブ信号(DS)nは、ビジー生成回路２９内の入力回路４４に入力されている。入力回路４４は、データ・ストローブ信号(DS)nの反転論理と、ＡＮＤ回路４６の出力値とのＯＲ論理を出力する。従って、入力回路４４は、Ｄフリップ・フロップ４５の入力端子Dに対して１を出力する。

また、このデータ・ストローブ信号(DS)nの立ち下がりにおいて、入力変数レジスタ２２は、外部データ入力信号（Data input）の値をラッチし、入力変数選択回路２３に出力する。入力変数選択回路２３は、入力変数レジスタ２２から入力される入力データを、選択信号INSELの値に従って選択し、入力変数信号x₀〜x_u-1として接続回路２５に出力する。この時点で、入力変数信号x₀〜x_u-1の値が確定する。接続回路２５は、接続切換信号CNSETの値に従って、入力端子Y₀〜Y_u-1より入力される入力変数信号x₀〜x_u-1の値を、出力端子W₀〜W_u-1からＬＵＴ変数値a₀〜a_u-1として出力する。この時点で、ＬＵＴ変数値a₀〜a_u-1の値も確定する。

（４）時刻t₃
時刻t₃において、クロックCLKが０から１に変化する。この立ち上がりにおいて、ビジー生成回路３９内のＤフリップ・フロップ４５は、入力端子Dから入力されている論理値１をラッチして、出力端子Qに出力する。このＤフリップ・フロップ４５の出力は、ＯＲ回路４７に入力される。ＯＲ回路４７のもう一方の入力には、その前から、Ｄフリップ・フロップ４２の反転出力(Q)nとして論理値１が入力されているので、ここではＯＲ回路４７の出力は１に保持されたままで変化はしない。従って、ビジー信号BUSYは１に保持される。

（５）時刻t₄
時刻t₄において、データ・ストローブ信号(DS)nが０から１に変化する。終端節点判定器３７内のＴフリップ・フロップ４１のトリガ入力端子Ｔには、データ・ストローブ信号(DS)nが入力されている。従って、データ・ストローブ信号(DS)nの立ち上がりにおいて、Ｔフリップ・フロップ４１の出力(Q)nは０から１に反転する。

（６）時刻t₅
時刻t₅において、クロックCLKが１から０に変化する。このとき、論理関数メモリ２１は、この立ち下がりにおいて、アドレス端子A₀〜A_u+m-1より入力されているＬＵＴ変数値a₀〜a_u-1及びページ・カウント信号CNTの値（０）を、内部のアドレス・レジスタにラッチする。これに伴って、論理関数メモリ２１は、０ページに格納された１段目のＬＵＴを使用して、ＬＵＴ変数値a₀〜a_u-1を入力とする選択演算を行い、その結果を出力端子D₀〜D_u-1からＬＵＴ出力値d₀〜d_u-1として出力する。この時点で、ＬＵＴ出力値d₀〜d_u-1の値が確定する。

また、デジタル・コンパレータ４０の入力端子Aには終端判定閾値th₀〜th_u-1が入力されており、入力端子BにはＬＵＴ出力値d₀〜d_u-1が入力されている。従って、ＬＵＴ出力値d₀〜d_u-1が確定すると、デジタル・コンパレータ４０は、終端判定閾値th₀〜th_u-1とＬＵＴ出力値d₀〜d_u-1とを比較して、ＬＵＴ出力値d₀〜d_u-1が終端判定閾値th₀〜th_u-1より大きい場合には１（未終了）を、それ以外の場合には０（終了）を出力する。この時点で、デジタル・コンパレータ４０の出力値（A<B）が確定する。図１５の例では、最初の演算の結果、まだ終端節点に達していないとして、デジタル・コンパレータ４０は、１を出力している。デジタル・コンパレータ４０の出力値（A<B）は、ＯＲ回路４３の入力端子の一方に入力される。

一方、終端節点判定器３７内のＤフリップ・フロップ４２は、このクロックCLKの立ち下がりにおいて、Ｔフリップ・フロップ４１の出力(Q)nから入力されている論理値１をラッチする。そして、Ｄフリップ・フロップ４２は、出力端子Qに論理値１を、出力端子(Q)nに論理値０を出力する。Ｄフリップ・フロップ４２の出力(Q)nが０となると、ＯＲ回路４３の入力の一方が０となる。しかしながら、ＯＲ回路４３のもう一方の入力端子へ入力されているデジタル・コンパレータ４０の出力値（A<B）は１なので、ＯＲ回路４３の出力は１に保持される。従って、アウトプット・イネーブル信号(OE)nは１（無効）に保持される。

また、Ｄフリップ・フロップ４２の出力端子Qは、Ｔフリップ・フロップ４１のリセット端子Rに接続されている。従って、Ｔフリップ・フロップ４１はリセット状態となり、以降はその出力(Q)nは１に固定される。Ｔフリップ・フロップ４１の出力(Q)nが１に固定されると、Ｄフリップ・フロップ４２の出力端子Qも１に固定される。その結果、時刻t₅以降は、次にリセット信号(RST)nが０となるまでは、Ｔフリップ・フロップ４１及びＤフリップ・フロップ４２の出力値は固定され、これらの回路は他の外部入力を受け付けなくなる。

さらに、Ｄフリップ・フロップ４２の出力Qが１となると、アウトプット・イネーブル信号(OE)nは１、リセット信号(RST)nは１なので、ＡＮＤ回路３８の出力が１となる。これにより、ページ・カウンタ３５は、リセット状態が解除され、クロックCLKのカウントが可能な状態となる。

（７）時刻t₆
時刻t₆において、クロックCLKは０から１に変化する。このクロックCLKの立ち上がりにおいて、ページ・カウンタ３５は、ページ・カウント信号CNTの値を１だけ増加させる。ページ・カウント信号CNTが１となると、入力選択メモリ２４、接続メモリ２６、出力デコーダ２７、及び終端判定値メモリ３６の出力ページ数が１ページに設定される。

入力選択メモリ２４の出力ページ数が１ページに切り換わると、選択信号INSELの値が、２段目のＬＵＴの入力変数を選択する信号に切り換わる。これにより、入力変数選択回路２３の接続の切り換えが行われ、入力変数信号x₀〜x_u-1の値が変更される。

接続メモリ２６の出力ページ数が１ページに切り換わると、接続切換信号CNSETの値が、２段目のＬＵＴの入力変数及び中間変数を出力するための接続信号に切り換わる。これにより、接続回路２５の接続の切り換えが行われ、ＬＵＴ変数値a₀〜a_u-1の値が変更される。

（８）時刻t₇
時刻t₇において、クロックCLKは１から０に変化する。このクロックCLKの立ち下がりにおいて、論理関数メモリ２１は、アドレス端子A₀〜A_u+m-1より入力されているＬＵＴ変数値a₀〜a_u-1及びページ・カウント信号CNTの値（１）を、内部のアドレス・レジスタにラッチする。これに伴って、論理関数メモリ２１は、１ページに格納された２段目のＬＵＴを使用して、ＬＵＴ変数値a₀〜a_u-1を入力とする選択演算を行い、その結果を出力端子D₀〜D_u-1からＬＵＴ出力値d₀〜d_u-1として出力する。

また、このクロックCLKの立ち下がりにおいて、終端判定値メモリ３６は、ページ・カウント信号CNTを内部のアドレス・レジスタにラッチする。これにより、終端判定値メモリ３６が出力する終端判定閾値th₀〜th_u-1は、２段目のＬＵＴの出力に対して終端節点に達したか否かを判定するための閾値に変更される。

以上の、時刻t₆〜t₇の動作は、ＬＵＴカスケード論理回路による演算が終了するまで繰り返される。尚、図１５の例では、２段目のＬＵＴによる演算が終了した時点で、終端節点に達している。そこで、次のようなアウトプット・イネーブル信号(OE)nを有効とする動作を行い演算終了処理動作に移行する。

時刻t₇において、２段目のＬＵＴに対してＬＵＴ出力値d₀〜d_u-1が出力されると、この出力値は、終端節点判定器３７のデジタル・コンパレータ４０に入力される。デジタル・コンパレータ４０は、２段目のＬＵＴのＬＵＴ出力値d₀〜d_u-1と、２段目のＬＵＴの出力に対する終端判定閾値th₀〜th_u-1とを比較する。この場合、前者の値は後者の値以下であり、デジタル・コンパレータ４０の出力は０に切り換わる。このデジタル・コンパレータ４０の出力はＯＲ回路４３の一方の入力端子に入力される。ＯＲ回路４３のもう一方の入力端子には、Ｄフリップ・フロップ４２の出力(Q)nが入力されているが、この値は既に０にラッチされている。従って、ＯＲ回路４３の出力であるアウトプット・イネーブル信号(OE)nは０（有効）に切り換わる。アウトプット・イネーブル信号(OE)nは出力レジスタ２９のチップ・イネーブル端子(CE)nに入力されている。従って、アウトプット・イネーブル信号(OE)nが０（有効）となると、出力レジスタ２９は、それ以降はクロックCLKの立ち上がりにおいてデータの取り込みが可能な状態となる。

尚、このとき、ＬＵＴ出力値d₀〜d_u-1は、出力デコーダ２７に入力されている。出力デコーダ２７は、ＬＵＴ出力値d₀〜d_u-1を、２段目のＬＵＴ出力に対応する復号テーブルによって復号して、ｎビットの出力変数f₀〜f_n-1を出力する。そして、この出力変数f₀〜f_n-1が、出力レジスタ２９の入力端子Di₀〜Di_n-1に入力されている。

また、アウトプット・イネーブル信号(OE)nが０となると、ビジー生成回路３９のＡＮＤ回路４６の一方の入力値が０となる。従って、ＡＮＤ回路４６の出力値は０となる。一方、入力回路４４は、ＡＮＤ回路４６の出力値と、データ・ストローブ信号(DS)nの否定とのＯＲ演算を行う。この時点で、データ・ストローブ信号(DS)nは１である。従って、入力回路４４は、Ｄフリップ・フロップ４５のデータ入力端子Dに対して０を出力する。

（９）時刻t₈
時刻₈において、クロックCLKは０から１に変化する。このクロックCLKの立ち上がりにおいて、出力レジスタ２９は、出力変数f₀〜f_n-1をラッチする。これにより、出力レジスタ２９の出力端子Do₀〜Do_n-1から、出力値（Data OUT）として出力変数f₀〜f_n-1が出力され、演算が終了する。

また、ビジー生成回路３９のＤフリップ・フロップ４５は、クロックCLKの立ち上がりにおいて、データ入力端子Dの入力値０をラッチし、ＯＲ回路４７の一方の入力端子に０を出力する。ここで、ＯＲ回路４７のもう一方の入力端子には、終端節点判定器３７のＤフリップ・フロップ４２の出力(Q)nが入力されている。この時点で、Ｄフリップ・フロップ４２の出力(Q)nは０である。従って、ＯＲ回路４７が出力するビジー信号BUSYは０に切り換わる。ビジー信号BUSYが０であることが、外部データ入力信号(Data input)に対する演算が終了することを表す。従って、ビジー信号BUSYが０のときの出力レジスタ２９の出力値(Data out)が、外部データ入力信号(Data input)に対する目的関数の演算結果であることが分かる。

以上のようにして、ＬＵＴカスケードの一連の演算処理動作が行われる。

〔２〕リセット直後以外の演算処理動作
次に、リセット直後以外の演算処理動作について説明する。この場合、終端節点判定器３７のＴフリップ・フロップ４１の出力(Q)nは１にラッチされたまま変化せず、Ｄフリップ・フロップ４２の出力Q,(Q)nは、それぞれ、１，０にラッチされたまま変化しない。従って、動作は単純となる。

（１）時刻t₉,t₁₀
まず、時刻t₉において、外部データ入力信号（Data input）が切り換わり、演算に使用する入力変数が設定される。そして、時刻t₁₀において、データ・ストローブ信号DSが０（有効）とされる。

このデータ・ストローブ信号(DS)nの立ち下がりにおいて、入力変数レジスタ２２は、新たな外部データ入力信号（Data input）の値をラッチし、入力変数選択回路２３に出力する。

一方、データ・ストローブ信号(DS)nが０となると、ＡＮＤ回路３８の出力値も０となり、ページ・カウンタ３５はリセットされる。ページ・カウンタ３５がリセットされると、ページ・カウント信号CNTは０となる。これにより、入力選択メモリ２４、接続メモリ２６、出力デコーダ２７、及び終端判定値メモリ３６の出力ページ数が０ページに設定される。

入力選択メモリ２４は、０ページに格納されたm_iビットの選択信号INSELを出力する。これにより、入力変数選択回路２３が切り換えられる。入力変数選択回路２３は、入力変数レジスタ２２から入力される入力データを、選択信号INSELの値に従って選択し、入力変数信号x₀〜x_u-1として接続回路２５に出力する。この時点で、入力変数信号x₀〜x_u-1の値が確定する。

また、接続メモリ２６は、０ページに格納された接続回路２５の接続切換信号CNSETを出力する。これにより、接続回路２５が切り換えられる。接続回路２５は、接続切換信号CNSETの値に従って、入力端子Y₀〜Y_u-1より入力される入力変数信号x₀〜x_u-1の値（１段目のＬＵＴに入力するための入力変数値）を、出力端子W₀〜W_u-1からＬＵＴ変数値a₀〜a_u-1として出力する。この時点で、ＬＵＴ変数値a₀〜a_u-1の値も確定する。

また、終端判定値メモリ３６は、０ページに格納されたuビットの終端判定閾値th₀〜th_u-1を出力する。

一方、ビジー生成回路３９の入力回路４４は、データ・ストローブ信号(DS)nの否定とＡＮＤ回路４６の出力とのＯＲ論理を演算する。この時点では、データ・ストローブ信号(DS)nが０なので、Ｄフリップ・フロップ４５の入力端子Dに対して１を出力する。

（２）時刻t₁₁
時刻t₁₁において、クロックCLKは０から１に変化する。このクロックCLKの立ち上がりにおいて、ビジー生成回路３９のＤフリップ・フロップ４５は、入力端子Dの入力値１をラッチして、出力端子Qから出力する。このＤフリップ・フロップ４５の出力は、ＯＲ回路４７に入力される。そして、ＯＲ回路４７の出力であるビジー信号BUSYは１に反転する。

（３）時刻t₁₂
時刻t₁₂において、クロックCLKは１から０に変化する。このクロックCLKの立ち下がりにおいて、論理関数メモリ２１は、アドレス端子A₀〜A_u+m-1より入力されているＬＵＴ変数値a₀〜a_u-1及びページ・カウント信号CNTの値（１）を、内部のアドレス・レジスタにラッチする。これに伴って、論理関数メモリ２１は、１ページに格納された１段目のＬＵＴを使用して、ＬＵＴ変数値a₀〜a_u-1を入力とする選択演算を行い、その結果を出力端子D₀〜D_u-1からＬＵＴ出力値d₀〜d_u-1として出力する。

また、このクロックCLKの立ち下がりにおいて、終端判定値メモリ３６は、ページ・カウント信号CNTを内部のアドレス・レジスタにラッチする。これにより、終端判定値メモリ３６が出力する終端判定閾値th₀〜th_u-1は、１段目のＬＵＴの出力に対して終端節点に達したか否かを判定するための閾値に変更される。

ＬＵＴ出力値d₀〜d_u-1と終端判定閾値th₀〜th_u-1は、終端節点判定器３７のデジタル・コンパレータ４０に入力され、終端節点に達したか否かが判定される。そして、ＬＵＴ出力値d₀〜d_u-1が終端判定閾値th₀〜th_u-1よりも大きい場合には１が、それ以外の場合には０が、アウトプット・イネーブル信号(OE)nとして出力される。

以下、２段目以降のＬＵＴの演算処理動作は、リセット直後の演算処理動作の場合と同様である。尚、図１５においては、１段目のＬＵＴの演算が終了した時点で、既に終端節点に達し、アウトプット・イネーブル信号(OE)nとして０が出力されている。従って、ページ・カウンタ３５はリセット状態が維持され、ページ・カウント信号CNTは０に維持される。そして、時刻t₁₃において、データ・ストローブ信号(DS)nが１に反転した後に、最初にクロックCLKが立ち上がった時点（時刻t₁₄）で、出力レジスタ２９が出力変数f₀〜f_n-1をラッチするとともに、ビジー生成回路３９のＤフリップ・フロップ４５が０をラッチしてビジー信号BUSYが０となる。これにより、演算処理が終了する。

以上のように、終端節点判定器３７において、ＬＵＴカスケードの中間変数から終端節点に達しているか否かを判定して、終端節点に達した場合には、後段のＬＵＴによる演算を打ち切って、出力レジスタ２９から出力変数を出力させることで、ＬＵＴカスケードによる演算速度を向上させることが可能となる。

本発明の実施例１に係るＬＵＴ符号化装置の構成を表すブロック図である。 本発明の実施例１に係るＬＵＴ符号化方法を表すフローチャートである。 ＢＤＤの例を表す図である。 図３のＢＤＤを既約化したＲＯＢＤＤを表す図である。 ＲＯＢＤＤの分割を説明する図である。 図５のＲＯＢＤＤから生成されるＬＵＴカスケードを表す図である。 本発明の実施例２に係るＬＵＴ符号化装置の構成を表すブロック図である。 本発明の実施例２に係るＬＵＴ符号化方法を表すフローチャートである。 ４ビット比較器のＭＴＢＤＤを表す図である。 図９のＭＴＢＤＤから生成されるＬＵＴカスケードを表す図である。 本発明の実施例３に係るＬＵＴカスケード論理回路の構成を表すブロック図である。 図１１の入力変数選択回路の構成の一例を示す図である。 図１１の接続回路の構成の一例を示す図である。 図１１の演算制御部の構成を表すブロック図である。 図１１及び図１４の各端子の出力値を表すタイムチャートである。 図１４の各出力値を表すタイムチャートである。 図１５の演算において使用したＬＵＴである。 論理関数の二分決定グラフ（ＢＤＤ）を表す図である。 ＬＵＴカスケード論理回路の構成を表す図である。

符号の説明

１ 論理仕様記憶手段
２ ＲＯＢＤＤ生成手段
３ ＲＯＢＤＤ記憶手段
４，１１ ＢＤＤ分割手段
５，１２ 符号化手段
６ ＬＵＴ記憶手段
９ ＭＴＢＤＤ生成手段
１０ ＭＴＢＤＤ記憶手段
２１ 論理関数メモリ
２２ 入力変数レジスタ
２３ 入力変数選択回路
２３−０〜２３−３ バレルシフタ
２４ 入力選択メモリ
２５ 接続回路
２５ａ 切換回路
２６ 接続メモリ
２７ 出力デコーダ
２９ 出力レジスタ
３０ 演算制御部
３５ ページ・カウンタ
３６ 終端判定値メモリ
３７ 終端節点判定器
３８ ＡＮＤ回路
３９ ビジー生成回路
４０ デジタル・コンパレータ
４１ Ｔフリップ・フロップ
４２ Ｄフリップ・フロップ
４３ ＯＲ回路
４４ 入力回路
４５ Ｄフリップ・フロップ
４６ ＡＮＤ回路
４７ ＯＲ回路

Claims (6)

1. 演算を行う対象となる目的論理関数を表す二分決定グラフを、適所に設定される切断線で分割し、その分割で得られる各部分グラフを真理値表で表したものであるＬＵＴが、直列に順序づけて接続されており、最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部は、当該ＬＵＴの前段のＬＵＴの出力が入力される構成からなるＬＵＴカスケードにおいて、コンピュータにより前記各ＬＵＴの出力値に符号の割り当てを行うＬＵＴ符号化方法であって、
   前記目的論理関数の論理仕様が記憶された論理仕様記憶手段から、論理仕様を読み出し、該論理仕様に基づいて二分決定グラフ（以下「ＢＤＤ」という。）を生成し、該ＢＤＤをＢＤＤ記憶手段に格納する第１ステップと、
   前記ＢＤＤ記憶手段に記憶された前記ＢＤＤを分割する切断線をｓ−１本（ｓ≧２）設定し、該ＢＤＤをｓ個の部分グラフに分割する第２ステップと、
   ｓ個の前記各部分グラフのそれぞれについて、該部分グラフの各入力値に対する出力に符号を割り当てることで各入力値とそれに対する出力値の関係を定めてＬＵＴを生成し、該ＬＵＴをＬＵＴ記憶手段に格納する第３ステップと、
   を備え、
   前記第３ステップにおいては、０番目からｓ−１番目の前記各部分グラフについて、
   ａ．ｉ番目（ｉ＝０，…，ｓ−１）の前記部分グラフの出力のうち、終端節点に向かう枝に対応する出力に対しては、その終端節点の値に対応して決められた特定の符号をｉ番目の前記ＬＵＴの出力値として割り当て、
   ｂ．非終端節点に向かう枝に対応する出力に対しては、前記特定の符号以外の符号をｉ番目の前記ＬＵＴの出力値として割り当てる
   という処理を順次実行することで、該部分グラフの各入力値に対する出力に符号の割り当てを行うことを特徴とするＬＵＴ符号化方法。
2. 前記ＬＵＴカスケードは、最終段のＬＵＴが１ビットの出力変数を出力するＬＵＴカスケードであって、
   前記第３ステップにおいては、０番目からｓ−１番目の前記各部分グラフについて、
   ａ’．ｉ番目（ｉ＝０，…，ｓ−２）の前記部分グラフの出力のうち、終端節点に向かう枝に対応する出力に対しては、
   その終端節点の値が０の場合には前記ＬＵＴの出力値として全ビットが０又は全ビットが１の符号を前記ＬＵＴの出力値として割り当て、
   その終端節点の値が１の場合には前記ＬＵＴの出力値として全ビットが１又は全ビットが０の符号をｉ番目の前記ＬＵＴの出力値として割り当て、
   ｂ’．非終端節点に向かう枝に対応する出力に対しては、前記全ビットが０及び全ビットが１以外の符号をｉ番目の前記ＬＵＴの出力値として割り当てる
   という処理を順次実行することで、該部分グラフの各入力値に対する出力に符号の割り当てを行うこと
   を特徴とする請求項１記載のＬＵＴ符号化方法。
3. 前記ＬＵＴカスケードは、最終段のＬＵＴが２ビット以上の出力変数を出力するＬＵＴカスケードであって、
   前記第３ステップにおいては、０番目からｓ−１番目の前記各部分グラフについて、
   ａ”．ｉ番目（ｉ＝０，…，ｓ−２）の前記部分グラフの出力のうち、終端節点に向かう枝に対応する出力に対しては、ｉ番目のＬＵＴに対して決められている所定の閾値以下となるような前記特定の符号を、該ｉ番目のＬＵＴの出力値として割り当て、
   ｂ”．非終端節点に向かう枝に対応する出力に対しては、前記所定の閾値より大きい符号をｉ番目の前記ＬＵＴの出力値として割り当てる
   という処理、または、
   ａ”．ｉ番目（ｉ＝０，…，ｓ−２）の前記部分グラフの出力のうち、終端節点に向かう枝に対応する出力に対しては、ｉ番目のＬＵＴに対して決められている所定の閾値以上となるような前記特定の符号を、該ｉ番目のＬＵＴの出力値として割り当て、
   ｂ”．非終端節点に向かう枝に対応する出力に対しては、前記所定の閾値より小さい符号をｉ番目の前記ＬＵＴの出力値として割り当てる
   という処理の何れか一方を順次実行することで、該部分グラフの各入力値に対する出力に符号の割り当てを行うことを特徴とする請求項１記載のＬＵＴ符号化方法。
4. 演算を行う対象となる目的論理関数を表す二分決定グラフを、適所に設定されるｓ−１本（ｓ≧２）の切断線で分割し、その分割で得られるｓ個の各部分グラフを真理値表により表したものであるｓ個のＬＵＴが格納された論理関数メモリと、
   最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部を、当該ＬＵＴの前段のＬＵＴの出力に接続する接続回路と、
   を備えたＬＵＴカスケード論理回路であって、
   前記論理関数メモリに格納されたｓ個の前記ＬＵＴのうち、最終段以外の少なくとも一つの前記ＬＵＴは、前記二分決定グラフの終端節点に対応する出力値を有しており、かつ終端節点に対応する前記ＬＵＴの出力値には、その終端節点の値に対応して決められた特定の符号が割り当てられており、
   最終段以外の前記ＬＵＴの出力値が前記特定の符号であった場合、当該特定の符号に対応する節点値を出力する演算制御手段を備えていることを特徴とするＬＵＴカスケード論理回路。
5. 前記論理関数メモリに格納された最終段のＬＵＴは、１ビットの出力変数を出力するＬＵＴであって、
   前記演算制御手段は、
   前記ＬＵＴの出力値の全ビットが０であることを検出する終端判定器と、
   前記終端判定器が、最終段以外の前記ＬＵＴの出力値において、全ビットが０であることを検出したときに、その出力値に応じて節点値を出力する出力回路と、を備え、
   又は、
   前記ＬＵＴの出力値の全ビットが１であることを検出する終端判定器と、
   前記終端判定器が、最終段以外の前記ＬＵＴの出力値において、全ビットが１であることを検出したときに、その出力値に応じて節点値を出力する出力回路と、
   を備えていることを特徴とする請求項４記載のＬＵＴカスケード論理回路。
6. 前記論理関数メモリに格納された最終段のＬＵＴは、２ビット以上の出力変数を出力するＬＵＴであって、
   前記演算制御手段は、
   最終段以外の各段の前記ＬＵＴに対する終端判定値が格納された終端判定値メモリと、
   最終段以外の各段の前記ＬＵＴの出力値が、その段に対する前記終端判定値以下又は以上であることを検出する終端判定器と、
   前記終端判定器が、最終段以外の前記ＬＵＴの出力値が、その段に対する前記終端判定値以下であることを検出したときに、その出力値は前記特定の符号であると判定し、その出力値に応じて節点値を出力する、
   又は、前記終端判定器が、最終段以外の前記ＬＵＴの出力値が、その段に対する前記終端判定値以上であることを検出したときに、その出力値は前記特定の符号であると判定し、その出力値に応じて節点値を出力する
   出力回路と、
   を備えていることを特徴とする請求項４記載のＬＵＴカスケード論理回路。

Images