JPH1063709A - 組み合せ回路の機能抽出方法 - Google Patents

Abstract

(57)【要約】 【課題】 二分決定グラフ、即ちＢＤＤ（Ｂｉｎａｒｙ
Ｄｅｃｉｓｉｏｎ Ｄｉａｇｒａｍ）を用いることに
より、回路全体の真理値表を求める機能抽出方法におい
て、入力数が多い場合にも対応でき、高速に処理可能な
機能抽出方法を提供しようとするものであり、多出力を
１つの併合されたＢＤＤ（ＭｅｒｇｅされたＢＤＤ）に
て表し、出力値が０、１以外の値をとる部分回路を含む
回路にも対応できる機能抽出方法を提供する。 【解決手段】 ＢＤＤ（Ｂｉｎａｒｙ Ｄｅｃｉｓｉｏ
ｎ Ｄｉａｇｒａｍ）演算を応用して組み合せ回路全体
の真理値表を求める機能抽出方法であって、組み合わせ
回路の出力をＢＤＤの併合（Ｍｅｒｇｅ）により１つの
ＢＤＤにて表すものであり、ＢＤＤ化は入力変数の２項
の値がともにリーフに達するまで行い、リーフに達した
時点で再帰を打ちきるもので、且つ、必要な場合には、
リーフ同志の演算でビット数を増やしたリーフを作成す
る処理を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は，ＬＳＩの動作検証に関
し、特に回路の機能（論理）抽出に関する。

【０００２】

【従来の技術】近年、電子機器の高性能化と軽薄短小の
傾向から、ＡＳＩＣに代表される種々のＬＳＩには、ま
すます高集積化、高機能化が求められるようになってき
た。即ち、できるだけチップサイズを小さくして、高機
能を実現することがＡＳＩＣ等のＩＣには求められてい
る。上記ＡＳＩＣ等のＩＣの作製は、機能、論理設計、
回路設計、レイアウト設計等を経て、フオトマスクパタ
ーン用のパターンを作製し、これを用いてフオトマスク
を作製した後、フオトマスクのパターンをウエハ上に縮
小投影露光等により転写して、半導体作製のプロセスを
行うものである。従来、レイアウト設計の段階で設計変
更がある場合には、トランジスタレベルから更に論理回
路へ戻して、ここで動作検証をしていた。この動作検証
は、論理レベルで、回路に入るデータ信号と制御信号に
注目する処理を行う検証方法が採られていた。そして、
一連の入力データ信号と出力データ信号とからＬＳＩの
動作（回路機能）を得る、即ち、（入力データ信号の）
形をあてはめる処理からＬＳＩの動作（回路機能）を得
ていたが、高機能化、高密度化が進むに伴ない、入力数
が多くなり、次第に莫大な量の入力データ信号を必要と
するようになり、その処理には多くの時間がかかり、実
用上問題となってきた。

【０００３】このような状況のもと、組み合わせ回路の
真理値表を求める機能抽出を大規模な回路でも高速に求
める方法として、論理関数のデータ表現に二分決定グラ
フ、即ちＢＤＤ（Ｂｉｎａｒｙ Ｄｅｃｉｓｉｏｎ Ｄ
ｉａｇｒａｍ）を用い、ＢＤＤ演算を行い処理する方法
が注目されるようになってきた。ＢＤＤは論理関数のグ
ラフによる表現で、論理関数のＳｈａｎｏｎ展開（ある
入力変数に０、１の値を代入して二つの部分関数を得る
手続き）をすべての変数について再帰的に適用した結果
を二分木グラフで表したものである。ＢＤＤを用いる処
理は記憶効率や計算速度の面で優れている。

【０００４】ここで、ＢＤＤについて簡単に説明してお
く。図１６の論理関数の真理値表は図１７の通りである
が、ＹをＢＤＤで表現したものが図１８である。丸で囲
んだＡ、Ｂ、Ｃは入力変数を表しノードと呼ばれ、各ノ
ードの左下にのびた枝を０枝といい、その変数が０であ
ることを意味し、各ノードの右下にのびた枝を１枝とい
い、その変数が１であることを意味する。四角で囲んだ
０、１は論理値を表し、リーフと呼ばれ、そこに至る経
路、即ち入力値に対する出力値を意味する。図１８の経
路Ｒ１は全て０枝を通っているのでＡ＝０、Ｂ＝０、Ｃ
＝０の時の出力値が０であることを表す。図１８の経路
Ｒ２はＡ＝０、Ｂ＝１、Ｃ＝０の時の出力値が１である
ことを表す。尚、経路の方向は矢印のように上から下へ
と進む。

