(57)【要約】【課題】回路規模を大規模化することなく従来よりも高速な論理演算を可能とするＬＵＴカスケード論理回路を提供する。【解決手段】演算を行う対象となる目的論理関数を表す二分決定グラフを適所で分割して得られる各部分グラフを真理値表で表したものであるＬＵＴが、直列に順序づけて接続されており、最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部は、当該ＬＵＴの前段のＬＵＴの出力が入力される構成からなるＬＵＴカスケードにおいて、各ＬＵＴの出力値に符号の割り当てを行うＬＵＴ符号化方法であって、前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その終端節点の値に対応して決められた特定の符号を割り当てる。【選択図】        図２
2005165502.tif 000002
【特許請求の範囲】
【請求項１】
演算を行う対象となる目的論理関数を表す二分決定グラフを適所で分割して得られる各部分グラフを真理値表で表したものであるＬＵＴが、直列に順序づけて接続されており、最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部は、当該ＬＵＴの前段のＬＵＴの出力が入力される構成からなるＬＵＴカスケードにおいて、各ＬＵＴの出力値に符号の割り当てを行うＬＵＴ符号化方法であって、
前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その終端節点の値に対応して決められた特定の符号を割り当てることを特徴とするＬＵＴ符号化方法。
【請求項２】
前記ＬＵＴカスケードは、最終段のＬＵＴが１ビットの出力変数を出力するＬＵＴカスケードであって、
前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その終端節点の値が０の場合には前記ＬＵＴの出力値として全ビットが０（又は全ビットが１）の符号を割り当て、その終端節点の値が１の場合には前記ＬＵＴの出力値として全ビットが１（又は全ビットが０）の符号を割り当てることを特徴とする請求項１記載のＬＵＴ符号化方法。
【請求項３】
前記ＬＵＴカスケードは、最終段のＬＵＴが２ビット以上の出力変数を出力するＬＵＴカスケードであって、
前記二分決定グラフの終端節点に対応する前記ＬＵＴカスケードのｉ段目のＬＵＴの出力値に対しては、当該ｉ段目のＬＵＴに対して決められている所定の閾値以下又は以上となるように符号を割り当てることを特徴とする請求項１記載のＬＵＴ符号化方法。
【請求項４】
演算を行う対象となる目的論理関数を表す二分決定グラフを適所で分割して得られる各部分グラフを真理値表で表したものであるＬＵＴが、直列に順序づけて接続されており、最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部は、当該ＬＵＴの前段のＬＵＴの出力が入力される構成からなるＬＵＴカスケードにおいて、各ＬＵＴの出力値に符号の割り当てを行うＬＵＴ符号化装置であって、
前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その節点の値に対応して決められた特定の符号を割り当てる符号化手段を備えていることを特徴とするＬＵＴ符号化装置。
【請求項５】
前記ＬＵＴカスケードは、最終段のＬＵＴが１ビットの出力変数を出力するＬＵＴカスケードであって、
前記符号化手段は、前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値に対しては、その終端節点の値が０の場合には前記ＬＵＴの出力値として全ビットが０（又は全ビットが１）の符号を割り当て、その終端節点の値が１の場合には前記ＬＵＴの出力値として全ビットが１（又は全ビットが０）の符号を割り当てることを特徴とする請求項４記載のＬＵＴ符号化装置。
【請求項６】
前記ＬＵＴカスケードは、最終段のＬＵＴが２ビット以上の出力変数を出力するＬＵＴカスケードであって、
前記符号化手段は、前記二分決定グラフの終端節点に対応する前記ＬＵＴカスケードのｉ段目のＬＵＴの出力値に対しては、当該ｉ段目のＬＵＴに対して決められている所定の閾値以下又は以上となるように符号を割り当てることを特徴とする請求項４記載のＬＵＴ符号化装置。
【請求項７】
演算を行う対象となる目的論理関数を表す二分決定グラフを適所で分割して得られる各部分グラフを真理値表により表したものであるＬＵＴが格納された論理関数メモリと、
最前段のＬＵＴ以外のＬＵＴの入力の一部又は全部を、当該ＬＵＴの前段のＬＵＴの出力に接続する接続回路と、
を備えたＬＵＴカスケード論理回路であって、
前記二分決定グラフの終端節点に対応する前記ＬＵＴの出力値は、その終端節点の値に対応して決められた特定の符号を割り当てられており
最終段以外の前記ＬＵＴの出力値が前記特定の符号であった場合、当該特定の符号に対応する節点値を出力する演算制御手段を備えていることを特徴とするＬＵＴカスケード論理回路。
【請求項８】
前記論理関数メモリに格納された最終段のＬＵＴは、１ビットの出力変数を出力するＬＵＴであって、
演算制御手段は、
前記ＬＵＴの出力値の全ビットが０（又は全ビットが１）であることを検出する終端判定器と、
前記終端判定器が、最終段以外の前記ＬＵＴの出力値において、全ビットが０（又は全ビットが１）であることを検出したときに、その出力値に応じて節点値を出力する出力回路と、
を備えていることを特徴とする請求項７記載のＬＵＴカスケード論理回路。
【請求項９】
前記論理関数メモリに格納された最終段のＬＵＴは、２ビット以上の出力変数を出力するＬＵＴであって、
演算制御手段は、
最終段以外の各段の前記ＬＵＴに対して終端判定値が格納された終端判定値メモリと、
各段の前記ＬＵＴの出力値が、その段に対する前記終端判定値以下又は以上であることを検出する終端判定器と、
前記終端判定器が、最終段以外の前記ＬＵＴの出力値が、その段に対する前記終端判定値以下又は以上であることを検出したときに、その出力値に応じて節点値を出力する出力回路と、
を備えていることを特徴とする請求項７記載のＬＵＴカスケード論理回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＵＴ（Look-Up Table）カスケード論理回路において、目的論理関数の演算速度を高速化することを可能とするＬＵＴ符号化技術に関するものである。
【背景技術】
【０００２】
従来、ソフトウェア的に自由に論理関数の組み換えが可能で、かつ、論理関数の演算処理をＭＰＵに比べて高速に行うことが可能な技術として、ルックアップテーブル・カスケード論理回路（以下、「ＬＵＴカスケード論理回路」という。）が知られている（例えば、非特許文献１，２参照）。
【０００３】
図１８は論理関数の二分決定グラフ（ＢＤＤ : Binary decision diagrams）を表す図、図１９はＬＵＴカスケード論理回路の構成を表す図である。ＬＵＴカスケード論理回路では、演算を行う論理関数（以下、「目的論理関数」という。）をs個の部分グラフ（sub graph）に分割する。そして、各部分グラフのそれぞれを真理値表（truth table）で表しＬＵＴを作成する。そして、図１９のようにＬＵＴをカスケード接続する。各ＬＵＴは、論理関数メモリに格納され、論理関数メモリのアクセスにより各部分グラフの演算は行われる。
【０００４】
図１８，図１９において、X1,…,Xsは入力変数組を表している。μ1,…,μs-1は、ＢＤＤの切断線を横切る有向枝（directed edge）の数を表す。但し、同一の節点（node）を終点（end node）とする有向枝は１本として数える。u1,…,us-1は、前段のＬＵＴから後段のＬＵＴに入力される中間変数の数を表す。一般に、中間変数の数u1,…,us-1は、（数１）により表される。
【０００５】
【数１】
2005165502.tif 000003
【０００６】
従来のＬＵＴカスケード論理回路では、最前段のＬＵＴから順にメモリアクセスによる参照演算を行ってゆき、最終段のＬＵＴによる演算の結果として得られる出力値ｆを、目的論理関数による演算値として得る。
【０００７】
このように、目的論理関数の演算を複数段のＬＵＴのメモリアクセスによる参照演算で行うことによって、通常のＭＰＵ（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。以下、「ＲＯＢＤＤ」という。）を生成してＲＯＢＤＤ記憶手段３に格納する。ＢＤＤ分割手段４は、ＲＯＢＤＤ記憶手段３に格納されたＲＯＢＤＤを、所定の大きさの部分グラフに分割する。符号化手段５は、ＢＤＤ分割手段４が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。
【００３４】
以上のように構成された本実施例に係るＬＵＴ符号化装置について、以下その動作を説明する。
【００３５】
図２は本発明の実施例１に係るＬＵＴ符号化方法を表すフローチャートである。まず、ＲＯＢＤＤ生成手段２は、論理仕様記憶手段１に格納された論理仕様を読み出して、ＢＤＤを生成しながらこれを既約化してＲＯＢＤＤを生成し、これをＲＯＢＤＤ記憶手段３に格納する（Ｓ１）。ここで、ＢＤＤの「既約化」とは、展開する変数の順序を固定して、冗長な節点の削除と同型な部分グラフの共有を可能な限り行うことをいう。
【００３６】
〔例１．１〕
例えば、目的論理関数ｆが（数２）のような関数であったとする。
【００３７】
【数２】
2005165502.tif 000004
【００３８】
（数２）を表す２分決定木（BDT : Binary Decision Tree）は図３のようになる。図３において「○」が非終端節点（non-terminal node）を表し、「□」が終端節点を表す。また、各非終端節点を始節点とする有向枝のうち、実線で表されたものは、非終端節点における入力が「１」に対応する有向枝、点線で表されたものは、非終端節点における入力が「０」に対応する有向枝を表している。
【００３９】
図３のＢＤＴは、目的論理関数ｆを展開する変数の順序を固定し、冗長な節点の削除と同型な部分グラフの共有を可能な限り行うことにより、図４に示したＲＯＢＤＤに変形することができる。ＲＯＢＤＤ生成手段２は、目的論理関数の論理仕様から、図３に示したＢＤＴを生成しながら、同時に図３のＢＤＴを既約化し、図４のようなＲＯＢＤＤを生成する。そして、このＲＯＢＤＤは、ＲＯＢＤＤ記憶手段３に（表１）のようなＲＯＢＤＤテーブルとして格納される。
【００４０】
【表１】
2005165502.tif 000005
【００４１】
（表１）において、「アドレス」は、ＲＯＢＤＤの節点のデータが格納されたメモリ内のアドレスを表す。「index」は、各節点の節点ラベル（vertex Label）に対応した符号を表す。（表１）では、節点ラベル「Ａ」に対して「００１」、節点ラベル「Ｂ」に対して「０１０」、節点ラベル「Ｃ」に対して「０１１」の符号が付されている。また、終端節点に対しては、符号「０００」が付されている。「０枝」と「１枝」の欄には、各節点を始節点（initial vertex）とする入力「０」に対応する有向枝の終点のアドレス又は入力「０」に対応する有向枝の終点のアドレスが格納されている。但し、終端節点に対しては、それを始節点とする有向枝は存在しないので、当該終端節点の値に対応する適当な値（（表１）では、節点値１の終端節点に対しては「１１１１」、節点値０の終端節点に対しては「００００」）が割り当てられる。
（例終わり）
【００４２】
次に、ＢＤＤ分割手段４は、ＲＯＢＤＤ記憶手段３に格納されたＲＯＢＤＤを、所定の大きさのｓ個の部分グラフに分割する（Ｓ２）。ここで、「所定の大きさの部分グラフ」とは、各部分グラフを符号化してＬＵＴを作成した場合に、作成されるＬＵＴが、ＬＵＴを格納するメモリの入力数以下の入力数となる程度の大きさの部分グラフをいう。
【００４３】
〔例１．２〕
図５（ａ）のようなＲＯＢＤＤを持つ論理関数を考える。ＬＵＴを格納するメモリのアドレスの入力数が３であるとした場合、ＢＤＤ分割手段４は、図５（ｂ）の一点鎖線で示した位置でＲＯＢＤＤを分割する。これにより、図５（ａ）のＲＯＢＤＤを４個の３入力ＬＵＴにより実現することができる。図５（ｂ）において「○」が非終端節点を表し、「□」が終端節点を表す。また、各非終端節点を始節点とする有向枝のうち、実線で表されたものは非終端節点における入力が「１」に対応する有向枝、点線で表されたものは非終端節点における入力が「０」に対応する有向枝を表している。
（例終わり）
【００４４】
次に、符号化手段５は、ＢＤＤ分割手段４が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。この符号化処理は、以下のようにして行われる。
【００４５】
まず、符号化手段５は、作成するＬＵＴの段数を表す内部変数ｉを０として（Ｓ３）、ＢＤＤ分割手段４が生成したｉ番目の部分グラフの出力数ｕ（ｉ）を計算する（Ｓ４）。ここで、部分グラフの出力数ｕ（ｉ）は（数１）により計算することができる。例えば、図５（ｂ）に示したＲＯＢＤＤを分割して得られる各部分グラフの出力数は２となる。
【００４６】
次に、符号化手段５は、ｉ番目の部分グラフの出力のうち、終端節点に対しては、その終端節点の値に対応して決められた特定の符号を割り当てる。本実施例においては、符号化手段５は、節点値０の終端節点に対しては「０…０」、節点値１の終端節点に対しては「１…１」の符号を割り当てる（Ｓ５）。また、符号化手段５は、ｉ番目の部分グラフの出力の非終端節点に対して、上記終端節点に割り当てた符号以外の符号を割り当てる（Ｓ６）。そして、符号化手段５は、以上の符号割り当てにより、ｉ番目のＬＵＴを生成し、これをＬＵＴ記憶手段６に格納する（Ｓ７）。
【００４７】
以上のステップＳ５〜Ｓ８までの動作を、ｉを１ずつ繰り上げながら、ｉがｓ−１となるまで繰り返す（Ｓ８）。ｉがｓ−１となるまでステップＳ４〜Ｓ７の動作を行ってｓ個のＬＵＴを生成した時点で、ＬＵＴ符号化装置は動作を終了する。
【００４８】
〔例１．３〕
図５（ｂ）に示したようなＲＯＢＤＤの部分グラフを符号化手段５により符号化することによって、図６に示したようなＬＵＴカスケードが生成され、ＬＵＴ記憶手段６に格納される。図６において、各ＬＵＴの出力値（y2i+1，y2i）には、値が０の終端節点に対して「００」又は「０」が、値が１の終端節点に対して「１１」又は「１」が割り当てられる。図５（ｂ）のＲＯＢＤＤから符号化により作成されたＬＵＴの例を（表２）に示す。尚、（表２）において、「x」はドント・ケアを表す。
【００４９】
【表２】
2005165502.tif 000006
【００５０】
このような符号化により生成された各ＬＵＴにより、図６のようなＬＵＴカスケードを構成した場合、各段のＬＵＴの出力値が総て０又は総て１である場合には、終端節点であることを識別することが可能となる。従って、各段のＬＵＴの出力値を監視し、総て０の出力を検出した時点でｆ＝０を出力して計算を終了し、又は、総て１の出力を検出した時点でｆ＝１を出力して計算を終了する。これにより、従来は４回のメモリアクセスを必要としたＬＵＴカスケード論理回路による演算を、平均２．３７５回のメモリアクセスにより行うことが可能となる。
（例終わり）
【実施例２】
【００５１】
本実施例においては、出力変数が複数ビットである多端子二分決定グラフ（Multi-Terminal BDD．以下、「ＭＴＢＤＤ」という。）に対して、ＬＵＴカスケード論理回路の演算速度を高速化するための符号化方法について説明する。
【００５２】
図７は本発明の実施例２に係るＬＵＴ符号化装置の構成を表すブロック図である。図７において、論理仕様記憶手段１及びＬＵＴ記憶手段６は、図１と同様のものであるため、同符号を付して説明は省略する。本実施例に係るＬＵＴ符号化装置は、更に、ＭＴＢＤＤ生成手段９、ＭＴＢＤＤ記憶手段１０、ＢＤＤ分割手段１１、及び符号化手段１２を備えている。
【００５３】
ＭＴＢＤＤ生成手段９は、論理仕様記憶手段１に記憶された目的論理関数を表す論理仕様からＭＴＢＤＤを生成してＭＴＢＤＤ記憶手段１０に格納する。ＢＤＤ分割手段１１は、ＭＴＢＤＤ記憶手段１０に格納されたＭＴＢＤＤを、所定の大きさの部分グラフに分割する。符号化手段１２は、ＢＤＤ分割手段１１が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。
【００５４】
以上のように構成された本実施例に係るＬＵＴ符号化装置について、以下その動作を説明する。
【００５５】
図８は本発明の実施例２に係るＬＵＴ符号化方法を表すフローチャートである。まず、ＭＴＢＤＤ生成手段９は、論理仕様記憶手段１に格納された論理仕様を読み出してＭＴＢＤＤを生成し、これをＭＴＢＤＤ記憶手段１０に格納する（Ｓ１１）。続いて、ＢＤＤ分割手段１１は、ＭＴＢＤＤ記憶手段１０に格納されたＭＴＢＤＤを、所定の大きさのｓ個の部分グラフに分割する（Ｓ１２）。
【００５６】
〔例２．１〕
例えば、目的論理関数が、入力変数A＝（a3 a2 a1 a0），B＝（b3 b2 b1 b0）の大小を比較する４ビット比較器であるとする。４ビット比較器は、例えば、（数３）により表される。
【００５７】
【数３】
2005165502.tif 000007
【００５８】
ＭＴＢＤＤ生成手段９は、（数３）で表される論理仕様から図９に示すようなＭＴＢＤＤを生成し、ＭＴＢＤＤ記憶手段１０に格納する。図９において、ＭＴＢＤＤは２ビットの出力変数Ｆを出力する。Ａ＞Ｂの場合にはＦ＝（００）、Ａ＝Ｂの場合にはＦ＝（１１）、Ａ＜Ｂの場合にはＦ＝（０１）が出力される。入力変数Ａ，Ｂの比較は、上位ビットから比較することにより行われる。すなわち、まず、a3，b3を比較してa3＞b3ならばA＞B、a3＜b3ならばA＜Bと決定する。a3＝b3のときは、次の下位ビットa2，b2を比較する。a2＞b2ならばA＞B、a2＜b2ならばA＜Bと決定する。a2＝b2のときは、次の下位ビットa1，b1を比較する。以下同様に比較演算を行い、入力変数AとBの比較が行われる。
【００５９】
そして、ＢＤＤ分割手段１１は、このＭＴＢＤＤを、例えば、図９の一点鎖線の箇所において分割し、３個の部分グラフを生成する。図９では、４入力のＬＵＴにより構成されるようにＭＴＢＤＤの分割を行ったものである。一般に、ＬＵＴの入力変数の数が指定された数以下となるように、ＭＴＢＤＤの分割が行われる。
（例終わり）
【００６０】
次に、符号化手段１２は、ＢＤＤ分割手段１１が生成する部分グラフを符号化してＬＵＴを生成し、ＬＵＴ記憶手段６に格納する。この符号化処理は、以下のようにして行われる。
【００６１】
まず、符号化手段１２は、内部変数ｉを０として（Ｓ１３）、ＢＤＤ分割手段１１が生成するｉ番目の部分グラフの出力数ｕ（ｉ）を計算する（Ｓ１４）。ここで、部分グラフの出力数ｕ（ｉ）は（数１）により計算される。例えば、図９に示したＭＴＢＤＤを分割して得られる各部分グラフの出力数は２となる。
【００６２】
次に、符号化手段１２は、ｉ番目の部分グラフの出力のうち、終端節点に対しては、その終端節点の値に対応して決められた特定の符号を割り当てる。本実施例においては、符号化手段１２は、ｉ番目の部分グラフの出力（yu(i)，yu(i)-1，…，y0）のうち終端節点に対しては、２進数（yu(i)，yu(i)-1，…，y0）2が所定の閾値ti以下となるように符号の割り当てを行う（Ｓ１５）。これにより、ｉ番目の部分グラフの出力から得られる２進数（yu(i)，yu(i)-1，…，y0）2と閾値tiとを比較することにより、（yu(i)，yu(i)-1，…，y0）2≦tiであれば終端節点であることを判別することが可能となる。
【００６３】
尚、終端節点に対する符号の割り当て方法はこの方法に限られるものではなく、終端節点であることが識別できる符号であれば、どのような符号の割り当て方を用いてもよい。
【００６４】
また、符号化手段１２は、ｉ番目の部分グラフの出力の非終端節点に対して、上記終端節点に割り当てた符号以外の符号を割り当てる（Ｓ１６）。そして、符号化手段１２は、以上の符号割り当てにより、ｉ番目のＬＵＴを生成し、これをＬＵＴ記憶手段６に格納する（Ｓ１７）。
【００６５】
以上のステップＳ１４〜Ｓ１７までの動作を、ｉを１ずつ繰り上げながら、ｉがｓ−１となるまで繰り返す（Ｓ１８）。ｉがｓ−１となるまでステップＳ１４〜Ｓ１７の動作を行ってｓ個のＬＵＴを生成した時点で、ＬＵＴ符号化装置は動作を終了する。
【００６６】
〔例２．２〕
図９に示したようなＭＴＢＤＤの部分グラフを符号化手段１２により符号化することによって、図１０（ａ）に示したようなＬＵＴカスケードが生成され、ＬＵＴ記憶手段６に格納される。図１０（ａ）において、ＬＵＴ０，ＬＵＴ１の出力値には、Ａ＞Ｂの終端節点に対して符号「００」が、Ａ＜Ｂの終端節点に対して符号「０１」が割り当てられる。終端節点以外の節点に対しては、符号「１１」又は符号「１０」の何れかを割り当てることができる。また、最終段のＬＵＴ２の出力値には、Ａ＞Ｂの終端節点に対して符号「００」が、Ａ＜Ｂの終端節点に対して符号「０１」が、Ａ＝Ｂの終端節点に対して符号「１１」又は符号「１０」が割り当てられる。
【００６７】
図９のＭＴＢＤＤから符号化により作成されたＬＵＴの例を（表３）に示す。（表３）では、ＬＵＴ０，ＬＵＴ１の出力値のうち終端節点以外の節点に対しては符号「１１」を割り当てて符号化を行っている。また、ＬＵＴ２の出力は総て終端節点なので、符号「００」、「０１」、「１１」を割り当てて符号化を行っている。尚、「ｘ」は、ドント・ケアを表す。
【００６８】
【表３】
2005165502.tif 000008
【００６９】
このような符号化を行うことによって、ＬＵＴ０又はＬＵＴ１による演算が終了した時点で、ＬＵＴの出力値（ｙ2i，ｙ2i+1）を２進数で表した値（ｙ2iｙ2i+1）2が（０１）２以下であれば、終端節点に達したものと判定することが可能である。従って、ＬＵＴ０又はＬＵＴ１の出力値から終端節点に達したことが検出されると、出力値（ｙ2i，ｙ2i+1）を出力F＝（F0，F1）として出力し、演算を終了することが可能となる。これにより、従来は３回のメモリアクセスを必要としたＬＵＴカスケード論理回路による演算を、平均１．３７５回のメモリアクセスにより行うことが可能となる。
（例終わり）
【実施例３】
【００７０】
本実施例においては、実施例１又は実施例２で説明したＬＵＴ符号化方法によって符号化されたＬＵＴカスケードを用いて、目的論理関数の演算を行うＬＵＴカスケード論理回路について説明する。
【００７１】
図１１は本発明の実施例３に係るＬＵＴカスケード論理回路の構成を表すブロック図である。本実施例に係るＬＵＴカスケード論理回路は、論理関数メモリ２１、入力変数レジスタ２２、入力変数選択回路２３、入力選択メモリ２４、接続回路２５、接続メモリ２６、出力デコーダ２７、出力レジスタ２９、及び演算制御部３０を備えている。
【００７２】
論理関数メモリ２１は、目的論理関数に基づいて、上記実施例１，２において説明した符号化方法によって生成された複数のＬＵＴが記憶されている。この論理関数メモリ２１には、通常のＳＲＡＭ（Static Random Access Memory）等が使用される。
【００７３】
論理関数メモリ２１は、メモリのｉページ目（ｉ＝０，１，…）にｉ段目のＬＵＴ（以下、「ＬＵＴｉ」と表す。）が格納されている。従って、論理関数メモリ２１のｉページを読み出すことにより、ＬＵＴｉにアクセスすることが可能となる。
【００７４】
〔例３．１〕
例えば、目的論理関数が、図１０（ａ）に示したような３つのＬＵＴ（ＬＵＴ０，ＬＵＴ１，ＬＵＴ２）からなるＬＵＴカスケードにより表される場合、図１０（ｂ）に示したように、ＬＵＴ０は論理関数メモリ２１の０ページ目に、ＬＵＴ１は論理関数メモリ２１の１ページ目に、ＬＵＴ２は論理関数メモリ２１の２ページ目に、それぞれ格納される。これにより、例えば、ＬＵＴ１を読み出す場合には、論理関数メモリ２１の１ページにアクセスすればよいことになる。
（例終わり）
【００７５】
論理関数メモリ２１は、u+mビットのアドレス入力端子A0〜Au+m-1、uビットのデータ出力端子D0〜Du-1、及び、アドレス・ストローブ（address strobe）端子(AS)nを備えている。尚、「(  )n」の記号は負論理であることを表す。アドレス・ストローブ端子(AS)nには、外部から入力されるクロックCLKが入力される。論理関数メモリ２１は、アドレス・ストローブ端子(AS)nから入力されるクロックの立ち下がりにおいて、アドレス入力端子A0〜Au+m-1に入力されているアドレス値を、内部のアドレス・レジスタにラッチする。そして、アドレス・レジスタにラッチされたアドレス値が示すアドレスに格納されたデータの値を、データ出力端子D0〜Du-1から出力する。
【００７６】
入力変数レジスタ２２は、ＬＵＴカスケードの各段のＬＵＴに対して入力する入力変数を一時的に記憶するレジスタである。入力変数レジスタ２２には、外部からのデータ入力（Data input）の他に、制御信号として、データ・ストローブ信号(DS)nが入力される。入力変数レジスタ２２は、データ・ストローブ信号(DS)nの立ち下がりにおいて、外部からのデータ入力（Data input）をラッチする。
【００７７】
入力変数選択回路２３は、入力変数レジスタ２２が出力する入力変数から、ＬＵＴカスケードの各段で使用する入力変数を選択する回路である。入力変数選択回路２３としては、クロスバ・スイッチ、マルチプレクサ、シフタ等が使用される。また、入力選択メモリ２４には、ＬＵＴカスケードの各ＬＵＴに対応して、当該ＬＵＴにおいて使用する入力変数の選択に関する情報が格納されている。入力変数選択回路２３のデータ入力端子は、入力変数レジスタ２２の出力端子に接続されている。入力変数選択回路２３の選択制御入力端子は、ｍiビットの入力選択メモリ２４の出力端子に接続されている。
【００７８】
接続回路２５は、ＬＵＴカスケードの各ＬＵＴで使用する変数を選択して論理関数メモリ２１のアドレス入力端子に接続するための切換回路である。また、接続メモリ２６には、ＬＵＴカスケードの各ＬＵＴに対応して、当該ＬＵＴで使用する変数（入力変数及び中間変数）を論理関数メモリ２１に接続するための接続切換信号が格納されている。
【００７９】
接続回路２５は、入力端子X0〜Xu-1,Y0〜Yu-1、出力端子W0〜Wu-1、及び切換制御入力端子C0〜Cu-1を備えている。入力端子Y0〜Yu-1は、入力変数選択回路２３の各出力端子に接続されている。入力端子X0〜Xu-1は、論理関数メモリ２１の各出力端子D0〜Du-1に接続されている。出力端子W0〜Wu-1は、論理関数メモリ２１のアドレス入力端子A0〜Au-1に接続されている。また、切換制御入力端子C0〜Cu-1は、接続メモリ２６の各出力端子に接続されている。接続回路２５は、入力端子X0〜Xu-1,Y0〜Yu-1と出力端子W0〜Wu-1との接続を、切換制御入力端子C0〜Cu-1から入力される接続切換信号INSELに従って切り換える。
【００８０】
尚、論理関数メモリ２１のアドレス入力端子Au〜Au+m-1には、演算制御部３０から出力されるｍビットのページ・カウント信号CNTの出力線が接続されている。
【００８１】
出力デコーダ２７は、符号化された論理関数メモリ２１の出力値を復号して、ＬＵＴカスケードの出力変数f0〜fn-1を出力するための回路である。出力デコーダ２７は、ＬＵＴカスケードの各段のＬＵＴの出力に対する復号テーブルが格納されたメモリにより構成されている。出力デコーダ２７は、u+mビットの入力端子A0〜Au+m-1と、nビットの出力端子D0〜Dn-1とを備えている。出力デコーダ２７のデータ入力端子A0〜Au-1は、それぞれ論理関数メモリ２１の出力端子D0〜Du-1に接続されている。また、出力デコーダ２７のデータ入力端子Au〜Au+m-1には、後述のページ・カウンタ３５が出力するページ・カウント信号CNTが入力される。このページ・カウント信号CNTによって、復号テーブルが選択される。そして、データ入力端子A0〜Au-1から入力されるＬＵＴ出力値d0〜du-1に対応する復号テーブルの値が、出力デコーダ２７の出力端子D0〜Dn-1から、出力変数f0〜fn-1として出力される。
【００８２】
出力レジスタ２９は、出力デコーダ２７から出力されるＬＵＴカスケードの出力変数f0〜fn-1をラッチして記憶するレジスタである。出力レジスタ２９は、後段の回路との同期をとるためのバッファとしての役割を有する。出力レジスタ２９は、nビットのデータ入力端子Di0〜Din-1、nビットのデータ出力端子Do0〜Don-1、クロック入力端子CLK、チップ・セレクト端子CE、及びリセット端子(R)nを備えている。リセット端子(R)nには、外部からのリセット信号(RST)nが入力される。このリセット端子(R)nに０が入力されると、出力レジスタ２９は、ラッチした値をすべて０として、データ出力端子Do0〜Don-1の出力値を０とする。チップ・セレクト端子CEには、後述の演算制御部３０が出力するアウトプット・イネーブル信号(OE)nが入力される。クロック入力端子CLKには、外部からのクロックCLKが入力される。リセット端子(R)nに０が入力された状態であっても、チップ・セレクト端子CEの入力値が１のときには、出力レジスタ２９は、データ入力端子Di0〜Din-1からの入力を受け付けない。一方、チップ・セレクト端子CEの入力値が０のときには、出力レジスタ２９は、クロックCLKの立ち上がりにおいて、データ入力端子Di0〜Din-1からの入力をラッチする。そして、ラッチしたデータを、データ出力端子Do0〜Don-1から出力する。
【００８３】
演算制御部３０は、ＬＵＴカスケード論理回路全体の演算動作の制御を行う。演算制御部３０の詳細については後で詳述する。
【００８４】
図１２は図１１の入力変数選択回路の構成の一例を示す図である。図１２においては、入力変数選択回路２３は循環的なバレルシフタにより構成している。ここでは、一例として、入力変数選択回路２３は１７入力８出力としているが、入出力数はこれに限られるものではない。
【００８５】
入力変数選択回路２３は、入力側から、８ビットの循環的なバレルシフタ２３−３、４ビットの循環的なバレルシフタ２３−２、２ビットの循環的なバレルシフタ２３−１、１ビットの循環的なバレルシフタ２３−０が直列に接続された構成からなる。バレルシフタ２３−３の各入力パッドIn0〜In16には、入力変数レジスタ２２の各出力端子が接続される。また、バレルシフタ２３−０の各入力パッドOut0〜Out7には、接続回路２５の入力端子の一部が接続される。各バレルシフタ２３−０〜２３−３は、入力選択メモリ２４から入力される４ビットの選択信号INSEL（INSEL0〜INSEL3）により任意ビット数の循環的なシフトを行う。これにより、入力変数レジスタ２２の各出力端子の一部と接続回路２５の入力端子の一部との接続位置を自由に変更することが可能である。
【００８６】
図１３は図１１の接続回路の構成の一例を示す図である。図１３（ａ）は接続回路２５の全体構成を表している。図１３（ａ）において、接続回路２５の変数入力端子X0〜Xu-1は、それぞれ、論理関数メモリ２１のｕ本の出力端子D0〜Du-1に接続される。また、接続回路２５の変数入力端子Y0〜Yu-1は、入力変数選択回路２３のｕ本の出力端子x0〜xu-1に接続される。また、接続回路２５の選択入力端子C0〜Cu-1は、接続メモリ２６のｕ本の出力端子CNSET0〜CNSETu-1に接続される。一方、接続回路２５の変数出力端子W0〜Wu-1は、それぞれ、論理関数メモリ２１のｕ本のアドレス入力端子A0〜Au-1に接続される。
【００８７】
接続回路２５の変数入力端子Xi，Yi及び変数出力端子Wi（ｉ∈{0,1,…,u-1}）の交点には、切換回路２５ａが設けられている。選択入力端子Ciには、これらの各切換回路２５ａを制御するための信号が入力される。
【００８８】
切換回路２５ａは、具体的には、図１３（ｂ）に示したような論理回路により構成されている。図１３（ｂ）の切換回路２５ａは、入力Xi，Yi，Ciに対して、出力Wiは（数４）のようになる。
【００８９】
【数４】
2005165502.tif 000009
【００９０】
すなわち、接続メモリ２６から選択入力端子Ciに入力される接続切換信号CNSETiが論理０の場合には、Wi=Yiとなり、入力変数選択回路２３の出力端子xiが論理関数メモリ２１の入力端子Aiに接続される。これにより、ＬＵＴカスケードの次段のＬＵＴに入力変数xiを直接入力することができる。
【００９１】
一方、接続メモリ２６から選択入力端子Ciに入力される接続切換信号CNSETiが論理１の場合には、Wi=Xiとなり、入力変数選択回路２３の出力端子xiが論理関数メモリ２１の入力端子Aiに接続される。これにより、ＬＵＴカスケードの前段のＬＵＴの出力である中間変数を後段のＬＵＴの入力変数として転送することができる。
【００９２】
図１４は図１１の演算制御部の構成を表すブロック図である。本実施例に係る演算制御部３０は、ページ・カウンタ３５、終端判定値メモリ３６、終端節点判定器３７、ＡＮＤ回路３８、及びビジー生成回路３９を備えている。
【００９３】
ページ・カウンタ３５は、外部から入力されるクロックCLKを計数し、その計数値をｍビットのページ・カウント信号CNTとして出力するカウンタである。このページ・カウント信号CNTは、ＬＵＴカスケードのうち、次に演算を行うＬＵＴの段数に対応している。ページ・カウンタ３５は、クロック入力端子CLK、リセット入力端子(R)n、及びmビットのデータ出力端子Q0〜Qm-1を備えている。クロック入力端子CLKには、外部からのクロックCLKが入力される。ページ・カウンタ３５は、クロックCLKの立ち上がりをカウントして、データ出力端子Q0〜Qm-1から、ページ・カウント信号CNTとして出力する。リセット入力端子(R)nは、ＡＮＤ回路３８の出力端子に接続されている。リセット入力端子(R)nが０のとき、ページ・カウンタ３５は、ページ・カウント信号CNTを強制的に０クリアする。
【００９４】
終端判定値メモリ３６には、各ページ・カウント信号CNTに対して、そのページ・カウント信号CNTに対応する段のＬＵＴの出力が終端節点であるか否かを判定するための判定値が記憶されている。この終端判定値メモリ３６は、mビットのアドレス入力端子Di0〜Dim-1、uビットのデータ出力端子Do0〜Dou-1、及びアドレス・ストローブ端子(AS)nを備えている。アドレス入力端子 Di0〜Dim-1には、ページ・カウンタ３５が出力するページ・カウント信号CNTが入力される。アドレス・ストローブ端子(AS)nには、クロックCLKが入力される。終端判定値メモリ３６は、クロックCLKの立ち下がりで、ページ・カウント信号CNTをラッチする。そして、ラッチされたページ・カウント信号CNTの値で指定されるアドレスに格納されている判定値を、終端判定閾値th0〜thu-1として、データ出力端子Do0〜Dou-1から出力する。
【００９５】
終端節点判定器３７は、デジタル・コンパレータ４０、Ｔフリップ・フロップ４１、Ｄフリップ・フロップ４２、及びＯＲ回路４３により構成されている。この終端節点判定器３７は、終端判定値メモリ３６から出力される判定値と、論理関数メモリ２１の出力値とを比較する。そして、終端節点に達したか否かを判定し、その判定値をアウトプット・イネーブル信号(OE)nとして出力する。終端節点に達した場合には、アウトプット・イネーブル信号(OE)nとして０を出力し、達していない場合には１を出力する。
【００９６】
デジタル・コンパレータ４０は、uビットの入力端子A、uビットの入力端子B、及び１ビットの出力端子(A<B)を備えている。入力端子Aには、終端判定閾値th0〜thu-1が入力される。入力端子Bには、論理関数メモリ２１から、ＬＵＴ出力値d0〜du-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には１（無効）が設定されている。以下、時間を追って、ＬＵＴカスケード論理回路の動作を説明する。
【０１０４】
尚、図１５の例においては、論理関数メモリ２１の入力数は６ビット（入力変数４ビット＋ページ番号２ビット）、出力数は４ビットとした。また、論理関数メモリ２１には図１７に示したような、４つのＬＵＴを格納して演算を実行している。尚、図１７において、「ｘ」はドント・ケアを表す。
【０１０５】
〔１〕リセットからリセット直後の演算処理動作
（１）時刻t0
まず、時刻t0においてリセット信号(RST)nが０（有効）とされる。リセット信号(RST)nが０となると、出力レジスタ２９がリセットされ、出力レジスタ２９のnビットの出力値（Data OUT）はすべて０となる。また、演算制御部３０のＡＮＤ回路３８には、リセット信号(RST)n、アウトプット・イネーブル信号(OE)n、及びＤフリップ・フロップ４２の出力Qが入力されている。従って、リセット信号(RST)nが０となると、ＡＮＤ回路３８は０を出力する。これにより、ページ・カウンタ３５が出力するページ・カウント信号CNTの値が０クリアされる。そして、入力選択メモリ２４、接続メモリ２６、出力デコーダ２７、及び終端判定値メモリ３６の出力ページ数が０ページに設定される。
【０１０６】
入力選択メモリ２４は、０ページに格納されたmiビットの選択信号INSELを出力する。ここで、選択信号INSELは、入力変数選択回路２３において、入力変数レジスタ２２の出力のうちの一部を選択して接続回路２５に出力するための選択情報を有するバイナリ信号である。また、接続メモリ２６は、０ページに格納された接続回路２５の接続切換信号CNSETを出力する。ここで、接続切換信号CNSETは、接続回路２５の2u個の入力端子X0〜Xu-1, Y0〜Yu-1から入力される入力信号のうち、u個の出力端子W0〜Wu-1から出力する信号を選択するための選択情報を有するuビットのバイナリ信号である。また、終端判定値メモリ３６は、０ページに格納されたuビットの終端判定閾値th0〜thu-1を出力する。
【０１０７】
選択信号INSELが制定されると、その選択信号INSELに従って、入力変数選択回路２３が切り換わる。しかしながら、この時点では、入力変数レジスタ２２の出力は不定である。従って、入力変数選択回路２３の出力値であるuビットの入力変数信号x0〜xu-1の値も不定である。また、接続切換信号CNSETが制定されると、接続回路２５の接続状態が切り換わる。しかしながら、この時点では、入力変数信号x0〜xu-1の値も論理関数メモリ２１の出力値（「ＬＵＴ出力値」という。）d0〜du-1も不定である。従って、接続回路２５のuビットの出力値（「ＬＵＴ変数値」という。）a0〜au-1も不定である。更に、終端判定閾値th0〜thu-1が制定されると、デジタル・コンパレータ４０の出力値(A<B)も切り換わる。しかしながら、この時点では、ＬＵＴ出力値d0〜du-1は不定である。従って、デジタル・コンパレータ４０の出力値(A<B)も不定である。
【０１０８】
一方、時刻t0において、リセット信号(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）として不定な値が出力されることが防止される。
【０１１０】
一方、時刻t0において、リセット信号(RST)nが０（有効）とされると、ビジー生成回路３９内のＤフリップ・フロップ４５のリセット端子(R)nの入力値が０となる。従って、Ｄフリップ・フロップ４５はリセットされて、出力Qは０となる。
【０１１１】
また、ビジー生成回路３９内のＯＲ回路４７には、ビジー生成回路３９内のＤフリップ・フロップ４５の出力Qと、終端節点判定器３７内のＤフリップ・フロップ４２の出力(Q)nとが入力される。そして、両者のＯＲ論理を、ビジー信号BUSYとして出力する。上述のように、時刻t0で、Ｄフリップ・フロップ４２の出力(Q)nは１に設定される。従って、ＯＲ回路４７は、ビジー信号（BUSY）として１（有効）を出力する。このように、リセット直後の不定な状態において、Ｄフリップ・フロップ４２の出力(Q)nを使ってビジー信号BUSYを１（有効）としておくことで、誤った出力値（Data OUT）が出力されることが防止される。
【０１１２】
（２）時刻t1
時刻t1において、リセット信号(RST)nは１（無効）となる。このとき、終端節点判定器３７のＴフリップ・フロップ４１の出力(Q)nは０に、Ｄフリップ・フロップ４２の出力(Q)nは１に、ビジー生成回路３９のＤフリップ・フロップ４５の出力Qは０に、それぞれラッチされた状態で保持される。従って、アウトプット・イネーブル信号(OE)nは１（無効）に、ビジー信号BUSYは１に保持される。
【０１１３】
また、終端節点判定器３７のＴフリップ・フロップ４１のセット端子(S)nの入力値は１（無効）となり、Ｔフリップ・フロップ４１はトリガ入力の受け付けが可能となる。また、終端節点判定器３７のＤフリップ・フロップ４２のリセット端子(R)nの入力値は１（無効）となり、Ｄフリップ・フロップ４２は、クロックCLKの立ち下がりにおいてデータ入力の受け付けが可能となる。
【０１１４】
一方、ＡＮＤ回路３８の入力のうち、Ｄフリップ・フロップ４２の出力Qの値は０である。従って、ＡＮＤ回路３８の出力は０に保持される。そして、ページ・カウンタ３５は、リセット状態に保持される。
【０１１５】
（３）時刻t2
時刻t2において、データ・ストローブ信号(DS)nが０となる。このデータ・ストローブ信号(DS)nは、ビジー生成回路２９内の入力回路４４に入力されている。入力回路４４は、データ・ストローブ信号(DS)nの反転論理と、ＡＮＤ回路４６の出力値とのＯＲ論理を出力する。従って、入力回路４４は、Ｄフリップ・フロップ４５の入力端子Dに対して１を出力する。
【０１１６】
また、このデータ・ストローブ信号(DS)nの立ち下がりにおいて、入力変数レジスタ２２は、外部データ入力信号（Data input）の値をラッチし、入力変数選択回路２３に出力する。入力変数選択回路２３は、入力変数レジスタ２２から入力される入力データを、選択信号INSELの値に従って選択し、入力変数信号x0〜xu-1として接続回路２５に出力する。この時点で、入力変数信号x0〜xu-1の値が確定する。接続回路２５は、接続切換信号CNSETの値に従って、入力端子Y0〜Yu-1より入力される入力変数信号x0〜xu-1の値を、出力端子W0〜Wu-1からＬＵＴ変数値a0〜au-1として出力する。この時点で、ＬＵＴ変数値a0〜au-1の値も確定する。
【０１１７】
（４）時刻t3
時刻t3において、クロックCLKが０から１に変化する。この立ち上がりにおいて、ビジー生成回路３９内のＤフリップ・フロップ４５は、入力端子Dから入力されている論理値１をラッチして、出力端子Qに出力する。このＤフリップ・フロップ４５の出力は、ＯＲ回路４７に入力される。ＯＲ回路４７のもう一方の入力には、その前から、Ｄフリップ・フロップ４２の反転出力(Q)nとして論理値１が入力されているので、ここではＯＲ回路４７の出力は１に保持されたままで変化はしない。従って、ビジー信号BUSYは１に保持される。
【０１１８】
（５）時刻t4
時刻t4において、データ・ストローブ信号(DS)nが０から１に変化する。終端節点判定器３７内のＴフリップ・フロップ４１のトリガ入力端子Ｔには、データ・ストローブ信号(DS)nが入力されている。従って、データ・ストローブ信号(DS)nの立ち上がりにおいて、Ｔフリップ・フロップ４１の出力(Q)nは０から１に反転する。
【０１１９】
（６）時刻t5
時刻t5において、クロックCLKが１から０に変化する。このとき、論理関数メモリ２１は、この立ち下がりにおいて、アドレス端子A0〜Au+m-1より入力されているＬＵＴ変数値a0〜au-1及びページ・カウント信号CNTの値（０）を、内部のアドレス・レジスタにラッチする。これに伴って、論理関数メモリ２１は、０ページに格納された１段目のＬＵＴを使用して、ＬＵＴ変数値a0〜au-1を入力とする選択演算を行い、その結果を出力端子D0〜Du-1からＬＵＴ出力値d0〜du-1として出力する。この時点で、ＬＵＴ出力値d0〜du-1の値が確定する。
【０１２０】
また、デジタル・コンパレータ４０の入力端子Aには終端判定閾値th0〜thu-1が入力されており、入力端子BにはＬＵＴ出力値d0〜du-1が入力されている。従って、ＬＵＴ出力値d0〜du-1が確定すると、デジタル・コンパレータ４０は、終端判定閾値th0〜thu-1とＬＵＴ出力値d0〜du-1とを比較して、ＬＵＴ出力値d0〜du-1が終端判定閾値th0〜thu-1より大きい場合には１（未終了）を、それ以外の場合には０（終了）を出力する。この時点で、デジタル・コンパレータ４０の出力値（A<B）が確定する。図１５の例では、最初の演算の結果、まだ終端節点に達していないとして、デジタル・コンパレータ４０は、１を出力している。デジタル・コンパレータ４０の出力値（A<B）は、ＯＲ回路４３の入力端子の一方に入力される。
【０１２１】
一方、終端節点判定器３７内のＤフリップ・フロップ４２は、このクロックCLKの立ち下がりにおいて、Ｔフリップ・フロップ４１の出力(Q)nから入力されている論理値１をラッチする。そして、Ｄフリップ・フロップ４２は、出力端子Qに論理値１を、出力端子(Q)nに論理値０を出力する。Ｄフリップ・フロップ４２の出力(Q)nが０となると、ＯＲ回路４３の入力の一方が０となる。しかしながら、ＯＲ回路４３のもう一方の入力端子へ入力されているデジタル・コンパレータ４０の出力値（A<B）は１なので、ＯＲ回路４３の出力は１に保持される。従って、アウトプット・イネーブル信号(OE)nは１（無効）に保持される。
【０１２２】
また、Ｄフリップ・フロップ４２の出力端子Qは、Ｔフリップ・フロップ４１のリセット端子Rに接続されている。従って、Ｔフリップ・フロップ４１はリセット状態となり、以降はその出力(Q)nは１に固定される。Ｔフリップ・フロップ４１の出力(Q)nが１に固定されると、Ｄフリップ・フロップ４２の出力端子Qも１に固定される。その結果、時刻t5以降は、次にリセット信号(RST)nが０となるまでは、Ｔフリップ・フロップ４１及びＤフリップ・フロップ４２の出力値は固定され、これらの回路は他の外部入力を受け付けなくなる。
【０１２３】
さらに、Ｄフリップ・フロップ４２の出力Qが１となると、アウトプット・イネーブル信号(OE)nは１、リセット信号(RST)nは１なので、ＡＮＤ回路３８の出力が１となる。これにより、ページ・カウンタ３５は、リセット状態が解除され、クロックCLKのカウントが可能な状態となる。
【０１２４】
（７）時刻t6
時刻t6において、クロックCLKは０から１に変化する。このクロックCLKの立ち上がりにおいて、ページ・カウンタ３５は、ページ・カウント信号CNTの値を１だけ増加させる。ページ・カウント信号CNTが１となると、入力選択メモリ２４、接続メモリ２６、出力デコーダ２７、及び終端判定値メモリ３６の出力ページ数が１ページに設定される。
【０１２５】
入力選択メモリ２４の出力ページ数が１ページに切り換わると、選択信号INSELの値が、２段目のＬＵＴの入力変数を選択する信号に切り換わる。これにより、入力変数選択回路２３の接続の切り換えが行われ、入力変数信号x0〜xu-1の値が変更される。
【０１２６】
接続メモリ２６の出力ページ数が１ページに切り換わると、接続切換信号CNSETの値が、２段目のＬＵＴの入力変数及び中間変数を出力するための接続信号に切り換わる。これにより、接続回路２５の接続の切り換えが行われ、ＬＵＴ変数値a0〜au-1の値が変更される。
【０１２７】
（８）時刻t7
時刻t7において、クロックCLKは１から０に変化する。このクロックCLKの立ち下がりにおいて、論理関数メモリ２１は、アドレス端子A0〜Au+m-1より入力されているＬＵＴ変数値a0〜au-1及びページ・カウント信号CNTの値（１）を、内部のアドレス・レジスタにラッチする。これに伴って、論理関数メモリ２１は、１ページに格納された２段目のＬＵＴを使用して、ＬＵＴ変数値a0〜au-1を入力とする選択演算を行い、その結果を出力端子D0〜Du-1からＬＵＴ出力値d0〜du-1として出力する。
【０１２８】
また、このクロックCLKの立ち下がりにおいて、終端判定値メモリ３６は、ページ・カウント信号CNTを内部のアドレス・レジスタにラッチする。これにより、終端判定値メモリ３６が出力する終端判定閾値th0〜thu-1は、２段目のＬＵＴの出力に対して終端節点に達したか否かを判定するための閾値に変更される。
【０１２９】
以上の、時刻t6〜t7の動作は、ＬＵＴカスケード論理回路による演算が終了するまで繰り返される。尚、図１５の例では、２段目のＬＵＴによる演算が終了した時点で、終端節点に達している。そこで、次のようなアウトプット・イネーブル信号(OE)nを有効とする動作を行い演算終了処理動作に移行する。
【０１３０】
時刻t7において、２段目のＬＵＴに対してＬＵＴ出力値d0〜du-1が出力されると、この出力値は、終端節点判定器３７のデジタル・コンパレータ４０に入力される。デジタル・コンパレータ４０は、２段目のＬＵＴのＬＵＴ出力値d0〜du-1と、２段目のＬＵＴの出力に対する終端判定閾値th0〜thu-1とを比較する。この場合、前者の値は後者の値以下であり、デジタル・コンパレータ４０の出力は０に切り換わる。このデジタル・コンパレータ４０の出力はＯＲ回路４３の一方の入力端子に入力される。ＯＲ回路４３のもう一方の入力端子には、Ｄフリップ・フロップ４２の出力(Q)nが入力されているが、この値は既に０にラッチされている。従って、ＯＲ回路４３の出力であるアウトプット・イネーブル信号(OE)nは０（有効）に切り換わる。アウトプット・イネーブル信号(OE)nは出力レジスタ２９のチップ・イネーブル端子(CE)nに入力されている。従って、アウトプット・イネーブル信号(OE)nが０（有効）となると、出力レジスタ２９は、それ以降はクロックCLKの立ち上がりにおいてデータの取り込みが可能な状態となる。
【０１３１】
尚、このとき、ＬＵＴ出力値d0〜du-1は、出力デコーダ２７に入力されている。出力デコーダ２７は、ＬＵＴ出力値d0〜du-1を、２段目のＬＵＴ出力に対応する復号テーブルによって復号して、ｎビットの出力変数f0〜fn-1を出力する。そして、この出力変数f0〜fn-1が、出力レジスタ２９の入力端子Di0〜Din-1に入力されている。
【０１３２】
また、アウトプット・イネーブル信号(OE)nが０となると、ビジー生成回路３９のＡＮＤ回路４６の一方の入力値が０となる。従って、ＡＮＤ回路４６の出力値は０となる。一方、入力回路４４は、ＡＮＤ回路４６の出力値と、データ・ストローブ信号(DS)nの否定とのＯＲ演算を行う。この時点で、データ・ストローブ信号(DS)nは１である。従って、入力回路４４は、Ｄフリップ・フロップ４５のデータ入力端子Dに対して０を出力する。
【０１３３】
（９）時刻t8
時刻8において、クロックCLKは０から１に変化する。このクロックCLKの立ち上がりにおいて、出力レジスタ２９は、出力変数f0〜fn-1をラッチする。これにより、出力レジスタ２９の出力端子Do0〜Don-1から、出力値（Data OUT）として出力変数f0〜fn-1が出力され、演算が終了する。
【０１３４】
また、ビジー生成回路３９のＤフリップ・フロップ４５は、クロックCLKの立ち上がりにおいて、データ入力端子Dの入力値０をラッチし、ＯＲ回路４７の一方の入力端子に０を出力する。ここで、ＯＲ回路４７のもう一方の入力端子には、終端節点判定器３７のＤフリップ・フロップ４２の出力(Q)nが入力されている。この時点で、Ｄフリップ・フロップ４２の出力(Q)nは０である。従って、ＯＲ回路４７が出力するビジー信号BUSYは０に切り換わる。ビジー信号BUSYが０であることが、外部データ入力信号(Data input)に対する演算が終了することを表す。従って、ビジー信号BUSYが０のときの出力レジスタ２９の出力値(Data out)が、外部データ入力信号(Data input)に対する目的関数の演算結果であることが分かる。
【０１３５】
以上のようにして、ＬＵＴカスケードの一連の演算処理動作が行われる。
【０１３６】
〔２〕リセット直後以外の演算処理動作
次に、リセット直後以外の演算処理動作について説明する。この場合、終端節点判定器３７のＴフリップ・フロップ４１の出力(Q)nは１にラッチされたまま変化せず、Ｄフリップ・フロップ４２の出力Q,(Q)nは、それぞれ、１，０にラッチされたまま変化しない。従って、動作は単純となる。
【０１３７】
（１）時刻t9,t10
まず、時刻t9において、外部データ入力信号（Data input）が切り換わり、演算に使用する入力変数が設定される。そして、時刻t10において、データ・ストローブ信号DSが０（有効）とされる。
【０１３８】
このデータ・ストローブ信号(DS)nの立ち下がりにおいて、入力変数レジスタ２２は、新たな外部データ入力信号（Data input）の値をラッチし、入力変数選択回路２３に出力する。
【０１３９】
一方、データ・ストローブ信号(DS)nが０となると、ＡＮＤ回路３８の出力値も０となり、ページ・カウンタ３５はリセットされる。ページ・カウンタ３５がリセットされると、ページ・カウント信号CNTは０となる。これにより、入力選択メモリ２４、接続メモリ２６、出力デコーダ２７、及び終端判定値メモリ３６の出力ページ数が０ページに設定される。
【０１４０】
入力選択メモリ２４は、０ページに格納されたmiビットの選択信号INSELを出力する。これにより、入力変数選択回路２３が切り換えられる。入力変数選択回路２３は、入力変数レジスタ２２から入力される入力データを、選択信号INSELの値に従って選択し、入力変数信号x0〜xu-1として接続回路２５に出力する。この時点で、入力変数信号x0〜xu-1の値が確定する。
【０１４１】
また、接続メモリ２６は、０ページに格納された接続回路２５の接続切換信号CNSETを出力する。これにより、接続回路２５が切り換えられる。接続回路２５は、接続切換信号CNSETの値に従って、入力端子Y0〜Yu-1より入力される入力変数信号x0〜xu-1の値（１段目のＬＵＴに入力するための入力変数値）を、出力端子W0〜Wu-1からＬＵＴ変数値a0〜au-1として出力する。この時点で、ＬＵＴ変数値a0〜au-1の値も確定する。
【０１４２】
また、終端判定値メモリ３６は、０ページに格納されたuビットの終端判定閾値th0〜thu-1を出力する。
【０１４３】
一方、ビジー生成回路３９の入力回路４４は、データ・ストローブ信号(DS)nの否定とＡＮＤ回路４６の出力とのＯＲ論理を演算する。この時点では、データ・ストローブ信号(DS)nが０なので、Ｄフリップ・フロップ４５の入力端子Dに対して１を出力する。
【０１４４】
（２）時刻t11
時刻t11において、クロックCLKは０から１に変化する。このクロックCLKの立ち上がりにおいて、ビジー生成回路３９のＤフリップ・フロップ４５は、入力端子Dの入力値１をラッチして、出力端子Qから出力する。このＤフリップ・フロップ４５の出力は、ＯＲ回路４７に入力される。そして、ＯＲ回路４７の出力であるビジー信号BUSYは１に反転する。
【０１４５】
（３）時刻t12
時刻t12において、クロックCLKは１から０に変化する。このクロックCLKの立ち下がりにおいて、論理関数メモリ２１は、アドレス端子A0〜Au+m-1より入力されているＬＵＴ変数値a0〜au-1及びページ・カウント信号CNTの値（１）を、内部のアドレス・レジスタにラッチする。これに伴って、論理関数メモリ２１は、１ページに格納された１段目のＬＵＴを使用して、ＬＵＴ変数値a0〜au-1を入力とする選択演算を行い、その結果を出力端子D0〜Du-1からＬＵＴ出力値d0〜du-1として出力する。
【０１４６】
また、このクロックCLKの立ち下がりにおいて、終端判定値メモリ３６は、ページ・カウント信号CNTを内部のアドレス・レジスタにラッチする。これにより、終端判定値メモリ３６が出力する終端判定閾値th0〜thu-1は、１段目のＬＵＴの出力に対して終端節点に達したか否かを判定するための閾値に変更される。
【０１４７】
ＬＵＴ出力値d0〜du-1と終端判定閾値th0〜thu-1は、終端節点判定器３７のデジタル・コンパレータ４０に入力され、終端節点に達したか否かが判定される。そして、ＬＵＴ出力値d0〜du-1が終端判定閾値th0〜thu-1よりも大きい場合には１が、それ以外の場合には０が、アウトプット・イネーブル信号(OE)nとして出力される。
【０１４８】
以下、２段目以降のＬＵＴの演算処理動作は、リセット直後の演算処理動作の場合と同様である。尚、図１５においては、１段目のＬＵＴの演算が終了した時点で、既に終端節点に達し、アウトプット・イネーブル信号(OE)nとして０が出力されている。従って、ページ・カウンタ３５はリセット状態が維持され、ページ・カウント信号CNTは０に維持される。そして、時刻t13において、データ・ストローブ信号(DS)nが１に反転した後に、最初にクロックCLKが立ち上がった時点（時刻t14）で、出力レジスタ２９が出力変数f0〜fn-1をラッチするとともに、ビジー生成回路３９のＤフリップ・フロップ４５が０をラッチしてビジー信号BUSYが０となる。これにより、演算処理が終了する。
【０１４９】
以上のように、終端節点判定器３７において、ＬＵＴカスケードの中間変数から終端節点に達しているか否かを判定して、終端節点に達した場合には、後段のＬＵＴによる演算を打ち切って、出力レジスタ２９から出力変数を出力させることで、ＬＵＴカスケードによる演算速度を向上させることが可能となる。
【図面の簡単な説明】
【０１５０】
【図１】本発明の実施例１に係るＬＵＴ符号化装置の構成を表すブロック図である。
【図２】本発明の実施例１に係るＬＵＴ符号化方法を表すフローチャートである。
【図３】ＢＤＤの例を表す図である。
【図４】図３のＢＤＤを既約化したＲＯＢＤＤを表す図である。
【図５】ＲＯＢＤＤの分割を説明する図である。
【図６】図５のＲＯＢＤＤから生成されるＬＵＴカスケードを表す図である。
【図７】本発明の実施例２に係るＬＵＴ符号化装置の構成を表すブロック図である。
【図８】本発明の実施例２に係るＬＵＴ符号化方法を表すフローチャートである。
【図９】４ビット比較器のＭＴＢＤＤを表す図である。
【図１０】図９のＭＴＢＤＤから生成されるＬＵＴカスケードを表す図である。
【図１１】本発明の実施例３に係るＬＵＴカスケード論理回路の構成を表すブロック図である。
【図１２】図１１の入力変数選択回路の構成の一例を示す図である。
【図１３】図１１の接続回路の構成の一例を示す図である。
【図１４】図１１の演算制御部の構成を表すブロック図である。
【図１５】図１１及び図１４の各端子の出力値を表すタイムチャートである。
【図１６】図１４の各出力値を表すタイムチャートである。
【図１７】図１５の演算において使用したＬＵＴである。
【図１８】論理関数の二分決定グラフ（ＢＤＤ）を表す図である。
【図１９】ＬＵＴカスケード論理回路の構成を表す図である。
【符号の説明】
【０１５１】
１    論理仕様記憶手段
２    ＲＯＢＤＤ生成手段
３    ＲＯＢＤＤ記憶手段
４，１１    ＢＤＤ分割手段
５，１２    符号化手段
６    ＬＵＴ記憶手段
９    ＭＴＢＤＤ生成手段
１０    ＭＴＢＤＤ記憶手段
２１    論理関数メモリ
２２    入力変数レジスタ
２３    入力変数選択回路
２３−０〜２３−３    バレルシフタ
２４    入力選択メモリ
２５    接続回路
２５ａ    切換回路
２６    接続メモリ
２７    出力デコーダ
２９    出力レジスタ
３０    演算制御部
３５    ページ・カウンタ
３６    終端判定値メモリ
３７    終端節点判定器
３８    ＡＮＤ回路
３９    ビジー生成回路
４０    デジタル・コンパレータ
４１    Ｔフリップ・フロップ
４２    Ｄフリップ・フロップ
４３    ＯＲ回路
４４    入力回路
４５    Ｄフリップ・フロップ
４６    ＡＮＤ回路
４７    ＯＲ回路
【図１】
2005165502.tif 000010
【図２】
2005165502.tif 000011
【図３】
2005165502.tif 000012
【図４】
2005165502.tif 000013
【図５】
2005165502.tif 000014
【図６】
2005165502.tif 000015
【図７】
2005165502.tif 000016
【図８】
2005165502.tif 000017
【図９】
2005165502.tif 000018
【図１０】
2005165502.tif 000019
【図１１】
2005165502.tif 000020
【図１２】
2005165502.tif 000021
【図１３】
2005165502.tif 000022
【図１４】
2005165502.tif 000023
【図１５】
2005165502.tif 000024
【図１６】
2005165502.tif 000025
【図１７】
2005165502.tif 000026
【図１８】
2005165502.tif 000027
【図１９】
2005165502.tif 000028