(57)【特許請求の範囲】
【請求項１】
基準となる基準側回路および検査される検査側回路の各々のネットリストに基づいて各々の回路において、直列に接続された素子を直列の仮想素子に変換する直列縮約処理および並列に接続された素子を並列の仮想素子に変換する並列縮約処理をコンピュータによって行うステップと、
前記直列縮約処理および並列縮約処理が行われた前記基準側回路および検査側回路に複合ゲート縮約処理をコンピュータによって行うステップと、
を備え、
前記複合ゲート縮約処理は、並列の仮想素子の入力側に複数の直列の仮想素子が接続され、これら直列の仮想素子の入力側に共通の信号が入力されていた場合に、新しい直列の仮想素子と新しい並列の仮想素子をコンピュータによって追加し、共通の入力信号のある前記直列の仮想素子の出力をコンピュータによって新しい前記並列の仮想素子の入力に接続し直し、新しい前記並列の仮想素子の出力と元の直列の仮想素子に共通に入力されていた信号をコンピュータによって新しい前記直列の仮想素子の入力に接続し、新しい直列仮想素子の出力をコンピュータによって元の並列仮想素子の入力に接続するステップを備えたことを特徴とする半導体集積回路の等価性検証方法。
【請求項２】
基準となる基準側回路および検査される検査側回路の各々のネットリストに基づいて各々の回路において、直列に接続された素子を直列の仮想素子に変換する直列縮約処理および並列に接続された素子を並列の仮想素子に変換する並列縮約処理をコンピュータによって行うステップと、
前記直列縮約処理および並列縮約処理が行われた前記基準側回路および検査側回路に複合ゲート縮約処理をコンピュータによって行うステップと、
を備え、
前記複合ゲート縮約処理は、直列の仮想素子の入力側に複数の並列の仮想素子が接続され、これら並列の仮想素子の入力側に共通の信号が入力されていた場合に、新しい並列の仮想素子と新しい直列の仮想素子をコンピュータによって追加し、共通の入力信号のある前記並列の仮想素子の出力をコンピュータによって新しい直列の仮想素子の入力に接続し直し、新しい直列の仮想素子の出力と元の並列の仮想素子に共通に入力されていた信号をコンピュータによって新しい並列の仮想素子の入力に接続し、新しい並列の仮想素子の出力をコンピュータによって元の直列仮想素子の入力に接続するステップを備えたことを特徴とする半導体集積回路の等価性検証方法。
【請求項３】
前記複合ゲート縮約処理は、
入力ネットが１つでかつ出力ネットが１つの仮想素子を削除し、前記入力ネットと出力ネットをコンピュータによって直接接続するステップと、
コンピュータによって、入力ネットを有さない並列の仮想素子を削除しかつこの仮想素子の出力ネットを論理値「０」の固定ネットに置換えるステップと、
コンピュータによって、入力ネットを有さない直列の仮想素子を削除しかつこの仮想素子の出力ネットを論理値「１」の固定ネットに置換えるステップと、
論理値が「０」または「１」に固定された入力ネットを有する仮想素子をコンピュータによって、論理的に、より簡単な仮想素子に置換えるステップと、
を備えたことを特徴とする請求項１または２記載の半導体集積回路の等価性検証方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、半導体集積回路の等価性検証方法に関し、特に、論理ＬＳＩ回路のレイアウト設計に用いられる。
【０００２】
【従来の技術】
一般に、半導体集積回路、特に論理ＬＳＩ回路の設計に等価性検証方法が用いられる。これは以下の理由による。
【０００３】
１）  回路設計者が設計した回路図（ネットリスト（素子と、素子間を接続するネット（配線）とを有する接続情報））と、この回路図を元にレイアウト設計者が設計したレイアウト図から作成された回路図（ネットリスト）とが一致しているか否かを検査する必要がある。
【０００４】
２）修正や改良のため、レイアウトに変更があったとき、修正／改良前のレイアウト図面から作成した回路図と、修正／改良後のレイアウト図面から作成した回路図とを比較することで、修正／改良が正しく行われたか否かを検証する必要がある。
【０００５】
３）レイアウト後の図面から配線抵抗や配線容量等の回路パラメータを抽出し、そのパラメータを回路設計段階のシミュレーションにフィードバックする為には、回路図上の信号とレイアウト上の信号の対応が必要あり、このため等価性の検証が行われる。
【０００６】
従来の等価性検証方法を図２５乃至図３１を参照して説明する。
【０００７】
等価性検証方法は、記憶装置に格納されている基準側回路（例えば回路設計者が設計した回路）のネットリストに基づいて形成されるグラフと、検査側回路（例えばレイアウト図から作成された回路）のネットリストに基づいて形成されるグラフとがトポロジー的に同一かどうかをコンピュータを用いて比較することによって行う。例えば、基準側回路が図２６（ａ）に示すように入力Ａを受けるトランジスタＴ1 のソースに、入力Ｂを受けるトランジスタＴ2 が直列に接続されており、検査側回路が図２６（ｂ）に示すように入力Ａを受けるトランジスタＴ1 のソースに、入力Ｂを受けるトランジスタＴ2 が直列に接続されている場合は、比較すれば基準側回路と検査側回路とはトポロジー的に同一となり、等価となる。
【０００８】
しかし、一般に半導体集積回路は図２６（ａ），（ｂ）に示すような簡単な構成となっていない。このため、従来の等価性検証方法は、図２５に示すような処理を行う。即ち、まず基準側回路において、後述する直列縮約および並列縮約を行う（ステップＦ３０）とともに検査側回路においても直列縮約および並列縮約を行う（ステップＦ３２参照）。その後、トポロジー的に同一か否かの比較処理をコンピュータによって行う（ステップＦ３４参照）。
【０００９】
次に直列縮約について説明する。図２７（ａ），（ｂ）に示すように、各々、トランジスタＴ1 ，Ｔ2 から構成される基準側回路と検査側回路において、トランジスタＴ1 ，Ｔ2 との直列接続が逆になっている場合を考える。このままの状態では、基準側回路と、検査側回路とはトポロジー的に同一ではない。
【００１０】
そこで、基準側回路および検査側回路において、直列接続されたトランジスタＴ1 ，Ｔ2 を、一つの直列接続を表わしかつ入力端子Ａ，Ｂが交換可能な直列の仮想素子６０，６２に各々変換する（図２７（ａ′），（ｂ′）参照）。このように直列接続されたスイッチング素子（トランジスタ）を直列の仮想素子に変換することを直列縮約と言う。図２７（ａ′），（ｂ′）に示すように、直列縮約を行った後は、比較処理を行うことにより仮想素子６０からなる基準側回路と仮想素子６２からなる検査側回路とはトポロジー的に同一となり、基準側回路と検査側回路は等価であると証明される。
【００１１】
この直列縮約の処理は図２８に示すようにして行う。図２８において、まず回路中に複数のスイッチング素子（または仮想素子）が存在するか否かを検索する（ステップＦ４２）。存在しない場合は直列縮約処理を終了する。存在する場合は、ステップＦ４４に進み、これらの複数のスイッチング素子（または仮想素子）の中で直列接続するものがあるか否かを検索する。直列接続しているものが存在しない場合は直列縮約処理を終了する。存在する場合は、ステップＦ４６に進み、直列接続しているスイッチング素子（または仮想素子）を直列の仮想素子に変換する。その後、ステップＦ４８に進み、他の直列接続する複数のスイッチング素子（または仮想素子）が存在するか否かを検索する。存在しない場合は直列縮約処理を終了し、存在する場合はステップＦ４６に戻り、上述の処理を行う。
【００１２】
次に並列縮約について説明する。図２９（ａ）に示すように基準側回路が並列に接続されたトランジスタＴ1 ，Ｔ2 と、これに直列に接続されたトランジスタＴ3 とから構成され、図２９（ｂ）に示すように検査側回路が、基準側回路と同じ要素から構成されていて、直列接続の位置が逆になっている場合を考える。このままの状態では、基準側回路と検査側回路とはトポロジー的に同一ではない。
【００１３】
そこでまず、基準側回路および検査側回路において、並列接続されたトランジスタＴ1 ，Ｔ2 を、１つの並列接続を表わしかつ入力端子Ａ，Ｂが交換可能な並列の仮想素子６４，６６に各々変換する（図２９（ａ′），（ｂ′）参照）。このように並列接続されたスイッチング素子（トランジスタ）を並列の仮想素子に変換することを並列縮約という。図２９（ａ′）に示すように基準側回路に並列縮約を行った後は、並列の仮想素子６４とトランジスタＴ3 との直列縮約を行い、直列の仮想素子６５に変換する（図２９（ａ″）参照）。また、図２９（ｂ′）に示すように検査側回路に並列縮約を行った後は、トランジスタＴ3 と並列の仮想素子６６との直列縮約を行い、直列の仮想素子６７に変換する（図２９（ｂ″）参照）。この状態で基準側回路と検査側回路の比較処理を行うことにより、トポロジー的に同一となり、基準側回路と検査側回路は等価であると証明される。
【００１４】
上述の並列縮約の処理は図３０に示すようにして行う。図３０において、まず回路中に複数のスイッチング素子（または仮想素子）が存在するか否かを検索する（ステップＦ５２参照）。存在しない場合は並列縮約処理を終了する。存在する場合はステップＦ５４に進み、これらの複数のスイッチング素子（または仮想素子）の中で並列接続するものがあるか否かを検索する。並列接続しているものが存在しない場合は並列縮約処理を終了する。存在する場合はステップＦ５６に進み、並列接続しているスイッチング素子（または仮想素子）を並列の仮想素子に変換する。その後、ステップＦ５８に進み、他の並列接続する複数のスイッチング素子（または仮想素子）が存在するか否かを検索する。存在しない場合は並列縮約処理を終了し、存在する場合はステップＦ５６に戻り、上述の処理を行う。
【００１５】
【発明が解決しようとする課題】
上述のように従来の等価性検証方法においては、基準側回路および検査側回路各々において、これ以上直列縮約処理および並列縮約処理を行うことができなくなるまで上記処理を行った後、比較処理を行い、基準側回路と検査側回路とがトポロジー的に同一であるか否かによって等価であるか否かを検証していた。
【００１６】
しかし、基準側回路および検査側回路が各々図３１（ａ），（ｂ）に示すような場合は、論理機能としては等価の回路であるにも関わらず従来の等価性検証方法を用いても等価であるか否かを検証することができないという問題が生じる。以下、これについて説明する。
【００１７】
基準側回路は、図３１（ａ）に示すように入力信号Ａをゲートに受けるトランジスタＴ1 および入力信号Ｃをゲートに受けるトランジスタＴ3 とからなる第１の直列回路と、入力信号Ｂをゲートに受けるトランジスタＴ2 および入力信号Ｃをゲートに受けるトランジスタＴ4 とからなる第２の直列回路とが並列に接続された構成を有している。一方、検査側回路は、図３１（ｂ）に示すように入力信号Ａをゲートに受けるトランジスタＴ1 および入力信号Ｂをゲートに受けるトランジスタＴ2 からなる並列回路と、この並列回路に直列に接続されてゲートに入力信号Ｃを受けるトランジスタＴ3 とからなる構成を有している。
【００１８】
上述の基準側回路および検査側回路に従来の等価性検証方法を実施すると、基準側回路においては図３１（ａ′）示すようにまず、第１の直列回路および第２の直列回路が各々、直列縮約されて直列の仮想素子７２，７３に変換された後、これらの仮想素子が並列縮約処理され、並列の仮想素子７６に変換される。一方、検査側回路においては図３１（ｂ′）に示すように並列回路が並列縮約され、並列の仮想素子７７に変換され、この仮想素子７７とトランジスタＴ3 とが直列縮約処理され、直列の仮想素子７８に変換される。
【００１９】
したがって、並列の仮想素子７６と直列の仮想素子７８はトポロジー的に一致せず、従来の等価性検証方法では、等価であるか否かを検証することができない。
【００２０】
本発明は上記事情を考慮してなされたものであって、等価であるか否かを検証することのできる、半導体集積回路の等価性検証方法を提供することを目的とする。
【００２１】
【課題を解決するための手段】
本発明による半導体集積回路の等価性検証方法は、基準となる基準側回路および検査される検査側回路の各々のネットリストに基づいて各々の回路において、直列に接続された素子を直列の仮想素子に変換する直列縮約処理および並列に接続された素子を並列の仮想素子に変換する並列縮約処理を行うステップと、
前記直列縮約処理および並列縮約処理が行われた前記基準側回路および検査側回路に複合ゲート縮約処理を行うステップと、を備えたことを特徴とする。
【００２２】
なお、前記複合ゲート縮約処理は、直列の仮想素子を論理代数の論理積と見なし、並列の仮想素子を論理和と見なしたときに論理代数の分配律により共通項を括り出した場合と等価な、仮想素子からなる回路に変換するステップを備えたことを特徴とする。
【００２３】
なお、前記複合ゲート縮約処理は、並列の仮想素子の入力側に複数の直列の仮想素子が接続され、これら直列の仮想素子の入力側に共通の信号が入力されていた場合に、新しい直列の仮想素子と新しい並列の仮想素子を追加し、共通の入力信号のある前記直列の仮想素子の出力を新しい前記並列の仮想素子の入力に接続し直し、新しい前記並列の仮想素子の出力と元の直列の仮想素子に共通に入力されていた信号を新しい前記直列の仮想素子の入力に接続し、新しい直列仮想素子の出力を元の並列仮想素子の入力に接続するステップを備えることが好ましい。
【００２４】
なお、前記複合ゲート縮約処理は、直列の仮想素子の入力側に複数の並列の仮想素子が接続され、これら並列の仮想素子の入力側に共通の信号が入力されていた場合に、新しい並列の仮想素子と新しい直列の仮想素子を追加し、共通の入力信号のある前記並列の仮想素子の出力を新しい直列の仮想素子の入力に接続し直し、新しい直列の仮想素子の出力と元の並列の仮想素子に共通に入力されていた信号を新しい並列の仮想素子の入力に接続し、新しい並列の仮想素子の出力を元の直列仮想素子の入力に接続するステップを備えることが好ましい。
【００２５】
なお、前記複合ゲート縮約処理は、入力ネットが１つでかつ出力ネットが１つの仮想素子を削除し、前記入力ネットと出力ネットを直接接続するステップと、入力ネットを有さない並列の仮想素子を削除し、この仮想素子の出力ネットを論理値「０」の固定ネットに置換えるステップと、入力ネットを有さない直列の仮想素子を削除し、この仮想素子の出力ネットを論理値「１」の固定ネットに置換えるステップと、論理値が「０」または「１」に固定された入力ネットを有する仮想素子を論理的に、より簡単な仮想素子に置換えるステップと、を備えることが好ましい。
【００２６】
【発明の実施の形態】
本発明による半導体集積回路の等価性検証方法の一実施の形態を図１乃至図２４を参照して説明する。
【００２７】
本実施の形態の等価性検証方法の処理手順を図１に示す。図１において、まず、基準となる基準側回路において、従来の場合と同様に直列縮約および並列縮約処理を行う（ステップＦ１参照）。続いて、後述する複合ゲート縮約処理を行う（ステップＦ２参照）。同様に、検査すべき検査側回路においても直列縮約および並列縮約処理を行い（ステップＦ３参照）、続いて複合ゲート縮約処理を行う（ステップＦ４参照）。そして複合ゲート縮約処理が行われた基準側回路と検査側回路がトポロジー的に同一か否かの比較処理を行う（ステップＦ５参照）。なお、上記説明においては、直列縮約および並列縮約処理は基準側回路を先に行ったが、検査側回路を先に行っても良い。
【００２８】
次に複合ゲート縮約処理について説明する。この複合ゲート縮約処理の処理手順を図２に示す。まず、直列縮約および並列縮約処理が行われた回路において、直列の仮想素子の入力側に複数の並列の仮想素子からなる仮想素子群が接続されているか、または並列の仮想素子の入力側に複数の直列の仮想素子からなる仮想素子群が接続されているものが存在するか否かを検索する（図２のステップＦ１０参照）。存在しない場合は複合ゲート縮約処理を終了する。存在する場合はステップＦ１２に進み、上記仮想素子群の各仮想素子の入力側に共通なネットが接続するか否かを検証する。
【００２９】
そして接続しない場合は後述のステップＦ１８に進む。接続する場合はステップＦ１４に進む。そして上記仮想素子と上記仮想素子群との間に、上記仮想素子の入力ネットに接続される仮想素子Ａと、上記仮想素子群の出力ネットに接続される仮想素子Ｂを挿入し、仮想素子Ｂの出力ネットを仮想素子Ａの入力ネットに接続する。続いて、上記仮想素子群中の共通のネットを上記仮想素子Ａの入力側に接続する（図２のステップＦ１６参照）。なお、上記仮想素子群が直列の仮想素子から構成されていれば、仮想素子Ａは直列の仮想素子でかつ仮想素子Ｂは並列の仮想素子とする。また上記仮想素子群が並列の仮想素子から構成されていれば、仮想素子Ａは並列の仮想素子でかつ仮想素子Ｂは直列の仮想素子とする。
【００３０】
ステップＦ１６の処理が終了した後は、ステップＦ１８に進み、入力ネットが１でかつ出力ネットが１つの仮想素子を削除し上記入力ネットと上記出力ネットを直接に接続し、入力ネットを有さない並列の仮想素子を削除しこの仮想素子の出力ネットを論理値「０」に固定されたネットに置き換え、入力ネットを有さない直列の仮想素子を削除しこの仮想素子の出力ネットを論理値「１」に固定されたネットに置き換え、論理値「０」または「１」に固定された入力ネットを有する仮想素子を論理的に等価なより簡単な仮想素子に置き換える。
【００３１】
その後、ステップＦ２０に進み、他の直列の仮想素子の入力側に複数の並列の仮想素子からなる仮想素子群が接続するか、または並列の仮想素子の入力側に複数の直列の仮想素子からなる仮想素子群が接続するものがあるか否かを検索する。接続するものが無い場合は複合ゲート縮約処理を終了し、接続するものが有る場合はステップＦ１２に戻り上述のステップを繰返す。
【００３２】
次に上述の複合ゲート縮約のステップＦ１２、Ｆ１４、Ｆ１６の処理について図３乃至図１０を参照して具体的に説明する。
【００３３】
今、図３（ａ）に示す論理回路を考える。この論理回路は、第１乃至第ｍの並列部と、ｑ個のトランジスタＳ1 ，…，Ｓq が直列に接続された直列部とを有している。第ｉ（ｉ＝１，…ｍ）の並列部はｐｉ個のトランジスタＴi1，…Ｔipiとｎ個のトランジスタＱi1，…Ｑinが並列に接続された構成を有している。なお第１乃至第ｍの並列部と上記直列部は直列に接続されて直列回路を構成している。トランジスタＴij（ｉ＝１，…ｍ、ｊ＝１，…ｐｉ）はゲートに信号Ａijを受ける。ｎ個のトランジスタＱ1i，…Ｑni（ｉ＝１，…ｎ）はゲートに共通の信号Ｂi を受ける。そしてトランジタＳi （ｉ＝１，…ｑ）はゲートに信号Ｃi を受ける。
【００３４】
上記の論理回路のブール代数表現は図３（ｂ）に示す通りとなる。この論理回路に、本実施の形態の直列縮約処理および並列縮約処理を施すと図４に示す通りとなる。即ち、第ｉ（ｉ＝１，…ｍ）の並列部は並列の仮想素子１２i に変換され、上記直列回路は直列の仮想素子１６に変換される。
【００３５】
この図４に示す回路は直列の仮想素子１６の入力側に、複数の並列の仮想素子１２1 ，…１２m からなる仮想素子群が接続している構成となっている。このため図４に示す回路に複合ゲート縮約処理のステップＦ１０を適用すると、Ｙｅｓとなり、ステップＦ１２に進むことになる。すると、各並列の仮想素子１２i （ｉ＝１，…ｍ）には共通の入力Ｂ1 ，…Ｂn が入力されているので、ステップＦ１２においてＹｅｓとなり、ステップＦ１４に進む。
【００３６】
ステップＦ１４の処理では上記仮想素子群１２1 〜１２m と仮想素子１６の間に、図５に示すように並列の仮想素子Ａと直列の仮想素子Ｂが挿入され、これらの仮想素子Ａと仮想素子Ｂは接続される。そしてステップＦ１６の処理によって仮想素子群１２1 ，…１２m に入力されていた共通の入力は仮想素子Ａに入力され、図４に示す並列の仮想素子１２i （ｉ＝１，…ｍ）は図５に示す並列の仮想素子１２aiとなる。
【００３７】
図５に示すブロック図を実際の回路図で表現すれば図６（ａ）示す通りとなり、そのブール代数表現は図６（ｂ）に示す通りとなる。図３（ａ）に示す論理回路と、図６（ａ）に示す論理回路は論理的に等価であることが分かる。
【００３８】
次に図７（ａ）に示す論理回路を考える。この論理回路は第１乃至第ｎの直列部と、ｍ個のトランジスタが並列に接続された並列部とを有している。第ｉ（ｉ＝１，…ｎ）の直列部はｐｉ個のトランジスタＡi1，…Ａipiと、ｑ個のトランジスタＱi1，…Ｑiqが直列に接続された構成となっている。そして、これらの第１乃至第ｎの直列部と上記並列部は並列に接続されて並列回路を構成している。なおトランジスタＴij（ｉ＝１，…ｎ、ｊ＝１，…ｐｉ）のゲートは信号Ａijを受ける。ｑ個のトランジスタＱ1i，…Ｑqiの各ゲートは信号Ｂi を受ける。またトランジスタＳi （ｉ＝１，…ｍ）のゲートは信号Ｃi を受ける。
【００３９】
図７（ａ）に示す論理回路のブール代数表現は図７（ｂ）に示す通りとなる。この論理回路に、本実施の形態の直列縮約処理および並列縮約処理を施すと図８に示す通りとなる。即ち第ｉ（ｉ＝１，…ｎ）の直列部は直列の仮想素子２２i に変換され、上記並列回路は並列の仮想素子２６に変換される。
【００４０】
この図８に示す回路に本実施の形態の複合ゲート縮約処理を行うと、前述したと同様に図９に示す通りとなる。即ち仮想素子群２２1 ，…２２n と、並列の仮想素子２６との間に直列の仮想素子Ａと並列の仮想素子Ｂが挿入され、かつ、これらの仮想素子Ａ，Ｂは接続される。そして仮想素子群２２1 ，…２２n に共通に入力されている信号は仮想素子Ａに入力されるように変更されるため、仮想素子２２i （ｉ＝１，…ｎ）は仮想素子２２aiとなる。
【００４１】
この図９に示す論理回路を具体的に表現すれば、図１０（ａ）に示す通りとなり、そのブール代数表現は図１０（ｂ）に示す通りとなる。図７（ａ）に示す論理回路と図１０（ａ）に示す論理回路は論理的に等価であることが分かる。
【００４２】
次に複合ゲート縮約のステップＦ１８の処理について図１１乃至図２３を参照して具体的に説明する。
【００４３】
この複合ゲート縮約は、まず図１１（ａ），（ｂ）に示すように入力ネットが１つでかつ出力ネットが１つの仮想素子を削除し、上記入力ネットと上記出力ネットを直接に接続する。続いて図１２（ａ）に示すように入力ネットを有さない並列の仮想素子を削除し、この仮想素子の出力ネットを論理値「０」に固定されたネットに置き換え、図１２（ｂ）に示すように入力ネットを有さない直列の仮想素子を削除し、この仮想素子の出力ネットを論理値「１」に固定されたネットに置換える。そして論理値「０」または「１」に固定された入力ネットを有する仮想素子を論理的に等価な簡単な仮想素子に置換える。
【００４４】
論理値「０」に固定された入力ネットを有する仮想素子が存在する場合の複合ゲート縮約処理を図１３乃至図１７を参照して説明する。図１３に示す論理回路は直列縮約処理および並列縮約処理を行う前の回路であり、第１乃至第ｎの直列部と、ｍ個のトランジスタＳ1 ，…，Ｓm からなる並列部とを有している。第１の直列部は直列に接続されたｑ個のトランジスタＱ11，…Ｑ1qから構成されている。第ｉ（ｉ＝２，…ｎ）の直列部は、直列に接続された（ｐｉ＋ｑ）個のトランジスタＴi1，…Ｔipi、Ｑi1，…Ｑiqから構成されている。そして第１乃至第ｎの直列部と上記並列部は並列に接続されて並列回路を構成する。
【００４５】
なおトランジスタＴij（ｉ＝２，…ｎ、ｊ＝１，…ｐｉ）のゲートには信号Ａijが入力される。ｎ個のトランジスタＱ1i，…Ｑni（ｉ＝１，…ｑ）の各ゲートには信号Ｂi が入力される。また、トランジスタＳi （ｉ＝１，…ｍ）のゲートには信号Ｃi が入力される。
【００４６】
図１３に示す論理回路に本実施の形態の直列縮約処理および並列縮約処理ならびに図２に示す複合ゲート縮約のステップＦ１６までの処理を行うと図１４に示す通りとなる。第１の直列部は入力信号の無い直列の仮想素子３３1 に変換され、第ｉ（ｉ＝２，…ｎ）の直列部は直列の仮想素子３３i に変換され、上記並列部は並列の仮想素子３６に変換される。そして複数の直列の仮想素子３３1 ，…３３n からなる仮想素子群と、並列の仮想素子３６との間に仮想素子Ａと仮想素子Ｂが挿入される。仮想素子Ｂは並列の仮想素子３４であり、仮想素子Ａは直列の仮想素子３５である。この仮想素子３４と仮想素子３５は接続されるとともに、仮想素子３５には共通の信号Ｂ1 ，…Ｂq が入力される。
【００４７】
この図１４に示す回路に複合ゲート縮約のステップＦ１８の処理を行うと、直列の仮想素子３３1 は削除されて、論理値が「１」の信号に変換される。これにより図１４に示す回路は図１５（ａ）に示す回路に変換される。この図１５（ａ）に示す論理回路のブール代数表現は図１５（ｂ）に示す通りとなる。そして更に上記ステップＦ１８において、図１５（ａ）に示す回路は論理的に等価でかつより単純な回路、例えば図１６（ａ）に示す回路に変換される。即ち、仮想素子群３３2 ，…３３n と、並列の仮想素子３４と、直列の仮想素子３５は直列の仮想素子４２に変換される。この図１６（ａ）に示す回路のブール代数表現は図１６（ｂ）に示す通りとなる。更にこの図１６（ａ）に示す回路は、図１７（ａ）に示す、より単純な回路に置換えられる。即ち、直列の仮想素子４２は入力「１」が削除された直列の仮想素子４２ａに変換される。この図１７（ａ）に示す回路のブール代数表現は図１７（ｂ）に示す通りとなる。
【００４８】
次に、論理値「１」に固定された入力ネットを有する仮想素子が存在する場合の複合ゲート縮約処理を図１８乃至図２３を参照して説明する。
【００４９】
図１８（ａ）に示す論理回路は直列縮約及び並列縮約処理を行う前の回路であり、第１乃至第ｍの並列部と、ｑ個のトランジスタＳ1 ，…，Ｓq からなる直列部とを有している。第１の並列部は並列に接続されたｎ個のトランジスタＱ11，…Ｑn1から構成されている。第ｉ（ｉ＝２，…ｍ）の並列部は、並列に接続された（ｐｉ＋ｎ）個のトランジスタＴi1，…Ｔipi、Ｑ1i，…Ｑniから構成されている。そして第１乃至第ｍの並列部と上記直列部とは直列に接続されて直列回路を構成する。
【００５０】
なお、トランジスタＴij（ｉ＝２，…ｍ、ｊ＝１，…ｐｉ）のゲートには信号Ａijが入力される。ｍ個のトランジスタＱi1，…Ｑim（ｉ＝１，…ｎ）の各ゲートには信号Ｂi が入力される。また、トランジスタＳi （ｉ＝１，…ｑ）のゲートには信号Ｃi が入力される。この図１８（ａ）に示す論理回路のブール代数表現は図１８（ｂ）に示す通りとなる。
【００５１】
図１８（ａ）に示す論理回路に、本実施の形態の直列縮約処理及び並列縮約処理ならびに図２に示す複合ゲート縮約のステップＦ１６までの処理を行うと図１９（ａ）に示す通りとなる。第ｉ（ｉ＝１，…ｍ）の並列部は並列の仮想素子５２i に変換され、上記直列部は直列の仮想素子５６に変換される。なおこの図１９（ａ）に示す回路のブール代数表現は図１９（ｂ）に示す通りとなる。
【００５２】
続いて複数の並列の仮想素子５２1 ，…５２m からなる仮想素子群と、直列の仮想素子５６との間に図２０に示すように仮想素子Ａと仮想素子Ｂが挿入される。仮想素子Ｂは直列の仮想素子５４であり、仮想素子Ａは並列の仮想素子５５である。
【００５３】
この仮想素子５４と仮想素子５５は接続されるとともに、仮想素子５５には共通の信号Ｂ1 ，…Ｂn が入力される。このとき図１９（ａ）に示す並列の仮想素子５２i （ｉ＝１，…ｍ）から共通の入力信号Ｂ1 ，…Ｂn が除去されるため、並列の仮想素子５２i は図２０に示すように並列の仮想素子５２ａi となる。
【００５４】
この図２０に示す回路に、図２に示すステップＦ１８の処理を行うと、まず、並列の仮想素子５２ａi は削除されて、図２１（ａ）に示すように論理値が「０」の信号に変換される。この図２１（ａ）に示す回路のブール代数表現は図２１（ｂ）に示す通りとなる。そして更に、上記ステップＦ１８において、図２１（ａ）に示す回路は、論理的に等価でかつより単純な回路、例えば図２２（ａ）に示す回路に変換される。即ち、並列の仮想素子５２ａ2 ，…５２ａm と、直列の仮想素子５４は削除されて、並列の仮想素子５５に論理値が「０」の信号が入力する構成となる。この図２２（ａ）に示す回路のブール代数表現は、図２２（ｂ）に示す通りとなる。更にこの図２２（ａ）に示す回路は、図２３（ａ）に示す、より単純な回路に置換えられる。即ち、並列の仮想素子５５は、入力「０」が削除された並列の仮想素子５５ａに変換される、この図２３（ａ）に示す回路のブール代数表現は図２３（ｂ）に示す通りとなる。
【００５５】
以上説明したように本実施の形態に係る複合ゲート縮約処理によって、論理的に等価な回路に変換される。
【００５６】
次に本実施の形態の等価性検証方法を、従来の方法では等価であると検証することのできなかった図３１に示す回路に適用した場合を図２４を参照して説明する。
【００５７】
図２４（ａ）示す基準側回路および図２４（ｂ）に示す検査側回路に各々、直列縮約および並列縮約処理を行って、従来の場合と同様に図２４（ａ′）および図２４（ｂ′）に示す回路に変換する。そこで本実施の形態に係る複合ゲート縮約処理を図２４（ａ′）に示す基準側回路に施すと、直列の仮想素子７２，７３は、図２４（ａ″）に示すように直列の仮想素子７２ａ，７３ａに各々変換されるとともに、これらの直列の仮想素子７２ａ，７３ａと、並列の仮想素子７６との間に並列の仮想素子７４および直列の仮想素子７５が挿入される。そして仮想素子７５に、共通の入力信号が入力される。
【００５８】
その後、図２４（ａ″）に示す回路を、論理的に等価な図２４（ａ´´´ ）に示す回路に変換する。即ち、直列の仮想素子７２ａ，７３ａおよび並列の仮想素子７４は並列の仮想素子７７に変換され、直列の仮想素子７５と並列の仮想素子７６は直列の仮想素子７８に変換される。これにより、図２４（ａ´´´ ）に示す基準側回路と、図２４（ｂ′）に示す検査側回路はトポロジー的に同一となるから、等価であることが検証される。
【００５９】
以上説明したように、本実施の形態の等価性検証方法によれば、等価であるか否かを検証することができる。
【００６０】
【発明の効果】
以上述べたように、本発明によれば、等価であるか否かを検証することができる。
【図面の簡単な説明】
【図１】本発明による等価性検証方法の一実施の形態の処理手順を示すフローチャート。
【図２】本発明に係る複合ゲート縮約処理の処理手順を示すフローチャート。
【図３】本発明の方法を具体的に説明するために使用される回路の構成図。
【図４】図３に示す回路に直列縮約および並列縮約処理を施した後の回路の構成を示すブロック図。
【図５】図４に示す回路に複合ゲート縮約処理を行った後の回路の構成を示すブロック図。
【図６】図５に示す回路の具体的な構成を示す構成図。
【図７】本発明の方法を具体的に説明するために使用される回路の構成図。
【図８】図７に示す回路に直列縮約および並列縮約処理を施した後の回路の構成を示すブロック図。
【図９】図８に示す回路に複合ゲート縮約処理を行った後の回路の構成を示すブロック図。
【図１０】図９に示す回路の具体的な構成を示す構成図。
【図１１】複合ゲート縮約処理の一手順を示す図。
【図１２】複合ゲート縮約処理の一手順を示す図。
【図１３】本発明の方法を具体的に説明するために使用される回路の構成図。
【図１４】図１３に示す回路に直列および並列縮約処理ならびに複合ゲート縮約処理を施したときの回路の構成を示すブロック図。
【図１５】図１４に示す回路に複合ゲート縮約処理を施したときの回路の構成を示すブロック図。
【図１６】図１５に示す回路を論理的に等価でより単純な回路に変換したときの回路の構成を示すブロック図。
【図１７】図１６に示す回路を論理的に等価でより単純な回路に変換したときの回路の構成を示すブロック図。
【図１８】本発明の方法を具体的に説明するために使用される回路の構成図。
【図１９】図１８に示す回路に直列縮約及び並列縮約処理を施したときの回路の構成を示すブロック図。
【図２０】図１９に示す回路に複合ゲート縮約処理を施したときの回路の構成を示すブロック図。
【図２１】図２０に示す回路に複合ゲート縮約処理を施したときの回路の構成を示すブロック図。
【図２２】図２１に示す回路を論理的に等価でより単純な回路に変換したときの回路の構成を示すブロック図。
【図２３】図２２に示す回路を論理的に等価でより単純な回路に変換したときの回路の構成を示すブロック図。
【図２４】本発明の作用効果を説明するために使用される回路図。
【図２５】従来の等価性検証方法の処理手順を示すフローチャート。
【図２６】従来の等価性検証方法を説明するための回路図。
【図２７】直列縮約処理を説明するための回路図。
【図２８】直列縮約処理の処理手順を示すフローチャート。
【図２９】並列縮約処理を説明するための回路図。
【図３０】並列縮約処理の処理手順を示すフローチャート。
【図３１】従来の等価性検証方法の問題点を説明するために使用される回路図。
【図１】
0003813754.tif 000002
【図２】
0003813754.tif 000003
【図３】
0003813754.tif 000004
【図４】
0003813754.tif 000005
【図５】
0003813754.tif 000006
【図６】
0003813754.tif 000007
【図７】
0003813754.tif 000008
【図８】
0003813754.tif 000009
【図９】
0003813754.tif 000010
【図１０】
0003813754.tif 000011
【図１１】
0003813754.tif 000012
【図１２】
0003813754.tif 000013
【図１３】
0003813754.tif 000014
【図１４】
0003813754.tif 000015
【図１５】
0003813754.tif 000016
【図１６】
0003813754.tif 000017
【図１７】
0003813754.tif 000018
【図１８】
0003813754.tif 000019
【図１９】
0003813754.tif 000020
【図２０】
0003813754.tif 000021
【図２１】
0003813754.tif 000022
【図２２】
0003813754.tif 000023
【図２３】
0003813754.tif 000024
【図２４】
0003813754.tif 000025
【図２５】
0003813754.tif 000026
【図２６】
0003813754.tif 000027
【図２７】
0003813754.tif 000028
【図２８】
0003813754.tif 000029
【図２９】
0003813754.tif 000030
【図３０】
0003813754.tif 000031
【図３１】
0003813754.tif 000032