【０００５】更に、ＢＤＤは、ＢＤＤの入力変数の順序
を固定し、冗長なノードの削除と、等価な部分木（部分
グラフとも言う）の共有を可能な限り行うことにより規
約なグラフが得られ、論理関数をコンパクト、且つ一意
に表すことができる。以下、ＢＤＤの共有化、冗長なノ
ードの削除を説明する。図１９の点線の丸で囲んだ部分
木は同一であり、図２０（ａ）のように共有化できる。
この時、ノードＢの０枝１枝がおなじグラフを指してい
る。即ち、ノードＢが０であっても１であっても同じで
あることを意味しており、ノードＢが冗長ノードである
のでこれを削除して、図２０（ａ）は図２０（ｂ）のよ
うに表すことができる。そして、図１８に示すＢＤＤは
図２１に示すＢＤＤに規約化される。このようにして規
約なＢＤＤを得ることができる。

【０００６】しかし、真理値表から得られるＢＤＤを直
接規約化したのではＢＤＤを用いる利点が少なく、実際
には、論理関数に論理演算を施した新しい論理関数を得
る２項演算にてＢＤＤを構築していく。与えられたブー
ル式（真理値表から式）の論理を表すＢＤＤを生成する
には、まず、各入力変数を表すＢＤＤを生成し、ブール
式の構文にしたがってＢＤＤどうしの二項（論理）演算
処理を繰り返し適用し、式全体の論理を表すＢＤＤを構
築していく。二項（論理）演算処理のアルゴリズムは公
知であるので、以下、論理関数のＢＤＤをｆ、ｇとし、
ｆ（ｏｐ）ｇのＢＤＤを求めるＢＤＤ演算方法を簡単に
説明する。尚、（ｏｐ）はａｎｄとかｏｒなどの演算子
であり、ＢＤＤ演算のことをＢＤＤ二項演算とも言う。
ある１つの入力変数ｖに着目して、ｖ＝０、１の場合分
けを行い、それぞれについて演算を行う。具体的にはＢ
ＤＤの上位の変数から順に展開してそれぞれのグラフ同
志の演算を再帰的に実行する。ここで変数の順序を予め
決めておき、それにもとずき展開を行う。グラフがリー
フになり自明な演算となったところで再帰が打ち切られ
結果が返される。図２２に示す、２個の入力変数Ａ、Ｂ
のＡＮＤ（論理積）を出力Ｙとする論理回路を例に説明
する。入力変数Ａ、ＢのＢＤＤｆ、ｇは図２３のように
なる。ｆとｇのａｎｄに対するＢＤＤの二項演算は始め
に（１）と（２）のＢＤＤの二項演算からなる。図２４
に示すように、変数順序をＡ、Ｂの順とすれば、先ず、
Ａ＝０のグラフつまりリーフ０と（２）の二項演算とな
り、演算子はａｎｄなのでリーフ０が返される。次に、
Ａ＝１のグラフつまりリーフ１と（２）の二項演算とな
り、（２）つまりｇが返される。これより、図２５に示
す出力ＹのＢＤＤが生成される。

【０００７】

【発明が解決しようとする課題】上記のように、組み合
わせ回路の真理値表を求める機能抽出を大規模な回路で
も高速に求める方法として、論理関数のデータ表現に二
分決定グラフ、即ちＢＤＤを用いる処理方法が知られて
いるが、これらは、多出力の場合には、各出力ごとにＢ
ＤＤを生成して処理するものであり、組み合わせ回路の
一部に、その特性を真理値表で表される部分回路を有
し、その出力値が０、１以外にもある場合、即ち３値以
上の部分回路を有する場合には対応できないものであっ
た。本発明は、このような状況のもと、二分決定グラ
フ、即ちＢＤＤ（Ｂｉｎａｒｙ Ｄｅｃｉｓｉｏｎ Ｄ
ｉａｇｒａｍ）を用いることにより、回路全体の真理値
表を求める機能抽出方法において、入力数が多い場合に
も対応でき、高速に処理可能な機能抽出方法を提供しよ
うとするものであり、多出力を１つの併合されたＢＤＤ
（ＭｅｒｇｅされたＢＤＤ）にて表し、出力値が０、１
以外の値をとる部分回路を含む回路にも対応できる機能
抽出方法を提供しようとするものである。

