J106 j IEICE 2003 9 最近の更新履歴 Hideo Fujiwara J106 j IEICE 2003 9

論 文

ホールド と ス イッチの機能を考慮し た 内部平衡構造

神野 元彰

井上美智子

藤原 秀雄

Internally Balanced Structure with Hold and Switching Functions

あら まし 本論文では ，ホールド と スイッチの機能を考慮し て ，内部平衡構造を拡張し た順序回路のクラスで ある内部切換平衡構造を提案する．提案するクラスは ，組合せテ スト 生成複雑度でテ スト 生成可能であり，平衡 構造，内部平衡構造，切換平衡構造の順序回路のクラスを真に 含む．本論文では ，内部切換平衡構造順序回路に 対し て ，(1) 組合せ論理部の故障に対して組合せテスト生成複雑度でテスト生成可能であることを示し ，(2) ホー ルド レジ スタ及び スイッチの故障に 対し て検出可能となるための十分条件と故障検出率の実験的評価を示し ，₍₃₎ 計算量に 基づ く組合せテ スト 生成複雑度に 関し て考察する．

キーワード 平衡構造，内部平衡構造，切換平衡構造，組合せテ スト 生成複雑度，テ スト 生成

1. ま え が き

順序回路のテ スト 生成は 一般に 困難な 問題で あ り， 回路規模が 大きくなると実用的な時間で 解けなくなる 場合が 多い_[2]．完全スキャン 設計法では ，スキャンレ ジ スタを取り除いた残りの回路（ 核回路と呼ぶ ）に対 し て組合せ回路用のテ スト 生成アルゴ リズムが 適用可 能であるが ，ハード ウェアオーバヘッド は大きくなる． 一方，部分スキャン 設計法では ，核回路にレジ スタが 残るため ，一般には ，順序回路用のテ スト 生成アルゴ リズムを適用し なければ ならない．完全スキャン 設計 法の利点を保持し たままハード ウェアオーバヘッド を 削減するために ，組合せ回路用のテスト 生成アルゴ リ ズムでテスト 生成が 可能な順序回路のクラスが 提案さ れている_{[1], [3]}∼_[8]．

平衡構造，内部平衡構造，切換平衡構造は ，組合せ 論理部に 対し ，組合せテ スト 生成複雑度でテ スト 生成 可能_[3]な 順序回路のクラスであ る．レジ スタとし て ロード レジ スタだけを考え る場合，順序回路の回路構 造には ，｛ 無閉路構造順序回路 ｝_⊃｛ 内部平衡構造順序 回路 ｝_⊃｛ 平衡構造順序回路 ｝とい う関係が ある ．一

†奈良先端科学技術大学院大学情報科学研究科，生駒市

Graduate School of Information Science, Nara Institute of Science and Technology, 8916–5 Takayama-cho, Ikoma-shi, 630–0192 Japan

∗現在，三菱電機株式会社

方，有限状態機械を実現可能性で分類すると，｛ 無閉路 構造実現可能な 有限状態機械 ｝₌｛ 内部平衡構造実現 可能な 有限状態機械 ｝_⊃｛ 平衡構造実現可能な 有限状 態機械 ｝となる_[3]．文献_[5]の 平衡構造順序回路に 関 する定義では ，レジ スタとし てロード レジ スタとホー ルド レジ スタを 考慮し て いるが ，文献_[3]の内部平衡 構造順序回路に 関する定義では ，レジ スタとし てロー ド レジ スタだけを考慮し ている．

本論文では ，内部平衡構造の定義がホールド レジ ス タを含むように拡張する．更に ，切換平衡構造と同様 に ，ス イッチの機能を考慮し て内部平衡構造を拡張し た内部切換平衡構造を提案する．内部切換平衡構造は ， 組合せ論理部に 対し ，組合せテスト 生成複雑度でテス ト 生成可能な 順序回路のクラ スであり，平衡構造_[5]， 内部平衡構造_[3]，切換平衡構造_[4]を真に 含むクラス である．故障とし て信号線の縮退故障を考える．まず， 内部 切 換 平 衡 構 造 順 序 回 路が ，ホ ールド レ ジ スタの 制御信号線，スイッチ以外の故障に 対し ，組合せテ ス ト 生成複雑度でテ スト 生成可能であることを示す．ま た，平衡構造_[5]，切換平衡構造_[4]では 考慮され てい なか ったホールド レジ スタの 制御信号線，スイッチの 故障に 対し ，検出可能で あ るための 十 分条件を 示す． 更に ，この十分条件だけで ，ホールド レジ スタの制御 信号線，ス イッチの故障に 対し ，高い故障検出率が 得 られ ることを実験的に 評価する．

本論文では まず，拡張組合せ変換により順序回路の

682 D– Vol. J86–D– No. 9 pp. 682–690 2003 9

テ スト 生成問題が 組合せ回路のテ スト 生成問題に 帰着 する回路を組合せテスト 生成複雑度でテスト 生成可能 な順序回路と定義し 議論する．5.では，更に ，文献_[3] で 提案され た計算量に 基づ く組合せテ スト 生成複雑度 に 関し ても，組合せテ スト 生成複雑度でテ スト 生成可 能であることを示す．

2. 内部切換平衡構造

2. 1 諸 定 義

