FIT2005(第4回情報科学技術フォーラム)C-021
畳込み圧縮器における X マスク確率の評価に関する一考察
A Note on Evaluation of X-Masking Probability for Convolutional Compactors
新井雅之†

Masayuki Arai福本聡†

Satoshi Fukumoto

1. まえがき
半導体技術の微細化および高集積化に伴い，VLSI テストに必要なデータ量はますます増大している．このため，テストデータ量の削減および圧縮は，テストコスト削減のための重要な課題の 一 つ で あ る [1] ． Rajski ら は 畳 込 み 圧 縮 器 (convolutionalcompactor)について提案している[2]．畳込み圧縮器はテスト応答圧縮器の一つであり，多重誤りの検出を可能としながらテスト応答を 1/100 以下に圧縮できる．我々はこれまで，畳込み圧縮器において不定値によって誤りが見逃される確率である X マス
ク確率について，簡単な近似式および組合せ全検索手法により評価した[3]．近似式は精度の点で問題があり，また組合せ全検索は実用的な回路規模には適用できない．より高精度な近似式を導出することにより，畳込み圧縮器に関するより詳細な議論が可能になると期待される．
本稿では，畳込み圧縮器における X マスク確率の解析的な評価について議論する．スキャンチェーンから入力された不定値が同時に複数の FF へ伝播する特性を考慮して，X マスク確率の近似式を導出する．従来手法と数値例の比較を行い，計算精度が改善されることを示す．

岩崎

各スキャンチェーンの出力は，互いに等しい q (同 3) 個の FFに接続されている．q を奇数とすることにより，任意の奇数個の多重故障は検出可能となる．また，あるスキャンチェーンの接続状態をシフトさせることによって構成される接続状態を他のスキャンチェーンに用いないことにより，任意の 2 重故障が検出可能である．
インジェクタネットワークの接続を，S 行 b 列の接続行列
CN(x)⎡ CN 1,1 ( x ) L CN b ,1 ( x ) ⎤(1)⎢⎥,
CN ( x ) = ⎢MOM⎥
⎢CN 1,S ( x ) L CN b , S ( x ) ⎥⎣⎦で表す．ここで，行列の各要素CNi,j(x) はGF(2)上の最大M/b –1 次の多項式であり，
CN i , j ( x) = ci , j ,1 + ci , j , 2 ⋅ x + K + ci , j ,M / b ⋅ x M / b −1 (2)と表される．スキャンチェーンjがi番目のシフトレジスタ内のk番目のFFに接続されている場合，ci,j,k は 1 となる．例えば，図 1 に示した畳込み圧縮器における接続行列は以下のようになる．

⎡ 1+ x + x2 ⎤⎢⎥CN( x) = ⎢1 + x 2 + x 3 ⎥.
⎢ 1 + x + x3 ⎥⎣⎦2. 畳込み圧縮器と X マスク
2. 1 畳込み圧縮器の構成
図 1 に，畳込み圧縮器の構成例について示す．被テスト回路(CUT)のスキャンチェーンの出力は，EOR ゲートからなるインジェクタネットワークをとおして，シフトレジスタ内のフリップフロップ(FF) へ入力される．スキャンチェーンの本数を S (図では 3)，FF数を M (同 4), シフトレジスタ数を b (同 1) とおく．シフトレジスタの値は並列に外部へ出力されるため，テスト応答の圧縮率は b/ S となる．

b outputs S

outputsscan

q connections
for each scan

M FFs

一彦†

Kazuhiko Iwasaki(3)

2. 2 X マスク
スキャンチェーンから入力された値が不定値である場合，その不定値が入力される FF の値もまた不定値となる．以下では，不定値によって誤りを含む 1 個以上の FF が不定値になることを X マスクと記述する．また，あるクロック i においてあるスキャンチェーン j から入力される 1 ビットの値をスキャンデータ d(i, j)と記述する．
各スキャンチェーンにおける誤りおよび不定値の発生状
況を，XER(x) = [XER1(x) ... XERS(x)]で表す．XER(x)の要素XERi(x)は(4)
XERi ( x) = u i ,1 + u i , 2 ⋅ x + K + u i , N ⋅ x N −1 ,と表される．ここで，ui,j ∈{0, 1, X}である．誤りが発生した場合には 1 とし，不定値が発生した場合にはXとする． XER(x)に係数1 が存在し，かつXER(x)·CN(x) に係数 1 が存在しない場合，誤りの検出は不可能である．

