JP2000067105A

JP2000067105A - 集積回路の検査容易化設計方法

Info

Publication number: JP2000067105A
Application number: JP11106082A
Authority: JP
Inventors: Toshinori Hosokawa; 利典細川; Toshihiro Hiraoka; 敏洋平岡
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1998-06-08
Filing date: 1999-04-14
Publication date: 2000-03-03
Also published as: US20030009716A1; EP0964257A1; US6510535B1; TW466401B

Abstract

(57)【要約】【課題】スキャン化ＦＦを同定する検査容易化設計方
法として、従来よりも検査系列生成を容易にする。【解決手段】集積回路からＦＦ関係グラフを作成し
（ＳＡ１）、このＦＦ関係グラフからセルフループを構
成するＦＦを認識した上で（ＳＡ２）、全てのＦＦをス
キャン化する（ＳＡ３）。そして、セルフループを構成
しない全ＦＦを、検査系列生成の困難度との関連度合を
表す所定の評価指標に従って、ソートする（ＳＡ４）。
例えば、平衡再収斂構造との関連度合を表す指標を評価
指標として用いる。このソート順に、セルフループを構
成しない各ＦＦについて、非スキャン化すると仮定した
ときに集積回路がｎ重整列構造になるか否かの判定を行
い、スキャン化するか否かを決定する（ＳＡ５〜ＳＡ
８）。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、集積回路の検査容
易化設計手法に関するものである。

【０００２】

【従来の技術】従来の検査容易化設計の手法の代表的な
ものとして、スキャン設計方法がある。スキャン設計方
法とは、論理設計された集積回路内のフリップフロップ
（ＦＦ）を、外部から直接に制御（スキャンイン）およ
び観測（スキャンアウト）可能なスキャンＦＦに置き換
え、スキャンＦＦを外部入出力として扱うことによっ
て、検査系列の生成が容易になるようにするものである
（1990年，コンピュータサイエンスプレス（Computer S
cience Press）社発行，「Digital Systems Tesingand
Testable DESIGN」，９章デザインフォーテスタビリテ
ィ（Design For Testability）参照）。

【０００３】スキャン設計には、回路中の全てのＦＦを
スキャンＦＦに置き換えるフルスキャン設計手法と、回
路中の一部のＦＦをスキャンＦＦに置き換えるパーシャ
ルスキャン設計手法とがある。フルスキャン設計手法
は、テスト回路の付加による面積増大、速度低下、消費
電力増加といった問題を生じるが、パーシャルスキャン
設計はこれらの問題を低減することができる。パーシャ
ルスキャン設計におけるスキャン化するＦＦの同定方法
については、「An Exact Algorithm for Selecting Part
ial Scan Flipflop」(1994年,DAC(design automation co
nference),pp81〜pp86)とその参考文献に詳しく書かれ
ている。

【０００４】また、集積回路がｎ重整列構造になるよう
にスキャン化するＦＦを同定するという手法がすでに提
案されている（「A partial scan design method based
onn-fold line up structures」（1997年，6th Asian
test symposium, PP306-311）参照）。「ｎ重整列構
造」とは、故障検査系列生成が容易な構造（例えば特開
平１０−１２４５６２号公報参照）であり、ｎ重整列構
造になるようスキャン化ＦＦを同定することによって、
従来のパーシャルスキャン設計では得られないような高
い故障検出率を得ることができる。

【０００５】図５１は集積回路がｎ重整列構造になるよ
うにスキャン化するＦＦを同定する手順を示すフローチ
ャートである。まず、全てのＦＦをスキャン化して（Ｓ
Ｊ３）、いわゆるフルスキャンの回路を構成する。そし
て、あるスキャンＦＦを非スキャン化したときに回路構
造がｎ重整列構造になるか否かを判定し、ｎ重整列構造
になるときはそのＦＦを非スキャン化するものと決定す
る一方、そうでないときはそのＦＦをスキャン化するも
のと決定する（ＳＪ５〜ＳＪ７）。このような処理を、
セルフループを構成しない全てのＦＦに対して実行する
（ＳＪ４）。

【０００６】

【発明が解決しようとする課題】ところが、従来のアル
ゴリズムでは、集積回路がｎ重整列構造になるようにス
キャン化するＦＦを同定するものの、同定した後の集積
回路のスキャン化率については考慮していない。このた
め、検査容易化設計の結果として、スキャン化率が必要
以上に高まることがある。スキャン化率が高ければ、そ
の分、集積回路に付加するテスト回路の面積が増大する
ため、パーシャルスキャンの利点が薄まることになる。

【０００７】また、本願発明者の検討によると、従来の
アルゴリズムでは、スキャン化するか否かの判定を行う
ＦＦの順序によって、集積回路のスキャン化率や、検査
系列生成の困難度に、大きな差が出ることが分かった。

【０００８】前記の問題に鑑み、本発明は、スキャン化
するＦＦまたはレジスタを同定する検査容易化設計方法
として、より高い故障検出効率が得られるようにするこ
とを課題とする。

【０００９】

【課題を解決するための手段】前記の課題を解決するた
めに、請求項１の発明が講じた解決手段は、ゲートレベ
ルまたはレジスタ・トランスファ・レベルで設計された
集積回路に対し、製造後の検査が容易になるよう、設計
変更を行う検査容易化設計方法として、前記集積回路の
全てのフリップフロップ（ＦＦ）またはレジスタをスキ
ャン化するものとして仮決定するフルスキャン処理と、
ＦＦまたはレジスタのソートを検査系列生成の困難度と
の関連度合を表す所定の評価指標に従って行うソート処
理と、前記フルスキャン処理においてスキャン化するも
のとして仮決定された各ＦＦまたはレジスタについて、
前記ソート処理によって得たソート順に従って、当該Ｆ
Ｆまたはレジスタをスキャン化しないものと仮定したと
きに前記集積回路がｎ重整列構造になるか否かを判定
し、ｎ重整列構造になるときは、スキャン化しないもの
として仮決定する一方、ｎ重整列構造にならないとき
は、スキャン化するものとする仮決定を維持する非スキ
ャン化選択処理とを備え、非スキャン化選択処理を実行
した結果、スキャン化するものとして仮決定されている
ＦＦまたはレジスタを、スキャン化するＦＦまたはレジ
スタとして確定するものである。

【００１０】請求項１の発明によると、各ＦＦまたはレ
ジスタについて、検査系列生成困難度との関連度合を表
す所定の評価指標に従ったソート順に、スキャン化する
か否かの判定が行われる。このため、検査系列の生成が
より容易な回路を得ることができ、従来よりも故障検出
効率が向上する。

【００１１】請求項２の発明では、前記請求項１の発明
におけるソート順は、前記所定の評価指標が表す関連度
合が低い方から高い方への順であるものとする。

【００１２】請求項３の発明では、前記請求項１の発明
におけるソート処理は、前記集積回路が有する平衡再収
斂構造を認識し、認識した平衡再収斂構造との関連度合
を表す指標を前記所定の評価指標としてＦＦまたはレジ
スタのソートを行うものとする。

【００１３】請求項４の発明では、前記請求項１の発明
におけるソート処理は、前記集積回路を表すＦＦ関係グ
ラフまたはレジスタ関係グラフにおける入出力数を前記
所定の評価指標としてＦＦまたはレジスタのソートを行
うものとする。

【００１４】請求項５の発明では、前記請求項１の発明
におけるソート処理は、最大順序入力距離および最大順
序出力距離を用いた所定の演算の演算結果を前記所定の
評価指標としてＦＦまたはレジスタのソートを行うもの
とする。

【００１５】請求項６の発明では、前記請求項１の発明
における非スキャン化選択処理は、セルフループ構造を
持つものとして認識したＦＦまたはレジスタについては
前記判定処理を省き、スキャン化するものとする仮決定
を維持するものとする。

【００１６】請求項７の発明では、前記請求項１の発明
は、前記集積回路から単一出力ＦＦまたは単一出力レジ
スタを探索する処理を備え、前記非スキャン化選択処理
は、探索された単一出力ＦＦまたは単一出力レジスタに
ついては前記判定処理を省き、スキャン化するものとす
る仮決定を維持するものとする。

【００１７】請求項８の発明では、前記請求項１の発明
は、前記集積回路から単一入出力ＦＦまたは単一入出力
レジスタを探索する処理を備え、前記非スキャン化選択
処理は、探索された単一出力ＦＦまたは単一出力レジス
タについては前記判定処理を省き、スキャン化するもの
とする仮決定を維持するものとする。

【００１８】また、請求項９の発明が講じた解決手段
は、ゲートレベルまたはレジスタ・トランスファ・レベ
ルで設計された集積回路に対し、製造後の検査が容易に
なるよう、設計変更を行う検査容易化設計方法として、
前記集積回路が所定の条件を満たす平衡再収斂構造を有
さないように、スキャン化するＦＦまたはレジスタを決
定するものである。

