(57)【要約】【課題】回路の更なる簡単化及び回路を構成する素子の個数の更なる低減を行うことができる論理回路設計装置、方法及びプログラムを提供する。【解決手段】ステップＳ０で、所定の論理関数を表現する無向グラフを構築する。ステップＳ１で、その無向グラフの各枝及び節点での許容関数集合を取得する。ステップＳ２，Ｓ３で、許容関数集合に基づいて、無向グラフ内に削除可能な枝又は併合可能な節点対が存在するか否かを判断する。ステップＳ４で、許容関数集合に基づいて、無向グラフ内に追加可能なリテラルがラベル付けされた枝が存在するか否かを判断する。ステップＳ９において、縮小された論理関数を表現する無向グラフを出力する。【選択図】図１８
2006059022.tif 000002
【特許請求の範囲】
【請求項１】
節点と、両端の節点対とラベルとして割り当てられるリテラルにより特徴付けられる枝から成る、論理関数を表現するグラフを用いて、回路設計を行う回路設計装置であって、
所定の論理関数を表現する無向グラフを構築する手段と、
その無向グラフの各枝及び節点での許容関数集合を取得する手段と、
その許容関数集合に基づいて、前記無向グラフ内に削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合する手段と、
削除可能な枝又は併合可能な節点対が存在しない場合に、前記許容関数集合に基づいて、前記無向グラフ内に追加可能である枝の存在を判断し、追加可能な枝のうち一つを追加する手段と、
追加可能な枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力する手段とを具えることを特徴とする回路設計装置。
【請求項２】
削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合した後、前記無向グラフ内の形状的に冗長な枝又は節点を削除する手段を更に具えることを特徴とする請求項１記載の回路設計装置。
【請求項３】
節点と、両端の節点対とラベルとして割り当てられるリテラルにより特徴付けられる枝から成る、論理関数を表現するグラフを用いて、回路設計を行う回路設計方法であって、
所定の論理関数を表現する無向グラフを構築するステップと、
その無向グラフの各枝及び節点での許容関数集合を取得するステップと、
その許容関数集合に基づいて、前記無向グラフ内に削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合するステップと、
削除可能な枝又は併合可能な節点対が存在しない場合に、前記許容関数集合に基づいて、前記無向グラフ内に追加可能である枝の存在を判断し、追加可能な枝のうち一つを追加するステップと、
追加可能な枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力するステップとを具えることを特徴とする回路設計方法。
【請求項４】
削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合した後、前記無向グラフ内の形状的に冗長な枝又は節点を削除するステップを更に具えることを特徴とする請求項３記載の回路設計方法。
【請求項５】
節点と、両端の節点対とラベルとして割り当てられるリテラルにより特徴付けられる枝から成る、論理関数を表現するグラフを用いて、回路設計を行う回路設計プログラムであって、
所定の論理関数を表現する無向グラフを構築するステップと、
その無向グラフの各枝及び節点での許容関数集合を取得するステップと、
その許容関数集合に基づいて、前記無向グラフ内に削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合するステップと、
削除可能な枝又は併合可能な節点対が存在しない場合に、前記許容関数集合に基づいて、前記無向グラフ内に追加可能である枝の存在を判断し、追加可能な枝のうち一つを追加するステップと、
追加可能な枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力するステップとを具えることを特徴とする回路設計プログラム。
【請求項６】
削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合した後、前記無向グラフ内の形状的に冗長な枝又は節点を削除するステップを更に具えることを特徴とする請求項５記載の回路設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理関数を表現する無向グラフを縮小し、決定グラフからその論理関数を実現するスイッチ型論理回路を設計する論理回路設計装置、方法及びプログラムに関する。特許請求の範囲又は明細書において、「グラフ」とは、節点と、節点対を繋ぐ枝とから成る図形を意味し、現実世界の実体を概念化するものであり、「無向グラフ」とは、節点と無向枝（グラフをたどるときに導通方向が制限されない枝）のみから成るグラフを意味し、「有向グラフ」とは、節点と有向枝（グラフとたどるときに導通方向が一つに制限される枝）のみから成るグラフを意味し、「決定グラフ」とは、各接点に属性が与えられ、その属性がとりうる条件をその節点から隣接接点へ導通する有向枝に与えられて構成される有向グラフであって、節点における条件判定による有向枝の選択と導通を繰り返すことによって終端節点に到達するグラフを意味し、「属性」とは、実体をグラフ表現で概念化するときに、実体において節点又は枝に相当するものが有する属性（地理情報をグラフ表現する場合、地点を節点とし、それらの対に置かれる枝には、距離のような属性値が与えられることが考えられる。）を意味する。また、「枝の導通」とは、グラフをたどるときに枝を通過することを意味し、枝の導通あるいは不導通は枝に与えられた属性により決定されるため、決定グラフは終端節点以外の節点の属性と枝の属性をひとまとめにして枝の属性とすることで有向グラフや無向グラフで表現可能であり、「導通関数」とは、枝の導通を表すための関数を意味する。
【背景技術】
【０００２】
論理関数は、１つ以上の論理変数それぞれに対して０又は１を代入することで得られるベクトルと定義域としともに値域を０又は１とする関数であり、従来の表現形態としては、次のようなものがある。
（１）「リテラル」と呼ばれる論理変数自身あるいはその論理否定の論理和、論理積、論理否定などの演算子を用いた論理式表現。
（２）ベクトルと関数の値の尾関係を表現した真理値表。
（３）決定グラフ
【０００３】
論理関数を論理式で表現して、その式から論理回路を導出する場合、その論理関数を論理式中の演算子が対応付けられた節点と、節点の関係を枝であらわした有向グラフによって表現する手法がある。
【０００４】
前記有向グラフから論理回路を実現する場合、節点に対応する論理演算子を１つのゲートで実現する方法が考えられるが、その論理演算を行う論理ゲートが回路設計で利用される技術に適していない場合があることや、できるだけ多くの論理演算を１つのゲートでまとめて行う方がより高性能な回路を実現できることから、論理式を表現する有向グラフ中の部分グラフを１つのゲートに対応させることで論理回路を実現する方法で回路設計を行うのが一般的である。
【０００５】
論理関数を表現する論理式を有向グラフで表現する場合、その有向グラフに対して、回路技術に適した部分グラフを見つける工程が必要となるため、有向グラフが目的の論理関数を実現する回路を直接表現していない。
【０００６】
論理関数を積和形で実現し、格子状のトランジスタ網で実現するＰＬＡ(Programmable Logic Array)の回路構成を、図１に示す。この場合、回路に与えられた変数の正負両リテラルを意味する信号をＮＯＴゲートで生成し、積項生成部１と論理和生成部２とで複数の論理関数の積和形を実現するために、定型的な回路パターンにより設計コストが低減するという利点がある。
【０００７】
ＰＬＡは、実現される一つ以上の論理関数のうち、積和形が複雑であるとともに積項数が論理変数の個数に対して指数関数的に増大するときには回路面積も指数関数的に増大するため、高性能化及び面積抑制の観点から不都合である。
【０００８】
論理関数を表現する真理値表を直接的に利用可能にするためには、図２に示すように、値を記憶するメモリ３と、ベクトルに応じて出力する値を選択する多制御入力のマルチプレクサ４とによって直接的に構成することができるが、この場合、論理変数の個数に応じてメモリの大きさが指数関数的に増大するという不都合や、必要なメモリ容量が論理関数の性質によらずに論理変数の個数で決定されるという不都合がある。
【０００９】
比較的少ない記憶量で論理関数を表現できる手法として決定グラフがあり、決定グラフには様々な種類がある。最も基本的な決定グラフは、図３に一例を示す二分決定グラフであり、この場合、論理積演算子及び論理和演算子をそれぞれ“・”及び“＋”で表記したときにｘ１・ｘ２＋ｘ３・ｘ４と表記される論理関数を表現している。
【００１０】
二分決定グラフは、帰還ループのない有向グラフであり、図４に示すように、節点５にはそれぞれ変数ｘがラベル付けされ、「０枝」５と「１枝」６の２本の枝を必ず有する。グラフの最下部には「０終端節点」８と「１終端節点」９があり、どのようなベクトルに対しても「０終端節点」８と「１終端節点」９のいずれかに到達するパスが存在する。
【００１１】
二分決定グラフは、全てのパスにおける変数順序が固定されている場合、次のような利点のために、集積回路の論理設計ツールの標準的データ構造として採用されている。
（１）論理関数とそれを表現するグラフとが１対１の関係にあるため、二つの関数が等価であるか否かの判定が容易である。
（２）単純な論理関数は、少ない記憶量で表現できる。
（３）論理演算のための操作の計算量が比較的小さく、アルゴリズムが簡潔である。
【００１２】
二分決定グラフにおいて、グラフ中の各節点及びその２本の出力枝の組を、図５に示すような１制御入力のマルチプレクサで実現することができる。この場合、１制御入力のマルチプレクサは、二つのパストランジスタによって構成されるスイッチと同様な動作を行う伝送ゲートと、ＮＯＴゲートとで実現することができ、０終端節点及び１終端節点をそれぞれ接地点及び電源として回路中で実現することができるので、グラフの構造から直接的にトランジスタ回路を構成することができる（例えば、特許文献１及び非特許文献１参照）。
【００１３】
図５に示す１制御入力のマルチプレクサは、図６に示すリレー・コンタクト回路と同様な動作を行う。本明細書中、図５，６に示す回路を、図７のように簡単に表記する。図８に示すような簡単に表記された回路は、「電源までの導通パスがあるか否か」という点で決定グラフになると考えられ、接地点にしか導通パスのない枝を除去することによって、図８に示すような有向グラフで論理関数ｆ＝ｘ１・ｘ２＋ｘ３・ｘ４を表現することができる。
【００１４】
一般的な集合は、各要素を０と１によるベクトルで表現し、その集合にベクトルが含まれている場合には、対応する値を１とし、それ以外の場合には、対応する値を０とすることによって、一般的な集合を論理関数で扱うことができるため、一般的な集合を扱う問題への応用のための論理関数表現として零圧縮二分決定グラフが提案されている。その一例として、論理関数の積和形ｆ＝ｘ１・ｘ２＋ｘ３・ｘ４を表現する零圧縮二分決定グラフを、図１０に示す。
【００１５】
零圧縮二分決定グラフも、有向グラフであり、節点、枝及び葉を有し、各節点には論理変数がラベル付けされ、図４で示される二分決定グラフの各節点と、次の節点や終端節点に向かって出ている二つの枝と同様に表現される。
【００１６】
論理関数の積和形は積項の集合と解釈できるため、それを零圧縮二分決定グラフで表現することができ、積和形を表現する場合、各節点にラベル付けされるのは、変数ではなく、（図１０の例では、一方だけであるが、）一般的には正負いずれかのリテラルである。
【００１７】
各変数の正リテラルと負リテラルについて、積項がそのリテラルを有するときは１で表現し、積項がそのリテラルを有しないときは０で表現して、全ての変数の正負両リテラルについての０と１での情報をベクトルで表現する場合、そのベクトルの集合が積和形を意味しており、その集合を零圧縮二分決定グラフで表現することができる。
【００１８】
零圧縮二分決定グラフにおいて、図１１に示すように、先ず、０終端節点への枝を全て取り払って開放端とするとともに、１終端節点を端子とし、各節点からでる１枝及び０枝をそれぞれ、対応する節点にラベル付けされたリテラルで制御されるスイッチと結線を形成し、スイッチ型素子による論理回路を直接的に構成することができる（例えば、非特許文献２参照）。
【００１９】
図１０に例示されるような零圧縮二分決定グラフから、図１２に示すようなスイッチ型論理回路を構成できることを考慮すれば、スイッチ型素子の組合せによる２端子回路は、論理関数の表現法であるとみなすことができ、従来のスイッチ型素子による組合せ論理回路設計技術は、論理関数を表現するグラフ表現であるとみなすことができる（例えば、非特許文献３〜９参照）。
【００２０】
一般に、有向グラフよりも無向グラフの方が、少ない記憶量で複雑な論理関数を表現することができ、図３に示す二分決定グラフ、図１０に示す零圧縮二分決定グラフ、図１２に示す簡略化した零二分決定グラフに対する論理関数ｇ＝ｘ１・ｘ２＋ｘ３・ｘ４＋ｘ１・ｘ４・ｘ５＋ｘ２・ｘ３・ｘ５を表現する図１３に示す二分決定グラフ、図１４に示す零圧縮二分決定グラフ及び図１５に示す簡略化した零圧縮二分決定グラフのこれらの例からわかるように、有向グラフでは論理式の複雑さに応じてグラフ表現が大きくなるのに対して、論理関数ｆ，ｇを表現する無向グラフはそれぞれ、図１３及び図１６に示すものとなり、論理式中の積項又はリテラルの増加量に対してグラフの増大量を低減することがわかる。
【００２１】
図１６の無向グラフにおいては、ｅが双方向性であり、ｘ１〜ｘ５に与えられた値により、ｖ１からｖ２への向きと、ｖ２からｖ１への向きとのいずれの向きの枝にもなり、このような双方向性の枝を用いるため、無向グラフは、有向グラフに比べてサイズを小さくすることができる。
【００２２】
従来の二分決定グラフや零圧縮二分決定グラフを更に小さいものに変換する技術では、節点の併合のような局所的な縮小変換の可能性を形状により判断するが、この判断のための条件は、従来の二分決定グラフや零圧縮二部決定グラフが有向グラフであるために自明に導出され、容易に適用できるものの、論理関数を表現する無向グラフに適用することができない。
【００２３】
ゲートによる論理回路は、ゲートを節点とみなすとともに結線を枝とみなすことによって有向グラフとして表現されるもので、ゲート型組合せ論理回路は、変数が回路入力信号として与えられるとともにその演算結果を出力する回路であり、回路の入出力端子及び内部での信号は、０と１のみを値としてとる論理関数で表現されるため、ゲート型組合せ回路を表現する有向グラフにおいてゲートを節点とみなすとともに入力端子を葉とみなした場合、節点が対応するゲートと入力端子間の部分回路で実現される論理関数が表現されているとみなすことができる。
【００２４】
帰還ループのないゲート型組合せ論理回路を表現する有向グラフを許容関数の概念に基づいて変形しおよび縮小する手法が、上林、室賀らによりトランスダクション法として提案されている。（例えば、非特許文献１０〜１５参照）。
【００２５】
許容関数は０又は１を値としてとる「完全指定論理関数」であり、許容関数集合は０と１に加えてドントケア（＊）をとる不完全指定論理関数として表現されるが、許容関数および許容関数集合の実施上の表現形態が真理値表など如何なるものであれ、トランスダクション法は実施可能な論理最適化手法である。
【００２６】
トランスダクション法は当初、必要とする記憶容量や計算時間の大きさのため、実用的ではないと考えられてきたが、複数の論理関数を少ない記憶容量で表現してそれらの関数の演算を比較的容易に実現することができる共有二分決定グラフが応用されるようになって以来、実用的な論理最適化手法として広く受け入れられるようになったが、これらの
発明はトランスダクション法の実施上の表現形態に関するもので、トランスダクション法そのものの提案とは異なるが、共有二分決定グラフを用いた場合でもグラフ内の変数順序により実施時の速度が大きく変化するため、これらの発明ではより効率的な変数順序決定手法が提案されている。（例えば、特許文献１，２参照）。
【００２７】
ゲート型組合せ論理回路における出力端子を、回路を表現する有向グラフの根とみなすとき、許容関数は、全ての根で表現される論理回路が変わらないように部分グラフが変形可能であるか否かを判定するための概念であり、二分決定グラフや零圧縮二分決定グラフが根で表現される論理関数だけでなく変形対象となる節点で表現される論理関数をも維持することを考慮すると、許容関数は、論理関数を表現するグラフを更に柔軟に変形できる概念であると考えられる。
【００２８】
トランスダクション法は、当初、必要とする記憶容量や計算時間の大きさのため、実用的ではないと考えられてきた。一方、計算機上で複数の論理関数を少ない記憶容量で表現してそれらの関数の演算を比較的容易に実現することができる方法として共有二分決定グラフが考えられた。それにともなって、共有二分決定グラフが計算機上で論理関数を表現するデータ構造となり、それがトランスダクション法のデータ構造に適用されるようになって、以来、トランスダクション法は実用的な論理最適化手法として広く受け入れられるようになった。（例えば、特許文献１，２参照）。これら引用文献はトランスダクション法を計算機上で実施するための方法に関するものである。
【００２９】
許容関数は、０又は１のみを値としてとる完全指定論理関数であるが、許容関数集合は、０と１だけでなくドントケア（＊）も値としてとる不完全指定論理関数で表現され、これら許容関数及び許容関数集合を、回路を表現する有向グラフとは別のデータ構造である二分決定グラフで効率よく表現する手法が提案されているが、これは、回路を表現する有向グラフで論理関数を表現するという概念とは全く異なる（例えば、特許文献２，３参照）
【特許文献１】米国特許明細書第６，２６０，１８５号
【特許文献２】特開平３−２１８５７１号公報
【特許文献３】米国特許明細書第５，４６１，５７４号
【非特許文献１】Kazuo Yano et al, “Top-Down Pass-Transistor Logic Design”, pp.792-803, IEEE Journal of Solid-State Circuits, Vol. 31, No. 6, June, 1996
【非特許文献２】V. Bertacco et al, “Decision Diagrams and Pass transistor Logic Synthesis”, International Workshop on Logic Synthesis, 1997
【非特許文献３】Samuel H. Caldwell, “Switching Circuits and Logical Design”, pp.87-91, John Wiley & Sons, Inc. New York, 1958
【非特許文献４】Samuel H. Caldwell, “Switching Circuits and Logical Design”, pp.236-273, John Wiley & Sons, Inc. New York, 1958
【非特許文献５】Samuel H. Caldwell, “Switching Circuits and Logical Design”, pp.274-318, John Wiley & Sons, Inc. New York, 1958
【非特許文献６】Michael A. Harrison, “Introduction to Switching and Automata Theory”, pp. 408-472, McGraw-Hill Book Company, 1965
【非特許文献７】W. Semon, “Matrix Methods in the Theory of Switching”, International Symposium on the Theory of Switching, pp.13-50, 1959
【非特許文献８】F. E. Horn et al, “Boolean Matrices and the Design of Combinational Relay Switching Circuits”, Bell System Technical Journal, Vol. 34, No. 1, pp.177-202, 1955
【非特許文献９】R. Gould, “The Application of Graph Theory to the Synthesis of Contact Networks”, In the Proceedings of International Symposium on the Theory of Switching, No. 1, pp.244-292, 1959
【非特許文献１０】Saburo Muroga et al, “The Transduction Method…Design of Logic Networks Based on Permissible Functions”, IEEE Transaction on Computers, Vol. 38, No. 10, pp. 1404-1424, Oct., 1989
【非特許文献１１】k. Tanaka, Y. Kambayashi, “Transduction Method for Design of Logic Cell Structure”, PROCEEDING OF THE ASP-DAC 2004, pp.600-603, January 27 - January 30, 2004
【非特許文献１２】H. C. Lai and Y. Kambayashi, ``NOR Network Transduction by Generalized Gate Merging and Substitution Procedures (Principles of NOR Network Transduction Programs NETTRA-G3 and NETTRA-G4),'' Dept. of Computer Science, UIUCDCS-R-75-728, Univ. of Illinois at Urbana-Champaign, 1975.
【非特許文献１３】Y. Kambayashi, H. C. Lai, J. N. Culliney and S. Muroga, ``NOR Network Transduction Based on Error-Compensatio (Principles of NOR Network Transduction Programs NETTRA-E1, NETTRA-E2 and NETTRA-E3),'' Dept. of Computer Science, UIUCDCS-R-75-737,  Univ. of Illinois at Urbana-Champaign, 1975.
【非特許文献１４】Y. Kambayashi and S. Muroga, ``Network Transduction Based on Permissible Functions(General Principles of NOR Network Transduction NETTRA Programs),'' Dept. of Computer Science, UIUCDCS-R-76-804,  Univ. of Illinois at Urbana-Champaign, 1976.
【非特許文献１５】Y. Kambayashi and J. N. Culliney, ``NOR Network Transduction Procedures Based on Connectable and Disconnectable Conditions (Principles of NOR Network Transduction Programs NETTRA-G1 and NETTRA-G2),'' Dept. of Computer Science, UIUCDCS-R-76-841,  Univ. of Illinois at Urbana-Champaign, 1976.
【発明の開示】
【発明が解決しようとする課題】
【００３０】
論理関数を設計するに際し、回路の簡単化及び回路を構成する素子の個数の低減の観点から、論理回路に対応する論理関数を表現する枝数をできるだけ少なくするのが望ましい。既に説明したように、無向グラフを利用することにより、有向グラフよりも少ない記憶量で複雑な論理関数を表現することができる、すなわち、無向グラフは、より少ない枝数及び節点数で論理関数を表現できるので、有向グラフよりも好ましい論理関数表現である。しかしながら、これまで説明した従来の回路設計では、単方向でループがない場合しか考慮していないため、有向グラフを適用することができるものの、無向グラフに設計手法を適用するのが不可能である。その結果、回路の簡単化及び回路を構成する素子の個数の低減を、有向グラフの限界を超えて行うことができない。
【００３１】
本発明の目的は、回路の更なる簡単化及び回路を構成する素子の個数の更なる低減、すなわち、回路の簡単化及び回路を構成する素子の個数の低減を有向グラフの限界を超えて行うことができる論理回路設計装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００３２】
本発明による回路設計装置は、
節点と、両端の節点対とラベルとして割り当てられるリテラルにより特徴付けられる枝から成る、論理関数を表現するグラフを用いて、回路設計を行う回路設計装置であって、
所定の論理関数を表現する無向グラフを構築する手段と、
その無向グラフの各枝及び節点での許容関数集合を取得する手段と、
その許容関数集合に基づいて、前記無向グラフ内に削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合する手段と、
削除可能な枝又は併合可能な節点対が存在しない場合に、前記許容関数集合に基づいて、前記無向グラフ内に追加可能である枝の存在を判断し、追加可能な枝のうち一つを追加する手段と、
追加可能な枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力する手段とを具えることを特徴とする。
【００３３】
本発明による回路設計方法は、
節点と、両端の節点対とラベルとして割り当てられるリテラルにより特徴付けられる枝から成る、論理関数を表現するグラフを用いて、回路設計を行う回路設計方法であって、
所定の論理関数を表現する無向グラフを構築するステップと、
その無向グラフの各枝及び節点での許容関数集合を取得するステップと、
その許容関数集合に基づいて、前記無向グラフ内に削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合するステップと、
削除可能な枝又は併合可能な節点対が存在しない場合に、前記許容関数集合に基づいて、前記無向グラフ内に追加可能である枝の存在を判断し、追加可能な枝のうち一つを追加するステップと、
追加可能な枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力するステップとを具えることを特徴とする。
【００３４】
本発明による回路設計プログラムは、
節点と、両端の節点対とラベルとして割り当てられるリテラルにより特徴付けられる枝から成る、論理関数を表現するグラフを用いて、回路設計を行う回路設計プログラムであって、
所定の論理関数を表現する無向グラフを構築するステップと、
その無向グラフの各枝及び節点での許容関数集合を取得するステップと、
その許容関数集合に基づいて、前記無向グラフ内に削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合するステップと、
削除可能な枝又は併合可能な節点対が存在しない場合に、前記許容関数集合に基づいて、前記無向グラフ内に追加可能である枝の存在を判断し、追加可能な枝のうち一つを追加するステップと、
追加可能な枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力するステップとを具えることを特徴とする。
【発明の効果】
【００３５】
本発明によれば、論理関数を表現するグラフを用いて、回路設計を行うに際し、先ず、所定の論理関数を表現する無向グラフを構築する。次いで、その無向グラフの各枝及び節点での許容関数集合を取得する。次いで、その許容関数集合に基づいて、無向グラフ内に削除可能な枝又は併合可能な節点対が存在するか否かを判断し、削除可能な枝又は併合可能な節点対が存在する場合には、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合する。削除可能な枝又は併合可能な節点対が存在しない場合、許容関数集合に基づいて、無向グラフ内に追加可能なリテラルがラベル付けされた枝が存在するか否かを判断し、追加可能なリテラルがラベル付けされた枝が存在する場合には、追加可能なリテラルがラベル付けされた枝のうちの一つを追加する。追加可能なリテラルがラベル付けされた枝が存在しない場合に、縮小された論理関数を表現する無向グラフを、回路設計で使用するために出力する。
【００３６】
このようにして、許容関数集合に基づいて、削除可能な枝のうちの一つの削除又は併合可能な節点のうちの一対の併合と、追加可能なリテラルがラベル付けされた枝の追加とを行うので、双方向でループがあるグラフについても考慮することができ、したがって、論理関数を表現する無向グラフが、更に少ない節点及び枝で同一の論理関数を表現する無向グラフ、すなわち、縮小された論理関数を表現する無向グラフに変換され、その無向グラフを用いて回路設計ができる。その結果、回路の更なる簡単化及び回路を構成する素子の個数の更なる低減、すなわち、回路の簡単化及び回路を構成する素子の個数の低減を有向グラフの限界を超えて行うことができる。
【００３７】
無向グラフを更に縮小して、回路の更なる簡単化及び回路を構成する素子の個数の更なる低減を促進するために、削除可能な枝のうちの一つを削除し又は併合可能な節点のうちの一対を併合した後、前記無向グラフ内の形状的に冗長な枝又は節点を削除するのが好適である。
【発明を実施するための最良の形態】
【００３８】
本発明による論理回路設計装置、方法及びプログラムの実施の形態を、図面を参照して詳細に説明する。
図１７は、本発明による論理回路設計装置の一実地の形態を有するシステムを示す図であり、図１８は、本発明による論理回路設計方法の一実施の形態のフローチャートである。
【００３９】
図１７において、使用による入力及びハードウェア記述言語によるネットリスト１１や、論理図による入力１２から、与えられた論理関係により、スイッチ型素子によって実現すべき回路の伝達関数が得られ、例えば Contact Network 論理回路自動設計システムによって実現される論理回路設計装置１３が、満たされるべき仕様を考慮するなどによる設計性能の向上と、仕様を満たすための有効性の順に変形対象となる枝や節点対を並べたリストやハッシュテーブルなどを用いて高速化を行いつつ、図１８のフローチャートを実行することによって、スイッチ型素子による具体的な回路が得られる。その結果のデータが、ＦＰＧＡプログラムツール１４及びレイアウトツール１５に送られ、実際のＦＰＧＡ回路１６及びＩＣマスクパターン１７を実現するために用いられる。
【００４０】
本実施の形態における論理回路設計では、先ず、ステップＳ０において、与えられた論理関数ｆを表現する無向グラフを構築し、論理図による入力１２から論理回路設計装置１３に入力される。
【００４１】
ステップＳ０で与えられる無向グラフとして、積和形から各積項を枝の直列接続で表すとともに和を並列接続で表したものや、論理関数ｆを表現する二分決定グラフや零二分決定グラフを簡略化したものを扱うことができるが、零二分決定グラフを用いる場合には、無向化したときに論理関数ｆを表現するグラフでなくなるおそれがあるため、かかるおそれが生じないようにする必要がある。
【００４２】
次いで、ステップＳ１において、各節点又は枝での導通関数及び許容関数集合を計算する。本実施の形態では、無向グラフの二つの端点で論理関数を表現することを意図しており、無向であるために本来はこれらの端点に区別はないが、計算のために、一方を入力端点とするとともに他方を出力端点とし、各節点での導通関数は、入力端点との間のものとして定義する。また、各枝での導通関数は、入力端点からの導通パス上にあるような入力ベクトルに対して値１をとるとともに、それ以外の入力ベクトルに対しては値０をとる関数として定義される。
【００４３】
上記定義に基づいて、回路の入力端点の導通関数を恒真関数とし、その他の節点及び枝の導通関数を恒偽関数とし、節点の導通関数は、それを一方の端としている枝の導通関数の和として計算され、枝の導通関数は、両端にある節点の導通関数の論理和として得られた論理関数及びその枝にラベル付けされたリテラルの論理積を計算することによって得られ、回路内の全ての枝及び節点の導通関数が変化しなくなるまで、導通関数の計算及び更新を繰り返す。
【００４４】
各節点又は枝の許容関数集合を得るためには、その節点又は枝での導通関数の論理否定を計算し、入力端点の導通関数を恒真関数として、該当接点又は枝の導通関数の論理否定を更新することなく出力端点の導通関数ｇを計算し、該当接点又は枝の導通関数の論理否定を行わずに計算した出力端点での導通関数ｆと比較する。各入力ベクトルに対してｆとｇの値が同一である場合、該当節点又は枝での不完全指定論理関数として表される許容関数集合の値を、ドントケア（＊）とし、ｆとｇの値が異なる場合、該当接点又は枝での許容関数集合の値をｆの値と同じにし、全ての入力ベクトルに対して値を得ることによって、該当節点又は枝の許容関数集合を計算する。
【００４５】
ステップＳ２において、許容関数集合が恒偽関数を有する枝の有無を調べ、削除可能な枝を削除する。許容関数集合が恒偽関数を有する枝が存在する場合、ステップＳ５において、そのような枝（複数枝が存在する場合には、そのうちの一つの枝）を削除し、後に説明するステップＳ７に進む。なお、削除すべき枝が複数存在する場合、例えば、回路設計の際に目的関数に矛盾が生じて整合性がなくなる程度が一番高いものを削除する。許容関数集合が恒偽関数を有する枝が存在しない場合、ステップＳ３に進む。
【００４６】
ステップＳ３において、導通関数の和が許容関数集合の共通集合に含まれるような節点対の有無を調べ、併合可能な節点対を併合する。導通関数の和が許容関数集合の共通集合に含まれるような節点対が存在する場合、ステップＳ６において、そのような節点対（複数の節点対が存在する場合には、そのうちの一つの節点対）を併合して、ステップＳ７に進む。なお、同一の節点対間で同一リテラルを有する枝が複数ある場合には、許容関数集合を用いて判定するまでもなくそのような枝のうちの一つを残して全てが削除可能であるため、許容関数集合を用いて併合可能な節点対が複数発見された場合には、それらのうちの同一のリテラルを有する枝が接続されている節点対を優先的に併合する。導通関数の和が許容関数集合の共通集合に含まれるような節点対が存在しない場合には、ステップＳ４に進む。
【００４７】
ステップＳ５又はＳ６後のステップＳ７において、枝の削除又は節点対の併合の結果として、行き止まりになる枝や、接続されている枝が存在しない節点のように形状的に明らかに冗長になるものを削除し、ステップＳ１に戻る。
【００４８】
ステップＳ４において、今までグラフ中で枝が設けられたことがないような一つのリテラル及び一つの節点対を選択し、その節点対の両方の節点のそれぞれについて、リテラルが０であるような入力ベクトルに対して、値をドントケア（＊）をとり、その他のベクトルに対しては、許容関数集合と同一の値をとるような枝追加用関数集合を計算し、該当節点の両方の枝追加用関数集合の共通集合に両節点の導通関数の和が含まれるか否か、すなわち、許容関数に基づき無向グラフ内に追加可能なリテラル又はラベル付けされた枝が存在するか否かを判断する。該当節点の両方の枝追加用関数集合の共通集合に両節点の導通関数の和が含まれる場合、枝追加が可能であると判断して、ステップＳ８において、そのような枝（複数存在する場合には、そのうちの一つ）を追加して、ステップＳ１に戻る。該当節点の両方の枝追加用関数集合の共通集合に両節点の導通関数の和が含まれない場合、ステップＳ９において、論理回路設計装置１３は、凝縮された論理関数ｆを表現する無向グラフをＦＰＧＡプログラムツール１４又はレイアウトツール１５に出力する。
【００４９】
本実施の形態によれば、無向グラフを用いることによって、論理関数を表現するために必要最小限又はそれに近い大きさのグラフを得ることができるようになる。そのようなグラフは、人手による導出が困難な形状である場合もあるが、本実施の形態では自動的に導出することができ、その結果、本発明を、縮小された無向グラフから２端子間スイッチ回路の設計に適用することができる。
【００５０】
ここで、本発明の固有の効果を示すために、図１９に示す論理関数ｆを表現するグラフを導出し、図１８に示すアルゴリズムを用いて、論理関数ｆを必要最小限又はそれに近い大きさに凝縮する。
【００５１】
ステップＳ０（図１８）において、図１９に示す積和形から各々の積項を枝の直列接続で表現して、積項の和を枝の直列接続を並列接続することで実現することができ、図２０に示すグラフを得ることができる。
【００５２】
変形対象節点対を強調するために、図２０のグラフを、図２１に示すように書き改め、図２１に示すグラフのうちの二つの節点をｖ２，ｖ９とすると、ステップＳ１（図１８）において、図２２の真理値表で示されるような導通関数ｆｖ２，ｆｖ９が得られ、これらの論理否定をとったと仮定したときのグラフが表現する導通関数ｇｖ２，ｇｖ９を計算することによって、許容関数集合Ｇｖ２，Ｇｖ９が得られる。
【００５３】
図２２に示す許容関数集合及び導通関数の真理表とからわかるように、図２１のグラフ中の節点ｖ２，ｖ９はそれぞれ、ステップＳ３（図１８）で見つかる複数の併合可能な節点対のうちの一つであるため、ステップＳ６（図１８）に進んでｖ２とｖ９とを併合し、その結果、図２３に示すようなグラフが得られる。
【００５４】
節点ｖ２と節点ｖ１７とは、図２４に示す許容関数集合及び導通関数の真理表とから併合可能であることがわかるので、図２３のグラフ中の節点ｖ２と節点ｖ１７とも同様に併合すると、図２５に示すグラフが得られる。節点ｖ２とグラフ最下部との間には、ｘ２の論理否定であるリテラルがラベル付けされた枝が複数存在するため、これらのうちの一つを除いては形状的に明らかに冗長であると判断でき、ステップＳ７（図１８）で削除される。その結果、図２６に示すグラフが得られる。
【００５５】
同様にして図１８のステップＳ１〜Ｓ３及びＳ５〜Ｓ７を繰返し適用することによって、図２７に示すグラフまで短縮される。
【００５６】
図２７のグラフに対するステップＳ２及びＳ３の適用結果がＮｏであるため、図２７のグラフのステップＳ４に進み、図２７のグラフ中の節点ｖ２，ｖ１とｘ２の論理否定は、図２８に示すように、枝を追加するための条件を満たす節点対とリテラルの組の一つであるため、図１８のステップＳ８で枝を追加してステップＳ１に戻る。ステップＳ１で再度グラフ内の各枝及び節点での導通関数及び許容関数集合を計算すると、ステップＳ２において、図２９に示すように、節点ｖ７と節点ｖ１１の間の枝ｅ７，１１での許容関数集合が恒偽関数を含んでいるために削除可能と判断されるため、ステップＳ５で削除され、その結果、図３０のグラフが得られる。
【００５７】
図３０のグラフにおいて、節点ｖ７と節点ｖ１５がステップＳ３で併合可能と判断されるものの１対であるためにステップＳ６で併合される。併合の結果、節点ｖ７と節点ｖ１５の間にあった枝が、同一節点を両端に持つようになり、形状的に明らかに冗長であるので、ステップＳ７で削除され、図３１のグラフが得られる。
【００５８】
図３１のグラフにおいて、節点ｖ３と最上部の節点の間にあるｘ３の論理否定がラベル付けされた枝は、ステップＳ４で追加可能と判断される枝の一つであるため、ステップＳ８で追加を行い、再度Ｓ１に戻る。ステップＳ１で導通関数と許容関数集合の計算を行うと、節点ｖ３と最上部の節点との間にあるｘ１の論理否定がラベル付けされた枝と、節点ｖ１１と最上部の節点との間にある枝とが、許容関数集合に基づいて削除され、節点ｖ１１と、節ｖ２と節ｖ１１の間の枝は、形状的に明らかに冗長であるので削除され、図３２のグラフが得られる。
【００５９】
図３２のグラフにおいて、節点ｖ２と節点ｖ７との間に、ｘ２の論理否定がラベル付けされた枝の追加が行われ、図３３のグラフが得られる。図３３のグラフの形を整えると、図３４のグラフが得られ、枝数が１１まで削減された。
【００６０】
図１９の論理関数を表現するグラフとしては、図３５に示す枝数１２のグラフが最小であるとほぼ半世紀に亘って考えられてきたが、本発明の手法による縮小で得られた図３４のグラフは、図３５のグラフより枝数が少なく、本発明の手法の結果として得られたグラフから、更に少ない素子数でのスイッチ型回路の設計が可能であるという効果を示している。
【００６１】
また、図３４のグラフにおける節点ｖ３と節点ｖ４の間の枝は、いかなる節点及び枝の配置を行ったとしても、最上部及び最下部の端点の外側を通さない限り他の枝と交差することになるため、非平面グラフである。このような非平面グラフの導出が困難であることが知られており、本発明の手法が、導出困難な小さいグラフに縮小されるという効果を有することを示す。
【００６２】
図１９の論理関数を表現する二分決定グラフを簡略化したものが、図３６に示すグラフである。このグラフの枝数は１４であり、本発明の手法により導出された図３４のグラフよりも多くの枝で構成されており、本発明の方が有利であることを示している。
【００６３】
図１９の論理関数を表現する零圧縮二分決定グラフを簡略化したものが、図３７に示すグラフである。このグラフの枝数は１５であり、本発明の手法により導出された図３４のグラフよりも多くの枝で構成されるだけでなく、有向グラフであるものを無向した結果、図３８のグラフにおいて太線で示すように、目的の導通関数を実現する場合に端点間に存在してはならない導通路で、存在してしまうと回路をその目的の導通関数を実現しないようにしてしまう同通路であるスニーク・パスが生じる。その結果、図３８に示すような無向化されたグラフは、目的とする図１９の論理関数を表現していない。それに対して、本発明では、そのようなスニーク・パスが生じるおそれがなく、目的とする論理関数を正確に表現する。
【００６４】
図１９の論理関数は、対称関数という特別な性質を有する関数であるため、独特のグラフ構成法があり、その手法を用いて得られるグラフを図３９に示す。このグラフの枝数は１７であり、本発明の手法により導出された図３４のグラフよりも多くの枝で構成され、本発明は、特殊な性質を有する論理関数に対しても、枝数の低減を行うことができることを示している。
【００６５】
図３９のグラフは、図４０のグラフに縮小可能であるが、この場合、枝数は依然として１４であり、本発明の手法による結果よりも多くの枝数を必要としており、本発明が枝数削減効果を有することを示す。
【００６６】
図４１は、５個以上の変数に対する論理関数を表現するグラフの作成実験の結果を示す表である。図４１において、初期グラフは、直並列形で作成した結果を直並列欄に示し、その直列接続において様々な変数順序で初期グラフを作り、図１８のアルゴリズムで縮小し、その平均を、「本発明」の欄に示し、比較対称として、二分決定グラフや零圧縮二分決定グラフより形状制約が少ない木状グラフの作成結果を「木」の欄に示す。この結果から、直並列グラフを約４０％削減し、木に比べて約２５％少ない枝数で目的の論理関数を表現するグラフを作成できるという、本発明の効果を示すことができる。
【００６７】
本発明は、上記実施の形態に限定されるものではなく、幾多の変更及び変形が可能である。
例えば、上記実施の形態において、削除可能な枝の削除と併合可能な節点対の併合の両方を行った場合について説明したが、削除可能な枝の削除と併合可能な節点対の併合のうちのいずれか一方を行ってもよい。また、形状的に明らかに冗長な枝や節点の削除を省略してもよい。
【図面の簡単な説明】
【００６８】
【図１】格子状のトランジスタ網で実現するＰＬＡの一例の回路図である。
【図２】論理関数の真理値表の表現から直接合成が容易なメモリ及びマルチプレクサの回路図である。
【図３】二分決定グラフの一例を示す図である。
【図４】二分決定グラフの一つの節点及び二つの枝からなる１基本構成単位と、最下部に描かれる葉とを示す図である。
【図５】１制御入力のマルチプレクサで実現したグラフ中の各節点及びその２本の出力枝の組を示す図である。
【図６】図５の１制御入力のマルチプレクサと同様な動作を行うリレー・コンタクト回路を示す図である。
【図７】図５，６の回路図を簡単に表記した図である。
【図８】図３の二分決定グラフを図７の回路表記を用いて簡略に示した図である。
【図９】図８に示すグラフにおいて、０に直接接続される枝を削除して得られた有向グラフを示す図である。
【図１０】論理関数の積和形ｆ＝ｘ１・ｘ２＋ｘ３・ｘ４を表現する零圧縮二分決定グラフの一例を示す図である。
【図１１】二分決定グラフにおいて一つの節点及び二つの枝からなる１基本構成単位の簡単な表記を示す図である。
【図１２】図１０のグラフを簡略化した論理関数ｆを表現する有向グラフを示す図である。
【図１３】論理関数ｇ＝ｘ１・ｘ２＋ｘ３・ｘ４＋ｘ１・ｘ４・ｘ５＋ｘ２・ｘ３・ｘ５を表現する二分決定グラフを示す図である。
【図１４】論理関数ｇを表現する零圧縮二分決定グラフを示す図である。
【図１５】零圧縮二分決定グラフを簡略化した論理関数ｇを表現する有向グラフを示す図である。
【図１６】論理関数ｇを表現した、少ない枝数の無向グラフを示す図である。
【図１７】本発明による論理回路設計装置の一実地の形態を有するシステムを示す図である。
【図１８】本発明による論理回路設計方法の一実施の形態のフローチャートである。
【図１９】本発明の効果を示すためのグラフによる表現目標の論理関数を示す図である。
【図２０】図１９の積和形からのグラフ表現を示す図である。
【図２１】変形対象節点対が強調された図２０と等価のグラフを示す図である。
【図２２】図１９における節点ｖ２と節点ｖ９が併合可能であることを示す許容関数集合と導通関数の真理値表を示す図である。
【図２３】図２１における節点ｖ２と節点ｖ９とを併合した後のグラフを示す図である。
【図２４】図２３における節点ｖ２と節点ｖ１７が併合可能であることを示す許容関数集合と導通関数の真理値表を示す図である。
【図２５】図２３における節点ｖ２と節点ｖ１７とを併合した後のグラフを示す図である。
【図２６】図２５のグラフにおいて明らかに冗長な節点ｖ２と最下部の節点との間にあるｘ２の論理否定がラベル付けされた枝を削除した後のグラフを示す図である。
【図２７】図１８におけるステップＳ１〜Ｓ３及びＳ５〜Ｓ７のみを繰返し適用し、ステップＳ４に至る直前のグラフを示す。
【図２８】図２７のグラフにおいて節点ｖ２と節点ｖ１の間にｘ２の倫理否定がラベル付けされた枝を追加可能であることを示す許容関数集合と導通関数の真理値表を示す図である。
【図２９】図２７のグラフにおいて節点ｖ２と節点ｖ１の間にｘ２の倫理否定がラベル付けされた枝を追加した後、節点ｖ７と節点ｖ１１の間の枝ｅ７，１１が削除可能であることを示す許容関数集合の真理値表を示す図である。
【図３０】図２７のグラフにおいて節点ｖ２と節点ｖ７の間に枝を追加し、節点ｖ７と節点ｖ１１の間の枝ｅ７，１１を削除した後のグラフを示す図である。
【図３１】図３０のグラフで節点ｖ７と節点ｖ１５を併合し、形状的に明らかに冗長になった節点ｖ７と節点ｖ１５の間にあった枝を削除したグラフを示す図である。
【図３２】図３１のグラフにおいて、最上部の節点と節点ｖ３の間の枝と、最上部の節点と節点ｖ１１の間の枝とを許容関数集合に基づいて削除し、形状的に明らかに冗長になった節点ｖ７及び節点ｖ７と節点ｖ２の間の枝を削除した後のグラフを示す図である。
【図３３】図３２のグラフにおいて、節点ｖ２と節点ｖ７の間に、ｘ２の論理否定がラベル付けされた枝を追加した後に節点ｖ２と最下部の節点の間の枝を削除した結果として得られたグラフを示す図である。
【図３４】図３３のグラフの形を整えたグラフを示す図である。
【図３５】図１９の論理関数を表現する無向グラフとして最小であると考えられてきたグラフを示す図である。
【図３６】図１９の論理関数を表現する二分決定グラフを簡略化して得られたグラフを示す図である。
【図３７】図１９の論理関数を表現する零圧縮二分決定グラフを簡略化して得られたグラフを示す図である。
【図３８】有向グラフである零圧縮二分決定グラフを無向化することによるグラフが表現する論理関数の変化を示すスニーク・パスを示す図である。
【図３９】対称関数を表現するグラフ合成手法により得られる図１９の論理関数を表現するグラフを示す図である。
【図４０】図３９のグラフを縮小して得られたグラフを示す図である。
【図４１】５個以上の変数に対する論理関数を表現するグラフの作成実験の結果を示す表である。
【符号の説明】
【００６９】
１  積項生成部
２  論理和生成部
３  メモリ
４  マルチプレクサ
５  節点
６  ０枝
７  １枝
８  ０終端節点
９  １終端節点
１１  仕様による入力及びハードウェア記述言語によるネットリスト
１２  論理図による入力
１３  論理回路設計装置
１４  ＦＰＧＡプログラムツール
１５  レイアウトツール
１６  ＦＰＧＡ回路
１７  ＩＣマスクパターン
【図１】
2006059022.tif 000003
【図２】
2006059022.tif 000004
【図３】
2006059022.tif 000005
【図４】
2006059022.tif 000006
【図５】
2006059022.tif 000007
【図６】
2006059022.tif 000008
【図７】
2006059022.tif 000009
【図８】
2006059022.tif 000010
【図９】
2006059022.tif 000011
【図１０】
2006059022.tif 000012
【図１１】
2006059022.tif 000013
【図１２】
2006059022.tif 000014
【図１３】
2006059022.tif 000015
【図１４】
2006059022.tif 000016
【図１５】
2006059022.tif 000017
【図１６】
2006059022.tif 000018
【図１７】
2006059022.tif 000019
【図１８】
2006059022.tif 000020
【図１９】
2006059022.tif 000021
【図２０】
2006059022.tif 000022
【図２１】
2006059022.tif 000023
【図２２】
2006059022.tif 000024
【図２３】
2006059022.tif 000025
【図２４】
2006059022.tif 000026
【図２５】
2006059022.tif 000027
【図２６】
2006059022.tif 000028
【図２７】
2006059022.tif 000029
【図２８】
2006059022.tif 000030
【図２９】
2006059022.tif 000031
【図３０】
2006059022.tif 000032
【図３１】
2006059022.tif 000033
【図３２】
2006059022.tif 000034
【図３３】
2006059022.tif 000035
【図３４】
2006059022.tif 000036
【図３５】
2006059022.tif 000037
【図３６】
2006059022.tif 000038
【図３７】
2006059022.tif 000039
【図３８】
2006059022.tif 000040
【図３９】
2006059022.tif 000041
【図４０】
2006059022.tif 000042
【図４１】
2006059022.tif 000043