JPH0310377A - 論理回路生成方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は論理回路の設計における自動論理合成技術に係
わり、特に高品質の回路の合成に必要な論理回路生成方
法に関するものである。

従来の技術 従来の論理回路生成方法の中で用いられてきた論理最小
化手法として、古くから研究され実用化が進められてき
たものに２段論理の簡単化アルゴリズムがある。このよ
うなアルゴリズムとしてクワイン・マフラスキ法（ＱＭ
法）やＭＩＮＩ、ＥＳＰＲＥＳＳＯ等が有名である。Ｑ
Ｍ法は結果が最小解になることが保証されているカミ　
回路規模とともに処理時間が指数関数的に増大していく
ので大規模な回路には使用できない。そこでヒュリステ
イクスを用いることにより、必ずしも最小解が得られる
とは限らない力丈　実用的な処理時間内に最小解に近い
解が得られるようにしたものがＭＩＮＩやＥＳＰＲＥＳ
ＳＯである。これらのアルゴリズムは扱える回路規模や
出力する解の品質からみて現状でも十分実用レベルに達
している。

ＥＳＰＲＥＳＳＯについて（よ　クルーワーアカデミッ
クパブリシャーズ−ｆＬ　　ロジック　ミニマイゼイシ
ョンアルゴリズムズフオープイ・エル・ニス・アイ　シ
ンセシス（１９８４年）（Ｋｌｕｗｅｒ　Ａｃａｄｅｍ
ｉｃＰｕｂｌｉｓｈｅｒｓ、Ｌｏｇｉｃ　Ｍｉｎｉｍｉ
ｚａｔｊ、ｏｎ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒＶＬＳ
Ｉ　５ｙｎｔｈｅｓｉｓ（１９８４））に詳しく述べら
れている。

２段論理の簡単化に関連して、出力する解の品質をかな
り改善できる手法として出力極性の最適化がある。従来
　出力極性最適化方法として以下の方法が提案されてき
九 （１）全での出力極性の組合せに対して入力された２段
論理関数の簡単化を行（＼　その中で結果が最良のもの
を探す方法 （２）■出力ごと独立にそのまま簡単化した場合とその
否定を簡単化した場合とて結果を比較して極性を決定す
る方嵐 （３）入力された２段論理関数をもと置　出力とその否
定をともに実現する２重極性特性関数を作り、それを簡
単化した後、積項数が最小になる出力極性の組合せを探
す方嵐 これらの方法を比較すると、　（１）は必ず最適な出力
極性が得られることが保証されているバ処理時間が出力
数とともに指数関数的に増大していくので大規模な回路
には使用できなしも（２）は処理時間が出力数にリニア
に増大するので大規模な回路にも使用できる力＜　１出
力ごと独立に最適化を行うので関数全体として結果が最
適になるとは限らない。

（３）は論理の簡単化を一度行うだけなので実用的な処
理時間内に準最適な出力極性を得ることができる。この
方法について（よ　アイ・イー・イ・イー、　トランザ
クションオンコンピューターズ、　シー３３．ナンバー
１０（１９８４年）第８７９頁から第８９４頁（ＩＥＥ
Ｅ、　Ｔｒａｎｓ、　ｃｏｍｐｕｔｅｒｓ、　ｖｏｌ、
　ｃ−３３，ｎｏ、　１０（１９８４）ＰＰ８７９−８
９４）に論じられている。　２段論理関数はＰＬＡ　（
プログラミング・ロジック・アレイ）を用いて直接実現
できるた八　これらのアルゴリズムはＰＬＡの面積を削
減したり、市販のＰＬＡチップで実現できるように論理
を圧縮したい時などに有効に用いられている。しかしな
がら通常の論理設計において（よ　論理回路は面積効率
や遅延時間の制約から、　２段論理回路ではなく多段論
理回路として実現される。自動論理合成においても多段
論理回路を合成する必要があり、＼多段論理の最小化手
法が重要である。従来　多段論理回路の合成は困難なも
のと考えられてきたカミ　ここ数年の研究によりかなり
良い品質の回路を合成できるようになつれ　従来の多段
論理合成システムとして、アイ・イー・イー・イー、プ
ロシーデイングオブインタナショナルシンポジウムオン
サーキット　アンドシステム（１９８６）、第３５６頁
から第３５９頁（ＩＥＥＥ、　Ｐｒｏｃ、Ｓｙｍｐ、　
Ｃ１ｒｃ、　５ｙｓｔ、　（１９８６）ＰＰ３５６−３
５９）に述べられているＭＩＳが有名である。ＭＩＳに
はいくつかの多段論理最小化手法が組込まれており、そ
れらの最小化手法を入力された論理関数に適用すること
によって、最小化された多段論理を得ることができる。

