JP2865136B2 - テスト考慮論理合成システム - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、テスト考慮論理合
成システムおよびテスト考慮論理合成方法に関する。

【０００２】

【従来の技術】テスト考慮論理合成システムは、スキャ
ン手法に代表される論理回路のテスト容易性を論理回路
設計後に付加するテスト容易化設計とは、異なる。テス
ト考慮論理合成システムは、論理回路設計中、即ち論理
合成中に、テスト容易性を考慮した最適化処理を実行す
ることにより、テスト容易化設計よりも少い面積オーバ
ーヘッドで、高い故障検出率、テストパタン生成容易な
回路を論理合成するシステムである。

【０００３】従来のテスト考慮論理合成システムの一例
が、文献[F.F.Hsu and J.H.Patel,"A Distance Reducti
on Approach to Design for Testability,"The 13th IE
EE VLSI Test Symposium,pp.158-163,4/30-5/3,1995]に
示されている。このシステムは、有限状態装置（Ｆｉｎ
ａte Ｓｔａte Ｍａｃｈｉｎｅ、ＦＳＭ）を対象とし
たCenter Stateを用いるシステムである。ここでは、Ｆ
ＳＭのテスト容易性の尺度として、全ての状態の組の距
離の平均値を用いている。状態の組の距離とは、現状態
と最終遷移目的先状態の２つの状態からなる状態の組を
考え、その現状態から最終遷移目的先状態へ遷移するた
めに必要な最小のクロック数が状態の組の距離である。
数値が小さい場合は、「距離が近い」といい、大きい場
合には「距離が遠い」という。

【０００４】距離の平均値がＦＳＭのテスト容易性の尺
度になり得る理由は、ＦＳＭから合成された順序回路の
テストパタン長が、状態間の距離に依存するからであ
る。順序回路のテストパタンは、遷移系列、故障活性化
系列、および識別系列の３種類の系列の組の繰り返しか
らなる。遷移系列とは、順序回路の内部状態を現内部状
態から故障活性化系列が必要とする内部状態に遷移させ
る入力パタン系列である。故障活性化系列とは、故障の
影響をフリップフロップ（ＦＦ）あるいは外部出力端子
に伝搬する入力パタンである。識別系列とは、故障活性
化系列によりＦＦに伝搬した故障の影響をＦＦから外部
出力端子に伝搬させるための入力パタン系列である。順
序回路の内部状態とは、順序回路中のＦＦが保持する二
値論理値ベクトルである。例えば、２つのＦＦを持つ順
序回路では、ＦＦが保持する二値論理値ベクトルは“０
０”，“０１”，“１０”，および“１１”の４通りが
あり、それぞれが一つの内部状態である。故障活性化系
列が必要とする内部状態と現在の内部状態とが等しい場
合には、遷移系列は必要ない。故障活性化系列による故
障の影響が外部出力端子に伝搬している場合には、識別
系列は必要ない。ＦＳＭの一つの状態は、順序回路の一
つの内部状態に対応するので、遷移系列による内部状態
の遷移は、ＦＳＭの状態の遷移と等価である。したがっ
て、遷移系列長は、ＦＳＭの状態間の距離に依存する。
それゆえに、ＦＳＭの状態間の距離の短縮は、遷移系列
長を短縮し、かつ順序回路テストパタン長を短縮する効
果がある。長い遷移系列を必要とする順序回路を順序回
路テストパタン自動生成プログラムに入力した場合に
は、テストパタン生成に長大な時間が必要である。よっ
て、プログラム実行時間に制限を与えられた場合に、仮
にテストパタン系列の生成に時間がかかる故障がある
と、その故障に対するテストパタン生成が処理途中で打
ち切られ、別の故障に対するテストパタン生成に処理が
移される。このため、検出される故障数が減り、満足な
故障検出率が得られない場合がある。したがって、ＦＳ
Ｍの状態間の距離を短縮した場合には、合成された結果
の回路は、系列長が短く、故障検出率が高いテストパタ
ンを短時間で生成可能となる。即ち、ＦＳＭの距離の平
均値が小さい方が、テスト容易性が高いといえる。

【０００５】Center Stateを用いたテスト考慮論理合成
システムでは、他の状態への距離の合計が最小である状
態をCenter Stateとする。Center Stateから他の状態へ
の距離が近いことを利用し、各状態からCenter Stateへ
の遷移をＦＳＭに付加することにより、距離の遠い状態
組の距離の短縮を、実現できる。即ち、Center Stateを
経由した近い経路を発生させることにより、距離の短縮
を実現し、テスト容易な順序回路を合成する。あるＦＳ
Ｍ中の３つの状態ＳＴ１，ＳＴ２，およびＳＴ３を考え
る。ＳＴ１からＳＴ３への距離は１であり、ＳＴ２から
ＳＴ３への距離は３であり、ＳＴ２からＳＴ１への距離
は２以上であるとする。ここで、ＳＴ２からＳＴ１への
距離１の経路、即ち遷移を付加することにより、ＳＴ２
からＳＴ３へはＳＴ１を経由した距離２の経路が発生
し、距離が短縮される。これがCenter Stateによる距離
短縮の原理である。

【０００６】次に、図面を参照して、従来のテスト考慮
論理合成システムの詳細を説明する。ＦＳＭには、外部
出力論理値が現状態と外部入力論理値とから決まるＭｅ
ａｌｙ型と、外部出力論理値が現状態のみから決まるＭ
ｏｏｒｅ型とがある。Ｍｏｏｒｅ型は、外部出力論理値
が外部入力論理値に依存しないＭｅａｌｙ型であるとみ
なすことができる。よって、Ｍｅａｌｙ型を用いて説明
を行う。

【０００７】図１１は、従来のテスト考慮論理合成シス
テムの全体構成を示すブロック図である。図１１を参照
して、このテスト考慮論理合成システムは、論理合成対
象回路、テクノロジマッピングに使用するテクノロジラ
イブラリ、ならびに論理合成対象回路の面積および遅延
などの制約条件を保持する記憶部１０１と、テクノロジ
ライブラリを読み込んで記憶部１０１に保持させるライ
ブラリ入力手段１０２と、論理合成対象回路を読み込ん
で記憶部１０１に保持させる回路入力手段１０３と、制
約条件を読み込んで記憶部１０１に保持させる制約条件
入力手段１０４と、記憶部１０１に保持された論理合成
対象回路がＦＳＭ以外の形式で表現されている場合にＦ
ＳＭを抽出するＦＳＭ抽出手段１０５と、記憶部１０１
に保持されたＦＳＭで表現された論理合成対象回路のテ
スト容易性を向上するテスト容易化手段１１０１と、記
憶部１０１に保持されたＦＳＭで表現された論理合成対
象回路の状態に二値論理値ベクトルを割り当てる状態割
り当て手段１０７と、記憶部１０１に保持された論理合
成対象回路の面積を最適化する面積最適化手段１０８
と、記憶部１０１に保持された論理合成対象回路の遅延
を最適化する遅延最適化手段１０９と、記憶部１０１に
保持された論理合成結果の回路を出力する回路出力手段
１１０とを有している。

【０００８】テスト容易化手段１１０１は、ＦＳＭ中の
全ての状態を候補にしてCenter Stateを選択するCenter
State選択手段１１２と、ＦＳＭにCenter Stateへの遷
移を付加する遷移付加手段１１３と、状態割り当て後の
回路にCenter Stateに割り当てられた二値論理値ベクト
ルを生成する論理回路を付加する論理付加手段１１４と
を備えている。

