ホールド 機能を考慮し た順序回路の部分スキャン 設計法
佐野ちいほ
†三原 隆宏
††井上 智生
†††Debesh K. DAS
††††藤原 秀雄
†A Partial Scan Design Method for Sequential Circuits with Hold Registers
Chiiho SANO†, Takahiro MIHARA††, Tomoo INOUE†††, Debesh K. DAS††††, and Hideo FUJIWARA†
あらまし 本論文では ，ホールド 機能をもつレ ジ スタ（ ホールド レジ スタ ）を考慮し た順序回路の部分スキャ ン 設計法を提案する．無閉路順序回路のテ スト 生成は ，すべての極大展開モデルに対し ，組合せ回路用のテ スト 生成アルゴ リズムでテ スト 生成を行えば 十分である．そこで ，極大展開モデルが 唯一となる（ 最大展開モデルを もつ ）ような順序回路のクラスを提案する．更に ，一般の順序回路から 最大展開モデルが 存在する無閉路順序回 路に 変更する部分スキャン 設計法について ，スキャン ハード ウェアオーバヘッド を最小にするスキャンレジ スタ 選択問題を 定式化し ，その問題を解くヒューリステ ィックアルゴ リズムを提案する．これ により，部分スキャン 設計に おけ るスキャン ハード ウェアオーバヘッド は ，ホールド レジ スタを 含まない順序回路に 比べ小さく実現可 能である．
キーワード ホールド レジ スタ，無閉路順序回路，最大展開モデル ，組合せテ スト 生成，部分スキャン
1. ま え がき
順序回路の テ スト 生成は 一般に 困難な 問題で あり， 回路規模が 大きくなると解けなくなる場合が 多い．こ れ を 解決す るた めに ，フ リップ フ ロップ（ 以 下 ，FF と 略す ）を スキャン 可能なFFに 変更する部分スキャ ン 設計法が 提案されている[1], [2]．これらの設計では ， スキャンFFを 等価 的に 外部 入出力と みな せ るので ， スキャンFFを取り除いた残りの回路（ 核回路と呼ぶ ） に 対し てテ スト 生成を行えば よい．回路中のすべての FFを スキャンFFに 変更する完全スキャン 設計法で は ，核回路が 組合せ回路となるので 組合せ回路用のテ スト 生成アルゴ リズムでテ スト 生成が 可能（ 以下，組
†奈良先端科学技術大学院大学情報科学研究科，生駒市
Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma-shi, 630–0101 Japan
††
三菱電機コント ロール ソフト ウェア 株式会社，神戸市
Mitsubishi Electronic Control Software Corporation, Kobe-shi, 652–0871 Japan
†††
広島市立大学情報機械シ ステム工学科，広島市
Department of Information Machines and Interfaces, Fac- ulty of Information Sciences, Hiroshima City University, Hiroshima-shi, 731–3194 Japan
††††ジ ャダプ ール 大学計算機科学・工学科，インド
Dept. of Comp. Sc. and Engg., Jadavpur University, Calcutta-700 032, India
合せテスト 生成可能と略す ）である．一方，一部のFF を スキャン FFに 変 更する 部 分 スキャン 設計 法で は ， 核回路にFFが 残るため ，一般には ，順序回路用のテ スト 生成アルゴ リズムを適用し なければ ならず，真の 意味で 組合せ回路レ ベルのテスト 容易化は 達成され て いない．文献[3], [4]では ，フ ィード バックループ を切 断することでテスト 生成を容易にし ているが ，核回路 は 自己ループ を含んでいるため ，順序回路用のテ スト 生成アルゴ リズムが 必要となる．
一方，順序回路を組合せテスト 生成可能とする方法 とし て ，核回路が 組合せ回路となるように ，自己ルー プ を含むすべてのフ ィード バックループ を切断し ，回 路を 無 閉 路 化（ 無 閉 路 順 序 回 路と 呼ぶ ）す る 部 分 ス キャン 設計 法が あ る[5], [6]．また ，文 献[7], [8]で は ， それぞれ ，無閉路順序回路に対し ，テスト 生成モデル ， 時間展開モデルを用いることで 組合せテ スト 生成可能 とし た ．更に ，RTレ ベル 回路に おいて ，核回路を 無 閉路にする無閉路部分スキャン 設計法も提案され てい る[8]．
し かし ，無閉路部分スキャン 設計において ，回路に ホールド 機能を有するレジ スタ（ ホールド レジ スタと 呼ぶ ）が 存在するとき，ホールド レジ スタは 機能的に 自 己ル ープ と みな され るた め ，すべ て の ホ ールド レ
D– Vol. J83–D– No. 9 pp. 981–990 2000 9 981
電子情報通信学会論文誌2000/9 Vol. J83–D–I No. 9
ジ スタが スキャンの対象となり，スキャンに 伴うハー ド ウェアオーバヘッド が 大きい．そこで ，本論文では ホールド レジ スタを 含む無閉路順序回路に 対し ，組合 せテスト 生成可能な時間展開モデルを提案する[9]．こ の結果，ホールド レジ スタが スキャンの対象とならず， ハード ウェアオーバヘッド の削減が 可能となる．し か し ながら ，ホールド レジ スタに 与え る制御系列が 異な れば ，得られ る時間展開モデ ルも一般に 異なり，し た がって，無閉路順序回路のテスト 生成を行うためには ， 得られ るすべての時間展開モデ ルに 対し てテ スト 生成 する必要がある．し かし ，時間展開モデ ルの被覆関係 を考えた場合，得られ るすべての時間展開モデルに 対 し てテスト 生成する必要はな く，極大展開モデルに 対 し てのみテ スト 生成を行えば 十分である．本論文では 更に ，テ スト 生成に 必要な極大展開モデ ルが 唯一とな る（ 最大展開モデ ルと呼ぶ ）順序回路のクラスを提案 する．また ，その条件のもとで ，核回路が 最大展開モ デルを 有する無閉路順序回路となるよ うな部分スキャ ン 設計法について ，ハード ウェアオーバヘッド 最小を 目指し たヒューリスティックアルゴ リズムを提案する．
2. 順序回路のテスト 生成法
2. 1 回路モデ ル
順序回路は ，複数の組合せ論理ブ ロック（ 以下，論 理部と略す ）からなり，それらの論理部が 直接，ある いは ，レジ スタを 通し て相互に 接続され ていると考え る．レジ スタにはホールド レジ スタとロード レジ スタ があり，ホールド レジ スタは ，ホールド モード （ 連続 するクロックサイクル 間，値を保持 ）とロード モード
（ クロックが 与えられたとき，値を取り込む ）の二つの 動作モード をもつ．一方，ロード レジ スタは 常にロー ド モード で 動作する．また ，レジ スタへのクロック信 号は ，外部から 直接印加され るものとする．し たが っ て ，順序回路の入力パターンは ，論理部へのデ ータ入 力とホールド レジ スタへの制御入力の二つからなる． このとき，順序回路は 以下のト ポロジ ーグ ラフを 用 いて 表現できる．
［ 定義1］（トポロジ ーグ ラフ ）
トポロジ ーグ ラフG = (V, A, r)は 有向グ ラフで あ り，頂点v ∈ V は 一つの論理部，辺(u, v) ∈ Aは 二 つの論理部u, v間の接続を表す．また，各辺にはラベ ル r : A → Z+∪ {h}（Z+は 非負の 整数集合 ）が 付 いており，二つの 論理部が0個以上のロード レジ スタ で 接続され ている場合，ラベルr(u, v)はロード レジ
スタの 個数(r(u, v) ∈ Z+)を ，一方，一つのホール ド レジ スタ
（ 注 1 ）
で接続されている場合，r(u, v) = hと
表す． ✷
2. 2 時間展開モデ ル
時間展開モデ ルを用いた 無閉路順序回路のテスト 生 成は，まず，無閉路順序回路S（ 図1 (a)：1, 2, . . . , 7は 論理部，b, . . . , iはロード レジ スタ，a，jはホールド レ ジ スタ（ 黒色 ））のトポロジ ーグ ラフG（ 図1 (b)）を 作り，それに基づく時間展開グラフE = (VE, AE, t, l)
（ 図2）を生成する．
Gの 任 意 の 頂 点に 対 応 す る 頂 点 集 合を VE とし ， u, v(u, v ∈ VE)に 対応するGの 頂点間に 有向辺が あ るとき，有向辺(u, v) ∈ AEで接続する．Gの任意の 頂点に 隣接する頂点集合（ 祖先 ）は ，Eのそれに対応 する頂点の祖先と等し い．tはVEから整数への写像を 表し ，(u, v) ∈ Z+であれば ，頂点u, vをt(v) − t(u) がu, vに 対応するGの頂点間のレジ スタ数となるよ うに 接続し ，(u, v) = hであれば ，ホールド レジ スタ に対する制御系列が 得られ るように 接続する（ 例1参 照 ）．lはVE からGの頂点集合V への写像を 表す． ここで ，Gの 任 意の頂 点に 対し ，それ に 対応するE の頂点は 一般に 複数存在する
（ 注 2 ）
．また ，E の各頂点 uが 表す数は ，対応するGの 頂点名l(u)(∈ V )を 表 し ，グ ラフ上部の数字は ，その列にある頂点uのラベ ルt(u)を表す．
［ 例1］ 図3に 示す有向グ ラフN Eに おいて ，ホー ルド レ ジ ス タ a（ 図 1 (a)）の 制 御 系 列 を 考 え る ． 今 ，時 刻0で ロ ード し 時 刻4まで ホ ー ルド され て い る a の 制 御 系 列 を a(1) = (L, H, H, H, X, X)
（ 図 3 (1)），時 刻2で ロード し て い るa の 制 御 系 列 をa(2) = (X, X, L, X, X, X)（ 図3 (2)）とする．た だし ，X はド ント ・ケアとする．ここで ，同じ aの 制御系列に ついて ，時刻2でホールド (H)とロード (L)の異なる制御が 必要となる．し かし ，同時刻に 異 なる制御を与えることはできないため ，N Eにおいて ホ ールド レ ジ スタ aの 制 御系列を 得ることが で きな
い． ✷
得られたEに基づき時間展開モデルCE（ 図1 (c)： SのE1に基づく時間展開モデ ル ）を生成する．Eの
（ 注1）：二つの 論理部間に 二つのホールド レジ スタか ，若し くは ，ロー ド レ ジ スタと ホールド レ ジ スタが 存在する 場合 ，二つのレ ジ スタ間に ，
信号線のみか ，またはバッファ のみで 構成され る論理部が あると 仮定し ， ト ポロジ ーグ ラフを 表現することが できる．
（ 注2）：t(u) = t(w)かつl(u) = l(w)ならば ，uとwは 同一の頂点 (u = w)と する．これ を単 一化と 呼ぶ．
(a) 無閉路順序回路 S (b) S のトポロジーグラフ G (c) E1に 基づ く時間展開モデ ルCE1
図1 (a) 無閉路順序回路，(b) トポロジーグラフ，(c) 時間展開モデル
Fig. 1 (a) Acyclic Sequential Circuit, (b) Topology Graph, (c) Time Expansion Model (TEM).
(a) 時間展開グラフ E1 (b) 時間展開グラフ E2 (c) 時間展開グラフ E3
図2 SのGに 基づ く時間展開グ ラフE1，E2，E3 Fig. 2 Time Expansion Graph (TEG) of S based on G.
図3 矛盾し た有向グ ラフN E Fig. 3 Example of inconsistent graph N E.
各頂点uについて，論理部l(u)をuに 対応する論理 部とし ，有向辺(u, v)(∈ AE)に ついて ，(l(u), l(v)) と同様に ，uの出力をvの入力とし て信号線で接続す る（ その際，接続にレジ スタは 介さない ）．ここで ，各 論理部内の信号線及び 論理ゲートが ，外部出力，また は ，他の論理部の入力のいずれにも到達不可能なとき， その 信号線または 論理ゲ ート を 削除する（ 図1 (c)の 点線部分 ）．この結果，組合せ回路となるCE に 対し ， 組合せテ スト 生成を行う．
また ，一つのト ポロジ ーグ ラフから 得られ る時間展 開グ ラフは 一般に 複数存在し ，一方，時間展開モデ ル は 時間展開グ ラフから 一意に 決定することができる．
2. 3 時間展開モデ ルを用いたテスト 生成
時間展開モデ ルに 対し ，組合せテ スト 生成を行った 結果得られ る時間展開モデルのテ スト パターンは ，無 閉路順序回路の 入力系列に 変換可能である．し たが っ て，時間展開モデルに対し てテスト 生成を行うことで ， 無閉路順序回路は 組合せテ スト 生成可能となる．
今 ，時 間 展 開 モデ ル CE1（ 図 1 (c)）に 対し て テ スト 生 成し た 結 果 得 ら れ た 入 力 パ タ ー ン に つ い て 考 え る ．CE1 の 論 理 部1，5に 対 す る 入 力 パ タ ー ン を そ れ ぞ れ ，IC(1) = (X10, X11) = (I10, I11)， IC(5) = (X2) = (I2)，それ に 対 応 す る CE1 の 出 力パターン をOC= (Z1, Z2) = (O1, O2)とする．こ のとき，S の入力系列は ，論理部1に 対し て ，時刻0 にI10，時刻1にI11を ，論理部5に 対し て ，時刻1 に I2を 入力することで 得られ る．一方，ホールド レ ジ スタへの 制御系列は ，CE1 の入力パターンに 関係な く，E1からのみ求めることができる（ 表1参照．X はド ント ・ケア ）．
また ，無閉路順序回路のデ ータ入力系列と制御系列 は ，時間展開グ ラフとそれに基づ く時間展開モデ ルの 入力パターンに 変換可能である．
まず，無閉路順序回路S の制御系列をもとに時間展
電子情報通信学会論文誌2000/9 Vol. J83–D–I No. 9 表1 E1から変換され たSへの入出力系列
Table 1 Input and output sequences for S from E1.
0 1 2 3
X1 I10 I11 × × X2 × I2 × × Reg.a L H × × Reg.j × × L × Z1 × × × O1 Z2 × × × O2
開グ ラフEを 生成する．S の 時刻tに おけ る論理部 vの入力パターンが 出力に 影響する場合，vに 対応す るE の頂点の 入力パターン を ，Sの時刻tに おけ る 論理部vの入力系列とする．このことから ，一つの時 間展開グ ラフ（ 時間展開モデル ）は ，順序回路のデ ー タ入力系列とは 関係なく，ホールド レジ スタに 対する 制御系列のみから 求めることができる．
2. 4 時間展開モデ ルの故障
無閉路順序回路と時間展開モデ ルの故障の関係につ いて考える．ここで ，論理部間の信号線の縮退故障や， 2種類のレ ジ スタの 出力線の 縮退故障は ，論理部の 入 力線や出力線の縮退故障と等価と考えることができる．
無 閉 路 順 序 回 路 S のト ポ ロ ジ ーグ ラ フ を G = (V, A, r)，G の 任 意 の 時 間 展 開 グ ラ フ を E = (VE, AE, t, l)，E に 基 づ く S の 時 間 展 開 モデ ル を CEとする．また ，Sの故障集合を F，CE の故障集
合をFEとする．
［ 定義2］（ 時間展開モデ ルの故障 ）
Sの故障f (∈ F )に 対応するCEの故障fe(∈ FE) は ，故障fの存在する論理部v(∈ V )に対応するCE の各論理部u(∈ l−1(v))の同じ 位置（ 信号線 ）に 存在 する多重故障とする．すなわち，l(u) = vとなる論理 部uに 存在する故障が ただ 一つのとき，feは 単一縮 退故障 ，複数存在す ると き ，fe は 多重縮退故障とな
る． ✷
［ 定理1］（1） S の 故 障 f (∈ F )に 対応す る CE の故障 fe (∈ FE)が テ スト 生成可能とな るよ うなE が 存在するとき，かつそのときに 限り，Sの故障fは テ スト 生成可能（ 非冗長 ）である．
（2） CEで得られた故障fe(∈ FE)に対するテス ト パターンは ，feに 対応するS の故障f (∈ F )に 対 するテ スト 系列に 変換可能である． ✷
定理1の証 明は 紙 面の 都 合 上省略す る ．詳細は 文 献[10]を参照されたい．
定理1より，無閉路順序回路は ，異なるいくつかの
時間展開モデルに 対し てテ スト 生成を行うことでテ ス ト 可能である．また ，時間展開モデ ルは 完全な組合せ 回路であるので ，組合せテ スト 生成アルゴ リズムが 適 用できる（ ただし ，多重故障対応 ）．
更に ，定理1より以下のことが いえ る．
［ 系1］ 無閉路順序回路をS，S の故障集合をF と する ．故障f (∈ F )に 対応する任意の時 間展開モデ ルの故障fe(∈ FE)がテスト 不能ならば ，かつそのと きに 限り，故障f もテ スト 不能である． ✷
ゆえに ，順序回路に 対する完全なテ スト 系列を得る ためには ，順序回路から 得られ るすべての時間展開モ デ ルに 対し てテ スト 生成を 行 う必要が ある ．し かし ， 一般にすべての時間展開モデルを求めることは困難で ある．そこで ，テ スト 生成に必要となる時間展開モデ ルの数を減らすため ，時間展開モデ ルに 被覆関係を導 入し ，完全なテスト 集合が 得られ る時間展開モデ ルを 考え る．
3. 最大テスト 可能な順序回路
3. 1 時間展開モデ ルの被覆
無 閉 路 順 序回 路 S のト ポ ロジ ーグ ラフ Gに つい て ，Gの 頂点v1 からvkまでのすべての 経路集合を P (v1, vk) = {p1, p2, · · · , pn}，その一つの 経路をp = (v1, v2, · · · , vk)とする．
［ 定義3］（ 被覆関係 ）
S の 任 意 の 二 つ の 時 間 展 開 グ ラ フ を E1 = (V1, A1, l1, t1)，E2 = (V2, A2, l2, t2) と す る ．こ の とき，E2の任意の頂点s2に対し ，以下の条件を満た すようなl2(s2) = l1(s1)となる頂点s1がE1に存在 するとき，E1は E2 を 被覆する（E Eと 書く ） という．
l1(u) = l2(v)∧
P (l1(u), l1(s1)) ∩ P (l2(v), l2(s2)) = φ
⇒ P (l1(u), l1(s1))⊂=P (l2(v), l2(s2))
ただし ，u (∈ V1)，v (∈ V2)はそれぞれ ，s1，s2の
祖先とする． ✷
二つの時間展開グ ラフE1，E2 について ，l1(o1) = l2(o2)である任意の頂点o1(∈ V1)，o2(∈ V2)のすべ ての祖先集合により導出され る部分グ ラフをそれぞれ ， E1′ = (V1′, A1′, t′1, l′1)，E2′ = (V2′, A′2, t′2, l′2)とする．
［ 補題1］時間展開グ ラフE1がE2を被覆するとき， 任意の頂点u (∈ V
′
1)に ついて ，以下の 条件を 満たす v = m(u)で 与えられ るちょうど 一つの頂点vに 対応 するような関数m : V
′
1 → V2′が 存在する．
（1）l1(u) = l2(v)
（2）P (l1(u), l1(s1))⊂
=P (l2(v), l2(s2)) ✷ 補題1の証 明は 紙 面の 都 合 上省略す る ．詳細は 文 献[10]を参照されたい．
時 間 展 開グ ラ フ E1 が E2 を 被 覆 す る と き ，E1， E2 の 時 間 展 開 モ デ ル CE1 も CE2 を 被 覆 す る
(CE1 CE2)．ま た ，E1 が E2 を 被 覆し ，E2 が
E3を被覆するとき，E1はE3を被覆する．
定義3より，関数 mはト ポロジ ーグ ラフの一つの 論理部について ，それに 対応するE1とE2 の論理部 間の 関 係を 表し て い る ．E1 が E2 を 被 覆す ると き ， V1 からV2 への 関数 mが 存在し ，V1に 存在する同
じ ラベル をもつ 複数の頂 点が ，V2 の 同じ ラベル をも つあ る一つの頂点に 対応する場合がある．
無閉路順序回路S（ 図1 (a)）の二つの 時 間展開モ デ ルを CE1，CE3（ 図1 (c)，図4）とする．CE1 へ の入力パターン (X10, X11, X2) = (Ia, Ib, Ic)に 対す る出力パターン を(Z1, Z2) = (O1, O2)とする．この とき，CE3 への 入力パターン (X10, X11, X12, X2) = (Ia, Ia, Ib, Ic)に 対するCE3 の出力パターンは ，CE1
の出力パターンと等し い．よってCE3 はCE1 を被覆 する．
これより，CE1がCE2 を被覆するとき，CE2の入 出力の関係をCE1でも再現できる．これは，被覆する CE1の任意の論理部に影響を与える論理部の数は ，常 に 被覆され るCE2 の 論理部の 数に 比べて ，等し いか 多いからである．一方，定義2より，無閉路順序回路 の任意の故障について ，それに対応する故障は ，CE1， CE2により定義され る．
［ 命題1］無閉路順序回路Sの二つの時間展開モデル CE1，CE2の故障集合をそれぞれF1，F2とする．ま
た ，S の故障f (∈ F1)に 対応するCE1，CE2の故障
をそれぞれ ，f1(∈ F1)，f2(∈ F2)とする．
図4 E3に 基づ く時間展開モデ ルCE3 Fig. 4 TEM CE3of S based on G.
CE1 CE2⇒
[CE2で 故障f2( ∈ F2)がテ スト 可能⇒ CE1で 故障f1( ∈ F1)はテスト 可能] ✷ 時間展開グ ラフ対E1，E2について ，E1 E2，か つ，E2 E1 であるとき，E1はE2を真に 被覆する
（E1≻ E2と 書く ）とい う．また ，E
′ E
を 満たす 時間展開グ ラフE
′
が 存在し ないとき，Eを極大であ るという．
今 ，無閉路順序回路S（ 図1 (a)）の 時間展開グ ラ フE1，E2，E3（ 図2）に ついて ，E3 はE1 を 被覆 するが ，E2 とE3 を 真に 被覆する時間展開グ ラフは 存在し ない．し たがって ，E2，E3がSのすべての極 大展開グ ラフである．
このことにより，次の系が 成り立つ．
［ 系2］ 順序回路S の任意の 故障をfとする．あ る 極大展開モデ ル CEm が 存在し ，f に 対応するCEm の故障fmがテスト 可能であるとき，かつそのときに 限り，S の故障f もテ スト 可能である． ✷
系2より，順序回路中のテ スト 可能なすべての故障 に 対する完全なテ スト 系列を得るためには ，すべての 極大展開モデルに 対し てテ スト 生成を行えば 十分であ る．し かし ，無閉路順序回路の極大展開モデルは 一般 に 複数存在し ，ゆえに ，その数が 多ければ 組合せテ ス ト 生成にもそれだけ多くの時間がかかると考えられ る． そこで ，極大展開モデ ルが 唯一となるための回路の条 件について考え る．ここで ，極大展開モデルが 唯一に なるとき，その極大展開モデルを最大展開モデルと呼 び ，最大展開モデ ルを有する順序回路を最大テスト 可 能という．また，回路が 最大テ スト 可能であれば ，最 大展開モデルに 対し てのみ，組合せテ スト 生成を行え ば 十分である．
［ 例2］ 無閉路順序回路S（ 図1 (a)）の極大展開グラ フを E2，E3（ 図2 (b)，(c)）と する ．ここで ，図3 に 示す有向グ ラフ N Eについて ，N EからE2，E3 に 対する 関数 mが 存在するため ，N Eは S の 最 大 展開グ ラフであると 考えられ る．し かし ，例1より， N Eか ら ホ ールド レ ジ スタの 制 御系 列を 得るこ とが できないため ，N EはS の時間展開グ ラフではない． ゆえに ，Sは 最大展開グ ラフとはならない． ✷
例2より，ホールド レジ スタから一つの外部出力ま でに 複数の経路が 存在するとき，一般に 時間展開グ ラ フには ，その ホールド レジ スタに 対応する辺（ 頂点 ） が 複数存在する．し たが って，最大テ スト 可能な回路 の最大展開モデ ルを作るためには ，トポロジ ーグ ラフ
電子情報通信学会論文誌2000/9 Vol. J83–D–I No. 9
の 任 意の 頂点対間に 存在するすべ ての 頂 点に ついて ， それに 対応する時間展開グ ラフの頂点が ，その経路数 だけ 存在すれば よい．ただし ，ホールド レジ スタに 関 係なく単一化が 生じ る頂点に関し ては ，必ずし もこの 限りではない．また ，このとき，すべてのホールド レ ジ スタに 対する 制御系列が 存在し なければ ならな い ． このように ，ホールド レジ スタの制御系列が 得られ る ように ，かつ，すべての頂点が 単一化され ることなく 存在させ ることを最大化するという．
3. 2 経路調整可能性
最大テ スト 可能な順序回路とし て ，一つの 回路クラ スを導入する．
［ 定義4］（ 経路調整可能 ）
無 閉 路 順 序 回 路 S のト ポ ロ ジ ーグ ラ フ を G = (V, A, r)，Gの任意の頂点uからv(u, v ∈ V )への経 路集合をP (u, v)とする．Gが 以下の条件を満たすと き，S(G)は経路調整可能であるという（ 図5参照 ）．
［ 条件CM］ r(ah) = hである任意の辺ah(∈ A)か ら 到達可能な頂点集合をV
′(⊂
=V )とする．このとき， 任意の 経 路対p, q(∈ P (u, v), u, v ∈ V′)に ついて ， 次のいずれかが 成り立つ．
（1） (H(p) = H(q))のとき(d(p) = d(q))
（2） (H(p) = H(q))のとき， (H(p) ∩ H(q) = φ) ⇒
(H(p) ⊃ H(q)) ∨ (H(p) ⊂ H(q))
ここで ，d(p)，H(p)はそれぞれ ，経路pに 存在する r(a) ∈ Z+であ る辺a (∈ A(p))のラベル r(a)の 和， r(a) = hである辺の 集合を表す．ただし ，A(p)は 経 路pに 存在する辺集合を表す． ✷
（1），（2）以外の 場合(H(p) ∩ H(q) = φ)，経路pに 存在する任意のホールド レジ スタに 対する制御系列は ， 経路qのホールド レジ スタに 関係なく決定できる．
CM(1)は ，各経路が 共通のホールド レジ スタhを 通り，かつ，ロード レジ スタ数が 等し いことを意味す る．し たが って，同じ hをもつ経路に 関し ては ，その 経路数に 関係な く，hに 対応する辺は 唯一であり，常
図5 経路調整可能な順序回路S3
Fig. 5 Path-adjustable acyclic sequential circuit S3.
に 最大化可能となる．このとき，hに 必要なロード 信 号はたかだか 一つであり，ゆえに ，hの制御系列は 自 由に与えることができる．一方，CM(2)について ，最 大化可能となるためには ，ホールド レジ スタの制御が
‘調整可能’であれば よい（ となるようなホールド レジ スタが 存在すれば よい ）．すべての経路に対し てホール ド レジ スタの 制御を一つず つ決めていく場合，経路p のすべてのホールド レジ スタに 対する制御系列を ，他 の経路 qのホ ールド レジ スタに 優先し て 決定し ても， それ 以外の（ 決定され ていない ）ホールド レジ スタが 経路qに存在すれば ，それによって制御系列を得るこ とができる．更に ，ホールド レジ スタを 含まない経路 については ，それ 以外の別の経路に 存在するホールド レジ スタの 制御によって最大化可能となる．
経路調整可能な順序回路に対し て ，以下のアルゴ リ ズムを適用し ，最大展開モデルを生成する．
［ 最大展開モデル生成アルゴ リズム ］
経 路 調 整 可 能 な 順 序 回 路 を S，S の ト ポ ロジ ー グ ラ フ を G = (V, A, r)，G の 時 間 展 開 グ ラ フ を E = (VE, AE, t, l)とする．
（1）Gから ，ホールド レジ スタに 関する以下の到 達可能グラフGR= (VR, AR)を求める．頂点集合VR
は ，Gに おけ るr(a) = hで あ る辺aの ラベル 集合 とする．また，r(a1) = h1，r(a2) = h2(a1, a2 ∈ VR) であるGの二つの 辺a1，a2について ，辺a1の終点 から 辺a2の 始点へ 経路が 存在する場合（ 到達可能な と き ，か つ ，その と きに 限り ），GR の 頂点h1 か ら h2 へ 有向辺を 書く．これ ら の 辺すべてから な る集合 をARとする．
（2）GR のすべ ての 頂点に ついて ，v1(∈ VR)か らv2(∈ VR)へ辺が 存在すれば ，v1がv2 よりも前に くるように並べる．この順序をGT とする．
（3）Gの 出次数0の 頂点集合を VO(∈ V )とし ， 各 頂 点 v(∈ VO) に つ い て ，l(u) = v と な る E の 頂 点 集 合を U と す る ．各 頂 点 u ∈ U に つ いて ，u の す べ て の 祖 先 集 合 に よ り 導 出 さ れ る 部 分グ ラ フ E′ = (VE′, A′E, t′, l′)を 求め る．このと き ，すべ ての ホ ー ルド レ ジ ス タ の ラ ベ ル 値 を1と み な す．ま た ， t′(v1) = t′(v2)，l′(v1) = l′(v2) とな るE′ の 任意の 頂点v1，v2からuまでの経路に含まれ るロード レジ スタの個数が 等し いときにのみ，v1とv2を単一化す る ．各頂点uに 対し て 得られ た 部分グ ラフの 集 合を
Eとする．
（4）GT の順序に 従い，ホールド レジ スタのホ ー
ルド 時間を以下の（a）∼（d）の手順で 変更する．
（a）GT = φならば（5）へ ．GT = φ| ならば ， 先頭の要素を一つ選択し ，それをheとする．
（b）各E′ = (V′, A′, t′, l′)(∈ E)に ついて ，E′ の出力頂点u′(∈ V′)から GT に 含まれ るホールド レ ジ スタのラベルに 出逢うまで 祖先をたど り，それ まで に たど った すべて の 頂 点集合 V
′
S を 求め る ．ここで ， VS′ にはホールド レジ スタに 対応する辺の 始点は 含め ない．
（c）r(l′(ve), l′(ve′)) = he で あ る す べ て の 頂 点 l′(ve) の ，すべ て の 祖 先か ら な る E′ の 頂 点 集 合を V (ve)とする．このとき，V (ve)の任意の頂点が ，VS′
に 含まれ る頂点に 対し て ，単一化され るのを避け るた めに必要な最小の値tを決定する．また，ui(∈ V (ve)) について ，t′(ui) = t′(ui) − thとする．
（d）GT= GT− {he}とし ，（a）に 戻る．
（5）ホールド レジ スタの制御系列が 得られ るよう に ，各 E
′
を 平行移動し t
′
を 変更する ．ただし ，E
′
の頂点の相対的な位置関係は 変更され ない．
こ の ア ルゴ リ ズ ム を 用 い て 得 ら れ た 経 路 調 整 可 能 な 順 序 回 路 S（ 図 5）の 最 大 展 開 モデ ル CEmax を 図 6 に 示 す．また ，CEmax の 論 理 部1に 対 す る 入 力パタ ーン IC(1) = (X10, X11, X12, X13, X14) = (I10, I11, I12, I13, I14)，それ に 対 応す るCEmax の 出 力パ ターン OC = (Z1) = (O1)に ついて ，IC，OC から 得られ るSの入力系列を表2に 示す（Xはド ン
図6 S3の最大展開モデルCEmax Fig. 6 Maximum TEM CEmax for S3.
表2 CEmaxから変換され たSへの入出力系列
Table 2 Input and output sequences for S from CEmax.
0 1 2 3 4 5 6 7
X1 I14 I13 I11 I12 I10 × × ×
Reg.a L × L L × × × ×
Reg.b × L × L H × × ×
Reg.d × × × × L H × ×
Reg.i × × L H H H H ×
Z1 × × × × × × × O1
ト ・ケア ）．
［ 命題2］経路調整可能な順序回路は 最大テ スト 可能
である． ✷
4. 部分スキャン 設計法
4. 1 問題の定式化
与えられた順序回路に 対し ，最小個のレジ スタを ス キャンレジ スタとし て選択することに より，核回路を 経路調整可能（ 最大テ スト 可能 ）とするスキャンレジ スタ選択問題を考え る．
［ スキャンレジ スタ選択問題 ］
入力：順序回路Sのト ポロジ ーグ ラフG = (V, A, r) 出力：集合R を取り除いた 核回路のト ポ ロジ ーグ ラ フGP = (V, A − R, r)が 経路調整可能となり，かつ，
a∈Rc(a)が 最小となるような辺集合R ⊂
= A ここで ，c(a)はレジ スタを スキャンレジ スタに 変更 する（ 以下，選択するとい う）際のハード ウェアオー バヘッド を表す．
この スキャンレジ スタ撰択問題に 対し て ，必ずし も 最小性は 保証され ないが ，多項式時間で 解け るヒュー リステ ィックアルゴ リズムを次に提案する．
4. 2 ヒューリステ ィックアルゴ リズ ム
この問題を2段階に 分けて解く．各段階での最適解 が 必ずし も全体の最適解になるとは 限らないが ，既存 のアルゴ リズムが 適用できるという利点がある．以下 に ，アルゴ リズムの概略を説明する．
Step 1 ト ポ ロ ジ ー グ ラ フ G = (V, A, r) か ら ，
a∈RAc(a)
が 最 小と な るよ うなフ ィード バック 辺 の 集 合 RA を 取り 除き ，無閉 路なト ポ ロジ ーグ ラフ GA= (VA, AA, r)に 変換する．
Step 2 GAから ，a∈R P c(a)
が 最小となるような 辺の集合RP を取り除き，経路調整可能なトポロジー グ ラフGP に 変換する．
こ の 結 果 ，R = RA∪ RP が 求 め る 集 合 と な り， GP = (V, A − R, r)が 核回路のト ポ ロジ ーグ ラフ と なる．
Step 1，Step 2におけ る最小化問題はNP完全であ ることが 知られている．そこで ，Step 1の問題に対し て，既存のMFAS（Minimum Feedback Arc Set）を 求めるアルゴ リズム[11]を適用する．このとき，ホー ルド レジ スタに対応する辺（ 以下，ホールド 辺と略す ） を多く選択すれば ，後の計算量が 削減できる．
Step 2の問題を解くヒューリステ ィックアルゴ リズ ムとし て ，Adjustを以下に 示す．
電子情報通信学会論文誌2000/9 Vol. J83–D–I No. 9 Adjust
1. procedure Adjust(GA) begin 2. RP := φ;
3. GT := T ransf orm(GA); 4. while GT(RP) = Adjustable do 5. GS:= Subcircuit(GT(RP)); 6. Calcweight(GS);
7. if¬Check Adjustable(GS) then begin 8. aF := Select(GS);
9. RP := RP∪ {aF}; 10. GS:= Redraw(GS, RP);
11. end
12. end
13. RP := RP∪ L Select(GR); 14. end RETURN RP;
Step 1で 得られ たト ポ ロジ ーグ ラフGA の 任意の 入 出 力 頂 点の 対に ついて ，その 頂 点 間に 存 在す る 頂 点 集合と 辺 集合か ら 導 出され る部分グ ラフ GS を 求 め ，GSが 条件CMを満たすまで ，その時点でのハー ド ウェアオーバヘッド が 最小となるように スキャンレ ジ スタを 決定する．この処理を ，得られ るすべての部 分グ ラフについて 繰り返し 実行する．なお，GT(RP) は ，グ ラフ GT から 辺集合RP を 取り除いて 得られ るグ ラフを 表す．以下，主な手続きについて説明する．
（1） Calcweight
部分グ ラフGSのすべての辺aについて重み(l, r) を求める．l, rはそれぞれ ，出力側に一番近いホールド 辺の終点（ 出発点と呼ぶ ）と辺aの終点間，辺aの始 点と出力頂点間に 存在するすべての経路において ，他 の経路には含まれないホールド 辺を含む経路数を表す．
l, rは，以下に示す3通りの値をとる．1）l, r = 0： すべての経路にホールド 辺は含まれない（ 条件CM(1)）． ただし ，r(a) = h ∨ r = 0 の 場合 ，すべて の 経 路は ホールド 辺aを通る．2）l, r = 1：任意の経路対につ いて ，それぞれの経路に 含まれ るホールド 辺の集合が
（a）等し い，または ，（b）包含関係が 成り立つ（ 条件 CM(2)）．3）l, r > 1：任意の 経路対に ついて ，それ ぞれの経路に含まれ るホールド 辺の集合に 包含関係は 成立し ない．このとき，l, rは ，包含関係が 成り立た ない経路数を表す．また ，重みを 求める際，辺aを選 択するためのハード ウェアオーバヘッド を求める．辺 aに 隣接するすべての入射辺，出射辺それぞれのハー ド ウェアオーバヘッド の和cin(a)，cout(a)とc(a)の
三つの 値を比較し ，その 最小値とする．
今，図7の辺x = (3, 4)の重みについて考える．入力 頂点15から辺xまでに存在する3種類の経路に含まれ るホールド 辺の集合はそれぞれ ，p1= {b}，p2= {a}， p3 = {c}であ る ．このと き，ど の 集合も 包含関係が 成り立たな いのでl = 3とな る．同様に ，辺xから 出力頂点7までの3種類の 経路に ついて ，p1 = {e}， p2= {e, f, g}，p3= {g}である．ここで ，p2⊃=p3 で
あるので ，p2とp3を1種類とみなすと，包含関係の成 り立たない経路数はr = 2となる((l, r) = (3, 2))．ま た，辺xを選択する場合のハード ウェアオーバヘッド c(x)は，min{cin(x) = 7, cout(x) = 5, c(x) = 1} = 1 となる．
（2） Check Adjustable
部分グ ラフGSが 条件CMを 満たし て い るか を 調 べる．l, r > 1，または ，一方が1，他方が2以上であ れば ，条件CMを 満たす 包含関係は 成立し ない ．l, r が ともに1のとき ，ど ちらか 一方が 上述の（a）で あ れば ，他方に 関係な く包含関係が 成立するが ，l, rが ともに（b）の場合，包含関係は成立し ない．し たがっ て ，(1, 1)の場合，常に 条件CMを満たすとは 限らな い．このような場合，重み(0, ∗), (∗, 0)(∗ > 1)をもつ ホールド 辺に 注目する．一方が0であれば ，それ 以降
（ 以前 ）の 経路は 必ず その ホールド 辺を 通るため ，他 方の 値はそれ 以上増加し ない．つまり，0でない値は 部分グ ラフ中に 存在するすべての経路について，他の 経路には 含まれ な いホ ールド 辺を 含 む経路数を 表す． ゆえに ，(1, 1)の矛盾も当然この値に 現れ る．
以上より，重みの取り得る値の条件CLを示す．
図7 無閉路なトポロジ ーグ ラフGA
Fig. 7 Acyclic topology graph GA.
［ 条件CL］
i） r(a) ∈ Z+の場合，(1, 1)∨(∗, 0)∨(0, ∗)(∗ >= 0) ii） r(a) = hの場合，(1, 1) ∨ (1, 0) ∨ (0, 1)
（3） Select
スキャンレジ スタ選択は 以下の二つの ステップから なり，1回の実行で 一つのレジ スタを 選択する． Step 1 重み(l, r)について，l, rがともに2以上のす べての辺に対し ，lr/c(a)が 最大である辺を選択する． Step 2 重み(l, r)に ついて ，l, rのいずれかが1以 下であるすべての辺に対し ，lrが 最小である辺を選択 する．ただし ，lr > 1とする．
重み(l, r)(l, r > 1)をもつ辺を選択すれば ，その辺 の終点と出力頂点間，出発点とその辺の始点間に 存在 するすべての辺について ，少なくとも，包含関係の成 り立たな い 経路が l, r個減少する ．し たが って ，l, r が 大きい辺を選択すると ，各辺の重みへの影響が 大き い．一方，l, rのど ちらかが1以下になった場合，ホー ルド 辺で ，かつ，lrが 小さいものから 選択する．重み (1, r)について ，条件CMを満たすためには ，少なく ともr <= 1でなければ いけない（r = 1は 必ずし も条 件CMを満たさな い ）．rが 大きいと い うことは ，そ れ よりも小さい値をもつ辺に比べ，より出発点に 近い ことを意味する．し たが って，小さい値をもつ辺を選 択すれば ，そのために 重みが 減少する辺の 数が 増え ， より速く1以下になると期待できる．逆に ，大きい値 を選択すると ，出発点とその辺間に 存在するすべての 辺に 関し ては解決するが ，それ 以下の値をもつ辺は 依 然とし て未解決のままである．ホールド 辺のみを 対象 とする理由は ，同じ 重みのロード 辺を選択し ても，必 ずし もホールド 辺の重みが 解決するとは 限らないから である．(l, 1)に 対し ても同様である．
また ，このとき，出発点に接続するホールド 辺を選 択 す るの も 一つの 解で あ る ．し かし ，最 悪すべ て の ホールド 辺が 選択され ることがある．
その他の手続きについて ，Redrawは ，それ までに 得られ た 辺集合RP をGA から 取り除き，グ ラフ を 再構成する．このとき，新し くできる入出力頂点は 別 の部分グ ラフとなる．また ，L Selectは ，GSが条件 CM(1)を 満たし て いな い場 合 ，ハード ウェア オ ーバ ヘッド 最小のロード 辺をGSが 条件を満たすまで一つ ずつ撰択する．
今，無閉路なト ポロジ ーグ ラフGA（ 図7）に 対し
（GA に おいて ，太線はホールド 辺を 表し ，( )で 表す
図8 核回路のトポロジ ーグ ラフGP
Fig. 8 Kernel for GP.
数字は ，その辺を スキャン 化する際のオーバヘッド を 示す ），Adjustを適用し た結果得られ る核回路のト ポ ロジ ーグ ラフを図8に 示す．このとき，求める辺集合 はRP = {(3, 4), (1, 3), (1, 8)}となり，ハード ウェア オーバヘッド は3となる．
また ，Adjustを 適用する部分グ ラフ の 順番も 重要 である．ここでは ，元のグ ラフに 存在するホールド 辺 数に 対し ，部分グ ラフに 含まれ るホールド 辺数が 多い ものを優先する．その 結果，異なるホールド 辺を含む 経路に 重複し て現れ る辺が 最初に 選択され ることにな り，早い段階で 条件を満たす可能性が 高くなる．
4. 3 時間計算量
本 手 法は ，入 出 力 頂 点 対か ら 得られ るすべ て の 部 分グ ラ フ に 対し Adjust を 適 用 す る ．T ransf orm は 必 ず し も 必 要 で は な い が ，簡 単 化 を 行 う こ と で 後の 処 理が 簡 単に な る ．T ransf orm，Calcweight， Check Adjustable，Select，Redraw，L Selectは ， 各辺をそれぞれ一度ずつ調べるだけでよいため，O(m) で で き る (m = |A|)．また ，一つの 部 分グ ラフ に 対 し ，各手続きは 最悪m回繰り返され ，部分グ ラフの 総数はO(n2)であるため ，Adjustに要する計算量は O(n2m)となる．
5. む す び
本論文では ，ホールド レジ スタを 含む無閉路順序回 路に 対する組合せテ スト 生成可能な時間展開モデ ルを 提案し ，更に ，最大展開モデルを有する（ 最大テスト 可能な ）順序回路の一つの クラスとし て ，経路調整可 能な回路を示し た ．更に ，核回路が 経路調整可能とな るような部分スキャン 設計法を提案し た ．今後の課題 とし て ，経路調整可能な回路クラスより大きな，最大
電子情報通信学会論文誌2000/9 Vol. J83–D–I No. 9
テ スト 可能な回路クラスを探すことが 挙げ られ る．こ れにより，部分スキャン 設計において ，ロード レジ ス タを ホールド レ ジ スタに 変更すること も可 能に な り， ハード ウェアオーバヘッド の削減が 期待できる．
謝辞 本研究に 関し ，多くの貴重な御意見を頂いた 本学の増澤利光助教授，井上美智子助手，大竹哲史助 手，並び に ，情報論理学講座の諸氏に 感謝し ます．本 研究は 一部，文部省科学技術研究費補助金・基盤研究 B（2（ 課題番号） 09480054），及び ，奨励研究（A（ 課） 題番号09780280）の研究助成による．
文 献
[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, no.4, pp.544–548, April 1990.
[4] D.H. Lee and S.M. Reddy, “On determining scan flip-flops in partial-scan design approach,” Proc. Int. Conf. Computer-Aided Design, pp.322–325, Nov. 1990.
[5] R. Gupta, R. Gupta, and M.A. Breuer, “The BALLAST methodology for structured partial scan design,” IEEE Trans. Comput., vol.39, no.4, pp.538– 544, April 1990.
[6] 藤原秀雄，大竹哲史，高崎智也，“組合せテスト生成複雑 度で テスト 生成可能な 順序回路構造とその 応用，” 信学論
（D-I），vol.J80-D-I, no.2, pp.155–163, Feb. 1997. [7] R. Gupta and M.A. Breuer, “Testability properties of
acyclic structures and applications to partial scan de- sign,” Proc. IEEE VLSI Test Symp., pp.49–54, 1992. [8] T. Inoue, T. Hosokawa, T. Mihara, and H. Fujiwara,
“An optimal time expansion model based on com- binational ATPG for RT level circuits,” Proc. IEEE 7th Asian Test Symp., vol.39, no.4, pp.190–197, April 1998.
[9] 三原隆宏，井上智生，藤原秀雄，“L/H 型レジスタを考慮 し た組合せATPG に基づく RT レベル部分スキャン設計 法，” 信学技報，FTS96-67, Feb. 1997.
[10] 佐野ちいほ ，ホールド 機能を考慮し た順序回路のテスト 容 易化設計に 関する研究，奈良先端科学技術大学院大学修士 論文，NAIST-IS-MT9751051, Feb. 1999.
[11] S.T. Chakradhar, A. Balakrishnan, and V.D. Agrawal, “An exact algorithm for selecting partial scan flip-flops,” Proc. 31th ACM/IEEE Design Au- tomation Conf., pp.81–86, June 1994.
（ 平成12 年 1 月 21 日受付，3 月 28 日再受付）
佐野ちいほ （ 学生員 ）
平9 四国大・経営情報・情報コース卒． 平11 奈良先端大博士前期課程了．現在奈 良先端大博士後期課程に 在学中．テスト 生 成，テスト 容易化設計に関する研究に従事．
三原 隆宏
平8 岡山大・工・情報卒．平 10 奈良先 端大博士前期課程了．同年三菱電機コント ロールソフト ウェア（ 株 ）に 入社．
井上 智生 （ 正員 ）
昭63 明大・工・電子通信卒．平 2 同大 大学院博士前期課程了．同年松下電器産業
（ 株 ）入 社．明治大大学院博士後期課程を 経て，平5 奈良先端大情報科学研究科助手． 平11 より広島市立大学情報科学部助教授． 松下電気電器産業（ 株 ）に おいて マイクロ プ ロセッサの研究開発に 従事．明治大，奈良先端大，広島市大 に おいて ，テスト 生成，並列処理，テスト 容易化設計に 関する 研究に 従事．博士（ 工学 ）．IEEE，情報処理学会各会員．
Debesh K. Das
Jadavpur University 卒．同大大学院博 士課程了．現 在同大学準教授．1998 日本 学術振興会特別研究員（ 奈良先端大客員研 究員 ）．論理合成 ，テ スト 生成に 関する研 究に 従事．
藤原 秀雄 （ 正員 ）
昭44 阪大・工・電子卒．昭 49 同大大学 院博士課程了．阪大工学部助手，明治大理 工学部教授を経て，現在奈良先端大情報科 学研究科教授．昭56 ウォータールー大客 員助教授．昭59 マッギル大客員準教授．論 理設計，高信頼設計，設計自動化，テスト 容 易 化 設計 ，テ スト 生 成 ，並 列処 理 ，計 算 複 雑度に 関す る 研 究に 従事．著書に“Logic Testing and Design for Testabil- ity”（ The MIT Press）など ．工博．情報処理学会会員．IEEE Fellow，IEEE Golden Core Member．