第５図にＭＩＳの典型的な処理フロー図を示す。４１と
４５は論理関数の各出力変数（もしくは中間変数）ごと
に独立に因数分解を行うステップ、４２と４４は論理関
数の各出力変数（もしくは中間変数）ごとに独立に論理
の簡単化を行うステップ、４３は論理関数の複数の出力
変数（もしくは中間変数）に対応する論理式の間で共通
の因子があればそれを抽出するステップ、４４は複数の
積項間に共通の入力があればそれを抽出するステップで
ある。このようなＭＩＳの処理フローにおいて（よ　入
力された論理関数は因数分解ステップ０− ４１とそれに続く多段簡単化ステップ４２によって各出
力変数（もしくは中間変数）ごとに独立に最小化された
後、共通因子抽出ステップ４３．多段簡単化ステップ４
４．因数分解ステップ４５によって共通因子を優先した
因数分解が行われ　最後に共通入力抽出ステップ４６に
よって回路中のゲートの共通部分のくくり出しが行われ
る。このようにＭＩＳでは入力された論理関数を一且　
２段論理に展開することなく、多段論理のままで最小化
が行われる。ここでは複数の出力変数（もしくは中間変
数）間の論理の冗長性を取り除く大域的最適化は共通因
子抽出ステップ４３と共通入力抽出ステップ４６によっ
て実現される。ＭＩＳの持つ多段論理最小化手法のうち
、共通因子抽出ステップ（戴　２つの出力変数（もしく
は中間変数）に対応する論理式の因子をそれぞれ求へ　
それらの間の共通要素を捜し　新たな中間変数としてく
くり出すことによって実現されている。第６図に共通因
子抽出処理の例を示す。以下、記述する全ての論理式に
おいて、”　ａ＝ｂ″はａとｂが論理的に等価であるこ
と、ａ’ｂ’　はａとｂの論理積’ａ＋ｂ’はａとｂの
論理私　″　ａ＠ｂ″はａとｂの排他的論理和′　ａ′
はａの否定を表すものとする。論理関数５１の出力変数
Ｘの因子はに１＝ａ＋ｂ＋ｃであり、同じく出力変数Ｙ
の因子はに２＝ａ＋ｂである。

Ｋ１とに２の共通要素であるａ＋ｂが出力変数ＸとＹの
共通因子であり、これを中間変数Ｚとしてくくり出した
結果が論理関数５２である。ま？Ｑ　　ＭＩＳの因数分
解ステップに（よ　各出力変数（もしくは中間変数）に
対応する論理式の因子を１つだけ求めるものと、全ての
因子を計算しその中から最適な因子を求めるものが用意
されている。後者は前者に比べて処理時間はかかるカミ
　結果は高品質である。第６図の例では論理関数５２の
出力変数Ｘが因数分解されて論理関数５３に変換されて
いる。

この場合、因子はＺ＋ｃのみである。出力変数Ｙと中間
変数Ｚには因子は存在しない。

発明が解決しようとする課題 以上述べたように　論理回路生成方法の中で用いられる
論理最小化手法には大きく分けて２段論１ ２− 埋置小化手法と多段論理最小化手法とがあり、それぞれ
に長所と短所がある。　２段論理最小化手法はＰＬＡの
ような２段論理回路の設計には有効であり、ＡＮＤＮ−
ゲート間くの共通入力が存在するため多段論理としては
冗長である。一般の論理回路は通電　多段論理で実現さ
れるためへ　２段論理最小化手法のみを用いて設計する
と結果の回路規模が大きくなってしまう。一方、ＭＩＳ
のような多段論理最小化手法のみによっては取り除くこ
とが困難な論理的冗長性が存在する。すなわち、このよ
うなシステムで（よ　通常、多段論理回路を部分回路で
ある１出力の２段論理回路を接続したものとして処理し
ており、多段簡単化処理も各部分回路ごとに独立に行わ
れるため４Ｑ　　複数の部分回路にまたがって論理的冗
長性が存在する場合にはそれらを簡単化処理によって取
り除くことは困難である。ＭＩＳではこのような問題点
を、　（１）多段論理を局所的に２段論理に展開する方
法、　（２）入力と中間変数の間のドントケア条件を作
砥利用する方法、によって解決しようとしているバこれ
らの方法で完全な簡単化を行おうとすると処理効率が悪
くなる。また　現状では多段論理のままで出力極性を最
適化する有効なアルゴリズムは得られていない。従って
、ある出力を実現するよりもその否定を実現した方が回
路規模が小さくなるような場合で耘　それを判定する方
法を持たないため番へ　　規模の大きな回路を合成して
しまうことになる。その上　従来の多段論理最小化手法
で１よ　因子とその否定の抽出も　排他的論理和の抽出
には特別な注意が払われていなかっ九　このような共通
因子や排他的論理和の抽出は回路規模削減に大きな効果
がある。また　従来の出力極性最適化手法は２段論理回
路を対象としていたたム積項数が最小になる出力極性を
選択していたカミ一般の多段論理回路を扱う場合には積
項数が最小になっても多段化した後で必ずしも回路規模
が小さくなるとは限らなｌ、％　　本発明はかかる問題
点に鑑へ　２段論理最小化手法と多段論理最小化手法を
うまく組み合わせるととも番へ　　従来の論理最小化手
法になかった新たな機能を付加することによ３− ４ リ、高性能の論理回路生成方法を提供することを目的と
する。

