論 文
時間展開モデ ルを用いた無閉路順序回路のテスト 系列圧縮方法
細川 利典
†井上 智生
††平岡 敏洋
†∗藤原 秀雄
††Test Sequence Compaction Methods for Acyclic Sequential Circuits Using a Time
Expansion Model
Toshinori HOSOKAWA†, Tomoo INOUE††, Toshihiro HIRAOKA†∗, and Hideo FUJIWARA††
あらまし 無閉路順序回路に 対するテスト 系列は ，時間展開モデルを用いて 生成することができる．本論文で は ，時間展開モデルを用いて 生成され るテ スト 系列は（1）テスト系列長が一定である，（2）各外部入力に対する 未定義値(X) が存在する位置がテスト生成の対象故障とは無関係に決まる，という性質に着目し，静的圧縮，動 的圧縮の二つのテ スト 系列圧縮方法を提案する．まず，テスト 系列の値に 依存し ないテンプレ ート を用いた 静的 テ スト 系列圧縮方法を提案する．また圧縮後のテ スト 系列を逆変換し たテ スト パターンで ，時間展開モデルに 対 し て 故障シ ミュレ ーシ ョン を 実行する逆変換故障シ ミュレ ーシ ョンに よる動的テ スト 系列圧縮方法を 提案する． いくつか の実際の回路にパーシャル スキャン 設計を適用し て作成し た無閉路順序回路で本提案方法を評価し た結 果，テ スト 系列長を19∼34％に削減することができた．
キーワード 時間展開モデル ，無閉路順序回路，テスト 系列圧縮，テンプレ ート，逆変換故障シ ミュレ ーション
1. ま え がき
近年のLSIの大規模化，複雑化により，LSIのテ ス ト 設計の 自動化が 必要不可欠となっている．LSIのテ スト 設計のコストを考えた場合，
（1）高い故障検出効率（ 例，95％以上 ）を達成す るテ スト 系列を生成する時間
（2）高い故障検出効率を達成するテ スト 系列の長 さ，すなわちLSIテ スタでのテスト 時間
の2点を挙げ ることができる．
一般の順序回路に 対し て現実的な時間で 高い故障検 出効率を 達成することは 非常に 困難なので ，（1）に 関 す るテ スト 設 計コ スト を 削 減す るた めに は ，フル ス キャン 設計[1], [2]や パーシャル スキャン 設計[3]∼[9] に 代 表 され るテ スト 容 易 化 設 計が 必 要で あ る ．パー シャル スキャン 設計では 回路中のど のフ リップ フロッ
†
松下電器産業株式会社半導体開発本部，守口市
Corporate Semiconductor Development Division, Mat- sushita Electric Industrial Co., Ltd., 3–1–1 Yagumo- Nakamachi, Moriguchi-shi, 570–8501 Japan
††
奈良先端科学技術大学院大学情報科学研究科 ，生駒市
Graduate School of Information Science, Nara Institute of Science and Technology, 8916–5 Takayama-cho, Ikoma-shi, 630–0101 Japan
∗
現在，京都大学大学院情報学研究科
プ（FF）をスキャンFFに置き換えるかということが 重要な問題である．無閉路順序回路は 組合せテスト 生 成アルゴ リズムでテ スト 生成可能であることが 知られ ている[6]∼[9]．し たがって核回路（ スキャンFFを取 り除いた回路 ）が 無閉路順序回路にな るように スキャ ンFFを 選択する[6]∼[9]ことで ，フル スキャン 設計 に 比べて小さいハード ウェアオーバヘッド で 高い故障 検出効率を 得ることが で き る．特に 文献[9]では ，時 間展開モデルを用いた 無閉路順序回路のテ スト 系列生 成方法が 提案され いる．
また ，（2）に 関するテ スト 設計コ スト を 削減する解 決策とし て ，テスト パターンの圧縮技術がある．
このテ スト パターン 圧縮技術に 関し て近年数多くの 論文[10]∼[19]が 発 表され て い る．文献[10]∼[13]は 組合せ 回路を 対象にし たテ スト パターン 圧縮の方 法 ， 文献[14]∼[19]は 順序回路を 対象にし たテ スト 系列圧 縮の方法を提案し ている．
本論文では ，文献[9]で 提案され た 時間展開モデ ル を用いて 得られたテ スト 系列を圧縮する方法を提案す る．時間展開モデルを用いて得られるテスト 系列には ， 生成され たテスト 系列の値に依存し ない規則があるこ とに 着目し ，次の二つの 圧縮方法を提案する．
（1）静的圧縮方法
D– Vol. J82–D– No. 7 pp. 869–878 1999 7 869
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
時間展開モデルに対する基本テンプレ ートを作成し ， テ スト 系列長を最小にするテンプレ ート を求め，その テンプレ ート を用いる静的圧縮方法
（2）動的圧縮方法
静的圧縮後に 得られ るテ スト 系列から ，まだ 故障シ ミュレ ーシ ョンが 行われていないテ スト 系列を時間展 開モデ ルのテスト パターン とし て抽出する逆変換故障 シ ミュレ ーションによる動的圧縮方法．
本論文は次のような構成になっている．まず，2. で 時間展開モデルを用いた 無閉路順序回路のテ スト 系列 生成方法について述べる．3. では ，テンプレ ートを用 いた 無閉路順序回路の静的なテスト 系列圧縮方法につ いて述べる．また4. では ，逆変換故障シミュレ ーショ ンによる動的圧縮方法について述べる．5. では ，実際 の回路を 用いた 実験結果を示し ，その考察を 行う．6. では ，本論文のまとめと今後の課題について述べる．
2. 時間展開モデルを用いた無閉路順序回路 のテスト 系列生成方法
2. 1 テスト 生成
時間展開モデ ルを用いた 無閉路順序回路のテスト 系 列生成方法[9]について ，例を用いて説明する．図1は 無閉路順序回路Sの例を示す．図1において ，FF1∼ FF11はFF，1∼9は組合せ論理部，PI1∼PI3は外部
入力，POは外部出力を示す．
図2は 図1の無閉路順序回路Sの 時間展開モデ ル C(S)を示す．時間展開モデ ルC(S)はSの各外部出
図1 無閉路順序回路S Fig. 1 Acyclic sequential circuit: S.
図2 S の時間展開モデル：C(S) Fig. 2 Time expansion model of S: C(S).
力から 外部入力まで ，入力方向に 組合せ論理部を展開 し た 組合せ 回路である ．C(S)の 組合せ 論理部，外部 入 力 ，外部 出 力は ラベ ルt を もつ ．時 間 展 開モデ ル C(S)に おいて ，ラベルtの 組合せ 論理部aから ラベ
ル t + 1の 組合せ 論 理部bにデ ータが 入 力され て い るときには ，対応する無閉路順序回路Sにおいて 組合 せ 論理部aからのデ ータが 一つのFFを 通過し て ，1 時刻遅れて組合せ論理部bに 到着することを表し てい る．図2において，時間展開モデルC(S)の上部に書 かれている数は ，その 列に 存在する組合せ論理部，外 部入力，外部出力のラベルを表す．また ，組合せ論理 部の黒塗りの部分は ，外部出力又は 他の組合せ論理部 の入力のいずれにも到達不可能である信号線又は 論理 ゲ ート を表し ，時間展開モデルから 除去され ている． 無閉路順序回路Sの故障faに 対応する時間展開モ デ ル C(S)の故障feは ，故障faの存在する組合せ 論理部と対応するC(S)の各組合せ論理部の同じ 位置
（ 信号線 ）に 存在する一つの 多重故障となる．例えば ， 図1の無 閉路順序回路Sの 組合せ論 理部3中の 故障 は ，図2の時間展開モデルC(S)に示すように組合せ 論理部3が 二つ存在するので ，時間展開モデ ルC(S) では 一つの2重故障とし て扱う．ここで ，無閉路順序 回路Sの故障集合をFa, Faに 対応する時間展開モデ ルC(S)の故障集合を Fe とし たとき，以下のことが 成り立つ[9]．
（1）無閉路順序回路Sの 任意の 故障fa∈ Fa に ついて ，fa に 対応する時間展開モデ ルC(S)の故 障 fe∈ Feがただ 一つ存在する．
（2）故障fa ∈ Fa に 対す るテ スト 系列が 存在す るとき ，か つそのときに 限り，故障faに 対応する故 障fe∈ Feに 対するテ スト パターンが 存在する．
（3）故障fe∈ Feに対するテ ストパターンは ，対 応する故障faに 対するテ スト 系列に変換可能である．
すなわち，時間展開モデ ルC(S)の故障に 対し て生 成し たテ スト パターンは 無閉路順序回路Sのテスト 系 列に 変換可能で ，その 変換し たテ スト 系列で 対応する 無閉路順序回路の故障を検出することができる．よっ て ，時間展開モデルC(S)に 対し て組合せテ スト 生成
（ 多重故障対応 ）を 適用し ，テ スト パターン を 生成す ることができる．その 後で ，時間展開モデ ルC(S)で 生成し たテ スト パターンをC(S)の各外部入力の存在 するラベルの値を参照し て ，無閉路順序回路Sのテス ト 系列に 変換する．
図2の時間展開モデルC(S)のある故障に対して生
表1 S のテスト系列 Table 1 Test sequences for S. (a) Test sequence T1
Time
（ 時刻 ） P I1 P I2 P I3
0 0 1 0
1 1 X X
2 X X X
3 X X X
4 X 1 X
5 X X 0
6 X X X
(b) Test sequence T2 Time
（ 時刻 ） P I1 P I2 P I3
0 0 0 1
1 1 X X
2 X X X
3 X X X
4 X 0 X
5 X X 1
6 X X X
成されたテストパターンを(P I1(0), P I2(0), P I3(0), P I1(1), P I2(4), P I3(5)) = (0, 1, 0, 1, 1, 0)とする
と（P Ii(t): ラベルtに 存在する外部入力P Iiの値 ）， 回路Sにおけ る時刻0のPI1の値は0，時刻0のPI2 の値は1，時刻0のPI3の値は0，時刻1のPI1の値 は1，時刻4のPI2の 値は1，時刻5のPI3の 値は0 となり，無閉路順序回路Sのテ スト 系列は 表1 (a)に 示され るテ スト 系列に 変換され る．
2. 2 圧 縮
時間展開モデルC(S)で 生成された二つのテ スト パ ターンt1 = (0, 1, 0, 1, 1, 0), t2 = (0, 0, 1, 1, 0, 1) を無閉路順序回路Sのテ スト 系列に変換し た二つのテ スト 系列をそれぞれT1, T2とする．テスト 系列T1を 表1 (a)に ，テ スト 系列 T2 を 表1 (b)に 示す．テ ス ト 系列T1中に未定義(X)の部分が 存在するので，テ スト 系列T2 はテ スト 系列T1 の 時刻2から 入力でき る．し たが って ，表2に 示すようにテ スト 系列T1と T2を圧縮し たテスト 系列T を生成することができる．
また ，テ スト 系列T1, T2 に 示すよ うに ，テ スト 系 列において0又は1に値が 決定し ている箇所とX で ある箇所は ，すべてのテスト 系列について一定である． この 情報から 複数のテ スト 系列が 圧縮可能か 否かは ， テ スト 系列中の値に 関係なく決定できる．よって，テ スト 系列が 生成され る前の段階で ，静的に 圧縮方法が 決定でき，圧縮時に 高速にテスト 系列を圧縮すること がで きる ．この静的圧縮方法に ついては 次の3. で 述 べる．
表2に 示すテ スト 系 列T に 着 目す ると ，まだ X の部分が 残っているので ，表 3に 示すよ うに ，X の 部分に 対し てランダ ムに 0又は 1の 値を 設定し たテ スト 系列T′を生成する．このT′において ，例えば ， 時刻1から時刻7のテスト 系列に 着目すると ，テ スト 系列T1, T2とは 別のテスト 系列であることがわか る． こ の テ スト 系列を 無閉 路順 序 回路Sに 対し て 故 障シ
表2 圧縮され た テスト 系列：T Table 2 Compacted test
sequence: T . Time
（ 時刻 ） P I1 P I2 P I3
0 0 1 0
1 1 X X
2 0 0 1
3 1 X X
4 X 1 X
5 X X 0
6 X 0 X
7 X X 1
8 X X X
表3 Xに0，1 を設定した テスト 系列：T′ Table 3Test sequence after
setting 0 or 1 to Xs in T : T′.
Time
（ 時刻 ） P I1 P I2 P I3
0 0 1 0
1 1 0 1
2 0 0 1
3 1 1 0
4 0 1 0
5 1 0 0
6 0 0 0
7 1 1 1
8 0 0 1
ミュレ ーシ ョンを実行すれば ，新たに 未検出故障を検 出できる可能性がある．また，そのテ スト 系列を時間 展開モデ ル C(S)のテ スト パターン に 逆変換すると ， (P I1(0), P I2(0), P I3(0), P I1(1), P I2(4), P I3(5)
= (1, 0, 1, 0, 0, 0)になり，このテ スト パターンで 時
間展開モデルC(S)に 対し て，故障シミュレ ーション を実行することもできる．時間展開モデ ルC(S)は組 合せ回路なので ，故障シ ミュレ ーシ ョンの実行速度は 無閉路順序回路Sに 比べて速くなる．この逆変換故障 シ ミュレ ーション に よ る 動 的 圧 縮 方 法に ついて は4. において 述べる．
3. テンプレ ート を用いた無閉路順序回路の 静的テスト 系列圧縮方法
本章では ，テンプレ ート を用いた 無閉路順序回路の テ スト 系列の圧縮方法について 述べる．
3. 1 諸 定 義
まず，無閉路順序回路のテ スト 系列圧縮方法を説明 するために 必要な用語を定義する．
［ 定義1］（ テンプ レ ート ） 外部入力(P0, P1, . . . , Pw−1)をもつ回路に対するテスト系列T を考える（w
は 外部入力数 ）．T のテ スト 系列長をlとする．T の 時刻tに おけ る外部入力Piの 値をT (t, i)と 表記す る ．テ スト 系列T に おけ るT (t, i) = 0又は 1を 満 たすすべての値(0 <= t < l, 0 <= i < w)をbに置き換 えてできるテ スト 系列T
′
を，テスト 系列T のテンプ レ ート という．また，X又はbからなるテ スト 系列を 単にテンプレ ート という．また，T′のテスト 系列長を テンプレ ート の長さ又はテンプレ ート 長といい，（ テン プレ ートT
′
中に bが 存在する最大時刻 ）−（bが 存 在する最小時刻 ）+1をテンプレ ート T
′
の 有効長と
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
表4 演 算∩c
Table 4 Operation ∩c.
∩c b X
b φ b
X b X
図3 スキュー2 で圧縮可能な例
Fig. 3Example that T is compatible with skew 2.
いう． ✷
［ 定義2］（ 圧縮可能 ） 外部入力(P0, P1, . . . , Pw−1) をもつ回路に 対する二つのテンプレ ート T1, T2 を 考 え る（wは 外部入力数 ）．T1, T2 のテンプレ ート 長を それぞれl1, l2とする．T1, T2の時刻tにおけ る外部 入力Piの値をそれぞれT1(t, i), T2(t, i)と表記する． 任意の i(0 <= i < w)に ついて ，次の二つの 条件の う ちいずれかを満たす非負の整数kが 存在するとき，T2 はT1 に スキューkで 圧縮可能であるという．
（1）k >= l1
（2）k <= t < min{l1, k + l2}となる任意のtにつ いて ，T1(t, i) = X，又は ，T2(t − k, i) = X となる．
また，T1 = T2のとき ，T1(T2)は スキューkで 圧
縮可能であるという． ✷
T2はT1に スキューkで圧縮可能であるときに ，実
際に 圧縮し て 生成され るテンプレ ートT は 表4に 示 す演算∩cを用いると ，任意の i(0 <= i < w)に つい て ，以下の式で 表すことができる．
T (t, i) =
T1(t, i) 0 <= t < min{l1, k}, k + l2<= t < l1
T1(t, i) ∩cT2(t − k, i)
k <= t < min{l1, k + l2} X l1<= t < k
T2(t − k, i) max{l1, k} <= t < k + l2
例1：図3はT が スキュー2で圧縮可能であるとき に ，圧縮し て生成し たテンプレ ート T′を示し ている．
［ 定義3］（ 基本テンプレ ート ）無閉路順序回路をS, Sの時間展開モデ ルをC(S), C(S)に 対し て得られた テ ストパターンをtとする．ただし ，テスト パターン
表5 図2 の基本テンプレート Table 5 Primitive template for Fig. 2.
Time
（ 時刻 ） PI1 PI2 PI3
0 b b b
1 b X X
2 X X X
3 X X X
4 X b X
5 X X b
6 X X X
tには 未定義を 表すX は 含まれ ないもの と する ．こ
のとき ，テ スト パターン tをSのテ スト 系列T に 変 換し ，テスト 系列T のテンプレ ート をT′とする．こ のテンプレ ート T′を時間展開モデ ルC(S)に 対する
基本テンプレ ート という． ✷
例2：図2の時間展開モデルの基本テンプレ ート を 表5に 示す．
3. 2 問題の定式化
時間展開モデルC(S)で 生成され るすべてのテスト パターン 数をn と すると ，n 個のテ スト パターン を それぞれ 無閉路順序回路Sのテ スト 系列に 変換し ，n 個のテ スト 系列を圧縮し て ，全体のテ スト 系列長を最 小化することが ，理想的な目標である．しかし ながら ， n個のテ スト 系列を圧縮し て ，全体のテ スト 系列長を
最小にすることは ，計算量が 膨大となるために困難で あると考えられ る．
そこで 本節では ，あ る一定長のテンプ レ ート 中に ， 最 大 個の 基 本テン プ レ ート を 圧 縮し て ，か つテン プ レ ート の有効長を最小にする部分問題を解き，全体の テ スト 系 列 長を 短 縮す る ．こ の 部 分 問 題を 解 く 圧 縮 方法は4. で 述べ る動的圧縮方法と 組み合わせ ること ができ，更に圧縮が 可能となる．ある一定長のテンプ レ ート 中に ，最大個の 基 本テンプ レ ート を 圧縮し て ， か つテンプ レ ート の 有 効 長を 最 小に す る 最 適 化 問 題 の定式化を行う．この定式化を行う前に ，基本テンプ レ ートが スキューkで圧縮可能であることを表現する 圧縮可能グ ラフを以下に 定義する．
［ 定義4］（ 圧縮可能グ ラフ ）圧縮可能グ ラフは無向 グ ラフ G = (V, E, t)で あり，頂点v ∈ V は ，基本 テンプレ ート を表し ，各頂点にはラベル t : V → Z+
（Z+は 非負の 整数を 表す ）が 付けられ てい る．また
∀u, v ∈ V (u |= v)においてt(u) |= t(v)が 成り立つ． 辺(u, v) ∈ E は ，基本テンプレ ート は スキュー|t(u)
− t(v)|で 圧縮可能であることを表す． ✷
圧縮可能グ ラフから クリーク（ 部分完全グ ラフ ）を
形成する頂点の集合を取り出し ，頂点の個数の基本テ ンプレ ート を各頂点のラベル tの値を スキューとし て 圧縮を 行い ，圧縮に 用いるテンプ レ ート を 生成する ． このとき，できるだけ 数多くの頂点を取り出せば ，圧 縮効率の高いテンプレ ート になる．このことは以下の 最大クリーク（ 頂点数が 最大であるクリーク ）抽出問 題[20]とし てとらえ ることができる．
［ 最大クリーク抽出問題 ］
入力：圧縮可能グ ラフG(V, E, t)
出力：クリークサイズ|C|が 最大となるCの うち，
| max t(v) − min t(u)|が 最小と な るク リーク C．た
だし ，v, u ∈ C かつv |= uで ，max t(v)は 最大のラ ベル 値，min t(u)は 最小のラベル 値である．
例3：図4に 示す圧縮可能グ ラフのクリークについ て考察する．基本テンプレ ートは表6に示す．図4に おいて ，三つのク リークC1, C2, C3を考えてみる．
C1 = {0, 1, 7}, C2 = {0, 1, 2}, C3 = {0, 1}で あ
る．C1とC2は 最大ク リークであ る．C1からテン プ レ ート を 生 成 す る ．三つの 基 本テン プ レ ート を ス キュー 1, 7で 圧縮す ることに より 生 成され るテンプ レ ート の 有効長は13とな る．ここで ，時間展開モデ ルで 生成され る総テ スト パターン 数を n 個と すると き，C1から 生成し たテンプレ ート を用いて圧縮を行 うと，無閉路順序回路の全体のテスト 系列長は13n/3 となる．同様にし て ，クリークC2, C3から 得られ る テンプレ ート の有効長は それぞれ 8, 7となり，また ，
図4 表6 の圧縮可能グラフ Fig. 4 Compatibility graph for Table 6.
表6 基本テンプレ ート Table 6 Primitive template.
Time
（ 時刻 ） PI1 PI2 PI3
0 b b b
1 X X X
2 X X X
3 X b X
4 b X X
5 X X b
全体のテ スト 系列長はそれぞれ8n/3, 7n/2となる． C1とC2のそれぞれの無閉路順序回路におけ るテ
スト 系列長を 比較すると ，C2がC1よりも短いこと がわか る．このことは ，|最大ラベル値−最小ラベル 値|の比較において，C1が|7 − 0|, C2が|2 − 0|と なることから 明らかである．また ，C2とC3を比較 し た 場合，C2の方が 無閉路順序回路の 全体のテ スト 系列長が 短いこ とが わか る．よって ，|最大ラベル 値
−最小ラベル値|が 最小となる最大クリークを求める
と ，圧縮効率の高いテンプレ ートが 生成できることが わか る．
3. 3 ヒューリステ ィックアルゴ リズ ム
本節では ，圧縮に 用いるためのテンプレ ート を生成 するヒューリスティックアルゴ リズムについて 述べる． 圧縮可能グ ラフから 最大クリークを抽出するヒューリ ステ ィックとし て ，圧縮可能グ ラフの辺(u, v)に 対し て 以 下の よ うにし て 求められ る 重み w(u, v)を 付け ることに する ．頂点u, vの 隣接頂点集合を nbr(u), nbr(v)とし ，nbr(u) − v, nbr(v) − uをそれぞれA, B
とする．そし て ，|A ∪ B| − |A ∩ B|を 重み w(u, v) とする．この重みが 表す数字は ，頂点u, vをクリーク に加えたときに ，頂点u, vの隣接頂点の中で ，クリー クに加え ることができな くなる隣接頂点の数になる． 図5に 与えられ た 圧縮可能グ ラフから 最大ク リー クを抽出するヒューリスティックアルゴ リズムを示す． 図5の関数Extract max cliqueで 説明すると ，まず 0のラベルが 付いた 頂点vを ク リークの 頂点集合C に 初期値とし て 加え る．次に C に 含まれ る各頂点u
図5 テンプレート生成ヒューリスティックアルゴ リズム Fig. 5 Heuristic algorithm of a template generation.
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
の 隣 接頂点集合の積 集合を 求め ，それ を 新たに S と する（ 関数Candidates）．Sがφ（ 空集合 ）になるま で ，S の 探 索と S の 中か ら 一つの 頂 点vを 選択し ， Cに挿入する処理を繰り返す．この「S の中から一つ
の頂点vを選択する 」ときには ，候補となる頂点の集 合S の各頂点vに ついて ，以下の（1）から（3）の 三つの 評価尺度を求め ，ただ一つの頂点を選択できる まで（1）から優先的に用いる．すなわち，（1）を満た す頂 点が ただ 一つ存 在す るならば その 頂 点を 選択し ， 複数あるならば その 中で（2）を 満た す頂点を 選択す る．更に（2）を満たす頂点が 複数あるならば ，その中 で（3）を満たす頂点を選択する（ 関数Best vertex）．
（1）頂点vとクリークの頂点集合Cにあるすべ ての頂点 uとの 間にあ る辺(v, u)に 付けられ た 重み w(v, u)の 総和が 最も小さい頂点を 選択する（ 頂点集
合V 1）．重みの 総和が 最小と な る頂点を 選択す るこ とで ，Cに 加えられ る可能性が ある頂点数が 増加し ， 結果とし て最終的に 得られ るCの頂点数が 多くなる． すなわちテンプレ ート に 圧縮され る基本テンプレ ート 数が 多くなる可能性がある．
（2）頂点集合V 1において ，隣接頂点数が 最も多 い頂点を選択する（ 頂点集合V 2）．
隣接頂点数が 最大の頂点をCに 加え ることで ，（1） と同様にテンプレ ート に 圧縮され る基本テンプレ ート 数が 多くなる可能性がある．
（3）頂点集合V 2において，ラベルtが 最小とな る頂点を選択する（ 頂点集合V3）．
ラベ ル tが 最 小と な る頂 点を 選 択す るこ とで ，生 成され るテンプレ ート の有効長を短くできる可能性が ある．
以上の 手順に 従って ク リークCを 抽出し た 後 ，C に含まれ る頂点数の基本テンプレ ート を，Cに含まれ る頂点の各ラベル 値をスキューとし て圧縮することで ， 無閉路順序回路の圧縮に 用いるテンプレ ート を生成す る．ATPG時には ，生成し たテンプレ ート を繰り返し 使用する．また，テンプレ ートは 一つ前に 使用し たテ ンプレ ート の有効長の時刻から 重ねて置くことが 可能 である．
例4：表5の基本テンプレ ート を スキュー9まで 考 慮に 入れ た 圧縮可能グ ラフ（ 頂点数10）を 図6に 示 す．また ，図6の 圧 縮可能グ ラフに ついて ，図5に 示し たヒューリステ ィックアルゴ リズムを 用いて 求め た ク リークは {0, 3, 6, 9}となり，図7に 示すテンプ レ ートが圧縮に用いるテンプレ ート として生成される．
図6 表5 の圧縮可能グラフ Fig. 6 Compatibility graph for Table 5.
図7 図6 から求めたテンプレート Fig. 7 Template generated from Fig. 6.
4. 逆変換故障シ ミュレ ーシ ョンによる無閉 路順序回路の動的圧縮方法
図8に ，テンプレ ート を用いた静的テ スト 系列圧縮 方法と逆変換故障シ ミュレ ーションによる動的テスト 系列圧縮方法を含んだ 無閉路順序回路のテ スト 系列生 成アルゴ リズムを示す．
まず，与え られ た 無 閉 路 順 序 回 路Sの 時 間 展 開モ デルを生成する．続いて ，圧縮可能グ ラフからテンプ レ ート を生成する．テンプレ ート はN 個の 基本テン プレ ート を圧縮し て生成され たとする．つまり，時間 展開モデ ル 上で 生成され たN 個のテスト パターンは ， テンプ レ ート を 参 照し て テ スト 系 列の 定 められ た 位 置に 無条件に変換（ 圧縮 ）できることを意味する．し かし ，テンプレ ート に おいて ，その N 個のテスト パ ターンが 変換され る部分以外は 故障シ ミュレ ーション を 実 行し て いな いことに な る ．そこ で ，「 時 間展 開モ デ ルの 未検出故障f に 対し てテスト パターン 生成→ 時間展開モデ ル 上で 故障シ ミュレ ーシ ョン→未検出 故障集合F から 検出故障を 削除→無閉路順序回路 のテ スト 系列に 変換 」とい う操作を N 回繰り返し た
後(n == N )に ，圧縮後のテ スト 系列に おいて ，ま だ 故障シ ミュレ ーシ ョンを実行し ていない基本テンプ レ ート 長分のテ スト 系列を逆変換し て時間展開モデ ル のテ スト パターンを抽出する．具体的には ，まだ 故障 シ ミュレ ーションを実行し ていないテ スト 系列の先頭 に 基本テンプレ ート の先頭を重ね 合わせて ，基本テン プレ ート のbの位置に 重ね合わさったテ スト 系列の値 を取り出す．続いて ，その 抽出し たテ スト パターン を 用いて 時間展開モデ ル 上で 故障シ ミュレ ーシ ョンを実 行し ，検出故障を 未検出故障集合F から 削除すると い うもので ある（ 逆変換故障シ ミュレ ーション ）．た だし ，逆変換故障シ ミュレ ーションを行う前に ，圧縮 後のテ スト 系列に存在するX にランダ ムに0か1の 値を設定し ておくものとする．最終的に 得られ るテス ト 系列は ，テンプレ ート を用いて 圧縮し たテ スト 系列 を一つ前のテンプレ ート を用いて 圧縮し たテ スト 系列 の有効長の時刻から 重ねていく操作を繰り返すことに より生成できるので ，以上で述べた「N 回のテストパ ターン 生成→逆変換故障シ ミュレ ーシ ョン 」という 処理を 未検出故障集合F が 空集合にな るまで 繰り返 すことになる．
図8 静的，動的圧縮を含んだ 無閉路順序回路のテ スト 系 列生成アルゴ リズム
Fig. 8 Test sequence generation algorithm including static and dynamic compaction.
例5：図 7 の テ ン プ レ ート を 圧 縮 に 用 い る テ ン プ レ ート と す る ．図 7 の テ ンプ レ ート は 表 5の4 個 の 基 本 テ ン プ レ ート を 圧 縮し た も の で あ る ．ま た こ こ で は ，時 間 展 開 モデ ル 上 で 生 成し た 四 つ の テ スト パタ ーン (P I1(0), P I2(0), P I3(0), P I1(1), P I2(4), P I3(5)) = (0, 1, 0, 0, 0, 1), (1, 1, 0, 0, 1, 0), (1, 0, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0) が あ る と す る ．こ の
四つのテ スト パターン を変換し た四つのテ スト 系列を テンプレ ート を用いて圧縮すると，図9に示すよ うな テ スト 系列になる．圧縮に 用いたテンプレ ート の有効 長は15であるので ，次のテンプレ ート を 用いて圧縮 し たテ スト 系列と 重な る時刻は 時刻15である ．よっ て ，時刻0∼時刻14まで のテ スト 系列中に 存在する X に ランダ ムに 0又は 1を 設定する．図 10に 示す
図9 図7 のテンプレートを用いた圧縮の例 Fig. 9 Example of compaction using the template of
Fig. 7.
図10 時間展開モデ ルのテスト パターン 抽出の例 Fig. 10 Example of extraction of a test pattern for a
time expansion model.
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
よ うに ，時刻1∼ 時刻7 まで の テ スト 系 列を 逆変 換 し て，テストパターン(0, 0, 0, 1, 0, 1)を抽出し た ．ま た ，図10に おいて ，値を 抽出し た部分を 四角で 囲ん だ ．同様に ，時刻2∼時刻8までのテスト 系列を逆変 換し て ，テ スト パターン (1, 0, 1, 1, 0, 0)，時刻4∼時 刻10までのテ スト 系列を 逆変換し て ，テ スト パター ン(0, 0, 0, 1, 1, 0)，時刻5∼時刻11までのテスト 系列 を 逆変換し て ，テ スト パターン (1, 0, 1, 1, 0, 1)，時刻 7∼時刻13までのテスト 系列を逆変換し て，テストパ
ターン (0, 1, 0, 1, 0, 1)，時刻 8∼時 刻 14まで のテ ス ト 系列を逆変換し て ，テ スト パターン (1, 1, 0, 0, 0, 1) をそれぞれ 抽出できる．
5. 実 験 結 果
表7に 実験に 用いる実際の回路（#1∼#4）の特性 を示す．表7において ，#PIは 外部入力数，#POは 外部出力数，#FFはFF数，SRは回路をテ スト 時に 無閉路順序回路にするために 必要な スキャンFFの割 合（ スキャン 化率 ），#GATEは2入力NANDゲート 換算でのゲ ート 数をそれぞれ 表す．表8に圧縮可能グ ラフの頂点数を変化させて，提案したヒューリスティッ クアルゴ リズムを用いてテンプレ ート を生成する実験 結果を示す．表8において ，NVは 圧縮可能グ ラフの 頂点数，CPU（ 単位：秒 ）は 圧縮に 費やし たCPU時 間すなわち圧縮可能グ ラフの作成とクリーク抽出に 要 し たCPU時 間（Ultra2使 用 ，動 作速 度：296 MHz， SPECint95：12.1，SPECfp95：18.3），VLは 生成し
表7 実験回路の特性
Table 7 Properties of experimental circuits. 回路名 #PI #PO #FF SR(％) #GATE
#1 97 16 176 0 4687
#2 113 16 272 0 4706
#3 342 11 1550 61.9 11682
#4 673 487 3744 72.5 51135
表8 実験結果：テンプレ ート 生成
Table 8 Experimental results: Template generation. 回路 NV CPU VL NP TL CR
#1 8 0.01 12 3 984 4.00
15 0.02 18 5 864 3.60 114 1.16 119 37 738 3.22 171 6.54 176 56 720 3.14 200 8.35 205 66 708 3.11
#2 11 0.01 16 3 1616 5.33 21 0.02 29 5 1762 5.80 153 1.50 162 30 1635 5.40 200 4.66 209 39 1622 5.36 304 25.70 314 58 1638 5.41
た テンプ レ ート の 有 効 長 ，NPは 圧 縮し た 基 本テン プ レ ート 数，TLは 全体のテ スト パターン 長，CRは VL/NPで 圧縮効率を それぞれ 表す．CRの値が 小さ
いほど ，圧縮効率が 高くなる．実験結果は#1，#2の み 示 す．#3と#4は 結果とし て 一 定の スキュー 値の 整数倍で 基本テンプレ ート の圧縮を繰り返し たテンプ レ ートが 生成され る．つまり二つの基本テンプレ ート をテンプレ ート の 有効長が 最短にな るよ うに 圧縮し ， 更に 圧縮し たテンプレ ート と基本テンプレ ート を同様 に 圧縮し て新たなテンプレ ート を生成する方法（ 貪欲 なアルゴ リズム ）を使用し た 場合と同一の結果になっ た．表8に示すように 圧縮可能グ ラフの 頂点数が 多く なるほど テンプレ ート の生成に 時間がかか るが ，圧縮 可能グ ラフの頂点数が200個程度であれば ，ほとんど 無視できる時間内で 生成できることがわか る．圧縮効 率と頂点数についての考察は今後の課題とし て残る． 表9にヒューリスティックアルゴ リズムの有効性を 評価するために ，圧縮可能グ ラフから 圧縮効率が 最も 高くなる最大クリークを抽出し て生成し たテンプレ ー ト との比較を行った実験結果を示す．
表 9 に お い てHVL，HNP，HCRは ヒュー リ ス テ ィックアルゴ リズムを 用いて 生成し たテンプレ ート の 有 効 長 ，圧 縮す る 基 本テンプ レ ート 数 ，圧 縮 効 率
（HVL/HNP）を それぞれ 示し ，OVL，ONP，OCR は 最大ク リークから 生成し たテンプ レ ート の 有効長 ， 圧縮する基本テンプレート 数，圧縮効率（OVL/ONP） をそれぞれ 表す．表9の結果から 提案し たヒューリス テ ィックアルゴ リズムはほぼ 最高の 圧縮効率を 達成し ていることがわか る．また ，圧縮可能グ ラフの頂点数 は200とし た．以後テンプレ ート を用いた圧縮の実験 は 頂点数200で 行う．
表10に テンプ レ ート を 用 いた 圧 縮 方 法を 評 価し た 実験結果を 示す．表 10に おいて ，NCは 圧縮を 行 わない実験結果，TCはテンプレ ート を用いて 圧縮を 行った実験結果，3TCはテスト系列の先頭からX, 0, 1 の3値の 圧縮演算で 圧縮可能[8], [17]であ る部分を探 索し ，圧縮 可 能で あ る 部 分を 探 索し た 時 点で 圧 縮を 行った 実 験 結 果を 示す．CPU（ 単 位：秒 ）は 圧 縮 時 間（Ultra2使用，動作速度：296 MHz，SPECint95：
表9 実験結果：ヒューリスティックアルゴ リズム Table 9 Experimental results: Heuristic algorithm.
回路 HVL HNP HCR OVL ONP OCR
#1 206 66 3.12 205 67 3.06
#2 209 39 5.35 208 39 5.33
表10 実験結果：テンプレ ート を用いた圧縮方法 Table 10 Experimental results: Compaction method
using a template.
回路 NC TC 3TC
TL CPU TL TR CPU TL TR
#1 1589 8.85 708 44.56 6.08 910 57.27
#2 3030 4.58 1622 53.53 5.86 1821 60.10
#3 1140 13.17 584 51.23 9.98 572 50.18
#4 13740 8.86 7573 55.12 5137.75 6791 49.43
表11 逆変換故障シ ミュレ ーシ ョン を 用いた 圧 縮方法の 実験
Table 11 Experimental results: Compaction method using reverse transformation fault simula- tion.
回路 TC TCRF
CPU TL CPU TL TR1 TR2
#1 215.88 708 136.92 287 40.53 18.06
#2 138.24 1622 74.57 803 49.51 26.50
#3 44.32 584 51.54 351 60.10 30.79
#4 1150.23 7573 1525.21 4792 63.28 34.88
12.1，SPECfp95：18.3），TLは全体のテ スト 系列長， TRはNCのテ スト 系列長を基準とし たTC又は3TC
のテ スト 系列 長の 割合を 示す．TCはNCに 比べ て ， テスト 系列長を45∼55％に 削減することができた ．ま た3TCと 比較すると ，テ スト 系列長は 複数の基 本テ ンプレ ート の圧縮を同時に 考え ることによって効果の あった#1，#2の回路に対し てはTCのテスト 系列長 のほ うが短く，#3，#4の回路に対し ては ，3TCのほ うが 短くなる．圧縮時間に 関し ては ，#1∼#3の回路 についてはTC，3TCともほぼ 同程度であるが ，大規 模回路である#4についてはTCは3TCの約57倍の 速度でテ スト 系列の圧 縮を 行 うことが で きた ．表11 に 逆変換故障シ ミュレ ーシ ョンを用いた 圧縮方法を評 価する実験結果を 示す．表11に おいて ，TCは テン プレ ート を用いた 圧縮のみを行った実験結果，TCRF はテンプレ ート を用いた 圧縮と逆変換故障シ ミュレ ー ション を 用いた 圧縮を 組み合わせ て 行った 実験結果 ， TR1はTCのテ スト 系列長を基準とし たTCRFのテ
スト 系 列長の 割合 ，TR2は 表 10のNCのテ スト 系 列長を 基準とし たTCRFのテ スト 系列長の 割合を 示 す．CPUはATPG時間，TL全体のテ スト 系列長で あ る ．TCRFはTCに 比べて 全体のテ スト 系列長を 41∼63％に ，NCに比べて全体のテスト 系列長を19∼ 34％に 削減することができ，静的圧縮と動的圧縮を組 み合わせて更にテスト 系列を圧縮することができた ．
6. む す び
本論文では ，テンプレ ート を用いた 無閉路順序回路 の 静 的テ スト 系 列 圧 縮 方 法と 逆 変 換 故 障シ ミュレ ー ションによる無閉路順序回路の動的テ スト 系列圧縮方 法を提案し た．実際の回路で提案方法を評価し た結果， 以下の結論を得ることができた ．
（1）提案し たヒューリ ステ ィックアルゴ リズムは 効果的である．
（2）テンプ レ ート を 用いた 圧縮を 用い ることで ， テ スト 系列長を45∼55％に 短縮することができた ．
（3）逆変換故障シ ミュレ ーションによる圧縮を用 いることで ，テスト 系列長を更に41∼63％に 短縮する ことができた．
今後の課題とし て ，以下のことが 挙げ られ る．
（1）圧縮効率と圧縮可能グ ラフの頂点数の関係を 考察する．
（2）逆変換故障シ ミュレ ーションによる圧縮方法 をより圧縮効率が 高くなるように 改善する．
謝辞 本論文に 関し ，貴重な御意見をいただいた 松 下電器産業株式会社（ 株 ）半導体開発本部の辻史郎氏， 太田光保氏，川口謙一氏，並び に ，奈良先端科学技術 大学院大学の増澤利光助教授，井上美智子助手に 感謝 致し ます．
文 献
[1] H. Fujiwara, Logic Testing and Design for Testability, The MIT Press, 1985.
[2] M. Abramovici, M.A. Breuer, and A.D. Friedman, Digital Systems Testing and Testable Design, Com- puter Science Press, 1990.
[3] K.-T. Cheng and V.D. Agrawal, “A partial scan method for sequential circuits with feedback,” IEEE Trans. Comput., vol.39, no4, pp.544–548, April 1990. [4] D.H. Lee and S.M. Reddy, “On determining scan flip- flops in partial scan design approach,” Proc. IEEE Proc. Int. Conf. Computer-Aided Design, pp.322– 325, Nov. 1990.
[5] S.T. Chakradhar, A. Balakrishnan, and V.D. Agrawal,
“An exact algorithm for selecting partial scan flip- flops,” Proc. ACM/IEEE Design Automation Conf., pp.81–86, June 1994.
[6] R. Gupta, R. Gupta, and M.A. Breuer, “The BAL- LAST methodology for structured partial scan de- sign,” IEEE Trans. Comput., vol.39, no.4, pp.538– 544, April 1990
[7] T. Takasaki, T. Inoue, and H. Fujiwara, “Partial scan design methods based on internally balanced struc- ture,” IEEE Proc. Asia and South Pacific Design Au- tomation Conf., pp.211–216, Feb. 1998.
電子情報通信学会論文誌’99/7 Vol. J82–D–I No. 7
[8] T. Hosokawa, T. Hiraoka, M. Ohta, M. Muraoka, and S.Kuninobu, “A partial scan design method based on n-fold line-up structures,” IEEE Proc. Asian Test Symp., pp.306–311, Nov. 1997.
[9] T. Inoue, T. Hosokawa, T. Mihara, and H. Fujiwara,
“An optimal time expansion model based on com- binational ATPG for RT level circuits,” IEEE Proc. Asian Test Symp., pp.190–197, Dec. 1998.
[10] P .Goel and B.C. Rosales, “Test generation and dy- namic compaction of tests,” IEEE Proc. Int. Test Conf., pp.189–192, Oct. 1979.
[11] G. Tromp, “Minimal test sets for combinational cir- cuits,” IEEE Proc. Int. Test Conf., pp.204–209, Oct. 1991.
[12] I. Pomeranz, L.N. Reddy, and S.M. Reddy, “COM- PACTEST: A method to generate compact test sets for combinational circuits,” IEEE Proc. Int. Test Conf., pp.194–203, Oct. 1991.
[13] S. Kajihara, I. Pomeranz, K. Kinoshita, and S.M. Reddy, “Costeffective generation of minimal test sets for stuck-at faults in combinational logic circuits,” IEEE Trans. on Computer-Aided Design, pp.1496– 1504, Dec. 1995.
[14] I. Pomeranz and S.M. Reddy, “Dynamic test com- paction for synchronous sequential circuits using static compaction techniques,” IEEE Proc. Fault- Tolerant Computing Symp., pp.53–61, June 1996. [15] I. Pomeranz and S.M. Reddy, “On static compaction
of test sequences for synchronous sequential circuits,” ACM/IEEE Proc. Design Automation Conf., pp.215– 220, June 1996.
[16] I. Pomeranz and S.M. Reddy, “Vector restoration based static compaction of test sequences for syn- chronous sequential circuits,” IEEE Proc. Int. Conf. on Computer Design, pp.360–365, Oct. 1997. [17] T.M. Niermann, R.K. Roy, J.H. Patel, and J.A.
Abraham, “Test compaction for sequential circuits,” IEEE Trans. on Computer-Aided Design, vol.11, no.2, pp.260–267, Feb. 1992.
[18] M.S. Hsiao, E.M. Rudnick, and J.H. Patel, “Fast al- gorithm for static compaction of sequential circuit test vectors,” IEEE Proc. VLSI Test Symp., pp.188– 195, April 1997.
[19] S.T. Chakradhar and A. Raghunathan, “Bottleneck removal algorithm for dynamic compaction in sequen- tial circuits,” IEEE Trans. on Computer-Aided De- sign, vol.16, no.10, pp.1157–1172, Oct. 1997. [20] Giovanni De Micheli, Synthesis and optimization of
digital circuits, McGraw-Hill, Inc., 1994.
（ 平成10 年 10 月 23 日受付，11 年 2 月 10 日再受付）
細川 利典
昭62 明大・工・電子通信卒．同年松下 電器産業（ 株 ）入社．論理シ ミュレ ーシ ョ ンエンジン ，テストパターン 生成，故障シ ミュレ ーション ，テスト 容易化設計，上流 テ スト の 研究開発に 従事 ．情報処理 学会 ， IEEE 各会員．
井上 智生 （ 正員 ）
昭63 明大・工・電子通信卒．平 2 同大 大学院博士前期課程了．同年松下電器産業
（ 株 ）に 入社 ，明治大大学院博士後期課程 を経て ，現在奈良先端科学技術大学院大学 助手．松下電器産業（ 株 ）に おいて マイク ロプ ロセッサの研究開発に 従事．明大，奈 良先端大に おいて ，テスト 生成，並列処理，テスト 容易化設計 の研究に 従事．工博．情報処理学会，IEEE 各会員．
平岡 敏洋
平6 京大・工・精密卒．平 8 同大大学院 修士課程了．同年松下電器産業（ 株 ）入社． 平10 年 10 月より京都大学大学院情報科学 研究科シ ステム科学専攻助手．松下電器産 業（ 株 ）に おいて ，テスト 容易化設計，テ ストパターン 生成の研究開発に 従事．
藤原 秀雄 （ 正員 ）
昭44 阪大・工・電子卒．昭 49 同大大学 院博士課程了．同大・工・電子助手，明治 大・工・電子通信助教授，理工・情報科学 教授を経て ，現在奈良先端科学技術大学院 大学教授 ，昭56 ウォールタールー大客員 助教授．昭59 マッギル大客員準教授．論 理設計論，高信頼性設計，設計自動化，テスト 容易化設計，テ スト 生 成 ，並 列 処理 ，計 算複 雑度に 関す る 研 究に 従 事 ．著 書
「Logic Testing and Design for Testability」（MIT Press） など ．工博．情報処理学会会員．IEEE Fellow．
