Comments
Description
Transcript
L/H型レジスタを有する無閉路順序回路の テスト生成法に関する研究
NAIST−IS−MT9651105 修士論文 りH型レジスタを有する無閉路順序回路の テスト生成法に関する研究 三原隆宏 1998年2月13日 奈良先端科学技術大学院大学 情報科学研究科情報処理学専攻 本論文は奈良先端科学技術大学院大学情報科学研究科に 修士（工学）授与の要件として提出した修士論文である0 三原隆宏 指導教官：藤原秀雄教授 渡連勝正教授 増澤利光助教授 りH型レジスタを有する無閉路順序回路の テスト生成法に関する研究＊ 三原隆宏 内容梗概 本論文では，ホールド機能を持つレジスタ（リH型レジスタ）を有する無閉路 順序回路のテスト生成法を提案する∴りH型レジスタを考慮した時間展開モデル を撞案し，無閉路順序回路に対するテストが，提案する時間展開モデルを用いて， 組合せテスト回路用テスト生成アルゴリズムでテスト生成可能であることを示す・ 本手法により，一般の順序回路を部分スキャン設計によって組合せテスト生成ア ルゴリズムでテスト生成を行う際のスキャンオーバーヘッドは，既に提案されて いるりH型レジスタを含まない無閉路順序回路のテスト生成法に比べて小さく なる． キーワード L／H型レジスタ，無閉路順序回路，時間展開モデル，組合せテスト生成 ・奈良先端科学技術大学院大学情報科学研究科情報処理学専攻修士論文，NAIST−IS− MT9651105，1998年2月13日． 1 StudiesonaTest GenerationMethodfbr AcyclicsequentialCircuitswithIJ／H−Type Registers＊ Ta址iroMihara Abstract hthispaper，WePreSentateStgenerationmethodforacyclicsequentialcircuits includingloadnlOld−tyPe（L／H−tyPe）registers・Weproposeatimeexpansion modelofacyclicsequentialcircuitswithL／H−typeregisters，aJldshowthattest vectorsfortheacyclicsequentialcircuitcanbegeneratedusingthetimeexpansion models．Thescanoverheadrequiredtoapplytheproposedtestgenerationmethod togeneralsequentialcircuitsgeneral1ybecomessmal1erthanthatrequiredto applythetestgenerationmethodforacyclicsequentialcircuitswithoutL／H− typeregisters・ Ⅸeywords： L／Htyperegisters，aCyClicsequentialcircuits，time，eXpanSionmodel，COmbina− tionaltestgeneration ＊Master，sThesis，DepartmentofInformationProcessing，GraduateSchoolofInformation Science，NaraInstituteofScienceandTechnology，NAIST−IS−MT9651105，February13，1998・ 2 目次 1序論 1 2 論理回路のテストとスキャン設計 4 2．1．故障モデルとテスト 4 2．2．順序回路のテスト生成 6 2．3．スキャン設計 ‥ 7 2．4．組合せ回路用のテスト生成アルゴリズムを指向したスキャン設計・ 8 2．5．無閉路部分スキャン設計‥‥ 9 ＄1イH型レジスタを有する無閉路順序回路のテスト生成法 3．1．りH型レジスタを考慮に入れた時間展開モデル・ 11 11 3．1．1トポロジーグラフ‥ 11 3．1．2 時間展開グラフと時間展開モデル． 13 3．2．りH型レジスタを有する無閉路順序回路のテスト生成‥ 3．2．1時間展開モデルを用いたテスト生成‥． 3．2．2 時間展開グラフの被覆関係‥ 3．3．最大展開モデルが存在する順序回路の構造． 3．3．1最大展開モデルが存在する回路構造．． 3．4．適用例 ‥ 16 16 22 27 27 30 4 結論 36 謝辞 37 3 38 参考文献 4 図目次 2．1順序回路の時間展開 6 2．2 スキャン設計の原理 7 2．3 通常レジスタとりH型レジスタ 10 3．1無閉路順序回路∫‥ 12 3．2 gのトポロジーグラフ：G‥． 12 3．3 時間展開グラフ且1 14 3．4 時間展開グラフ且2 14 3．5 月1に基づく時間展開モデルCβ1（5） 15 3．6 Cβ2（g）入出力パターン‥ 3．7 5一のGに基づく時間展開グラフ品 18 25 3．8 5のGに基づく時間展開グラフ月4 25 3．9 5のGに基づく時間展開グラフ且5 25 3．10月1，β2，β3，仇，且5の関係グラフ‥ 25 3．11ステップ2．で得られる部分グラフ．． 32 3．12ステップ4．で最大化した部分グラフ ‥ 32 3．13ステップ5．で得られる最大展開グラフ月m。∬． 32 3．14順序回路とL／H型レジスタを有する無閉路順序回路・ 33 3．1551に基づくトポロジーグラフGl． 33 3．16MAXTEGのステップ2．で得られた部分グラフ． 34 3．17MAXTEGのステップ4．で得られた最大部分グラフ． 34 3．18MAXTEGによって得られた最大展開グラフEmw． 35 3．19月m。才に基づく最大展開モデルCβ爪。∬（5）・ 35 5 表目次 3．1g入出力系列と各Lノ旧型レジスタの制御系列・ 18 6 第1章 序論 近年の半導体技術の急速な進歩に伴う超大規模集積回路（VLSI）の普及により， その信頼性は非常に重要な問題となっている．正しく動作しないVLSIの存在は， それを構成するシステムのサービスの停止，中断にとどまらず，社会的に大きな 影響を与えることにもなりかねない．信頼性の高い，故障のないVLSIを設計， 製造するためにはテストが必要不可欠であるが，VIJSIの急速な技術進歩により 回路規模が飛躍的に増大したため，そのテストに関する問題はますます困難で費 用のかかるものとなっている． 現在における論理回路のテスト生成問題を考えた場合，組合せ回路については， 完全な故障検出効率を得る自動テスト生成法が提案されているが，順序回路にお いては，回路規模が大きくなると解けなくなる場合があり，一般に困難な問題と されている．テスト生成を容易にするための手法の一つとしてテスト容易化設計 がある．主として用いられるテスト容易化設計法には，フリップフロップをスキャ ン可能なフリップフロップ（スキャンフリップフロップ）に置き換えるスキャン設 計【1，2げある．スキャン設計で■は，スキャンフリップフロップを外部入出力とみ なすことができるので，スキャンフリップフロップを取り除いた残りの回路（核 回路）に対してテスト生成を行えばよい．順序回路内のすべてのフリップフロッ プをスキャンフリップフロップに置き換える完全スキャン設計は，核回路が組合 せ回路と等価になるので，組合せテスト生成アルゴリズムでテスト生成可能（以 下，組合せテスト生成可能という）となり，ほぼ完全な故障検出効率が得られる が，大きなハードウエアオーバーヘッドを要する．また，一部のフリップフロツ 1 プをスキャンフリップフロップに置き換える部分スキャン設計は，小さいハード ウエアオーバーヘッド（スキャンフリップフロップ数）でテスト生成が容易な回路 を実現するための手法の1つである．文献【3，4］では，スキャンフリップフロッ プによって大域フィードバックループを切断することでテスト生成を容易にして いるが，スキャン設計を施して得られる核回路には自己ループを残しているので， 依然として順序回路テスト生成アルゴリズムが必要である・ これに対して，文献【5】では，無閉路順序回路（フィードバックや自己ル￣プを 含まない順序回路）を核回路とする部分スキャン設計法を提案し，文献［9］のテス ト生成モデルを拡張した時間展開モデルを用いることで組合せテスト生成可能と した．無閉路順序回路のクラスは，組合せテスト生成が可能な平衡構造【6〕，内部 平衡構造【7］や切替平衡構造【8】を核回路とするクラスを真に含むグラスであるた め，スキャン設計によって必要とされる追加のハードウェアオーバヘッドが少な くて実現可能な回路である．しかし，文献【5】の手法では，回路中にホールド機 能を有するレジスタ（以下，りH型レジスタと呼ぶ）が存在する場合・りH型レ ジスタは機能的に自己ループが存在するものとして考えられているため，回路を 無閉路化するために，全てのりH型レジスタをスキャンレジスタに置きかえる 必要がある．そのため，回路中に多くのりH塑レジスタが存在すると，スキャン に必要なハードウェアオーバーヘッドが増加してしまう・ 本論文では，りH型レジスタを有する無閉路順序回路に対するテスト生成法 を提案する．無閉路順序回路に対する時間展開モデルを拡張し，L／H型レジスタ を残したままの無閉路順序回路に対しても，組み合わせテスト生成アルゴリズム が適用可能な時間展開モデルを提案する．L／技塾レジスタを有する無閉路順序回 路に対するテストは，各りH型レジスタの制御の異なる全ての時間展開モデル に対してテスト生成を行わなければならない．そこで，時間展開モデルの検出可 能故障に関する被覆関係を示す．被覆する時間展開モデルに対してテスト生成を 行えば，被覆される時間展開モデルに対するテスト生成を行う必要がないことを 示す．しかし，全ての時間展開モデルに対する被覆関係を考えた場合，テスト生 成に必要な時間展開モデルは一般に複数存在する．そのため，テスト生成に必要 な時間展開モデルが容易に，かつ，一意に決定できる回路クラスを示し，それに 対する時間展開モデルを求めるアルゴリズムを示す，本掟案手法により，部分ス 2 キヤン設計に必要なハードウェアオーバーヘッドの低減が期待できる・ 本論文の構成は以下の通りである．第2章では，本論文に関連する故障モデル とテスト，順序回路のテスト生成，スキャン設計の基本的事項について説明する・ また，組合せテスト生成アルゴリズムを適用可能にするスキャン設計について述 第3章では，文献【5】で提案された無閉路順序回路に対するテスト生成法を拡 張し，りH型レジスタを有する無閉路順序回路に対して組合せテスト生成アルゴ リズムが適用可能な時間展開モデルを提案する．また，適用例を示すことで提案 手法の有効性を示す． 第4章で研究のまとめと今後の課題について総括する・ 3 第2章 論理回路のテストとスキャン設計 論理回路のテストは，集積化技術の進歩に伴い，ますます重要になってきてい る．本章では，論理回路に対するテスト生成について説明する・ まず，テストの対象となる故障について述べ，テスト生成とその手法について 述べる．次に，順序回路に対するテスト生成について説明し，順序回路に対する テスト生成を容易にするテスト容易化設計について述べる． 2．1．故障モデルとテスト 回路を構成する要素に物理的欠陥があれば，回路が正しい動作をしなくなる・ このような物理的欠陥を回路の故障という．論理回路の論理機能が故障により別 な論理機能に変化してしまう故障を論理故障という．論理故障の中で最もよく扱 われる故障には，信号線の値が論理値0に固定されるか（0縮退，StuCk−at−0），ま たは論理値1に固定されること（1縮退，StuCk−at−1）を仮定しており，前者の故 障を0縮退故障（s−a−0），後者を1縮退故障（s−a−1）という・そして，1つの論理 回路において同時に1つの縮退故障しか存在しないと仮定したものを単一縮退故 障という．以下，本論文は，単一縮退故障のみを扱うものとする・ 回路に入力パターンや入力系列を加え，それに対する回路の出力パターンや出 力応答系列を観測し，回路に故障が存在するか否かを調べることをテストという・ 故障の存在しない正常な組合せ論理回路の出力関数をふ（ご1，∬2，…，ごれ）とし， 4 ある故障αによってふがム（ご1，エ2，…，‡n）になったとする・この2つの関数を 区別する次の関数を考える． 凡（ご1，ご2，…，ごれ）＝ふ（ご1，ご2，‥・，諾れ）⑳ム（∬1，エ2，…，エれ） この関数を故障差関数という．鳥（∬1，ご2，‥・，ごれ）＝1を満たす入力パタ￣ン ズ＝（ご1，エ。，…，エn）に対しては，ふ（∬1，ご2，‥・，ごm）と以∬1，J2，…，∬几）の値が 異なり，正常な場合と故障αが存在するときで異なる出力を与える・したがっ て，この人カバターンズで故障αを検出することができる・この人カバタ￣ン ズを故障αに対するテストパターンという．故障回路の出力関数が正常な場合 の出力関数と等しい場合，この故障差関数は恒等的に0である・このような故障 は，入出力端子だけから見る限り検出することのできない故障であり，冗長故障 という． 順序回路の場合は，故障を検出するためには，回路の外部入力に入力パターン の系列を与えて，その故障の影響を外部出力に伝搬させる入力パターンの系列を 求める必要がある．これらの入力パターン系列をテスト系列という・いかなる入 力パターンの系列によっても観測が不可能である場合には，その故障は冗長故障 という．これらのテストパターン（系列）は，テストの対象となる回路の論理機能 や，回路を構成している要素の論理横能や要素間の接続といった回路情報をもと に作成される． 生成されたテストパターン（系列）集合で，最初に想定した故障のうち冗長と 判明した故障を含めて，どれだけの故障が検出されるかを示す比率［％】を故障積 出効率（Faulte熟＝iency）とよび，次の式で与えられる・ 改植出勤率＝墜些塑型）＋（空空三雲定され塑些型×100（％） 全故障敷 この故障検出効率を用いることでテストの質を評価することができる・ 5 入力x（t） 現状態 モ 次状磨 出力y（l） 回 申ヰ T 時刻 図2．1順序回路の時間展開 2．2．順序回路のテスト生成 回路中に存在する故障を検出するテストパターン（系列）を求めるアルゴリズ ムをテスト生成アルゴリズムという．組合せ回路についてはこれまで多くのテス ト生成アルゴリズムが提案されており【1］【2］，それらはかなり大規模な回路に対 して高い故障検出効率を得ることが可能である．順序回路についても多くのテス ト生成法が提案されているが，回路規模が大きくなればテスト系列生成が非常に 困難となり，高い故障検出効率を達成することができない場合がある・ 図2．1に示すように，順序回路のテスト生成は，時間展開により得られた組合 せ回路の繰り返し展開に対して組合せ回路用のテスト生成アルゴリズムを適用し て行うことができる．しかし，この場合，回路中のフィードバックループに存在 するフリップフロップのために，時間展開のサイズが一意に定めることができな くなり，テスト生成が行えないと−いう問題がある・ 順序回路のテスト生成において問題となるのは，フリップフロップ（以下，単 にFFと呼ぶ）の可制御性と可観測性である・したがって，順序回路に対して高 い故障検出効率を達成するテスト系列を自動生成するためには，テスト生成を容 6 スキャン出力 ∋ □ 回□ 回□ 回切⊆w 図2．2 スキャン設計の原理 易にするテスト容易化設計によって，このFf、の可制御性と可観測性を高める必 要がある．順序回路に対するテスト容易化設計の一手法として，スキャン設計を 次の2．3節に示す． 2．3．スキャン設計 順序回路のテスト生成において問題となるのは，FFの可制御性と可観測性で ある．したがって，次に示す2つの性質を持つ順序回路に対しては，そのテスト 生成の複雑度は組合せ回路のそれとほほ同じにすることができる． 1．順序回路を構成する各FFに外部から自由に値を設定できる 2．順序回路を構成する各FFの億を自由に観測できる これを実現する方法として，通常の動作のほかに，制御信号によりすべてのFF を直列のシフトレジスタとして動作させるスキャン設計方式【1】【2】がある・ 図2．2にスキャン設計方式の原理図を示す．スキャン設計された順序回路では， 外部からの値を切替スイッチを通してFFに入力する．そのため，スキヤシレジ 7 スタを直列に接続（スキャンチェイン）することによって，シフトレジスタとして 動作させることができる．よって，容易に各FFを任意の状態に設定（スキャン イン）できると同時に，それらの状態を観測（スキャンアウト）することができる・ スキャン設計はテスト容易化設計で広く用いられている手法の一つである・こ の手法では，回路の記憶素子であるFFの組から成るレジスタはシフトレジスタ に置き換えられる．そのため，外部からレジスタの値を直接制御，観測が可能と なる． 全てのレジスタをスキャンレジスタに置き換える完全スキャン設計では，余分 な論理回路を追加したことによる，ハードウェアオーバーヘッドの増加や回路の 動作速度の低下，などの弊害も現れる．これを少しでも解消するために，スキャ ンレジスタになるレジスタを部分的に選択した部分スキャン設計では，ハード ウェアオーバヘッドの増加や動作速度の低下を削減することが可能となる・部分 スキャン設計におけるスキャンレジスタの選択法として，テスト容易性解析に基 づく選択【10，11】，テスト生成に基づく選択【12，13，14，15】，構造解析に基づく選 択【16，17］，などが提案されている．文献【16】ではテスほ成が複雑になる理由 として，フィードバックループに存在するレジスタの値の観測が大きな要因とし て挙げられている．そのため，回路中に存在するフィードバックループを切断す るようにスキャン設計を行うと，その回路に対するテストは非常に容易になる・ しかし，部分スキャン設計を施した回路はレジスタを含んでいるので，依然とし て順序回路用のテスト生成アルゴリズムが必要となる・ 2．4．組合せ回路用のテスト生成アルゴリズムを指向し たスキャン設計 スキャン設計方式において，スキャンレジスタを除いた残りの回路を核回路と いう． 完全スキャン設計により，回路中のすべてのレジスタをスキャンレジスタに置 き換えられた核回路は，組合せ回路となるので，そのテスト生成の問題は組合せ 回路のテスト生成問題として取り扱うことができる．そのため，テスト生成の複 雑虔が飛躍的に改善されるが，前節で述べたように，余分な論理回路を追加した 8 ことによるハードウェアオーバーヘッドの増加，回路の動作速度の低下，などの 弊害も現れる． また，一部のレジスタだけをスキャンレジスタに置き換える部分スキャン設計 方式における核回路は順序回路となる・従来から行われてきた部分スキャン設計 において，核回路に対して順序回路のテスト生成法を利用している［2】【3］では・依 然として高い故障検出効率を得ることは困妊である・これに対して・テスト生成 の複雑度をさらに改善するために，組合せ回路用のテスト生成アルゴリ￣ズムでテ スト生成可能な（組合せテスほ成可能な）部分スキャン設計として・核回路を無 閉路順序回路とする部分スキャン法とテスト生成法【5】が提案されている・文献 何では，無閉路順序回路に基づく時間展開モデルを捷案した・時間展開モデルは 組合せ回路となるので，時間展開モデルに対して組合せテスト生成を行い（ただ し，多重故障対応），得られたテスト集合を無閉路順序回路のテスト集合に変換 することで，テスト生成の複雑度を順序回路の問題から組合せ回路の問題にする ことが可能となる．無閉路順序回路のクラスは，それまでに掟案されていた，平 衡構造【6】，内部平衡構造【7】や切替平衡構造囲のクラスを真に含むクラスである ため，スキャン設計のために必要な追加のハードウェアオーバーヘッドが低減可 能な核回路である． 2．5．無閉路部分スキャン設計 順序回路を無閉路化するために用いる部分スキャン設計では，回路中に存在す る全てのループを切断するような，最小個のスキャンレジスタが選択される・ ここで，一般の順序回路を構成する記憶素子を考えた場合，レジスタは，回路 に対してクロックが与えられとき値を取り込む（ロードする）通常レジスタと，ク ロックの入力の他に1つの制御入力を持ち，制御入力値が真のときにのみ，ク ロックに応じて値を取り込み，それ以外は現在の値を保持し続ける（ホールドす る）ロード／ホールド型レジスタ（以下，りH型レジスタと略す）が存在する・図 2．3に通常レジスタとりH型レジスタの原理図を示す・ 図2．3（b）で示すように∴りH型レジスタは制御信号によって・現在の値を保持 し続けるため，機能的に一種の自己ループとなる．そのため，順序回路に対して 9 HOLD 姻 凰 些 Clo（：k （a）通常レジスタ （b）L／H型レジスタ 図2．3通常レジスタとりH型レジスタ 無閉路部分スキャン設計を行う場合，全てのりH型レジスタがスキャンの対象 となってしまう．そのため，回路中にりH塑レジスタが多く存在すると，スキャ ン設計に必要なハードウェアオーバーヘッドが増加する要因となっている・ 本論文の提案方式では，L／H型レジスタをスキャン設計の対象とせず・りH型 レジスタを有する無閉路順序回路について考える．これにより，りH型レジスタ を考慮しない無閉路部分スキャンに比べて低ハードウェアオーバーヘッドが期待 できる．第3章では，りH型レジスタを有する無閉路順序回路に対して，組合せ テスト生成が可能な時間展開モデルを提案する． 10 第3章 りH型レジスタを有する無閉路順序 回路のテスト生成法 本章では，L／H型レジスタを有する無閉路順序回路に村して，組合せテスほ 成が可能な時間展開モデルを提案する．また，L／H型レジスタを有する無閉路順 序回路と時間展開モデルのテスト生成に関してどのような関係があるかを考察し・ 適用例を用いて提案手法の有効性を示す． 3．1．りH型レジスタを考慮に入れた時間展開モデル 3．1．1トポロジーグラフ 順序回路は複数の論理部から成り，それらの論理部が直接，あるいは，フリッ プフロップの組から成るレジスタを通して接続されているものと考えることがで きる．ここでは，順序回路を構成するレジスタとして，前節で示した通常レジス タとりH型レジスタを考える・このような順序回路に対するトポロジーグラフ は以下のように表現することができる． 定義1（トポロジーグラフ）： トポロジーグラフは，ラベル付き有向グラフG＝（りA，r）であり，頂点り∈V は，外部入出九論理ゲートから成る記憶素子を含まない組合せ論理部，有向辺 11 a ○ ロ傭E b 号 5 UH 図3．1無閉路順序回路5 1・1、11‥）lぢ 1 つ1、l’コ J→／・l’3 −・し 図3．2 gのトポロジーグラフ：G （叫ル）∈Aは，論理部祝がuに単数または，複数の信号線で接続されていること 表す．各辺にはラベルr‥A→Z＋∪ズが付けられている・Z＋は非負の整数の 集合を表し，ズ＝（可1≦壱≦乃）とする．ここで，陀はりH型レジスタの個数 である．申，γ）は，論理部鋸から論理部ひへの接続間には，r（叫ル）∈Z＋ならば r（叫γ）個の通常レジスタがあることを示し，r（叫ル）∈ズならば1つのりH型レ ジスタがあることを示す． ■ 例1‥ 図3．1の無閉路順序回路∫において，1，2，…，6を組合せ論理部，d，e，…，ゐ を通常レジスタとし，α，あ，CをりH型レジスタとする・5に対するトポロジーグ ラフGは図3．2のようになる．ここで，L／H型レジスタに対応する辺には，それ ぞれごいエ2，ご3のラベルが付けられている・ ■ 12 3．1．2 時間展開グラフと時間展開モデル 定義2（時間展開グラフ）‥ 無閉路順序回路5のトポロジーグラフG＝（VA，r）を考える・これに対し，有向 グラフβ＝（鴨，舶，り）を考える．ここで，陀は頂点集合，舶は有向辺集合・f は晦から整数への写像，㍑＝履からトポロジーグラフGの頂点集合Vへの写像 を表す．グラフ厨が次の5つの条件を満たすとき，且をトポロジーグラフGの時 間展開グラフという． Cl（組合せ論理部の保存） 写像は仝射である．すなわち，グラフGの任意の頂点をu（∈V）とする と，写像Jにより，U＝g（u）となるグラフβの頂点u（∈陀）が存在する・ C2（入力の保存） グラフβの任意の頂点を祝（∈鴨）とする．頂点餌に対応するグラフG中の 頂封（w）の任意の隣接する祖先γ（∈Fe（J（u）））に対して・J（u′）＝ひかつ〟∈ pre（u）を満たすβ中の頂点鮎′が存在する・ここで，pre（祝）＝（叫（w′，u）∈A） とする． C3（時刻の無矛盾性） グラフβの任意の辺（叫ル）（∈Ag）について，グラフGに対応する辺（J（祝），J（v）） が存在し，かつ，もし，r（J（祝），J（u））∈Z＋ならば壬（u卜f（ぴ）＝r（J（祝い（瑚， r（J（u），J（り））∈ズならばf（v）＞ま（視）を満たす・ C4（論理部の時刻の単一性） グラフ且の任意の頂点叫ル（∈鴨）について，もし，土（w）＝慮（u）かつJ（祝）＝ J（り）ならば，祝とγは同一の頂点，すなわち，u＝Uである・ C5（りH型レジスタの時刻の単一性） グラフβのJ（ぴ）＝J（w′）∧J（γ）＝J（り′）を満たす任意の辺の組（叫ル），（む′，ひ′） について，もし，r（J（u），申））∈ズかつf（む）＞f（祝′）ならば，f（v′）≧ま（祝）で ある． ■ 13 O 1 2 3 1 2 3 4 5 1 2 6 5 5 図3．3 時間展開グラフ且1 0 蔓1 2 茎 3 1 2 3 4 5 1 5ト・ト16 図3．4 時間展開グラフ且2 例2：図3．1で示される無閉路順序回路を5，gのトポロジーグラフを図3・2のG とする．図3．3，3．4にGの時間展開グラフ旦，β2を示す・それぞれの時間展開グ ラフ且1，且2について，各頂点u（∈帖）が表す数は，対応するトポロジ￣グラフG の頂点名J（u）（∈Ⅴ）を表し，グラフの上部に善かれた数字は・その列にある頂点 uのラベル申）を表す．さらに，β1とβ2のどちらも定義3の条件ClからC5を 満たしている． t この様に，1つのトポロジーグラフから得られる時間展開グラフは複数存在す ることに注意する． 定義き（時間展開モデル）： 無閉路順序回路を∫，∫のトポロジーグラフをC＝（巧A，r），Gの任意の時間展 開グラフをβ＝（陀，AE，り）とする．以下の手続きによって得られる組合せ回路 をグラフ且に基づく回路gの時間展開モデルCβ（∫）という， （1）各頂点む∈鴨について，組合せ論理部J（u）を祝に対応する組合せ論理部と する． （2）各有向辺（叫ル）∈Aβについて，（∫（ひい（u））と同様に，祝からuへ信号線（バ 14 訳悪評 瓦「七乳ヨ互 図3．さ．glに基づく時間展開モデルCgl（5） ス）で接続する．ただし，J（ひ）＝J（む′）∧り≠ひ′となる2辺（叫り），（叫ル′）が存 在するなら，論理部別の出力から論理部り，り′のそれぞれの入力に，分岐し て接続する．このとき，たとえJ（w）とJ（γ）の間にレジスタ（ただし，L／H型 レジスタも含む）が存在しても，論理部叫ル間の接続はレジスタを介さない・ （3）各論理部内の信号線および論理ゲートについて，外部出九または，他の 論理部の入力のいずれにも到達不可能なとき，その信号線または論理ゲー トを削除する． ■ 例3：図3．3の時間展開グラフ鋸こ対する時間展開モデルは定義3の手続きを用 いると図3．5に示すものとなる．ここで，国中の点線の部分は手続き（3）で取り 除かれた回路を表す． ■ 以上のように，時間展開モデルCg（5）は，時間展開グラフβから一意に決定 することができる． ここで示した時間展開モデルは，L／H型レジスタの制御によって保持される値 の様子も表し，これは文献【51の拡張となっている．したがって，L／H塾レジス タに与える制御の違いにより，異なる時間展開モデルが得られることに注意する・ 例4‥ 図3．5で示す時間展開モデルCgl（5）は，無閉路順序回路∫において，各 りH塑レジスタは通常レジスタとして動作するときの時間展開モデルを表す・ま た，図3．3で示す時間展開グラフ鋸こ基づく時間展開モデルをCgl（∫）とする・こ のとき，Cgl（5）はラベルご1，∬。で示されるりH型レジスタは通常レジスタとし て動作し，ヱ2は時刻1でロードした値を1時刻の問保持し，論理部4の入力とな 15 るときの時間展開モデルを表す． 3．2．りH型レジスタを有する無閉路順序回路のテスト 生成 本節では，無閉路順序回路と時間展開モデルの間の故障の関係と，時間展開モ デルの故障の関係を考察する．さらに，無閉路順序回路に対するテスト生成は時 間展開モデルを用いて組合せテスト生成可能であることを示す・ 3．2．1時間展開モデルを用いたテスト生成 ここで，無閉路順序回路の入出力系列と時間展開モデルの入出力パターンとの 関係を考える．ただし，りH型レジスタの制御入力信号は自由に設定できるもの とする．L／H型レジスタを示すヱ‘の制御系列を筏とし，時刻士での制御信号の 値を且（f）とし，制御信号はL（ロード），H（ホールド），×（ドンけア）と表す・ 無閉路順序回路を∫，5のトポロジーグラフをG＝（VA，r）とする・Gの任意 の時間展開グラフを且＝（晦，AE，り），捌こ基づく5の時間展開モデルをCg（5）・ βのラベル上の最小値と最大値をそれぞれ，士m如上m8。とする．時間展開モデル Cβ（∫）に対する入力パターンを，5に対する時刻fm‘nからfmα。までの入力パター ン系列とL／H型レジスタの制御系列を，以下に示す手続き巧によって変換する・ 定義4（手続き巧）‥ 条件C4より，∫の各論理部γ∈Ⅴについて，各±（㌦壷≦ま≦土耶。）に対し， 申）＝＝川前J（祝）＝Vである祝∈晦力滴々1つ存在する・このとき・uへの入力 パターンんを，論理部uへの時刻fの入力パターンん（f）とする・L／H型レジス タ勘に対応する，すなわち，こち＝r（J（u），J（u））（∈ズ）となる各辺（叫ル）（∈Ag）に ついて，時刻≠′におけるご一への制御信号既（f′）を以下のようにする・ f′＝ま（祝）−㍍血 ′川こ（：i 中）−㍍血＜f′＜申）−㍍血 ただし，上記の式で定義されない制御信号の値はドントケアとする・ ■ 16 この手続き毎について，以下の補題が成立する・ 補題1：時間展開モデルCg（∫）への任意の入力パターンをん，手続き丁ざによっ て得られるgへの入力系列をん，各L／H型レジスタ勘の制御系列を玖とする・ このとき，入力パターンJcに対するCE（∫）の任意の論理部w∈陀の出力パタ￣ ンOuは，入力系列んに対する，Uに対応する論理部J（u）の時刻申）−㍍血の出 力パターン0′（u）（ま（u卜まm‘n）と等しい・ 証明‥侮（5）の論理部別の入力に接続されている任意の論理部をu′（∈pre（u）） とする．u′に対応する∫の論理部J（祝′）は，条件C2，C3より，J（u）の入力側の 論理部として接続されている．祝′への入力パターンんは，手続き丁βによって時 刻叫）−㌔血の論理部J（ぴ′）への入力パターンム（u′）（叫）−㍍血）に変換され る．このとき，条件C4により，時刻f（u）−㍍血の論理部J（ひ′）への入力パタ ーンに変換される入力パターンはただ一つである．論理部u′への入力パターン ム（呵（申′卜f血）と・U′の論理によって出力された論理値は・r（J（M′），J（む））∈Z＋ のとき，r（J（u′），J（w））（J（u′），J（u）間のレジスタ数）時刻後に論理酎（ぴ）の入力値と なる．また，r（J（“′），J（M））＝エ‘（∈ズ）ならば，手続き巧で得られた既により・時 刻f（u′）一㍍血で論理部u′の入力パターンム（呵（堰）−㍍血）と・祝′の論理によっ て出力された論理値が，筏（f（u′）−㍍血）＝Lとなることで，りH型レジスタに ロードされ，時刻f（u）−㌦血まで，その論理値は保持されている（条件C5によ り，J（u）＝J（む′）∧J（γ）＝申′）∧申）＞申′）∧r（J（uい（γ））∈ズを満たす任意の辺 の組（叫ル），（u′，ひ′）について，f（ひ）＜ま（w′）＜申）となるま（り）は存在しない）・よっ て，論理部u′への入力パターンム（叫（f（㍑′）−㍍血）と，“′の論理によって出力され た論理値は，蓋（可十申′）時刻後に必ず論理部J（w）の入力パターンとなる・以上 より，補題が成立する． ■ 例5‥図3．6は且2の時間展開モデルC哉（∫）を表し，図中のんふ，ん0，んl，043，082 は入出力応答を示す．表3．1は，図3．1で示す無閉路順序回路5に対する入出力系列 と，そのときのりH型レジスタの制御系列仇，仇，仇を示す・変換Tβから，Cβ。（g） の入力パターンはぶの入力系列と各りH型レジスタ勘の制御系列且（1≦壱≦3） に変換できる． ■ ■ 17 IlO問Il匪野 Ⅰ5［∃bl［雪月互062 図3．6C包（ぶ）入出力パターン 0 1 2 3 論理部1の入力 ム0 ん × × 論理部5の入力 ム0 ム1 × × 論理部4の出力 × × × 043 論理部6の出力 × × 062 × ガ1 × L x x 筏 × L H x 仇 × L x x 表3．1∫入出力系列と各L仲型レジスタの制御系列 次に．無閉路順序回路を∫，∫のトポロジーグラフをG＝（隼A，r）とする・無 閉路順序回路引こおける時刻㌦の論理部び（∈りの出力パターン0ぴ（りを決 定するための入力系列と各L／H型レジスタへの制御系列をそれぞれん，筏とす る（入力系列または，制御系列中で0ぴ（りに影響しない部分はドントケア）とす る．このとき，以下に示す手続き巧によって，ん，筏（1≦壱≦陀）は時間展開グラ フβ＝（陀，Ag，り）とβに基づく時間展開モデルCβ（∫）の入力パターンに変換 する． 定義5（手続き叱）： （1）時間展開グラフ生成手続き 18 （1−a）V′‥＝（ぴ）とする．グラフ且＝（陀，Aβ，り）を考え・その初期値を J（〟）：＝叫匝′）：＝fu，晦：＝￠，舶：＝￠とする・ （1−b）頂点ひ（∈V′）を1つ選択し，V′＝＝V′−iり）とする・βの頂点をJ（明：＝ひ とし，陀‥＝陀∪（り′）とする．任意の頂点址（∈pre（り））を考える・ J（u′）＝餌とする頂点u′について，もし，r（叫び）∈Z＋ならば・t（鋸′）‥＝ f（u′トr（叫ル）とし，r（叫び）＝ご‘ならば，岬）の値を，旦（玩）＝L∧まん＜ 岬）を満たす最大のf九とする・ （1−C＝（u′′）＝J（u′）＜f（u′′）＝f（祝′）となる頂点祝′′（∈陀）が存在するなら ば，Aβ：＝舶∪（（祝′′，明）とし，存在しないならば，Aβ‥＝Agu （（w′，明），陀‥＝陀∪（v′），V′‥＝V′∪（u）とする・ （1−d）V′≠￠ならば，（1−b）を繰り返す・ （1−e）Gの頂点wにおいて，J￣1（u）が存在しないならば・頂点㍑とその全て の祖先からなる部分グラフを，条件ClからC5を満たすようなグラフ にする． （2）入力系列変換手続き （2−a）∫の論理部びに対応するCg（∫）の論理部の集飢￣1（Ⅶ）からある論理部 び′（∈J￣1（ぴ））を選択する・ （2−b）論理部びの時亥軋の出力値（0り（り）に必要な入力パタ￣ンについて・ 5の時刻電′のv′への入力パターンん（りを，ひ′∈J￣1（り′）かつ士（u′）− ま（〟）＝電一がを満たす論理部u′への入力パターンんとする・ ■ また，手続き巧について，以下の補選が成立する． 補題2：無閉路順序回路5の任意の論理部をひ（∈V），任意の時刻fにおけるり の出力パターンOv（りを決定するための入力系列をんとし，各L／H型レジスタ ヘの制御系列を且とする．このとき，手続き旬によって得られる入力パターン をん，時間展開グラフβに基づく時間展開モデルをCβ（5）とすると，γに対応す るCβ（∫）の論理部uにおける出力パターンOvはOv（f）と等しい・ 19 証明：（1−b）によりC2，C3を満たす・また，g（u）＝J（u′）∧JM＝J（ひ′）∧r（J（ぴい（u））∈ ズを満たす任意の辺の組（叫り），（祝′，V′）について考える・電（u），申′）は制御系列常 によって，ま（u）＞岬）ならば，岬）＜申）となり，また，￡（u）＜f（む′）ならば・ f（u）＝岬）となる．これは条件C5を満たす・（トc）において・頂点u′′を考える ことで条件C4を満たしている．（1−b），（1−e）により条件Clを満たす・よって，（1） の時間展開グラフ生成手続きによって得られるグラフは，時間展開グラフの全て の条件を満たしている． また，条件Clにより，りに対応するCβ′（5）の論理部鋸∈J￣1（γ）が少なくと も1つ存在する．論理部γの入力に接続されている任意の論理部をu′（∈pγe（ひ）） とする．り′に対応するCE∫（g）の論理部u′∈J−1（り′）は，条件C2により，祝の 入力に接続されている．時刻まの論理部γの出力パターン0リ（f）に必要となる 論理値は，論理部ひ′への入力パターンと，U′の論理によって出力された論理値と なる．論理部v′への入力パターンは，r（り′，り）＝Z＋ならば，r（り′，り）（再開のレ ジスタ数）時刻前のパターンん（土−r（再））となり，r（再）＝ご‘ならば，時刻 f九（＝叫））でL／H塑レジスタにロードされたパターンん（亡ん）となる（手続き巧 の時間展開グラフ生成により，且（岬））＝Lとなり，条件C5により，叫）から 電（u）までの時刻でその倍は保持されている）・よって，時刻吋（再）∈Z＋なら ば，f′＝f（㍑）−r（u′，W）とし，r（再）∈ズならば，f′＝玩とする）入力パタ￣ン ん（f′）は，手続きTcの入力系列変換によって，叫）＝f（可−イを満たす論理部u′ への入力パターンんに変換される．このとき，条件C3および条件C4により， 叫）＝ま（祝）−がを満たす頂点はただ1つ存在する・以上より，補題が成立する・■ 次に，無閉路順序回路の故障とその時間展開モデルの故障との関係を考える・ ここでは，無閉路順序回路∫の故障として，組合せ論理部内の信号線の単一縮退 故障を考える．組合せ論理部間の信号線の縮退故障やレジスタ（L／H型レジスタ も含む）の入出力線の縮退故障は，組合せ論理部の入力線や出力線の縮退故障と 等価と考えることができる． 定義叩寺間展開モデルの故障）： 無閉路順序回路を5とする．5のトポロジーグラフをG＝（隼A，r），Gの任意の 時間展開グラフをβ＝（陀，A釣り），捌こ基づく5の時間展開モデルをCβ（∫）と 20 する．無閉路順序回路∫の組合せ論理部の故障集合をダ，時間展開モデルCβ（5） における故障集合を克とする．このとき，回路∫の故障J∈利こ対応する時間 展開モデルCE（g）の故障ム∈鞄は，故障Jの存在する論理部り∈Ⅴと対応する C月（g）の各論理部u∈J−1（り）の同じ位置（信号線）に存在する多重故障とする・ 以上より， （1）J（ぴ）＝りとなる論理部びがただ一つのとき，ムは単一縮退故障 （2）J（ぴ）＝りとなる論理部祝が複数存在するとき，ムは多重縮退故障 ■ となる． 定理1‥ 無閉路順序回路を∫，∫のトポロジーグラフをG＝（りA，r），Gの任意 の時間展開グラフを且＝（陀，A訊り），捌こ基づく∫の時間展開モデルをCβ（∫） とする．無閉路順序回路∫の故障集合をダ，時間展開モデルCg（g）における故 障集合を鞄とする．このとき，故障ム（∈鞄）に対するテストパターンは，対応 する故障J（∈ダ）に対するテスト系列に変換可能である・ 証明：故障先のテストパターンを±ムとする．故障Jが存在する回路gをざJとする・ 故障ムが存在するCg（5）をCg（g）′。とする・このとき，Cg（g），砧（g）ムにfJ。を与 えたときの出力値をそれぞれ，砧（g）（り．），Cg（g）ム（七Jモ）とすると・Cg（g）（電Je）≠ Cβ（g）ム（重ん）となる・故障ムは・故障Jが存在する論理部り（∈V）に対応する論 理部J−1（ひ）すべてに存在する多重故障なので，C丘（∫）ムは，時間展開グラフ且に 基づく∫∫の時間展開モデル砧（gJ）と同型である・したがって，手続き巧によっ て土人から変換される入力系列とりH型レジスタの制御系列からなるテスト系列 をちとする．∫，5′に符を与えたときの出力値をそれぞれ，5（乃），5／（乃）とする・ 補遺1より，∫（乃）＝Cg（∫）（fん），5J（乃）＝砧（∫）ム（fふ）となり，g（乃）≠∫ノ（乃） である．よって，乃はJのテスト系列である・ ■ 定理2：無閉路頒序回路ぶとし，gのトポロジーグラフをG＝（りA，r）とする． ∫の故障集合を∫とする．無閉路順序回路において検出可能な，すなわち，テス ト系列が存在する任意の故障J（∈ダ）について，故障Jに対応する故障ふが検出 可能な時間展開モデルが存在する． 21 証明：故障Jのテスト系列を乃とする．故障げ存在する回路5を5Jとする・ 手続き町により得られる時間展開グラフを月とし・且に基づく時間展開モデルを c且（∫）とする・故障Jに対応する故障ふがCg（5）に存在する時間展開モデルを C且（∫）J．とする・故障ムは，故障げ存在する論理部り（∈V）に対応する論理部 J−1（v）すべてに存在する多重故障なので，C鞍（g）は・時間展開グラフ動こ基づ く∫Jの時間展開モデルCβ（5J）と同型である・このとき・補選2より・手続き 化によって符から変換されるテストパターンまJeは・ムのテストパターンになる・ よって，ムを検出可能な時間展開モデル砧（g）が存在する・ ■ 定理2の対偶より，以下の系が成立する． 系1：無閉路順序回路gの任意の故障をJ七すると，任意の時間展開モデルに対 して対応する故障ムがテスト不能ならば，故障Jもテスト不能である・ 以上のことから，りH型レジスタを有する無閉路順序回路は，りH型レジスタ を考慮した時間展開モデルを用いることで，組合せテスト生成アルゴリズムが適 用可能であるといえる． 3．2．2 時間展開グラフの被覆関係 前節で述べたように，無閉路順序回路はその時開展開モデルを用いることでテ スト生成が可能である．また，時間展開モデルは組合せ回路なので，多重故障相 応組合せ回路用のテスト生成アルゴリズムを使ってテスト生成を行うことができ る．一方，時間展開モデルは，無閉路順序回路中のL／H型レジスタに与える制 御系列に応じて作られる．したがって，各L／H型レジスタの異なる制御系列を 考え，それに応じた全ての時間展開モデルを用いてテスト生成を行うことは・無 閉路順序回路中の全ての故障について検出可能か不可能かを判定するために十分 である．しかし，一般に，全ての時間展開モデルを求めることは困難であり，か っ，多くの時間展開モデルに対してテスト生成アルゴリズムを実行することは・ たとえそのアルゴリズムが組合せ回路用であっても，多くの時間を要すると思わ れる．ここでは，2つの時間展開モデルの間に検出できる故障に関してどのよう な関係があるかを考察し，全ての時間展開モデルに対してテスト生成を行う旦要 がないことを示す． 22 定義7（時間展開グラフの被覆関係）： 無閉路順序回路を5，∫のトポロジーグラフをGとする・トポロジーグラフG の，任意の2つの時間展開グラフを且1＝（Ⅵ，Al，Jl，土1），且2＝（鴨，A2，J2，f2）と する．Jl（り1）＝J轟2）となる任意の頂点対をり1（∈Ⅵ），ひ2（∈鴨）とする・頂点 γ1，V2とその全ての祖先から導出されるグラフを，それぞれ且i＝（咋，A；，Ji，fi）， β左＝（堵，Aら，J⊆，まら）とする．このとき， ∀（u′，り′）（∈A左）ロ（叫ル）∈A；， 視∈覇咋（u′）∧り∈喘鳴（珊 （3．1） を満たす写像布，喝＝吋→畷力囁在するとき・且は旦逐被覆するといい・ 月1ヒ L β。と表す． 定義7より，以下の系が成立する． 系2：無閉路順序回路をg，5のトポロジーグラフをGとし，且1≧：β2である Gの2つの時間展開グラフを風＝（Ⅵ，Al，Jl，fl），且2＝（鴨，A2，J2，t2）とする・ Jl（り1）＝J2（γ2）となる任意の頂点り1，り2に対し，頂点vl，り2とその全ての祖先から 導出されるグラフを，βi＝（町，Ai，Ji，≠i）とβ墓＝（咋，Aち，g；，士ち）とする・グラフ 且i，β；の頂点数をそれぞれ＃叫，＃畷とする・；のとき，以下の式が成立する・ ＃吋≧＃堵 （3・2） 証明：写像在明：咋→咋が定義されるためには句，りは仝射となる・よって・ 系2は明らかである． ■ 無閉路順序回路をg，∫のトポロジーグラフをGとする．β1とβ2を満たす任 意の時間展開グラフを且1＝（Ⅵ，AlんJl），β。＝（鴨，A2，ま2，J2）とする・β2に基づ く時間展開モデルC筏（∫）の任意の論理部v2の出力パターン0γ2を決定するため に必要な入力パターンちは，以下に示す手続き伽によって，鋸こ基づく時間展 開モデルCgl（∫）への入力パターンムに変換できる・ 定義8（手続き1w）： Cβ2（5）の論理部ひ2に対応するCβ1（g）の論理部をγ1とする（すなわち・Jl（り1）＝ 23 柚。））．り1とその全ての祖先からなる頂点集合を町・り2とその全ての祖先からな る頂点集合を畷とする．定義7の条件（3・1）を満たす写像布，り‥咋→畷を求 める．時間展開モデルCg。（∫）の各論理部γ；∈堵への入力パターンん星を・Cβ1（g） の対応する論理部境埠（り；）（∈呵）への入力パタ￣ンとする・ 1 この手続きにより，以下の補題が成立する． 補題3‥無閉路順序回路を∫，∫のトポロジーグラフをGとする・β1ヒβ2を満た す任意の時間展開グラフをβ1＝（坑，Al，fl，り，且2＝（鴨，A2，f2，J2）とする・時間 展開モデルC包（ぶ）の任意の論理部をu。とする・論理部ひ2の出力パターンを決定 するためのCE。（5）の入力パターンをちとする・手続き瑚によって得られる写像 を句，愕とする・句，堵によって論理部明に対応付けられたCぷ1（∫）の任意の論理 部をul（∈境写（v2））とする・手続き伽によって得られる，ムに対応するCβ1（∫） への入力パターンをムとする．このとき，入力パターンムをCEl（5）に与えて得 られる論理部ひ1の出力パターン仇1はOtりと等しい・ 証明：Cg2（g）の論理部w2の入力に接続されている任意の論理郡を丞（∈pre（加2）） とする．変換手続き旬によって得られる写像環喝により，祝2に対応するCgl（5） の任意の論理部をul∈環埠（u2）とする・Uちへの入力パタ￣ン句は・変換手続き 伽によって，ul∈pre（叫）∧可∈瑞喝（ひち）への入力パターン句に変換される・ 条件C2より，句とuちの論理によって出力される論理値が・論理部祝2の入力と なるとき，句と祝iの論理によって出力される論理値も・論理部ulの入力値とな る．論理部祝。の出力パターンOv。は，対応するCぷ1（∫）の論理部祝1の全ての出力 パターン0叫と等しい・よって，変換加によってムから変換される入力パターン ムについて，ムをC仇（ざ）に与えることで得られる論理部り1の出力パタ￣ン0γ1 は，論理部u。の出力パターンOtセと等しい． ■ 定義7よりβ1とβ。かつβ1＝≦且。となるならば，たとえ，L／H型レジスタの制 御系列が異なっていても，且1とβ2に基づく時間展開モデルCgl（ぶ）とCg2（∫）は 同じ機能を実現する時間展開モデルになる．このとき，β1とβ2は等価で同値類 に属すると考えると，同値類のクラスは半順序の関係となる． 例6：無閉路順序回路5を図3．1とし，gのトポロジーグラフGを図3・2とする・ 24 0 】 2 ：事 1 2 3 J 5 1 2 1 5 5 6 図3．7 5■のGに基づく時間展開グラフβ3 0 1 2 3 1 2 3 4 5 1 2 5 5 6 図3．85−のGに基づく時間展開グラフβ4 0 1 2 1 2 3 4 63 5 豪 図3．9 5−のGに基づく時間展開グラフ且5 匡⊇ 回因 回 図3．10仇，且2，品，β。，且5の関係グラフ 25 Gの時間展開グラフの一部の例を図3．3，3．4，3．7，3．8，3．9で示す且1から属5とする・ このとき，定義7によって得られる関係グラフを図3・10とする・この関係グラフ において，馬は且1を被覆している．また，β2と且4かつβ2ゴβ4となり，時間展 開グラフ且。，包は同値類に属する． ■ 定理3：テスト可能性 無閉路順序回路を5，gのトポロジーグラフをGとする・β1とβ2を満たすG の時間展開グラフを風，β2とする．且，且2に基づく時間展開モデルをそれぞれ C月1（∫），C包（g）とする．5の故障Jに対するCβ。（5）の故障をムとし・それに 対応する免1（∫）の故障をムとすると，次式が成立する・ 且1ヒβ2⇒【砧。（ぶ）で故障ムがテスト可能⇒Cgl（g）で故障ムはテスト可能】 証明‥故障ムのテストパターンをま′。とする．故障ムが存在するCE2（5）をCE2（∫）か 故障ムが存在する瑚g）を侮1（∫）ムとする・CE。（∫），砧2（∫）ムに玩を与えた ときの出力値をそれぞれ，Cg。（g）（玩），Cβ。（∫）ム（玩）とすると，Cg2（g）（り。）≠ 砧2（5）ム（t力）となる・手続き瑚によって玩から変換されるパターンを玩とする・ このとき，CEl（g），CEl（∫）ムにり1を与えたときの出力値をそれぞれ・Cβ1（g）（ま′1），CEl（g）ム（り1） とする．補題4より，Cgl（g）（まム）＝C筏（5）（電ム）となり，Cgl（∫）ム（まム）＝Cg2（∫）／2（電力） である．よって，Cβ1（∫）（玩）≠C動（∫）′1（士ム）である・したがって・り1はムのテ ストパターンになる．以上より，Cg2（∫）で検出可能な故障はCgl（∫）でも検出可 能である． ■ 時間展開グラフβが」且と同値でない全ての時間展開グラフ且りこついて，β′と且 ならば，且を極大展開グラフと呼び，捌こ基づく時間展開モデルを極大展開モデ ルと呼ぶ． 無閉路順序回路に対するテスト生成のためには，全ての極大展開モデルに村し てテスト生成を行うことが十分である．したがって，極大展開モデルが多く存在 する場合，テスト生成に多くの時間がかかる．また，極大展開モデルを求めるた めには，一般にりH型レジスタに与える制御の違いを考えた時間展開モデルに 対して被覆関係を考える必要があり，多くの時間を要する．これらを解決す皐方 法を以下に述べる． 26 3．3．最大展開モデルが存在する順序回路の構造 無閉路順序回路のテストを考えたとき，完全故障検出効率を達成するためには・ 全ての極大展開モデルに対してテスト生成を行う必要がある・ここでは，極大展 開モデルがただ1つ存在し，すなわち，最大展開モデルが存在し，かつ，最大展 開モデルが容易に生成可能な無閉路順序回路のクラスを考える・ 3．3．1最大展開モデルが存在する回路構造 トポロジーグラフに関して，2つの頂点間の経路長を次のように定義する・ 定義9（経路長β）‥ トポロジーグラフG＝（隼A，r）において，2つの頂点り，U′（∈りの間に存在する経 路の集合を鳥，V．とする．経路p＝（vl，U2，…，りれ）について，占（p）＝∑慧r（明，恥1） と＿する・ただし，r（ひi，叫1）∈ズのときは・そのラベルは変数と考える・ ■ ここで，トポロジーグラフが以下の条件を満たすような無閉路順序回路を考 える． cMlトポロジーグラフG＝（VA，r）において，r（叫ル）∈ズなる任意の頂点ひ とびから到達可能な任意の頂点γ′（∈りについて，次式が成り立つ・ ∀p，9∈鳥〝，β（p）＝β（q） 条件CMlを満たす無閉路順序回路5のトポロジーグラフGとする・Gの時間 展開グラフをβ＝（陀，Ag，り）とする．且の任意の頂点とその全ての祖先からな る部分グラフβ′＝（畷，A忘，f′，りについて考える・飢こおいて各L／H型レジス タに必要なロード信号は高々1つだけ出現する．このことから，各部分グラフに 関して，γ（J（祝い（u））＝ご‘∧r（J（ぴ），J（γ））＝r（J（祝′），岬））となる辺（再′）は存在 しない．そのため，各部分グラフに関して条件C5は必ず満たしている・よって， 各りH型レジスタの制御は条件C5に関係なく，そのロード時刻とホールド時間 を自由に与えることができることを表している． 以上のことから，条件CMl・を満たすトポロジーグラフ（＝こ対して，以下のア ルゴリズムを通用する． 27 アルゴリズムMAXTEG l．トポロジーグラフ引こおける出次数0の頂点集合を％（⊆りとする・各 頂点ひ∈鴨について，J（㍑）＝γとなる時間展開グラフβの頂点u∈陀を決 定する．その頂点集合を打とする． 2．各項点w∈Uについて，条件C2，C3を満たすように，祝を終端頂点とする部 分グラフを作成する．また，頂点uを終端とする部分グラフの集合をβとす る．ここで，りH型レジスタのラベル値は全て1とする・また・r（叫ル）＝ごf となる辺の，L／H型レジスタェ‘の制御信号を変えると，頂点uの全ての祖 先からなる部分グラフの各頂点に関して，ラベル関数fによって与えられ る値も変化する． 3．且；＝（Ⅵ，A‘，土‘，り∈月としたとき， d‘＝欝（柚）ト恕（埴）） とするd‘を決定する． 4．（a）βご＝（Ⅵ，A‘，f‘，り∈βを1つ選択し，且；の終端頂点w（∈U）とする・ （b）頂点祝から祖先をたどっていき，その頂点間の辺にL／H型レジスタのラ ベルが存在する場合（すなわち，r（J（w′い（明）＝勺），叫）＝f（u′）一子ん とする．ただし，玩は1≦玩≦琉を満たす，頂点u′の全ての祖先から なる部分グラフの任意の頂点が，条件C4により単一化されないとき の最小値とする（系2より，部分グラフの頂点数が最大となるように fんを調整）． （c）坑‥＝di＋ま九とし（b）へ・ （d）β‥＝β−1句）とする・ガ≠￠ならば（a）へ・ 5．条件（C5）を満たすように各部分グラフのf‘の値を調整する・ このアルゴリズムを用いて得られる時間展開グラフβと，且のL／H型レジネタ の制御信号であるホールド信号を与える時刻を変えることによって得られる任意 28 の時間展開グラフ且′を考える．且とβ′との間に定義7の条件（3・1）を満たす写像 げ存在するならば，且と茸は同値類に属するか・または・βと且′となるかのい ずれかである．したがって，求められたグラフ別ま，最大展開グラフとなり・こ れを且mα。と記す，且冊に基づく時間展開モデルが最大展開モデルCgm。J（g）と なる． 例7：無閉路順序回路∫を図3．1とし，∫のトポロジーグラフGを図3・2とする・ Gは条件CMlを満たすので，G＝こ対してアルゴリズム（MAXTEG）を適用した 例を，図3．11，3．12，3．13に示す．ステップ2・で得られる部分グラフは図3・11の月i ，β墓となる・βi，些不対してステップ4・を適用すると図3・12となり・各部分グラ フで最大化が行われている．また，ステップ5．で土を調整したものが，最大展開 グラフ且mα￡となり，βmα。に基づく時間展開モデルCEm。J（∫）が最大展開モデル となる． ■ このことから，無閉路順序回路∫に最大展開グラフが存在するとき，無閉路順 序回路に対するテストは，最大展開モデルに対してテスト生成を行うことが必要 かつ十分となる． また，トポロジーグラフGが以下の性質を満たすならば，Gから最大展開グ ラフが作成可能である． cM2トポロジーグラフG＝（VA，r）において，r（叫ル）∈ズなる任意の頂点uと びから到達可能な任意の頂点v′（∈V）について，］9，9′∈且，V・，β（9）≠β（〆） となる経路が存在する（すなわち，条件CMlを満たさないL／H型レジス タ）ときの，L川型レジスタのトポロジーグラフ上のラベルr（叫ル）＝ご‘を Ji＝1に置き換える．任意の頂点びと，ぴから到達可能な頂点び′間に存在 する2つの経路p＝（Ⅷ十Ⅷ1，ぴ2，…，呵と〆＝（ぴ，可，ぴ；，…，叫を考える・ ただし，経路p，〆は以下の条件を満たす・ （1）］妄r（叫，叫．1）∈ズ∨］jr（ぴ；，ぴ；．1）∈ズ （2）∀よ，jr（叫，叫＋1）≠r（ぴ；，ぴ；．1） （8）∀盲，J叫≠可 29 経路p，〆が存在するならば，以下の条件が成立する・ 埠，〆∈鳥両β（p）≠5（〆） 上述の性質CM2は，条件CMlの最大展開グラフが存在する条件を緩和したもの である．これにより，トポロジーグラフに最大展開グラフが存在する条件は，さ らに広い範囲のトポロジーグラフのクラスに対して適用可能と考えられる・ 3．4．適用例 本節では，一般の順序回路に対して本手法を適用する例を示す・ まず，一般の順序回路を図3．14（a）で示されるものとする・文献【5】で提案され た無閉路順序回路では，L／H型レジスタは自己ループとして扱われているので・ 回路の無閉路化のために最小フィードバック頂点集合（MFVS）【171によって，レ ジスタα，ゐ，C，d㍉，J，gがスキャンレジスタとして選択される・ しかし，条件CMlを満たすようにスキャン設計を施すと，スキャンレジスタ はレジスタJ，gだけとなり，L／H型レジスタを有する無閉路順序回路が図3・14（b） となる．以上のことから，本手法は文献【5】で提案されたりH型レジスタを考慮 しない無閉路順序回路より，スキャン設計に伴うハードウェアオーバーヘッドが 低減可能となる． 図3．15は，図3．14（b）で示されたりH型レジスタを有する無閉路順序回路51 のトポロジーグラフGlである．ここで，Glは前節で述べた条件CMlを満たし ているので，glは最大展開モデルが存在する回路となる．このことから，トポロ ジーグラフGlを基にアルゴリズムMAXTEGを用いて最大展開グラフを生成 する．アルゴリズムMAXTEGを用いて，Glからステップ2．によって求められ る部分グラフが図3．16の（a），（b）となる．ステップ4・によって最大化された部分 グラフが図3．17の（a），（b）となる．ステップ5・によって各部分グラフのラベルt の値を調整して得られた最大展開グラフが図3．18となる．最大展開グラフβm血∬ に基づく最大展開モデルCEm。β（g）が図3．19となる・ 以上のようにして，最大展開モデルを得ることが可能となる．Cgm。f（5）に対 して組合せテスト生成を行う．時間展開モデルに対応したL／H型レジスタゐ制 30 御系列集合を定義44に基づき変換し，組合せテスト生成によって得られたテス トパターン集合を定義4に基づき無閉路順序回路のテスト系列集合に変換する・ これらにより，順序回路用に変換されたテスト系列集合は，完全故障検出効率を 達成することが可能となる． 31 tli3蔓tl≦2蔓tl云1≡ t2−2 5 1 邑t≒1旨 1 2 5 5 5 （b）且墓 （a）且i 園3．11ステップ2．で得られる部分グラフ tl−4 t−3 tl−2 1 2 竃t−1 t1 3 4 5 1 1 2 5 （a）且i t2−2 t2−1 t2 1＝二！＝（l 5 5 （b）且i 彗 図3．12 ステップ4．で最大化した部分グラフ 0蔓壬 5 2 3 4 2、3 4 1 嘗 豪 家 1 2 6 5 を 国3．13ステップ5．で得られる最大展開グラフ月mα∬ 32 一 a［可 a［丸i b 加岨 ‥回≡転 C 且h［可 kL d 川7盟謹 b 饗砧j C 回e回l聖賢圃 （b）無閉路順序回路51 （a）順序回路 図3．14順序回路とりH型レジスタを有する無閉路順序回路 ⑦1 ①1⑦ 毎」El さl、1γ‥j 回1四 1 ⑥∬5（ヨ 1 9 1 図3．15∫1に基づくトポロジーグラフGl 33 l5l t妄t鍼芸 岳至岩 J l l 】 1 2】‡ 竃 …t誠事実 2 1 7日8日 2奉 ∩ 1 t−1日 t l l H 8 6 ■ 7 〔司 l 10 − 9 （a）βi （b）且墓 園3．16MAXTEGのステップ2．で得られた部分グラフ ト5 t−3 ト2 t＿4 lJi 】 2 r 1【 4 3 弓彗①弓 t 21巨 琵 1：■ 2 】； 1 2】 ⊇≧ 8 1 【 萱書 6 謀 7 日 三≡二≒二 10 （a）βi （b）β； 図3．17MAXTEGのステップ4．で得られた最大部分グラフ 34 l 】 廷 1 2 0 3 4 5 3 4 5 1 2： …眉2 1 2 1 8 （司 【 7 臣10 l 9 日 捜 図3．18MAXTEGによって得られた最大展開グラフEmac 圧トセか耳已づ互 7、、2 5 ［□」∃ 中 也 S 回H回 匂 圃 図3．19軌皿に基づく最大展開モデル毎mェ（5） 35 第4章 結論 本論文ではりH型レジスタを有する無閉路順序回鱒＿に対しても組合せテスト生 成が可能な時間展開モデルを提案した．第2章では組合せテスト生成が可能な順 序回路として，核回路を無閉路順序回路にしたときのテスト生成法を示した・無 閉路順序回路は平衡構造，内部平衡構造や切替平衡構造よりも，低いハードウェ アオーバーヘッドで実現可能なテスト容易な回路である．第3章ではL／H型レ ジスタを有する無閉路順序回路に対して，組合せテスト可能な時間展開モデルを 遺棄し，冬時間展開モデルに対して故障検出における被覆関係を導入した・被覆 関係を用いることで，テスト生成に必要な時間展開モデルを明らかにし，得られ た時間展開モデルに対して組合せテスト生成を行うことで，無閉路順序回路のテ ストが可能であることを示した．また，一般にテスト生成に必要な時間革開モデ ルは唯一でなく複数存在する．そのため，必要な時間展開モデルを求めるために は，りH型レジスタの制御の異なる組合せから生成される時間展開モデルに対し て被覆関係を調べる必要があった．そこで，テスト生成に必要な時間展開モデル が唯一存在し，また時間展開モデルが容易に求まるクラスを示し，それに対する 時間展開モデルの生成アルゴリズムを提案した．また，従来の完全無閉路順序回 路より，さらに低いハードウェアオーバーヘッドで組合せテスト生成が可能であ ることを適用例を用いて示した．今後の課題として，最大展開モデルが存在する 無閉路順序回路の十分条件の緩和と，最大展開モデルを生成するアルゴリズムの 拡張が挙げられる．また，一般の順序回路から，最大展開モデルが存在するよう な無閉路順序回路に変更する部分スキャン設計手法の掟案が挙げられる・ 36 謝辞 本研究の全過程において，絶えず懇切な御教示，御援助を賜わりました藤原秀 雄教授に深く感謝の意を表します． 本研究に際して，有益な御指導を頂きました渡連勝正教授に深く感謝の意を表 します． 本研究に際して，日頃から有益な御指導を頂きました増澤利光助教授に深く感 謝の意を表します． 本研究を進めるにあたって，日頃から様々な面での暖かい御指導，御援助を頂 きました井上智生助手に深く感謝致します． 本研究の全過程を通じ，様々な面でお世話になり，御助言，御協力頂きました 井上美智子助手に深く感謝致します． 最後に，様々な面で御協九御援助頂きました藤原研究室の諸氏に対し深く感 謝致します． 37 参考文献 【1】H．Fujiwara，lo9icleslin9anddesi9nJbrtestability，TheMITPress，1985・ 【2】M．Abram0vici，M・A・BreuerandA・D・Friedman，di9italsyslerTWleslin9 andtestableDesi9n，ComputerSciencePress，1990・ 【3］K．ChengandV・D・Agrawal，“apaRtialscanmethodforsequentialcircuits withfeedback，”1EEEThns・OnComput・）Vol・39INo・4†Pp・544T548，Apri1 【4】D．H．LeeandS・M・Reddy，“Ondeteminingscan且ip−flopsinpartialーSCande− signapproach，”Proc．Inl・ConfComputerT＾idedDesi9n，pP・322−325，Nov・ 【5】井上智生，細川利典，藤原秀雄，“組合せATPGに基づく灯レベル部分ス キャン設計法，”信学技報，FTS96T67，pP・73−80，Feb・1997・ ［6］R・Gupta，R・GuptF，andM・A・Breuer，“theBALLASTmethodologyfor structuredpartialscandesign）n〃退βTねns・Comput・）Vol・39，No・4，pp・538− 544，Apr．1990・ 【7】藤原秀雄，大竹菅史，高崎智也，“組合せテスト生成複雑度でテスト生成可能な 順序回路構造とその応用”電子情報通信学会論文誌（DI），Vol・J80−D−Ⅰ，No・ 2，pp．155−163，Fbb・1997・ ［8］R．G。ptaandM．A．占reuer，“partialscandesignofregister−tranSferlevel circuits，”J仙r花αJイβねc摘花吏c旅β王宮花ダニ恥叩α乃dAppgicαf加5，Vol・7， pp．25−46，1995・ 38 【9］R．GuptaandM．A．Breuer，”testabilitypropertiesofacyclicstructuresand applicationstopartialscandesign）））PrDC・IEEEl几SI7tstSymp・）Pp・49−54， 【10］E．Trischler，“incomplete scan pathwith an automatic test generation methodology，”inProc．qftheIntl・TbstConf，pP・153−162，1980・ 【11］M．AbramOVici，J・JtKulikowski，aJldR・K・Roy，“thebestflipTflopstoscan，“ 盲花P和C．イ亡んe九丑飛β￡C卯げ，pp・166−173，1991・ t12】V．D．Agrawal，K・T・Cheng，D・D・Jolmson，andT・Lin，“designingcircuitswith partialscan，“LEEEDesi9nandTbsl扉Computers・，VOl・5，pP・8−15，Apri1 ［13］H．−K．T．Ma，S．Devadas，A・R・Newton，andA・SangiovanniVincentelli，“an incompletescandesignapproachtotestgenerationfor＄equentialmachines ，“古几P和C．げ鳶ゐe九丑飛βfCbげ，pp・730−734，198臥 ［14】V．ChickermaneandJ・H・Patel，‘‘afault orientedpartialscandesign ap− proach，“inProc．qflheIntl・Co扉onComputer−AidedDesi9n・，pp・40O−403， 【15］P．S．ParikhandM．Abram0vici，“aCOStbased■approachtopartialscan，“in Proc．げ娩eタβ亡んA岬βeβ如A祝わmα土盲0花Co扉，June1993・ 【16］K．T．ChengandV・D・Agrawal，“apartialscanmethodforsequentialcircuits withfeedback，“mEE Thmsaclions on Cbmpulers・，VOl・39，Pp・544−548， April1990・ 【17】S．T．Chakradhar，A．Balakrishman，andV・D・Agrawal，“aneXaCtalgoT rithmforselectingpartialscan鮎p−flops）乃Proc・1EEEDesi9nAutomation Coゆre花Ce，pp．8ト86，1994・ 39