課題を解決するための手段 本発明（よ　与えられた論理関数を実現する論理回路を
生成する論理回路生成方法であり、多段論理関数を２段
論理関数に展開する２段論理展開手段と、前記２段論理
関数の最適出力極性を求める出力極性最適化手段と、前
記２段論理関数を簡単化するｄ没論理簡単化手段と、論
理関数の複数の出力変数（もしくは中間変数）に対応す
る論理式の間の共通積項を中間変数としてくくり出す共
通積項抽出手段と、論理関数の複数の出力変数（もしく
は中間変数）に対応する論理式の間の共通因子を中間変
数としてくくり出す共通因子抽出手段と、論理関数の各
出力変数（および中間変数）に対応する論理式をそれぞ
れ独立に因数分解する因数分解手段と、論理関数に含ま
れる複数の積項間の共通入力を中間変数としてくくり出
す共通入力抽出手段とを有し　入力された論理関数を前
記２段論理展開手段により２段論理関数に展開し　次５
− に前記出力極性最適化手段により前記２段論理関数の最
適出力極性を求取　次に前記２段論理簡単化手段により
、前記２段論理関数を前記最適出力極性のもとで簡単化
し　次に前記共通積項抽出手段により、複数の出力変数
に対応する論理式の間に共通の積項があれば中間変数と
してくくり出し次に前記共通因子抽出手段により、複数
の出力変数（もしくは中間変数）に対応する論理式の間
に共通の因子があれば中間変数としてくくり出し次に前
記因数分解手段により、各出力変数（および中間変数）
に対応する論理式をそれぞれ独立に因数分解し　次に前
記共通入力抽出手段により、論理関数に含まれる複数の
積項間に共通の入力があれば中間変数としてくくり出す
ことにより、与えられた論理関数を別の論理関数に変換
してから実現する論理回路生成方法である。また本発明
（よ２段論理関数の最適出力極性を求める出力極性最適
化方法であり、入力された２段論理関数の各出力に対応
する論理とその否定論理を表現する出力を共に有する２
段論理関数である２重極性特性関６− 数を生成する２重極性特性関数生成手段と、前記２重極
性特性関数生成手段の結果得られた２重極性特性関数を
簡単化する２重極性特性関数簡単化手段と、前記２重極
性特性関数簡単化手段により簡単化された２重極性特性
関数を用いて、必要な積項数が小さくなる順にいくつか
の出力極性を選択する最適出力極性候補選択手段と、前
記最適出力極性候補選択手段により選択された各々の出
力極性のもとで前記入力された２段論理関数の簡単化を
行う２段論理簡単化手段と、前記２段論理簡単化手段の
結果得られた２段論理関数の総接続数を計算し　総接続
数が最小になる出力極性を求める最適出力極性選択手段
とを有する出力極性最適化方法である。また本発明は論
理関数の複数の出力変数（もしくは中間変数）に対応す
る論理式の間に共通の因子があれば中間変数としてくく
り出す共通因子抽出方法であり、論理関数の出力変数（
もしくは中間変数）に対応する論理式の因子を計算し求
める手段と、前記因子の否定を計算し求める手段と、前
記因子かあるいは前記因子の否定が前記論理関数の別の
出力変数（もしくは中間変数）に対応する論理式の因子
になっているかどうかを検査する手段とを有し　ある出
力変数（もしくは中間変数）に対応する論理式の因子の
否定が別の出力変数（もしくは中間変数）に対応する論
理式の因子になっていれば　共通因子としてくくり出す
共通因子抽出方法である。また本発明は論理関数の各出
力変数（もしくは中間変数）に対応する論理式の因子の
中から最適な因子をくくり出す論理関数の因数分解方法
であり、論理関数の出力変数（もしくは中間変数）に対
応する論理式の因子を計算し求める手段と、前記因子の
中から排他的論理和になるものを探す手段とを有し　論
理関数の出力変数（もしくは中間変数）に対応する論理
式の因子の中に排他的論理和になるものがあれば優先し
てくくり出す因数分解方法である。

作用 本発明における論理回路生成方法では　入力された論理
関数を一旦　２段論理に変換し　最適出力極性を求めた
後、その出力極性のもとで論理の７− 簡単化を行う。その結果、出力極性最適化を含めて２段
論理として最小化された関数が得られる。

その後、　２段論理関数の複数の出力変数に対応する論
理式の間に共通の積項があればそれを中間変数としてく
くり出した後、複数の出力変数（もしくは中間変数）に
対応する論理式の間に共通の因子があればそれを新たな
中間変数としてくくり出す。その後、各出力変数（もし
くは中間変数）に対応する論理式を独立に因数分解した
後、複数の積項間に共通の入力があればそれを中間変数
としてくくり出も　このように−旦　２段論理に変換し
て最小化を行うた八　従来の多段論理最小化手法では取
り除（こと・が困難であった論理的冗長性を効率的に取
り除°くことができる。また２段論理に変換することに
より、多段論理では困難であった出力極性最適化が可能
になつ九　さらに２段論理最小化に続く高性能の多段化
処理によって、前記２段論理回路を高品質な多投論理回
路に変換することができる。これにより本発明における
論理回路生成方法を用いて一般的な多段論理回路を極９
− めて高品質に設計することができる。また本発明におけ
る出力極性最適化方法では　入力された２段論理関数の
各出力変数に対応する論理とその否定論理を共に出力と
する２重極性特性関数を生成しそれを最適化した後、必
要な積項数が小さくなる順にいくつかの出力極性を選択
する。その後、選択された各々の出力極性のもとで元の
°２段論理関数の簡単化を行（＼　その結果得られた２
段論理関数の総接続数が最小になる出力極性を選択する
。