【０００８】

【課題を解決するための手段】本発明の組み合せ回路の
機能抽出方法は、ＢＤＤ（Ｂｉｎａｒｙ Ｄｅｃｉｓｉ
ｏｎ Ｄｉａｇｒａｍ）演算を応用して組み合せ回路全
体の真理値表を求める機能抽出方法であって、組み合わ
せ回路の出力をＢＤＤの併合（Ｍｅｒｇｅ）により１つ
のＢＤＤにて表すものであり、ＢＤＤ化は入力変数の２
項の値がともにリーフに達するまで行い、リーフに達し
た時点で再帰を打ち切るもので、且つ、必要な場合に
は、リーフ同志の演算でビット数を増やしたリーフを作
成する処理を行うものであることを特徴とするものであ
る。そして、上記における出力が２以上であることを特
徴とするものである。そしてまた、上記において、組み
合せ回路内に、真理値表のみを与えられた部分回路があ
る場合には、部分回路を対応する論理回路に展開して作
成し、部分回路を含めた組み合わせ回路全体に対して、
出力のＢＤＤを作成することを特徴とするものであり、
部分回路の出力の値ｙｉ’とした真理値表より、真理値
表のｙｉ’の値１に対する行の積和表現の論理式ｆを作
成し、部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ
（ｊ＝１〜ｍ）をとる場合には、真理値表のｙｉ’の値
ｘｊに対する行の積和表現の論理式ｇｊ（ｊ＝１〜ｍ）
を作成し、且つ論理式のトップにｘｊに対応するマー
クＭｊを付けておき、得られた論理式ｆとｊ＝１からｊ
＝ｍまでの論理式ｇｊとをＯＲで結び、回路全体の論理
式を作成した後、該回路全体の論理式から拡張ＢＤＤ演
算により回路全体の出力ｙｉをＢＤＤ化して求めるもの
で、ＢＤＤ化に際しては、演算する論理式にマークＭｊ
がある場合には、ＢＤＤ化されたリーフ１をｘｊに置換
してＢＤＤ化を行うものであることを特徴とするもので
ある。

【０００９】

【作用】本発明の組み合せ回路の機能抽出方法は、この
ような構成にすることにより、入力数が多い場合にも対
応でき、高速に処理可能な機能抽出方法でき、且つ、多
出力を１つの併合されたＢＤＤ（ＭｅｒｇｅされたＢＤ
Ｄ）にて表すことができ、出力値が０、１以外の値をと
る部分回路を含む回路にも対応できる機能抽出方法の提
供を可能としている。詳しくは、ＢＤＤ（Ｂｉｎａｒｙ
Ｄｅｃｉｓｉｏｎ Ｄｉａｇｒａｍ）演算を応用して
組み合せ回路全体の真理値表を求める機能抽出方法であ
って、組み合わせ回路の出力をＢＤＤの併合（Ｍｅｒｇ
ｅ）により１つのＢＤＤにて表すものであり、ＢＤＤ化
は入力変数の２項の値がともにリーフに達するまで行
い、リーフに達した時点で再帰を打ち切るもので、且
つ、必要な場合には、リーフ同志の演算でビット数を増
やしたリーフを作成する処理を行うものであることによ
りこれを達成しており、特に出力が２以上、多数の場合
にも対応できるものとしている。具体的には、組み合せ
回路内に、真理値表のみを与えられた部分回路がある場
合には、部分回路を対応する論理回路に展開して作成
し、部分回路を含めた組み合わせ回路全体に対して、出
力ピンのＢＤＤを作成することにより、部分回路を含む
場合にも対応できるものとしており、部分回路の出力の
値ｙｉ’とした真理値表より、真理値表のｙｉ’の値１
に対する行の積和表現の論理式ｆを作成し、部分回路の
出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）を
とる場合には、真理値表のｙｉ’の値ｘｊに対する行の
積和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成し、且つ論
理式のトップにｘｊに対応するマークＭｊを付けてお
き、得られた論理式ｆとｊ＝１からｊ＝ｍまでの論理式
ｇｊとをＯＲで結び、回路全体の論理式を作成した後、
該回路全体の論理式から拡張ＢＤＤ演算により回路全体
の出力ｙｉをＢＤＤ化して求めるもので、ＢＤＤ化に際
しては、演算する論理式にマークＭｊがある場合には、
ＢＤＤ化されたリーフ１をｘｊに置換してＢＤＤ化を行
うものであることにより、出力が０、１以外の値をとる
部分回路がある場合にも対応できるものとしている。

