(57)【要約】【課題】ＣＭＯＳロジック回路よりも小消費電流および小面積を実現し、かつ人手による少しのレイアウト修正で実動作可能なＳＰＬ回路を設計できるパストランジスタ論理回路の合成方法を提供する。【解決手段】中間ノードと終端ノードとを含むＢＤＤの全ノードに初期値を付与し、ノードの値から１を差し引いた値を最大出力信号数で割り、その商に１を加えた値だけ２つある子ノードの各々の値をインクリメントし、そのノードがパストランジスタにマッピングされれば、商の数だけ等価なノードを複製して出力信号を最大出力信号数以下になるように分割する。【選択図】        図１
2004152018.tif 000002
【特許請求の範囲】
【請求項１】
サイズが最適化された二分決定グラフをマッピングして得られるパストランジスタ論理回路において、
各ノードを構成するパストランジスタについて、その出力信号数が最大出力信号数を超えるパストランジスタに関して、その複製を作成して出力信号を分割することを特徴とする、パストランジスタ論理回路の合成方法。
【請求項２】
前記ノードは、それぞれが展開処理によって得られた２つの部分関数を指す枝を有する複数の中間ノードと、枝を有さず展開処理の結果得られた０または１の値を有する終端ノードとを含み、
前記中間ノードと前記終端ノードとを含む二分決定グラフの全ノードに初期値を付与し、
前記ノードの値から１を差し引いた値を最大出力信号数で割り、その商に１を加えた値だけ２つある子ノードの各々の値をインクリメントし、そのノードがパストランジスタにマッピングされれば、商の数だけ等価なノードを複製して出力信号を最大出力信号数以下になるように分割することを特徴とする、請求項１に記載のパストランジスタ論理回路の合成方法。
【請求項３】
サイズが最適化された二分決定グラフをマッピングして得られるパストランジスタ論理回路において、
各ノードを構成するパストランジスタについて、最大直列トランジスタ数を超過しないようにバッファを挿入することを特徴とする、パストランジスタ論理回路の合成方法。
【請求項４】
前記ノードは、それぞれが展開処理によって得られた２つの部分関数を指す枝を有する複数の中間ノードと、枝を有さず展開処理の結果得られた０または１の値を有する終端ノードとを含み、
前記各ノードの２つの枝に関係するパストランジスタの段数を示す値をそれぞれ付与し、
各ノードの２つの枝に関して、子ノードの２つの値を取得し、２つの値のうち小さくない方の値を一方の新たな値とし、その値に１を加えた値を他方の値として付与し、付与された新たな値が所定数を超えていれば、そのノードの入力側にバッファ回路を挿入することを特徴とする、請求項３に記載のパストランジスタ論理回路の合成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はパストランジスタ論理回路の合成方法に関し、特に、ノードと枝からなる二分決定グラフ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ；以下、ＢＤＤと称する。）を用いて論理関数または部分集合を表現する際に、実動作可能性を目的とした修正を短時間で実行するアルゴリズムのようなパストランジスタ論理回路の合成方法に関する。
【０００２】
【従来の技術】
ＢＤＤについては、特開平６―２１５０６５号公報に記載されており、図７に示すように、３つの入力変数に対してｘ３、ｘ２、ｘ１という固定した順序が与えられている。展開処理入力変数の１つに０および１の論理値を代入することにより、論理関数から２つの部分関数が導出される。たとえば、入力変数ｘ３に０および１を代入することによって、２つの部分関数が導出される。
【０００３】
二分木グラフ生成処理順序付け処理によって与えられた順序にしたがって、展開処理をすべての入力変数について繰り返し、図７に示すような二分木グラフを生成する。図７において○は中間ノードを示し、□は終端ノードを示す。中間ノードは個々の展開処理に対応するもので、展開処理によって得られた２つの部分関数を指す０枝と１枝の２本の枝を持っている。慣用的には、各ノードの根元から左下へ延びている枝が０枝であり、右下へ伸びている枝が１枝である。また、終端ノードは、一連の展開処理の結果として得られた０または１の論理値を表している。
【０００４】
共有化処理は、図８（ａ）に示すように、第１の中間ノード１１から出た０枝と第２の中間ノード１２から出た０枝が同じ中間ノード１３を指し、かつこれら第１および第２の中間ノード１１および１２は図８（ｂ）に示すように共有化され、１つの中間ノード１５にまとめられる。
【０００５】
非冗長化処理は、図９（ａ）に示すように、第１の中間ノード１７から出た０枝および１枝が、同じ第２の中間ノード１８を指しているときには図９（ｂ）に示すように第１の中間ノード１８に直結する。これらの共有化処理と非冗長化処理とによって図７に示す二分木グラフは図１０に示す二分決定グラフに圧縮される。このように、ＢＤＤを用いて論理関数を表現でき、集合データの表現にも用いることができる。
【０００６】
【特許文献】
特開平６―２１５０６５号公報（段落番号０００３〜００１０、図１〜図４）
【０００７】
【発明が解決しようとする課題】
上述のＢＤＤをマッピングしてＳｉｎｇｌｅ−ｒａｉｌ  Ｐａｓｓ−Ｔｒａｎｓｉｓｔｏｒ  Ｌｏｇｉｃ：以下ＳＰＬと称する）を合成する際に、出力信号が多数接続されたＭＯＳトランジスタが存在することがある。このようなロジック回路において、出力信号が多数接続されたＭＯＳトランジスタが存在することは、その遅延時間のために指定したクロック周波数で実動作が不可能になる原因の１つになっており、論理的等価性を維持しながら、回路内のすべてのＭＯＳトランジスタに対して、出力信号の数が設計者の指定する最大出力信号数以下になるように出力分割アルゴリズムを用いて修正を行う必要がある。
【０００８】
しかし、このような出力分割アルゴリズムを用いて修正されたＢＤＤをマッピングして得られるＳＰＬ回路には、直列接続された多数のトランジスタを含んでいる場合がある。これに対して、バッファ挿入アルゴリズムを用いて一定の間隔で挿入したときよりも少ないバッファ回路で、設計者が制約条件として課す最大直列トランジスタ数を超過しないＳＰＬ回路に修正する必要がある。
【０００９】
それゆえに、この発明の主たる目的は、ＣＭＯＳロジック回路よりも小消費電流および小面積を実現し、かつ人手による少しのレイアウト修正で実動作可能なＳＰＬ回路を設計できるパストランジスタ論理回路の合成方法を提供することである。
【００１０】
【課題を解決するための手段】
この発明は、サイズが最適化された二分決定グラフをマッピングして得られるパストランジスタ論理回路において、各ノードを構成するパストランジスタについて、その出力信号数が最大出力信号数を超えるパストランジスタに関して、その複製を作成して出力信号を分割することを特徴とする。
【００１１】
また、ノードは、それぞれが展開処理によって得られた２つの部分関数を指す枝を有する複数の中間ノードと、枝を有さず展開処理の結果得られた０または１の値を有する終端ノードとを含み、中間ノードと終端ノードとを含む二分決定グラフの全ノードに初期値を付与し、ノードの値から１を差し引いた値を最大出力信号数で割り、その商に１を加えた値だけ２つある子ノードの各々の値をインクリメントし、そのノードがパストランジスタにマッピングされれば、商の数だけ等価なノードを複製して出力信号を最大出力信号数以下になるように分割することを特徴とする。
【００１２】
他の発明は、サイズが最適化された二分決定グラフをマッピングして得られるパストランジスタ論理回路において、各ノードを構成するパストランジスタについて、最大直列トランジスタ数を超過しないようにバッファを挿入することを特徴とする。
【００１３】
また、ノードは、それぞれが展開処理によって得られた部分関数を指す２つの枝を有する複数の中間ノードと、枝を有さず展開処理の結果得られた０または１の値を有する終端ノードとを含み、各ノードの２つの枝に関係するパストランジスタの段数を示す値をそれぞれ付与し、各ノードの２つの枝に関して、子ノードの２つの値を取得し、２つの値のうち小さくない方の値を一方の新たな値とし、その値に１を加えた値を他方の値として付与し、付与された新たな値が所定数を超えていれば、そのノードの入力側にバッファ回路を挿入することを特徴とする。
【００１４】
【発明の実施の形態】
図１はこの発明の一実施形態の出力分割アルゴリズムを適用した例を示す図であり、特に、図１（ａ）はノードの出力信号が最大出力信号数を超えている例であり、図１（ｂ）は最大出力信号数を超えているノードの複製を作成し、出力信号を分割した例を示す。図１（ａ）○で示す中間ノード２１〜２８はスイッチ回路素子であり、□で示す非端末ノード３１，３２はそれぞれグランド（ＧＮＤ），電源である。各ノード２１〜２８の根元から延びている枝のうち点線は０枝であり、実線は１枝である。
【００１５】
ノード２１は０枝側が電源のノード３１に接続され、１枝側がグランドのノード３２に接続され、ノード２２は０枝側がグランドのノード３２に接続され、１枝側が電源のノード３１に接続されている。ノード２３は０枝側が初段のノード２１の出力に接続され、１枝側が初段のノード２２の出力に接続され、ノード２４は０枝側が初段のノード２２の出力に接続され、１枝側が初段のノード２１の出力に接続されている。ノード２５は０枝側が初段のノード２２の出力に接続され、１枝側が電源のノード３１に接続され、ノード２６は０枝側がＧＮＤのノード３２に接続され、１枝側が初段のノード２２の出力に接続されている。
【００１６】
ノード２７は０枝側が２段目のノード２４の出力に接続され、１枝側が２段目のノード２３の出力に接続され、ノード２８は０枝側が２段目のノード２６の出力に接続され、１枝側が２段目のノード２５の出力に接続されている。そして、入力信号ａ，ｂ，ｃに応じて、ノード２８からａｂ＋ａｃ＋ｂｃ、ノード２７からａｂｃ＋ａ´ｂ´ｃ＋ａ´ｂｃ´＋ａｂ´ｃ´の論理演算信号が出力される。
【００１７】
図１（ａ）において各ノード２１〜２８，３１，３２に示されている数字は、出力信号数である。この出力信号数が最大出力信号数たとえば「３」を超えると、動作が不安定になるものとして説明する。図１（ａ）に示したノード２２の最大出力信号数が「４」であり、「３」を超えている。そこで、出力分割アルゴリズムによって図１（ｂ）に示すように、ノード２２を複製した新たなノード２９を作成し、出力信号を分割する。このノード２９は０枝側がＧＮＤのノード３２に接続され、１枝側が電源のノード３１に接続され、出力はノード２６の１枝側に接続されている。
【００１８】
図２は図１のＢＤＤ構成要素に対応するパストランジスタ論理回路構成要素を示す図である。図１（ａ）に示したＢＤＤの各ノードは図２（ａ）に示すように２つの入力Ａ，Ｂと出力Ｙとを有しており、このノードは図２（ｂ）に示すように２つのＭＯＳトランジスタＴ１，Ｔ２の対からなるパストランジスタで構成される。ＭＯＳトランジスタＴ１，Ｔ２は２−１マルチプレクサを構成しており、それぞれのソースが入力Ａ（０枝），Ｂ（１枝）となり、各ドレインは共通接続されて出力Ｙとなり、各ゲートにはＳ´，Ｓ信号が与えられる。ここでＳは論理信号であり、Ｓ´はＳの論理否定信号である。論理信号Ｓが「Ｈ」レベルであれば入力Ｂが出力Ｙに現れ、論理否定信号Ｓ´が「Ｈ」レベルであれば入力Ａが出力Ｙとして現れる。
【００１９】
出力分割アルゴリズムでは、ＳＰＬ回路内のすべてのＭＯＳトランジスタについて、その出力信号の数が最大出力信号数以下になるように修正が行われる。そのアルゴリズムでは、出力信号の数が最大出力信号数よりも大きいＭＯＳトランジスタの対に関して、その複製を作成して出力信号を分割するという操作が行われる。出力分割アルゴリズムはＢＤＤのデータ上で実行可能であり、図３はその出力信号を分割するアルゴリズムを示すフローチャートである。
【００２０】
図３に示すステップ（図示ではＳＰと略称する）ＳＰ１において、図１（ａ）に示すＢＤＤの全ノード２１〜２８、３１，３２に初期値を付与する。モノリシックなＢＤＤに対しては、通常、ルートに値「１」、それ以外のノードに値「０」が付与される。ただし、マルチレベルＢＤＤなどに見られるように、ＢＤＤのノードからの出力を入力信号として利用する場合、設計者が初期値を適切に定める必要がある。図１（ａ）の各ノード２１〜２８，３１，３２の横に示されている数値は出力分割アルゴリズムを適用した後の出力信号数である。
【００２１】
ステップＳＰ２において、ノードの値から「１」を差し引いた値を最大出力信号数で除算する。ステップＳＰ３において、除算した商に「１」を加えた値だけ２つある子ノード各々の値をインクリメントする。たとえば、図１（ａ）に示すノード２３の値「１」から「１」を引いた値「０」を最大出力信号数「３」で割り、その商に「１」を加えた値「１」だけ２つある子ノード２１，２２の値をインクリメントする。そして、ステップＳＰ４において、そのノードがＭＯＳトランジスタの対にマッピングされるものであれば、商の数だけ等価なノードを複製して出力信号を最大出力信号数以下になるように分割する。
【００２２】
この結果、図１（ａ）に示すようにノード２２の出力信号数が最大出力信号数を超えていても、図１（ｂ）に示すようにノード２２を複製したノード２９を作成し、出力信号を分割することにより、すべてのノードの出力信号数を最大出力信号数以下にすることができる。
【００２３】
上述の実施形態では出力信号数が最大出力信号数を超えていれば、ノードを複製して出力信号を分割するようにしたが、これに限ることなく各ノードの途中にバッファ回路を挿入するようにしてもよい。次に、そのような実施形態について説明する。
【００２４】
図４はこの発明の他の実施形態におけるバッファ挿入アルゴリズムを示す図であり、図１（ｂ）に示したＢＤＤに適用した結果を図４（ａ）に示しており、図４（ｂ）はバッファの挿入位置を示す。
【００２５】
この実施形態によるバッファ挿入アルゴリズムでは、設計者が制約条件として課す最大直列トランジスタ数を超過しないように、ＳＰＬ回路にバッファ挿入が行われる。ただし、「ＳＰＬ回路に対して直列トランジスタ数がある数を超えないように最少数のバッファを挿入する配置を求める」という問題はＮＰ困難なクラスに属するため、厳密にその配置を求めることは現実的でない。したがって、シミュレーテッドアニーリング法、タブーサーチなどの現実的な時間内に終了可能な最適化アルゴリズムによって挿入するバッファの位置を求める。
【００２６】
バッファ挿入の配置に関する最適化アルゴリズムには、最大直列トランジスタ数制約を満たさない配置であってもその有効性を点数付けできる方法があると都合がよい。そこで、回路内にある図４に示すＭＯＳトランジスタ各々について制約を満たすか否かを調べる直列トランジスタ数算出アルゴリズムを用いる。このアルゴリズムはＢＤＤ上で実行可能であり、そのフローチャートを図５に示す。
【００２７】
図５に示すステップＳＰ１１において、図４（ａ）に示す各ノード２１〜２８，３１，３２に２つの値ｐｌ０、ｐｌ１を付与する。それらの値は関係するＭＯＳトランジスタを含む直列トランジスタにおいて何段目にあるかを意味する。ｐｌ０はＢＤＤをＳＰＬ回路にマッピングしたときに０枝側にあるＭＯＳトランジスタに対する値であり、ｐｌ１は１枝側のＭＯＳトランジスタに対する値である。初期設定数値は表１のように定められる。ただし、ＢＤＤがモノリシックでない場合、初期値を適切に定める必要がある。
【００２８】
【表１】
2004152018.tif 000003
すなわち、図４（ａ）に示すノード３１は電源を表しているためｐｌ０，ｐｌ１として０，０が設定され、ノード３２はグランドを表すため−１，−１が設定されている。ノード２１は０枝側が電源のノード３１に接続され、１枝側がグランドのノード３２に接続されているので１，−１に設定され、ノード２２，２９はともに０枝側がグランドのノード３２に接続され、１枝側が電源のノード３１に接続されているので−１，１に設定されている。
【００２９】
ノード２３は０枝側が初段のノード２１の出力に接続され、１枝側が初段のノード２２の出力に接続されているので２，２に設定され、ノード２４は０枝側が初段のノード２２の出力に接続され、１枝側が初段のノード２１の出力に接続されているので２，２に設定されている。ノード２５は０枝側が初段のノード２９の出力に接続され、１枝側が電源のノード３１に接続されているので２，１に設定され、ノード２６は０枝側が電源のノード３１に接続され、１枝側が初段のノード２９の出力に接続されているので−１，２に設定されている。
【００３０】
ノード２７は０枝側が２段目のノード２４の出力に接続され、１枝側が２段目のノード２３の出力に接続されているので３，３に設定されている。ノード２８は０枝側が２段目のノード２６の出力に接続され、１枝側が２段目のノード２５の出力に接続されているので３，３に設定されている。
【００３１】
前述のごとくｐｌ０、ｐｌ１はＭＯＳを含む直列トランジスタにおいて何段目にあるかを意味しているので、たとえば図４（ａ）に示すノード２７，２８には０枝側，１枝側ともに３個のトランジスタが直列接続されていることになる。
【００３２】
ステップＳＰ１２において、ＢＤＤのルートから再帰的な深さ優先探索をしながら以下に示す処理を行う（ただし、重複探索は行わない）。処理の内容は、行きがけに探索済みを表すマークを付け、帰りがけに０枝側の子ノードのｐｌ０，ｐｌ１のうち、小さくない方に１を加えたものをノードｐｌ１とする。
【００３３】
ここで、一例としてノード２３，２４におけるｐｌ０，ｐｌ１の算出過程について説明する。ノード２３における０枝の子ノード２１のｐｌ０，ｐｌ１のうちの小さくない方は１であり、それに１を加えた２が求める値となる。同様に、１枝の子ノード２２のｐｌ０，ｐｌ１のうちの小さくない方は１であり、それに１を加えた２が求める値となる。その結果、ノード２３には、２，２が付与される。
【００３４】
ノード２４における０枝の子ノード２２のｐｌ０，ｐｌ１のうちの小さくない方は１であり、それに１を加えた２が求める値となる。同様に、１枝の子ノード２１のｐｌ０，ｐｌ１のうちの小さくない方は１であり、それに１を加えた２が求める値となる。その結果、ノード２４には２，２が付与される。
【００３５】
図４（ａ）において、ノード２８にはｐｌ１、ｐｌ０として３，３が付与されており、３個ずつトランジスタが接続されている。したがって、ステップＳＰ１３において取得される回路の最大直列トランジスタ数が「３」になるので、最大直列トランジスタ数が「２」に定められている場合にはその個数を減らすためにバッファ回路を挿入する。図４（ｂ）に示すようにノード２９とノード２５，２６との間にバッファ回路Ｂ１，Ｂ２を接続するものとする。バッファ回路Ｂ１が接続されたことにより、ノード２５の０枝側は表１の初期設定数値より、バッファ回路が接続されているＭＯＳに関係する変数が１に設定され、１枝側は電源のノード３２に接続されているので１のままである。また、ノード２６の０枝側はグランドのノード３２が接続されているのでＭＯＳに関係する変数が−１に設定され、１枝側はバッファ回路Ｂ２の出力に接続されているので１に設定される。これにより、ノード２８の変数は２，２となり、直列接続されたＭＯＳトランジスタの個数が減ったことになる。
【００３６】
上述のごとく、すべてのｐ１０、ｐ１１の最大値が、バッファ回路の挿入されたＳＰＬ回路が含む直列トランジスタの最大数になり、この値が設計者の課す最大直列トランジスタ数以下ならば、このＳＰＬ回路は制約を果たす。また、非端末ノードに関係するｐｌ０およびｐｌ１のうち最大直列トランジスタ数以下になるものの個数は制約を満たすＭＯＳトランジスタの個数にほかならない。
【００３７】
図５は図４（ｂ）ＢＤＤに対応するパストランジスタ論理回路を示す図である。図４（ｂ）に示した各ノード２１〜２９は、それぞれが２−１のマルチプレクサＵ１〜Ｕ９を構成するパストランジスタＴ１１，Ｔ１２〜Ｔ２７，Ｔ２８の組合せで構成されている。すなわち、マルチプレクサＵ１のパストランジスタＴ１１，Ｔ１２各ゲートには入力信号ｃ´，ｃが与えられており、一方のパストランジスタＴ１１のソースは電源ＶＤＤに接続され、他方のパストランジスタＴ１２のソースはグランドに接続され、各ドレインはノードＮ１に共通接続されている。マルチプレクサＵ２のパストランジスタＴ１３，Ｔ１４の各ゲートには入力信号ｃ´，ｃが与えられており、一方のパストランジスタＴ１３のソースはグランドに接続され、他方のパストランジスタＴ１４のソースは電源ＶＤＤに接続され、各ドレインはノードＮ３に共通接続されている。マルチプレクサＵ９のパストランジスタＴ２７，Ｔ２８の各ゲートには入力信号ｃ´，ｃが与えられており、一方のパストランジスタＴ２７のソースはグランドに接続され、他方のパストランジスタＴ２８のソースは電源ＶＤＤに接続され、各ドレインはノードＮ２に共通接続されている。
【００３８】
マルチプレクサＵ３のパストランジスタＴ１５，Ｔ１６の各ゲートには入力信号ｂ１´，ｂ１が与えられており、一方のパストランジスタＴ１５のソースはノードＮ１に接続され、他方のパストランジスタＴ１６のソースはノードＮ３に接続され、各ドレインはノードＮ４に共通接続されている。マルチプレクサＵ４のパストランジスタＴ１７，Ｔ１８の各ゲートには入力信号ｂ´，ｂが与えられており、一方のパストランジスタＴ１７のソースはノードＮ３に接続され、他方のパストランジスタＴ１８のソースはノードＮ１に接続され、各ドレインはノード５に共通接続されている。
【００３９】
マルチプレクサＵ５のパストランジスタＴ１９，Ｔ２０の各ゲートには入力信号ｂ´，ｂが与えられており、一方のパストランジスタＴ１９のソースはバッファ回路Ｂ１の出力に接続され、バッファ回路Ｂ１の入力はノードＮ２に接続されている。パストランジスタＴ２０のソースは電源ＶＤＤに接続され、各ドレインはノードＮ６に共通接続されている。マルチプレクサＵ６のパストランジスタＴ２１，Ｔ２２の各ゲートには入力信号ｂ´，ｂが与えられており、一方のパストランジスタＴ２１のソースはグランドに接続され、他方のパストランジスタＴ２２のソースはバッファ回路Ｂ２の出力に接続され、バッフア回路Ｂ２の入力はノードＮ２に接続され、各ドレインはノードＮ７に共通接続されている。
【００４０】
マルチプレクサＵ７のパストランジスタＴ２３，Ｔ２４の各ゲートには入力信号ａ´，ａが与えられており、各ドレインは出力信号ａｂｃ＋ａ´ｂ´ｃ＋ａ´ｂｃ´＋ａｂ´ｃ´を導出する。マルチプレクサＵ８のパストランジスタＴ２５，Ｔ２６の各ゲートには入力信号ａ´，ａが与えられており、各ドレインは出力信号ａｂ＋ａｃ＋ｂｃを導出する。
【００４１】
図面を参照してこの発明の一実施形態を説明したが、本発明は、図示した実施形態に限定されるものではない。本発明と同一の範囲内において、または均等の範囲内において、図示した実施形態に対して種々の変更を加えることが可能である。
【００４２】
【発明の効果】
以上のように、この発明によれば、出力分割アルゴリズムとバッファ挿入アルゴリズムを含む修正アルゴリズムによって、ＣＭＯＳロジック回路よりも小消費電流および小面積を実現し、かつ人手による少しのレイアウト修正で実動作可能なＳＰＬ回路を設計できる。
【００４３】
この修正アルゴリズムは、実動作を単純化したモデルに基づいているため、真の最適解を得ることは難しいが、アルゴリズムの実行時間が短いという長所があり、限られた開発期間の中での利用に向いている。
【図面の簡単な説明】
【図１】この発明の一実施形態の出力分割アルゴリズムを適用した例を示す図である。
【図２】図１のＢＤＤ構成要素に対応するパストランジスタ論理回路構成要素を示す図である。
【図３】出力分割アルゴリズムを示すフローチャートである。
【図４】この発明の他の実施形態におけるバッファ挿入アルゴリズムを示す図である。
【図５】バッファ挿入の配置に関する最適化アルゴリズムに必要な最大直列トランジスタ数算出アルゴリズムを示すフローチャートである。
【図６】図４（ｂ）のＢＤＤに対応するパストランジスタ論理回路を示す図である。
【図７】二分木グラフ生成処理順序付け処理によって与えられた二分木グラフである。
【図８】共有化した二分木グラフを示す図である。
【図９】非冗長化処理により中間ノードを直結した例を示す図である。
【図１０】圧縮されたＢＤＤを示す図である。
【符号の説明】
２１〜２９，３１，３２，Ｎ１〜Ｎ７  ノード、Ｂ１，Ｂ２  バッファ回路、Ｔ１，Ｔ２  ＭＯＳトランジスタ、Ｔ１１〜Ｔ２８  パストランジスタ。
【図１】
2004152018.tif 000004
【図２】
2004152018.tif 000005
【図３】
2004152018.tif 000006
【図４】
2004152018.tif 000007
【図５】
2004152018.tif 000008
【図６】
2004152018.tif 000009
【図７】
2004152018.tif 000010
【図８】
2004152018.tif 000011
【図９】
2004152018.tif 000012
【図１０】
2004152018.tif 000013