このように本発明における出力極性最適化方法で（よ　
従来と同じように２重極性特性関数を利用している力士
　積項数ではなく総接続数が最小になる出力極性を選択
している。一般に総接続数最小の出力極性を選択するに
は全ての場合について最適化を行ってみて総接続数を計
算する必要があり、出力数が増大するに伴って組合せ的
爆発を引き起こす力士　ここでは２重極性特性関数を用
いて候補を絞り込むことによって効率的に出力極性を最
適化している。また本発明における共通因子抽出方法で
（よ　ある出力変数（もしくは中間変数）に対２０− 応する論理式の因子を求ム　それが他の出力変数（もし
くは中間変数）に対応する論理式の因子になっているか
どうかを調べるのは従来と同じである力（さらに因子の
否定を計算して他の出力変数（もしくは中間変数）に対
応する論理式の因子になっているかどうかを調べること
によって、従来方法では発見できなかった共通因子を抽
出することが可能となる。また本発明における因数分解
方法で（よ　ある出力変数（もしくは中間変数）に対応
する論理式の因子の中から排他的論理和になるものを探
し出し　それを優先的にくくり出すことによって、回路
中から可能な限り多くの排他的論理和ゲートを抽出する
ことが可能となる。

実施例 第１図は本発明における論理回路生成方法の一実施例の
処理フロー図を示すものである。第１図において、　１
は２段論理展開ステップ、　２は出力極性最適化ステッ
プ、　３は２段論理簡単化ステツー７４は共通積項抽出
ステップ、　５は共通因子抽出ステップ、　６は因数分
解ステップ、　７は共通入力抽出ステップである。この
うち２段論理展開ステップ１、出力極性最適化ステップ
２、２段論理簡単化ステップ３が２段論理最小化処理で
あり、共通積項抽出ステップ４、共通因子抽出ステップ
５、因数分解ステップ６、共通入力抽出ステップ７が多
段化処理である。以下、順をおって論理回路生成方法の
各ステップにおける処理の詳細な説明を行う。

ステップ１：２段論理への展開 入力された論理関数に対して、　ドモルガンの定理や分
配側等のプール代数の諸芸式（第７図）を再帰的に適用
することによってＡＮＤＯＲの２段論理へ展開する。こ
の時、論理関数の入力間に論理的制約があればこれも展
開し　制約条件を満たさない入力データをドントケアと
して扱う。後で説明するように　これらのドントケア情
報は論理を最小化する上で極めて有効に利用することが
できる。第８図に入力された論理関数を本実施例を用い
て２段論理に展開した結果（キューブ表現）を示す。以
下、記述する全てのキューブ表現にお１ ２２− いて、′、１′の後の数字は入力数、′、０′の後の数
字は出力数、’、ｉｌｂ’の後の文字列は入力区’、　
　。

ｂ′の後の文字列は出力部’、ｐ’の後の数字は積項数
を表している。その後に複数のキューブが記述されてい
るカミ　１行１キユーブであり、　１行の途中にあるス
ペースより前が入力撒　後が出力部である。キューブに
おいて各数字はそれぞれの位置によって決まる入出力に
対応している。入力部は数字が１′の場合は対応する入
力　′０”の場合は対応する入力の否定、′−″の場合
は対応する入力にかかわらず１　（真）として全ての数
字について論理積を取ったもの（積項）を表す。出力部
（友数字が１′の場合は対応する出力がその積項を論理
和の入力として含へ　′０”の場合は含まないことを表
している。論理関数７１が論理関数７３に展開されてい
る。またドントケア情報７４は制約条件７２の両辺の排
他的論理和をとって２段論理に展開することによって得
られる。

ステップ２：　出力極性最適化 論理関数の中にはそのまま実現するよりも、その否定を
実現する方が容易なものがある。そこで２段論理最小化
に先立ち出力極性の最適化を行っている。第２図に本発
明における出力極性最適化方法の一実施例の処理フロー
図を示す。第２図において、１１は２重極性特性関数生
成ステップ、１２は２重極性特性関数簡単化ステップ、
１３は最適出力極性候補選択ステップ、１４は２段論理
簡単化ステップ、１５は最適出力極性選択ステップであ
る。

本発明においても従来と同じく２重極性特性関数を用い
る手法を採用している力（積項数を最小にする手法では
多段化した後、必ずしも回路規模が小さくなるとは限ら
ないた敦　接続数を最小にする手法を採っ九　すなわち
２重極性特性関数を用いて求めたいくつかの候補につい
て総接続数を計算し　それが最小になるものを最適出力
極性としｋ　ここで積項と（よ　いくつかの入力（もし
くはその否定）の論理積を取ったものであり、　２段論
理関数では各出力変数はいくつかの積項の論理和となる
。積項数は２段論理回路ではＡＮＤゲート数に　また　
総接続数は全ゲートの入力の総数に一％− 一冴一 対応する。一般の論理回路においてはゲート数よりも接
続数の方が回路規模に対するより正しい目安を与えるこ
とが知られている。この点カミ　本発明の極めて重要な
点の一つであり、これによって初めて一般的な多段論理
回路に対して有効な出力極性最適化を実現することが可
能となる。第９図に２段論理間数８１から２重極性特性
関数を生成し簡単化した結果の２重極性特性関数８２（
キューブ表現）を示す。２重極性特性関数は元の論理関
数の各出力とそれぞれの否定を出力として持つカミ実際
には各出力について正負のいずれかがあればよい。２重
極性特性関数を用いて全ての出力極性の組み合せのうち
、必要な２重極性特性関数の積項数が少ないものから順
にいくつかの候補を選択することができる。第９図の２
重極性特性関数８２から本実施例を用いて選択した最適
出力極性候補と、その出力極性で元の２段論理関数８１
を簡単化した結果の総接続数を第１０図に示す。この例
では積項数最小の（１１１１）ではなく、総接続数最小
の（１０００）が最適出力極性として選択されている。