【００１９】請求項１０の発明では、前記請求項９の発
明における所定の条件は、段数が所定値以上であること
とする。

【００２０】請求項１１の発明では、前記請求項９の発
明における所定の条件は、経路数が所定値以上であるこ
ととする。

【００２１】請求項１２の発明では、前記請求項９の発
明における所定の条件は、ＦＦ数が所定値以上であるこ
ととする。

【００２２】また、請求項１３の発明が講じた解決手段
は、ゲートレベルまたはレジスタ・トランスファ・レベ
ルで設計された集積回路に対し、製造後の検査が容易に
なるよう、設計変更を行う検査容易化設計方法として、
前記集積回路がｎ重整列構造になるようにスキャン化す
べきフリップフロップ（ＦＦ）またはレジスタを決定す
るものであり、ＦＦまたはレジスタのソートを検査系列
生成の困難度との関連度合を表す所定の評価指標に従っ
て行うソート処理を備え、このソート処理によって得た
ソート順に従って、前記集積回路のＦＦまたはレジスタ
についてスキャン化すべきか否かを決定するものであ
る。

【００２３】請求項１４の発明では、前記請求項１３に
おけるソート処理は、前記集積回路が有する平衡再収斂
構造を認識し、認識した平衡再収斂構造との関連度合を
表す指標を前記所定の評価指標として、ＦＦまたはレジ
スタのソートを行うものとする。

【００２４】請求項１５の発明では、前記請求項１３に
おけるソート処理は、前記集積回路のＦＦ関係グラフま
たはレジスタ関係グラフにおける入出力数を前記所定の
評価指標として、ＦＦまたはレジスタのソートを行うも
のとする。

【００２５】請求項１６の発明では、前記請求項１３に
おけるソート処理は、最大順序入力距離および最大順序
出力距離を用いた所定の演算の演算結果を前記所定の評
価指標として、ＦＦまたはレジスタのソートを行うもの
とする。

【００２６】また、請求項１７の発明が講じた解決手段
は、ゲートレベルまたはレジスタ・トランスファ・レベ
ルで設計された集積回路に対し、製造後の検査が容易に
なるよう、設計変更を行う検査容易化設計方法として、
前記集積回路がｎ重整列構造になるようにスキャン化す
べきフリップフロップ（ＦＦ）またはレジスタを決定す
るものであり、前記集積回路の中から単一出力ＦＦまた
は単一出力レジスタを探索する処理を備え、探索された
単一出力ＦＦまたは単一出力レジスタはスキャン化しな
いものと決定するものである。

【００２７】また、請求項１８の発明が講じた解決手段
は、ゲートレベルまたはレジスタ・トランスファ・レベ
ルで設計された集積回路に対し、製造後の検査が容易に
なるよう、設計変更を行う検査容易化設計方法として、
前記集積回路がｎ重整列構造になるようにスキャン化す
べきフリップフロップ（ＦＦ）またはレジスタを決定す
るものであり、前記集積回路の中から単一入出力ＦＦま
たは単一入出力レジスタを探索する処理を備え、探索さ
れた単一出力ＦＦまたは単一出力レジスタはスキャン化
しないものと決定するものである。

【００２８】

【発明の実施の形態】(第１の実施形態)本発明の第１の
実施形態は、検査系列生成を困難にすると予想される
「平衡再収斂構造」という回路構造を利用して、スキャ
ン化するか否かの判定処理を行うＦＦの順をソートする
ことを特徴とする。

【００２９】図１は平衡再収斂構造を示す概念図であ
る。回路のＦＦ関係グラフ中の再収斂構造において、再
収斂構造の起点となるＦＦまたは（擬似）外部入力のこ
とを再収斂構造の分岐点（以後、単に分岐点と呼ぶ）と
呼び、再収斂構造の終点となるＦＦまたは（擬似）外部
出力のことを再収斂構造の再収斂点と呼ぶ。「ＦＦ関係
グラフ」とは、回路の外部入出力とＦＦとの間の、組合
せ論理を除いたときの接続関係を示す有向グラフであ
る。

【００３０】ＦＦ関係グラフの再収斂構造において、分
岐点から再収斂点までの全ての経路に、同じ順序深度
（１以上）を持つ再収斂経路が２つ以上存在する構造
を、「平衡再収斂構造」と定義する。特に順序深度ｊ、
経路数ｋのとき、この平衡再収斂構造のことを、段数
ｊ、多重度ｋの「ｊ段ｋ重平衡再収斂構造」と呼ぶ。ま
た、分岐点ＢＲから再収斂点ＲＣのｊ段ｋ重平衡再収斂
構造を、（ＢＲ，ＲＣ）（ｊ，ｋ）と表すことにする。

【００３１】次に、平衡再収斂構造を含む回路の検査系
列生成が困難になることについて、図２を用いて説明す
る。

【００３２】図２は２段３重平衡再収斂構造を含む回路
を示す図である。図２において、ＮＡＮＤ１ゲートの出
力信号線の１縮退故障（ｓ−ａ−１）について検査系列
を生成する場合を考える。図２に示すように、故障を励
起するためには、ＮＡＮＤ１の出力信号線の正常値を
“０”にする必要があり、このために、ＦＦ１，ＦＦ
２，ＦＦ３にそれぞれ“１”を割り当てる。

【００３３】ＦＦ１の“１”を正当化するためにＸＯＲ
１に“１”を割り当てる。そして、ＸＯＲ１の“１”を
正当化するために、ＸＯＲ１の２つの入力に“１”と
“０”を割り当てるような選択を行う。ここでは、ＦＦ
４側に“０”を割り当てたとする（選択割当Ａ）。同様
に、ＦＦ２の“１”を正当化するために、ＯＲ１に
“１”を割り当てる。そして、ＯＲ１の“１”を正当化
するためにＯＲ１の１つの入力に“１”を割り当てるよ
うな選択を行う。ここでは、ＦＦ５側に“１”を割り当
てたとする（選択割当Ｂ）。さらに、ＦＦ３の“１”を
正当化するために、ＦＦ６に“１”を割り当てる。

【００３４】ＦＦ４の“０”、ＦＦ５の“１”、ＦＦ６
の“１”をそれぞれ正当化すると、信号線ａにおいて矛
盾が発生する。この場合には、バックトラック処理が必
要になる。

【００３５】この例の場合、ＸＯＲ１とＯＲ１の値の正
当化で選択が発生し、それぞれの選択に対して、前述し
たような選択割当Ａ，Ｂを行ったために、信号線ａにお
いて矛盾が発生した。このように、回路が平衡再収斂構
造を含んでいる場合には、検査系列生成において矛盾を
発生する可能性が高くなる。

【００３６】そこで、図３に示すように、ＦＦ１，ＦＦ
６をスキャン化して、回路中の平衡再収斂構造を削除す
ると、信号線ａにおいて矛盾が発生することなく、検査
系列生成が可能になる。

【００３７】このように、平衡再収斂構造は、集積回路
の検査容易性を低下させる要因となる。したがって、本
実施形態では、「平衡再収斂構造」との関連度合を表す
指標を利用して、スキャン化するか否かの判定処理を行
うＦＦの順をソートし、これによって、スキャン化によ
る故障検出効率をより向上させる。

【００３８】図４〜図６は本発明の第１の実施形態に係
る検査容易化設計方法を示すフローチャートである。

【００３９】まず図４において、ステップＳＡ１では、
検査容易化設計を行う対象となる集積回路について、Ｆ
Ｆ関係グラフを作成する。ステップＳＡ２では、ステッ
プＳＡ１で作成したＦＦ関係グラフから、セルフループ
を構成するＦＦを認識する。そしてステップＳＡ３にお
いて、集積回路の全てのＦＦをスキャン化するものと仮
決定する。

【００４０】ステップＳＡ４では、セルフループを構成
しない全てのＦＦを、検査系列生成の困難度との関連度
合を表す所定の評価指標に従って、ソートする。本実施
形態では、集積回路が有する平衡再収斂構造を認識し、
認識した平衡再収斂構造との関連度合を表す指標を所定
の評価指標として利用して、ＦＦのソートを行う。この
ソートのための評価指標には、ＦＦが属する平衡再収斂
構造の段数や多重度、またはＦＦが属する再収斂経路の
本数などを基にした重み付けを行う。

【００４１】ステップＳＡ５では、セルフループを構成
しない全てのＦＦについて、ステップＳＡ６〜ＳＡ８の
処理を行ったか否かを判定する。

【００４２】ステップＳＡ６では、未処理のＦＦをステ
ップＳＡ４で得たソート順に選択し、そのＦＦを非スキ
ャン化するものと仮定する。そしてステップＳＡ７にお
いて、集積回路がｎ重整列構造であるか否かの判定を行
い、ｎ重整列構造であるときは、そのＦＦをそのまま非
スキャン化すると仮決定してステップＳＡ５にもどる一
方、ｎ重整列構造でないときはステップＳＡ８に進み、
そのＦＦを再びスキャン化すると仮決定する。