【００１０】

【実施の形態】本発明の組み合せ回路の機能抽出方法を
図にもとづいて説明する。図１は本発明の組み合せ回路
の機能抽出方法のフロー図であり、以下図１に基づいて
説明する。尚、図１中Ｓ１０〜Ｓ５０は処理のステップ
（工程）を示したものである。先ず、処理する組み合わ
せ回路が部分回路を有するか否かを判断し（図１（Ｓ１
０））、部分回路を有しない場合には、そのまま回路全
体の出力値ｙｉのＢＤＤを求める。（図１（Ｓ４０）） 部分回路が有る場合には、部分回路の出力の値ｙｉ’と
した真理値表より、真理値表のｙｉ’の値１に対する行
の積和表現の論理式ｆを作成する。（図１（Ｓ２０）） 次いで、部分回路の出力の値ｙｉ’が０、１以外の値ｘ
ｊ（ｊ＝１〜ｍ）をとるか否かを判断する。（図１（Ｓ
３０）） 部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝
１〜ｍ）をとらない場合には、得られた回路全体の論理
式より回路全体の出力ｙｉをＢＤＤ化して求める。（図
１（Ｓ４０）） 部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝
１〜ｍ）をとる場合には、真理値表のｙｉ’の値ｘｊに
対する行の積和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成
し、且つ論理式のトップにｘｊに対応するマークＭｊを
付けておき（図１（Ｓ３１））、ステップＳ２０で得ら
れた論理式ｆと、ステップＳ３１で得られたｊ＝１から
ｊ＝ｍまでの論理式ｇｊとをＯＲで結んだ回路全体の論
理式を作成し（図１（Ｓ３２））、得られた回路全体の
論理式から拡張ＢＤＤ演算により回路全体の出力ｙｉを
ＢＤＤ化して求める。（図１（Ｓ４０））

【００１１】ステップＳ４０は、回路全体の論理式をＢ
ＤＤ化する工程であるが、回路全体の出力ｙｉをトップ
とする論理式をボトムアップでＮＢＤＤ化処理するもの
であり、論理式のＢＤＤ化演算をボトムアップで繰り返
すが、ＢＤＤ化に際しては、演算する論理式にマークＭ
ｊがある場合には、ＢＤＤ化されたリーフ１をｘｊに置
換してＢＤＤ化を行う。

【００１２】次に、図２そのアルゴリズムを示す、拡張
されたＢＤＤ演算により、ｎ個の出力ｙｉ（ｉ＝１〜
ｎ）のＢＤＤを１つのＢＤＤに併合（Ｍｅｒｇｅ）す
る。（図１（Ｓ５０）） 尚、図２（ａ）は全体の流れを示したもので、簡単に
は、順次繰り返し１つづつ、併合していくことを示して
いる。図２（ｂ）は、併合（Ｍｅｒｇｅ）のフロー図で
あり、図２に示す、出力のＢＤＤ同志の併合（Ｍｅｒｇ
ｅ）の特徴は、一口に言うと、従来のＢＤＤ演算では二
項のうち片方がリーフになれば再帰を打ち切っていた
が、ここでは両方がリーフに達するまで再帰を繰り返す
点と、リーフ同志の演算でビット数を増やしたリーフを
作成する点である。この２点が従来のＢＤＤ演算と異な
る。このようなＢＤＤ演算を拡張ＢＤＤ演算とここでは
言っている。

