日本大学大学院 生産工学研究科
2014 年度
博士学位申請論文
スキャンテストにおけるコスト及び消費電力削減 のためのテスト生成法に関する研究
学位申請者 山崎 紘史
本論文は日本大学大学院生産工学研究科に博士（工学）授与 の 要件として提出した博士論文である．
山崎 紘史
審査委員： 細川 利典 教授 三井 和男 教授 角田 和彦 教授
井口 幸洋 教授（明治大学）
論 文 要 旨
近 年 ， 半 導 体 の 微 細 化 技 術 の 進 歩 に 伴 い ， 超 大 規 模 集 積 回 路(Very Large Scale Integrated circuits : VLSI)の 集 積 度 が 増 大し て い る ．ま た ， 設 計 自 動 化 技 術の 進 歩 に よ り ， 大 規模 な デ ジ タ ル シ ス テム を VLSI 上 に 実 装 す る こ と が 可 能 と な っ た ．VLSI 回 路 は ， 社 会 に お い て も 幅 広 く 利 用 さ れ て お り ，製 造 さ れ た VLSI に 故 障(物 理 的な 欠 陥)が 無 い こ と を 保 証 し な け れ ば な ら な い ． こ の た め ，VLSI の テ ス ト 設 計 が 非 常 に 重 要 に な っ て お り ， そ の 自 動 化 は 必 要 不 可 欠 に な っ て い る ．VLSI の テ ス ト 設 計 に は テ ス ト 生成(Automatic Test Pattern Generation : ATPG)と テ ス ト 容 易 化 設 計(Design For Testability : DFT)の 2 つ が 挙 げ ら れ る ． テ ス ト 生 成 と は VLSI 製 造 後 の 出 荷 検 査に 用 い る テ ス ト パ ター ン を 生 成 す る こ と を い う．ま た ，テ ス ト 容 易 化 設計 と は テ ス ト パ タ ーン の 生 成 を 容 易 に す る た めに VLSI の 回 路 構 造 を 変更 す る こ と を い う ．
VLSI の テ ス ト で は ， 製 造 さ れ た VLSI に 対 し て テ ス トパ タ ー ン を 外 部 入 力(Primary Input : PI)に 印 加 し ，そ の 出 力 応 答 を 外部 出 力(Primary Output : PO)で 観 測 す る ． こ の と き， 外 部 出 力 の 観 測 値と テ ス ト パ タ ー ン に よ る 出 力 期待 値 を 比 較 す る こ とで VLSI 内 部 の 故障 の 有 無 を 判 定 す る ． そ の た め ， テ ス ト 生 成 で は ，VLSI 内 部 に 欠 陥 を モ デ ル 化 し た 故 障 モ デ ル を 仮 定 し，そ の 故 障 モ デ ル の故 障 影 響 を 外 部 出 力で 観 測 で き る テ ス ト パ タ ー ン を生 成 す る ．こ の と き ，故 障 検 出 効 率 と いう 概 念 を 導 入 し，
出 荷 し た VLSI の 市 場 不 良 率 を で きる だ け 低 減 す る に は， 故 障 検 出 効 率 が 高 い(例 ，99%以 上)テ ス トパ タ ー ン を 用 意 す る 必 要が あ る ．
VLSI の 微 細 化 技 術 の 進 歩 に よ り ，VLSIの 集 積 度 が 増加 し て い る ．ま た ， テ ス ト パ ター ン 数 は ゲ ー ト 数の 0.5 乗 から 1.5 乗 に 比 例 し て 増 加 す る と 報 告 さ れ て い る ．VLSI の 微 細 化 に よ り 従 来 の 縮 退 故 障 モ デ ル の テ ス ト パ タ ー ン では 検 出 困 難 な タ イ ミン グ 遅 延 を 伴 う 欠 陥が 存 在 す る．そ の た め，縮 退 故 障 モ デ ル の テ ス ト パタ ー ン の 他 に 遷 移 故障 モ デ ル や パ ス 遅 延 故 障 モ デ ルな ど の テ ス ト パ タ ーン が 必 要 で あ る．テ ス ト パ タ ー ン 数 の 増 加 に 伴 い テス ト 実 行 時 間 が 増 加し ，テ ス ト コ ス ト の増 大 に つ な が る．
こ の こ と か ら ，VLSI に お け る テ スト 実 行 時 間 の 削 減 が重 要 で あ る ．
一 方 ，VLSI の 低 消 費 電 力 化 設 計 に 伴 い ， 実 速 度 ス キ ャ ン テ ス ト に お け る テ ス ト 時 消費 電 力 の 増 大 が 問 題と な っ て い る．実 速 度 ス キ ャ ン テ ス ト 特 有 の 消 費 電力 と し て ，キ ャ プ チ ャ 時 消 費 電 力 と シ フト 時 消 費 電 力 が 挙 げ ら れ る．キ ャ プ チ ャ 時 消 費 電 力は ，テ ス ト 応 答 を フリ ッ プ フ ロ ッ プ
（Flip-Flop：FF） へ 格 納 す る キ ャ プ チ ャ 動 作 時 に 発 生 す る ． シ フ ト 時 消 費 電 力 は ， スキ ャ ン FF へ の テ ス ト パ タ ー ン の 印 加 とテ ス ト 応 答 の 観 測 を 行 う シ フ ト動 作 時 に 発 生 す る．過 度 な キ ャ プ チ ャ 時消 費 電 力 に よ る 問 題 と し て，電 圧 降 下(IRド ロ ップ)に よ る 誤 テ ス ト が 挙 げ ら れ る．ま た ， 過 度 な シ フ ト 時消 費 電 力 に よ る 問 題と し て ，発熱 に よ る 回 路 の 熱 破 壊 が 挙 げ ら れ る ． そ の た め ，VLSI の テ ス ト 時 消 費 電 力 の 増 大 は 歩 留 ま り 低 下 の 原 因 の 一 つと し て 挙 げ ら れ る．し た が っ て ，歩留 ま り の 損 失 を 抑 制 す る た めに VLSI の テ ス ト 時 消 費 電力 の 削 減 が 重 要 で ある ．
本 研 究 は ，テス ト パ タ ー ン 数 削 減 のた め の ド ン ト ケ ア 判定 法 と ，キ ャ プ チ ャ 時 消 費 電力 削 減 の た め の マ ルチ サ イ ク ル キ ャ プ チャ・テ ス ト 生 成 法 を 提 案 す る ．
本 論 文 は 序 論 およ び 結 論 を 含め 7 つ の 章 か ら 構 成 さ れ る．
第 1 章 は 序 論 で あ る ． 本 研 究 の 目 的 と 意 義 お よ び 背 景 に つ い て 述 べ，
本 論 文 の 概 説 を行 っ て い る ．
第 2 章 で は ，故 障 モ デ ル ，テ ス ト 生 成 ，ス キ ャ ン 設 計 ，スキ ャ ン 設 計 回 路 に お け る 遷 移 故 障 の テ ス ト 方 式 な ど の ，VLSI の テ ス ト に 関 す る 技 術 に つ い て 概 説す る ．
第 3 章 で は ， 相 補 型 金 属 酸 化 膜 半 導体(Complementary Metal Oxide Semiconductor : CMOS)回 路 の 消 費 電 力 と ，VLSI の テ ス ト 時 消 費 電 力 そ の 影 響 と し て，キ ャ プ チ ャ 時 消 費電 力 と シ フ ト 時 消 費電 力 に つ い て ま と め て い る ． また VLSI の 消 費 電力 の 見 積 り 手 法 と し て広 く 用 い ら れ て い る 重 み 付 き 信号 遷 移(Weighted Switching Activity : WSA)に つ い て 概 説 す る ．
第 4 章 で は ，ド ン ト ケ ア ，故 障 シ ミ ュレ ー シ ョ ン ，テ ス ト圧 縮 な ど の ， VLSI の テ ス ト コ ス ト 削 減 に 関 す る 技 術 を 概 説 す る ． テ ス ト 圧 縮 に は ， テ ス ト 生 成 中 にテ ス ト 圧 縮 を 行 う 動的 圧 縮 と ，テ ス ト 生 成 後 の テ ス ト 集 合 に 対 し て テ スト 圧 縮 が 存 在 す る．本 章 で は ，故 障シ ミ ュ レ ー シ ョ ン に
基 づ く 静 的 圧 縮手 法 と ，テス ト パ タ ー ン 中 の ド ン ト ケ アに 基 づ く 静 的 圧 縮 手 法 に つ い て概 説 す る ．
第 5 章 で は ，テ ス ト 圧 縮 を 考 慮 し たド ン ト ケ ア 判 定 法 を提 案 す る ．一 般 に ，生 成 さ れ た テ ス ト パ タ ー ン の各 外 部 入 力 値 は ，全て 0 ま た は 1 の 論 理 値(ケ ア ビ ッ ト)に 設 定 さ れ て い る ． し か し な が ら ， 生 成 さ れ た テ ス ト パ タ ー ン の 中に は ，逆 の値 に 変 更 し て も 故 障 検 出 率 が低 下 し な い 外 部 入 力 値 が 存 在 する ．こ の よ う な 外 部入 力 値 を ド ン ト ケ アと い う ．テ ス ト 集 合 か ら ド ン トケ ア を 判 定 す る 技 術に は ，ド ント ケ ア 判 定 法 が 提 案 さ れ て い る ．
過 去 に 提 案 さ れた ド ン ト ケ ア 判 定 法で は ，テ ス ト集 合 中 の ド ン ト ケ ア の 最 大 化 や，テ ス ト 時 消 費 電 力 の 分野 を 考 慮 し た ド ン トケ ア 判 定 法 が 提 案 さ れ て い る ．
し か し な が ら，過 去 に 提 案 さ れ た ドン ト ケ ア 判 定 法 で は，各 外 部 入 力 に 対 し て は ド ント ケ ア 数 の 均 一 化 を考 慮 し て い な い．そ の た め ，テ ス ト 圧 縮 の 分 野 に おい て ，特 定の 外 部 入 力 に ケ ア ビ ッ ト が 集中 す る と テ ス ト 圧 縮 効 率 が 低 下す る 可 能 性 が 存 在 する ．本 論 文 で は，各 外 部 入 力 の ド ン ト ケ ア 数 を 均 一に し ，ド ント ケ ア 数 を 最 大 化 す る テ ス ト圧 縮 に 効 果 的 な ド ン ト ケ ア 判 定法 を 提 案 し ，ISCAS’89，ITC’99 ベン チ マ ー ク 回 路 に 対 し て 実 験 を 行 った ．
テ ス ト 圧 縮 を 未適 用 な 初 期 テ ス ト 集合 に 対 す る 実 験 結 果で は ，従 来 の ド ン ト ケ ア 判 定 法 と 比 較 し て ， ド ン ト ケ ア 判 定 率 は 平 均 約 1%の 増 加 ， 外 部 入 力 の ド ント ケ ア 分 散 は 平 均約 30%の 削 減 を 達 成 した ．ま た ，テ ス ト 圧 縮 後 の テ スト パ タ ー ン 数 に 関 して は ，従 来の ド ン ト ケ ア 判 定 法 と 比 較 し て ，平 均 約 12%の 削 減 を 達 成 した ．ま た ，テ ス ト 圧 縮 を 適 用 済 みの 初 期 テ ス ト 集 合に 対 す る 実 験 結 果 では ，従 来 の ド ン ト ケア 判 定 法 と 比 較 し て ， ド ン ト ケ ア 判 定 率 は 平 均 約 1%の 増 加 ， 外 部 入 力 の ド ン ト ケ ア 分 散 は 平 均約 10%の 削 減 を 達 成 し た．テ ス ト 圧 縮 後 の テ スト パ タ ー ン 数 に 関 し て は ， 従 来 の ド ン ト ケ ア 判 定 法 と 比 較 し て ， 平 均 約 3%の 削 減 を 達 成 し た ．
第 6 章 で は ，キ ャ プ チ ャ 時 消 費 電 力を 考 慮 し た マ ル チ サイ ク ル キ ャ プ チ ャ・テ ス ト生 成 法 を 提 案 す る ．フ ル ス キ ャ ン 設 計 を した 回 路 で は ，一
般 的 な テ ス ト 生成 は 機 能 動 作 を 考 慮せ ず ，テ スト 生 成 の 容 易 性 を 優 先 し て テ ス ト 生 成 を行 う ．こ の た め，生 成 さ れ た テ ス ト パ ター ン は ，ス キ ャ ン FF の 状 態 が 機 能 動 作 で は 起 こり え な い 状 態(無 効 状 態)と な る 可 能 性 が あ る ． 無 効 状 態 で は ， 回 路 内 の 多 く の 信 号 線 に 遷 移 を 発 生 さ せ WSA を 増 加 さ せ て いる 可 能 性 が あ る ．
一 方 ，過 去 の文 献 に お い て ，一 般的 な テ ス ト 生 成 で 生 成し た 遷 移 故 障 モ デ ル の テ ス トパ タ ー ン を 印 可 し た後 に ， キ ャ プ チ ャ 動作 を 20 サ イ ク ル 行 う こ と で WSA が 減 少 す る こ とが 報 告 さ れ て い る ． ま た ， テ ス ト 生 成 時 に ，時 間 展 開モ デ ル(マ ルチ サ イ ク ル キ ャ プ チ ャ・テ ス ト 生 成 モ デ ル) を 用 い て テ ス ト生 成 を 行 う こ と で，テ ス ト 不 可 能 故 障 を同 定 す る 手 法 も 提 案 さ れ て い る．
本 論 文 で は ，こ の 現 象 に 着 目 し ，キ ャ プ チ ャ 時 消 費 電 力を 考 慮 し た マ ル チ サ イ ク ル キ ャ プ チ ャ ・ テ ス ト 生 成 法 を 提 案 し ，ISCAS’89，ITC’99 ベ ン チ マ ー ク 回路 に 対 し て 実 験 を 行っ た ． 提 案 手 法の 20 時 間 展 開 モ デ ル に お い て WSA 閾 値 50%で は 最大 78%(平 均 45%)，WSA 閾 値 60%で は 最 大 85%(平 均 62%)，WSA 閾 値 70%で は 最大 100%(平 均 72%)，WSA 閾 値80%で は 最 大100%(平 均75%)の ア ン セ ー フ 故 障 数 の 削 減 が で き た．
ま た ，他 の テ ス ト生 成 法 と の 比 較 実験 と し て ，平 均約 22%か ら 40%のア ン セ ー フ 故 障 数の 削 減 が 確 認 で き た．
第 7 章 は 結 論 で あ り ，以 上 の 研 究 成 果 を 述 べ る と と も に ，今 後 の 研究 課 題 に つ い て 議論 し て い る ．
i
関連発表一覧
● 学術論文誌
1. Hiroshi Yamazaki, Motohiro Wakazono,Toshinori Hosokawa and Masayoshi Yoshimura, " A Test Compaction Oriented Don’t Care Identification Method Based on X-bit Distribution," IEICE TRANS.INF. & SYST., VOL.E96-D, NO.9 SEPTEMBER 2013, pp.1994-2002, Sep.2013
● 国際会議（査読付き）
1. Hiroshi Yamazaki, Motohiro Wakazono,Toshinori Hosokawa and Masayoshi Yoshimura, "A Test Compaction Oriented Don’t Care Identification Method," The 12th Workshop on RTL and High Level Testing, pp.69-76, Nov. 2011.
2. Hiroshi Yamazaki, Motohiro Wakazono,Toshinori Hosokawa and Masayoshi
Yoshimura, " A Don’t Care Identification Method for Test Compaction," 2013 IEEE 16th International Symposium on Design and Diagnostics of Electronic Circuits &
Systems, pp.215-218, Apr. 2013.
● 研究会報告
1. 山崎紘史, 細川利典, 吉村正義, “ケアビット分布制御ドントケア抽出 ～ キャプチ ャ消費電力削減への適用 ～,” 信学技報, vol. 111, no. 100, pp. 23-28, 2011年6月.
2. 山崎紘史, 細川利典, 吉村正義, “ケアビット分布制御ドントケア抽出法,” 第 44回日本 大学生産工学部学術講演会, 2011年12月.
3. 山崎紘史, 細川利典, 吉村正義, “テスト圧縮指向ドントケア判定法の解析,” 第 4 回 VLSIテストセミナー, 2012年2月.
4. 山崎紘史, 細川利典, 吉村正義, “ケアビット数を考慮したテスト圧縮指向ドントケア抽 出法,” 第67回FTC研究会, 2012年7月.
5. 山崎紘史, 細川利典, 吉村正義, “テスト圧縮指向ドントケア抽出を用いた静的テスト圧 縮の評価,” 日本大学生産工学部第45回学術講演会, 2012年12月.
6. 川連裕斗，平井淳士，高橋慶安，山崎紘史，細川利典，吉村正義, “マルチサイクルキャ プチャテスト生成を用いた低消費電力指向テスト生成法,” 日本大学生産工学部第46回 学術講演会, 2013年12月.
7. 山崎紘史，川連裕斗，西間木淳，平井淳士，細川利典，吉村正義，山崎浩二, “マルチ
ii
サイクルキャプチャテスト生成を用いた低消費電力指向遷移故障テスト生成法,” 信学 技報, vol. 113, no. 430, pp. 61-66, 2014年2月.
8. 山崎紘史，西間木淳，細川利典，吉村正義，山崎浩二, “マルチサイクルキャプチャテ ストの消費電力評価,” 第71回FTC研究会, 2014年7月.
9. 山崎紘史, 細川利典, 吉村正義, “キャプチャ消費電力削減のためのマルチサイクルキャ プチャテスト生成法,” デザインガイア 2014 -VVLSI 設計の新しい大地-, pp.191-196, 2014年11月.
iii
目次
第1章 序論 ... 1
第2章 VLSIのテストとスキャン設計 ... 5
2.1 VLSIのテスト ... 5
2.2 故障モデル ... 6
2.2.1 縮退故障モデル ... 7
2.2.2 遷移故障モデル ... 8
2.3 テスト生成 ... 10
2.3.1 組合せ回路のテスト生成 ... 10
2.3.2 順序回路のテスト生成 ... 11
2.4 テスト品質評価尺度 ... 15
2.5 スキャン設計 ... 16
2.6 実速度スキャンテスト ... 18
2.6.1 ブロードサイド方式 ... 18
2.6.2 スキュードロード方式 ... 20
第3章 VLSIの消費電力 ... 23
3.1 CMOS論理回路の消費電力 ... 23
3.2 VLSIのテスト時消費電力 ... 26
3.2.1 キャプチャ時消費電力 ... 27
3.2.2 シフト時消費電力 ... 28
3.3 WSA ... 30
第4章 テストコスト削減技術 ... 31
iv
4.1 ドントケア ... 31
4.2 故障シミュレーション ... 32
4.3 テスト圧縮 ... 34
4.3.1 ドントケアに基づくテスト圧縮 ... 34
4.3.1.1 テスト圧縮問題 ... 34
4.3.1.2 頂点彩色問題 ... 38
4.3.2 故障シミュレーションに基づくテスト圧縮 ... 40
4.3.2.1 逆順故障シミュレーション ... 40
4.3.2.2 二重検出法 ... 43
第5章 テスト圧縮を考慮したドントケア判定 ... 47
5.1 緒言 ... 47
5.2 ドントケア判定 ... 48
5.2.1 ドントケア判定問題定式化 ... 48
5.2.2 ドントケア判定アルゴリズム ... 49
5.2.3 故障伝搬経路の決定規則... 51
5.2.4 限定含意操作と限定正当化操作 ... 57
5.2.4.1 限定含意操作 ... 58
5.2.4.2 限定正当化操作 ... 59
5.2.5 見逃し故障 ... 60
5.3 テスト圧縮指向ドントケア判定 ... 63
5.3.1 外部入力のドントケア分散とテスト圧縮 ... 63
5.3.2 テスト圧縮指向ドントケア判定 ... 66
5.3.3 外部入力のドントケア分散とドントケア数のコスト ... 71
5.3.4 実験結果 ... 74
5.4 結言 ... 82
第6章 キャプチャ時消費電力を考慮したマルチサイクルキャプチャ・テスト生成 ... 83
6.1 緒言 ... 83
6.2 マルチサイクルキャプチャ動作とWSA ... 84
6.3 キャプチャ時消費電力を考慮したマルチサイクルキャプチャ・テスト生成 ... 86 6.3.1 キャプチャ時消費電力を考慮したマルチサイクルキャプチャ・テスト生成のテスト
v
生成モデル ... 87
6.3.2 キャプチャ時消費電力を考慮したマルチサイクルキャプチャ・テスト生成アルゴリ ズム ... 89
6.3.3 実験結果 ... 91
6.4 結言 ... 110
第7章 結論 ... 111
謝辞 ... 113
参考文献 ... 114
vi
Study on Test Generation Method
to Reduce Costs and Power Dissipation in Scan Testing
Hiroshi Yamazaki
In recent years, the growing density and complexity of very-large-scale integration circuits (VLSI) has caused an increase in the numbers of test patterns and test power dissipation. Test patterns for not only stuck-at faults but also transition faults are required for VLSI testing. Test cost is generally proportional to the number of test patterns. It is important to reduce the number of test patterns for test cost reduction.
In at-speed scan testing of deep submicron era, high power dissipation can occur when the response to a test pattern is captured by flip-flops, resulting in excessive IR drop, which may cause significant capture-induced yield loss.
A test compaction technique is one to reduce the number of test patterns. A don’t care based test compaction method reduces the number of test patterns by merging a test pattern with other compatible test patterns. Some of specified primary input (PI) and pseudo primary input (PPI) values in a test set may be able to be changed to opposite logic values without losing fault coverage. Such PI and PPI values can be regarded as X-bits. X-identification methods to identify many don’t care inputs of test patterns in a given test set have been proposed. However, conventional X-identification techniques are less effective for application-specific fields such as test compaction because the X-bits concentrate on particular primary inputs and pseudo primary inputs.
Test generation methods for transition faults based on broadside testing have been proposed. It is considered that structural test generation without considering functional operations of VLSI, causes high capture power dissipation in broadside testing. Automatic test pattern generator (ATPG) generally generates test patterns without considering functional operations for full scan circuits. Thus, test patterns generated by ATPG cause transitions on many lines in circuits. On the other hand, it was reported that capture behavior for cycles more than four could drastically reduce capture power dissipation. It is important to generate test patterns with sequential operations fo multi cycles.
This dissertation proposes an X-identification method for test compaction and a test generation method using multi-cycle model to reduce capture power dissipation.
1
第 1 章 序論
近 年 ，半 導 体の 微 細 化 技 術 の 進 歩 に伴 い ，超 大 規 模 集積 回 路(Very Large Scale Integrated circuits : VLSI)の 集 積 度 が 増 大 し て いる ．ま た ，設 計 自 動 化 技 術 の 進 歩に よ り ，大 規 模 な デ ジ タ ル シ ス テ ムを VLSI 上 に 実 装 す る こ と が 可 能 と なっ た ．VLSI 回 路 は ， 社 会 に お い て も 幅広 く 利 用 さ れ て お り ， 製 造 さ れた VLSI に 故 障(物 理 的 な 欠 陥)が 無い こ と を 保 証 し な け れ ば な ら な い ． こ のた め ，VLSI の テ ス ト 設 計 が 非 常 に 重 要に な っ て お り ， そ の 自 動 化 は 必 要不 可 欠 に な っ て い る．VLSI の テス ト 設 計 に は テ ス ト 生 成 [1](Automatic Test Pattern Generation : ATPG)と テ ス ト 容 易 化 設 計 [1](Design For Testability : DFT)の 2 つ が 挙 げ ら れ る． テ ス ト 生 成 と は VLSI 製 造 後 の 出 荷 検 査 に 用 い る テス ト パ タ ー ン を 生 成す る こ と を い う ． ま た ， テ ス ト 容 易 化 設 計 と は テ ス ト パ タ ー ン の 生 成 を 容 易 に す る た め に VLSI の 回 路 構 造 を 変 更 す る こ と を い う ．
VLSI の テ ス ト で は ， 製 造 さ れ た VLSI に 対 し て テ ス トパ タ ー ン を 外 部 入 力(Primary Input : PI)に 印 加 し ， そ の 出 力 応 答 を 外 部 出 力(Primary Output : PO)で 観 測 す る ．こ の と き ， 外 部 出 力 の 観 測 値と テ ス ト パ タ ー ン に よ る 出 力 期 待値 を 比 較 す る こ とで VLSI 内 部 の 故 障 の 有 無 を 判 定 す る ． そ の た め ， テ スト 生 成 で は ，VLSI 内 部 に 欠 陥 を モ デ ル化 し た 故 障 モ デ ル [1]を仮 定 し ，そ の 故 障 モ デ ル の 故 障影 響 を 外 部 出 力 で 観測 で き る テ ス ト パ
2
タ ー ン を 生 成 する ．こ の と き ，故 障 検 出 効 率 と い う 概 念を 導 入 し ，出 荷し た VLSIの 市 場 不 良 率 を で き る だ け低 減 す る に は ，故 障 検 出 効 率 が 高 い(例 ， 99%以 上)テス ト パ タ ー ン を 用 意 する 必 要 が あ る ．
VLSI の 微 細 化 技 術 の 進 歩 に よ り ，VLSIの 集 積 度 が 増 加し て い る ．ま た，
テ ス ト パ タ ー ン数 は ゲ ー ト 数の 0.5 乗 か ら 1.5 乗に 比 例 し て 増 加 す る と 報 告 さ れ て い る[2]．VLSIの 微 細 化 に よ り 従 来 の 縮 退 故 障モ デ ル[1]の テ ス ト パ タ ー ン で は 検 出 困 難 な タ イ ミ ン グ 遅 延 を 伴 う 欠 陥 が 存 在 す る[3][4]． そ の た め ，縮退 故 障 モ デ ル の テ ス ト パタ ー ン の 他 に 遷 移 故障 モ デ ル[1]や パ ス 遅 延 故 障 モ デ ル[1]な ど の テ ス ト パタ ー ン が 必 要 で あ る．テ ス ト パ タ ー ン 数 の 増 加 に 伴 い テ ス ト 実 行 時 間 が 増 加 し ， テ ス ト コ ス ト の 増 大 に つ な が る ． こ の こ と か ら ，VLSIに お け る テ スト 実 行 時 間 の 削 減 が重 要 で あ る ．
一 方 ，VLSI の 低 消 費 電 力 化 設 計 に 伴 い ， 実 速 度 ス キ ャン テ ス ト に お け る テ ス ト 時 消 費電 力 の 増 大 が 問 題 とな っ て い る[5]．実 速 度 ス キ ャ ン テ ス ト 特 有 の 消 費 電 力 と し て ， キ ャ プ チ ャ 時 消 費 電 力[6]と シ フ ト 時 消 費 電 力[6]
が 挙 げ ら れ る．キ ャ プ チ ャ 時 消 費 電力 は ，テ ス ト応 答 を フ リ ッ プ フ ロ ッ プ
（Flip-Flop：FF） へ 格 納 す る キ ャ プ チ ャ 動 作 時 に 発 生 す る ． シ フ ト 時 消 費 電 力 は ， ス キャ ン FF へ の テ ス ト パ タ ー ン の 印 加 とテ ス ト 応 答 の 観 測 を 行 う シ フ ト 動 作時 に 発 生 す る ．過 度 な キ ャ プ チ ャ 時 消 費電 力 に よ る 問 題 と し て ， 電 圧 降 下(IR ド ロ ッ プ)に よ る 誤 テ ス ト[7][8]が 挙 げ ら れ る ． ま た ， 過 度 な シ フ ト 時 消 費 電 力 に よ る 問 題 と し て ， 発 熱 に よ る 回 路 の 熱 破 壊[9]
が 挙 げ ら れ る ．そ の た め ，VLSI の テ ス ト 時 消 費 電 力 の増 大 は 歩 留 ま り 低 下 の 原 因 の 一 つと し て 挙 げ ら れ る．し た が っ て ，歩 留 ま り の 損 失 を 抑 制 す る た めに VLSIの テ ス ト 時 消 費 電 力 の 削 減 が 重 要 で あ る ．
本 研 究 は，テ ス ト パ タ ー ン 数 削 減 の た め の ド ン ト ケ ア 判定 法 と ，キ ャプ チ ャ 時 消 費 電 力削 減 の た め の マ ル チ サ イ ク ル キ ャ プ チ ャ・テ ス ト 生 成 法 を 提 案 す る ．
本 論 文 は 序 論 およ び 結 論 を 含め 7 つ の 章 か ら 構 成 さ れ る．
第 1 章 は 序 論 で あ る ．本 研 究 の 目 的と 意 義 お よ び 背 景 につ い て 述 べ ，本 論 文 の 概 説 を 行っ て い る ．
第 2 章 で は ，故 障 モ デ ル ，テ ス ト 生成 ，ス キ ャ ン 設 計 ，ス キ ャ ン 設 計 回 路 に お け る 遷 移故 障 の テ ス ト 方 式 など の ，VLSI の テ ス ト に 関 す る 技 術 に
3
つ い て 概 説 す る．
第 3 章 で は ， 相 補 型 金 属 酸 化 膜 半 導 体(Complementary Metal Oxide Semiconductor : CMOS)回 路 の 消 費 電 力 と ，VLSI の テ ス ト 時 消 費 電 力 と そ の 影 響 に つ いて ま と め て い る ．ま た VLSI の 消 費 電 力 の 見 積 り 手 法 と し て 広 く 用 い ら れ て い る 重 み 付 き 信 号 遷 移(Weighted Switching Activity : WSA)[10]に つ い て 概 説 す る ．
第 4 章 で は ， ド ン ト ケ ア ， 故 障 シミ ュ レ ー シ ョ ン ， テ ス ト 圧 縮 な ど の，
VLSI の テ ス ト コ ス ト 削 減 に 関 す る技 術 を 概 説 す る ． テス ト 圧 縮 で は ， テ ス ト 生 成 中 に テス ト 圧 縮 を 行 う 動 的圧 縮[11-15]と，テ ス ト 生 成 後 の テ ス ト 集 合 に 対 し て テス ト 圧 縮 を 行 う 静 的圧 縮[11,13,16,17]に つ い て 述 べ る ．
第 5 章 で は ，テ ス ト 圧 縮 を 考 慮 し たド ン ト ケ ア 判 定 法 を提 案 す る ．一 般 に ，生 成 さ れ た テ ス ト パ タ ー ン の 各外 部 入 力 値 は ，全て 0 ま た は 1 の 論 理 値(ケ ア ビ ッ ト)に 設 定 さ れ て い る ． し か し な が ら ， 生 成 さ れ た テ ス ト パ タ ー ン の 中 に は，逆 の 値 に 変 更 し て も故 障 検 出 率[1]が 低 下 し な い 外 部 入 力 値 が 存 在 す る ． こ の よ う な 外 部 入 力 値 を ド ン ト ケ ア(X)と い う ． テ ス ト 集 合 か ら ド ン ト ケ ア を 判 定 す る 技 術 に は ， ド ン ト ケ ア 判 定 法[18]が 提 案 さ れ て い る ． し か し な が ら ， 文 献[18]の ド ン ト ケ ア 判 定 法 は ， 各 テ ス ト パ タ ー ン で 検 出 を 保 証 する 故 障 数 が 異 な る．そ の た め ，ドン ト ケ ア 数 が 少 な い テ ス ト パ タ ー ン が 生成 さ れ る 可 能 性 が ある ．こ の た め，テ ス ト 時 低 消 費 電 力 化 の 分 野 に お い て，ド ン ト ケ ア へ の ケア ビ ッ ト 再 割 当 て の効 果 が ほ と ん ど な い テ ス ト パ タ ー ン が 存 在 す る[19]． こ の 問 題 を 解 決 す る 手 法 と し て ， 各 テ ス ト パ タ ー ン で 検 出 を 保 証 す る 故 障 数 を 均 一 化 す る ド ン ト ケ ア 判 定 法 が 提 案 さ れ て い る[19]． こ の 手 法 に よ り ， 各 テ ス ト パ タ ー ン の ド ン ト ケ ア 数 が 均 一 に な り，テ ス ト 時 低 消 費 電 力 化 に 対 し ，より 効 果 の あ る テ ス ト パ タ ー ン が 生 成 可 能と な っ た[19]．
し か し な が ら ， 文 献[19]の ド ン ト ケ ア 判 定 法 で は ， 各 外 部 入 力 に 対 し て は ド ン ト ケ ア 数の 均 一 化 を 考 慮 し て い な い[20-22]．そ の た め ，テ ス ト 圧縮 の 分 野 に お い て，特 定 の 外 部 入 力 にケ ア ビ ッ ト が 集 中 する と テ ス ト 圧 縮 効 率 が 低 下 す る こ と が 報 告 さ れ て い る[20]． 本 論 文 で は ， 各 外 部 入 力 の ド ン ト ケ ア 数 を 均 一に し ，テ ス ト 圧 縮 に 効 果 的 な ド ン ト ケ ア判 定 法 を 提 案 す る．
ま た ，ISCAS’89，ITC’99 ベ ン チ マ ー ク 回 路 に 対 し て 提案 手 法 の 有 効 性 を
4
評 価 す る ．
第 6 章 で は ，キ ャ プ チ ャ 時 消 費 電 力 を 考 慮 し た マ ル チ サイ ク ル キ ャ プ チ ャ・テ ス ト生 成 法 を 提 案 す る ．フ ル ス キ ャ ン 設 計 を 施 した 回 路 で は ，一般 的 な テ ス ト 生 成 は 機 能 動 作 を 考 慮 せず ，テ ス ト 生 成 の 容易 性 を 優 先 し て テ ス ト 生 成 を 行 う ． こ の た め ， 生 成 さ れ た テ ス ト パ タ ー ン は ， ス キ ャ ン FF の 状 態 が 機 能 動 作 で は 起 こ り え な い 状 態(無 効 状 態)と な る 可 能 性 が あ る ． 無 効 状 態 で は ，回 路 内 の 多 く の 信 号線 に 遷 移 を 発 生 さ せ WSA を 増 加 さ せ て い る 可 能 性 があ る[23][24]．
一 方 ， 文 献[25]で は ， 一 般 的 な テ ス ト 生 成 で 生 成 し た 遷 移 故 障 モ デ ル の テ ス ト パ タ ー ンを 印 可 し た 後 に ， キャ プ チ ャ 動 作を 20 サ イ ク ル 行 う こ と で WSA が 減 少 す る こ と が 報 告 さ れて い る ． ま た ， 文 献[26]で は k(≧2)時 間 展 開 モ デ ル を利 用 し て 遷 移 故 障 を検 出 す る テ ス ト 生 成 法 と し て，マ ル チ サ イ ク ル キ ャ プ チ ャ ・ テ ス ト 生 成 が 提 案 さ れ て い る ． 文 献[26]で は ， 順 序 回 路 的 に テ ス ト 不 可 能 な 故 障 が 数 多 く 同 定 で き る こ と が 報 告 さ れ て い る ． 本 論 文 で は ， 文 献[25]で 報 告 さ れ て い る 現 象 と ， 文 献[26]の テ ス ト 生 成 法 に 着 目 し ， キ ャプ チ ャ 時 消 費 電 力 を考 慮 し た マ ル チ サ イク ル キ ャ プ チ ャ・
テ ス ト 生 成 法 を提 案 す る ． ま た ，ISCAS’89，ITC’99 ベ ン チ マ ー ク 回 路 に 対 し て 提 案 手 法の 有 効 性 を 評 価 す る．
第 7 章 は 結 論 で あ り ，以 上 の 研 究 成果 を 述 べ る と と も に，今 後 の 研 究 課 題 に つ い て 議 論し て い る ．
5
第 2 章
VLSI のテストとスキャン設計
2.1 VLSI のテスト
VLSI の テ ス ト と は ，VLSI の 製 造 時 に 偶 発 的 に 混 入 する 不 良 品 を 選 別 す る た め の 作 業 のこ と で あ る ．VLSI の テ ス ト に は ，VLSI テ ス タ ー と 呼 ば れ る 装 置 を 用 い る．VLSI テ ス タ ー は ， 製 造 さ れ た VLSI の 外 部 入 力 に テ ス ト パ タ ー ン を 印加 し ，外 部 出 力の 応 答 値 を 観 測 す る．こ の と き ，あ ら かじ め 求 め て お い た外 部 出 力 の 期 待 値 と ，VLSI テ スタ ー の 応 答 値 を 比 較 し ， VLSI に 欠 陥 が 存 在 す る か 検 査 を 行う ． こ の と き ， 期 待値 と 応 答 値 が 一 致 し な い 場 合 ， テス ト 対 象 の VLSI に 欠 陥 が 存 在 す る と 判定 で き る ．
6
2.2 故障モデル
製 造 さ れた VLSIの 回 路 内 に は ，断 線 や 短 絡 ，不 純 物 の 混 入 に よ る 抵抗 値 の 増 大 な ど，さ ま ざ ま な 欠 陥 が 生じ る 可 能 性 が あ る．そ の 欠 陥 が 存 在 す る か 否 か を 調 べる た め に テ ス ト を 行う が ，こ れ ら 全 て の 欠 陥 を 直 接 取 り 扱 う こ と は テ ス ト 生 成 時 間 や テ ス ト 実 行 時 間 の 面 か ら 考 え て も 非 現 実 的 で あ る ．そ こで ，欠 陥 を そ の 振 る 舞 いか た に よ っ て 分 類 し，故 障 モ デ ル と し て 表 現 す る こ とが 一 般 的 に 行 わ れ てい る ．こ れ によ り ，異 な る 欠 陥 で も 同 じ 故 障 モ デ ル で 表 現 で き れ ば ， 同 一 の 故 障 と し て 扱 う こ と が 可 能 で あ り ， 扱 う 故 障 の 個 数を 少 な く す る こ と が で き る．故 障 は 論 理 故 障 と タ イ ミ ン グ 故 障 の 二 つ に 分類 で き る ．
論 理 故 障 は，論 理 回 路 の 論 理 機 能 が故 障 に よ り 別 な 論 理機 能 に 変 化 し て し ま う 故 障 で ある ．論 理 故 障 を モ デル 化 し た も の に ，縮 退 故 障 モ デ ル ，ブ リ ッ ジ 故 障 モ デ ル[1]， ト ラ ン ジ ス タ 故 障 モ デ ル[1]，PLA(Programmable Logic Array)故 障 モ デ ル[1]， メ モ リ 故 障 モ デ ル[1]， 機 能 故 障 モ デ ル[1]な ど が あ る．タ イ ミ ン グ 故 障 は，ゲ ー ト の ス イ ッ チ ン グ 時間 や 配 線 の 信 号 伝 搬 時 間 が 増 大 し， 本 来 起 き る は ずの FF の 値 の 変 化 が 規定 の 時 間 内 に 起 こ ら な い 故 障 で ある ．タ イ ミ ン グ 故 障を モ デ ル 化 し た も のに ，遷 移 故 障 モ デ ル ，パ ス 遅 延 故 障 モ デ ル ，ゲ ー ト 遅 延 故 障 モ デ ル[1]な ど が あ る ．VLSI の テ ス ト に は，縮 退 故 障 が 回 路 内 の 一か 所 に 存 在 す る と 仮定 す る 単 一 縮 退 故 障 モ デ ル[1]が 広 く 用 い ら れ て い る．し か し な が ら，近 年 ，単 一 縮 退 故 障 の テ ス ト 集 合 だ けで は 不 良 品 と 判 定 でき な い 欠 陥 VLSI が あ る[3][4]． そ の た め ，市場 不 良 率 を 低 減 す る た め には ，遷 移 故 障 モ デ ルな ど の テ ス ト パ タ ー ン が 必 要 で ある と 報 告 さ れ て い る[3][4]．
本 節 で は，本 論 文 で 取 り 扱 う 縮 退 故障 モ デ ル と 遷 移 故 障モ デ ル に つ い て 説 明 す る ．
7
2.2.1 縮退故障モデル
現 在 ，最も 広 く 用 い ら れ て い る 故 障モ デ ル が 縮 退 故 障 モデ ル で あ る ．縮 退 故 障 モ デ ル は，論 理 ゲ ー ト の 入 力ま た は 出 力 の 信 号 値が 一 定 の 論 理 値 に 固 定 さ れ る 故 障で あ る ． 信 号 線 の 値 が 0 に 固 定 さ れ る 場 合 を 0 縮 退 故 障 (stuck-at-0 : s-a-0)と い い ，1 に 固 定 さ れ る 場 合を 1 縮 退 故 障(stuck-at-1 : s-a-1)と い う ．図 2.2.1(a)に 1 縮 退 故 障 の 例 を ，図 2.2.1(b)に 0 縮 退 故 障の 例 を 示 す ．
図 2.2.1(a)にお い て ，VDD は 電 源 を 示 す ． 図 2.2.1(a)で は 信 号 線 e と VDD(電 源)とが 短 絡 し ，常 に 信 号 線 e の 論 理 値が 1 に 固 定 さ れ る 1 縮 退 故 障 を 示 し て い る． こ こ で ，s-a-1 は 1 縮 退 故 障 を 示 す ．
図 2.2.1(b)に お い て ，GND は グラ ン ド を 示 す ． 図 2.2.1(b)で は 信 号 線 f と GND(グ ラ ン ド)と が 短 絡 し，常 に 信 号 線 f の 論 理 値 が 0 に 固 定 さ れる 0 縮 退 故 障 を 示 して い る ． こ こ で ，s-a-0 は 0 縮 退 故 障 を 示 す ．
a
d
b e
c f
G0
G1
G2
g VDD
短絡 s-a-1
a
d
b e
c f
G0
G1
G2
g
GND
短絡 s-a-0
（a）1 縮 退 故 障 （b）0 縮 退 故 障 図 2.2.1： 縮 退 故 障 の 例
8
2.2.2 遷移故障モデル
遷 移 故 障 モ デ ル は ，あ る 一 つ の 論 理ゲ ー ト の 入 力 ま た は出 力 の 信 号 線 の 伝 搬 遅 延 が 増 大す る 遅 延 故 障 モ デ ルで あ る．遷 移 故 障 モ デ ル に は 立 ち 上 が り 遷 移 故 障(slow-to-rise : STR)と ， 立 ち 下 が り 遷 移 故 障(slow-to-fall : STF)の 2 種 類 に 分 類 で き る ． 立 ち上 が り 遷 移 故 障 は ，あ る 信 号 線 値 が 0 か ら 1 に 遷 移 す る の が 遅 延 す る 故 障で あ る ．立 ち 下 が り遷 移 故 障 は ，あ る 信 号 線 値が 1 か ら 0 に 遷 移 す る の が遅 延 す る 故 障 で あ る ．遷 移 故 障 モ デ ル の 遅 延 は ， 経 路の 長 短 に か か わ らず FF で 観 測 さ れ る ．そ の た め ， 遅 延 が VLSI の 動 作 周 期 よ り 大 き い と 考 え て よ い ．
図 2.2.2 に 立 ち上 り 遷 移 故 障 の 例 を示 す ．図 2.2.2 に おい て ， 信 号線 b の(0,1)は ，1 時 刻 目 の 信 号 線 値 が 0，2 時 刻 目 の 信 号 線値 が 1 を 示 す ． 図 2.2.2 で は ， 信 号 線 c の 立 ち 上 が り 遷 移 故 障 の 例 で あ る． 信 号 線 c で 立 ち 上 が り 遷 移 故 障 が 発 生 し ，FF に 伝 搬 さ れ る 値 が 次 の ク ロ ッ ク の キ ャ プ チ ャ タ イ ミ ン グ に間 に 合 わ ず ， 正 常 値と は 異 な る 1 が 取 り 込 ま れ る ．
クロック Q D
FF
a
b d e
f
G0 c
g
×
G1 (1,1)(0,1)
(0,1)
(U,1)
(1,0)
(1,0) (1,0)
遅延発生
0
1
キャプチャ タイミング
0 1
0
正常時1
故障時
STR
図 2.2.2： 立 ち 上 り 遷 移 故 障 の 例
図 2.2.3 に ， 図 2.2.2 の 回 路 に お け る 立 ち 上 り 遷 移 故 障 の タ イ ミ ン グ チ
9
ャ ー ト 例 を 示 す． 図 2.2.3 は ， 図 2.2.2 の 信 号線 c が 立 ち 上 が り 遷 移 故 障 し て い る 例 で ある ．T は ク ロ ッ ク 周期 を 示 す ．Tgは 正 常 時 の c を 通 過 す る FF 間 ま で の 経 路 の 最 小 伝 搬 時 間 を示 す ．遅 延時 間 が T-Tg を 越 え る 時，遷 移 故 障 が 発 生 する ．
1時刻 2時刻
クロック
正常時 故障時
遷移故障 による遅延
T
T-Tg Tg
信号線cの論理値
図 2.2.3： 立 ち 下 り 遷 移 故 障 の タ イ ミ ン グ チ ャ ー ト
10
2.3 テスト生成
テ ス ト 生 成 は ， 与 え ら れ た 故 障 に 対 し て 冗 長 で あ る か 否 か を 判 定 す る ． 冗 長 で な い 故 障の 場 合，そ の 故 障 の 影 響 を 外 部 出 力 で 観測 可 能 な 外 部 入 力 値 の 組 合 せ を 求め る ．こ の よ う な 外 部 入 力 値 の 組 合 せ をテ ス ト パ タ ー ン と い う ．ま た，テ ス ト パ タ ー ン の 集 合を テ ス ト 集 合 と 呼 ぶ．テ ス ト 生 成 に は 回 路 構 造 に 基 づき 分 枝 限 定 法 で 解 を求 め る 経 路 活 性 化 法[27-31]と ，充 足 可 能 性 問 題(Satisfiability Problem : SAT)を 用 い て 解 を 求 め る 手 法[32-36]
が あ る ．
本 節 で は，2.3.1 で 組 合 せ 回 路 の テ ス ト 生 成，2.3.2 で 順 序 回 路 の テ ス ト 生 成 に つ い て 述べ る ．
2.3.1 組合せ回路のテスト生成
組 合 せ 回 路 の 回路 構 造 に 基 づ く テ スト 生 成 ア ル ゴ リ ズ ムと し て，D ア ル ゴ リ ズ ム[27]，PODEM(Path Oriented Decision Making)ア ル ゴ リ ズ ム [28]，FAN(Fan-out Oriented Test Generaion Algorithm)ア ル ゴ リ ズ ム [29]，SOCRATES[30]，SPIRIT[31]な ど が 提 案 さ れ て いる ．ま た ，充 足 可 能 性 問 題 に 基 づ く テ ス ト 生 成 ア ル ゴ リ ズ ム と し て ，NEMESIS[32][33]， TEGUS[34]，TG-GRASP[35]，PASSAT[36]な ど が 提 案さ れ て い る ．
図 2.3.1 に 組 合 せ 回 路 に 対 す る テ ス ト 生 成 の 例 を 示 す ．図 2.3.1 は ， 信 号 線 a の 0 縮 退 故 障 に 対 す る テ ス ト生 成 例 で あ る．図 2.3.1 に お い て，1/0 は 正 常 値 1， 故 障値 0 を 示 す ． 同 様に 0/1 は 正 常 値 0， 故 障 値 1 を 示 す ． ま ず ，信 号線 a に 故 障 励 起 の た め に 正 常 値 1 を 割 当 て る ．次 に ，信 号線 d に 故 障 影 響 を 伝搬 さ せ る た め に ， 信号 線 b に AND ゲ ー ト の 非 制 御 値 で あ る 1 を 割 当 て る ．さ ら に ，故 障 影 響 を 信 号 線 e に 伝 搬 させ る た め に ，信 号 線 c に 0 を 割 当て る ．す る と 外 部 出 力 e で 故 障 が 検 出 でき る こ と を 確 認 で き る ．図 2.3.1 の 回 路 に お い て ，信 号 線 a の 0 縮 退 故 障 を 検 出 可 能 な テ ス ト パ タ ー ン は(a, b, c) = (1, 1, 0)で あ る こ と が わ か る．ま た ，誤 り が 伝 搬 し た 経 路(パ ス)で あ る a, d, e を 活 性 化 経 路 と 呼 ぶ ．
11
a d
b e
c
×
1/0 G0 1/00
1 G1 0/1
図 2.3.1： 組 合 せ 回 路 に 対 す る テ ス ト 生 成 例
2.3.2 順序回路のテスト生成
ス キ ャ ン 設 計を 用 い な い 順 序 回 路に 対 す る テ ス ト 生 成は ，順 序 回 路 か ら 組 合 せ 回 路 モ デ ル の 一 種 で あ る 時 間 展 開 モ デ ル[1]を 用 い る 手 法 が よ く 利 用 さ れ る．し か し な が ら ，展開 時 間 数 が 大 き い と 回 路 モデ ル の 規 模 が 増 大 す る ．回路 モ デ ル の 規 模 が 増 大 す ると ，テ ス ト 生 成 の 複雑 度 が 増 し 高 い 故 障 検 出 効 率 を 得る こ と が 困 難 と な る．順 序 回 路 の テ ス ト生 成 ア ル ゴ リ ズ ム と し て ， 拡張 D ア ル ゴ リ ズ ム[37]な ど が 提 案 さ れ て いる ．
図 2.3.2 に ， 順 序 回 路 の テ ス ト 生 成 例 を 示 す ． 順 序 回 路の テ ス ト 生 成 ア ル ゴ リ ズ ム は 回路 中 の 組 合 せ 回 路 部を 図 2.3.2 に 示 す よ う に 時 間 軸 に 展 開 し た 時 間 展 開 モデ ル を 生 成 し て 行 う． 図 2.3.2 に お い て 各 回 路 C(i)（ 以 後 セ ル と 呼 ぶ）は ，時 刻 i に 対 応 す る 順 序 回 路 の 組 合 せ 回路 部 に 対 応 し ，X(i) は そ の 時 刻 の 入力 を 表 す ．Y(i), Y(i+1)は そ れ ぞ れ ， 時刻 i, i+1 の FF の 状 態 に 対 応 し て いる ．一 般 に FF の初 期 状 態 は 未 知 で あ るの で ，Y(0) = (U, U, U, …, U)と す る ． こ こ で ，U は 未 知 の 値(不 定 値)を 示 す ． 図 2.3.2 で は ， 時 刻 q に お い て 故 障 箇 所 に 誤 り が 発 生 し ，p 時 刻 後 に 誤 り が 外 部 出 力 Z(q+p)に 伝 搬 す る 例 を 示 し て い る ．
順 序 回 路 の テ スト 生 成 法 の う ち，時 間 展 開 モ デ ル を 利 用し て テ ス ト 系 列 を 生 成 す る 手 順例 は 次 の よ う に な る．
12
Step 1：
p と q に 適 当 な 非 負 の 整 数 を 選 ぶ ．最 初 は p=q=0 とお く ．
Step 2：
q 番 目 の セル C(q)に お い て，故 障 箇 所 の 正 常 値 と 故 障 値が 異 な る よ う な 入 力 パ タ ーン X(q)と Y(q)を 求 め る ．
Step 3：
故 障 の 影 響 を q+p 番 目 の セ ル の 出 力 Z(q+p)にま で 伝 搬 さ せ る ． 伝 搬 で き な け れば p を 1 つ 増 加 し て 繰 り 返す ．伝 搬 に 成 功 し た場 合 は ，入 力 X(q), X(q+1), …, X(q+p)お よ び Y (q), Y (q+1), …, Y (q+p)の値 を 決 定 す る ．こ れ ら の 値 を 決 定 する 際 に 何 ら か の 矛 盾が 発 生 し ，値の 決 定 に 失 敗 し た ら，再 び q 番 目 の セ ル に お い て 別 の X(q)と Y(q)を 求 め る．
Step 4：
Y(q)が 求 め ら れ た 値 を と り ，かつ 初 期 状 態 が 任 意 状 態，す な わ ち Y(0) = (U,U,U,…,U)に な る よ う に ，X (0), X (1), …, X (q-1)の 値 を 求 め る ．求 めら れ な い 場 合 ，q の 値 を 1 つ 増 し ， 繰 り 返 す ．
Step 4 で 注 意す べ き 点 は ，故 障 は 単 一 故 障 で あ っ て も 時間 展 開 し た 回 路 で は 多 重 故 障 にな る こ と で あ る ．
C(0) C(q-1) C(q) C(q+p)
X(0) X(q-1) X(q) X(q+p)
Z(0) Z(q-1) Z(q) Z(q+p)
Y(q+1) Y(q)
Y(q-1) Y(0)=
(U,U,・・・,U)
図 2.3.2： 順 序 回 路 の 時 間 展 開 と テ ス ト 系 列
13
図 2.3.3 に 順 序 回 路 の 例 を 示 す．図 2.3.4 と 図 2.3.5 に，図 2.3.3 の 順 序 回 路 の 信 号線 d に 1 縮 退 故 障 を 仮 定し て ，時 間 展 開 モ デ ル を 用 い て テ ス ト 生 成 を し た 例 を示 す ．図 2.3.4 は p=q=1 の 例 で あ り，図 2.3.5 は p=1, q=2 の 例 で あ る ．
D
D
a
d b
Q
Q
z e
k
f
j
i h
g c
クロック
G3 G1
G2
FF1
FF2
図 2.3.3： 順 序 回 路 例
ま ず，p=0, q=1 と お き，d の 1 縮 退 故 障 を 検 出 す る テ ス ト パ タ ー ン を 求 め る ． セ ル C(1)に お け る 信 号 線 d1の 値 を 0/1 と す る ． セ ル C(1)の 外部出 力 z1に 故 障 影 響 を 伝 搬 す る こ と が出 来 な い の で，p=1 と 増 や す．こ の 時 の 時 間 展 開 モ デ ルの 回 路 図 は ， 図 2.3.4 と な る ． 図 2.3.4 で は ， セル C(1)の 信 号 線 d1の 故 障 値 0/1 がセ ル C(2)へ 伝 搬 し て ， 外 部出 力 z2に伝搬 する．
こ の と き ，入 力 は a1=1，a2=1 で ，内 部 状 態 は g0=h0=0 で あ る ．h0=0 と す る た め に は，セ ル C(0)の OR ゲ ー ト G3 の 入 力 信 号線 f0と i0を 両 方 とも 0 に 割 当 て る 必 要が あ る ． し た が っ て，j0=0 とな り ，j0=U と で き な い ． そ こ で ，q を 1 つ 増 加 さ せ q=2 と す る ． こ の 場 合 の 時間 展 開 モ デ ル 例 を 図 2.3.5 に 示 す ．