【００４３】非スキャン化選択処理ＳＡ５〜ＳＡ８を実
行した結果、スキャン化するものとして仮決定されてい
るＦＦを、スキャン化するＦＦとして確定する。

【００４４】図５は図４のステップＳＡ４の詳細を示す
フローチャートである。

【００４５】まず、全てのＦＦのソート用の重みを０に
初期化し（ＳＡ１１）、セルフループを構成していない
全てのＦＦを非スキャン化する（ＳＡ１２）。ステップ
ＳＡ１３では、非スキャン化した全てのＦＦと、全ての
外部入力（ＰＩ）および擬似外部入力（ＰＰＩ）とに対
して、ステップＳＡ１４〜ＳＡ２０の処理を行ったか否
かを判定する。全て処理を終了したときはステップＳＡ
１７に進む一方、そうでないときはステップＳＡ１４に
進む。

【００４６】ステップＳＡ１４では、未処理のＦＦまた
は（擬似）外部入力のうちの１つをノードとして選択す
る。ＦＦ関係グラフにおいて、ステップＳＡ１４で選択
したノードが複数の出力を持つか否かを判定し（ＳＡ１
５）、複数の出力を持つときはステップＳＡ２０に進
み、そうでないときはステップＳＡ１３にもどる。

【００４７】ステップＳＡ２０では、ステップＳＡ１４
で選択したノードを分岐点として、平衡再収斂経路の探
索を行う。ここでの平衡再収斂構造の探索は、いわゆる
時間軸展開と同様にして行う。そして、その探索結果に
基づき、各ＦＦのソートのための評価指標に、重み付け
を行う。

【００４８】ステップＳＡ１７では、ステップＳＡ１４
〜ＳＡ２０で計算した評価指標の値を基にして、全ての
ＦＦを指標値の小さい方から順にソートする。そして、
全てのＦＦを再びスキャン化する（ＳＡ１８）。

【００４９】図６は図５のステップＳＡ２０の詳細を示
すフローチャートである。

【００５０】まず、現在の探索位置を０とし、ステップ
ＳＡ１４で選択したノードを分岐点として探索位置０に
配置する（ＳＡ２１）。そして、分岐点の１つ先の出力
に相当するノードを全て探索位置１に配置する（ＳＡ２
２）。探索位置を現探索位置から１つ進めて（ＳＡ２
３）、予め与えた探索終了条件を判定し（ＳＡ２４）、
この探索終了条件を満たすときはステップＳＡ２０を終
了する一方、そうでないときはステップＳＡ２５に進
む。

【００５１】ステップＳＡ２５では、現探索位置Ｔに配
置された全ノードに対して、ステップＳＡ２６，ＳＡ２
７が終了したか否かを判定する。終了したときはステッ
プＳＡ２８に進み、終了していないときはステップＳＡ
２６に進む。ステップＳＡ２６では、現探索位置Ｔに配
置されたノードの中から未処理のノードを１つ選択し、
そして、選択したノードの１つ先の出力に相当するノー
ドを全て探索位置Ｔ＋１に配置する（ＳＡ２７）。

【００５２】一方、ステップＳＡ２８では、探索位置Ｔ
＋１に配置されたノードのうち再収斂点に相当するノー
ドが存在するか否かを判定する。存在するときは、ステ
ップＳＡ２９に進み、存在しないときはステップＳＡ２
３に戻る。

【００５３】ステップＳＡ２９では、探索位置Ｔ＋１の
全ての再収斂点に対して、ステップＳＡ３０，ＳＡ３１
が終了した否かを判定する。終了したときはステップＳ
Ａ２３に戻り、そうでないときはステップＳＡ３０に進
む。ステップＳＡ３０では、未処理の再収斂点を１つ選
択し、そして、分岐点からステップＳＡ３０で選択した
再収斂点までの再収斂経路上のＦＦの評価指標に、所定
の計算式によって計算した重みを加える（ＳＡ３１）。

【００５４】図４〜図６に示すフローチャートに従っ
て、本実施形態に係る検査容易化設計方法について、具
体的な回路例を用いて説明する。ここでの説明では、ス
テップＳＡ１において、図７に示すようなＦＦ関係グラ
フが検査容易化設計の対象となる集積回路から得られた
ものとする。

【００５５】なおここでの説明では、ステップＳＡ７に
おいて、ｎ＝２とする。すなわち、集積回路が「２重整
列構造」になるか否かによって、ＦＦをスキャン化する
か否かを決定する。なお、ｎの値を「２」としたのは説
明の便宜上であり、他の値に設定してもかまわない。

【００５６】また、ステップＳＡ３１において、ＦＦが
ｊ段ｋ重平衡再収斂構造の再収斂経路に属するとき、そ
のＦＦに重みとして（ｊ×ｋ）を与えるものとする。こ
の（ｊ×ｋ）という計算式は、再収斂経路において段数
ｊおよび多重度ｋが大きい経路ほど検査系列生成が困難
になることを考慮して、設定したものである。なお、こ
の重みの計算式は本実施形態の説明のために設定したも
のであり、他の計算式を設定することも可能である。さ
らに、ステップＳＡ２４において、探索終了条件とし
て、探索位置の最大値を６とする。すなわち、６つ先の
出力まで探索したときは、そこでステップＳＡ２０を終
了する。

【００５７】まず、ステップＳＡ２，ＳＡ３において、
図７のＦＦ関係グラフではセルフループを構成するＦＦ
は存在しないので、全てのＦＦをスキャン化する。

【００５８】次いで、ソート処理ＳＡ４を実行する。図
６のＦＦ関係グラフにおいて、複数の出力を有するノー
ドすなわちＦＦまたは外部入出力はＡ，Ｃ，Ｅ，Ｆ，Ｋ
の５つである。すなわちソート処理ＳＡ４では、この５
個のノードＡ，Ｃ，Ｅ，Ｆ，Ｋを分岐点として、ステッ
プＳＡ２０を順に実行する。

【００５９】まず、ノードＡを分岐点としてステップＳ
Ａ２０を実行する。図８〜１３はノードＡを分岐点とし
たステップＳＡ２０の実行結果を示す図である。

【００６０】図８（ａ）に示すように、探索位置０に配
置されたノードは｛Ａ｝、探索位置１に配置されたノー
ドは｛Ｂ，Ｅ，Ｆ｝、探索位置２に配置されたノードは
｛Ｃ，Ｆ，Ｉ，Ｇ，Ｊ｝である。このとき、探索位置２
におけるノードＩが再収斂点であり、太矢印で示すよう
に分岐点Ａ、再収斂点Ｉの１段２重平衡再収斂構造が認
識される（ＳＡ２８）。これにより、図８（ｂ）に示す
ように、この１段２重平衡再収斂構造を構成する再収斂
経路上のノードＥ，Ｆの評価指標に、重みとして２（＝
１×２）が加えられる（ＳＡ３１）。

【００６１】同様にして、図９に示すように、分岐点
Ａ、再収斂点Ｇの２段２重平衡再収斂構造が認識され、
この２段２重平衡再収斂構造を構成する再収斂経路上の
各ノードの評価指標に、重みとして４（＝２×２）が加
えられる。また、図１０に示すように、分岐点Ａ、再収
斂点Ｈの２段２重平衡再収斂構造が認識され、この２段
２重平衡再収斂構造を構成する再収斂経路上の各ノード
の評価指標に、重みとして４（＝２×２）が加えられ
る。

【００６２】さらに、図１１に示すように、分岐点Ａ、
再収斂点ＰＯの３段４重平衡再収斂構造が認識され、こ
の３段４重平衡再収斂構造を構成する再収斂経路上の各
ノードの評価指標に、重みとして１２（＝３×４）が加
えられる。ただし、複数の再収斂経路に属するノード
Ｆ，Ｈには、重み１２に、属する再収斂経路の個数（こ
こでは２）を乗じた値２４が、その評価指標に重みとし
て加えられる。また、図１２に示すように、分岐点Ａ、
再収斂点Ｊの４段２重平衡再収斂構造が認識され、この
４段２重平衡再収斂構造を構成する再収斂経路上の各ノ
ードの評価指標に、重みとして８（＝４×２）が加えら
れる。ただし、図１１の場合と同様に、複数の再収斂経
路に属するノードＦには、重み８に、属する再収斂経路
の個数（ここでは２）を乗じた値１６が、その評価指標
に重みとして加えられる。さらに、図１３に示すよう
に、分岐点Ａ、再収斂点ＰＯの４段３重平衡再収斂構造
が認識され、この４段３重平衡再収斂構造を構成する再
収斂経路上の各ノードに、重みとして１２（＝４×３）
が加えられる。ただし、図１１，図１２の場合と同様
に、複数の再収斂経路に属するノードＧ，Ｈには、重み
１２に、属する再収斂経路の個数（ここでは２）を乗じ
た値２４が、その評価指標に重みとして加えられる。