【００１３】図２のアルゴリズムに従い、具体的な例に
ついて説明する。出力がｙ１とｙ２の２個で、ＢＤＤ
が、それぞれ、図１０（ａ）、図１０（ｂ）のように表
される場合の併合（Ｍｅｒｇｅ）を図１１に基づいて説
明する。尚、図１０では、ノードに、、と番号を
ふって区別している。図１１では、併合（Ｍｅｒｇｅ）
の手続きの再帰呼び出し過程を（ａ）、（ｂ）、
（ｃ）、（ｄ）、（ｅ）として、この順に呼び出しが起
こる。この呼び出しブロック内の上段をノード（図２の
Ｙ、ｙｉにあたる）、下段を変数名として示している。
以下、順に処理を説明する。まず呼び出し（ａ）におい
て、演算対象の二項はとであり、両方ともノードで
あり、同じｘ１という変数なので、図２のＳ２０４が実
行され、各々の０、１枝同志の子で再帰呼び出しが起こ
る。（（ｂ）と（ｅ）） 始めに０枝同志の呼び出し（ｂ）が起こり、の０枝の
子はリーフ０、はであるので（ｂ）のようになる。
（ｂ）では、は変数ｘ２であり、リーフ０より上位な
ので、図２のＳ２０３が実行され再帰呼び出し（ｃ）、
（ｄ）が順に起こる。（ｃ）では、リーフ０との０枝
の子つまりリーフ０との二項演算となり、図２のＳ２０
１が実行され、新たにリーフ００を作成して戻る。（Ｒ
１） ここで（ｂ）に戻り（ｄ）が実行される。（ｄ）でも同
様にリーフ０１を作成して戻る。（Ｒ２） ここで（ｂ）に戻り図２のＳ２０５が実行される。つま
り、変数名ｘ２、（ｃ）、（ｄ）からの結果Ｒ１、Ｒ２
を０枝、１枝としたノードを作成し戻る。（Ｒ３） ここで（ａ）に戻り（ｅ）が実行される。（ｅ）でも同
様にリーフ１１を作成して戻る。（Ｒ４） そして（ａ）に戻り、図２のＳ２０５が実行され、変数
名ｘ１、０枝の子をＲ３、１枝の子をＲ４としたノード
を作成して戻る。（Ｒ５） ここでは（ａ）は最上位の再帰呼び出しなので、この結
果Ｒ５のＢＤＤが求めるものである。即ち、ｙ１のＢＤ
Ｄとｙ２のＢＤＤの併合（Ｍｅｒｇｅ）されたものが、
Ｒ５のＢＤＤである。

【００１４】次に、図１に示すステップＳ３０におい
て、部分回路お出力値が１、０のみである場合につい
て、もう少し具体的に説明しておく。部分回路の真理値
表を論理式に変換して展開すれば、もともとの回路はＢ
ＤＤで扱える形となるが、これには、積和表現の論理式
に変換すればよい。変換方法を説明すると、真理値表の
各出力毎に以下の処理を行う。注目する出力が１である
行に対して各入力ｘｉが１ならｘｉ、０ならｉｎｖ（ｘ
ｉ）とし、？なら何もしないというリケテラルをａｎｄ
で結び、行同志をｏｒで結ぶ。更に、図１２を例にとっ
て説明すると、行、行が処理の対象であり、行で
は、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）、行ではｘ１で
あり、両者をｏｒで結んだｏｒ（ａｎｄ（ｉｎｖ（ｘ
１）、ｘ２）、ｘ１）が求める論理式となる。これをも
とに展開する。

【００１５】次に、図１に示すステップＳ４０につい
て、具体例に基づいて説明しておく。図１３（ａ）のよ
うに、２個の入力ｘ１、ｘ２と１個出力ｙとをもつ部分
回路で、図１３（ｂ）の真理値表で示すように、ｙが
０、１以外の値ｘと３値を持つ場合を例にあげる。尚、
ここでは、ＡＮＤ（０、ｘ）＝０、ＡＮＤ（１、ｘ）＝
ｘ、ＯＲ（０、ｘ）＝ｘ、ＯＲ（１、ｘ）＝１のように
論理演算を定義する。これを含めたものをここでは拡張
ＢＤＤ演算と言う。また、ここでは、（ｘ１、ｘ２）＝
（０、１）の時、ｙは０、１でないｘという値をとるこ
とを意味する。この回路が全体回路の一部となるため、
全体回路のＢＤＤを得るのに、この部分回路のＢＤＤを
先ず求めるのであるが、図１３（ｂ）に示す真理値表で
表される部分回路をＢＤＤ化する。先ず、ｙの値１に対
する行の積和表現は、ｘ１でこれはＢＤＤ化すると図１
４（ａ）のようにＢＤＤ化される。これをｆとする。次
いで、ｙの値ｘに対する行の積和表現は、ａｎｄ（ｉｎ
ｖ（ｘ１）、ｘ２）で、図１４（ｂ）のようにＢＤＤ化
される。これをｇとする。そして、更に、このＢＤＤの
リーフ１をｘに置換して、再構築してＢＤＤ化し、これ
を新たにｇとすると、ｇは図１４（ｃ）のようになる。
次に、得られたＢＤＤｆとＢＤＤｇについて、ＯＲ
（ｆ、ｇ）の二項演算を行なうと図１５のようなＢＤＤ
が得られる。これをｈとする。得られたＢＤＤｈから真
理値表を作成してみれば正しいことが分かる。このよう
にして、部分回路の出力が１、０以外に値ｘをもつ場合
には、ＢＤＤの作成を行う。