ステップ３：２段論理簡単化 ２段論理展開ステップ１で得られた２段論理関数に対し
て、出力極性最適化ステップ２で求めた最適出力極性の
もとでの簡単化を行う。２段論理簡単化アルゴリズムと
して従来から様々なシステムが開発されてきた力（ここ
ではカリフォルニア大学バーク１４校で開発されたＥＳ
ＰＲＥＳＳＯを用いている。ＥＳＰＲＥＳＳＯは積項数
と総接続数ともに準最小の解を効率的に生成することが
可能である。第９図に示した２段論理関数８１を出力極
性（１０００）のもとで簡単化した結果（キューブ表現
）を第１１図に示す。この例では簡単化前に積項数２１
、総接続数１７４であったのカミ　簡単化後は積項数１
宍総接続数９２になっており、総接続数が約半分に削減
され九　第１２図に論理最小化における制約条件の効果
を示す。今、論理関数１１１の入力Ｂ１とＢ２の間に制
約条件１１２が成立していたとする。

ここで制約条件１１２はＢ１が真の時は必ずＢ２も真に
なることを示している。この時、論理関数１１１を制約
条件を考慮せずに（すなわち入力Ｂ１とＢ２５− 加− を独立として）簡単化した結果１１３と制約条件を考慮
して（すなわちドントケア情報を利用して）簡単化した
結果１１４を比較すると、元の論理関数１１１は制約条
件１１２を用いることによって、より簡単化されている
ことがわかる。このような制約条件の利用は本実施例の
重要な点の一つであり、階層的な論理設計においては各
部分回路の入力は必ずしも独立ではなく、その間に制約
条件がある場合が多いので特に有効である。

ステップ４：　共通積項抽出 多段化の第一ステップとして、　２段論理の各出力変数
に対応する論理式の間で共通の積項があればそれをくく
り出湯１　これは第１３図に示すようにＡＮＤ−ＯＲの
２段論理回路の複数の出力に対応するＯＲゲート間の共
通入力をくくり出す処理である。このステップは後に述
べる共通入力抽出ステップ７とよく似ている力士　この
ステップを共通因子抽出ステップ５や因数分解ステップ
６等の因子抽出処理の前に行うことは重要である。なぜ
ならば２段論理簡単化処理では積項数を減らすためにで
きるだけ多くの積項を複数の出力変数に共有させるカミ
　これらの共通積項は独立した中間変数と見なされ　以
後に因子抽出処理の対象外とされてしまう。共通積項抽
出ステップによってこれらの積項も単一のＯＲゲートに
接続され　因子抽出を行うことが可能になる。この点も
本発明の極めて重要な効果の一つであり、共通積項抽出
ステップによって単にＯＲゲートの共通入力をくくり出
すだけではなく、因子抽出処理の性能向上にも貢献して
いる。

ステップ５：　共通因子抽出 このステップと次のステップは因子をくくり出すことに
よって論理の最小化を行う（因子抽出処理）。通常くく
り出せる因子は複数存在するのでその中で最適なものを
求める必要がある。第１４図に示すように論理関数の複
数の出力変数（もしくは中間変数）に対応する論理式に
共通の因子があればそれを優先してくくり出すのが本ス
テップの共通因子抽出である。なお共通因子でなくとも
第１５図に示すように　ある論理関数の因子の否定が− −公 別の論理関数の因子になっていれば　その因子も優先し
てくくり出される必要がある。ここでは各因子の否定を
求めることにより、このような共通因子の抽出も行って
いる。第３図に本発明における共通因子抽出方法の一実
施例の処理フロー図を示す。第３図において、２１は出
力変数（もしくは中間変数）Ａの因子生成ステップ、２
２は出力変数（もしくは中間変数）Ｂの因子生成ステッ
プ、２３はＡの因子とＢの因子の間に共通要素を探すス
テップ、２４はＡの因子の否定を生成するステッズ２５
はＡの因子の否定とＢの因子の間に共通要素を探すステ
ップ、２６は共通要素があればそれをＡとＢの共通因子
としてくくり出すステップである。

本発明ではＡとＢの因子を生成した後、従来と同じくＡ
とＢの共通因子を捜し　もしも見つかればそれを優先し
てくくり出すカミ　見つからなかった場合にはＡの否定
とＢの間に共通要素を捜し　もしも見つかればそれを中
間変数としてくくり出すことを行う。この点が本発明に
おいて極めて重要な点の一つであり、これにより初めて
、従来見落とされてきたタイプの共通因子を一般の因子
に対して優先的に抽出することが可能になった　以上に
述べた処理を全ての出力変数（もしくは中間変数）につ
いて再帰的に繰り返すことによって共通因子抽出ステッ
プ５が終了する。本実施例における共通因子抽出方法で
は複数の出力変数（もしくは中間変数）に対応する論理
式の間の共通因子を見つけるのに　それぞれの出力変数
（もしくは中間変数）に対応する論理式の因子を生成し
　それの共通要素を捜すという方法を取っているカミ　
別の方法　例えばある出力変数（もしくは中間変数）に
対応する論理式の因子を生成し　それで他の出力変数（
もしくは中間変数）に対応する論理式の因子を生成し　
それで他の出力変数（もしくは中間変数）に対応する論
理式を割ってみるというような方法によっても共通因子
を見つけることが可能である。

