JPH04264979A - ２分決定グラフの変数順決定方式 - Google Patents
２分決定グラフの変数順決定方式Info
- Publication number
- JPH04264979A JPH04264979A JP3026388A JP2638891A JPH04264979A JP H04264979 A JPH04264979 A JP H04264979A JP 3026388 A JP3026388 A JP 3026388A JP 2638891 A JP2638891 A JP 2638891A JP H04264979 A JPH04264979 A JP H04264979A
- Authority
- JP
- Japan
- Prior art keywords
- variable
- order
- variables
- binary decision
- decision graph
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Test And Diagnosis Of Digital Computers (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は論理関数の表現手段の１
つとしての２分決定グラフに係り、さらに詳しくは２段
論理回路の論理関数を表現する２分決定グラフの作成時
における変数順決定方式に関する。
つとしての２分決定グラフに係り、さらに詳しくは２段
論理回路の論理関数を表現する２分決定グラフの作成時
における変数順決定方式に関する。
【０００２】
【従来の技術】論理関数を計算機上で効率よく表現する
ことは、各種の論理設計支援技術、例えば論理照合、論
理検証、論理回路簡単化、テスト回路生成などの応用に
おいて極めて重要である。また論理照合や論理回路の簡
単化は論理設計支援技術の中心をなすものである。
ことは、各種の論理設計支援技術、例えば論理照合、論
理検証、論理回路簡単化、テスト回路生成などの応用に
おいて極めて重要である。また論理照合や論理回路の簡
単化は論理設計支援技術の中心をなすものである。
【０００３】計算機での論理関数の表現法としては真理
値表、積和形論理式、２分決定グラフなどがある。この
うち２分決定グラフは、その作成時に良い変数順を与え
ることができれば、大きな論理関数を表現することがで
きる。２分決定グラフは、決定木において場合分けする
変数順を全てのパスで固定することにより、サブグラフ
を共有する（もとは木であるが共有することでグラフと
なる）ことでコンパクトに論理関数を表現するとともに
、正規形となる、すなわちもとの論理が同じであれば、
２分決定グラフに変換した結果は同一になるようにした
論理関数の表現手法である。
値表、積和形論理式、２分決定グラフなどがある。この
うち２分決定グラフは、その作成時に良い変数順を与え
ることができれば、大きな論理関数を表現することがで
きる。２分決定グラフは、決定木において場合分けする
変数順を全てのパスで固定することにより、サブグラフ
を共有する（もとは木であるが共有することでグラフと
なる）ことでコンパクトに論理関数を表現するとともに
、正規形となる、すなわちもとの論理が同じであれば、
２分決定グラフに変換した結果は同一になるようにした
論理関数の表現手法である。
【０００４】図１４は２分決定グラフの例である。同図
は論理関数Ｘ１ ・Ｘ２ ＋ 外１ （
は論理関数Ｘ１ ・Ｘ２ ＋ 外１ （
【０００５
】
】
【外１】
【０００６】外２ はＸ３ の否定）を表現している
。図中○印はノードであり、これは各変
。図中○印はノードであり、これは各変
【０００７】
【外２】
【０００８】数に対応し、■はＸ１ に対応する。また
□は論理関数値に対応し、□の中に１が記入されている
場合には論理関数値が１であるこを表わす。例えばＸ１
が０の場合には０という記号のついたエッジがたどら
れ、１の場合には１という記号のついたエッジがたどら
れる。そして例えば最終的に中に０が記入された□にた
どりついた場合には、その論理関数値は０となる。場合
分けの変数順が各パスで固定されており、グラフを共有
することができ、結果的にコンパクトに論理関数を表現
できる。すなわち図１４で変数Ｘ３ に対するノードは
２つのエッジによって指されており、共有されている。
□は論理関数値に対応し、□の中に１が記入されている
場合には論理関数値が１であるこを表わす。例えばＸ１
が０の場合には０という記号のついたエッジがたどら
れ、１の場合には１という記号のついたエッジがたどら
れる。そして例えば最終的に中に０が記入された□にた
どりついた場合には、その論理関数値は０となる。場合
分けの変数順が各パスで固定されており、グラフを共有
することができ、結果的にコンパクトに論理関数を表現
できる。すなわち図１４で変数Ｘ３ に対するノードは
２つのエッジによって指されており、共有されている。
【０００９】
【発明が解決しようとする課題】図１４に示したような
２分決定グラフを用いると、実用的な論理関数をコンパ
クトに表現できるという長所がある反面、場合分けに使
用する変数の順序によってグラフの大きさが大きく変化
するという問題点がある。この問題点を図１５および図
１６を用いて説明する。
２分決定グラフを用いると、実用的な論理関数をコンパ
クトに表現できるという長所がある反面、場合分けに使
用する変数の順序によってグラフの大きさが大きく変化
するという問題点がある。この問題点を図１５および図
１６を用いて説明する。
【００１０】図１５および図１６は、共に同じ論理関数
Ｘ１ ・Ｘ２ ＋Ｘ３ ・Ｘ４ ＋Ｘ５ ・Ｘ６ を表
わしている。 しかしながら、図１５のように２分決定グラフを作成す
るための場合分けの変数順をＸ１ ，Ｘ２ ，Ｘ３ ，
Ｘ４ ，Ｘ５ ，Ｘ６ とすると、その順序は最適順と
なり、２分決定グラフはコンパクトなものになる。これ
に対して、変数順をＸ１ ，Ｘ３ ，Ｘ５ ，Ｘ２ ，
Ｘ４ ，Ｘ６ とすると、２分決定グラフは図１６に示
すようにかなり大きなものとなる。
Ｘ１ ・Ｘ２ ＋Ｘ３ ・Ｘ４ ＋Ｘ５ ・Ｘ６ を表
わしている。 しかしながら、図１５のように２分決定グラフを作成す
るための場合分けの変数順をＸ１ ，Ｘ２ ，Ｘ３ ，
Ｘ４ ，Ｘ５ ，Ｘ６ とすると、その順序は最適順と
なり、２分決定グラフはコンパクトなものになる。これ
に対して、変数順をＸ１ ，Ｘ３ ，Ｘ５ ，Ｘ２ ，
Ｘ４ ，Ｘ６ とすると、２分決定グラフは図１６に示
すようにかなり大きなものとなる。
【００１１】このため２分決定グラフの作成時には場合
分けのための変数順の決定が重要となるが、変数の多い
２分決定グラフでは最適変数順序は発見的手法によって
決定する必要がある。多段回路の場合には、従来回路の
構造から比較的よい変数順を決定する手法も開発されて
いるが、２段回路の場合には必ずしもよい結果が得られ
ないという問題点があった。
分けのための変数順の決定が重要となるが、変数の多い
２分決定グラフでは最適変数順序は発見的手法によって
決定する必要がある。多段回路の場合には、従来回路の
構造から比較的よい変数順を決定する手法も開発されて
いるが、２段回路の場合には必ずしもよい結果が得られ
ないという問題点があった。
【００１２】本発明は２段論理回路を表現する２分決定
グラフの作成時における最適変数順の決定方式を提供す
ることを目的とする。
グラフの作成時における最適変数順の決定方式を提供す
ることを目的とする。
【００１３】
【課題を解決するための手段及び作用】図１は本発明の
機能ブロック図である。同図は２段論理回路の論理関数
を表現する２分決定グラフの作成時における変数順決定
方式の機能ブロック図である。
機能ブロック図である。同図は２段論理回路の論理関数
を表現する２分決定グラフの作成時における変数順決定
方式の機能ブロック図である。
【００１４】図１において、まず１で２段論理回路の論
理関数を表わす論理式が積和形式に展開されて、簡単化
される。そして２で、その論理式に表われる各変数が肯
定もしくは否定の形式で用いられている積項数がそれぞ
れ調べられ、３でその積項数が多い順序に従って２分決
定グラフ作成時における変数順が決定される。
理関数を表わす論理式が積和形式に展開されて、簡単化
される。そして２で、その論理式に表われる各変数が肯
定もしくは否定の形式で用いられている積項数がそれぞ
れ調べられ、３でその積項数が多い順序に従って２分決
定グラフ作成時における変数順が決定される。
【００１５】本発明においては、例えばカバーと呼ばれ
るパターンによって２段論理回路の論理式が表現される
。カバーは変数の数と同じ列数と、積和形論理式の積項
数と同じ行数とを持つ行列形式のパターンである。その
パターンの各要素の値は、その変数がその積項に肯定と
して表われる時には例えば‘１’、否定で表われる時に
は‘０’、全く表われない時には‘─’とされる。そし
て各列毎に０と１の数を数えることにより、その数が多
い変数順が２分決定グラフの変数順とされる。
るパターンによって２段論理回路の論理式が表現される
。カバーは変数の数と同じ列数と、積和形論理式の積項
数と同じ行数とを持つ行列形式のパターンである。その
パターンの各要素の値は、その変数がその積項に肯定と
して表われる時には例えば‘１’、否定で表われる時に
は‘０’、全く表われない時には‘─’とされる。そし
て各列毎に０と１の数を数えることにより、その数が多
い変数順が２分決定グラフの変数順とされる。
【００１６】以上によって、２段論理回路の論理関数を
表現する２分決定グラフの大きさを小さくすることが可
能となる。
表現する２分決定グラフの大きさを小さくすることが可
能となる。
【００１７】
【実施例】図２は２段論理式を表現するパターンとして
のカバーの実施例である。同図はＸ３ ・Ｘ４ ＋Ｘ２
・Ｘ３ ・外３ ＋Ｘ１ ・Ｘ４ という積和型論
理式に
のカバーの実施例である。同図はＸ３ ・Ｘ４ ＋Ｘ２
・Ｘ３ ・外３ ＋Ｘ１ ・Ｘ４ という積和型論
理式に
【００１８】
【外３】
【００１９】対するカバーを示している。このカバーの
各列は左側から変数Ｘ１ ，Ｘ２ ，Ｘ３ およびＸ４
に対応しており、また各行は上から積項Ｘ３ ・Ｘ４
，Ｘ２ ・Ｘ３ ・外４ およびＸ１ ・Ｘ４ に
対応している。そしてこのカバー内の各値は、その変
各列は左側から変数Ｘ１ ，Ｘ２ ，Ｘ３ およびＸ４
に対応しており、また各行は上から積項Ｘ３ ・Ｘ４
，Ｘ２ ・Ｘ３ ・外４ およびＸ１ ・Ｘ４ に
対応している。そしてこのカバー内の各値は、その変
【００２０】
【外４】
【００２１】数がその積項に肯定として表われる時には
‘１’、否定として表われる時には‘０’、表われない
時には‘─’となっている。図２のようなカバーに対し
て、変数を表わす各列毎に０と１の数が数えられ、その
数が多い変数順が２分決定グラフの変数順とされる。図
２においてはＸ４ に対する０と１の数が３で最も多く
、次がＸ３ に対するもので、Ｘ１ とＸ２ に対する
数は共に１である。同じ数となったＸ１ とＸ２ の順
の決定方式については後述することとし、ここでは変数
順としてＸ４ ，Ｘ３ ，Ｘ２ ，Ｘ１ とする。
‘１’、否定として表われる時には‘０’、表われない
時には‘─’となっている。図２のようなカバーに対し
て、変数を表わす各列毎に０と１の数が数えられ、その
数が多い変数順が２分決定グラフの変数順とされる。図
２においてはＸ４ に対する０と１の数が３で最も多く
、次がＸ３ に対するもので、Ｘ１ とＸ２ に対する
数は共に１である。同じ数となったＸ１ とＸ２ の順
の決定方式については後述することとし、ここでは変数
順としてＸ４ ，Ｘ３ ，Ｘ２ ，Ｘ１ とする。
【００２２】この変数順を用いた２分決定グラフの実施
例が図３である。これに対して、元の変数順Ｘ１ ，Ｘ
２ ，Ｘ３ ，Ｘ４ の順序で２分決定グラフを作ると
図４となる。図３では２分決定グラフのノード数は７で
あるのに対して、図４では９となっており、図４の方が
２分決定グラフのサイズが大きくなってしまう。
例が図３である。これに対して、元の変数順Ｘ１ ，Ｘ
２ ，Ｘ３ ，Ｘ４ の順序で２分決定グラフを作ると
図４となる。図３では２分決定グラフのノード数は７で
あるのに対して、図４では９となっており、図４の方が
２分決定グラフのサイズが大きくなってしまう。
【００２３】図５は本発明における変数順決定処理実施
例のフローチャートである。同図において、まずステッ
プ（Ｓ）１０において与えられた論理式が積和型論理式
に展開され、Ｓ１１で例えば積和型論理式簡単化プログ
ラムで簡単化され、カバー表現に直され、Ｓ１２で各変
数毎にカバー表現中で０と１の数が多い順に変数が並べ
られて、処理が終了する。
例のフローチャートである。同図において、まずステッ
プ（Ｓ）１０において与えられた論理式が積和型論理式
に展開され、Ｓ１１で例えば積和型論理式簡単化プログ
ラムで簡単化され、カバー表現に直され、Ｓ１２で各変
数毎にカバー表現中で０と１の数が多い順に変数が並べ
られて、処理が終了する。
【００２４】図６はカバー中で０と１の数が同一の変数
に対する変数順決定処理の概略フローチャートである。 同図において、Ｓ１６で論理式の積と和がそれぞれアン
ドゲート、オアゲートとみなされて回路表現が作られ、
Ｓ１７で作られた回路の出力側から順次深さ優先に入力
側に回路がたどられ、Ｓ１８で回路をたどった際に見つ
けられた入力変数の順が２分決定グラフの変数順として
決定される。
に対する変数順決定処理の概略フローチャートである。 同図において、Ｓ１６で論理式の積と和がそれぞれアン
ドゲート、オアゲートとみなされて回路表現が作られ、
Ｓ１７で作られた回路の出力側から順次深さ優先に入力
側に回路がたどられ、Ｓ１８で回路をたどった際に見つ
けられた入力変数の順が２分決定グラフの変数順として
決定される。
【００２５】図７および図８は、カバー中で０と１の数
が同一の変数に対する変数順決定処理の詳細フローチャ
ートである。同図を図９の論理回路例を用いて詳細に説
明する。なお図９において、論理回路の各部分の信号に
はラベルＮ１からＮ９ が付けられ、入力変数に対応す
る入力信号はラベルＮ１ 〜Ｎ４ が付けられている。
が同一の変数に対する変数順決定処理の詳細フローチャ
ートである。同図を図９の論理回路例を用いて詳細に説
明する。なお図９において、論理回路の各部分の信号に
はラベルＮ１からＮ９ が付けられ、入力変数に対応す
る入力信号はラベルＮ１ 〜Ｎ４ が付けられている。
【００２６】図７において、Ｓ２１はＮの値を選んで論
理回路の出力に該当するラベルの処理を行うことに対応
し、Ｓ２２はラベルＮについてのグラフを作成するプロ
シジャＭＡＫＥＯＲＤＥＲ（Ｎ）なるプログラムを呼ぶ
ことに対応している。
理回路の出力に該当するラベルの処理を行うことに対応
し、Ｓ２２はラベルＮについてのグラフを作成するプロ
シジャＭＡＫＥＯＲＤＥＲ（Ｎ）なるプログラムを呼ぶ
ことに対応している。
【００２７】図８において、Ｓ２３はラベルＮについて
のグラフを作成するプログラムが呼ばれた状態を表わし
ている。以下、２分決定グラフ作成時における入力変数
に対する順序が決定される状況を説明する。 （１） 図８のＳ２３において、図９のラベルＮ９ の
所についてのグラフ作成に入る。 （２） Ｓ２４において、ラベルＮ９ についての処理
が先に行われたか否かが調べられる。 （３） 今の場合には先に処理がなされてはいないので
、Ｓ２５において、ラベルＮ９ に出力しているオアゲ
ートについての入力Ｎ７ ，Ｎ８ とを把握する。 （４） 今の場合、入力としてＮ７ 、Ｎ８ とが存在
することから、空集合（すなわち入力がない）ではなく
、Ｓ２６からＳ２７に向かう。 （５） Ｓ２７において入力の一方のＮ７ を取り出し
、１−Ｎ７ とする。 （６） Ｓ２８においてＮ７ が入力変数に直接接続さ
れているか否かを調べる。 （７） Ｎ７ の場合にはＮＯであり、Ｓ２９に進み、
ラベルＮ７ についてのグラフを作成する処理に入る。 Ｓ２９の処理を行うことは、Ｓ２３におけるＮとしてＮ
７ を設定したことに対応し、Ｎ＝１−Ｎ７ としてＳ
２４に進む。 （８） 今の場合にはＳ２５に進み、ラベルＮ７ に出
力を出しているアンドゲートについての入力Ｎ５ とＮ
３ とを把握する。 （９） Ｓ２６，２７をへて入力の一方Ｎ５ を取り出
し、１−Ｎ５ とする。 （１０） Ｓ２８においてＮ５ が入力変数に直接接
続されているか否かを調べる。 （１１） Ｎ５ の場合にはＮＯであり、Ｓ２９に進
み、ラベルＮ５ についてのグラフを作成する処理に入
る。Ｓ２９の処理を行うことは、Ｓ２３におけるＮとし
てＮ５ を設定したことに対応し、Ｎ＝１−Ｎ５ とて
Ｓ２４に進む。 （１２） 今の場合にはラベルＮ５ についてマーク
がないことから、Ｓ２５に進み、ラベルＮ５ に出力し
ているオアゲートについての入力Ｎ１ とＮ２ とを把
握する。 （１３） Ｓ２６，２７をへて入力の一方のＮ１ を
取り出し、１＝Ｎ１ とする。 （１４） Ｓ２８においてＮ１ が入力変数に直接接
続されていることが調べられ、Ｓ３０に進む。 （１５） Ｓ３０において、今の場合には１＝Ｎ１
であるＮ１ が、例えばＮ３ の場合のように２個以上
のゲートの入力に接続されていないことから、Ｓ３２に
進む。 （１６） Ｓ３２において、ＦＡＮＯＵＴ１ＬＩＳＴ
なるキューの末尾に、Ｎ１ を付加する（今の場合１＝
Ｎ１ である）。 （１７） 次いでＳ２６に戻り、Ｓ２７において、他
方の入力Ｎ２ を選び、１＝Ｎ２ とする。 （１８） Ｓ２８において、Ｎ２ が入力変数に直接
接続されていることから、Ｓ３０に進み、Ｓ３２に進む
。 （１９） Ｓ３２において、上記ＦＡＮＯＵＴ１ＬＩ
ＳＴなるキューの末尾に、Ｎ２ を付加する（上記Ｎ１
の次にＮ２ を付加する）。 （２０） 次にＳ２６に戻るが、空集合になったので
（Ｎ１ とＮ２ とが処理された）、Ｓ３３に進む。 （２１） 今の場合にはＦＡＮＯＵＴ２ＵＰなるキュ
ー（後述する）に値がセットされていないので、Ｓ３４
に進み、ラベルＮ５ に対応してマークをつけ、上記保
留にしておいたラベル３ についての処理に入る。 （２２） 上述と同様にＳ２３〜２７をへてＳ２８に
進むが、ラベルＮ３ の場合にはＹＥＳであり、Ｓ３０
に進む。 （２３） そして、ラベルＮ３ の場合には、Ｓ３０
においてＹＥＳであり（ラベルＮ３ が２つのゲートの
入力となっている）、Ｓ３１に進む。 （２４） Ｓ３１において、ＦＡＮＯＵＴ２ＵＰなる
キューにＮ３ を記録し（今の場合、１＝Ｎ３ である
）、次いでラベルＮ３ に対してオーダになければオー
ダ（ＯＲＤＥＲ）なるキューの末尾にＮ３ を記録する
。 （２５） これによって、ラベルＮ７ に出力してい
るアンドゲートについての入力に関して空集合となった
ので、Ｓ２６からＳ３３に進む。 （２６） 今の場合にはＦＡＮＯＵＴ２ＵＰなるキュ
ーに値がセットされていることから、Ｓ３５に進む。 （２７） Ｓ３５においては、ＦＡＮＯＵＴ１ＬＩＳ
Ｔに記録されているＮ１ とＮ２ とを、オーダなるキ
ューに接続する。すなわちオーダなるキューの中でラベ
ルＮ３ が記録されている位置の後であって、その後に
既に接続されているかも知れない所のゲート数が１であ
るラベルについてのオーダの後に、上記ラベルＮ１ と
Ｎ３ とを接続する。これによって、今の場合には、ラ
ベルＮ３ か順位「１」、ラベルＮ１ が順位「２」、
ラベルＮ２ が順位「３」となった。そして、上記ＦＡ
ＮＯＵＴ１ＬＩＳＴなるキューはクリヤされ、ラベルＮ
７ にマークをつけて、ラベルＮ８ についての処理に
進む。 （２８） ラベルＮ８ についての処理を行う際に、
上述と同様にしてラベルＮ６ の処理に進む。そしてラ
ベルＮ６ に出力しているノット・ゲートの入力に対応
するラベルＮ３ が把握され、当該ラベルＮ３ につい
ては既にマークがついていることから、処理を中止して
、Ｓ３７に進む。 （２９） そしてラベルＮ４ について処理が行われ
ることになる。 （３０） 以上のようにして、最終的にオーダなるキ
ュー上には、ラベルＮ３ ，Ｎ１ ，Ｎ２ ，Ｎ４ が
並ぶことになる。
のグラフを作成するプログラムが呼ばれた状態を表わし
ている。以下、２分決定グラフ作成時における入力変数
に対する順序が決定される状況を説明する。 （１） 図８のＳ２３において、図９のラベルＮ９ の
所についてのグラフ作成に入る。 （２） Ｓ２４において、ラベルＮ９ についての処理
が先に行われたか否かが調べられる。 （３） 今の場合には先に処理がなされてはいないので
、Ｓ２５において、ラベルＮ９ に出力しているオアゲ
ートについての入力Ｎ７ ，Ｎ８ とを把握する。 （４） 今の場合、入力としてＮ７ 、Ｎ８ とが存在
することから、空集合（すなわち入力がない）ではなく
、Ｓ２６からＳ２７に向かう。 （５） Ｓ２７において入力の一方のＮ７ を取り出し
、１−Ｎ７ とする。 （６） Ｓ２８においてＮ７ が入力変数に直接接続さ
れているか否かを調べる。 （７） Ｎ７ の場合にはＮＯであり、Ｓ２９に進み、
ラベルＮ７ についてのグラフを作成する処理に入る。 Ｓ２９の処理を行うことは、Ｓ２３におけるＮとしてＮ
７ を設定したことに対応し、Ｎ＝１−Ｎ７ としてＳ
２４に進む。 （８） 今の場合にはＳ２５に進み、ラベルＮ７ に出
力を出しているアンドゲートについての入力Ｎ５ とＮ
３ とを把握する。 （９） Ｓ２６，２７をへて入力の一方Ｎ５ を取り出
し、１−Ｎ５ とする。 （１０） Ｓ２８においてＮ５ が入力変数に直接接
続されているか否かを調べる。 （１１） Ｎ５ の場合にはＮＯであり、Ｓ２９に進
み、ラベルＮ５ についてのグラフを作成する処理に入
る。Ｓ２９の処理を行うことは、Ｓ２３におけるＮとし
てＮ５ を設定したことに対応し、Ｎ＝１−Ｎ５ とて
Ｓ２４に進む。 （１２） 今の場合にはラベルＮ５ についてマーク
がないことから、Ｓ２５に進み、ラベルＮ５ に出力し
ているオアゲートについての入力Ｎ１ とＮ２ とを把
握する。 （１３） Ｓ２６，２７をへて入力の一方のＮ１ を
取り出し、１＝Ｎ１ とする。 （１４） Ｓ２８においてＮ１ が入力変数に直接接
続されていることが調べられ、Ｓ３０に進む。 （１５） Ｓ３０において、今の場合には１＝Ｎ１
であるＮ１ が、例えばＮ３ の場合のように２個以上
のゲートの入力に接続されていないことから、Ｓ３２に
進む。 （１６） Ｓ３２において、ＦＡＮＯＵＴ１ＬＩＳＴ
なるキューの末尾に、Ｎ１ を付加する（今の場合１＝
Ｎ１ である）。 （１７） 次いでＳ２６に戻り、Ｓ２７において、他
方の入力Ｎ２ を選び、１＝Ｎ２ とする。 （１８） Ｓ２８において、Ｎ２ が入力変数に直接
接続されていることから、Ｓ３０に進み、Ｓ３２に進む
。 （１９） Ｓ３２において、上記ＦＡＮＯＵＴ１ＬＩ
ＳＴなるキューの末尾に、Ｎ２ を付加する（上記Ｎ１
の次にＮ２ を付加する）。 （２０） 次にＳ２６に戻るが、空集合になったので
（Ｎ１ とＮ２ とが処理された）、Ｓ３３に進む。 （２１） 今の場合にはＦＡＮＯＵＴ２ＵＰなるキュ
ー（後述する）に値がセットされていないので、Ｓ３４
に進み、ラベルＮ５ に対応してマークをつけ、上記保
留にしておいたラベル３ についての処理に入る。 （２２） 上述と同様にＳ２３〜２７をへてＳ２８に
進むが、ラベルＮ３ の場合にはＹＥＳであり、Ｓ３０
に進む。 （２３） そして、ラベルＮ３ の場合には、Ｓ３０
においてＹＥＳであり（ラベルＮ３ が２つのゲートの
入力となっている）、Ｓ３１に進む。 （２４） Ｓ３１において、ＦＡＮＯＵＴ２ＵＰなる
キューにＮ３ を記録し（今の場合、１＝Ｎ３ である
）、次いでラベルＮ３ に対してオーダになければオー
ダ（ＯＲＤＥＲ）なるキューの末尾にＮ３ を記録する
。 （２５） これによって、ラベルＮ７ に出力してい
るアンドゲートについての入力に関して空集合となった
ので、Ｓ２６からＳ３３に進む。 （２６） 今の場合にはＦＡＮＯＵＴ２ＵＰなるキュ
ーに値がセットされていることから、Ｓ３５に進む。 （２７） Ｓ３５においては、ＦＡＮＯＵＴ１ＬＩＳ
Ｔに記録されているＮ１ とＮ２ とを、オーダなるキ
ューに接続する。すなわちオーダなるキューの中でラベ
ルＮ３ が記録されている位置の後であって、その後に
既に接続されているかも知れない所のゲート数が１であ
るラベルについてのオーダの後に、上記ラベルＮ１ と
Ｎ３ とを接続する。これによって、今の場合には、ラ
ベルＮ３ か順位「１」、ラベルＮ１ が順位「２」、
ラベルＮ２ が順位「３」となった。そして、上記ＦＡ
ＮＯＵＴ１ＬＩＳＴなるキューはクリヤされ、ラベルＮ
７ にマークをつけて、ラベルＮ８ についての処理に
進む。 （２８） ラベルＮ８ についての処理を行う際に、
上述と同様にしてラベルＮ６ の処理に進む。そしてラ
ベルＮ６ に出力しているノット・ゲートの入力に対応
するラベルＮ３ が把握され、当該ラベルＮ３ につい
ては既にマークがついていることから、処理を中止して
、Ｓ３７に進む。 （２９） そしてラベルＮ４ について処理が行われ
ることになる。 （３０） 以上のようにして、最終的にオーダなるキ
ュー上には、ラベルＮ３ ，Ｎ１ ，Ｎ２ ，Ｎ４ が
並ぶことになる。
【００２８】以上によってラベルＮ３ ，Ｎ１ ，Ｎ２
，Ｎ４ にそれぞれ対応する変数Ｘ３ ，Ｘ１ ，Ｘ
２ ，Ｘ４ が変数順として決定される。なお図９の論
理回路は論理関数Ｘ１ ・Ｘ３ ＋Ｘ２ ・Ｘ３ ＋
外５ ・Ｘ４ を表わしており、この論理関数のカ
バーに
，Ｎ４ にそれぞれ対応する変数Ｘ３ ，Ｘ１ ，Ｘ
２ ，Ｘ４ が変数順として決定される。なお図９の論
理回路は論理関数Ｘ１ ・Ｘ３ ＋Ｘ２ ・Ｘ３ ＋
外５ ・Ｘ４ を表わしており、この論理関数のカ
バーに
【００２９】
【外５】
【００３０】おいて、０と１の数が３であるＸ３ を除
く他の３つの変数に対する０と１の数は全て同一であり
、その順序が図９に示したように回路を深さ優先でたど
った場合に見つかる変数の順序、すなわちＸ１ ，Ｘ２
，Ｘ４ として決定されることになる。なお回路をた
どる際には、上述の説明のように１つのゲートに対する
複数の入力端子に対して、常に上の入力端子からたどる
ものとする。
く他の３つの変数に対する０と１の数は全て同一であり
、その順序が図９に示したように回路を深さ優先でたど
った場合に見つかる変数の順序、すなわちＸ１ ，Ｘ２
，Ｘ４ として決定されることになる。なお回路をた
どる際には、上述の説明のように１つのゲートに対する
複数の入力端子に対して、常に上の入力端子からたどる
ものとする。
【００３１】図１０は図７〜図９を用いて説明した処理
の間における各キューとしてのファンアウト２アップ、
ファンアウトリスト、およびオーダの内容を示している
。なおＮＩＬは空を表わしている。
の間における各キューとしてのファンアウト２アップ、
ファンアウトリスト、およびオーダの内容を示している
。なおＮＩＬは空を表わしている。
【００３２】図１１は回路を深さ優先でたどる他の実施
例である。同図は図１５および図１６で説明した論理回
路の例であり、図７および図８で説明したフローチャー
トを用いることにより、図１５と同一の最適順が決定さ
れる。
例である。同図は図１５および図１６で説明した論理回
路の例であり、図７および図８で説明したフローチャー
トを用いることにより、図１５と同一の最適順が決定さ
れる。
【００３３】図１２は回路合成の研究等で用いられるベ
ンチマーク回路に本発明を適用した場合の結果を示して
いる。同図においてオリジナル順は本発明を適用しない
場合の変数の順序を示し、本発明を適用した順序の場合
と比較すると２分決定グラフのノード数は非常に大きく
なっている。
ンチマーク回路に本発明を適用した場合の結果を示して
いる。同図においてオリジナル順は本発明を適用しない
場合の変数の順序を示し、本発明を適用した順序の場合
と比較すると２分決定グラフのノード数は非常に大きく
なっている。
【００３４】図１３は本発明が適用可能な、拡張された
２分決定グラフとしての共有２分決定グラフの例である
。同図において、（ａ） において示されている２つの
２分決定グラフは（ｂ） の共有２分決定グラフ、また
は（ｃ） の否定エッジつき共有２分決定グラフに拡張
される。 （ｂ） では、（ａ） に示した２つの論理関数Ｆ１
およびＦ２ において同じ形の２分グラフを共有したも
のであり、共有２分決定グラフと呼ばれる。
２分決定グラフとしての共有２分決定グラフの例である
。同図において、（ａ） において示されている２つの
２分決定グラフは（ｂ） の共有２分決定グラフ、また
は（ｃ） の否定エッジつき共有２分決定グラフに拡張
される。 （ｂ） では、（ａ） に示した２つの論理関数Ｆ１
およびＦ２ において同じ形の２分グラフを共有したも
のであり、共有２分決定グラフと呼ばれる。
【００３５】また（ｃ） においては、（ｂ） の共有
２分決定グラフにおいて論理関数が互いに否定の関係に
なっている場合に、関数の否定を表わす特別な属性をエ
ッジに、ここではエッジの先に○をつけ、それによって
グラフを更にコンパクトにしたものである。すなわち関
数Ｆ１ とＦ２ とは互いに否定の関係にあるために、
Ｆ２ をＦ１ のルートノードに対して否定エッジでつ
なぐことで、（ｂ） と同一内容の否定エッジ付き共有
２分決定グラフが作成される。そして本発明の変数順決
定方式はこのような拡張された２分決定グラフに対して
も適用することができる。
２分決定グラフにおいて論理関数が互いに否定の関係に
なっている場合に、関数の否定を表わす特別な属性をエ
ッジに、ここではエッジの先に○をつけ、それによって
グラフを更にコンパクトにしたものである。すなわち関
数Ｆ１ とＦ２ とは互いに否定の関係にあるために、
Ｆ２ をＦ１ のルートノードに対して否定エッジでつ
なぐことで、（ｂ） と同一内容の否定エッジ付き共有
２分決定グラフが作成される。そして本発明の変数順決
定方式はこのような拡張された２分決定グラフに対して
も適用することができる。
【００３６】
【発明の効果】以上説明したように、本発明によれば２
分決定グラフの表現をコンパクトにすることができ、論
理照合、論理検証等の各種論理設計支援技術の効率化に
寄与するところが大きい。
分決定グラフの表現をコンパクトにすることができ、論
理照合、論理検証等の各種論理設計支援技術の効率化に
寄与するところが大きい。
【図１】本発明の機能ブロック図である。
【図２】２段論理式を表現するパターンとしてのカバー
の実施例を示す図である。
の実施例を示す図である。
【図３】本発明の変数順決定方式を用いた２分決定グラ
フの実施例を示す図である。
フの実施例を示す図である。
【図４】本発明の変数順決定方式を用いない２分決定グ
ラフの例を示す図である。
ラフの例を示す図である。
【図５】変数順決定処理実施例のフローチャートである
。
。
【図６】０と１の数が同一の変数に対する変数順決定処
理実施例の概略フローチャートである。
理実施例の概略フローチャートである。
【図７】０と１の数が同一の変数に対する変数順決定処
理の詳細フローチャート（その１）である。
理の詳細フローチャート（その１）である。
【図８】０と１の数が同一の変数に対する変数順決定処
理の詳細フローチャート（その２）である。
理の詳細フローチャート（その２）である。
【図９】論理回路を深さ優先でたどる実施例を示す図で
ある。
ある。
【図１０】図７，８の処理の間におけるキューの内容を
示す図である。
示す図である。
【図１１】論理回路を深さ優先でたどる他の実施例を示
す図である。
す図である。
【図１２】ベンチマーク回路に本発明を適用した場合の
結果を示す図である。
結果を示す図である。
【図１３】共有２分決定グラフの実施例を示す図である
。
。
【図１４】２分決定グラフの例を示す図である。
【図１５】最適変数順を用いた場合の２分決定グラフの
例を示す図である。
例を示す図である。
【図１６】最悪変数順を用いた場合の２分決定グラフの
例を示す図である。
例を示す図である。
Claims (4)
- 【請求項１】 ２段論理回路の論理関数を表現する２
分決定グラフの作成時において、該２段論理回路の論理
関数を表わす論理式を積和形式に展開して簡単化し（１
）、該論理式に表われる各変数が肯定もしくは否定の形
式で用いられている積項数をそれぞれ調べ（２）、該積
項数が多い変数の順序を該２分決定グラフ作成時におけ
る変数順とする（３）ことを特徴とする２分決定グラフ
の変数順決定方式。 - 【請求項２】 前記積項数を調べる（２）に際して、
前記積和形式の積項数と同じ行数、前記論理式に表われ
る変数の数と同じ列数を有する行列形式パターンとして
のカバーの各行に各積項を対応させ、各列に対応する変
数が該各行に対する積項に肯定、否定で表われる時、ま
たは表われない時にそれぞれ対応する３種類の記号を該
行列形式パターンの各要素としてカバーを作成し、該カ
バー内で各変数に対する肯定および否定に対応する記号
の数が多い順を前記変数順とすることを特徴とする請求
項１記載の２分決定グラフの変数順決定方式。 - 【請求項３】 前記積項数を調べる（２）に際して、
該積項数が同一の変数が存在する時、前記積和形式の論
理式における積を論理積ゲート、和を論理和ゲートで表
わした論理回路図を作成し、該回路図の出力側から深さ
優先に順次入力側へ該回路をたどり、見つけられた入力
変数の順序を該積項数が同一の変数に対する前記変数順
とすることを特徴とする請求項１記載の２分決定グラフ
の変数順決定方式。 - 【請求項４】 前記論理回路図の出力側から該回路を
たどるにあたり、同一ゲートに接続さている入力変数に
対しては可能な範囲で隣接する順位を与え、かつ複数回
使用される入力変数に対しては該使用回数が多いものほ
ど先順の順位を与えることを特徴とする請求項３記載の
２分決定グラフの変数順決定方式。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3026388A JP2824482B2 (ja) | 1991-02-20 | 1991-02-20 | ２分決定グラフの変数順決定方式 |
| US07/836,850 US5535132A (en) | 1991-02-20 | 1992-02-19 | Variable sequence determining method for a dichotomy determination graph |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3026388A JP2824482B2 (ja) | 1991-02-20 | 1991-02-20 | ２分決定グラフの変数順決定方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04264979A true JPH04264979A (ja) | 1992-09-21 |
| JP2824482B2 JP2824482B2 (ja) | 1998-11-11 |
Family
ID=12192155
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3026388A Expired - Lifetime JP2824482B2 (ja) | 1991-02-20 | 1991-02-20 | ２分決定グラフの変数順決定方式 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5535132A (ja) |
| JP (1) | JP2824482B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010044523A (ja) * | 2008-08-11 | 2010-02-25 | Fujitsu Ltd | 真偽判定方法 |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6444072B1 (en) * | 1999-08-11 | 2002-09-03 | Southpac Trust International | Process for producing holographic material |
| WO2001067207A2 (en) * | 2000-03-09 | 2001-09-13 | The Web Access, Inc. | Method and apparatus for organizing data by overlaying a searchable database with a directory tree structure |
| US8335779B2 (en) * | 2002-08-16 | 2012-12-18 | Gamroe Applications, Llc | Method and apparatus for gathering, categorizing and parameterizing data |
Family Cites Families (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4792909A (en) * | 1986-04-07 | 1988-12-20 | Xerox Corporation | Boolean logic layout generator |
| US5151867A (en) * | 1986-09-12 | 1992-09-29 | Digital Equipment Corporation | Method of minimizing sum-of-product cases in a heterogeneous data base environment for circuit synthesis |
| JPS63237436A (ja) * | 1987-03-26 | 1988-10-03 | Toshiba Corp | 半導体集積回路装置の配線方法 |
| US4918614A (en) * | 1987-06-02 | 1990-04-17 | Lsi Logic Corporation | Hierarchical floorplanner |
| US4815003A (en) * | 1987-06-19 | 1989-03-21 | General Electric Company | Structured design method for high density standard cell and macrocell layout of VLSI chips |
| US5146583A (en) * | 1987-09-25 | 1992-09-08 | Matsushita Electric Industrial Co., Ltd. | Logic design system for creating circuit configuration by generating parse tree from hardware description language and optimizing text level redundancy thereof |
| US5243538B1 (en) * | 1989-08-09 | 1995-11-07 | Hitachi Ltd | Comparison and verification system for logic circuits and method thereof |
| US5237513A (en) * | 1989-11-20 | 1993-08-17 | Massachusetts Institute Of Technology | Optimal integrated circuit generation |
| JPH03180976A (ja) * | 1989-12-11 | 1991-08-06 | Hitachi Ltd | 入出力端子割付方法 |
| US5287289A (en) * | 1990-04-13 | 1994-02-15 | Hitachi, Ltd. | Logic synthesis method |
| US5200907A (en) * | 1990-04-16 | 1993-04-06 | Tran Dzung J | Transmission gate logic design method |
| US5189629A (en) * | 1990-06-06 | 1993-02-23 | Hughes Aircraft Company | Method of logic gate reduction in a logic gate array |
| US5258919A (en) * | 1990-06-28 | 1993-11-02 | National Semiconductor Corporation | Structured logic design method using figures of merit and a flowchart methodology |
| US5189628A (en) * | 1991-03-11 | 1993-02-23 | National Semiconductor Corporation | System and method for partitioning PLA product terms into distinct logical groups |
| US5282147A (en) * | 1991-08-02 | 1994-01-25 | International Business Machines Corporation | Method and apparatus for optimizing a logic network |
-
1991
- 1991-02-20 JP JP3026388A patent/JP2824482B2/ja not_active Expired - Lifetime
-
1992
- 1992-02-19 US US07/836,850 patent/US5535132A/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010044523A (ja) * | 2008-08-11 | 2010-02-25 | Fujitsu Ltd | 真偽判定方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5535132A (en) | 1996-07-09 |
| JP2824482B2 (ja) | 1998-11-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US12216584B2 (en) | Methods and systems for handling data received by a state machine engine | |
| US10606787B2 (en) | Methods and apparatuses for providing data received by a state machine engine | |
| CN109003132B (zh) | 广告推荐方法及相关产品 | |
| Potter | Associative computing: a programming paradigm for massively parallel computers | |
| EP2891053B1 (en) | Results generation for state machine engines | |
| CN113449858A (zh) | 一种神经网络模型的处理方法以及相关设备 | |
| US10489062B2 (en) | Methods and systems for using state vector data in a state machine engine | |
| US20210232630A1 (en) | Methods and systems for creating networks | |
| CN111160551A (zh) | 计算图执行方法、计算机设备及存储介质 | |
| US9396298B1 (en) | Linear array display | |
| US20210133854A1 (en) | Information processing method and terminal device | |
| CN110689116A (zh) | 一种神经网络剪枝方法、装置、计算机设备及存储介质 | |
| US20180113951A1 (en) | Graph traversal using automata processor | |
| JPH06215065A (ja) | 論理関数データ処理装置 | |
| Eckroth | Python artificial intelligence projects for beginners: Get up and running with artificial intelligence using 8 smart and exciting AI applications | |
| JPH04264979A (ja) | ２分決定グラフの変数順決定方式 | |
| Sasao et al. | Applications of zero-suppressed decision diagrams | |
| CN117764122B (zh) | 计算图处理方法、装置、电子设备及存储介质 | |
| JP5512817B2 (ja) | 情報処理装置、情報処理方法、プログラム、および媒体 | |
| CN116738005A (zh) | 基于自适应节点级权值学习的混合阶图聚类方法及相关设备 | |
| CN119961283A (zh) | 基于自然语言的数据库查询方法、设备和存储介质 | |
| JPH09179897A (ja) | ２分決定グラフの変数交換方法 | |
| JPH0490025A (ja) | プログラム作成装置 | |
| JP2001022585A (ja) | 情報処理方式統合型の情報処理装置及び情報処理方法、情報処理プログラムを記録した記録媒体、並びに、集積回路装置 | |
| JPH05334387A (ja) | 論理回路の簡単化方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19980804 |