【００６３】図１４〜図１７はそれぞれ、他のノード
Ｃ，Ｅ，Ｆ，Ｋを分岐点としたステップＳＡ２０の実行
結果を示す図である。図１４，図１５および図１７に示
すように、ノードＣ，Ｅ，Ｋを分岐点とする平衡再収斂
構造は存在しない。一方、図１６に示すように、分岐点
Ｆ、再収斂点ＰＯの２段２重平衡再収斂構造が認識さ
れ、この２段２重平衡再収斂構造を構成する再収斂経路
上の各ノードの評価指標に、重みとして４（＝２×２）
が加えられる。

【００６４】図１８は図８〜図１７に示す平衡再収斂構
造の探索によって得られた各ＦＦの評価指標の値を示す
図である。各ＦＦを評価指標の値の小さいものから順に
ソートすると、｛Ａ，Ｄ，Ｌ，Ｉ，Ｅ，Ｊ，Ｋ，Ｂ，
Ｃ，Ｈ，Ｇ，Ｆ]となる。これは、評価指標が表す平衡
再収斂構造との関連度合が、低い方から高い方への順に
相当する。

【００６５】ステップＳＡ５〜ＳＡ８において、このソ
ート順にスキャン化判定を行う。Ａ，Ｄ，Ｌ，Ｉ，Ｅ，
Ｊまでは順に非スキャン化しても、図７の回路は２重整
列構造である。ところが、Ｋを非スキャン化すると、
Ｊ，Ｋ，Ｌからなる順序回路ループが構成されるため、
２重整列構造ではなくなる。したがって、Ｋはスキャン
化すると決定する。さらに、Ｂを非スキャン化しても、
図７の回路は２重整列構造である。ところがＣを非スキ
ャン化すると、ＡとＰＰＯＦ（スキャン化しているＦの
入力に対応する擬似外部入力）との間に、０｛Ａ→ＰＰ
ＯＦ｝、１｛Ａ→Ｅ→ＰＰＯＦ｝、および３｛Ａ→Ｂ→
Ｃ→Ｄ→ＰＰＯＦ｝の３種類の順序深度の経路が存在す
ることになり、図７の回路は２重整列構造ではなくな
る。したがって、Ｃはスキャン化すると決定する。同様
にして、Ｆもスキャン化すると決定する。

【００６６】この結果、図７の回路を２重整列構造にす
るために、図１９に示すように、Ｃ，Ｋ，Ｆの３つのＦ
Ｆがスキャンするものとして決定される。この図１９の
回路には、平衡再収斂構造が存在しない。

【００６７】一方、本実施形態の比較例として、スキャ
ン化判定するＦＦの選択順をランダムにした場合、例え
ば、ＦＦの判定順を前述したソート順の逆の順序すなわ
ち｛Ｆ，Ｈ，Ｇ，Ｃ，Ｂ，Ｋ，Ｊ，Ｅ，Ｉ，Ｌ，Ｄ，
Ａ｝とした場合を考える。この場合、図２０に示すよう
に、図７の回路に対して、Ｉ，Ｌ，Ｄの３つのＦＦがス
キャンするものとして決定される。

【００６８】図２１は図２０の回路に対する時間軸展開
の結果を示す図である。図２１から分かるように、図２
０の回路には、分岐点Ａから、ＰＰＯＩまでの１段２重
平衡再収斂構造、Ｇまでの２段２重平衡再収斂構造、Ｈ
までの２段２重平衡再収斂構造、およびＰＯまでの３段
３重平衡再収斂構造および４段２重平衡再収斂構造が存
在し、さらに、分岐点ＦからＰＯまでの２段２重平衡再
収斂構造が存在する。すなわち、合計６個の平衡再収斂
構造が存在する。

【００６９】以上のように本実施形態によると、検査容
易化設計の結果、従来よりも平衡再収斂構造が少ない集
積回路を得ることができるので、故障検査系列の生成が
容易になり、故障検出効率が向上する。

【００７０】なお、評価指標のための重みの計算式とし
て、段数と多重度の積（ｊ×ｋ）を用いたが、重みの計
算式はこれに限られるものではない。式（ｊ×ｋ）は、
段数ｊ、多重度ｋが大きい平衡再収斂構造ほど検査系列
生成を困難にするという想定のもとに設定したものであ
り、（ｊ×ｋ）の代わりに、ｊ，ｋを変数とする他の計
算式、例えば（ａｋ＋ｂｊ）（ただし、ａ，ｂは実数）
のような線形式や他の多項式を用いてもかまわない。ま
た、段数ｊや多重度ｋとともに、またはこれらに代え
て、再収斂経路の本数などを重みの計算式に用いてもよ
い。

【００７１】なお、本実施形態では、ｎ重整列構造はグ
ローバルループ構造やセルフループ構造を有さない無閉
路構造である、という性質を利用して、セルフループ構
造を持つものとして認識したＦＦについてはスキャン化
するものとして、スキャン化するか否かの判定処理を省
いている。同様に、グローバルループ構造を含む再収斂
経路を認識し、認識したグローバルループ構造に属する
ＦＦはスキャン化するものとして、スキャン化するか否
かの判定処理を省くことも可能である。

【００７２】また、ｎ重整列構造では、時間軸展開の際
に一のノードはｎ回以下しか現れないという性質を利用
し、ステップＳＡ２０における出力先の探索の際に、同
一ノードが現れる回数に制限を与えて、探索回数を減ら
すことも可能である。

【００７３】（第２の実施形態）図２２は本発明の第２
の実施形態に係る検査容易化設計方法を示すフローチャ
ートである。図２２に示すフローは、ステップＳＢ４以
外は図４に示す第１の実施形態に係るフローと同様であ
る。ステップＳＢ４では、設計対象となる集積回路を表
すＦＦ関係グラフにおける入出力数を、検査系列生成の
困難度との関連度合を表す評価指標として用いて、ＦＦ
のソートを行う。

【００７４】ここでは、ステップＳＢ１において、図２
３（ａ）に示すようなＦＦ関係グラフが、検査容易化設
計の対象となる集積回路から得られたものとする。ま
た、ステップＳＡ７において、ｎ＝１とする。すなわ
ち、集積回路が「１重整列構造」になるか否かによっ
て、ＦＦをスキャン化するか否かを決定する。なお、ｎ
の値を「１」としたのは説明の便宜上であり、他の値に
設定してもかまわない。

【００７５】図２３（ｂ）は図２３（ａ）のＦＦ関係グ
ラフにおける各ＦＦの入出力数を示す図である。この入
出力数を評価指標として、小さい方から順に並べると、
図２３（ｂ）に示すように、ステップＳＢ４におけるソ
ート順は｛Ｃ，Ｄ，Ｅ，Ｇ，Ｈ，Ｉ，Ｊ，Ｂ，Ｆ，Ａ，
Ｋ｝となる。これは、評価指標が表す平衡再収斂構造と
の関連度合が、低い方から高い方への順に相当する。こ
のソート順に従ってステップＳＢ６〜ＳＢ８を実行する
と、図２４に示すように、Ｆ，Ａの２個のＦＦがスキャ
ン化するものとして決定される。

【００７６】一方、本実施形態の比較例として、スキャ
ン化判定するＦＦの選択順をランダムにした場合、例え
ば、ＦＦの判定順を前述したソート順の逆の順序すなわ
ち｛Ｋ，Ａ，Ｆ，Ｂ，Ｊ，Ｉ，Ｈ，Ｇ，Ｅ，Ｄ，Ｃ｝と
した場合を考える。この場合、図２５に示すように、
Ｇ，Ｄ，Ｃの３個のＦＦがスキャン化するものとして決
定される。

【００７７】以上のように本実施形態によると、従来よ
りも、スキャン化するＦＦの数を減らすことができ、テ
スト回路の増大を防ぐことができる。

【００７８】（第３の実施形態）図２６は本発明の第３
の実施形態に係る検査容易化設計方法を示すフローチャ
ートである。図２６に示すフローは、ステップＳＣ４以
外は図４に示す第１の実施形態に係るフローと同様であ
る。ステップＳＣ４では、最大順序入力距離および最大
順序出力距離を用いた所定の演算の演算結果を、検査系
列生成の困難度との関連度合を表す評価指標として用い
て、ＦＦのソートを行う。

【００７９】ここで、「最大順序入力距離」とは、各外
部入力から当該ＦＦまでの全ての経路の順序深度の中で
最大のものをいい、「最大順序出力距離」とは、当該Ｆ
Ｆから各外部出力までの全ての経路の順序深度の中で最
大のものをいう。ただし、ＦＦから外部入力または外部
出力までの経路中にループがある場合は、そのループを
無視して計算する。

【００８０】そして本実施形態では、最大順序入力距離
をＸ、最大順序出力距離をＹとするとき、（Ｘ＋Ｙ）/｜Ｘ−Ｙ｜ …（１）の計算式による演算結果を評価指標として用いる。この
式による演算結果は、外部入力からの順序深度と外部出
力からの順序深度とが近似しているほど（すなわち、Ｆ
Ｆの位置が経路の中央に近いほど）大きな値になり、ま
た、ＦＦが属する経路が長いほど大きな値になる。

