(57)【特許請求の範囲】
【請求項１】
ＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）演算を応用して組み合せ回路全体の真理値表を求める、コンピュータ処理を主体とする機能抽出方法であって、組み合わせ回路の出力をＢＤＤの併合（Ｍｅｒｇｅ）により１つのＢＤＤにて表すものであり、ＢＤＤ化は入力変数の２項の値がともにリーフに達するまで行い、リーフに達した時点で再帰を打ち切るもので、且つ、必要な場合には、リーフ同志の演算でビット数を増やしたリーフを作成する処理を行うものであり、前記組み合わせ回路の出力である論理値が、０、１の２値以外の、他の値をもとることを特徴とする組み合せ回路の機能抽出方法。
【請求項２】
請求項１において、組み合せ回路内に、真理値表のみを与えられた部分回路がある場合には、部分回路を対応する論理回路に展開して作成し、部分回路を含めた組み合わせ回路全体に対して、出力のＢＤＤを作成することを特徴とする組合せ回路の機能抽出方法。
【請求項３】
請求項２において、部分回路の出力の値ｙｉ’とした真理値表より、真理値表のｙｉ’の値１に対する行の積和表現の論理式ｆを作成し、部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をとる場合には、真理値表のｙｉ’の値ｘｊに対する行の積和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成し、且つ論理式のトップにｘｊに対応するマークＭｊを付けておき、得られた論理式ｆとｊ＝１からｊ＝ｍまでの論理式ｇｊとをＯＲで結び、回路全体の論理式を作成した後、該回路全体の論理式から拡張ＢＤＤ演算により回路全体の出力ｙｉをＢＤＤ化して求めるもので、ＢＤＤ化に際しては、演算する論理式にマークＭｊがある場合には、ＢＤＤ化されたリーフ１をｘｊに置換してＢＤＤ化を行うものであることを特徴とする組合せ回路の機能抽出方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は，ＬＳＩの動作検証に関し、特に回路の機能（論理）抽出に関する。
【０００２】
【従来の技術】
近年、電子機器の高性能化と軽薄短小の傾向から、ＡＳＩＣに代表される種々のＬＳＩには、ますます高集積化、高機能化が求められるようになってきた。即ち、できるだけチップサイズを小さくして、高機能を実現することがＡＳＩＣ等のＩＣには求められている。
上記ＡＳＩＣ等のＩＣの作製は、機能、論理設計、回路設計、レイアウト設計等を経て、フオトマスクパターン用のパターンを作製し、これを用いてフオトマスクを作製した後、フオトマスクのパターンをウエハ上に縮小投影露光等により転写して、半導体作製のプロセスを行うものである。
従来、レイアウト設計の段階で設計変更がある場合には、トランジスタレベルから更に論理回路へ戻して、ここで動作検証をしていた。
この動作検証は、論理レベルで、回路に入るデータ信号と制御信号に注目する処理を行う検証方法が採られていた。
そして、一連の入力データ信号と出力データ信号とからＬＳＩの動作（回路機能）を得る、即ち、（入力データ信号の）形をあてはめる処理からＬＳＩの動作（回路機能）を得ていたが、高機能化、高密度化が進むに伴ない、入力数が多くなり、次第に莫大な量の入力データ信号を必要とするようになり、その処理には多くの時間がかかり、実用上問題となってきた。
【０００３】
このような状況のもと、組み合わせ回路の真理値表を求める機能抽出を大規模な回路でも高速に求める方法として、論理関数のデータ表現に二分決定グラフ、即ちＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）を用い、ＢＤＤ演算を行い処理する方法が注目されるようになってきた。
ＢＤＤは論理関数のグラフによる表現で、論理関数のＳｈａｎｏｎ展開（ある入力変数に０、１の値を代入して二つの部分関数を得る手続き）をすべての変数について再帰的に適用した結果を二分木グラフで表したものである。ＢＤＤを用いる処理は記憶効率や計算速度の面で優れている。
【０００４】
ここで、ＢＤＤについて簡単に説明しておく。
図１６の論理関数の真理値表は図１７の通りであるが、ＹをＢＤＤで表現したものが図１８である。丸で囲んだＡ、Ｂ、Ｃは入力変数を表しノードと呼ばれ、各ノードの左下にのびた枝を０枝といい、その変数が０であることを意味し、各ノードの右下にのびた枝を１枝といい、その変数が１であることを意味する。
四角で囲んだ０、１は論理値を表し、リーフと呼ばれ、そこに至る経路、即ち入力値に対する出力値を意味する。図１８の経路Ｒ１は全て０枝を通っているのでＡ＝０、Ｂ＝０、Ｃ＝０の時の出力値が０であることを表す。図１８の経路Ｒ２はＡ＝０、Ｂ＝１、Ｃ＝０の時の出力値が１であることを表す。
尚、経路の方向は矢印のように上から下へと進む。
【０００５】
更に、ＢＤＤは、ＢＤＤの入力変数の順序を固定し、冗長なノードの削除と、等価な部分木（部分グラフとも言う）の共有を可能な限り行うことにより規約なグラフが得られ、論理関数をコンパクト、且つ一意に表すことができる。
以下、ＢＤＤの共有化、冗長なノードの削除を説明する。
図１９の点線の丸で囲んだ部分木は同一であり、図２０（ａ）のように共有化できる。この時、ノードＢの０枝１枝がおなじグラフを指している。即ち、ノードＢが０であっても１であっても同じであることを意味しており、ノードＢが冗長ノードであるのでこれを削除して、図２０（ａ）は図２０（ｂ）のように表すことができる。そして、図１８に示すＢＤＤは図２１に示すＢＤＤに規約化される。
このようにして規約なＢＤＤを得ることができる。
【０００６】
しかし、真理値表から得られるＢＤＤを直接規約化したのではＢＤＤを用いる利点が少なく、実際には、論理関数に論理演算を施した新しい論理関数を得る２項演算にてＢＤＤを構築していく。
与えられたブール式（真理値表から式）の論理を表すＢＤＤを生成するには、まず、各入力変数を表すＢＤＤを生成し、ブール式の構文にしたがってＢＤＤどうしの二項（論理）演算処理を繰り返し適用し、式全体の論理を表すＢＤＤを構築していく。
二項（論理）演算処理のアルゴリズムは公知であるので、以下、論理関数のＢＤＤをｆ、ｇとし、ｆ（ｏｐ）ｇのＢＤＤを求めるＢＤＤ演算方法を簡単に説明する。尚、（ｏｐ）はａｎｄとかｏｒなどの演算子であり、ＢＤＤ演算のことをＢＤＤ二項演算とも言う。
ある１つの入力変数ｖに着目して、ｖ＝０、１の場合分けを行い、それぞれについて演算を行う。
具体的にはＢＤＤの上位の変数から順に展開してそれぞれのグラフ同志の演算を再帰的に実行する。
ここで変数の順序を予め決めておき、それにもとずき展開を行う。
グラフがリーフになり自明な演算となったところで再帰が打ち切られ結果が返される。
図２２に示す、２個の入力変数Ａ、ＢのＡＮＤ（論理積）を出力Ｙとする論理回路を例に説明する。
入力変数Ａ、ＢのＢＤＤｆ、ｇは図２３のようになる。
ｆとｇのａｎｄに対するＢＤＤの二項演算は始めに（１）と（２）のＢＤＤの二項演算からなる。
図２４に示すように、変数順序をＡ、Ｂの順とすれば、先ず、Ａ＝０のグラフつまりリーフ０と（２）の二項演算となり、演算子はａｎｄなのでリーフ０が返される。次に、Ａ＝１のグラフつまりリーフ１と（２）の二項演算となり、（２）つまりｇが返される。
これより、図２５に示す出力ＹのＢＤＤが生成される。
【０００７】
【発明が解決しようとする課題】
上記のように、組み合わせ回路の真理値表を求める機能抽出を大規模な回路でも高速に求める方法として、論理関数のデータ表現に二分決定グラフ、即ちＢＤＤを用いる処理方法が知られているが、これらは、多出力の場合には、各出力ごとにＢＤＤを生成して処理するものであり、組み合わせ回路の一部に、その特性を真理値表で表される部分回路を有し、その出力値が０、１以外にもある場合、即ち３値以上の部分回路を有する場合には対応できないものであった。
本発明は、このような状況のもと、二分決定グラフ、即ちＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）を用いることにより、回路全体の真理値表を求める機能抽出方法において、入力数が多い場合にも対応でき、高速に処理可能な機能抽出方法を提供しようとするものであり、多出力を１つの併合されたＢＤＤ（ＭｅｒｇｅされたＢＤＤ）にて表し、出力値が０、１以外の値をとる部分回路を含む回路にも対応できる機能抽出方法を提供しようとするものである。
【０００８】
【課題を解決するための手段】
本発明の組み合せ回路の機能抽出方法は、ＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）演算を応用して組み合せ回路全体の真理値表を求める、コンピュータ処理を主体とする機能抽出方法であって、組み合わせ回路の出力をＢＤＤの併合（Ｍｅｒｇｅ）により１つのＢＤＤにて表すものであり、ＢＤＤ化は入力変数の２項の値がともにリーフに達するまで行い、リーフに達した時点で再帰を打ち切るもので、且つ、必要な場合には、リーフ同志の演算でビット数を増やしたリーフを作成する処理を行うものであり、前記組み合わせ回路の出力である論理値が、０、１の２値以外の、他の値をもとることを特徴とするものである。
そして、上記において、組み合せ回路内に、真理値表のみを与えられた部分回路がある場合には、部分回路を対応する論理回路に展開して作成し、部分回路を含めた組み合わせ回路全体に対して、出力のＢＤＤを作成することを特徴とするものであり、
部分回路の出力の値ｙｉ’とした真理値表より、真理値表のｙｉ’の値１に対する行の積和表現の論理式ｆを作成し、部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をとる場合には、真理値表のｙｉ’の値ｘｊに対する行の積和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成し、且つ論理式のトップにｘｊに対応するマークＭｊを付けておき、得られた論理式ｆとｊ＝１からｊ＝ｍまでの論理式ｇｊとをＯＲで結び、回路全体の論理式を作成した後、該回路全体の論理式から拡張ＢＤＤ演算により回路全体の出力ｙｉをＢＤＤ化して求めるもので、ＢＤＤ化に際しては、演算する論理式にマークＭｊがある場合には、ＢＤＤ化されたリーフ１をｘｊに置換してＢＤＤ化を行うものであることを特徴とするものである。
【０００９】
【作用】
本発明の組み合せ回路の機能抽出方法は、このような構成にすることにより、入力数が多い場合にも対応でき、高速に処理可能な機能抽出方法でき、且つ、多出力を１つの併合されたＢＤＤ（ＭｅｒｇｅされたＢＤＤ）にて表すことができ、出力値が０、１以外の値をとる部分回路を含む回路にも対応できる機能抽出方法の提供を可能としている。
詳しくは、ＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）演算を応用して組み合せ回路全体の真理値表を求める機能抽出方法であって、組み合わせ回路の出力をＢＤＤの併合（Ｍｅｒｇｅ）により１つのＢＤＤにて表すものであり、ＢＤＤ化は入力変数の２項の値がともにリーフに達するまで行い、リーフに達した時点で再帰を打ち切るもので、且つ、必要な場合には、リーフ同志の演算でビット数を増やしたリーフを作成する処理を行うものであることによりこれを達成しており、特に出力が２以上、多数の場合にも対応できるものとしている。
具体的には、組み合せ回路内に、真理値表のみを与えられた部分回路がある場合には、部分回路を対応する論理回路に展開して作成し、部分回路を含めた組み合わせ回路全体に対して、出力ピンのＢＤＤを作成することにより、部分回路を含む場合にも対応できるものとしており、部分回路の出力の値ｙｉ’とした真理値表より、真理値表のｙｉ’の値１に対する行の積和表現の論理式ｆを作成し、部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をとる場合には、真理値表のｙｉ’の値ｘｊに対する行の積和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成し、且つ論理式のトップにｘｊに対応するマークＭｊを付けておき、得られた論理式ｆとｊ＝１からｊ＝ｍまでの論理式ｇｊとをＯＲで結び、回路全体の論理式を作成した後、該回路全体の論理式から拡張ＢＤＤ演算により回路全体の出力ｙｉをＢＤＤ化して求めるもので、ＢＤＤ化に際しては、演算する論理式にマークＭｊがある場合には、ＢＤＤ化されたリーフ１をｘｊに置換してＢＤＤ化を行うものであることにより、出力が０、１以外の値をとる部分回路がある場合にも対応できるものとしている。
【００１０】
【実施の形態】
本発明の組み合せ回路の機能抽出方法を図にもとづいて説明する。
図１は本発明の組み合せ回路の機能抽出方法のフロー図であり、以下図１に基づいて説明する。
尚、図１中Ｓ１０〜Ｓ５０は処理のステップ（工程）を示したものである。
先ず、処理する組み合わせ回路が部分回路を有するか否かを判断し（図１（Ｓ１０））、部分回路を有しない場合には、そのまま回路全体の出力値ｙｉのＢＤＤを求める。（図１（Ｓ４０））
部分回路が有る場合には、部分回路の出力の値ｙｉ’とした真理値表より、真理値表のｙｉ’の値１に対する行の積和表現の論理式ｆを作成する。（図１（Ｓ２０））
次いで、部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をとるか否かを判断する。（図１（Ｓ３０））
部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をとらない場合には、得られた回路全体の論理式より回路全体の出力ｙｉをＢＤＤ化して求める。（図１（Ｓ４０））
部分回路の出力の値ｙｉ’が０、１以外の値ｘｊ（ｊ＝１〜ｍ）をとる場合には、真理値表のｙｉ’の値ｘｊに対する行の積和表現の論理式ｇｊ（ｊ＝１〜ｍ）を作成し、且つ論理式のトップにｘｊに対応するマークＭｊを付けておき（図１（Ｓ３１））、ステップＳ２０で得られた論理式ｆと、ステップＳ３１で得られたｊ＝１からｊ＝ｍまでの論理式ｇｊとをＯＲで結んだ回路全体の論理式を作成し（図１（Ｓ３２））、得られた回路全体の論理式から拡張ＢＤＤ演算により回路全体の出力ｙｉをＢＤＤ化して求める。（図１（Ｓ４０））
【００１１】
ステップＳ４０は、回路全体の論理式をＢＤＤ化する工程であるが、回路全体の出力ｙｉをトップとする論理式をボトムアップでＮＢＤＤ化処理するものであり、論理式のＢＤＤ化演算をボトムアップで繰り返すが、ＢＤＤ化に際しては、演算する論理式にマークＭｊがある場合には、ＢＤＤ化されたリーフ１をｘｊに置換してＢＤＤ化を行う。
【００１２】
次に、図２そのアルゴリズムを示す、拡張されたＢＤＤ演算により、ｎ個の出力ｙｉ（ｉ＝１〜ｎ）のＢＤＤを１つのＢＤＤに併合（Ｍｅｒｇｅ）する。（図１（Ｓ５０））
尚、図２（ａ）は全体の流れを示したもので、簡単には、順次繰り返し１つづつ、併合していくことを示している。
図２（ｂ）は、併合（Ｍｅｒｇｅ）のフロー図であり、図２に示す、出力のＢＤＤ同志の併合（Ｍｅｒｇｅ）の特徴は、一口に言うと、従来のＢＤＤ演算では二項のうち片方がリーフになれば再帰を打ち切っていたが、ここでは両方がリーフに達するまで再帰を繰り返す点と、リーフ同志の演算でビット数を増やしたリーフを作成する点である。この２点が従来のＢＤＤ演算と異なる。このようなＢＤＤ演算を拡張ＢＤＤ演算とここでは言っている。
【００１３】
図２のアルゴリズムに従い、具体的な例について説明する。
出力がｙ１とｙ２の２個で、ＢＤＤが、それぞれ、図１０（ａ）、図１０（ｂ）のように表される場合の併合（Ｍｅｒｇｅ）を図１１に基づいて説明する。
尚、図１０では、ノードに▲１▼、▲２▼、▲３▼と番号をふって区別している。
図１１では、併合（Ｍｅｒｇｅ）の手続きの再帰呼び出し過程を（ａ）、（ｂ）、（ｃ）、（ｄ）、（ｅ）として、この順に呼び出しが起こる。
この呼び出しブロック内の上段をノード（図２のＹ、ｙｉにあたる）、下段を変数名として示している。
以下、順に処理を説明する。
まず呼び出し（ａ）において、
演算対象の二項は▲１▼と▲２▼であり、両方ともノードであり、同じｘ１という変数なので、図２のＳ２０４が実行され、各々の０、１枝同志の子で再帰呼び出しが起こる。（（ｂ）と（ｅ））
始めに０枝同志の呼び出し（ｂ）が起こり、▲１▼の０枝の子はリーフ０、▲２▼は▲３▼であるので（ｂ）のようになる。
（ｂ）では、▲３▼は変数ｘ２であり、リーフ０より上位なので、図２のＳ２０３が実行され再帰呼び出し（ｃ）、（ｄ）が順に起こる。
（ｃ）では、リーフ０と▲３▼の０枝の子つまりリーフ０との二項演算となり、図２のＳ２０１が実行され、新たにリーフ００を作成して戻る。（Ｒ１）
ここで（ｂ）に戻り（ｄ）が実行される。
（ｄ）でも同様にリーフ０１を作成して戻る。（Ｒ２）
ここで（ｂ）に戻り図２のＳ２０５が実行される。
つまり、変数名ｘ２、（ｃ）、（ｄ）からの結果Ｒ１、Ｒ２を０枝、１枝としたノードを作成し戻る。（Ｒ３）
ここで（ａ）に戻り（ｅ）が実行される。
（ｅ）でも同様にリーフ１１を作成して戻る。（Ｒ４）
そして（ａ）に戻り、図２のＳ２０５が実行され、変数名ｘ１、０枝の子をＲ３、１枝の子をＲ４としたノードを作成して戻る。（Ｒ５）
ここでは（ａ）は最上位の再帰呼び出しなので、この結果Ｒ５のＢＤＤが求めるものである。即ち、ｙ１のＢＤＤとｙ２のＢＤＤの併合（Ｍｅｒｇｅ）されたものが、Ｒ５のＢＤＤである。
【００１４】
次に、図１に示すステップＳ３０において、部分回路お出力値が１、０のみである場合について、もう少し具体的に説明しておく。
部分回路の真理値表を論理式に変換して展開すれば、もともとの回路はＢＤＤで扱える形となるが、これには、積和表現の論理式に変換すればよい。
変換方法を説明すると、真理値表の各出力毎に以下の処理を行う。
注目する出力が１である行に対して各入力ｘｉが１ならｘｉ、０ならｉｎｖ
（ｘｉ）とし、？なら何もしないというリケテラルをａｎｄで結び、行同志をｏｒで結ぶ。
更に、図１２を例にとって説明すると、▲１▼行、▲２▼行が処理の対象であり、行▲１▼では、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）、行▲２▼ではｘ１であり、両者をｏｒで結んだｏｒ（ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）、ｘ１）が求める論理式となる。
これをもとに展開する。
【００１５】
次に、図１に示すステップＳ４０について、具体例に基づいて説明しておく。図１３（ａ）のように、２個の入力ｘ１、ｘ２と１個出力ｙとをもつ部分回路で、図１３（ｂ）の真理値表で示すように、ｙが０、１以外の値ｘと３値を持つ場合を例にあげる。
尚、ここでは、ＡＮＤ（０、ｘ）＝０、ＡＮＤ（１、ｘ）＝ｘ、ＯＲ（０、ｘ）＝ｘ、ＯＲ（１、ｘ）＝１のように論理演算を定義する。これを含めたものをここでは拡張ＢＤＤ演算と言う。
また、ここでは、（ｘ１、ｘ２）＝（０、１）の時、ｙは０、１でないｘという値をとることを意味する。
この回路が全体回路の一部となるため、全体回路のＢＤＤを得るのに、この部分回路のＢＤＤを先ず求めるのであるが、図１３（ｂ）に示す真理値表で表される部分回路をＢＤＤ化する。
先ず、ｙの値１に対する行の積和表現は、ｘ１でこれはＢＤＤ化すると図１４（ａ）のようにＢＤＤ化される。これをｆとする。
次いで、ｙの値ｘに対する行の積和表現は、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）で、図１４（ｂ）のようにＢＤＤ化される。これをｇとする。そして、更に、このＢＤＤのリーフ１をｘに置換して、再構築してＢＤＤ化し、これを新たにｇとすると、ｇは図１４（ｃ）のようになる。
次に、得られたＢＤＤｆとＢＤＤｇについて、ＯＲ（ｆ、ｇ）の二項演算を行なうと図１５のようなＢＤＤが得られる。これをｈとする。
得られたＢＤＤｈから真理値表を作成してみれば正しいことが分かる。
このようにして、部分回路の出力が１、０以外に値ｘをもつ場合には、ＢＤＤの作成を行う。
【００１６】
【実施例】
更に具体的に、本発明の組み合せ回路のＢＤＤ演算を応用した機能抽出方法を説明する。
図３（ａ）は本実施例の扱う、部分回路を有する組み合わせ回路を表しており、組み合わせ回路は２個の入力Ａ、Ｂと１個の出力ｙをもつ。図３（ｂ）は図３（ａ）に示す部分回路の真理値表であり、出力ｙ（部分回路の出力でもある）は、０、１の他の値ｘをもつ。
先ず、処理する組み合わせ回路には部分回路があるから、これの真理値表（図３（ｂ））から、真理値表のｙの値１に対する行の積和表現、真理値表のｙの値ｘに対する行の積和表現はそれぞれ、ｘ１、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）となるから、組合せ回路は図４に示すように論理式で示される（展開されるとも言う）。この際、ｘｊに対する行の積和表現の論理式のトップにｘｊに対応するマークＭｊを付けておく。
図４中、Ｄ１、Ｄ２、Ｄ３、Ｄ４は論理素子で、ａ、ｂは、素子Ｄ２、Ｄ３からの出力を示している。
【００１７】
次に、ｘ１のＢＤＤおよび、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）、すなわちｂのＢＤＤを求め、両ＢＤＤをＯＲ演算処理して組み合わせ回路の出力ｙのＢＤＤを求めるが、ｙの論理式をボトムアップで処理する。
入力Ａ、ＢのＢＤＤは、それぞれ図５（ａ）、図５（ｂ）に示すものである。ｘ１はａｎｄ（Ａ、Ｂ）であり、ｘ１のＢＤＤは、図６（ａ）に示す２つのＢＤＤの積（ａｎｄ）であり、これを演算処理して、図６（ｂ）のＢＤＤを得る。ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）を求めるには、予め、ｉｎｖ（ｘ１  ）、ｘ２のＢＤＤをそれぞれ求めておく。
ｉｎｖ（ｘ１）のＢＤＤは、図６（ｂ）に示すＢＤＤのｉｎｖであり、これを演算処理して図７のＢＤＤを得る。
ｘ２のＢＤＤは、図５（ｂ）に示す入力ＢのＢＤＤであり、結局、ａｎｄ（ｉｎｖ（ｘ１）、ｘ２）、即ちｂのＢＤＤは、図７に示すＢＤＤと図５（ｂ）に示すＢＤＤの積（ａｎｄ）であり、これを演算処理して、図８（ｂ）に示すＢＤＤを得る。このＢＤＤ化に際しては、マーク付きであるのでリーフ１をｘに置換して行う。
これより、組合せ回路の出力ｙのＢＤＤは、図９（ａ）に示すように、両ＢＤＤのＯＲとなり、これを演算処理して図９（ｂ）のＢＤＤが得られる。
【００１８】
【発明の効果】
本発明の組み合せ回路のＢＤＤ演算を応用した機能抽出方法は、上記のように組み合わせ回路において、多出力をまとめた表現の機能抽出を可能とするもので、３値以上の真理値表のみを与えられた部分回路を含む回路にも対応できるものとしている。
結局、本発明は、ＢＤＤを用い、高速処理を可能とするもので、且つ、多入力にも対応できるものとしていく
【図面の簡単な説明】
【図１】実施例の組み合わせ回路の機能抽出方法を示した工程概略図
【図２】出力が多数ある場合の出力ＢＤＤ同志の併合（Ｍｅｒｇｅ）を説明するためのフロー図
【図３】実施例の部分回路を有する組み合わせ回路および部分回路の真理値表を示した図
【図４】実施例の組合せ回路を論理素子で展開した図
【図５】入力Ａ、ＢのＢＤＤを示した図
【図６】ｘ１のＢＤＤを得る演算処理を示した図
【図７】ｉｎｖ（ｘ１）ＢＤＤを得る演算処理を示した図
【図８】ｂのＢＤＤを得る演算処理を示した図
【図９】組合せ回路の出力ｙのＢＤＤを得る演算処理を示した図
【図１０】出力ｙ１と出力ｙ２のＢＤＤを示した図
【図１１】併合（Ｍｅｒｇｅ）の手続きの再帰呼び出し過程を説明するための図
【図１２】部分回路の真理値表を積和表現の論理式に変換する仕方を説明するための図
【図１３】２個の入力ｘ１、ｘ２と１個出力ｙとをもつ部分回路とその真理値表を示した図
【図１４】真理値表の積和算表現からＢＤＤを作成する方法を説明するための図
【図１５】ＢＤＤｆとＢＤＤｇについて、ＯＲ（ｆ、ｇ）の二項演算によるＢＤＤを示した図
【図１６】論理関数の図
【図１７】真理値表を示した図
【図１８】ＹをＢＤＤで表現した図
【図１９】共有グラフを説明するための図
【図２０】共有化と冗長点削除を説明するための図
【図２１】規約化されたＢＤＤを示した図
【図２２】論理回路図
【図２３】入力変数Ａ、ＢのＢＤＤｆ、ｇを示した図
【図２４】ＢＤＤの二項演算を説明するための図
【図２５】二項演算により得られたＢＤＤを示した図
【符号の説明】
Ｓ１０〜Ｓ５０                ステップ
Ｓ２０１〜Ｓ２０５            ステップ
Ｄ１〜Ｄ４                    論理素子
【図１】
0003923568.tif 000002
【図２】
0003923568.tif 000003
【図３】
0003923568.tif 000004
【図４】
0003923568.tif 000005
【図５】
0003923568.tif 000006
【図６】
0003923568.tif 000007
【図７】
0003923568.tif 000008
【図８】
0003923568.tif 000009
【図９】
0003923568.tif 000010
【図１０】
0003923568.tif 000011
【図１１】
0003923568.tif 000012
【図１２】
0003923568.tif 000013
【図１３】
0003923568.tif 000014
【図１４】
0003923568.tif 000015
【図１５】
0003923568.tif 000016
【図１６】
0003923568.tif 000017
【図１７】
0003923568.tif 000018
【図１８】
0003923568.tif 000019
【図１９】
0003923568.tif 000020
【図２０】
0003923568.tif 000021
【図２１】
0003923568.tif 000022
【図２２】
0003923568.tif 000023
【図２３】
0003923568.tif 000024
【図２４】
0003923568.tif 000025
【図２５】
0003923568.tif 000026