【０００９】図１２は、図１１に示した従来のテスト考
慮論理合成システムの動作を示す図である。以下、図１
１および１２を参照して、このテスト考慮論理合成シス
テムの動作を説明する。

【００１０】処理２０１にて、ライブラリ入力手段１０
２によりテクノロジライブラリ２０２を読み込んで記憶
部１０１に保持する。処理２０３にて、回路入力手段１
０３により回路記述２０４を読み込んで記憶部１０１に
保持する。処理２０５にて、制約条件入力手段１０４に
より制約条件２０６を読み込んで記憶部１０１に保持す
る。処理２０７にて、ＦＳＭ抽出手段１０５により、記
憶部１０１に保持されている回路がＦＳＭ以外の形式で
表現されている場合には、ＦＳＭを抽出し、記憶部１０
１に保持する。処理２０９にてCenter State選択手段１
１２によりCenter Stateを選択する。処理２１０にて、
遷移付加手段１１３により各状態からCenter Stateへの
遷移を付加する。処理２１１にて、状態割り当て手段１
０７により記憶部１０１に保持されているＦＳＭの状態
に二値論理値ベクトルを割り当てる。処理２１２にて、
面積最適化手段１０８により記憶部１０１に保持されて
いる回路に二段論理最適化や論理多段化などのテクノロ
ジライブラリ２０２に依存しない面積の最適化とテクノ
ロジライブラリ２０２を用いたテクノロジに依存した面
積最適化テクノロジマッピングを行う。処理２１３に
て、遅延最適化手段１０９により指定された制約条件２
０６を満足する様に記憶部１０１に保持されている回路
にテクノロジライブラリ２０２に依存しない遅延の最適
化とテクノロジライブラリ２０２を用いたテクノロジに
依存した遅延最適化テクノロジマッピングを行う。処理
２１４にて、回路出力手段１１０により記憶部１０１に
保持されている論理合成結果の回路のネットリスト２１
５を出力する。

【００１１】次に、従来のテスト考慮論理合成システム
のテスト容易化手段１１０１の動作を詳細に説明する。

【００１２】図１３は、テスト容易化手段１１０１の対
象となる２つの外部入力端子と、２つの外部出力端子
と、６つの状態とから構成される非同期リセット状態の
無いＦＳＭの状態遷移表である。

【００１３】図１４は、図１３のＦＳＭの状態遷移グラ
フである。図１４にて、符号３０１〜３０６は、ＦＳＭ
の状態Ａ〜Ｆを示す。符号３０７〜３２０は、状態間の
遷移を示す。遷移のかたわらにて、／で区切られて記載
されている数値は、その遷移が起きる条件である外部入
力論理値とその遷移が起きた時の外部出力論理値であ
り、“外部入力論理値／外部出力論理値”の形式で記述
されている。遷移３０９は、現状態が状態Ａ３０１であ
る時に外部入力端子に論理値“０１”が入力されると、
次のクロックが印加された時に状態Ｂ３０２へ遷移し、
外部出力端子に論理値“０１”を出力することを示す。
遷移３０９は、図１３の状態遷移表の遷移１３０２と等
価である。他も同様である。

【００１４】図６は、Center State選択手段１１２のフ
ローチャートである。処理６０１にて、各状態組の距離
を求める。その結果を図１５に示す。状態Ａ３０１から
状態Ｂ３０２へは遷移３０９を介して１クロックで遷移
するので、図１５のＡ行Ｂ列のますは１となる。状態Ａ
３０１から状態Ｅ３０５へは一旦遷移３０９を介して状
態Ｂ３０２へ遷移し、次に遷移３１２を介して状態Ｅ３
０５へ遷移する２クロックでの遷移が最も距離が近い経
路であるので、図１５のＡ行Ｅ列のますは２となる。他
も同様にして距離を求める。得られた距離の平均値は
２．１６である。処理６０２にて、自分自身への距離を
０とする。その結果を図１６に示す。図１５と比較する
と、Ａ行Ａ列のますが０になっており、他も同様であ
る。処理６０３にて、各状態の他の状態への距離の合計
を求める。その結果を図１６のＳＵＭの列に示す。例え
ば、状態Ａ３０１の他の状態への距離の合計は７であ
る。処理６０４にて、距離の合計が最小である状態をCe
nter Stateに選択する。図１６より、合計が最小である
状態Ａ３０１がCenter Stateに選択される。

【００１５】次に、遷移付加手段１１３により、全ての
状態からCenter Stateへの遷移を付加し、距離の短縮に
よるテスト容易性を付加する。図１７は、遷移付加手段
１１３の動作を示すフローチャートである。

【００１６】処理１７０１にて、Center State制御用外
部入力端子を回路に付加する。Center State制御用外部
入力端子はＦＳＭの遷移を制御するための外部入力端子
で、Center State制御用外部入力端子に二値論理値の一
方が入力された場合には他の外部入力端子の論理値にし
たがって元のＦＳＭと同じ遷移をし、二値論理値の他方
が入力された場合には他の外部入力端子の論理値にかか
わらずCenter Stateへ遷移する。ここでは、Center Sta
te制御用外部入力端子の論理値が“０”である場合には
元のＦＳＭと同じ遷移をし、論理値が“１”の場合には
Center Stateへ遷移する様に動作させるとする。処理１
７０２にて、遷移条件である外部入力の論理値を変更す
る。即ち、遷移の条件である外部入力端子の論理値にCe
nter State制御用外部入力端子の元のＦＳＭと同じ遷移
をする論理値“０”を付加する。

【００１７】処理１７０３にて、Center State制御用外
部入力端子の論理値が“１”の場合には他の外部入力端
子の論理値にかかわらずCenter Stateへ遷移する様に遷
移を付加する。

【００１８】図１８は、遷移付加手段１１３が終了した
ＦＳＭの状態遷移表である。図１９は、そのＦＳＭの状
態遷移グラフである。遷移１３０２は、処理１７０１に
て、遷移１８０２に変更される。遷移１８０２は、遷移
１３０２に対してCenter State制御用外部入力端子の論
理値が“０”であるという条件が加わっている。遷移１
８０２は、遷移１９０２と等価である。他も同様であ
る。処理１７０２にて、遷移１８１５ないし１８２０が
付加される。遷移１８１６は、現状態が状態Ｂ３０２で
Center State制御用外部入力端子の論理値が“１”の場
合にはCenter Stateとして選択された状態Ａ３０１へ遷
移することを示している。他も同様である。ここで、Ce
nter Stateへの遷移時の外部出力端子の論理値を特に指
定をせずにドントケアとしているが、何らかの論理値を
指定してもよい。ドントケアを指定した場合には、後の
面積最適化手段１０８で出力論理値が割り当てられる。
遷移１８１６と遷移１９１５とは、等価である。遷移１
８０１と遷移１８１５とは、現状態と次状態が一致して
いるので、状態遷移グラフでは一つにまとめて遷移１９
０１として記述してある。遷移１８１２と遷移１８１９
とも、一つにまとめて遷移１９１１としてある。