【００８１】またステップＳＣ７において、ｎ＝１とす
る。すなわち、集積回路が「１重整列構造」になるか否
かによって、ＦＦをスキャン化するか否かを決定する。
なお、ｎの値を「１」としたのは説明の便宜上であり、
他の値に設定してもかまわない。

【００８２】まず、ステップＳＣ１において、図２７
（ａ）に示すようなＦＦ関係グラフが、検査容易化設計
の対象となる集積回路から得られたものとする。図２７
（ｂ）は図２７（ａ）のＦＦ関係グラフにおける各ＦＦ
の、式（１）から求めた評価指標の値を示す図である。
図２７（ｂ）に示すように、評価指標の値の小さい方か
ら順に並べると、ステップＳＣ４におけるソート順は
｛Ａ，Ｈ，Ｉ，Ｊ，Ｂ，Ｇ，Ｃ，Ｆ，Ｄ，Ｅ｝となる。
これは、評価指標が表す平衡再収斂構造との関連度合
が、低い方から高い方への順に相当する。このソート順
に従ってステップＳＣ６〜ＳＣ８を実行すると、図２８
に示すように、ＥのＦＦがスキャン化するものとして決
定される。図２８に示す回路の最大順序深度は４であ
る。

【００８３】一方、本実施形態の比較例として、スキャ
ン化判定するＦＦの選択順をランダムにした場合、例え
ばＦＦの判定順を｛Ａ，Ｈ，Ｉ，Ｅ，Ｂ，Ｇ，Ｃ，Ｆ，
Ｄ，Ｊ｝とした場合を考える。この場合、図２９に示す
ように、ＪのＦＦがスキャン化するものとして決定され
る。図２９に示す回路の最大順序深度は８である。

【００８４】以上にように本実施形態によると、従来よ
りも、順序深度が小さくなり、故障検査系列生成を容易
にすることができ、さらには生成する故障検査系列長を
短くすることができる。

【００８５】なお、評価指標のための計算式は、本実施
形態で示したものに限られるものではなく、最大入力順
序距離および最大出力順序距離を用いた他の計算式を用
いてもかまわない。

【００８６】（第４の実施形態）図３０は本発明の第４
の実施形態に係る検査容易化設計方法を示すフローチャ
ートである。図３０のフローは、ステップＳＤ３で単一
出力ＦＦを探索・認識し、ステップＳＤ６で単一出力Ｆ
Ｆは全て非スキャン化するものと決定する点を特徴とす
る。これ以外は、図４、図２２および図２６のフローと
同様である。ステップＳＤ５は、図４のステップＳＡ
４、図２２のステップＳＢ４または図２６のステップＳ
Ｃ４のいずれかに相当するソート処理である。

【００８７】「単一出力ＦＦ」とは、ＦＦ関係グラフに
おいて、出力先が１つであり、かつ、その出力先が自己
以外のＦＦまたは外部出力であるＦＦ、と定義する。本
実施形態では、単一出力ＦＦについては、スキャン化す
るか否かの判断を省き、無条件に非スキャン化するもの
と決定する。ステップＳＤ５のソート処理では、セルフ
ループ構造を持つＦＦと単一出力ＦＦとを除き、第１〜
第３の実施形態と同様に各ＦＦをソートする。

【００８８】第１〜第３の実施形態に示したようなスキ
ャン化ＦＦを決定するアルゴリズムでは、回路中の各Ｆ
Ｆについて、スキャン化するか否かを個別に判定してい
た。このため、ＦＦの個数が多いと場合には膨大な計算
時間が必要であった。一方、本願発明者の検討により、
フルスキャン回路から全ての単一出力ＦＦを非スキャン
化した場合でも、回路はｎ重整列構造になる可能性が高
いことが分かった。したがって、単一出力ＦＦについて
スキャン化するか否かの判断を省くことによって、スキ
ャン化ＦＦ決定のための計算時間を大幅に短縮すること
ができ、特に、回路中に多くの単一出力ＦＦが存在する
場合に、その効果は顕著になる。

【００８９】図７に示すＦＦ関係グラフがステップＳＤ
１によって得られたとする。ステップＳＤ３において、
単一出力ＦＦとして、Ｂ，Ｄ，Ｇ，Ｈ，Ｉ，Ｊ，Ｌが認
識される。したがって、スキャン化するか否かの判定
は、Ａ，Ｃ，Ｅ，Ｆ，ＫのＦＦについてのみ行う。

【００９０】なお、ここでは、出力先が１つである単一
出力ＦＦを認識するものとしたが、一般にｍ（ｍは自然
数）個の出力を持つＦＦに拡張することもできる。

【００９１】また、「単一出力ＦＦ」の代わりに「単一
入出力ＦＦ」について、スキャン化するか否かの判断を
省いてもよい。「単一入出力ＦＦ」とは、単一出力ＦＦ
であり、かつ、ＦＦ関係グラフにおいて入力の数が１で
あるＦＦ、と定義する。図７のＦＦ関係グラフでは、
Ｄ，Ｌが単一入出力ＦＦである。

【００９２】第２の実施形態のように、入出力数によっ
てＦＦをソートした場合には、単一出力ＦＦであっても
入力数の多いものはソート順の後の方に位置する。この
場合に、単一出力ＦＦを全て無条件に非スキャン化する
ものと決定すると、ソート順の後の方に位置する単一出
力ＦＦも非スキャンＦＦになるので、結果としてソート
の効果を損なう可能性が生じる。言い換えると、入出力
数によるソートによってスキャン化率を下げるという効
果が得られたが、単一出力ＦＦを全て非スキャンＦＦに
することによって、スキャン化率が増加する可能性があ
る。

【００９３】しかしながら、スキャン化するか否かの判
定を省く対象を「単一入出力ＦＦ」に限定することによ
って、ソート順の後の方に位置する単一出力ＦＦについ
てはスキャン化するか否かの判定が行われることにな
る。したがって、スキャン化ＦＦ決定のための計算時間
を短縮することができ、かつ、入出力数によるソートに
よってスキャン化率を下げるという効果が損なわれるこ
とはない。

【００９４】（第５の実施形態）図３１は本発明の第５
の実施形態に係る検査容易化設計方法を示すフローチャ
ートである。本実施形態では、集積回路から、段数が所
定値以上の平衡再収斂構造が削除されるように、スキャ
ン化するＦＦを決定する。

【００９５】第１〜第３の実施形態では、集積回路がｎ
重整列構造になり、かつ、平衡再収斂構造ができるだけ
残らないように、スキャン化するアルゴリズムを示し
た。ところがこのような方法では、平衡再収斂構造を積
極的に削除するわけではないので、回路に検査系列生成
を困難にするような平衡再収斂構造が残る場合があり、
必ずしも高い故障検出率を達成できない。

【００９６】一方、段数が深い平衡再収斂構造では、分
岐点で値の割当の矛盾を起こしたときに、矛盾の原因と
なった値割当のバックトラック処理を行う以前に、検査
系列生成処理自体が打ち切られる可能性がある。したが
って、段数が深い平衡再収斂構造を削除することによっ
て、回路の検査容易性を高めることができ、結果として
高い故障検出率を得ることができる。

【００９７】まずステップＳＥ１において、図３２に示
すようなＦＦ関係グラフが得られたとする。図３２にお
いて、ＰＩ１〜ＰＩ５は外部入力、Ａ〜ＫはＦＦ、ＰＯ
１、ＰＯ２は外部出力を表す。

【００９８】次にステップＳＥ２において、平衡再収斂
構造の探索を行う。図３２において、平衡再収斂構造の
分岐点となり得るＦＦはＡ、Ｃ、Ｅ、Ｆ、Ｋである。

【００９９】図３３はステップＳＥ２の実行結果すなわ
ち図３２の回路に存在する平衡再収斂構造を示す図であ
る。図３３に示すように、図３２の回路には６個の平衡
再収斂構造が存在する。なお例えば、（Ａ，Ｉ）（１，
２）は、分岐点Ａから再収斂点Ｉまでの１段２重平衡再
収斂構造を表している。また図３３では、各平衡再収斂
構造について、その経路に属するＦＦを列記している。

【０１００】次にステップＳＥ３において、図３２の回
路に段数が所定数以上の平衡再収斂構造があるか否かを
判断する。ここでは、所定数を「２」とする。図３３か
ら分かるように、図３２の回路には２段以上の平衡再収
斂構造として、（Ａ，Ｇ）（２，２），（Ａ，Ｈ）
（２，２），（Ａ，ＰＯ１）（３，４），（Ａ，ＰＯ
１）（４，３）および（Ｆ，ＰＯ１）（２，２）の５つ
が存在する。