【００１６】

【実施例】更に具体的に、本発明の組み合せ回路のＢＤ
Ｄ演算を応用した機能抽出方法を説明する。図３（ａ）
は本実施例の扱う、部分回路を有する組み合わせ回路を
表しており、組み合わせ回路は２個の入力Ａ、Ｂと１個
の出力ｙをもつ。図３（ｂ）は図３（ａ）に示す部分回
路の真理値表であり、出力ｙ（部分回路の出力でもあ
る）は、０、１の他の値ｘをもつ。先ず、処理する組み
合わせ回路には部分回路があるから、これの真理値表
（図３（ｂ））から、真理値表のｙの値１に対する行の
積和表現、真理値表のｙの値ｘに対する行の積和表現は
それぞれ、ｘ１、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）とな
るから、組合せ回路は図４に示すように論理式で示され
る（展開されるとも言う）。この際、ｘｊに対する行の
積和表現の論理式のトップにｘｊに対応するマークＭｊ
を付けておく。図４中、Ｄ１、Ｄ２、Ｄ３、Ｄ４は論理
素子で、ａ、ｂは、素子Ｄ２、Ｄ３からの出力を示して
いる。

【００１７】次に、ｘ１のＢＤＤおよび、ａｎｄ（ｉｎ
ｖ（ｘ１）、ｘ２）、すなわちｂのＢＤＤを求め、両Ｂ
ＤＤをＯＲ演算処理して組み合わせ回路の出力ｙのＢＤ
Ｄを求めるが、ｙの論理式をボトムアップで処理する。
入力Ａ、ＢのＢＤＤは、それぞれ図５（ａ）、図５
（ｂ）に示すものである。ｘ１はａｎｄ（Ａ、Ｂ）であ
り、ｘ１のＢＤＤは、図６（ａ）に示す２つのＢＤＤの
積（ａｎｄ）であり、これを演算処理して、図６（ｂ）
のＢＤＤを得る。ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）を求
めるには、予め、ｉｎｖ（ｘ１ ）、ｘ２のＢＤＤをそ
れぞれ求めておく。ｉｎｖ（ｘ１）のＢＤＤは、図６
（ｂ）に示すＢＤＤのｉｎｖであり、これを演算処理し
て図７のＢＤＤを得る。ｘ２のＢＤＤは、図５（ｂ）に
示す入力ＢのＢＤＤであり、結局、ａｎｄ（ｉｎｖ（ｘ
１）、ｘ２）、即ちｂのＢＤＤは、図７に示すＢＤＤと
図５（ｂ）に示すＢＤＤの積（ａｎｄ）であり、これを
演算処理して、図８（ｂ）に示すＢＤＤを得る。このＢ
ＤＤ化に際しては、マーク付きであるのでリーフ１をｘ
に置換して行う。これより、組合せ回路の出力ｙのＢＤ
Ｄは、図９（ａ）に示すように、両ＢＤＤのＯＲとな
り、これを演算処理して図９（ｂ）のＢＤＤが得られ
る。

【００１８】

【発明の効果】本発明の組み合せ回路のＢＤＤ演算を応
用した機能抽出方法は、上記のように組み合わせ回路に
おいて、多出力をまとめた表現の機能抽出を可能とする
もので、３値以上の真理値表のみを与えられた部分回路
を含む回路にも対応できるものとしている。結局、本発
明は、ＢＤＤを用い、高速処理を可能とするもので、且
つ、多入力にも対応できるものとしていく

【図面の簡単な説明】

【図１】実施例の組み合わせ回路の機能抽出方法を示し
た工程概略図