【００１９】上記処理の効果を確認するために図１８で
得られたＦＳＭに対して状態間の距離を求めた結果を図
２０に示す。例えば、図１５のＤ行Ｂ列に示される状態
Ｄ３０４から状態Ｂ３０２への距離が５であるのに対
し、図２０のＤ行Ｂ列に示される距離は２であり、Cent
er Stateへの遷移を付加したことにより距離が短縮され
ている。距離の平均値も図１５では２．１６であるのに
対し、図２０では１．１６であり、距離が短縮され、テ
スト容易性が向上したことが確認できる。

【００２０】次に、図を用いてＦＳＭに対するCenter S
tateへの遷移の付加と等価な効果を、ＦＳＭの状態割当
後の順序回路に対して論理回路を付加することにより実
現する論理付加手段１１４を用いる従来のテスト考慮論
理合成システムの動作を説明する。

【００２１】図２１は、論理付加手段１１４を用いる従
来のテスト考慮論理合成システムの動作を示すフローチ
ャートである。

【００２２】図２１は、図１２の遷移付加手段１１３を
用いる場合とは異なり、Center State選択手段１１２適
用後に状態割り当て手段１０７を適用し、その後に論理
付加手段１１４を適用している。即ち、遷移付加手段１
１３は適用していない。

【００２３】次に、論理付加手段１１４を用いる従来の
テスト考慮論理合成システムの動作を詳細に説明する。

【００２４】処理２０９のCenter State選択手段１１２
迄の手順は、前述の遷移付加手段１１３を適用する場合
と同様であるため、省略する。次に、処理２１１にて、
状態割り当て手段１０７により、各状態に内部状態の二
値論理値ベクトルを割り当てる。状態割り当てに関して
は周知の技術であるため、詳細の説明は省略する。

【００２５】図２２は、状態割り当て手段１０７の結果
の順序回路を示す図である。６つの状態を表現するため
に３つのＦＦを生成する。これは、ＦＦによる表現可能
な内部状態数が２のＦＦ数乗であるため、６つの状態を
表現可能な最小のＦＦの個数が３であるからである。状
態割り当て手段１０７により、ＦＳＭは、図２２に示す
様に、外部入力端子２２１２の論理値とＦＦ出力論理値
２２０５〜２２０７とから外部出力端子２２１３の論理
値とＦＦデータ入力論理２２０８〜２２１０とを生成す
る組合せ回路２２０１と、内部状態を保持するＦＦ２２
０２〜２２０４と、ＦＦ出力論理値２２０５〜２２０７
と、ＦＦの入力論理値である内部状態の各ビットを生成
するＦＦデータ入力論理２２０８〜２２１０と、ＦＦの
クロック２２１１と、外部入力端子２２１２と外部出力
端子２２１３で表現される順序回路に変換される。

【００２６】図２３は、論理付加手段１１４の動作を示
すフローチャートである。図２４は、図２２の順序回路
に論理付加手段１１４を適用した結果の順序回路を示す
図である。

【００２７】Center State選択手段１１２が選択した状
態Ａ３０１には、状態割り当て手段１０７により、内部
状態として二値論理値ベクトル“０１０”が割り当てら
れたとする。即ち、ＦＦ２２０２の保持する論理値が
“０”で、ＦＦ２２０３の保持する論理値が“１”で、
さらにＦＦ２２０４の保持する論理値が“０”である場
合が状態Ａ３０１と等価となる。したがって、ＦＦ２２
０２〜２２０４への入力論理値がCenter State制御用入
力端子に論理値“０”が入力された場合には、ＦＦデー
タ入力論理２２０８〜２２１０の論理値となり、Center
State制御用入力端子に論理値“１”が入力された場合
には二値論理値ベクトル“０１０”となるように回路を
変更すれば、Center Stateへの遷移を付加した場合と等
価な効果が得られることになる。

【００２８】処理２３０１にて、Center State制御用外
部入力端子２４０１を回路に付加する。処理２３０２に
て、未処理のＦＦの有無を判断し、未処理のＦＦがある
場合には処理２３０３に進み、未処理のＦＦが無い場合
には論理付加手段１１４を終了する。処理２３０３で
は、未処理のＦＦを一つ抽出して処理済みとする。ここ
では、まずＦＦ２２０２が抽出されたとする。処理２３
０４にて、ＦＦに割り当てられたCenter Stateの論理値
が判断され、論理値“０”が割り当てられている場合に
は処理２３０５へ進み、論理値“１”が割り当てられて
いる場合には処理２３０８へ進む。ＦＦ２２０２には論
理値“０”が割り当てられているので、処理２３０５に
進む。処理２３０５では、Center State制御用外部入力
端子の反転論理を生成するＮＯＴ素子の有無が判断さ
れ、ＮＯＴ素子がある場合には処理２３０７へ進み、Ｎ
ＯＴ素子が無い場合には処理２３０６へ進む。この場合
は、ＮＯＴ素子は無いので、処理２３０６へ進む。処理
２３０６では、Center State制御用外部入力端子の反転
論理を生成するＮＯＴ素子２４０２を回路に付加し、Ｎ
ＯＴ素子２４０２の入力端子とCenter State制御用外部
入力端子２４０１とを接続する。処理２３０７では、二
入力ＡＮＤ素子２４０３を付加し、一方の入力端子とＮ
ＯＴ素子２４０２の出力端子を接続し他方の入力端子と
ＦＦデータ入力論理２２０８とを接続し、ＦＦデータ入
力論理２２０８とＦＦ２２０２のデータ入力との接続を
切り離し、二入力ＡＮＤ素子２４０３の出力端子をＦＦ
２２０２のデータ入力端子に接続し、処理２３０２へ進
む。この変更により、ＦＦ２２０２のデータ入力端子へ
の入力論理値は、以下の数式１

【００２９】

【数１】 となり、所望の論理値がＦＦ２２０２に入力される。

【００３０】次に、処理２３０３にて、ＦＦ２２０３が
選択されたとする。処理２３０４にて、ＦＦに割り当て
られたCenter Stateの論理値が判断され、ＦＦ２２０３
には論理値“１”が割り当てられているので処理２３０
８へ進む。処理２３０８では、二入力ＯＲ素子２４０４
を付加し、一方の入力端子にはCenter State制御用外部
入力端子２４０１を接続し、他方の入力端子にはＦＦデ
ータ入力論理２２０９を接続し、ＦＦデータ入力論理２
２０９とＦＦ２２０３のデータ入力との接続を切り離
し、二入力ＯＲ素子２４０４の出力端子をＦＦ２２０３
のデータ入力端子に接続する。この変更により、ＦＦ２
２０３のデータ入力端子への入力論理値は、 Center State制御用入力端子２４０１＋ＦＦデータ入力
論理２２０９ （＋は論理和を表す）となり、所望の論理値がＦＦ２２
０３に入力される。

【００３１】ＦＦ２２０４の場合は、ＮＯＴ素子２４０
２が既に存在するために処理２３０５から処理２３０７
に進むことを除いてＦＦ２２０２に対する処理と同様で
あるので説明は省略する。

【００３２】以上の説明では、論理素子を用いてCenter
Stateに割り当てられた内部状態二値論理値ベクトルを
生成する論理回路を実現したが、実際に適用する場合に
は面積最適化手段１０８および遅延最適化手段１０９の
テクノロジマッピングで使用するテクノロジライブラリ
２０２中の実際の素子を用いてもよく、テクノロジライ
ブラリ２０２に依存しない論理そのものを挿入してもよ
い。