ステップ６：　因数分解 共通因子でなくとも論理関数の因子をくくり出すことは
論理を最小化する上で有効である。第１６−四− 一閣− 図に示すように　各出力変数（もしくは中間変数）に対
応する論理式ごとに独立に因子の抽出を行うのが本ステ
ップの因数分解ステップである。ここでも複数の因子の
候補の中から最適因子を求めることが重要である。ここ
では第１７図に示すように候補である因子の中から排他
的論理和になるものを探し出し　それを優先してくくり
出している。

通常セルライブラリはＥＸＣＬＵＳ　Ｉ　ＶＥ−ＯＲゲ
ートを含んでおり、このような排他的論理和の抽出は回
路規模を削減するのに大きな効果がある。

第４図に本発明における因数分解方法の一実施例の処理
フロー図を示す。第４図において、３１は出力変数Ａの
因子生成ステップ、３２は因子の中から排他的論理和に
なるものを探すステップ、３３は因子の中から一つを選
択するステップ、３４は選択された因子でＡを因数分解
するステップである。本発明ではＡの因子を生成した後
、ステップ３２においてまず排他的論理和となる因子を
探し　もしも見つかればそれをくくり出す点が従来とは
異なる。

見つからなければステップ３３で何らかの方略を用いて
一つの因子を選択してそれをくくり出も　この点が本発
明において極めて重要な点の一つであり、これにより従
来一般の因子に紛れて見逃されてきた排他的論理和を優
先して抽出することが可能になっ九　以上に述べた処理
を全ての出力変数（もしくは中間変数）について再帰的
に繰り返すことによって因数分解ステップ６が終了する
。

ステップ７：　共通入力抽出 多段化の最後のステップとして、複数の積項に共通の入
力があればそれをくくり出す。これは第１８図に示すよ
う４ＱＡＮＤゲ一ト間の共通入力をくくり出す処理であ
る。ＯＲゲート間の共通入力はすでに共通積項抽出ステ
ップ４でくくり出している。また同一の出力変数（もし
くは中間変数）に属している積項間の共通入力はすでに
因数分解ステップ６でくくり出している。従ってここで
は最後に残った　異なる出力変数（もしくは中間変数）
に属している積項間の共通入力の抽出を行う。

ここで因数分解ステップ６を共通入力抽出ステップ７よ
りも優先させたの法　第１９図に示すように３１ 一露一 一般的に前者の方が接続数が小さくなるためである。第
２０図に一連の多段化処理の例を示す。第２０図（ａ）
は２段論理簡単化後の論理関数であり、第２０図（ｂ）
は（ａ）から共通積項１９１を抽出した結果の論理関数
である。第２０図（Ｃ）は（ｂ）から不必要な中間変数
を削除した後、共通因子１９２を抽出した結果の論理関
数である。第２０図（ｄ）は（Ｃ）を因数分解した結果
の論理関数である。５因子１９３が抽出されたがそのう
ち２因子は排他的論理和である。第２０図（ｅ）は（ｄ
）から共通入力１９４を抽出した結果である。この例で
（ａ＞から（８）の多段化処理によって総接続数が８４
から５１に削減され九　本実施例は多段論理関数を入力
とじ　最小化された多段論理関数を生成するものである
力士　その結果における論理積をＡＮＤゲートに対応さ
せ、論理和をＯＲゲートに対応さ＋ｉ（排他的論理和を
ＥＸＣＬＵＳ　Ｉ　ＶＥ−ＯＲゲートに対応させ、否定
をインバータに対応させることにより、直ちに多段論理
回路を得ることができる。また本実施例の２段論理最小
化処理だけを行うことによって、最小化された２段論理
回路を出力することもでき、ＰＬＡの設計等に用いるこ
とも可能である。以上の説明では多段論理関数を入力と
している力（２段論理関数も一種の多段論理関数である
から、当然本実施例に入力することができる。この場合
、　２段論理展開ステップ１は入力された論理関数には
なにも処理を加えず、制約条件があればその処理を行う
。第２１図に本実施例の構成図を示机　第２１図におい
て、２０１は２段論理最小化手段、２０２は多段化手段
、２０３は回路要素割り付は手段２０４はＰＬＡプログ
ラミング手段である。入力された論理関数２０５は２段
論理最小化手段２０１、多段化手段２０２．回路要素割
り付は手段２０３を通して多段論理回路２０６を生成す
る力＼　あるいは２段論理最小化手段２０１の後、ＰＬ
Ａプログラミング手段２０４を通してＰＬＡとして実現
するかを選択することができる。次に実際の設計データ
を使って、本実施例における論理回路生成方法の評価を
行っ九　すなわち、いくつかの回路について、第５図に
処理フローを示した従来の論理回路生成方法で最小化し
た場合と本実施例で最小化した場−開− −胴− 合で結果（総接続数）を比較し九　その結果、本実施例
における論理回路生成方法を用いることによって、従来
方法に比べて最大８０尾　　平均して３３％の回路規模
削減を実現していることが分かったまた本実施例におけ
る出力極性最適化方法の評価を行っｋ　ずなわ叛　いく
っかの２段論理回路について従来の出力極性最適化方法
を用いた場合と本実施例における出力極性最適化方法を
用いた場合を比較し九　その結果　従来の出力極性最適
化方法が１５回路のうち２〜３回路しか真の最適出力極
性を選択できなかったのに対して、本実施例における出
力極性最適化方法は１５回路のうち１１回路で真の最適
出力極性を選択していることが分かった 発明の詳細 な説明したように　本発明では２段論理最小化手法と多
段論理最小化手法をうまく組み合わせることでそれぞれ
の手法の持つ欠点を補完するとともに　従来の論理最小
化手法にはなかった新たな機能を付加することにより、
従来の論理最小化＝３５− 手法では実現することができなかった高品質の論理回路
を効率的に生成することを可能にしている。