順序回路Sは ，組合せ論理部，レジ スタ，スイッチ からなる．組合せ論理部はレジ スタ，スイッチ，外部入 力，外部入力の分岐枝に 接続する連結し た極大な組合 せ回路部分とする．レジ スタには ，ホールド レジ スタ とロード レジ スタが ある．ホールド レジ スタは ，値を 保持するホールド モード（ 制御信号の値₀）と，値を取 り込むロード モード （ 制御信号の値₁）をもつ ．ロー ド レジ スタは 常にロード モード で 動作する．ス イッチ は ，マルチプレ クサやバ スであ る．レジ スタ，ス イッ チの制御信号及び クロック信号は ，独立に 外部から直 接印加され るとする．また ，経路に含まれ るレジ スタ の個数をその 経路の順序深度と呼ぶ ．本論文では ，組 合せテスト 生成複雑度でテ スト 生成可能な順序回路の クラスとし て無閉路順序回路を考え る．以下，順序回 路とし て無閉路順序回路のみを 考え る．まず，分離可 能性を 定義する ．本論文では ，文献_[3]で 定義され た 分離可能性を拡張する．

［ 定義₁］（ 分離可能性 ）_xを外部入力，_yi と_yjを x^{の分岐枝とし ，}z^をyi^とyj^{から到達可能な任意の}

外部出力とする．_yiと_yjから_zに至る任意の経路対 に 対し ，一方の経路にのみ存在するホールド レジ スタ が 存在するか ，または 外部入力に 最も近いホールド レ ジ スタまたは外部出力までの順序深度が 異なるならば ， yi^とyj^{は 分離可能という．} ✷

［ 定義₂］（ 拡張組合せ変換 ）以下の₂操作を行う．

（₁）外 部 入力 分離：外部 入力 _xの 分 岐枝の 集 合 を_Y とする ．分岐枝_ya と_ybが 分割 _Πの 異なるブ ロック_Y(i)，_Y(j)に属する（_{ya∈ Y (i)}，_{yb∈ Y (j);} Y(i) |= Y (j)^）ならば ya^とyb^{は分離可能であるとい}

う条件を満たす_Y の最小分割_Πを求める．分割し た 各ブ ロックご とに 新たに 外部入力を設けて ，_xを分離 する．

（₂）組合せ変換：各レジ スタを同じビ ット 幅の信

号線に置き換え る． _✷

順序回路_Sに対し ，外部入力分離操作のみ，及び 拡

図1 順序回路；(a) S（ 内部切換平衡構造），(b) S^∗（ 切 換平衡構造 ），(c) C^∗(S)