【０１０１】次にステップＳＥ４において、スキャン化
するＦＦを選択する。ここでの選択では、２段以上の平
衡再収斂構造について、各ＦＦが属する経路の数を求
め、この経路数を重みとして用いる。図３４は各ＦＦの
重みを示す図である。ここでは、重みが最も大きいＦＦ
であるＦをスキャン化するＦＦとして選択する。

【０１０２】図３５はＦをスキャン化すると選択した後
のＦＦ関係グラフを示す図である。図３５において、ス
キャン化するものとして選択したＦはＦＦ関係グラフか
ら削除されており、Ｆの入力が擬似外部出力ＰＰＯＦ
に、Ｆの出力が擬似外部入力ＰＰＩＦに置き換わってい
る。

【０１０３】ステップＳＥ２に戻り、図３５の回路にお
いて平衡再収斂構造を探索する。図３５において、平衡
再収斂構造の分岐点となり得るのは、Ａ，Ｃ，Ｅ，Ｋお
よびＰＰＩＦである。探索の結果、図３６に示すよう
に、Ａ，Ｃ，Ｅ，Ｋを分岐点とする平衡再収斂構造は存
在せず、平衡再収斂構造（ＰＰＩＦ，ＰＯ１）（２，
２）のみが認識される。次にステップＳＥ３において、
２段以上の平衡再収斂構造が図３５の回路中に存在する
か否かを判断するが、平衡再収斂構造（ＰＰＩＦ，ＰＯ
１）（２，２）が存在するのでステップＳＥ４に進む。

【０１０４】ステップＳＥ４において、スキャン化する
ＦＦを選択するが、図３７に示すように、平衡再収斂構
造（ＰＰＩＦ，ＰＯ１）（２，２）に含まれる各ＦＦの
重みは全て１であるので、ここでは、ランダムにスキャ
ン化するＦＦとしてＨを選択する。

【０１０５】図３８はＨをスキャン化すると選択した後
のＦＦ関係グラフを示す図である。図３８において、ス
キャン化すると選択したＨはＦＦ関係グラフから削除さ
れており、Ｈの入力が擬似外部出力ＰＰＯＨに、Ｈの入
力が擬似外部入力ＰＰＩＨに、それぞれ置き換えられて
いる。再びステップＳＥ２において、図３８の回路にお
いて平衡再収斂構造を探索する。図３８において、平衡
再収斂構造の分岐点となり得るのは、Ａ，Ｃ，Ｅ，Ｋお
よびＰＰＩＦである。Ａ，Ｃ，Ｅ，Ｋを分岐点とする平
衡再収斂構造は存在しないことはすでに分かっているの
で、ここでは探索を省略する。ＰＰＩＦを分岐点とする
探索を行うが、平衡再収斂構造は存在しないことが分か
るので、ステップＳＥ３を経て処理を終了する。

【０１０６】なお、ステップＳＥ４でのスキャン化ＦＦ
の選択方法は、本実施形態で示したものに限られるもの
ではない。例えば、スキャン化するＦＦとして、段数が
所定値以上の平衡再収斂構造に含まれ、かつ、回路中の
全平衡再収斂構造に最も数多く含まれるＦＦを選んでも
よい。また、平衡再収斂構造の段数、経路数またはＦＦ
数などの要素を、選択指標に重みとして加えてもよい。
また、スキャン化するＦＦを複数選択してもかまわな
い。

【０１０７】（第６の実施形態）図３９は本発明の第６
の実施形態に係る検査容易化設計方法を示すフローチャ
ートである。図３９のフローは、基本的には図３１のフ
ローと同様であるが、ステップＳＦ３において、「経路
数」が所定値以上の平衡再収斂構造が存在するか否かを
判断する。すなわち、本実施形態では、集積回路から、
経路数が所定値以上の平衡再収斂構造を削除するよう
に、スキャン化ＦＦを決定する。

【０１０８】経路数が多い平衡再収斂構造では、分岐点
で異なる値の割り当て要求がある可能性が高くなり、結
果として分岐点で矛盾を起こす可能性が高くなる。した
がって、平衡再収斂構造の経路数を削減することによっ
て、回路の検査容易性を高めることができ、結果として
高い故障検出率を得ることができる。

【０１０９】ステップＳＦ１では、図３２に示すＦＦ関
係グラフが作成されたとする。

【０１１０】次にステップＳＦ２において、平衡再収斂
構造の探索を行う。この結果、図３３に示したように、
図３２の回路には６個の平衡再収斂構造が存在すること
が分かる。

【０１１１】次にステップＳＦ３において、図３２の回
路に経路数が所定数以上の平衡再収斂構造があるか否か
を判断する。ここでは、所定数を「３」とする。すなわ
ち、経路数が３以上の平衡再収斂構造が図３２の回路に
存在するか否かを判断する。図３３から分かるように、
図３２の回路には経路数３以上の平衡再収斂構造とし
て、（Ａ，ＰＯ１）（３，４）および（Ａ，ＰＯ１）
（４，３）の２つが存在する。

【０１１２】次にステップＳＦ４において、スキャン化
するＦＦを選択する。ここでの選択では、２個の経路数
３以上の平衡再収斂構造において、各ＦＦが属する経路
の数を求め、この経路数を重みとして用いる。図４０は
各ＦＦの重みを示す図である。ここでは、重みが最も大
きいＦＦであるＦをスキャン化するＦＦとして選択す
る。

【０１１３】Ｆをスキャン化すると選択した後のＦＦ関
係グラフは図３５のようになる。再びステップＳＦ２に
戻り、図３５の回路において平衡再収斂構造を探索す
る。探索の結果、平衡再収斂構造（ＰＰＩＦ，ＰＯ１）
（２，２）のみが認識される。ところがこの平衡再収斂
構造は、経路数が３以下である。したがって、図３５の
回路には経路数が３以上の平衡再収斂構造が存在しない
ことが分かるので、ステップＳＦ３を経て処理を終了す
る。

【０１１４】なお、ステップＳＦ４でのスキャン化ＦＦ
の選択方法は、本実施形態で示したものに限られるもの
ではない。例えば、スキャン化するＦＦとして、経路数
が所定値以上の平衡再収斂構造に含まれ、かつ、回路中
の全平衡再収斂構造中に最も数多く含まれるＦＦを選ん
でもよい。また、平衡再収斂構造の段数、経路数または
ＦＦ数などの要素を、選択指標に重みとして加えてもよ
い。また、スキャン化するＦＦを複数選択してもかまわ
ない。

【０１１５】（第７の実施形態）図４１は本発明の第７
の実施形態に係る検査容易化設計方法を示すフローチャ
ートである。図４１のフローは、基本的には図３１のフ
ロートと同様であるが、ステップＳＧ３において、「Ｆ
Ｆ数」が所定値以上の平衡再収斂構造が存在するか否か
を判断する。すなわち、本実施形態では、集積回路か
ら、ＦＦ数が所定値以上の平衡再収斂構造を削除するよ
うに、スキャン化ＦＦを決定する。

【０１１６】ＦＦ数が多い平衡再収斂構造では、経路数
が多く、かつ、段数が多くなる可能性があり、結果とし
て分岐点で矛盾を起こし、バックトラック処理が打ち切
られる可能性が高くなる。したがって、平衡再収斂構造
中に含まれるＦＦ数を削減することによって、回路の検
査容易性を高めることができ、結果として高い故障検出
率を得ることができる。

【０１１７】ステップＳＧ１において、図４２に示すＦ
Ｆ関係グラフが作成されたとする。図４２において、Ｐ
Ｉ１〜ＰＩ４は外部入力、Ａ〜ＳはＦＦ、ＰＯは外部出
力を表す。次にステップＳＧ２において、平衡再収斂構
造の探索を行う。図４２において、平衡再収斂構造の分
岐点となり得るのは、ＰＩ２，Ｂ，Ｃ，Ｄ，Ｇ，Ｋであ
る。図４３はステップＳＧ２の実行結果すなわち図４２
の回路に存在する平衡再収斂構造を示す図である。図４
３に示すように、図４２の回路には６個の平衡再収斂構
造が存在する。また図４３では、各平衡再収斂構造につ
いて、その経路に属するＦＦを列記するとともに、ＦＦ
の個数も示している。

【０１１８】次にステップＳＧ３において、図４２の回
路にＦＦ数が所定数以上の平衡再収斂構造があるか否か
を判断する。ここでは、所定数を「８」とする。図４３
から分かるように、図４２の回路には、ＦＦ数が８以上
の平衡再収斂構造として、（ＰＩ２，ＰＯ）（５，９）
および（Ｄ，ＰＯ）（３，３）の２つが存在する。

【０１１９】次にステップＳＧ４において、スキャン化
するＦＦを選択する。ここでの選択では、ＦＦ数が８以
上の平衡再収斂構造について、各ＦＦが属する経路の数
を求め、この経路数を重みとして用いる。図４４は各Ｆ
Ｆの重みを示す図である。ここでは、重みが最も大きい
ＦＦであるＢをスキャン化するＦＦとして選択する。