すなわち２段論理最小化手法は一般の多段論理回路を対
象とする場合に（戴　２段論理であるという制約によっ
て多くの冗長な回路を生み出してしまうカミ　それを後
に続く多段論理最小化手法によって取り除くことができ
る。逆に多段論理最小化手法のみでは論理的冗長性を効
率的に取り除くことが困難なこと東　出力極性最適化を
実現不可能なこと等を２段論理最小化手法を用いること
によって解決することができる。また本発明における総
接続数を最小にする出力極性最適化方法　因子とその否
定をも抽出できる共通因子抽出方法　排他的論理和を優
先的に抽出する因数分解方法等の従来になかった新しい
論理最小化手法を用いることによって、さらに高性能な
論理回路の生成が可能である。このような高性能な論理
回路生成方法を自動論理合成システムの中で用いること
により、入力された仕様をもとにして、よりコストの小
さい論理回路を自動的に生成することが可能になり、３
６− ＬＳＩや回路基板等の製造価格低減に寄与する効果は極
めて大きい。

【図面の簡単な説明】

第１図は本発明の一実施例における論理回路生成方法の
処理フロー倣　第２図は本発明の一実施例における出力
極性最適化方法の処理フロー医第３図は本発明の一実施
例における共通因子抽出方法の処理フロー医　第４図は
本発明の一実施例における因数分解方法の処理フロー＠
　第５図は従来の多段論理合成システムＭＩＳの典型的
な処理フロー＠　第６図は共通因子抽出処理と因数分解
処理の例を用いた説明図　第７図は２段論理への展開で
用いるプール代数の公式の説明は　第８図は２段論理展
開の実例を用いた説明圀　第９図は２重極性特性関数の
説明＠　第１０図は最適出力極性候補選択の説明図　第
１１図は最適化された２段論理関数の説明図　第１２図
は論理最小化における制約条件の効果の説明ｌ　第１３
図は共通積項抽出処理の説明図　第１４図は通常の共通
因子抽出処理の説明図　第１５図は因子とその否定の抽
出の説明図　第１６図は通常の因数分解処理の説明図　
第１７図は排他的論理和抽出の説明図　第１８図は共通
入力抽出処理の説明＠　第１９図は因数分解と共通入力
抽出の比較の説明図　第２０図は一連の多段化処理の実
例を用いた説明図　第２１図は本発明の一実施例におけ
る論理回路生成方法の構成図である。 １・・・・２没論理展開ステッス　２・・・・出力極性
最適化ステップ、　３・・・・２段論理簡単化ステップ
、４・・・・共通積項抽出ステップ、　５・・・・共通
因子抽出ステップ、　６・・・・因数分解ステラス　７
・・・・共通入力抽出ステップ、１１・・・・２電極性
特性関数生成ステッス　１２・・・・２重極性特性関数
簡単化ステップ、１３・・・・最適出力極性候補選択ス
テップ、１４・・・・２没論理簡単化ステッズ　Ｉ５・
・・・最適出力極性選択ステップ、２１・・・・出力変
数（もしくは中間変数）Ａの因子生成ステップ、２２・
・・・出力変数（もしくは中間変数）Ｂの因子生成ステ
ラス　２３・・・・Ａの因子とＢの因子の間に共通要素
を探すステラ’：Ｘ　　２４・・・・Ａの因子の否定を
生成するステラス２５・・・・Ａの因子の否定とＢの因
子の間に共通要素−訂一 ３８ を探すステップ、２６・・・・共通要素があればそれを
ＡとＢの共通因子としてくくり出すステップ、３１・・
・・出力変数（もしくは中間変数）Ａの因子生成ステッ
プ、３２・・・・因子の中から排他的論理和になるもの
を探すステップ、３３・・・・因子の中から一つを選択
するステップ、３４・・・・選択された因子でＡを因数
分解するステラス

Claims (7)