3. X マスク確率の評価
CUT

畳込み圧縮器に入力された誤りは最大 q 回出力される．ここでは，あるスキャンデータが不定値である確率をεとして，1 個の誤りが入力された場合に，その誤りが i 回出力される確率 Pi の近似式を導出する．
S·N行 b列の行列 EMN(x)図 1 畳込み圧縮器の構成例(b = 1, M = 4, S = 2, q = 3)
Fig. 1. Example of arrangement ofconvolutional compactor(b = 1, M = 4, S = 2, q = 3)
†首都大学東京

229

FIT2005(第4回情報科学技術フォーラム)

q −1

(6)

Pq = ∏ (1 − ε )Tii =1

次に，誤りがq – 1 回出力される場合について考える．この場合，この誤りと 2 個以上FFを共有するスキャンデータが不定値であってはならない．また，1 個のFFを共有するスキャンデータに対して，ある 1 個の共有FFだけに不定値が入力されなければならない．すなわち，Pq-1は
q −1
T1 ⎧
T1 ⎫Ti ⎛ q ⎞T 1−(7)Pq −1 = ∏ (1 − ε ) ⋅ ⎜⎜ ⎟⎟ ⋅ (1 − ε ) ⎛⎜ q ⎞⎟ ⋅ ⎨1 − (1 − ε ) ⎛⎜ q ⎞⎟ ⎬⎜ ⎟⎜ ⎟⎝1⎠ ⎭⎝1⎠ ⎩i =2⎝1⎠と表される．ここで，各 FF が共有される確率は全て等しいと仮定した．
同様に，誤りが q – 2 回出力される場合，共有する FF 内の 2個だけに不定値が発生しなければならない．この場合，2 個のFF を共有するスキャンデータに不定値が発生する状況と，1 個の FF を共有する異なる 2 個のスキャンデータに不定値が発生する状況が考えられる．すなわち，
q −1T2T1 ⎛ 2 ⎞⎜ ⎟Ti ⎛ q ⎞T 2−T 1−Pq −2 = ∏ (1 − ε ) ⋅ ⎜⎜ ⎟⎟ ⋅ (1 − ε ) ⎛⎜ q ⎞⎟ ⋅ (1 − ε ) ⎛⎜ q ⎞⎟ ⎜⎝ 1 ⎟⎠⎜⎟⎜⎟⎝ 2⎠
⎝1⎠
i =3
⎝ 2⎠
2⎡⎧
T2 ⎫
T2 ⎧
T1 ⎫ ⎤⋅ ⎢⎨1 − (1 − ε )⎛⎜ q ⎞⎟ ⎬ + (1 − ε )⎛⎜ q ⎞⎟ ⋅ ⎨1 − (1 − ε )⎛⎜ q ⎞⎟ ⎬ ⎥(8)⎜2⎟
⎜2⎟⎜1⎟⎝ ⎠⎭⎝ ⎠ ⎩⎝ ⎠⎭ ⎥⎢⎣⎩⎦が得られる．
同様の議論により，Pi を求めることが可能である．例として，
図 1 の構成における Pi を示す．図 1 に示した畳込み圧縮器において，スキャンチェーン 1 に誤りが発生した場合，T1 = 8, T2= 8 となる．従って，
16(9)P3 = (1 − ε )13 ⎧3⎫
P2 = 3(1 − ε ) ⋅ ⎨(1 − ε ) − (1 − ε ) ⎬⎩⎭299[{}{⋅ 1 − (1 − ε ) + (1 − ε ) ⋅ 1 − (1 − ε )5P0 = 1 − P3 − P2 − P154. まとめ
本稿では，畳込み圧縮器における X マスク確率の解析的な評価について議論した．誤りと不定値が共有する FF 数の情報をもとに，誤りが i 回出力される確率 Pi の近似式を導出する手法について示した．また，数値例から，提案手法は従来手法と比較して，よりシミュレーション結果に近い値を持つことを示した．
今後の課題として，不定値に対してある程度耐性を持つ畳込み圧縮器[4]への解析結果の拡張などが挙げられる．
参考文献[1] 樋上他，"論理回路に対するテストコスト削減法―テストデータ量及びテスト実行時間の削減―," 信学論(D), Vol.
J87-D-I, No. 3, pp. 291-307, 2004 年 3 月.
[2] J. Rajski et. al., “Convolutional Compaction of TestResponses," Proc. ITC 2003, pp. 745-754, Sep. 2003.
[3] 新井他, "畳込み圧縮器における X マスク確率について,"
信学技報，DC2004-98, pp. 39-44, 2005 年 2 月.
[4] J. Rajski et. Al., "Synthesis of X-Tolerant ConvolutionalCompactors," Proc. VTS2005, pp. 114-119, Apr. 2005.

1.E+000.00010.001

1.E-02P0
P1
P2P3
P0 sim
P1 sim
P2 sim
P3 sim
P0 [3]P1[3]P2 [3]
P3 [3]} ] (11)289 2(12)が得られる．
図 2 に，b = 1, M = 32, S = 100, q = 3 におけるXマスク確率
P0，P1，P2，およびP3の計算結果を示す．横軸は不定値発生率εである．生成した行列において，T1 = 867, T2 = 15 となった．εが増加するに従い，P3 は減少し，P0 は増加しているのが判る．
誤りが 1 回または 2 回マスクされる確率は，εの増加に伴って一端高くなり，その後減少する．スキャンチェーン数Sが 100 である