【０１２０】図４５はＢをスキャン化すると選択した後
のＦＦ関係グラフを示す図である。図４５において、ス
キャン化するものとして選択したＢはＦＦ関係グラフか
ら削除され、Ｂの入力が擬似外部出力ＰＰＯＢに、Ｂの
出力が擬似外部入力ＰＰＩＢに置き換わっている。

【０１２１】ステップＳＧ２に戻り、図４５の回路にお
いて平衡再収斂構造を探索する。探索の結果、図４６に
示すように、４個の平衡再収斂構造が認識される。ステ
ップＳＧ３において、ＦＦ数が９である平衡再収斂構造
（Ｄ，ＰＯ）（３，３）が存在するので、ＦＦ数が８以
上の平衡再収斂構造が存在すると判断してステップＳＧ
４にすすむ。

【０１２２】ステップＳＧ４において、スキャン化する
ＦＦを選択するが、図４７に示すように、平衡再収斂構
造（Ｄ，ＰＯ）（３，３）に含まれる各ＦＦの重みは全
て１である。そこで、他の平衡再収斂構造にも含まれる
ＦＦを抽出し、その中からランダムにスキャン化するＦ
Ｆを選択する。ＫおよびＥが他の平衡再収斂構造（Ｃ，
Ｉ）（２，３）にも含まれるので、この中から、Ｋをス
キャン化するＦＦとして選択する。

【０１２３】図４８はＫをスキャン化すると選択した後
のＦＦ関係グラフを示す図である。図４８において、ス
キャン化すると選択したＫはＦＦ関係グラフから削除さ
れており、Ｋの入力が擬似外部出力ＰＰＯＫに、Ｋの出
力が擬似外部入力ＰＰＩＫに、それぞれ置き換えられて
いる。再びステップＳＧ２において、図４８の回路にお
いて平衡再収斂構造を探索する。探索の結果、図４９に
示すように３個の平衡再収斂構造が認識されるが、ＦＦ
数が８以上の平衡再収斂構造は存在しないので、ステッ
プＳＧ３を経て、処理を終了する。

【０１２４】なお、ステップＳＧ４でのスキャン化ＦＦ
の選択方法は、本実施形態で示したものに限られるもの
ではない。例えば、スキャン化するＦＦとして、ＦＦ数
が所定値以上の平衡再収斂構造に含まれ、かつ、回路中
の全平衡再収斂構造に最も数多く含まれるＦＦを選んで
もよい。また、平衡再収斂構造の段数、経路数またはＦ
Ｆ数などの要素を、選択指標に重みとして加えてもよ
い。また、スキャン化するＦＦを複数選択してもかまわ
ない。

【０１２５】なお、本発明の各実施形態は、レジスタ・
トランスファ・レベルで設計された集積回路にも同様に
適用することができる。この場合、レジスタ・トランス
ファ・レベルで設計された集積回路を構成するレジスタ
を、本実施形態におけるＦＦと同様に取り扱えばよい。

【０１２６】また、第１〜第３の各実施形態に係るソー
ト処理は、ノンスキャン回路から、回路構造がｎ重整列
構造になるようにスキャンＦＦを決定する方法にも適用
できる。図５０はこの場合の検査容易化設計方法のフロ
ーである。図５０において、ステップＳＨ３では第１〜
第３の各実施形態におけるソート処理と同様の処理を行
うが、ただしそのソート順は、第１〜第３の実施形態と
は逆にする。そして、回路構造がｎ重整列構造になるま
で（ＳＨ４）、ステップＳＨ３で得たソート順に、ＦＦ
をスキャン化していく（ＳＨ５）。

【０１２７】また、第５〜第７の各実施形態は、単独で
実施しても良いし、それぞれ組み合わせてもかまわな
い。さらに、第５〜第７の各実施形態は、ｎ重整列構造
になるようにスキャン化ＦＦを決定する方法と組み合わ
せてもよい。例えば、ｎ重整列構造になるようにスキャ
ン化ＦＦを決定した集積回路について、検査系列生成を
実行し、その結果が満足できるものでないときに、第５
〜第７の各実施形態と同様の検査容易化設計を実行して
もよい。

【０１２８】

【発明の効果】以上のように本発明によると、各ＦＦま
たはレジスタについて、検査系列生成困難度との関連度
合を表す所定の評価指標に従ったソート順にスキャン化
するか否かの判定が行われるので、検査系列の生成がよ
り容易な回路を得ることができ、従来よりも故障検出効
率を向上させることができる。

【図面の簡単な説明】

【図１】平衡再収斂構造を示す概念図である。

【図２】平衡再収斂構造を含む回路の検査系列生成が困
難になることを説明するための図であり、２段３重平衡
再収斂構造を含む回路を示す図である。

【図３】図２の回路において、ＦＦ１，ＦＦ６をスキャ
ン化した結果を示す図である。

【図４】本発明の第１の実施形態に係る検査容易化設計
方法を示すフローチャートである。

【図５】図４におけるソート処理ＳＡ４の詳細を示すフ
ローチャートである。

【図６】図５におけるステップＳＡ２０の詳細を示すフ
ローチャートである。

【図７】本発明の第１の実施形態において、検査容易化
設計の対象とする集積回路を表すＦＦ関係グラフであ
る。

【図８】（ａ）は図７の回路における分岐点Ａから２つ
先の出力までの探索結果を示す図であり、（ｂ）は
（ａ）で認識した平衡再収斂構造から求めた重みを示す
図である。

【図９】（ａ）は図７の回路における分岐点Ａから３つ
先の出力までの探索結果を示す図であり、（ｂ）は
（ａ）で認識した平衡再収斂構造から求めた重みを示す
図である。

【図１０】（ａ）は図７の回路における分岐点Ａから３
つ先の出力までの探索結果を示す図であり、（ｂ）は
（ａ）で認識した平衡再収斂構造から求めた重みを示す
図である。

【図１１】（ａ）は図７の回路における分岐点Ａから４
つ先の出力までの探索結果を示す図であり、（ｂ）は
（ａ）で認識した平衡再収斂構造から求めた重みを示す
図である。

【図１２】（ａ）は図７の回路における分岐点Ａから５
つ先の出力までの探索結果を示す図であり、（ｂ）は
（ａ）で認識した平衡再収斂構造から求めた重みを示す
図である。

【図１３】（ａ）は図７の回路における分岐点Ａから５
つ先の出力までの探索結果を示す図であり、（ｂ）は
（ａ）で認識した平衡再収斂構造から求めた重みを示す
図である。

【図１４】図７の回路における分岐点Ｃからの探索結果
を示す図である。

【図１５】図７の回路における分岐点Ｅからの探索結果
を示す図である。

【図１６】（ａ）は図７の回路における分岐点Ｆからの
探索結果を示す図であり、（ｂ）は（ａ）で認識した平
衡再収斂構造から求めた重みを示す図である。

【図１７】図７の回路における分岐点Ｋからの探索結果
を示す図である。

【図１８】図７の回路に対する平衡再収斂構造の探索か
ら得た各ＦＦの評価指標の値と、ソート順とを示す図で
ある。

【図１９】図１８に示すソート順に従ってＦＦのスキャ
ン化判定を行った結果を示す図である。

【図２０】本発明の第１の実施形態の比較例として、図
１８に示すソート順と逆の順序に従ってＦＦのスキャン
化判定を行った結果を示す図である。

【図２１】図２０の回路に対する時間軸展開の結果を示
す図である。

【図２２】本発明の第２の実施形態に係る検査容易化設
計方法を示すフローチャートである。

【図２３】（ａ）は本発明の第２の実施形態において、
検査容易化設計の対象とする集積回路を表すＦＦ関係グ
ラフ、（ｂ）は（ａ）のＦＦ関係グラフにおける各ＦＦ
の入出力数と、この入出力数から得たソート順を示す図
である。

【図２４】図２３（ｂ）に示すソート順に従ってＦＦの
スキャン化判定を行った結果を示す図である。

【図２５】本発明の第２の実施形態の比較例として、図
２３（ｂ）に示すソート順と逆の順序に従ってＦＦのス
キャン化判定を行った結果を示す図である。

【図２６】本発明の第３の実施形態に係る検査容易化設
計方法を示すフローチャートである。

【図２７】（ａ）は本発明の第３の実施形態において、
検査容易化設計の対象とする集積回路を表すＦＦ関係グ
ラフ、（ｂ）は（ａ）のＦＦ関係グラフにおける各ＦＦ
の順序距離に基づく評価関数と、この評価関数から得た
ソート順を示す図である。

【図２８】図２７（ｂ）に示すソート順に従ってＦＦの
スキャン化判定を行った結果を示す図である。

【図２９】本発明の第３の実施形態の比較例として、図
２７（ｂ）に示すソート順と異なる順序に従ってＦＦの
スキャン化判定を行った結果を示す図である。

【図３０】本発明の第４の実施形態に係る検査容易化設
計方法を示すフローチャートである。