【図２】出力が多数ある場合の出力ＢＤＤ同志の併合
（Ｍｅｒｇｅ）を説明するためのフロー図

【図３】実施例の部分回路を有する組み合わせ回路およ
び部分回路の真理値表を示した図

【図４】実施例の組合せ回路を論理素子で展開した図

【図５】入力Ａ、ＢのＢＤＤを示した図

【図６】ｘ１のＢＤＤを得る演算処理を示した図

【図７】ｉｎｖ（ｘ１）ＢＤＤを得る演算処理を示した
図

【図８】ｂのＢＤＤを得る演算処理を示した図

【図９】組合せ回路の出力ｙのＢＤＤを得る演算処理を
示した図

【図１０】出力ｙ１と出力ｙ２のＢＤＤを示した図

【図１１】併合（Ｍｅｒｇｅ）の手続きの再帰呼び出し
過程を説明するための図

【図１２】部分回路の真理値表を積和表現の論理式に変
換する仕方を説明するための図

【図１３】２個の入力ｘ１、ｘ２と１個出力ｙとをもつ
部分回路とその真理値表を示した図

【図１４】真理値表の積和算表現からＢＤＤを作成する
方法を説明するための図

【図１５】ＢＤＤｆとＢＤＤｇについて、ＯＲ（ｆ、
ｇ）の二項演算によるＢＤＤを示した図

【図１６】論理関数の図

【図１７】真理値表を示した図

【図１８】ＹをＢＤＤで表現した図

【図１９】共有グラフを説明するための図

【図２０】共有化と冗長点削除を説明するための図

【図２１】規約化されたＢＤＤを示した図

【図２２】論理回路図

【図２３】入力変数Ａ、ＢのＢＤＤｆ、ｇを示した図

【図２４】ＢＤＤの二項演算を説明するための図

【図２５】二項演算により得られたＢＤＤを示した図

【符号の説明】

Ｓ１０〜Ｓ５０ ステップ Ｓ２０１〜Ｓ２０５ ステップ Ｄ１〜Ｄ４ 論理素子

Claims (4)

【特許請求の範囲】
1. 【請求項１】 ＢＤＤ（Ｂｉｎａｒｙ Ｄｅｃｉｓｉｏ
   ｎ Ｄｉａｇｒａｍ）演算を応用して組み合せ回路全体
   の真理値表を求める機能抽出方法であって、組み合わせ
   回路の出力をＢＤＤの併合（Ｍｅｒｇｅ）により１つの
   ＢＤＤにて表すものであり、ＢＤＤ化は入力変数の２項
   の値がともにリーフに達するまで行い、リーフに達した
   時点で再帰を打ち切るもので、且つ、必要な場合には、
   リーフ同志の演算でビット数を増やしたリーフを作成す
   る処理を行うものであることを特徴とする組み合せ回路
   の機能抽出方法。
2. 【請求項２】 請求項１における出力が２以上であるこ
   とを特徴とする組み合せ回路の機能抽出方法。
3. 【請求項３】 請求項１ないし２において、組み合せ回
   路内に、真理値表のみを与えられた部分回路がある場合
   には、部分回路を対応する論理回路に展開して作成し、
   部分回路を含めた組み合わせ回路全体に対して、出力の
   ＢＤＤを作成することを特徴とする組合せ回路の機能抽
   出方法。
4. 【請求項４】 請求項３において、部分回路の出力の値
   ｙｉ’とした真理値表より、真理値表のｙｉ’の値１に
   対する行の積和表現の論理式ｆを作成し、部分回路の出
   力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をと
   る場合には、真理値表のｙｉ’の値ｘｊに対する行の積
   和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成し、且つ論理
   式のトップにｘｊに対応するマークＭｊを付けておき、
   得られた論理式ｆとｊ＝１からｊ＝ｍまでの論理式ｇｊ
   とをＯＲで結び、回路全体の論理式を作成した後、該回
   路全体の論理式から拡張ＢＤＤ演算により回路全体の出
   力ｙｉをＢＤＤ化して求めるもので、ＢＤＤ化に際して
   は、演算する論理式にマークＭｊがある場合には、ＢＤ
   Ｄ化されたリーフ１をｘｊに置換してＢＤＤ化を行うも
   のであることを特徴とする組合せ回路の機能抽出方法。