230

0.01

1.E-01(10)13P1 = 3 ⋅ (1 − ε )ため，εが 0.01 の場合，平均して各クロック毎に 1 個の不定値が出力される．この場合に誤りが全て見逃される確率は約 85.9%となった．
図には，モンテカルロシミュレーションを用いて求めた結果，および文献[3]で示した近似式を用いた計算結果も示している．
従来の近似式では，共有FF毎に不定値が独立に入力されると仮定しているため，P3以外ではシミュレーション結果に対する顕著な誤差が存在する．これに対して本稿で示した計算手法では，共有するFF数を考慮する．このため，従来手法と比較してシミュレーション結果に対する誤差が小さく，よりよい近似となっていることが判る．

X-masking probability⎡ CN( x) ⎤⎢ xCN( x) ⎥(5)⎥.
EM N ( x) = ⎢⎢⎥M
⎢ N −1⎥xCNx()⎣⎦
を考える．この行列は，Nクロック間に入力された各スキャンデータにおける，他のスキャンデータとのFFの共有状態を示している．
2 個のスキャンデータd(i1, j1) およびd(i2, j2)の値が同一のFFに同時に入力される場合，対応する 2 行は等しい位置に係数 1を 持 つ ． 行 列 EM2M-1(x) に つ い て ， あ る 行 xm-1[CN1,j(x) ...
CNb,j(x)]との共通する係数 1 の個数がiであるような行の数をTiで表す．畳込み圧縮器の性質から，Ti = 0 (i ≥ q)が成立する．
まず，入力された誤りがq回出力される場合について考える．
この場合，誤りが入力されたq個のFFに対して同時に不定値が入力されてはならない．すなわち，共有するFFが 1 個以上存在するようなスキャンデータが不定値であってはならない．従って，Pqは以下のように表される．

1.E-03

1.E-04

1.E-05ε

図 2 X マスク確率の計算結果(b = 1, M = 32, S = 100, q = 3)
Fig. 2. Calculation results for X-masking
probabilities(b = 1, M = 32, S = 100, q = 3)