【００３３】また、テスト容易性付加手段を状態割り当
て手段１０７直後に実行する様に説明したが、論理合成
が後に実行する面積最適化手段１０８および遅延最適化
手段１０９中に実行してもよい。ただし、ＦＦを組合せ
回路を跨いで移動させることにより遅延を最適化するリ
タイミング技術を応用した遅延最適化を適用する以前に
実行しなければならない。リタイミングは、回路中のＦ
Ｆの個数やＦＦデータ入力の論理を変更するので、Cent
er Stateと等価な内部状態が状態割り当て手段１０７が
割り当てた二値論理値ベクトルから別の二値論理値ベク
トルに変化してしまうためである。

【００３４】Center Stateを用いたテスト考慮論理合成
システムはＦＳＭを対象とするが、ＦＳＭ抽出手段１０
５により、ネットリストの様なＦＳＭ以外の形式で表現
された順序回路からＦＳＭを抽出し、抽出したＦＳＭに
対して適用してもよい。

【００３５】

【発明が解決しようとする課題】以上説明した例をも含
めた従来のテスト考慮論理合成システムの問題点は、非
同期リセット状態あるいは非同期リセット状態からの距
離が近い状態がCenter Stateとして選択された場合に、
テスト容易化の効果が得られないか、あるいは得られて
も効果が少いことである。

【００３６】この理由は、非同期リセット状態はその機
能により全ての状態からの遷移が可能であるため、新た
に非同期リセット状態への遷移を付加したとしても状態
間の距離は全く短縮されないからである。非同期リセッ
ト状態からの距離が近い状態も、既に非同期リセット状
態を介した経路が存在するために、距離を短縮する効果
が少い。

【００３７】図３は、図１４のＦＳＭの状態Ａ３０１が
非同期リセット状態である場合の状態遷移グラフであ
る。非同期リセット遷移３２１は、非同期リセット制御
外部入力端子ＲＳＴが論理値“１”の場合に、他の外部
入力端子およびクロックにかかわらず非同期リセット状
態である状態Ａ３０１に遷移することを示す。このＦＳ
Ｍに対して距離を求めた結果は、図５になる。非同期リ
セット状態への遷移のクロック数は０であるが、遷移す
るためのパタンが１パタン必要であるので、便宜上、１
クロックかかる、即ち距離１として処理する。ここで、
従来の技術を用いてCenter Stateを選択すると、状態Ａ
３０１がCenter Stateに選択され、CenterStateへの遷
移を付加したとしても距離は短縮されず、テスト容易性
は向上しない。

【００３８】本発明の課題は、非同期リセット状態を考
慮することにより、非同期リセット状態を有するＦＳＭ
に対してもテスト容易性が向上する、より効果の高いCe
nterStateの選択が可能なテスト考慮論理合成システム
を提供することである。

【００３９】

【課題を解決するための手段】本発明によれば、Center
Stateに選択してもテスト容易性が向上しない非同期リ
セット状態、およびテスト容易性向上の効果が少い非同
期リセット状態からの距離が近い状態を、Center State
の候補から除外するCenter State候補選択手段を備えて
たテスト容易化手段を有するテスト考慮論理合成システ
ムが得られる。

【００４０】Center Stateに選択されてもテスト容易性
向上の効果の少い非同期リセット状態および非同期リセ
ット状態からの距離が近い状態が、Center Stateの候補
から除外されているため、例え非同期リセット状態ある
いは非同期リセット状態からの距離が近い状態から、他
の状態への距離の合計が小さくても、Center Stateとし
て選択されない。

【００４１】

【発明の実施の形態】以下、図面を参照して、本発明の
実施の形態によるテスト考慮論理合成システムについて
説明する。

【００４２】［実施の形態１］図１は、本発明の実施の
形態１の全体構成を示すブロック図である。図１を参照
して、本システムは、論理合成対象回路、テクノロジマ
ッピングに使用するテクノロジライブラリ、ならびに論
理合成対象回路の面積および遅延などの制約条件を保持
する記憶部１０１と、テクノロジライブラリを読み込ん
で記憶部１０１に保持させるライブラリ入力手段１０２
と、論理合成対象回路を読み込んで記憶部１０１に保持
させる回路入力手段１０３と、制約条件を読み込んで記
憶部１０１に保持させる制約条件入力手段１０４と、記
憶部１０１に保持された論理合成対象回路がＦＳＭ以外
の形式で表現されている場合にＦＳＭを抽出するＦＳＭ
抽出手段１０５と、記憶部１０１に保持されたＦＳＭで
表現された論理合成対象回路のテスト容易性を向上する
テスト容易化手段１０６と、記憶部１０１に保持された
ＦＳＭで表現された論理合成対象回路の状態に二値論理
値ベクトルを割り当てる状態割り当て手段１０７と、記
憶部１０１に保持された論理合成対象回路の面積を最適
化する面積最適化手段１０８と、記憶部１０１に保持さ
れた論理合成対象回路の遅延を最適化する遅延最適化手
段１０９と、記憶部１０１に保持された論理合成結果の
回路を出力する回路出力手段１１０とを有している。

【００４３】テスト容易化手段１０６は、非同期リセッ
ト状態および非同期リセット状態からの距離が近い状態
をCenter Stateの候補から除外する、即ち非同期リセッ
ト状態からの距離が遠い状態をCenter Stateの候補とし
て選択するCenter State候補選択手段１１１と、選択さ
れた候補の状態からCenter Stateを選択するCenter Sta
te選択手段１１２と、ＦＳＭにCenter Stateへの遷移を
付加する遷移付加手段１１３と、状態割り当て後の回路
にCenter Stateに割り当てられた二値論理値ベクトルを
生成する論理回路を付加する論理付加手段１１４とを備
えている。

【００４４】図２は、図１に示した従来のテスト考慮論
理合成システムの動作を示す図である。以下、図１およ
び２を参照して、実施の形態１によるテスト考慮論理合
成システムの動作を説明する。

【００４５】処理２０１にて、ライブラリ入力手段１０
２によりテクノロジライブラリ２０２を読み込んで記憶
部１０１に保持する。処理２０３にて、回路入力手段１
０３により回路記述２０４を読み込んで記憶部１０１に
保持する。処理２０５にて、制約条件入力手段１０４に
より制約条件２０６を読み込んで記憶部１０１に保持す
る。処理２０７にて、ＦＳＭ抽出手段１０５により記憶
部１０１に保持されている回路がＦＳＭ以外の形式で表
現されている場合にはＦＳＭを抽出し、記憶部１０１に
保持する。

【００４６】処理２０８にて、Center State候補選択手
段１１１により非同期リセット状態および非同期リセッ
ト状態からの距離が近い状態をCenter Stateの候補から
除外する。

【００４７】処理２０９にて、Center State選択手段１
１２によりCenter Stateを選択する。処理２１０にて、
遷移付加手段１１３により各状態からCenter Stateへの
遷移を付加する。処理２１１にて、状態割り当て手段１
０７により記憶部１０１に保持されているＦＳＭの状態
に二値論理値ベクトルを割り当てる。処理２１２にて、
面積最適化手段１０８により記憶部１０１に保持されて
いる回路に二段論理最適化や論理多段化などのテクノロ
ジライブラリ２０２に依存しない面積の最適化とテクノ
ロジライブラリ２０２を用いたテクノロジに依存した面
積最適化テクノロジマッピングを行う。処理２１３に
て、遅延最適化手段１０９により記憶部１０１に保持さ
れている回路に指定された制約条件２０６を満足する様
にテクノロジライブラリ２０２に依存しない遅延の最適
化とテクノロジライブラリ２０２を用いたテクノロジに
依存した遅延最適化テクノロジマッピングを行う。処理
２１４にて、回路出力手段１１０により記憶部１０１に
保持されている論理合成結果の回路のネットリスト２１
５を出力する。