Fig. 1 Sequential circuits: (a) S (internally switched balanced structure), (b) S^∗ (switched bal- anced structure, (c) C^∗(S).

張組合せ 変換を 適用し た結 果の 回路は 一意に 決まる ． それらを ，それぞれ _S^∗，_C^∗_(S)と表す（ 図₁）．

［ 定義₃］（ 組合せテ スト 生成複雑度で のテ スト 生成 可能性 ） _Sを無閉路順序回路，_fを_Sの故障とする． C^∗(S)^にf^{に 対応する故障}fC^{が 存在し ，}f^がS^で

検出 可能で あ るた めの 必 要 十分条 件が _fC が _C^∗_(S) で検出可能であるならば ，_Sは_fに対し て，組合せテ スト 生成複雑度でテスト 生成可能であるという．_✷

2. 2 内部切換平衡構造

まず，トポロジ ーグ ラフと切換平衡構造を定義する．

［ 定義₄］（ 順序回路_S に 対す るト ポ ロジ ーグ ラフ ） 順序回路_S の組合せ論理部，スイッチ，外部入力，外 部出 力を それ ぞ れ 頂 点とし ，頂 点 間の 接 続 関 係を 有 向辺とし た有 向グ ラフを_S のト ポ ロジ ーグ ラフ と い う．トポロジーグ ラフの辺は信号線，ロード レジ スタ， ホールド レジ スタを 表す．トポロジ ーグ ラフの経路に

電子情報通信学会論文誌2003/9 Vol. J86–D–I No. 9

図2 トポロジーグラフ Fig. 2 Topology graph.

含まれ るロード レジ スタ辺及び ホールド レジ スタ辺の 個数を，その 経路の順序深度と呼ぶ ． _✷ 図₂に ，図_{1 (b) S}^∗のト ポロジ ーグ ラフを示す．

［ 定義₅］（ 切 換 平 衡 構 造 ） 順 序 回 路 _S のト ポ ロ ジーグ ラフ_GSに対し ，以下が 成り立つならば ，_Sは 切換平衡構造であるという．

（₁）_GSは 無閉路である．

（₂）任意の頂点対_{u, v}に 対し ，_uから _vへのす べての経路が ，順序深度が 等し い，若し くは頂点_uと は 異なる同じ ス イッチ頂点_mを通過する．

（₃）任意の頂点対_{u, v}に 対し ，_uから _vへのあ る経路上にホールド レジ スタ_hが 存在するならば ，_u から_vへのすべての経路が_hを 通過する，若し くは u^からvへのすべての経路が 頂点_uとは 異な る同じ

スイッチ頂点_mを通過する． _✷

［ 定義₆］（ 内部切換平衡構造 ） 順序回路_Sへの外部 入力分離操作の結果得られ る_S^∗が 切換平衡構造であ るならば ，Sは内部切換平衡構造であるという．_✷

図_{1 (a)}の順序回路_Sは ，_S^∗（ 図_{1 (b)}）が 切換平 衡構造となるので ，内部切換平衡構造である．

3. 組合せテスト 生成可能性

順序回路_S が 内部切換平衡構造ならば ，レ ジ スタ 及び ス イッチのデ ータ 入 出力信号 線 ，組合せ 論理部 ， 外 部入 力の 故 障に 対し ，_S は 組 合せテ スト 生 成 複雑 度でテスト 生成可能であることを示す．ここで ，_Sの 故障_f は ，_C^∗_(S)の同じ 信号線に 対する故障_fCに 対応する．ただし ，_Sの外部入力_xが_C^∗_(S)で 外部 入力_{x1,· · · , xm} に 分離し た 場合は ，_xの 故 障_f は ， x1,· · · , xm^{の多重故障}fCに対応する．テストパター ン_TCの入力_xの値を_TC(x)，テスト 系列_T の入力 x^の時刻t^の値をT(x, t)^と表す．

［ 補題₁］_S を 内部切換平衡構造順序回路とする ．_S のレジ スタのデ ータ入出力信号線，ス イッチのデ ータ 入出力信号線，組合せ論理部，外部入力の縮退故障_f が 検 出 可 能で あ るならば ，_f に 対 応す る 故 障 _fC は C^∗(S)^{で 検出可能である．}

図3 ^TからTC への変換 Fig. 3 Transformation from T to TC.

（ 証明 ） _Sに おけ る_f のテ スト 系列_T を _C^∗_(S)に おけ る_fC のテ スト パターン_TCに 変換する．

T ^の長さをlT ^{とし ，}f^{は 時刻}lT ^{に 外部出力}z^に

誤りを 伝搬するとする．_C^∗_(S)の各外部入力_xに 対 し て ，_T の_xに 対応する_Sの外部入力のど の時刻の 値が ，時刻_lT における_zの値に影響するかを考える． この 値が 各xに 対し て 一意に 決まれば ，T に おけ る その 時刻の値を割り当てることによって _TCを作るこ とができる．

S ^{に おけ る時刻}lT ^のz の 値に 影響する時刻を_S^∗

を用いて 求め る（ 図₃参照 ）．_aを 組合せ論理部，ス イッチ，レジ スタ，外部入力，及び 外部出力とし ，時 刻_taでの_aの出力値が 時刻_lT におけ る_zの値に 影 響することを_{a, ta}と表す．

z, lTをキューに 入れ ，以下をすべての外部入力に 時刻が 求まるまで 繰り返す．

（₁）キューから 一つの 要素_{a, ta}を取り出す．

（₂） _aが 外部入力でないとき，_aの入力に 接続す る任意の組合せ論理部，スイッチ，レジ スタ及び 外部 入力を_a^′とする．

• aがホールド レジ スタの場合

時 刻 _t で の _a の 制 御 信 号 線 の 値 を _ct と す る ．時 刻_ta で の _a の 値を ロ ード し た 時 刻を _t^′ と す ると ， t^′= max{t|(t < ta) ∧ (ct= 1)}^となる．t^{′の値が 決}

まらない場合，_t^′_{= −∞}とする．_a^′_{, t}^′_をキューに 入れ る．

• aが ロード レジ スタの場合

a^′, ta− 1をキューに 入れ る．

• aが 組合せ論理部または ス イッチの場合

a^′, taをキューに 入れ る．

a^′が スイッチの場合，時刻_taの制御信号線の 値に

よって選択されない入力にのみ到達可能な部分回路を

削除する．_Sは内部切換平衡構造であり，また，スイッ チは 制御信号により選択され た入力だけを考慮し てい る．よって，再収

れん

斂する経路の順序深度は 等し く，ま た ，再収斂する経路のある経路にホールド レジ スタ_h が 存在する場合，他のすべての経路にこの_hが 含まれ る．これ より，_z から _a^′ への複 数の経 路が 存在し て も_a^′_{, t}^′_の値は一意に 決まる．

S^{∗の外部入力}x^がS^{の外部入力}x^{′から 分離し た}

とする．外部入力_xに対し_{x, tx}ならば ，_{TC(x) =} T(x^′, tx)^{とする．スイッチ}m^に対し m, tm^{ならば ，} m^{の制御信号線}cm^{に対し ，}TC(cm) = T (cm, tm)^と

する．時刻が 決まっていない外部入力の値や ス イッチ の制御信号線の値は ，ド ント ・ケアとする．

このよ うにし て決まる_TCは ，_C^∗_(S)におけ る_fC

を検出することがわかる． _✷

以下の補題は ，スイッチの故障も対象とする．

［ 補題₂］_S を 内 部 切 換 平 衡 構 造 順 序 回 路 と す る ． C^∗(S)のレジ スタのデ ータ入出力信号線，組合せ論理

部，外部入力，ス イッチの縮退故障_fCが 検出可能で あ るならば ，_fC に 対応する故障_f が_S で 検出可能 である．

（ 証明 ）_C^∗_(S)におけ る_fCのテストパターン_TCを S^{におけ る}f^{のテ スト 系列}T ^{に 変換する．}

fC に よる 誤りが 外部出力_z に 伝搬され ると する ． S^∗のz に 対する出力錘に おいて ，_TC に よって 各ス

イッチで 選択され る経路だけを考えた部分回路に 対す るト ポ ロジ ーグ ラフ を_G^′と する ．ただし ，故障_fC が スイッチ_mの故障の場合は ，_mのすべての入力を 考慮する．このとき，_mの複数の入力に対し て，それ らに 到達可能な_G^′の部分グ ラフに 共通部分があれば 複製し ，それらが 共通部分をもたないよ うに 修正し た グ ラフを_G^′ と する（ 図_{4 (a)}）．_G^′ は 切換平衡構造 のトポロジ ーグ ラフで ，かつス イッチで 再収斂する経 路をもたないので ，頂点_u，_v間のある経路がホール ド レジ スタを もたなければ ，_u，_v 間のすべての 経路 はホールド レジ スタを含まず，その順序深度は等し い． 頂点_u，_v間の経路を ，その順序深度と同数のロード レ ジ スタ 辺か ら な る 経 路で 置き 換え る ．この 操 作を ホールド レジ スタをもたない再収斂経路がなくなるま で 繰り返し たグ ラフを _Gと する（ 図 _{4 (b)}）．_G^′は ， 異なるロード レジ スタ辺を通る再収斂経路をもたない ので ，_Gは 木構造となる．

各レジ スタ辺に_zに誤りを伝搬させるために必要な 値を何時間保持するかを表す重みを割り当てる．ロー

図4 ^TC からT_{への変換：(a)G}^′_，(b)G Fig. 4 Transformation from TCto T ; (a)G^′, (b)G.

ド レジ スタの重みを₁とする．ある経路上のすべての レジ スタの重みの和を経路重みという．以下，ホール ド レジ スタの 重みを 割り当てる．

外部入力から 外部出力に 至る経路で ，ホールド レジ スタ辺を含まない経路の最大の経路重みを_dmaxとす る．なければ ，_{dmax= 0}とする．

外部入力から 外部出力に 至りホールド レジ スタ辺を 含む経路に 対し ，経路に 含まれ るホールド レジ スタ辺 の個数の昇順に ，ホールド レジ スタ辺の個数が 等し い 場合は 順序深度の昇 順に ，経路_P を選択し ，以下を 行う．ホールド レジ スタ辺の個数，順序深度がともに 等し い経 路は 任意の 順序で 選 択す る ．_P の 経 路重み WP ^{が ，}WP ^>_{= d}max+ 1となるように ，各ホールド

レジ スタ辺に₁以上の重みを 割り当て る．このと き， 経路上のホールド レジ スタ辺の集合が 等し い他の経路 の経路重みも同時に 決まる．ここで ，_Gは 木構造なの で ，経路上のホールド レジ スタ辺の集合が 等し い経路 のみ同時に決まる．経路の選択順序より，これらは_P と同数以上のロード レジ スタ辺をもつので ，経路重み は_WP 以上とな る．_S の 同一の 外部入力から 分離し た_S^∗の異なる外部入力を始点とする経路の経路重み が 同時に 決まる場合は ，分離可能性の条件より，それ らは 外部入力に最も近いホールド レジ スタまでの順序 深度が 異なるので経路重みは 異なる．経路重みが 決ま る経路の最大の経路重みを_dmaxとする．

すべての経路に対する経路重みが 定まった時点での dmaxに 対し ，テスト 系列長_lT を_{lT = dmax+ 1}と する．_Gにおけ る頂点_v，辺_aの始点となる頂点から zに 至る経路の経路重みをそれぞれ_Wv，_Waとする．

G^{の 外部入力頂点}x^{が ，}C^∗(S)^{の 外部入力}x^′，S の外部入力_x^′′に対応するとする．_T(x,^′′_{lT− Wx) =} TC(x^′)^とする．S の同一の外部入力から 分離し た_S^∗ の異なる外部入力から_zまでの経路の経路重みは相異 なるので ，衝突なく値を割り当てることができる．

電子情報通信学会論文誌2003/9 Vol. J86–D–I No. 9

Gの 各ホ ールド レジ スタ辺_hの 重みを_wと する． Sの対応するホールド レジ スタ_rの制御信号を，時刻 (lT−Wh)^の値を1^，区間[lT−Wh+1, lT−Wh+w−1]

の値を₀に決める．ただし ，_hが 複製され ，同じ 時刻 に₀と₁の両方の値を割り当てようとする衝突が 起き る場合は ，その 時刻の値をド ント ・ケアとする．レジ スタ_rに値を取り込むのは ，_rのデ ータ入力線の値が ， C^∗(S)^にTCを印加し た 場合のその 信号線の 値 _vと

なるときである．よって ，制御信号の値に 衝突が 起き る場 合 ，デ ータ 入 力線 ，レ ジ スタの 値が と もに_vと なっているので 制御信号線の値は₀でも₁でもよい ．

スイッチ_mの制御信号線を_cmとする．_T での_cm の値を _TC(cm)に 固定する．それ 以外の値はド ント ・ ケアと決める．

以上のようにし て決まる_T は_Sにおける_fを検出

することがわか る． _✷

［ 定理₁］_S を 内部切換平衡構造順序回路とする ．_S のレジ スタ及び スイッチのデ ータ入出力信号線，組合 せ論理部，外部入力の故障に 対し ，_Sは 組合せテ スト 生成複雑度でテ スト 生成可能である．

（ 証明 ） 補題₁と補題₂より，成り立つ． _✷ S^{の分離する各外部入力}xに対する故障は ，組合せ

回路_C^∗_(S)で_xが 分離し た全外部入力に 対する多重 故障に 対応する ．文献_[6]では ，組合せ回 路の複 数の 外部入力の多重故障のテ スト 生成問題を ，それら 複数 の外部入力に 対する単一故障のテ スト 生成問題に 帰着 し た ．よって ，内部切換平衡構造順序回路の組合せ論 理部の単一故障に 対するテ スト 生成問題は 組合せ回路 の単一故障のテ スト 生成問題に 帰着する．

次に ，ス イッチの 故 障を 検 出 す る た めの 十 分 条 件

（ 補題₂）が 必要条件ではないことを示す．

［ 補題₃］_S を 内部切換平衡構造順序回路とする ．_S のスイッチの故障_fが 検出可能であるが ，_fに対応す る故障_fCは_C^∗_(S)で検出可能でないことがある．

（ 証明 ） 図₅のス イッチ_M の二つの入力を_m1，_m2 と する ．図 _{5 (a)}で は ，テ スト 系列 T = (01, 11)^を x1^，x2 ^{に 印加すれば ，}M ^に(m1m2) = (01)^を印加

す るこ とが で き ，_M の 制 御 信 号 線の 縮 退 故 障 _f を 検出できる．し かし ，図_{5 (b)}の_C^∗_(S)では ，_M に (m1m2) = (00), (11)のパターンし か 印加することが

できず，fC^{を検出できない．} _✷

ホールド レジ スタの故障に 対し て，検出可能である ための十分条件を示す．

［ 補題₄］_Sのホールドレジ スタ_hに対応する_C^∗_(S)

図5 スイッチの故障 Fig. 5 Faults in a switch.

の信号線を_iとする．_C^∗_(S)において ，_iの₀縮退故 障と₁縮退故障がともに 検出可能であるならば ，hの 制御信号線の故障は 検出可能である．

（ 証明 ） _hの入力信号線，出力信号線をそれぞれ_hin， hout^{とする．補題}2^{において，}i^{のテスト パターンを}

変換し て得られた_hinの₀縮退故障，₁縮退故障のテ スト 系列を_T0，_T1とする．このとき，_T0は_houtの 0縮退故障のテ スト 系列でもある．_T0，_T1はそれぞれ

長さが_l0，_l1であり，外部出力_z0，_z1 に 誤りを伝搬 するとする．また ，_T0 において 時刻_l0の_z0 の 値に 影響するhin^，hout^{の値の時刻を}t0^，t^′₀とし ，T1^に

おいて時刻_l1の_z1の値に影響する_hinの値の時刻を t1^とする．

（₁）_hの制御信号線の₀縮退故障

故障時に_hは 常にホールド モード で 動作するので ， 常にその 初期値を出力する．これは ，iの₀縮退故障， または₁縮退故障と 等価とみなすことがで きるので ， T0^とT1を印加することによって検出可能である．

（₂）_hの制御信号線の₁縮退故障

T0 ^{に おいて ，時刻}t^′₀ ^のhoutの値が 正常時と 故障

時で 異なれば _z0 で 異な る出力を 得ることがで き，故 障が 検出可能となる．そこで ，以下の場合に 分けて考 える．

• T0^{において 時刻}t^′₀− 1^のhin^の値が0^の場合 T0^はhout^の0縮退故障のテスト 系列であるので ，正 常時，時刻_t^′₀の_houtの値を₁とする．故障時，時刻 t^′0− 1^のhin^の値が0^{となるので ，時刻}t^′0^のhout^の

値は₀となる．

• T0^{において 時刻}t^′₀− 1^のhin^の値が1^の場合 T^′ = T1T0 ^{と し ，}T^{′ の} h の 制 御 信 号 線 の 区 間 [t1 + 1, l1 + t^′0 − 1] ^{の 値 を}0と 変 更し た テ スト 系

列を_T とする．_T1は_hinの₁縮退故障のテスト 系列 であるので ，時刻_t1において_hの値を₀にする．正常 時，時刻_{l1+ t}^′₀まで値は保持され るので，時刻_{l1+ t}^′₀ の_houtの値は₀となる．故障時，時刻_{l1+ t}^′_{0− 1}の hin ^の値が0^{となるので ，時刻}l1+ t^′0^のhout^の値は

1^となる． ✷ 4. 実験 評 価

内部切換平衡構造順序回路_S と_C^∗_(S)に 対し てテ スト 生成を 行い，組合せ_ATPGを使 うことの 効果を 評価する ．また ，補題₂，₄で ，ホールド レジ スタの 制御信号線，ス イッチの故障に 対し て ，検出可能であ るための十分条件を示し たが ，この十分条件での故障 検出率を実験的に 評価する．実験には ，ワークステー ションとし てSun Blade 1000を用い，テ スト 生成に は_TestGen（_Synopsys）を 用いた ．対象と す る 回 路 は ，_DP4及び_ISB-RISCである．_DP4は四つのベン チマーク回路_Tseng，_4thIIR，_LWF，_JWFを図₆の ように 接続し た回路を，_ISB-RISCは_RISCのデ ータ パス部を ，それぞれ 核回路が 内部切換平衡構造となる よ うに 部分 スキャン 設計を 行った 結 果の 回路で あ る ． これら核回路の回路特性を表₁に 示す．

回 路 全 体に 対 す る テ スト 生 成 の 結 果 を 表 ₂ に 示 す．_Sは順序回路DP4, ISB-RISC^{を表し ，}C^∗(S)^は C^∗(DP4)^，C^∗(ISB-RISC)^{を 表す．}C^∗(S)^{に 対する} テ スト 生 成に 対し て は ，そ の 結 果 _S に お い て 検 出

図6 回路DP4 Fig. 6 Circuit DP4.

表1 回路特 性 Table 1 Circuit characteristics.

回路名

ビ ット PI PO ^{ホールド ロード} ゲート

幅 レジ スタ レジ スタ

DP4 16 320 304 15 12 24381

ISB-RISC 32 1088 1152 7 12 70248

表2 テスト生成結果 Table 2 Test generation results.

検出可能な故障数 冗長と判定され た故障数

判定が 打ち切られた

回路名 テスト 生成時間(s) 全故障数

C^∗_(S) S C^∗_(S) ^S 故障数

冗長 判定不可能

DP4 ^{S 18476.9 30590 27404 361 2825}

C^∗(S) 1.6 28640 25517 27461 3123 3115 14 0

ISB-RISC ^{S 38251.2 120140 118984 272 884}

C^∗(S) 1952.4 119358 119037 119789 235 137 128 86

可能 ，冗長 ，判定不 可能とな る故障数も示す．_DP4， ISB-RISC^{に 対し ，}C^∗(S)を 用いた テ スト 生成では ， Sに 比べ，より多くの故障が 検出可能となり，テスト

生成時間もそれぞ れ 約_1/10000，_1/20と 大幅に 短縮 した ．また ，_C^∗_(S)で判定不可能となる故障も存在す るが ，_Sと比べてより多くの故障が 検出可能または冗 長と 判定され た ．すなわ ち，組合せ_ATPGを用いて テスト 生成を行 うことにより，より短いテ スト 生成時 間で 高い故障検出率，高い故障検出効率を得ることが できた ．

次に ，ホールド レジ スタの 制御信号線の故障に 対す る結果を表₃に 示す．_DP4に 対し て ，_C^∗_(S)を用い たテ スト 生成では₃₀個中₂₈個の 故障が 検出 可能で あった．_Sに対するテスト 生成を行った結果，残りの 2個の 故障は 冗 長故 障で あ るこ とが わか った ．また ， ISB-RISC^{に対し て，}C^∗(S)を用いたテスト 生成です

べての故障が 検出可能であった ．最後に ，スイッチの 故障に 対する結果を 表₄に 示す．補題 ₁と 等価故障 解析を行い，デ ータ入出力信号線の故障及び その等価 故障の 冗長判定を 行った ．_DP4に 対し て ，_C^∗_(S)を 用いたテ スト 生成で_S の すべての 検出可能な 故障が

表3 ホールドレジスタの故障 Table 3 Faults in hold registers.

回路名 全故障数 検出故障(C^∗(S)) 冗長判定故障 (S)

DP4 30 28 2

ISB-RISC 14 14 –

表4 スイッチの故障 Table 4 Faults in switches.

回路名

故障数

全故障 検出可能 冗長判定 判定打切り

DP4 ^{S 9214 9178 36 0}

C^∗(S) 9214 9178 36 0 ISB-RISC ^{S 38976 38756 207 13} C^∗(S) 38976 38756 220 0

電子情報通信学会論文誌2003/9 Vol. J86–D–I No. 9

検出できた．_ISB-RISCに対し ては ，_C^∗_(S)を用いた テ スト 生成で 検出できない故障は 冗長であると判定で きたが ，_Sに 対するテスト 生成では 一部の故障の判定 が 打ち切られ るとい う結果となった ．

5. 計算量に基づく組合せテスト 生成可能性

5. 1 計算量に関する定義

文献_[3]で 定義され た計算量に 基づ く組合せテ スト 生成複雑度で のテ スト 生成可能性に 関し て 考察する ． ここで ，テ スト 生成問題とし て以下の問題を扱う．

PC（ 組合せテスト 生成問題 ）： 組合せ回路_Cにお

ける故障_fを検出するテストパターンが 存在するかを 判定する問題で ，イン スタン スは 組合せ 回路_Cと 故 障_fである．

Pα^{（ クラス}αテ スト 生成問題 ）： クラス_αの順

序回路_Sに おけ る故障_f を 検出するテ スト 系列が 存 在するかを判定する問題で ，イン スタン スはクラス_α の順序回路_Sと故障_fである．

TC(n)^とTα(n)をそれぞれ テ スト 生成問題PC^と

Pα の計算量とする．ここで ，_nはその 問題の イン ス

タン スの大きさを 表す．

［ 定義₇］（ 帰着可能性 ） 問題_Aに属する任意の イン スタン ス_aの解が ，問題_Bに属する_τ(a)の解と同じ となる変換τが 存在するならば ，問題_Aは 問題_Bに

帰着可能である． _✷

［ 定義₈］（ 計算 量に 基づ く組合せテ スト 生成複雑度 でのテスト 生成可能性 ）

以下を満たす変換_τが存在するならば ，クラス_αは組 合せテスト 生成複雑度でテスト 生成可能であるという．

（₁）_Pαは変換_τによって，_PCに帰着可能である．

（₂）_Tτを変換_τに必要な計算量としたとき，順序 回路のクラス_αに 属する順序回路_Sに 対し て，_Tτ(S のサ イズ_{) = O(TC(S}のサ イズ₎₎かつ_{TC(τ (S)}のサ イズ_{)= O(TC(S}のサ イズ₎₎が 成り立つ． _✷

組合せテ スト 生成複雑度でテ スト 生成可能な順序回 路_S のテスト 生成問題は ，_Sを組合せ回路_τ(S)に変 換し ，_τ(S)に 組合せテ スト 生成アルゴ リズムを 適用 することによって解くことができる．この全体の計算 量は ，組合せテ スト 生成問題の計算量（_=TC(Sの サ イズ₎）以下である．

組 合せ テ スト 生成 問題_PC は_NP完 全で あ る ．し かし ，実際に 設計され る回路のクラスに対し ては ，経 験的に ，回路のサ イズを_nとし たとき，_{TC= O(n}^k₎

（_{k = 2} s ₃）と い わ れ て い る ．組 合 せ テ ス ト 生

成 複 雑 度で テ スト 生 成 可 能 な 順 序 回 路 の ク ラ スは ， TC(n) = O(n³)であると仮定し ，以下考察する．

5. 2 内部切換平衡構造の組合せテスト 生成複雑度 S を 内 部 切 換 平 衡 構 造 順 序 回 路 と す る ．_S の サ

イズ を n と す る と ，C^∗(S) ^{の サ イズ も} n と な り， TC(C^∗(S)^{の サ イズ}) = TC(n)と な る ．よって ，拡 張 組 合 せ 変 換 に 必 要 な 計 算 量 を _TC∗_(n) と す る と ， TC^∗(n) = TC(n)であれば ，内部切換平衡構造順序回

路のクラスは組合せテ スト 生成複雑度でテ スト 生成可 能となる．

拡張組合せ変換の計算量_TC∗_(n)は ，外部入力分離 操 作 ，及び 組 合せ 変 換に 必 要な 計 算 量と な る ．組 合 せ 変 換の 計 算 量は _O(n)で あ る ．外 部 入 力 分 離 操 作 は ，外部 入 力の 分 岐 枝 集 合の 最 小 分 割を 求め る 操 作 であり，入力とし て分岐枝間の分離可能性が 与えられ て いれば ，分 岐 枝を 頂 点とし ，分 離 可 能で な い 頂 点 間を 辺で 接 続し たグ ラフ の す べて の 連 結 成 分を 求め る問題に 帰着でき，計算量は_O(n²₎である．よって ， TC^∗(n) = O(n²)^となる．

し かし ，厳密には ，テ スト 生成問題の入力に ，分岐 枝間の分離可能性は 含まれていない．以下，外部入力 分離操作を実現する一つの 手続きを 示し ，その計算量 の上界を与える．外部入力の分岐枝の総数を_{nf(<= n)}， 外部出力数をno(<_{= n)}と する ．また ，一つの 経路上 に存在するロード レジ スタ，ホールド レジ スタ数の 最 大値をそれぞれ_nl，_{nh(<= n)}とする．

（₁）各分岐枝からロード レジスタ，または外部出力 までの順序深度を求める．経路_Pに対し ，_Pの始点に最 も近いホールド レジ スタまたは終点を_{f irst(P )}，_Pの 始点から_{f irst(P )}までの順序深度をf irst depth(P ) と表す．_S は 無閉路順序回路で あ るので ，_u，_vを 始 点とし ホールド レジ スタを 含む二つの経路_Pi，_Pjに 対し ，_{f irst(Pi) |= f irst(Pj)}ならば ，それ らの 経路 は一方にのみ存在するホールド レジ スタをもつ．逆に ， f irst(Pi) = f irst(Pj)^{ならば ，}u^，v^{を始点とし ，同}

じ ホールド レジ スタのみを 通り同じ 外部出力に至る経 路対が 存在する．このことより，分岐枝_yi，_yjが 分離 可能である条件は ，_yi，_yjを始点とし 外部出力に 至る 任意の経路対_Pi，_Pjに 対し ，_{f irst(Pi) |= f irst(Pj)} または f irst depth(Pi) |= f irst depth(Pj)^と言い換 えることができる．各外部入力_xの各分岐枝_yiに 対 し ，集合_D(yi) = {(r, d)|yi^{を 始点と する経路}P ^が 存在し ，_r = f irst(P ), d = f irst depth(P )}^{を 求め} る．各分岐枝からホールド レジ スタ，または 外部出力

に 到達するまで ，_Sの各信号線をたかだか₁回探索す る．分岐枝から 各信号線までの順序深度の集合を考慮 するので ，計算量は ，_{O(nf· n · nl) = O(n}

3₎

となる．

（₂）分 岐 枝 集 合の 最 小 分 割を 求め る ．分 岐 枝を 頂 点とし ，分離 可 能で な い 頂 点が 連 結と な るグ ラフ Gsep を 生 成し ，そ の 連 結 成 分 を 求 め る（ 分 離 可 能

で な いす べ て の 頂 点 間を 辺で 接 続す る 必 要は な い ）． 二 つ の 分 岐 枝 _yi，_yj が 分 離 可 能 と な ら な い の は ， D(yi) ∩ D(yj) |= ∅となるときである．各外部入力に 対し ，共通の_{(r, d)}を_D(y)の要素とし てもつ分岐枝 y^{が 連結となるよう}Gsep に 辺を 加え る．各_{(r, d)}に

対し ，分岐枝の個数回の探索を行えば よいので ，計算 量は ，_{O((nh+ no) · nl· nf) = O(n}

3₎

となる． 以上より，_TC∗_{(n) = O(n}³₎となり，内部切換平衡 構造順序回路のクラスは ，組合せテスト 生成複雑度で テ スト 生成可能となる．

6. む す び

本論文では ，組合せテ スト 生成アルゴ リズムを用い てテ スト 生成可能な順序回路のクラスとし て内部切換 平衡構造を 提案し た ．内部切換平衡構造の クラスは ， これ までに 提案されている内部平衡構造のクラスと切 換平衡構造のクラスを真に 含み，組合せテ スト 生成複 雑度でテスト 生成可能である．本論文では ，これ まで 考慮され ていなか ったホールド レジ スタの 制御信号線 と スイッチの故障に対し ，検出可能であるための十分 条件を示し た ．また，この十分条件だけでも，ホール ド レジ スタの 制御信号線，ス イッチの故障に 対し て検 出可能なほとんど の故障が 検出できることを実験的に 評価し た ．更に ，計算量に 基づ く組合せテ スト 生成複 雑度に関し ても，内部切換平衡構造は 組合せテ スト 生 成複雑度でテ スト 生成可能であることを示し た ．

提案し た内部切換平衡構造では ，ス イッチとホール ド レジ スタへの制御信号は 直接外部から 印加され ると 考え て い る．し かし ，一般の 順 序回路を 考え た 場合 ， これらの制御信号は回路内部から 印加され る場合も存 在する．今後の課題とし ては ，制御信号が 直接外部か ら 印加され る場合だけでなく，回路内部から 印加され る場合も考慮するよ うに 拡張することが 挙げ られ る． 謝辞 多くの意見を頂いた 奈良先端科学技術大学院 大学の大竹哲史助手，並び にコンピュータ設計学講座 の諸氏に 感謝し ます．本研究は 一部，奈良先端科学技 術大学院大学支援財団教育研究活動支援による．

文 献

[1] A. Balakrishman and S.T. Chakradhar, “Sequential circuits with combinational test generation complex- ity,” IEEE International Conference on VLSI Design, pp.111–117, Jan. 1996.

[2] H. Fujiwara, Logic testing and design for testability, The MIT Press, 1985.

[3] H. Fujiwara, “A new class of sequential circuits with combinational test generation complexity,” IEEE Trans. Comput., vol.49, no.9, pp.895–905, Sept. 2000. [4] R. Gupta and M.A. Breuer, “Partial scan design of register transfer level circuits,” J. Electronic Testing: Theory and Applications, vol.7, pp.25–46, 1995. [5] 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.

[6] M. Inoue, E. Gizdarski, and H. Fujiwara, “Sequen- tial circuits with combinational test generation com- plexity under single-fault assumption,” J. Electronic Testing: Theory and Applications, vol.18, pp.53–60, 2002.

[7] T. Inoue, D.K. Das, C. Sano, T. Mihara, and H. Fujiwara, “Test generation for acyclic sequential cir- cuits with hold registers,” Proc. Int. Conf. Computer- Aided Design, pp.550–556, Nov. 2000.

[8] Y.C. Kim, V.D. Agrawal, and K.K. Saluja, “Combi- national test generation for various classes of acyclic sequential circuits,” Proc. Int. Test Conf., pp.1078– 1087, Oct. 2001.

（ 平成15 年 1 月 8 日受付）

神野 元彰 （ 正員 ）

平12 神戸大・工・電気電子卒．平 14 奈 良先端科学技術大学院大学情報科学研究科 博士前期課程了．同年，三菱電機（ 株 ）入 社．テスト 生成，テスト 容易化設計，論理 合成に 関心をもつ．

井上美智子 （ 正員 ）

昭62 阪大・基礎工・情報卒．平元同大 大学院博士前期課程了．同年（ 株 ）富士通 研究所入社．平7 阪大大学院博士後期課程 了．奈良先端大・情報科学助手を経て ，現 在，同助教授．分散アルゴ リズム，グ ラフ 理論，テスト 容易化設計，高位合成に 関す る研究に 従事．工博．IEEE，情報処理学会，人工知能学会各 会員．

電子情報通信学会論文誌2003/9 Vol. J86–D–I No. 9

藤原 秀雄 （ 正員：フェロー ）

昭44 阪大・工・電子卒．昭 49 同大大 学院博士課程了．同大・工・電子助手，明 治大・工・電子通信助教授，情報科学教授 を経て ，現在，奈良先端大・情報科学教授． 昭56 ウォータールー大客員助教授．昭 59 マッギル大客員準教授．論理設計論，フォー ルト トレ ラン ス ，設 計 自 動化 ，テ スト 容易 化 設計 ，テ スト 生 成，並列処理，計算複雑度に 関する研究に 従事．著書「Logic Testing and Design for Testability」(MIT Press) など ．大 川出版賞，IEEE Computer Society Outstanding Contribu- tion Award，IEEE Computer Society Meritorious Service Award など 受賞．情報処理学会会員．IEEE Computer Soci- ety Golden Core Member, IEEE Fellow.