【図３１】本発明の第５の実施形態に係る検査容易化設
計方法を示すフローチャートである。

【図３２】本発明の第５の実施形態において、検査容易
化設計の対象とする集積回路を表すＦＦ関係グラフであ
る。

【図３３】図３２から認識された平衡再収斂構造を示す
図である。

【図３４】本発明の第５の実施形態において、図３３に
示す平衡再収斂構造から定めた各ＦＦに加える重みを示
す図である。

【図３５】図３２の回路においてＦをスキャン化した後
のＦＦ関係グラフである。

【図３６】図３５から認識された平衡再収斂構造を示す
図である。

【図３７】本発明の第５の実施形態において、図３６に
示す平衡再収斂構造から定めた各ＦＦに加える重みを示
す図である。

【図３８】図３５の回路においてＨをスキャン化した後
のＦＦ関係グラフである。

【図３９】本発明の第６の実施形態に係る検査容易化設
計方法を示すフローチャートである。

【図４０】本発明の第６の実施形態において、図３３に
示す平衡再収斂構造から定めた各ＦＦに加える重みを示
す図である。

【図４１】本発明の第７の実施形態に係る検査容易化設
計方法を示すフローチャートである。

【図４２】本発明の第７の実施形態において、検査容易
化設計の対象とする集積回路を表すＦＦ関係グラフであ
る。

【図４３】図４２から認識された平衡再収斂構造を示す
図である。

【図４４】本発明の第７の実施形態において、図４３に
示す平衡再収斂構造から定めた各ＦＦに加える重みを示
す図である。

【図４５】図４２の回路においてＢをスキャン化した後
のＦＦ関係グラフである。

【図４６】図４５から認識された平衡再収斂構造を示す
図である。

【図４７】本発明の第７の実施形態において、図４６に
示す平衡再収斂構造から定めた各ＦＦに加える重みを示
す図である。

【図４８】図４５の回路においてＫをスキャン化した後
のＦＦ関係グラフである。

【図４９】図４８から認識された平衡再収斂構造を示す
図である。

【図５０】第１〜第３の実施形態に係るソート処理を用
いた検査容易化設計の他の例を示すフローチャートであ
る。

【図５１】従来の検査容易化設計方法を示すフローチャ
ートである。

Claims

【特許請求の範囲】

【請求項１】ゲートレベルまたはレジスタ・トランス
ファ・レベルで設計された集積回路に対し、製造後の検
査が容易になるよう、設計変更を行う検査容易化設計方
法であって、前記集積回路の全てのフリップフロップ（ＦＦ）または
レジスタを、スキャン化するものとして仮決定するフル
スキャン処理と、ＦＦまたはレジスタのソートを、検査系列生成の困難度
との関連度合を表す所定の評価指標に従って行うソート
処理と、前記フルスキャン処理においてスキャン化するものとし
て仮決定された各ＦＦまたはレジスタについて、前記ソ
ート処理によって得たソート順に従って、当該ＦＦまた
はレジスタをスキャン化しないものと仮定したときに前
記集積回路がｎ重整列構造になるか否かを判定し、ｎ重
整列構造になるときは、スキャン化しないものとして仮
決定する一方、ｎ重整列構造にならないときは、スキャ
ン化するものとする仮決定を維持する非スキャン化選択
処理とを備え、非スキャン化選択処理を実行した結果、スキャン化する
ものとして仮決定されているＦＦまたはレジスタを、ス
キャン化するＦＦまたはレジスタとして確定することを
特徴とする検査容易化設計方法。
【請求項２】請求項１において、前記ソート順は、前記所定の評価指標が表す関連度合が
低い方から高い方への順であることを特徴とする検査容
易化設計方法。
【請求項３】請求項１において、前記ソート処理は、前記集積回路が有する平衡再収斂構造を認識し、認識した平衡再収斂構造との関連度合を表す指標を、前
記所定の評価指標として、ＦＦまたはレジスタのソート
を行うものであることを特徴とする検査容易化設計方
法。
【請求項４】請求項１において、前記ソート処理は、前記集積回路を表すＦＦ関係グラフまたはレジスタ関係
グラフにおける入出力数を、前記所定の評価指標とし
て、ＦＦまたはレジスタのソートを行うものであること
を特徴とする検査容易化設計方法。
【請求項５】請求項１において、前記ソート処理は、最大順序入力距離および最大順序出力距離を用いた所定
の演算の演算結果を、前記所定の評価指標として、ＦＦ
またはレジスタのソートを行うものであることを特徴と
する検査容易化設計方法。
【請求項６】請求項１において、前記非スキャン化選択処理は、セルフループ構造を持つものとして認識したＦＦまたは
レジスタについては、前記判定処理を省き、スキャン化
するものとする仮決定を維持するものであることを特徴
とする検査容易化設計方法。
【請求項７】請求項１において、前記集積回路から、単一出力ＦＦまたは単一出力レジス
タを探索する処理を備え、前記非スキャン化選択処理は、探索された単一出力ＦＦまたは単一出力レジスタについ
ては、前記判定処理を省き、スキャン化するものとする
仮決定を維持するものであることを特徴とする検査容易
化設計方法。
【請求項８】請求項１において、前記集積回路から、単一入出力ＦＦまたは単一入出力レ
ジスタを探索する処理を備え、前記非スキャン化選択処理は、探索された単一出力ＦＦまたは単一出力レジスタについ
ては、前記判定処理を省き、スキャン化するものとする
仮決定を維持するものであることを特徴とする検査容易
化設計方法。
【請求項９】ゲートレベルまたはレジスタ・トランス
ファ・レベルで設計された集積回路に対し、製造後の検
査が容易になるよう、設計変更を行う検査容易化設計方
法であって、前記集積回路が、所定の条件を満たす平衡再収斂構造を
有さないように、スキャン化するＦＦまたはレジスタを
決定することを特徴とする検査容易化設計方法。
【請求項１０】請求項９において、前記所定の条件は、段数が所定値以上であることである
検査容易化設計方法。
【請求項１１】請求項９において、前記所定の条件は、経路数が所定値以上であることであ
る検査容易化設計方法。
【請求項１２】請求項９において、前記所定の条件は、ＦＦ数が所定値以上であることであ
る検査容易化設計方法。
【請求項１３】ゲートレベルまたはレジスタ・トラン
スファ・レベルで設計された集積回路に対し、製造後の
検査が容易になるよう、設計変更を行う検査容易化設計
方法であって、前記集積回路がｎ重整列構造になるように、スキャン化
すべきフリップフロップ（ＦＦ）またはレジスタを決定
するものであり、ＦＦまたはレジスタのソートを、検査系列生成の困難度
との関連度合を表す所定の評価指標に従って行うソート
処理を備え、このソート処理によって得たソート順に従
って、前記集積回路のＦＦまたはレジスタについて、ス
キャン化すべきか否かを決定することを特徴とする検査
容易化設計方法。
【請求項１４】請求項１３において、前記ソート処理は、前記集積回路が有する平衡再収斂構造を認識し、認識した平衡再収斂構造との関連度合を表す指標を、前
記所定の評価指標として、ＦＦまたはレジスタのソート
を行うものであることを特徴とする検査容易化設計方
法。
【請求項１５】請求項１３において、前記ソート処理は、前記集積回路のＦＦ関係グラフまたはレジスタ関係グラ
フにおける入出力数を、前記所定の評価指標として、Ｆ
Ｆまたはレジスタのソートを行うものであることを特徴
とする検査容易化設計方法。
【請求項１６】請求項１３において、前記ソート処理は、最大順序入力距離および最大順序出力距離を用いた所定
の演算の演算結果を、前記所定の評価指標として、ＦＦ
またはレジスタのソートを行うものであることを特徴と
する検査容易化設計方法。
【請求項１７】ゲートレベルまたはレジスタ・トラン
スファ・レベルで設計された集積回路に対し、製造後の
検査が容易になるよう、設計変更を行う検査容易化設計
方法であって、前記集積回路がｎ重整列構造になるように、スキャン化
すべきフリップフロップ（ＦＦ）またはレジスタを決定
するものであり、前記集積回路の中から、単一出力ＦＦまたは単一出力レ
ジスタを探索する処理を備え、探索された単一出力ＦＦまたは単一出力レジスタは、ス
キャン化しないものと決定することを特徴とする検査容
易化設計方法。
【請求項１８】ゲートレベルまたはレジスタ・トラン
スファ・レベルで設計された集積回路に対し、製造後の
検査が容易になるよう、設計変更を行う検査容易化設計
方法であって、前記集積回路がｎ重整列構造になるように、スキャン化
すべきフリップフロップ（ＦＦ）またはレジスタを決定
するものであり、前記集積回路の中から、単一入出力ＦＦまたは単一入出
力レジスタを探索する処理を備え、探索された単一出力ＦＦまたは単一出力レジスタは、ス
キャン化しないものと決定することを特徴とする検査容
易化設計方法。