【００４８】実施の形態１の効果について説明する。実
施の形態１は、Center Stateの選択を全ての状態を候補
とせずに、非同期リセット状態自身および非同期リセッ
ト状態からの距離が近い状態をCenter Stateの候補から
除外するので、非同期リセット状態からの距離が遠く且
つ距離の短縮の効果のある状態がCenter Stateとして選
択される。このため、非同期リセット状態を持つＦＳＭ
に対して本発明を適用した場合には、非同期リセット状
態を考慮しない場合と比べてより距離の短縮の効果の高
い状態がCenter Stateに選択される効果がある。

【００４９】［実施の形態２］本発明の実施の形態２に
よるテスト考慮論理合成システムは、図１に示した実施
の形態１のCenter State候補選択手段１１１が、可能な
距離の最大値が状態数に依存することを利用して、非同
期リセット状態からの距離が近いか遠いかを判断する例
である。即ち、実施の形態２では、Center State候補選
択手段１１１は、非同期リセット状態からの距離が近い
か遠いかを判断する尺度として、状態数を利用した計算
式の計算結果の数値を閾値として用い、論理付加手段１
１４によりテスト容易性を付加する。

【００５０】ここでは、Center State候補選択手段１１
１が計算式として状態数の平方根を２で割った数値を閾
値として用いる。また、論理付加手段１１４が、状態割
り当て手段１０７により生成する順序回路の組合せ回路
部分が２段論理で表現されている時点で、その２段論理
に対してCenter Stateに割り当てられた内部状態二値論
理値ベクトルを生成する論理、即ちキューブを付加す
る。

【００５１】実施の形態２の第１の効果は、非同期リセ
ット状態からの距離の遠近の判断の閾値に状態数を用い
た計算式の計算結果を用いるので、全ての状態の組の距
離を求める必要がないことである。

【００５２】第２の効果は、状態割り当て手段１０７適
用後の組合せ回路を表現する２段論理に対して、Center
Stateへの遷移と等価な論理のキューブを付加すること
により、遷移付加手段２１０により遷移を付加した場合
や論理付加手段２１０１で論理素子を付加した場合と同
等のテスト容易性が得られることである。

【００５３】次に、実施の形態２の動作を説明する。

【００５４】図３０は、実施の形態２の動作を示すフロ
ーチャートである。実施の形態１の場合とは異なり、処
理２０９にて、Center State選択手段１１２適用後に処
理２１１にて、状態割り当て手段１０７を適用し、その
後に処理２１０にて、論理付加手段１１４を適用し、遷
移付加手段１１３は適用していない。

【００５５】次に、本発明の第２の実施の形態のテスト
容易化手段１０６の動作を詳細に説明する。

【００５６】図３のＦＳＭが論理合成対象のＦＳＭであ
るとする。

【００５７】処理２０８にて、Center State候補選択手
段１１１によりCenter State候補を選択する。

【００５８】図４はCenter State候補選択手段１１１の
詳細な動作を表すフローチャートである。

【００５９】処理４０１にて、非同期リセット状態が無
い場合は、処理４０２へ進み、全ての状態をCenter Sta
teの候補に選択してCenter State候補選択手段１１１を
終了する。非同期リセット状態がある場合には、処理４
０３へ進む。

【００６０】処理４０３にて、非同期リセット状態から
の距離の遠近の判断の尺度である閾値を求める。閾値は
状態数の平方根を２で割った数値であるので、状態数が
６であることから、閾値１．２２が求められる。

【００６１】処理４０４にて、非同期リセット状態から
の距離を算出する。算出した結果を図２９に示す。

【００６２】処理４０５にて、Center Stateの候補を空
にする。

【００６３】処理４０６にて、非同期リセット状態を選
別済みとし、Center Stateの候補から除外する。ここで
状態Ａ３０１はCenter Stateに選択されなくなる。

【００６４】処理４０７にて、Center Stateの候補とな
るか選別されていない状態の有無を判断し、全ての状態
が選別済みであればCenter State候補選択手段１１１を
終了し、選別されていない状態が残っている場合には処
理４０８へ進む。

【００６５】処理４０８にて、選別されていない状態を
一つ抽出し、選別済みとする。まず状態Ｂ３０２が抽出
されたとする。

【００６６】処理４０９にて、処理４０３にて、求めた
閾値と処理４０８にて、抽出した状態の処理４０４に
て、求めた非同期リセット状態からの距離を比較し、距
離が近い場合には処理４０７に進み距離が遠い場合には
処理４１０に進む。状態Ｂ３０２の非同期リセット状態
Ａ３０１からの距離は１であるので、閾値１．２２と比
較した結果、非同期リセット状態からの距離は近いと判
断され、処理４０７へ進む。

【００６７】処理４１０では、処理４０７にて抽出した
状態をCenter Stateの候補に加え、処理４０７へ進む。

【００６８】次に、処理４０８にて、状態Ｅ３０５が抽
出されたとする。

【００６９】処理４０９にて、状態Ｅ３０５の非同期リ
セット状態からの距離２が閾値１．２２と比較され、非
同期リセット状態からの距離は遠いと判断され、処理４
１０に進み、状態Ｅ３０５はCenter Stateの候補に加え
られ、処理４０７へ進む。

【００７０】Center State候補選択手段１１１が終了し
た結果、非同期リセット状態からの距離が閾値１．２２
よりも遠い状態は状態Ｅ３０５と状態Ｆ３０６であり、
この２つの状態がCenter Stateの候補となる。

【００７１】次にCenter State選択手段１１２によりCe
nter State候補選択手段１１１で選択された候補からCe
nter Stateを選択する。

【００７２】図６はCenter State選択手段１１２の詳細
な動作を表すフローチャートである。

【００７３】処理６０１にて、Center State候補状態間
の距離を求める。この時の最短経路にはCenter State候
補になっていない状態も経路として使用してよい。結果
を図７に示す。

【００７４】処理６０２にて、自分自身への距離を０と
する。結果を図８に示す。図７とは異なりＥ行Ｅ列とＦ
行Ｆ列のますが０になっている。

【００７５】処理６０３にて、Center State候補各状態
の距離の合計を求める。結果を図８のＳＵＭの列に示
す。

【００７６】処理６０４にて、距離の合計が最小である
状態をCenter Stateに選択する。図８より、状態Ｅ３０
５からの距離の合計が３であり、状態Ｆ３０６からの距
離の合計が２であるので、距離の合計値が最小である状
態Ｆ３０６をCenter Stateに選択する。

【００７７】次に、処理２１１にて、状態割り当て手段
１０７によりＦＳＭの各状態に内部状態二値論理値ベク
トルを割り当てる。

【００７８】従来例でも説明したが、状態割り当て手段
１０７はＦＳＭを状態を割り当てられた内部状態二値論
理値ベクトルで表現するためのＦＦと、外部入力端子論
理値とＦＦの出力論理値から外部出力端子論理値とＦＦ
のデータ入力論理値を生成する組合せ回路で表現する。
この組合せ回路の一表現方法が多入力多出力２段論理で
ある。この２段論理にCenter Stateに割り当てられた内
部状態二値論理値ベクトルを生成するキューブを付加す
る。