【特許請求の範囲】
1. （１）与えられた論理関数を実現する論理回路を生成す
   る論理回路生成方法であり、多段論理関数を２段論理関
   数に展開する２段論理展開手段と、前記２段論理関数の
   最適出力極性を求める出力極性最適化手段と、前記２段
   論理関数を簡単化する２段論理簡単化手段と、論理関数
   の複数の出力変数（もしくは中間変数）に対応する論理
   式の間の共通積項を中間変数としてくくり出す共通積項
   抽出手段と、論理関数の複数の出力変数（もしくは中間
   変数）に対応する論理式の間の共通因子を中間変数とし
   てくくり出す共通因子抽出手段と、論理関数の各出力変
   数（および中間変数）に対応する論理式をそれぞれ独立
   に因数分解する因数分解手段と、論理関数に含まれる複
   数の積項間の共通入力を中間変数としてくくり出す共通
   入力抽出手段とを有し入力された論理関数を前記２段論
   理展開手段により２段論理関数に展開し、次に前記出力
   極性最適化手段により前記２段論理関数の最適出力極性
   を求め、次に前記２段論理簡単化手段により、前記２段
   論理関数を前記最適出力極性のもとで簡単化し、次に前
   記共通積項抽出手段により、複数の出力変数に対応する
   論理式の間に共通の積項があれば中間変数としてくくり
   出し、次に前記共通因子抽出手段により、複数の出力変
   数（もしくは中間変数）に対応する論理式の間に共通の
   因子があれば中間変数としてくくり出し、次に前記因数
   分解手段により、各出力変数（および中間変数）に対応
   する論理式をそれぞれ独立に因数分解し、次に前記共通
   入力抽出手段により、論理関数に含まれる複数の積項間
   に共通の入力があれば中間変数としてくくり出すことに
   より、与えられた論理関数を別の論理関数に変換してか
   ら実現することを特徴とする論理回路生成方法。
2. （２）２段論理関数の最適出力極性を求める出力極性最
   適化方法であり、入力された２段論理関数の各出力に対
   応する論理とその否定論理を表現する出力を共に有する
   ２段論理関数である２重極性特性関数を生成する２重極
   性特性関数生成手段と、前記２重極性特性関数生成手段
   の結果得られた２重極性特性関数を簡単化する２重極性
   特性関数簡単化手段と、前記２重極性特性関数簡単化手
   段により簡単化された２重極性特性関数を用いて、必要
   な積項数が小さくなる順にいくつかの出力極性を選択す
   る最適出力極性候補選択手段と、前記最適出力極性候補
   選択手段により選択された各々の出力極性のもとで前記
   入力された２段論理関数の簡単化を行う２段論理簡単化
   手段と、前記２段論理簡単化手段の結果得られた２段論
   理関数の総接続数を計算し、総接続数が最小になる出力
   極性を求める最適出力極性選択手段とを有することを特
   徴とする出力極性最適化方法
3. （３）論理関数の複数の出力変数（もしくは中間変数）
   に対応する論理式の間に共通の因子があれば中間変数と
   してくくり出す共通因子抽出方法であり、論理関数の出
   力変数（もしくは中間変数）に対応する論理式の因子を
   計算し求める手段と、前記因子の否定を計算し求める手
   段と、前記因子かあるいは前記因子の否定が前記論理関
   数の別の出力変数（もしくは中間変数）に対応する論理
   式の因子になっているかどうかを検査する手段とを有し
   、ある出力変数（もしくは中間変数）に対応する論理式
   の因子の否定が別の出力変数（もしくは中間変数）に対
   応する論理式の因子になっていれば、共通因子としてく
   くり出すことを特徴とする共通因子抽出方法。
4. （４）論理関数の各出力変数（もしくは中間変数）に対
   応する論理式の因子の中から最適な因子をくくり出す論
   理関数の因数分解方法であり、論理関数の出力変数（も
   しくは中間変数）に対応する論理式の因子を計算し求め
   る手段と、前記因子の中から排他的論理和になるものを
   探す手段とを有し、論理関数の出力変数（もしくは中間
   関数）に対応する論理式の因子の中に排他的論理和にな
   るものがあれば優先してくくり出すことを特徴とする因
   数分解方法。
5. （５）出力極性最適化方法として、入力された２段論理
   関数の各出力に対応する論理とその否定論理を表現する
   出力を共に有する２段論理関数である２重極性特性関数
   を生成する２重極性特性関数生成手段と、前記２重極性
   特性関数生成手段の結果得られた２重極性特性関数を簡
   単化する２重極性特性関数簡単化手段と、前記２重極性
   特性関数簡単化手段により簡単化された２重極性特性関
   数を用いて、必要な積項数が小さくなる順にいくつかの
   出力極性を選択する最適出力極性候補選択手段と、前記
   最適出力極性候補選択手段により選択された各々の出力
   極性のもとで前記入力された２段論理関数の簡単化を行
   う２段論理簡単化手段と、前記２段論理簡単化手段の結
   果得られた２段論理関数の総接続数を計算し、総接続数
   が最小になる出力極性を求める最適出力極性選択手段と
   を有する方法を用いることを特徴とする特許請求の範囲
   第１項記載の論理回路生成方法。
6. （６）共通因子抽出方法として、論理関数の出力変数（
   もしくは中間変数）に対応する論理式の因子を計算し求
   める手段と、前記因子の否定を計算し求める手段と、前
   記因子かあるいは前記因子の否定が前記論理関数の別の
   出力変数（もしくは中間変数）に対応する論理式の因子
   になっているかどうかを検査する手段とを有する方法を
   用いることを特徴とする特許請求の範囲第１項記載の論
   理回路生成方法
7. （７）因数分解方法として、論理関数の出力変数（もし
   くは中間変数）に対応する論理式の因子を計算し求める
   手段と、前記因子の中から排他的論理和になるものを探
   す手段とを有する方法を用いることを特徴とする特許請
   求の範囲第１項記載の論理回路生成方法