【００７９】図２５は、図３のＦＳＭに状態割り当て手
段１０７を適用して得られた各状態に割り当てられた内
部状態二値論理値ベクトルを示す図である。ＦＦ２５０
９〜２５１１が生成され、状態Ａ３０１には内部状態
“０００”（２５０１）が割り当てられていることを示
す。“１０１”（２５０７）、“１１１”（２５０８）
は割り当てに使用されなかった二値論理値ベクトルであ
る。

【００８０】図２６は、図３のＦＳＭに状態割り当て手
段１０７を適用して得られた組合せ回路部分を表す２段
論理を示す図である。：で区切られた左側が入力論理値
を表し、右側が出力論理値を示す。入力論理値は外部入
力端子論理値とＦＦの出力論理値により構成され、出力
論理値はＦＦへのデータ入力論理値と外部出力端子論理
値から構成される。ＦＦの出力論理値とＦＦデータ入力
論理値は共に、ＦＦ２５０９，ＦＦ２５１０，ＦＦ２５
１１の順に記述してある。

【００８１】例えば、キューブ２６０２は外部入力端子
論理値が“０１”でＦＦの内部状態が“０００”の時に
クロックが印加されると、ＦＦの内部状態を“０１０”
に、外部出力端子論理値を“０１”にすることを示して
いる。これは遷移３０９と等価である。また、キューブ
２６１５は未使用の二値論理値ベクトル“１０１”（２
５０７）をドントケアとして用いているキューブであ
る。他も同様である。

【００８２】図２７は、Center Stateに割り当てられた
内部状態二値論理値ベクトルを生成するキューブを付加
する論理付加手段１１４の動作を示すフローチャートで
ある。

【００８３】図２８は、キューブを付加する論理付加手
段１１４を図２６の２段論理に適用した結果である。

【００８４】処理２７０１により、Center State制御用
外部入力端子の論理値を各キューブに付加する。Center
State制御用外部入力端子の論理値が“０”の場合には
元の動作をし、“１”の場合にはCenter Stateに割り当
てられた内部状態二値論理値ベクトルを生成する。例え
ば、キューブ２６０１にはCenter State制御用外部入力
端子の論理値が“０”であるという条件が付加され、キ
ューブ２８０１に変更されている。他も同様である。

【００８５】処理２７０２により、Center Stateに割り
当てられた二値論理値ベクトルを生成するキューブを付
加する。キューブ２８１７が付加したキューブである。
キューブ２８１７はCenter State制御用外部入力端子の
論理値が“１”である場合に、他の外部入力端子論理値
およびＦＦの出力論理値にかかわらずＦＦデータ入力論
理値を“１１０”すなわちCenter Stateに選択された状
態Ｆ３０６に割り当てられた二値論理値ベクトル２５０
６を生成し、外部出力端子の論理値はドントケアとして
いる。

【００８６】したがって、生成された回路はキューブ２
８０１〜２８１６により、Center State制御用外部入力
端子の論理値が“０”の場合には、元の回路と同じ動作
をする。一方、キューブ２８１７によりCenter State制
御用外部入力端子の論理値が“１”の場合には、ＦＦ２
５０９〜２５１１の値をCenter Stateに選択された状態
Ｆ３０６に割り当てられた内部状態二値論理値ベクトル
“１１０”にする。よって、論理素子を付加する論理付
加手段１１４と同じ効果が得られる。

【００８７】

【実施例】次に、本発明の実施の形態１の実施例を説明
する。本実施例では、まず、テスト容易化手段１０６の
一実施例の動作を詳細に説明する。

【００８８】図３は、記憶部１０１に保持されている論
理合成対象の非同期リセット状態のある２つの外部入力
端子と２つの外部出力端子と６つの状態からなるＦＳＭ
の状態遷移グラフである。非同期リセット状態は状態Ａ
３０１である。図４は、Center State候補選択手段１１
１の詳細な動作を表すフローチャートである。

【００８９】図３および４を参照して、処理４０１に
て、非同期リセット状態が無い場合は、処理４０２に進
み全ての状態をCenter Stateの候補に選択してCenter S
tate候補選択手段１１１を終了する。非同期リセット状
態がある場合には、処理４０３へ進む。この場合は非同
期リセット状態があるので処理４０３へ進む。

【００９０】処理４０３にて、非同期リセット状態から
の距離の遠近の判断の尺度である閾値を求める。距離が
近いか遠いかを判断する尺度としては、距離の平均値
を閾値として、非同期リセット状態からの距離の数値が
平均値よりも小さい状態をCenter Stateの候補から除外
することにより、非同期リセット状態から遠い状態を候
補として選択する尺度、可能な距離の最大値が状態数
に依存することから状態数を利用した計算式、例えば状
態数の平方根などの計算結果を閾値として、非同期リセ
ット状態からの距離の数値が計算結果よりも小さい状態
をCenter Stateの候補から除外することにより、非同期
リセット状態から遠い状態を候補として選択する尺度、
あるいは選択すべき候補の状態の個数が指定され、非
同期リセット状態からの距離が遠い状態から順番に指定
された選択すべき候補の個数を上限に候補を選択する尺
度等が考えられる。ここでは、距離の平均値を尺度と
して用いる。

【００９１】処理４０３にて、距離の遠近の判断尺度で
ある閾値を求める。距離の平均値を求めるために全ての
状態の組の距離を求め、その結果を図５に示す。距離の
平均値は１．６１である。

【００９２】処理４０４にて、非同期リセット状態から
他の状態への距離を求める。処理４０３にて、閾値を求
める段階で非同期リセット状態からの距離は既に求まっ
ているので、この距離を流用する。即ち、図５のＡ行
が、非同期リセット状態からの距離である。

【００９３】処理４０５にて、Center Stateの候補を空
にする。

【００９４】処理４０６にて、非同期リセット状態を選
別済みとし、Center Stateの候補から除外する。ここで
状態Ａ３０１はCenter Stateに選択されなくなる。

【００９５】処理４０７にて、Center Stateの候補とな
るか選別されていない状態の有無を判断する。全ての状
態が選別済みであれば、Center State候補選択手段１１
１を終了する。選別されていない状態が残っている場合
には、処理４０８へ進む。

【００９６】処理４０８にて、選別されていない状態を
一つ抽出し、選別済みとする。まず状態Ｂ３０２が抽出
されたとする。

【００９７】処理４０９にて、処理４０８にて抽出した
状態の処理４０４にて求めた非同期リセット状態からの
距離を、処理４０３にて求めた閾値と比較し、距離が近
い場合には処理４０７へ進み、一方距離が遠い場合には
処理４１０へ進む。状態Ｂ３０２の非同期リセット状態
Ａ３０１からの距離は１であるので、閾値１．６１と比
較した結果、非同期リセット状態からの距離は近いと判
断され、処理４０７へ進む。

【００９８】処理４１０では、処理４０７にて、抽出し
た状態をCenter Stateの候補に加え、処理４０７へ進
む。

【００９９】次に、処理４０８にて、状態Ｅ３０５が抽
出されたとする。

【０１００】処理４０９にて、状態Ｅ３０５の非同期リ
セット状態からの距離２が閾値１．６１と比較され、非
同期リセット状態からの距離は遠いと判断され、処理４
１０へ進み、状態Ｅ３０５はCenter Stateの候補に加え
られ、処理４０７へ進む。

【０１０１】Center State候補選択手段１１１が終了し
た結果、非同期リセット状態からの距離が距離の平均値
１．６１よりも遠い状態は、状態Ｅ３０５と状態Ｆ３０
６であり、この２つの状態がCenter Stateの候補とな
る。

【０１０２】次に、Center State選択手段１１２により
Center State候補選択手段１１１で選択された候補から
Center Stateを選択する。

【０１０３】図６は、Center State選択手段１１２の詳
細な動作を表すフローチャートである。

【０１０４】処理６０１にて、Center State候補状態間
の距離を求める。この時の最短経路には、Center State
候補になっていない状態も経路として使用してよい。Ce
nterState候補選択手段１１１で既に距離が求められて
いる場合には、その結果を流用してよい。本実施例で
は、処理４０３にて、閾値を求める段階で既に求まって
いるのでそれを流用する。この場合は、図５のＥ行Ｅ
列、Ｅ行Ｆ列、Ｆ行Ｅ列、およびＦ行Ｆ列のますを抽出
すればよい。結果を図７に示す。

【０１０５】処理６０２にて、自分自身への距離を０と
する。結果を図８に示す。図７とは異なりＥ行Ｅ列とＦ
行Ｆ列のますが０になっている。

【０１０６】処理６０３にて、Center State候補各状態
の距離の合計を求める。結果を図８のＳＵＭの列に示
す。

【０１０７】処理６０４にて、距離の合計が最小である
状態をCenter Stateに選択する。図８より、状態Ｅ３０
５からの距離の合計が３であり、状態Ｆ３０６からの距
離の合計が２であるので、距離の合計値が最小である状
態Ｆ３０６をCenter Stateに選択する。

【０１０８】次に、遷移付加手段１１３により全ての状
態からCenter State選択手段１１２でCenter Stateに選
択された状態Ｆ３０６への遷移を付加し、距離の短縮に
よるテスト容易性を付加する。図９は、遷移を付加した
結果のＦＳＭの状態遷移グラフである。

【０１０９】図９のＦＳＭの各状態組間の距離を求めた
結果を図１０に示す。距離の平均値は１．４１であり、
従来の技術では短縮されなかった距離の平均値が短縮さ
れている。

【０１１０】

【発明の効果】本発明によるテスト考慮論理合成システ
ムは、非同期リセット状態を考慮することにより、非同
期リセット状態を有するＦＳＭに対してもテスト容易性
が向上し、より効果の高いCenter Stateの選択が可能で
ある。

【０１１１】この理由は、全ての状態からの遷移が可能
である非同期リセット状態、および非同期リセット状態
からの距離が近い、即ち非同期リセット状態を介した経
路が存在するために距離を短縮する効果が少ない状態を
Center Stateの候補から除外して、Center Stateとして
選択しないからである。

【図面の簡単な説明】

【図１】本発明の全体構成を示すブロック図である。

【図２】本発明の動作を表すフローチャートである。

【図３】論理合成対象の非同期リセット状態のあるＦＳ
Ｍの状態遷移グラフである。

【図４】Center state候補選択手段１１１の詳細な動作
を表すフローチャートである。

【図５】図３の状態遷移グラフの状態間の距離の表であ
る。

【図６】Center state選択手段１１２の詳細な動作を表
すフローチャートである。

【図７】Center state候補状態間の距離の表である。

【図８】Center state選択処理の途中経過の表である。

【図９】テスト容易化手段１０６適用後のＦＳＭの状態
遷移グラフである。

【図１０】図９の状態遷移グラフの状態間の距離の表で
ある。

【図１１】従来のテスト考慮論理合成システムの全体構
成を示すブロック図である。

【図１２】従来のテスト考慮論理合成システムの動作を
表すフローチャートである。

【図１３】非同期リセット状態の無いＦＳＭの状態遷移
表である。

【図１４】図１３のＦＳＭの状態遷移グラフである。

【図１５】図１４の状態遷移グラフの状態間の距離の表
である。

【図１６】図１５の状態間の距離の表に処理６０２から
処理６０３を適用した結果の表である。

【図１７】遷移付加手段１１３の動作を示すフローチャ
ートである。

【図１８】遷移付加手段１１３が終了したＦＳＭの状態
遷移表である。

【図１９】図１８のＦＳＭの状態遷移グラフである。

【図２０】図１８の状態遷移グラフの状態間の距離の表
である。

【図２１】論理付加手段１１４を用いる従来のテスト考
慮論理合成システムの動作を示すフローチャートであ
る。

【図２２】状態割り当て手段１０７の結果の順序回路を
示す図である。

【図２３】論理付加手段１１４の動作を示すフローチャ
ートである。

【図２４】図２２の順序回路に論理付加手段１１４を適
用した結果の順序回路を示す図である。

【図２５】図３のＦＳＭに状態割り当て手段１０７を適
用して得られた各状態に割り当てられた内部状態二値論
理値ベクトルを示す図である。

【図２６】図３のＦＳＭに状態割り当て手段１０７を適
用して得られた組合せ回路部分を表す２段論理を示す図
である。

【図２７】Center stateに割り当てられた内部状態二値
論理値ベクトルを生成するキューブを付加する論理付加
手段１１４の動作を示すフローチャートである。

【図２８】キューブを付加する論理付加手段１１４を図
２６の２段論理に適用した結果である。

【図２９】図３のＦＳＭの非同期リセット状態から他の
状態への距離を求めた結果である。

【図３０】本発明の第２の実施の形態の動作を示すフロ
ーチャートである。

【符号の説明】

１０１ 記憶部 １０２ ライブラリ入力手段 １０３ 回路入力手段 １０４ 制約条件入力手段 １０５ ＦＳＭ抽出手段 １０６ テスト容易化手段 １０７ 状態割り当て手段 １０８ 面積最適化手段 １０９ 遅延最適化手段 １１０ 回路出力手段 １１１ Center State候補選択手段 １１２ Center State選択手段 １１３ 遷移付加手段 １１４ 論理付加手段 ２０１ ライブラリ入力処理 ２０２ テクノロジライブラリ ２０３ 回路入力処理 ２０４ 回路記述 ２０５ 制約条件入力処理 ２０６ 制約条件 ２０７ ＦＳＭ抽出処理 ２０８ Center State候補選択処理 ２０９ Center State選択処理 ２１０ 遷移付加処理 ２１１ 状態割り当て処理 ２１２ 面積最適化処理 ２１３ 遅延最適化処理 ２１４ 回路出力処理 ２１５ ネットリスト ３０１〜３０６ ＦＳＭの状態 ３０７〜３２０ ＦＳＭの状態間の遷移 ３２１ 非同期リセット遷移 ４０１ 非同期リセット状態有無判断処理 ４０２ 全状態候補選択処理 ４０３ 遠近判断尺度閾値算出処理 ４０４ 非同期リセット状態からの距離算出処理 ４０５ Center state候補初期化処理 ４０６ 非同期リセット状態除外処理 ４０７ 未選別状態有無判断処理 ４０８ 未選別状態抽出処理 ４０９ 遠近判断処理 ４１０ Center state候補追加処理 ６０１ 状態間距離算出処理 ６０２ 自己距離リセット処理 ６０３ 距離合計算出処理 ６０４ Center state決定処理 ９０１〜９０８ Center state制御用外部入力端子の
論理値を遷移条件に加えた遷移３０７〜３１４ ９０９ Center stateへの遷移条件とCenter state制
御用外部入力端子の論理値を遷移条件に加えた遷移３１
５ ９１０〜９１２ Center state制御用外部入力端子の
論理値を遷移条件に加えた遷移３１６〜３１８ ９１３ Center stateへの遷移条件とCenter state制
御用外部入力端子の論理値を遷移条件に加えた遷移３１
９ ９１４ Center state制御用外部入力端子の論理値を
遷移条件に加えた遷移３２０ ９１５〜９１８ Center stateへの遷移 １１０１ 従来のテスト考慮論理合成システムのテス
ト容易化手段 １３０１〜１３１４ 遷移 １７０１ Center state制御用外部入力端子付加処理 １７０２ 遷移条件変更処理 １７０３ Center stateへの遷移付加処理 １８０１〜１８１４ Center state制御用外部入力端
子の論理値を遷移条件に加えた遷移１３０１〜１３１４ １８１５〜１８２０ 付加されたCenter stateへの遷
移 １９０１ Center stateへの遷移条件とCenter state
制御用外部入力端子の論理値を遷移条件に加えた遷移３
０７ １９０２〜１９１０ Center state制御用外部入力端
子の論理値を遷移条件に加えた遷移３０８〜３１６ １９１５ Center stateへの遷移条件とCenter state
制御用外部入力端子の論理値を遷移条件に加えた遷移３
１７ １９１６〜１９１８ Center state制御用外部入力端
子の論理値を遷移条件に加えた遷移３１８〜３２０ ２１０１ 論理付加処理 ２２０１ 組合せ回路 ２２０２〜２２０４ ＦＦ ２２０５〜２２０７ ＦＦの出力論理値 ２２０８〜２２１０ ＦＦのデータ入力論理 ２２１１ ＦＦのクロック ２２１２ 外部入力端子 ２２１３ 外部出力端子 ２３０１ Center state制御用外部入力端子付加処理 ２３０２ 未処理ＦＦ有無判断処理 ２３０３ 未処理ＦＦ抽出処理 ２３０４ 割り当て論理値判断処理 ２３０５ ＮＯＴ素子有無判断処理 ２３０６ ＮＯＴ素子付加処理 ２３０７ 二入力ＡＮＤ素子付加処理 ２３０８ 二入力ＯＲ素子付加処理 ２４０１ Center state制御用外部入力端子 ２４０２ ＮＯＴ素子 ２４０３ 二入力ＡＮＤ素子 ２４０４ 二入力ＯＲ素子 ２４０５ 二入力ＡＮＤ素子 ２５０１〜２５０６ 図３のＦＳＭの状態に割り当て
られた内部状態二値論理値ベクトル ２５０７〜２５０８ 図３のＦＳＭの状態に割り当て
られず、未使用となった二値論理値ベクトル ２５０９〜２５１１ 内部状態二値論理値ベクトルを
保持するＦＦ ２６０１〜２６１４ 遷移を表すキューブ ２６１５〜２６１６ 未使用となった二値論理値ベク
トルをドントケアするキューブ ２７０１ Center state制御用外部入力端子付加処理 ２７０２ Center state二値論理値ベクトル生成キュ
ーブ付加処理 ２８０１〜２８１６ Center state制御用外部入力端
子論理値を付加したキューブ２６０１〜２６１６ ２８１７ Center state二値論理値ベクトル生成キュ
ーブ

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】 論理合成対象回路、テクノロジマッピン
   グに使用するテクノロジライブラリ、ならびに論理合成
   対象回路の面積および遅延などの制約条件を保持する記
   憶部と、テクノロジライブラリを読み込んで前記記憶部
   に保持させるライブラリ入力手段と、論理合成対象回路
   を読み込んで前記記憶部に保持させる回路入力手段と、
   制約条件を読み込んで前記記憶部に保持させる制約条件
   入力手段と、前記記憶部に保持された論理合成対象回路
   がＦＳＭ以外の形式で表現されている場合にＦＳＭを抽
   出するＦＳＭ抽出手段と、前記記憶部に保持されたＦＳ
   Ｍで表現された論理合成対象回路のテスト容易性を向上
   するテスト容易化手段と、前記記憶部に保持されたＦＳ
   Ｍで表現された論理合成対象回路の状態に二値論理値ベ
   クトルを割り当てる状態割り当て手段と、前記記憶部に
   保持された論理合成対象回路の面積を最適化する面積最
   適化手段と、前記記憶部に保持された論理合成対象回路
   の遅延を最適化する遅延最適化手段と、前記記憶部に保
   持された論理合成結果の回路を出力する回路出力手段と
   を有し、前記テスト容易化手段は、ＦＳＭを対象にＦＳ
   ＭのCenter Stateを用いて状態間の距離を短縮してテス
   ト容易性を向上させるものであるテスト考慮論理合成シ
   ステムにおいて、 前記テスト容易化手段は、Center Stateに選択してもテ
   スト容易性が向上しない非同期リセット状態、およびテ
   スト容易性向上の効果が少い非同期リセット状態からの
   距離が近い状態を、Center Stateの候補から除外するCe
   nter State候補選択手段を備えていることを特徴とする
   テスト考慮論理合成システム。
2. 【請求項２】 前記テスト容易化設計手段の前記Center
   State候補選択手段は、 （Ａ）非同期リセット状態の有無を判断する工程と、 （Ｂ）工程（Ａ）にて非同期リセット状態が無い場合に
   は全ての状態をCenterStateの候補とする工程と、 （Ｃ）工程（Ａ）にて非同期リセット状態がある場合に
   は非同期リセット状態からの距離の遠近判断尺度閾値を
   算出する工程と、 （Ｄ）全ての状態の非同期リセット状態からの距離を算
   出する工程と、 （Ｅ）Center State候補を空とする工程と、 （Ｆ）非同期リセット状態をCenter Stateの候補から除
   外し、非同期リセット状態を選択済みとする工程と、 （Ｇ）未選別状態の有無を判断する工程と、 （Ｈ）工程（Ｇ）にて未選別状態がある場合には未選別
   状態の中から状態を一つ抽出し選別済みとする工程と、 （Ｉ）工程（Ｈ）で抽出された状態の工程（Ｄ）にて算
   出された非同期リセット状態からの距離と工程（Ｃ）に
   て算出された閾値とを比較して距離の遠近を判断する工
   程と、 （Ｊ）工程（Ｉ）にて距離が遠いと判断された場合には
   工程（Ｈ）にて抽出された状態をCenter Stateの候補に
   加える工程とを実行するものであることを特徴とする請
   求項１に記載のテスト考慮論理合成システム。
3. 【請求項３】 前記テスト容易化手段は、ＦＳＭ中の全
   ての状態を候補にしてCenter Stateを選択するCenter S
   tate選択手段と、ＦＳＭにCenter Stateへの遷移を付加
   する遷移付加手段と、状態割り当て後の論理合成対象回
   路に、CenterStateに割り当てられた二値論理値ベクト
   ルを生成する論理回路を付加する論理付加手段とを備え
   ていることを特徴とする請求項１または２に記載のテス
   ト考慮論理合成システム。