電子通信学会 論文誌 別刷 T ra ns. I E C E' / 8 1 8V

4

2

電子通信学会 論文誌 別刷 T ra ns. I E C E' / 8 1 8V

UDC6813.

- d lJ o.

4 . 560..01

8 o.

DN

i l o na i t na b o m 構造記述関数 を用 いた組合 せ 回路 の

故 障検 査 につ いて

正 員 樹下 行三† 正 員 高松 雄三††

正 治†

正 員 柴 田 †† 正 員 松藤 信哉††

t e s

A Me dfrG g T si n C sb y S eD F

i n t e n e r a t t r ucur o

ho i i r c u

t t

C e s c rp it i o n u nc t i o n s

h sa ar

†

o KINOSHIT

A.

†Yu o TAKAMATSUz †, Ma u SH工

†

を用いた故幹検査について考察 したものである.これまで環案されている輯遵記述関数は.回路が大きくなると式 ers

Ko

Shi a MATSUFUJ工

†

,ReguclL'Memb

あ らまし 本論文は.論理回路の ゲ- トの草歳関係および出力を記述する一つの論理式 (構造記述関数 と呼ぶ ) が急掛 こ大 きくな り実用化が困姓である.そ こで本論文では.まず.計井故地理に遺 したれ造記述閑散の表現式お よびその井出7ルゴ[)ズムを与 えている.この表現式は経路の故の大 きさで表 されている.次に,その構造記述的 故に `組 に対す るブール敬分 ■とい う概念 を導入 し.経路が活性化できるための必要十分条件を与 えている.又,

この条件を基に して経路哉分に よる検査系列生成法 を述べている.次時,熊毛記述関数に故帝政分 を導入 した検査 系列生成について述べ.経路敬分 と故障敬分のそれぞれの特故 を有効に併用 した換査系列生成法 を現実 している.

最後に, この方法の プログラムによ り適用 した結果 を示 している.ここで述べた プログラムを用いると検出串 100

%の検査系列が得 られるので.回路の冗長性な どの検証に有用であると思われる.

z ny

1.ま え が き れ て お り,貫 に, これ らの関係 お よび構 造記述 関数 を 用 いた検 査系 列生成 につ いて考察 がな され てい る tBl. 論理 回路 の故 障診 断 の間 農 はかな り古 くか ら取 り扱 又, SPOOF表 現 を計 井故 処理 で求 め る方法 も提 案 さ わ れ て お り, これ まで数 多 くの論理 回路 の検査系 列 を れ てい るが qq, 実用化 までは至 ってい ない よ うであ る.

生成 す る手法 が提案 され て い る Il)-t4) 本論 文 では, まず計 耳故 処理 に適 した構 造記述的 数 本論文 は, 論理 回路 をそ の構造 お よび 出力 を表 す一 の一表 現法 お よび そ の算 出 アル ゴ リズ ムを示 す . ここ つ の論理 式 (以後, 構造 記述関数 と呼 ぶ )を用 い て表 で提 案 す る表 現式 は 回路 の経 路 の数 の大 きさで表 され 現 し, そ れ を 基に した検査 系 列生成法 につ い て考察 し て お り, SPOOF表 現 セ氏締 した もの であ る.次 に, た もの であ る t5h･ この 上 うな構造記述 関 数 として は, `最 終 に対 す る ブール数分 'とい う概 念 を導入 し, 回

d n BATA††† a

tera i

文字 命葛 記述 `8-(l lproxt'sition), en mf 路 の経 路 が活 性化 で きるため の必要十 分条件 を与 え る.

P or or en i equya

( J tn malf m),SW Ft引(st 拡trture-and 又, す べ ての逢 路 に対 す るプール故 分 を行 うことに 上 i

servng -

ty

P lar Ob Out tpu

†広島大学抱 合杓学部稔 合科学札 広島市 の 7'-ル故が山との関係 を示 す .貫 に,構造記述関 数 i

t unc o

F n)な どが 知 ら り得 られ る検査 系列 と, そ の回 路が実現 してい る関数 l

cences n t r tegraet

･ r Jt I t

FCa yofZ dA sadS ,Hi 且rohiEna と故 障 との閑膚 を述 べ,検 査 系列生成 のため一に故 障 教 h

ros t yersy.

"

Ur ･Hi iJtra-Sh呈,70J3 叩A n

††佐 訳大字理 工学 部電 :T･工学 札 佐 黙市 分 を導 入 す る.故障 故分 に 上る検 査系 列生成 は理 論 的 ty

i nvers i

rng i ng n i cenc It LUe i

F yofS eadE nee .S喝aU i . には簡潔 であ るが, それを すべ て の故障 に対 して行 う Jt

4 i h 5 -

S 8ag .80J叩a l c g 6 hi ecnca Tos

0 9

†

6

††佐 策県立鳥栖 工業高校. 鳥栖 市

uT lHihShoo.T

姶文 番号 :昭 5144

ことは計 昇量 の点 か ら容 易 では ない qa.そ こで本 論文 n

4 呈 h s -

osu .81J叩a では, 経路 故分 と故障 数分 のそ れ ぞれ の特 散を有効 に ]

3 0 1 - D [

3 併 用 した検 査系 列生成法 を捷菓 す る. この方法 を用 い

電子通信学会論文誌別刷

Trans． IECE  81／8Vol．」64−D No．8

UDC 681．325．6．001，4

構造記述関数を用いた組合せ回路の 故障検査について

正 員 樹下 行三†

正員 柴田 正治†††

正 員 高松 雄三††

正 員 松藤 信哉††

AMethod for Gelleratillg Tests ill Combillatiollal Circuits by Structure Descriptioll Fullctiolls

Kozo KINOSHITA†， Yuzo TAKAMATSU††， Masaharu SHIBATA†††αη4 Shinya MATSUFUJI††， Reg掘αアMθπδθrε

 あらまし 本論文は，論理回路のゲートの接続関係および出力を記述する一つの諭理式（構造記述関数と呼ぶ）

を用いた故障検査について考察したものである．これまで提案されている楠造記述関数は，回路が大きくなると式 が急激に大きくなり実用化が困難である．そこで本論文では．まず，計算機処理に適した構造記述関数の表現式お よびその算出アルゴリズムを与えている．この表現式は経路の数の大きさで表されている．次に，その構造記述関 数に゜経路に対するプール微分 という概念を導入し，経路が活性化できるための必要十分条件を与えている．又，

この条件を基にして経路微分による検査系列生成法を述べている．次に．楠造記述関数に故障微分を導入した検査 系列生成について述ぺ，経路微分と故障微分のそれぞれの特徴を有効に併用した検査系列生成法を提案している．

最後に，この方法のプログラムにより適用した結果を示している．こごで述べたプログラムを用いると検出率100

％の検査系列が得られるので，回路の冗長性などの検証に有用であると思われる．    

1．まえがき

 論理回路の故障診断の問題はかなり古くから取り扱 われており，これまで数多くの論理回路の検査系列を 生成する手法が提案されているm〜㈲．

 本論文は，論理回跳をその構造および出力を表す一 つの論理式（以後，構造記述関数と呼ぶ）を用いて表 現し，それを基にした検査系列生成法について考察し たものである軌このような構造記述関数としては，

文字命題記述 6｝（：iteral proposition）， enfl7｝

（画uivalmt n。rma且f・rm），SPOOF⑧（Str㏄ture一即d Parity−Observing Output F岨ctioh）などが知ら

 †広鳥大掌総合科学部総合科学科．広島市

  F8culty of I馳tegrated Arts and Sciences， Hiroshim8  U i▼ersity． Hiroshiロla−shi， 730 Japan

††佐買大掌理工学部電子工学科，佐質市

  Facu量ty of Scie魔ce a魔d Engineerin8， Saga Uniせersi止y，

 Saga−3hi． 840 Japa魔

†††佐賀県立矯栖工業高校．鳥栖市

  Tosu Tec』nical Hig卜Schoo監， Tosrshi，841』apa轟   論文番号：昭56−443［D−103］

れており，更に，これらの関係および構造記述関数を 用いた検査系列生成について考察がなされている9｝．

又，SPOOF表現を計算機処理で求める方法も提案さ れているがUO，実用化までは至っていないようである．

 本論文では，まず計算機処理に適した構造記述関数 の一表現法およびその算出アルゴリズムを示す．ここ で提案する表現式は回路の経路の数の大きさで表され ており，SPOOF表現を圧縮したものである．次に，

1 経路に対するプール微分 という概念を導入し，回 路の経路が活性化できるための必要十分条件を与える．

又・，すぺての経箪に対するプール微分を行うことによ り得られる検査系列と，その回路が実現している関数 のプール微分αガとの関係を示す．更に，構造記述関数 と故障との関係を述べ，検査系列生成のためk故障微 分を導入する．故障微分によゐ検査系列生成は理論的 には簡潔であるが，それをすべての故障に対して行う ことは計算量の点から容易ではない吻．そこで本論文 では，経路微分と故障微分のそれぞれの特徴を有効に 併用した検査系列生成法を提案する．この方法を用い 690

論文 /構 造 記述 関 数 を用 いた鼠合 せ 回路 の故障検 査 につ いて る と検 出率 100% の検 査系 列 が生成 で き,検 出 可能 で な いすべ て の故 障 を知 るこ とが で き る. この よ うな検 出 可能 {･な い故 障 を知 るこ とは一 筋 に容 易 ICはない . 最後 に, この方 法 の ブ pグ ラ ムに 上 り適用 され た結果 につ いて述 べ る. この方法 に 上る と検 出率 100%の検 査系 列 が得 られ るので, 回路 の冗長性 な どの検証 に有 用 であ る と思 われ る.

･ 2.

構 造 記 述 関 数

まず, 本論 文 で基 本 とな る構 造記 述 関数 (81ruclure Decisr iptonf'爪touCin, 以 下, SDFと略 す )を定義 し, そ の算 出 7ル ゴ 1)ズ ムを示 す .又, 以下 の議論 で 必要 とな る諸定 義 につ いて述 べ る.

ここで対 象 とす るゲー トは,AND,OR,NOT,

NAND及びNORの 5種 とす る.

次 の条件 を満 足 す る上 うな元 の回路 と等 価 な樹 枝 状 回路 で実 現 され る関数 を定義 す る.以下 , この論 理 式 を等 価樹 枝 状 回路表 現 (EquivalentFanOut-free

Form, EFFと略 記 す る )と呼 ぶ .

(1) 入 力端 子 か ら出力端 子へ 至 るすべ て の愚 路 を入 力変 数 が 同一 で あ って も別個 の入 力変数 と して故 う.

【2)入力 に 否定 を許す AND及びORゲー トのみ か ら な る樹 枝 状 回路 であ る.

この よ うな EFFは次 に示 す アル ゴ ))ズム EFFを用 い て得 られ る.以下, 回路 の信 号線 には, ラベル A, β ,･･･が付 され て い る もの と し, ラベルは正 また は負 の符 号 を もつ もの とす る.又, l個 の L(i),L(｢ 1),

･･･,L(I)の系 列 を

L ( -

)で表 す .

〔アル ゴ L)ズ ムEFF〕

10 A- i, )-I.

Zo 出力 端 子 に接続 され てい る信号線 (A と しよう) を取 り出 し, -L(i)-A とす る.

30 以下 の手塀 を行 え.

3.lO I- i+1と し. ラベル L(卜 1)か ら入力端 子 へ 向 い, ラベ ル L(一-I)が ゲー トGの出力 線 であれは

Gの入力 線 の うち マ ー クされ ていな い入力線 (β と し よ う )を取 り出 しBを 11- クす る. 3.3Cへ .そ うでな けれ ば, ラベ ル L(i-1)が接 続 され てい る入力側 の信 号線 (C とす る )を取 り出 し 3.20-行 く.

3.2o L(i)- C`

,

Cが入 力端子 に接続 され ていれ ば 3.50- .そ うでな けれ ば. 3.10へ行 く.

3.3o L(i)- B'(Gが NOR,NAND,NOTのとき),

L(i)-B'(Gが OR,ANDの とき ) とす る. こ こで, a+(B`)は ラベル L(i-I)と異 符 号 (同符号 )であ る

こ とを表 す .

3.4 o Bが入力 端子 に接 鼓 され てい れば 3.50-. そ うでなけ れ ば, 3.10-行 く.

3･50 魚 拓 p,と して L(i)を畳 卓 す る1 40へ1 40 以下 の手順 を行 え.

4.10 ラベル L(i)が 出 力 端 子 に接続 され ていれば, 50へ行 く. ラベル L(i)が ゲー トGの入力線 であれは 4.3Cへ .そ うで たけ れ は. 4.20-行 く.

4.2〇 一一 1- Iと して 4.10へ .

4.-3o Gに マー クされ てい ない入 力線 (Dと しよう) が存 在 すれ ば. 4.40- .そ うでなけれ ば, Gの入力線 すべ て のマ ー クを 消 し. 一一 一- 1と して. 4,10-行 く.

4･40 L(.)- D'(又 は, D')と して, p,とp,'1 の関係 R())を次 の よ うに決定 す る.

R())-GN･Gp･sgn(L(A-I))

こ こIC. GNは f(.)上 の ゲー トの数 であ り, 又.

(Gが OR又 は NANDの と き )

G p -

(_: (Gが AND又は NORの とき ) (ラベル上(ト 1)が正 ) sgn(L(i-I,,- L ll (ラベル上目-1)が 負 ) 4.50 ノーノ+1と して, 30-行 く.

5C R())の絶対値 の大 きい贋 に. 正 の ときは p,と p}･十1との済 算が OR, 負 の と きは ANDと な る 上 うに 括 弧 付 の式 を構 成 す る.

(アル ゴ l)ズ ム EFF終 り )

〔例l〕 アル ゴ t)ズ ム EFFを用 い て.団lの回 路 の EFF(sfと青く )を求 め る･

lo i-I, )A- I. 20出 力端子 に接 続 され てい る ラベル 上を取 り出す .上(1)- 上.

3o i- 2, Jを取 り出 し11- クす る. Lを出力線

ー

ノ

とす るゲ- トは ORで あ るか ら,L(2)-I. i- 3.

Elを取 り出す . Elを 17- クす る. Jを 出力線 とす る yl- トは ANDで あ るか ら.L(3)-El, 一一 4, Eを 取 り出す . L(4)-E. Eは入力 端子 に接続 され てい る ラベル IC･あ る.魚拓 plと して 3.cc.ILを萱費す る.

40 i- 3.ラベル L(3)(El)は ゲー トの入力線 IC あ り, その ゲー トの入力線 に 11- クされ ていな い ラ ベ ル Flが存在 す る. L(3)-Fl,R(I)- 2×(-1)×1. 1- 2. と して 30へ行 く.

3o i- 4. Fを取 り出す . L(4)- F, i- 5, C を取 り出 し71 クす る. Fを 出力 線 とす る ゲー トは

ORであ るか ら,L(5)-C.Cは入力端子 に接 続 され てい る ラベル で あ る. p2と して 3,cpp.JLを登 録す る･

以 下, 同様 に して,魚 拓 p" p.

, ･

･･,p,と して, そ 691 論文／構造記述関数を用いた組合せ回路の故障検査について

ると検出率100％の検査系列が生成でき，検出可能で ないすべての故障を知ることができる．このような検 出可能でない故障を知ることは一般に容易ではない。

最後に，この方法のプログラムにより適用された結果 にっいて述べる．この方法によると検出率100％の検 査系列が得られるので，回路の冗長性などの検証に有 用であると思われる．

②．構造記述関数

 まず，本論文で基本となる構造記述関数（Stfuc如re Descript最on Function，以下， SDFと略す）を定義 し，その算出アルゴリズムを示す。又，以下の議論で 必要となる諸定義について述べる．

 ここで対象とするゲートは，AND，OR，NOT，

NAND及びNORの5種とする．

 次の条件を満足するような元の回路と等価な樹技状 回路で実現される関数を定義する．以下，この論理式 を等価樹枝状回路表現（Equival㎝t Fanout−free Form， EFFと略記する）と呼ぶ．

 ω 入力端子から出力端子へ至るすべての経路を入 力変数が同一であっても別個の入力変数として扱う．

 〔2｝入力に否定を許すAND及びORゲートのみから なる樹枝状回路である．

 このようなEFFは次に示すアルゴリズムEFFを用 いて得られる．以下，回路の信号線には，ラベル∠，

8，…が付されているものとし，ラベルは正または負 の符号をもつものとする．又， 個のL（の，L（ −1），

…，L（1）の系列をL（ので表す．

 〔アルゴリズムEFF〕

 1°  −1，ブ←1．

 2°出力端子に接続されている信号線（濯としよう）

を取り出し，以の・−4とする．

 3°以下の手順を行え．  −

 3．1° ← ＋1とし，ラベルL（ −1）から入力端子 へ向い，ラベル以 −1）がゲート0の出力線であれぽ σの入力線のうちマークされていない入力線（8とし よう）を取り出し8をマークする．3．3qへ．そうでな けれぽ，ラペルLG−1）が接続されている入力側の信 号線（Cとする）を取り出し3．2°へ行く．

 3．2° L（の←C㍉ ごが入力端子に接続されていれ ば3．5°へ．そうでなけれぽ，3．1°へ行く．

 3．3° 五（ ）←8＋（σがNOR，NAND，NOTのとき〉，

L（ ）r」r（σがOR，ANDのとき）とする．ここで，

ガ（8 ）はラペルL（ −1）と異符号（同符号）である

ことを表す．

 3，4° 8が入力端子に接続されていれば3．5°へ．そ うでなければ，3．1°へ行く．

 3．5°経路うとしてL（のを登録する．4°へ．

 4°以下の手順を行え．

 4．1° ラベルL（のが出力端子に接続されていれば，

5°へ行く．ラベルL（のがゲートσの入力線であれば 43°へ．そうでなけれぽ，4．2°へ行く．

 4．2『  ← −1として4．1°へ．

 4．3° σにマークされていない入力線（Z）としよう）

が存在すれぽ，4．4°へ．そうでなければ，σの入力線 すべてのマークを消し，ご← −1として，4．1°へ行く．

 44° L（の←ゲ（又は，0＋）として，pノとpノ＋且 の関係R（ノ）を次のように決定する．

    R（ノ）←σ ・OP・Sgn（L（ −1））

 ここで，σ〃は五（の上のゲートの数であり，又、，

  砺一｛．llll：器錨濫ll；

馴…−1））−

q：；綴：：B震；

 4．5°ノ←ブ＋1として，3°へ行く．

 5°R（のの絶対値の大きい順に．正のときはpノと 功＋ユとの演算がOR．負のときはANDとなるように 括孤付の式を構成する．

       （アルゴリズムEFF終り）

 〔例1〕 アルゴリズムEFFを用いて，図1の回 路のEFF（5ノと書く）を求める。

 1° ←1，∫−1．2°出力端子に接続されている ラベル五を取り出す．以1）←L．

 3° ←2，ノを取り出しマークする．五を出力線 とするゲートはORであるから，双2）←ノ， ・−3．

81を取り出す．左1をマークする．ノを出力線とする ゲートはANDであるから，五（3）い左1， ←4，8を 取り出す．以4）←8． 五は入力端子に接続されてい るラペルである．経路p：としてエ4881几を登録する．

 4°  ←3，ラベル五（3）（E1）はゲートの入力線で あり，そのゲートの入力線にマークされていないラベ ルF1が存在する．以3）←F1，R（1）←2X（−1）X1，

ブー2，として3°へ行く．

 3°ε←4，Fを取り出す． L（4）←F， ←5， C を取り出しマークする．Fを出力線とするゲートは ORであるから，五（5）←ご． Cは入力端子に接続され ているラベルである．p2として範ごFF、，エを登録する．

 以下，同様にして，経路ア3，p喝，…，Pgとして，そ 691

、ン

電子通 膚学 会論文誌 '81/8

J

γol.J64-D No.8

LN ,<NJ勺 1IOItnELLEL C,<tprlP

ELtbELhAEL-dL ,叫も.

f i ircu h o i ircu

団 1 論理回路の例† 圏3 等価哉枝状回路

tfre reec tfrtec t｡

l xampe

o Fi 3g.-E i lquvaentfanout-f 1.

ig･1

F -L iogcci trcli Fi 1g. .

れ ぞれ' PIJL.I,～

L 2J

Jl =

L,言2ii

ルを表 す )が得 られ る.又, R()).)--2,3,

モB

= ,.

L

.DPPIJL, BLDP 2BEL,I.諺 -,戸ZBEL, を tJの よ うに表 す ことにす る･そ うす ると･ SpfIl･

L(一記 号は負 の ラベ

- p -p

一般 に次式 で表 され る.

t豆jl万的 BEL.I. B2B 否

=

(1

･･･9,は, ₎

3,0とな る. 又, これ らの式 に現れ る入力か ら出力へ至 る経 路 を Spf=Tl>T2

>

･･.>T上

- 4 1, , 3 -, ,

o R()A)か らSfを構成す ると図 2の よ うに して, 4 5,

5

2 -, -

T

aで表 され るか ら･

)･Pl･P書 I;を p)の入力 .)テ ラル と呼び. 入力 .)テラルが

J

pJで表 す･一般 に経 路 pJelpJ-Lr', 3･P.)>pB･(p8>p,

51=Pl･(p2>p

:

<=:> と書 く･但 し

,

I は &.又

が得 られ る. であ る経路 p)を p}

..,

又, この とき得 られ る囲1の等価樹枝状回臥 1図 3 は 3-1で あ り･ aOl入力 =;か ら出力 へ至 る進路 pJを表

で与 え られ る. す ラベルの系列 であ る.

の信号値 を V

(例終 ) 又,盾号線 A,8,- v,- の 1 うにB 上 記 の7ル ゴ .)ズムEFFで得 られ るEFFを展朗 し, 表 す ことにす る.

B) 経路 ptの額和形で表 した論理 式を作 るとSPOOFtと

な り, 又. 回路 の盾号線 の ラベルの代 りに y- ト名 で

3.

31.

軽 持微 分 と故 陣微 分 掻祐活性化条件 最蕗 p.を表 せばenfm とな る.

ll研和形 で表 され てい るので,経

SPOOF又 はenf ここでは, 2.で述 べ た SDFに農 路 に対 す るブ ール 路の個数 の増加 と共 にそ の表 現式は大 き くな り実用的 故分 とい う枚念 を導 入 し,農路活性化 条件 につ いて考 では な くな る. しか しなが ら. 本論文 で導大 したEFF 察 す る.

ll農 路 の数 で蓑 され るので, 比較 的大 きな規模の回路 ･L個 の入力変 数 J l, 3 2,･･･,I.を 有 す る論理 回路 に の SDf-として用い ることがで きると考 え られ る. おいて, nL個 の入力変 数 Jiに定数 4 ∈. 【0,11又 は.

L一 以下, 本論 文では, 論理関数Jを実現す る回路 の ド'/ トケア 止を頚 当r

7.

o ) 8 ' 9 p p

･ ( ( p 8 1 p 7 ◆ P 7 ) ) ) )

: :

- p

14

を入 EFFをSfで表 す･又･ Sfを展開 して8F和形 で表 した 力 といいJ七表 す.以康 ,小文字 の Jは ド./ トケアの 論理式 を Spfで表 し･ そ の積 項 を T)で･ TJの部分群 意味 で使用 す る.

lp 2 n

2 う

^B

p <J

)) -(1,0,0,1)を加 え

L, 割 り当てた TL次元 べ タ ト/

〔定義1〕 与 え られた回路に対 して入力 7.-(bl,

pl

4

･･･,i._" aり ,.I,^{- ,A.)}を加 え る場 合を考 え る.

冗

ここで･ i)は a}又01dである･ この とき,経路 '

, J･

せ た とき, その信 号線 を入力 とす る ゲー トの出力値が

> 上 の任 意 の信号魚 の骨号億 を 1箇所変化 さ

7ノ つ】 l

変化 すれば･経 路 p}< =:>は 7.で 4.1タ ])テ ィ カル

Y V 9 6 a

( .

＼

p

.

ぅ

P

4 ) i 4 - ) / 1

レ 叫

! 轟

L p _{Y ( pp プ ●}

( p f . P

( p 2 Y l ･ ( p

ヒ4

p 圭

_{/ (p}

)Y((pぅ

進 路 であ るとい う.

〔例2 〕 図 1の回路 で

国 2 5/の構成 ち. この とき, 農路 p7<32>につ い て考 え よ う.vA I,=1L , y

h ies t S ly.

･2- ig

F sofSf･

=1. vc--0, J-0とな る.従 って. I,E の債 8

2 9 6

† この例 は文如 Ip9の句 である. を変 え る とKを入力 とす るy- トの出力値 vLの値が変

LL

電子通信学会論文誌 81／8Vo1．」64−DN軌8

X！

X2 B

    図1 諭理回路の例†

Fig．1−Logic circuit for｛獣ample l．

   P1 翼

   ≒舞

ナ騎

   ；湧

   諺

EE

B82

         図3 等価樹枝状回路

Fig．3−Equivalent fanout−fr㏄ circui t for the circuit of    Fig．1．

ヂ

紅

れそれ・τMDFF量，L，勉EβiρFF1几，；3∂節盟島，；南茄戸2κ乱，

晦盈函茄戸2』協，萌切2δ1κ加晦莇2，乱（ 記号は負のラベ ルを表す）が得られる．又，R（の，ノ電2，3，…，9は，

3，−4，1，−4，5，−2，−3，0となる．

 5°R（∫）から5ノを構成すると図2のようにして．

  聾＝ρ1 （P2＞PゴP4）〉ρ5・（P6Vp？）・P．・P9 が得られる．

 又，このとき得られる図1の等価樹枝状回路は図3 で与えられる．

       （例終）

 上記のアルゴリズムEFFで得られる起FFを展開し，

経路P己の積和形で表した論理式を作るとSPOOFI8［と なり，又，回路の信号線のラベルの代りにゲート名で 経路p を表せばenfσ，となる．

 SPOOF又はenfは積和形で表されているので，経 路の個数の増加と共にその表現式は大きくなり実用的 ではなくなる・しかしながら，本諭文で導天したEFF は経路の数で表されるので，比較的大きな規模の回路 のSDFとして用いることができると考えられる．

 以下，本論文では，諭理関数ノを実現する回路の EFFを『ノで表す．又 彰を展開して積和形で表した 論理式を卸ノで表し，その積項をろで．7ンの部分積

Pj

R（」）

5．．．

4．．．

3．．．

2 ．．

1．．．

 P工  P2  P5  P4  P5  P6  P7  P8  P9

−2   5  −4   1  −4   5  −2  噂5   0

↓慰ll熊』

（Pゴ（P2・（PプPゴ）♪）・（（P5・（P6・P7）♪ （P8・P。））

    図2 5ノの構成  層     一   Fig・2 Synthesis・f 5ノ。

をらのように表すことにする．そうすると，5pノは，

一 般に次式で表される．

      51ケ富丁1＞T2＞…v7毒     ｛1｝

 又，これらの式に現れる入力から出力へ至る経路を pノで表す．一般に経路pノはp戸τ「αで表されるから，

竃をpノの入力リテラルと呼び，入力リテラルが銃 である経路pノをpノ〈 幽τ巳〉と書く．但し，τ，は置 又 は端であり，αは入力竃から出力へ至る経路p∫を表 すラベルの系列である．

 又，信号線∠，β，…の信号値をひ瀞ひ面…のように 表すことにする．

3．経路微分と故障微分

†この例は文脚魯P・98の例である．

692

 3ユ 経路活性化条件

 ここでは，2．で述べたSDFに経路に対するプール 微分という概念を導入し，経路活性化条件について考 察する．

 π個の入力変数τ、，範，・・㍉τ鴇を有する論理回路に おいて，昌個の入力変数τ に定数α、∈｛0，1｝又は，

ドントケア己を適当に割り当てたπ次元ベクトルを入 力といい1セ表す．以後，小文字の己はドントケアの 意味で使用する．

 〔牢義1〕 与えられた回路に対して入力11＝（ムp

…^・ム −pαρム」＋、，…，へ）を加える場合を考える．

ここで，らはαノ又は己である．このとき，経路 pノ＜τ3＞上の任意の信号線の信号値を1箇所変化さ せたとき，その信号線を入力とするゲートの出力値が 変化すれば，経路pゴ〈 ●τ8〉は1！でら一クリティヵル 経路であるという．

 〔例2〕 図1の回路で11＝（1，0，0，1）を加え る．このとき，経路p7〈τ2〉について考えよう．ワ』

＝1、聖＝0，り1＝1，u，＝0となる．従って，聖の値 を変えるとκを入力とするゲートの出力値 Lの値が変

論 文 /構 造 記 述関 数を用 いた鼠 合せ 回路 の故障 検 査 につ い て る.以 下, 同様 に して, 定義 l上 りp,<=,> は 7.で 0- ク リテ ィカル経 路 で あ るこ とが分 か る.同様 の考 察 に 上 り, pS<3 > 及, び p9く3 > も 7 で 02 . - ク [)チ ィ カル経 路 で あ る ことが分 か る. (例 解 )

〔定義2 〕 71-(bl,-,A.一日 aL,a.." ･･･,A.) とす る･経 路 pj

<3 : >

が Jlで ar クT)ティ カル径 路 で あ り,一且 つ, J2=(C1,-,0.-I,a.,0..1,･･･,C.) で a.- ク I)ティ カル径 路 で あ る と き･ pJ<3:> は

(-(el,･･･,C.ー" J , E..1,･･･,C.).で活性化農 路 であ る とい う･但 し･ cJ =bJ又 は cJ-d･ eJ-

b Jn

cJ()

≒ L)で あ り, 演 算 ∩は, and-a.and-dna-a.

α∩言

-め (¢は定義 され ない こ とを意 味 す る )で あ る.

〔例3 〕 図 1の回路 に 71-(0,J,1,1)を 加え, 農 路 p2く3,> を考 え よ う. p2く

3 } >

は定義 lか らJl で llク t)ティカル農 路 で あ る.又. 72-(0,I,0,

I)で O-クt)ティカル農 路 であ るこ とも分 か る.従 っ て. 定義 2上 り, p2<3}> は 7-(0,1,J,1)で活

性化経 路 で あ る. (例解 )

活 性化 径 路 に おいて は, そ の入力 Jに おいて, そ の 定義 か ら入力端 子 の変 化 は 出力 端子 まで伝搬 す る.す なわ も,活 性化法 で用 い られ た活 性化 最終 m と同 じに な る. ところが, ク l)ティ カル経 路 に おいては, 必 ず しも入力端 子 の変化 が 出力端 子 まで伝搬 す るとは 限 ら な い.例 えは, 例 2でみ た よ うに p,く32> は 7.- (1.

0,0,1)で 0-ク.)テ ィカル経 路 で あるが, 72=(I, 1,0,I)で 11 ク t)テ ィ カル最 終 とな らない. UI- 0とな るか らであ る.

しか し. 次 に定 義 す る同時 a.-ク t)テ ィ カル農 路 と い う概 念 を導 入 す ることに 上 り, 従来 の活 性化法 では 得 られ なか った検査 系 列が求 め られ る.

〔重義 S〕 入力変数 才.か ら出力-至 る連 絡 が 2個 以 上 存在 す ると して･ そ れを pjく

3 : >

,P▲< 3;> ,

･･･,p <3 > とす る. z : Jll-(bl ･ ,-, .‖ a,aa_ . .. "

････九 )につ いて pJ･pL･二･.･Pzが すべ て a.-ク.)テ ィ カル連絡 で あ るとき,農 路 pJ

<3 7 >

, p▲<3:> ,･･･, p

z <3 ; >

は Jlで同時 at-4 .)ティ カル農 路 で あ る と い う.

〔例4 〕 例2か ら

,

p,く32>

, P , <3 2 >

は 71- (1,0,0,1)で同時 0- ク t)テ ィ カル農 路 で あ る.

(例 解 )

〔定義4〕 連絡 pJ<

3> :

を a+ ク.)ティカル経 路 とす る入力 Jが存在 しない とき･ pj<

3 ; >

は非 クリテ ィカル農 路 であ るとい う.

例 えは, 図 1の回路 の p｡<31>は非 ク 1)テ ィ カル農

路 で あ る.

以 下, 回路 の SDf-が与 え られた とき, そ の中 で定 義 され てい る経 路 が活 性化 経 路 か ク l)テ ィカル径路 か, 又 は非 ク ])テ ィカル農 路 で あ るか を判定 す る方法 を述 べ よ う.

〔定義 5〕 次 式 で 定 ま るdSf/dpJを Sfの経路 pJ に対 す る農 路 教分 とい う.

君 -抽 - '1◎ 抽 - , 0 (,2 こ こで･ Sf(p,=a)は Sfに現れ る p,の値 を aqこし た式 を表 す.

〔定義 6 〕 dSf/dpJのすべ て の pz(Z≒))に対 応 す る入力 リテラル∫:を代入 して得 られ る関数 を pJの農 路 活 性化 関 数 といい fpJ(X)で表 す ･又･ fpJ(X)=l を満 た す入力 の集 合 を LJで表 す ･

〔例5〕 図 1ゐ回路 の Sfの plに対 す る経 路微分 dSf/dpl, 及び plの径 路活性化 関数 fp,(X)を求める･

例1で 求めた Sfか ら,

票 -(p2>p3P･VP- P9>- - ,

⑳ (pSP｡p.p.>p,P,PBP,)

=(p2>p'P.)･(p,

>

^p｡

>

^pB

>p ,)

･(pS>pT>p8>p,)

又 , fp▲(X)は pJ,)=2,3,･･･,9の入力 t)テ ラル 那, そ れ ぞれ 3" 31,32

,

3,

,

3

"

3" 3.

,

32であ る か ら, dSf/plに代 入 す る ことに 上 り.

fpl X)(

- (

^3}

>1

²

･

³

>

^.

3)

d

33)

⁽, 31>&

> 2

･(∫,

>

^∫2

>

^才

. >∫ 2)

=土3>LZ32 が得 られ る.従 って. Jlは,

Ll-I(J,J,I,d),(1,I,J,d日

で あ る. (例 解 )

〔補 題l 〕 回路 の農 路 p,<3:>が ク リティ カル経 路 で あ るた め の必 要十 分 条件 は･ LJ≠¢(¢は空 集合 を表 す )で あ る ことであ る. (証明^晦57)

定 義 1, 2及び定 義 4と補亀 1か ら次 の定理 が得 ら れ る.

〔定理 l 〕 連絡 pJ

<3 : >

が活 性化経路 で あ るため の必 要十 分条 件 は J∈LJ な る Jが存在 す るこ とで あ る･

又, pJく

J> :

が ク .)テ ィ カル農 路 で あ るた め の必要十 分 条件 は･ JleLJな る 7.が存在 す るこ と{･あ る｡ 但 し, ∫,71は, それ ぞ れ 7-(b‖ ･.･,a._‖ J,a.."

････b･), Jl=(b= ････b.一日 at･b… ,-,a.),bJ∈

10,1,dh a.∈10,11で ある.

693

臨

論文／構造記述関数を用いた組合せ回路の故障検査について る．以下，同様にして，定義1よりp7＜エ2＞はムで

0一クリティカル経路であることが分かる．同様の考 察により，p5〈ヱ3〉及びPg＜エ2＞も11で0一クリテ ィヵル経路であることが分かる．    （例終）

 〔定義2〕 ム＝（ゐ1ヂ・㍉へ＿1，α ，6 ＋1，…，転）

とする・経路Pノ〈エ：〉が11でα 一クリティカル経路

であり∫且つ， 2＝（σ1・…・σト竃，α ，σ ＋1，°9 ，σ・）

でα 一クリティカル経路であるとき，pプ〈 盧ヱ巴〉は 1＝（61，…・￠r1，己，6、＋1ヂ ㍉c．）、で活性化経路であ るという・但し・σノ＝ら又はoプ＝己・eノ＝ら∩oプ（ノ

≒のであり，演算∩は，α∩α＝α，α∩己＝己∩α＝α，

α∩α＝φ（φは定義されないことを意味する）である．

 〔例3〕 図1の回路にム量（0，己，馬1）を加え，

経路p2〈ヱ3〉を考えよう．p2〈鞠〉は定義1から 1 で1一クリティカル経路である．又，12＝（0，1，0，

1）で0一クリティカル経路であることも分かる．従っ て．定義2より，p2〈工3〉は1電（0，1，己，1）で活 性化経路である．       （例終）

 活性化経路においては，その入力1において，その 定義から入力端子の変化は出力端子まで伝搬する．す なわち，活性化法で用いられた活性化経路171と同じに なる．ところが，クリティカル経路においては，必ず しも入力端子の変化が出力端子まで伝搬するとは限ら ない．例えば，例2でみたようにp7〈ヱ2〉はム量（1，

0，0，Dで0一クリティカル経路であるが，12富（1，

1，0，1）で1一クリティカル経路とならない．ひ戸 0となるからである．

 しかし，次に定義する同時α已一クリティカル経路と いう概念を導入することにより，従来の活性化法では 得られなかった検査系列が求められる．

 〔定義3〕 入力変数エ、から出力へ至る経路が2個 以上存在するとして，それをpノ〈 盧工 〉，PL＜ヱ7＞，

…^{，初くヱ7＞とする． 1＝（ゐ1，…，6 −1，αi，6、＋p}

…，6隔）についてpノ，Pp豊・・，勘がすぺてα 一クリティ カル経路であるとぎ，経路pプ〈 禽工 〉，PL〈イ〉，…，

p4〈 盧工 〉は11で同時α 一〃リティカル経路であると いう。

 〔例4〕 例2から，p7＜ヱ2＞， Pg＜エ2＞は11＝

《1，0，0，1）で同時0一クリティカル経路である．

       （例終）

 〔定義4〕 経路朽くイ〉をδ 一クリティカル経路 とする入力1が存在しないとき，pノ〈 盧ヱ3〉は非クリテ ィカル経路であるという．

 例えば，図1の回路のp6＜エ1＞は非クリティカル経

路である．

 以下，回路のSDFが与えられたとき，その中で定 義されている経路が活性化経路かクリティカル経路か，

又は非クリティカル経路であるかを判定する方法を述 べよう．

 〔定義5〕 次式で定まる己51／己pノを51の経路房 に対する経路微分という．

    豊一身・朽一1）㊥聯・・ ②

 ここで，5ノ（pプ＝α）は51に現れるpプの値をαにし た式を表す．

 〔定義6〕 己51／己pプのすべてのp4（♂≒ノ）に対応 する入力リテラルヱ7を代入して得られる関数をpノの経 路活性化関数といいメpノ（X）で表す．又．メpノ（X）冒1 を満たす入力の集合をろで表す．

 〔例5〕 図1の回路の5ノのp1に苅する経路微分 己51宛p1，及びp1の経路活性化関数メPI（X）を求める．

 例1で求めた身から，

薯一（P2Vp3P4Vp5P6P8PgVp5P7P6Pg）

   ㊥（P5P6P8PgVp5P7P6Pg）

   量（P2Vp3P4）・（P5Vp6Vp6Vp9）

    ・（P5Vp7Vp8Vp9）

 又，プp量（X）はpノ，ノ＝2，3，…，9の入力リテラル が，それぞれ，南，崎，エ2，；3，；、，；2，繭，；2である から，己5ノ／己p1に代入することにより，

 メP1（X）＝（ヱ3Vヱ1ヱ2）・（エ3Vエ1 V；4Vヱ2）

     ・（ヱ，Vヱ、Vエ、Vエ、）

    ＝ま3Vヱ量α32 が得られる．従って，ろは，

  11冨｛（己，己，1，己），（1，1，己，己）｝

である．      （例終）

 〔補題1〕 回路の経路pプ＜エ7＞がクリティカル経 路であるための必要十分条件は，み≠φ（φは空集合 を表す）であることである．    （証明暗5り  定義1，2及び定義4と補題1から次の定理が得ら

れる．

 〔定理1〕 経路pノ＜エ7＞が活性化経路であるため の必要十分条件は1∈ろなる1が存在することである．

又，pノ＜4＞がクリティカル経路であるための必要十 分条件は，1i∈ちなる11が存在することである。但

し，1，11は，それぞれ，1＝（61パ・㍉6乙一1， 的6 ＋p

°°㍉6・）・11＝（6 °°㍉6、一 ・…・・ …・6．）・6プ・

｛0，14｝，α、∈｛0，1｝である．

693

r

 〔系1〕 1ノ雷φ（φは空集合を表す）のとき，且 つ，そのときに限り乃く苫，〉は非クリティカル経路で

ある．

 〔系2〕 回路の経路pノ＜4＞．ハ＜4＞，…，

勉く苫，〉が同時α 一クリティカル経路であるための搭 要十分条件は， 、∈ち∩ろ∩…∩16なる入力右が存在 することである．ここで．演算∩は、∀弓∈1ノ，》も∈

うについて定義2の演算∩を施すことである．

 経路pノ＜4＞が活性化経路であることは．その経路 の遅延テスト゜°（測定）が可能であることを示してい る．従って，回路の経路が活性化経路であるための必 要十分条件を与えている定理1は故障検査系列生成に 対してと同様有用であると思われる．

 〔定義7〕 ある回路の入力変数苫、から出力へ至る すべての経路をpノ邑く婦〉，乃2〈 幽≦＝ 〉，…，功6〈境〉

とする．このとき，鷹（2≦雇≦の個の経路pノ量くτ1〉，

…^{・P沖く媛〉が 1＝（ム且・・…ゐ 一・・α} ・ム、＋且・…・ム・）

で同時α6一クリティカル経路であり，且つ，（i〕残りの

（ど¶）個の経路乃．＋1〈τ：〉・° °・Pノ，〈τ：〉が ・＝（ム

り㍉ゐ −pαρゐ 刊ヂ゜°，へ）でα 一クリティカル経路 でない，及びGi） 2で例一クリティカル経路（α配＝ゐp

な≒のである経路Pg〈 虚τ幽〉が存在しない，とき，経路 Pハ〈 嚇≦＝乙〉・…・Pル〈苫：〉は ＝（妬…・ム…・己・ゐ ＋且・

…，へ）で同時活性化経路であるという．

 〔定理2〕 ある回路の入力変数端から出力へ至る

経路pム〈 嚇τ乙〉ヂ・㍉pム〈τ，〉カ1 ＝（ゐ、，…，ゐ ＿p己，

ゐi＋p…，ム隠）で同時活性化経路であるとき，入力 を 加える場合を考える．このとき，入力端の変化は経路 乃、〈 白τ乙〉，…，pたく㌶〉を経て出力端子に伝搬する．

       （証明略㈲）

 これまでの考察から検査入力を生成することは，経 路微分を行い，その活性化関数を呈とする入力集合を 求めることに帰着される．経路微分を行うとき，次の 補題2が有用である．

 ・〔補題2〕 5pノの項丁ノにおいて，経路乃が含ま れている項をろ、，…，ろ鱈，そうでない項をT 、，…，

T ，とすると，式②の経路微分は次式で与えられる．

    箭一（・・lv…v・隔）・死、…乞， 〔3）

 ここで・ろ西＝乃噌九（な＝呈・…・那）である・

 定理1，2及びプール微分脳の定義から次の定理3 が成立する．

  〔定理3〕．次のいずれかの条件を満足する ∈ 1〈 虚τ 〉は関数ノの艦に関するプール微分己ノ／幽、を

694

電子通信学会論文誌 81／8Vd．J64−DN。．8 1とする入力である．又，逆も成り立つ．

｛1｝pノ〈 幽≦＝8〉を活性化経路とする入力

② 乃、〈 ●≦＝ 〉，…，pんく鍍〉を同時活性化経路とす   る入力

但し，1〈 虚≦＝重〉は入力リテラルが魂である経路 pノ〈苫，〉の1ノの和集合を表す．

 〔例6〕 図1の回路のすべての1ノを求めると次の ようになる．

 P1〈τ4〉：1且＝｛（己，己，【，己）；（1，1，己，己）｝

 P，〈τ3〉：1、＝｛（0，己，1，D，（0，1，己，1），（己，0，1，1）｝

 P3〈τ量〉：13昌｛（妬【，0，1）｝

 P4〈τ2〉：ろ薯｛（【，1，0，1）｝

 p5〈τ3〉：15暑｛（偽0，0，1）｝

 P6〈苅〉：16＝φ

 p7〈τ2〉：為冨｛（1，0，0，1）｝

 P8〈τ4〉：1，＝｛（己，0，0，己）｝

 Pg〈τ2〉：．1g冒｛（04，0，D，（己，0，0，1）｝

 定理3から，この回路が実現する関数ノのプール微 分己ノ／面 を求めると，次のようになる．

  ￠ノ／己必1＝碗苫3τ4  （13から）

  己ノ／己必2＝ ＝且鞠苫4  （19から）

  己ノ／己必3＝ ＝且τ2τ4  （12から）

  己ノ／面4＝鞠v明吻v；2葛   （ろ及び18から ）       （例終）

 3．2 故障微分による検査系列の生成

 ここでは，仮定した故障を検査する入力を，EFF を用いて求める方法として．5ノの故障微分について述

べる．

 以下，経路に含まれる．ラベルが否定形（2でに負の ラペ・ルとした）のとき否定ラベル，そうでないとき，

  ザ 肯定ラベルという．又、信号線8の値がα∈｛0．，1｝に 縮退するときり故障をF（8＝α）で表す．ラペル8を含 む経路pノを考えたとき，8塑否定（肯定）ラベルのと

きpノの値をα（のとするこどを，故障F（8冒のによる 経路pノの値という．

 〔定義8〕 5ノにおいて，F（8＝α）による経路の 値を代入したものを，一信号線8のα縮退故障関数とい い・．毎（8＝α〉で表す・       n   ・  〔定義9〕 5ノの故障F（8＝α）による故障微分を次

の式で定義する．

論一・，㊥・…一・・

^｛4）

式〔4｝に現れるすべての経路に対応する入力リテラル ィを代入して得られる関数を方（炉の《X）で表すと，

論文 /構 造 記 述 関数 を 用 いた抱合 せ 回路 の故障 検 査 につ いて

fp(a_4)(X)=Iを満 たす 入力 は, 故障 F(B-a)を検査 す る入 力 とな る.又,fp(a_4)(X)=0であ れは, 故障

F(8-α)は検 査 で きない (検 出可能 で な い故 障 )こと を意 味 す る.

〔例7〕 図 1の回路 の故障 F(A=l)に よる故 障 数 分 を求 め よ う. ラベル Aを含 む経 路 は p" Aを含 む魚 拓 は p6であ るか ら･ p3=l･p6-0を例 1の Sfに代入

して,

Sf(A-I)=pl(p2Vp4)vpSP7PBP9 従 って,

訴豊 7 7

^{- tpl(p2Vp374,vps(p6Vp7,pBP9,}

◎ tp (lp2V

p)

.vp P P P IS7 . ,

次 に, pH p2,･.･,P,に対 応 す る入力 .)テ ラル 3.,r "

I"3

2 ,

=

, ,

I-

. ,

言 ,2I

. ,

言2を 代入 して整 理 す ると,

fp.(l_1()X)-313 2333.

が得 られ る.従 って, (0,I,0,I)は信 号線 Aの l 縮 退故 障 を検 出す る入力 であ る. (例解 )

ここで述 べ た故 障故 分 は 3.1で述 べ た経路 微分 と関 係が あ り. 農 路故 分 は故障 故分 を lとす る一 つ の条件 にな って い る.す なわ ち. 故 障 故分 は監 路 微分 を用 い て表 す こ とがで きる【Sl･例 えは･例 7で求 めた dSf/

dF(A-1)は .

品 -3 E ･ ( i ) p v 6 ･ ( a

),,_l

とな る.

4.

検 査 系 列 生 成 法

これ まで述 べ た よ うに, 回路 の検 査 系 列を 生成 す る には･ 経 路微 分 を行 い fp)(X)-1とす る入 力 を求 め る か, 又 は, 故 障 故分 を行 い ′∫(か .)(Ⅹ)-1とす る入力 を求 めれば よい . この と き, 経 路微分 のみ の方法 では 検 出率 †loo%の検査 系 列 を生成 することは一般に は困

I . Eh暮 - " ㌫ 諾 三蒜 諾 '書xloo

兼1

難 で あ る.一 方, 故 障 微分 のみ の方 法 を用 いて検 査系 列 を生成 す るこ とは 回路 が 大 き くな ると生 成 時間 が増 加 し佃, 実用 的 でな い , ここでは, 経路 故 分 と故 障 微 分 のそ れぞ れ の特 徴 を有 効 に併 用 した検 査系 列生成 法 を述べ る.

4. 1

プ ログ ラムの構 成

図 4に経路 徽分 と故 障 微分 を併用 した検査系 列生 成 プ ログ ラムの概 要 を示 す . プ ログラ ムは, (I)回路記 述 か ら回路 テー ブル の作 成. (Ⅱ)EFFの算 出, (班) 魚 拓 微分 , (Ⅳ)故 障 微分, の四つ の部分 か ら溝 成 され て い る.以下, 簡 単 に説 明す る.

(I) ここで は, 被検 査 回路 の回路記 述 データを読 み込 み.二 つ の回路 テー ブル (内部表 現 )を作 成す る.

(Ⅱ) 回路 テー ブルか ら,2.で述 べ た アル ゴ リズ ム EFFを用 い て EFFを 昇 出 す る.

()) 刀 Sfの経路 p}r関 す る農 路 数分 を行 い- ･fp) (Ⅹ)- 1を満 たす 入力 を生 成 す る.

図 4 全体の構成国 Fig.4IGeneralflow.

実行結果

香 最 良 数 分 テス ト

路号回 時間(珍) 検出率(%) 時 間 (秒)故 幹 敬

%

分生･3-.成 極

0

検出率( ) { /& シ1ネレ(､秒 ) -シ■ン 1 77.0 94.0 42.7 100 15 120 2 17.2 91.9 1.7 100 18

0

^18.9

3 121 83.0 ･240 99.4 77 4 .361

695

■

論文／構造記述関数を用いた組合せ回路の故障検査について ノF田一。）（X）昌1を満たす入力は，故障F（8＝ユ）を検査 する入力となる．又，ノ畑一。）（X）＝0であれば，故障

F（β呂α）は検査できない（検出可能でない故障）こと を意味する．『

 〔例7〕 図1の回路の故障F（濯判）による故障微 分を求めよう．ラベル濯を含む経路はp3，濯を含む経 路はp6であるから， p3＝1，p6＝0を例1の彰に代入

して．

   5ノ（．4呂1）＝P・（P・Vp・）Vp5P7P・P・

 従って，

  、，農1）一｛幽・節）・｛・初）酬

       ㊥｛P1（P2Vp4）Vp5P7P8P9｝

 次に，p亀，p2，…，Pgに対応する入力リテラル置4，鞠，

エ、，範，鞠，エ1，範，エ4，エ2を代入して整理すると，

     ノF（，一、）（x）電苅工2鞠工、

が得られる．従って，（0，1，0，1）は信号線濯の1 縮退故障を検出する入力である．    （例終）

 ここで述べた故障微分はa1で述べた経路微分と関 係があり，経路微分は故障微分を1とする一つの条件 になっている．すなわち，故障微分は経路微分を用い て表すことができる㈲．例えば．例7で求めた己5ノ／

己F（．4＝1）は，

となる．

詣，一異・傷）・穆・農）バ

4．検査系列生成法

 これまで述べたように，回路の検査系列を生成する には，経路微分を行いノ戸．（X）＝1とする入力を求める        ノ

か．又は，故障微分を行いノ，佃＿。）（X）＝1とする入力 を求めればよい．このとき，経路微分のみの方法では 検出率†100％の検査系列を生成することは一般には困

難である．一方，故障微分のみの方法を用いて検査系 列を生成することは回路が大きくなると生成時間が増 加し゜ ．実用的でない．ここでは，経路微分と故障微 分のそれぞれの特徴を有効に併用した検査系列生成法 を述べる．

 4．1 プログラムの構成

 図4に経路微分と故障微分を併用した検査系列生成 プログラムの概要を示す．プログラムは，（1）回路記 述から回路テーブルの作成，（mEFFの算出，（皿）

経路微分，（W）故障微分，の四つの部分から構成され ている．以下，簡単に説明するゼ

 （1） ここでは，被検査回路の回路記述データを読 み込み、二つの回路テープル（内音陵現）を作成する．

 （m 回路テーブルから，2．で述ぺたアルゴリズム EFFを用いてEFFを算出する．

 （1］） 5ノの経路乃に関する経路微分を行い，ノ今

（X）＝1を満たす入力を生成する．

（・・ar・）    ↓

Circuit table Generation of

circuit table

■

／   一

㌧

↓

Derivation of

    EFF

● EFF

、 ／  一

↓

L

Path difference ⁹ Test pattem    ／  『 No     detecte

、

   「9

fau工ts        yes

Fau工t difference 幽^「 Test pattem

、   ／   一

（・・。P）

    テストによウ検出された故瞳数

†

      X100  検出率3

     被検査回路の故障数

 図4 全体の構成図 Fig．4−GeneraI flow．

、，

表1 実行結果

経踏徴分

故 障 微 分

回 路 番

号 ^{時間（秒） 検出率（％） 時間（秒） 検出率（％）}

生  成バターソ数

検出可

能でない

故障数

テスト ジェネレーシロン

（秒）

7乳0 1乞2

121

9＆4

940 9L9 8ao 8a5

427

 1．7

240 8a6

100

100

ga4

9乳4

15 18 77

104

00417

  「

120

1＆9

361 182

695

C G :. . t .andMeZ:

S i B

lures.･ i a

.

8 i ys he

′ P U

- seOf S OOF9int am l

, 8 o.

血 電子通信学会論文誌 ● 8 V J6 D N/ o.l 4-

T 1

学 研究費 (課題番号一 般 C455146)に よる.

8

i re r

i agnos

t t

n a i cenc

.J s

` A

) F ma .P

1 r-,

t ue l id re

I(

eu r

h H la

Co t o (

L

( 2

3

4

mp rS ePess(

Wiey良 S on,T叱.

文 献

IP :. .

分割表現を導 入す ることなどが考 え られ るが 99.上 れ

1 B e M.. d F d z

I R . Di 90fauotm af , EFF 列生成 時間が大 き くなる と考 え られ るので の 2 被検査回路の構造

表

らは今後 の課 題であ る.なお, 本研究 は一部文部省科

L

t a

t i lt equvael

a

` : . D . A

an. Dipo

0 8 9 1 1( -

t I F.

l au oage dteec (5

(6

1樹下,高松.柴EE]:一構造記述関数を用いた組合せ

1 P .

∴

tf sinc

一 i

). 3 7 t F lau

). 9 7

pu Com rams. t..

' tem S y ta iig i

tdiagrpS80fd ls S F lau

'

o t es u im io

D i terva

` nof呼t m t st

一 i t ecr s E

mb E Tram . El

o n

氏 :- . . ' ts ,P G . ng ) Chazv,H.Y.,Nami ,E l

) l ear n iz

o T

- : a

.. nfdigan ymi ).

0 7 9 1 (

i ircu ta iig ionind lc dt teec

E E 7

. l E T ,.pp

まず, EFFに麓 路徽分 とい う概 念 を定義 し, 経路

u2) 樹下,高松.柴田.松茸 :`構造記述関数の故甲敏 ice- t ren

21回全国大会論文集.p

田) 安居玩.内藤 :`論理回路の故挿診新 一.虚報 (昭 he t or in lZy A

`n a gerr sWiht :

･L･W･

Beamson

' 皮

Res.

.

t e

` : . K . i k

d Susszd ,A A m hd - t l au

. ' 9 ) tter

3 8 4 . -

' ts i J i Irc

). 6 6

t aa t uom or

TheyOfA ,

o o t S e io t t eec l au e

malstoff td nt Sfrc n l r ittu t

ns eofB 00ky.pp

t uo A m.良 F

7

･ 9 7 C E

9 Fbe 7 1 6 6

. 3( .1

i s io t enera T Se A P :

. . tg nung

). 6 6

I9, 5 1 - 1 3 1 .

,pp 4(

S y ta iig i

esg l iba l

re ed nofd ls ). 6 7 9 1

9 J lu 2 - 8 7 2

. 91( y1

9 rc 3 2 - 9 2 2

. 4(Ma h 1 i

i tna noa b

om Lc

rams.

9 EE T 2(May1 )75.

T loerant - t

nm

rams.

.7EEE T E

'

"

t es

1 : i og .

C r.

tro

t er io

es Co

Com

Eo Co 0 7

9

O

l (

(8

(

) Arms ng,D

mt mll cn . I mpt ..pp ) Clegg.FW.

ff )地 y .I

u ro mpu .,

u) Sell sJ ,F ,M.Y.ard

). 5

). 8 7 n

D a . . l A. d M

t e

Okr W t e 5

h t e

S ad amZ

h t.

T ynp.

Proc P ltoyec

2 5

.S Ma hic I 8(

). 1 7 9

). 3 6 9 1 Clu l a t ac u

ky..[0.pp

5 1 1 C t ..

3 2 2 - ,,pp a

., put

lt au y

). 8 6

9 0 1 . 7(昭5

喝 i 6 5 1 0 6 5 .

9 J lu 8 6 - 6 7 6

. 3( y 1

9 tn J 6 1 - 9 5 1 p.

ingp. t l

X 4( e 1

t es D lea - I : . . yt ).

2 0

es.

- or r )

zy malf ms.I.D 4 3 3 t u.

o ,S.

T loeran i S

tC mp ,.- E ' ' in

) i ta

b T g SPOOFS, l

&

i sao H F . ..

C - .an

5 4 2 - ,,pp

erence ea

8001 ndiff 7 1 - G

). 1 5 あ ま り検 出率 が 10%の実行結果 は得 られ てい ない よ

うであ る. しか しなが ら, EFFの故障数分 とい う概 0

作成 した プ ログラムを 10ゲ- ト程度 か らな る回路 に対 して実行 した結果 の一 部を表 1に示す . プ ログラ

0

O ここで述 べた プ pグラムを用 い ると,検 出率 I0%

の検査系列が得 られ る.衰 lの中 で回路番号 3, 4の 0ステ ･/プ 0 20,

0 17グラムを用 い ると検 出率 1

X) ( ) . _ fp(a

42 .

5.

に利 用で きると考 え られ有用であろ う.

む

それが 10%でない のは被検査 回路に検 出可能 でない 故障 が存在 す るためであ る. この ような検出 可能 でな

0

d''. IBM sfの故障 F(Bea)に よる故障微 分 を行 い,

= 1を満 たす入力を生成す る.

実 行績異 と評価 (Ⅳ)

ムは FORTRANで記述 され, おお よそ

であ る.使用計 算鰍 ま九 州大学 大型計 耳壊 セ ソクー

FACOM M-200であ る. 回路の故幹検査法 '.骨学技軌

い故障 をすべ て知 ることは困難であ るため, これ まで,

念 を用い る と,検 出 可能 であ る故障 のすべて の検査 系

列が得 られ る と同時 に検 出可能 でない故障 も知 るこ と _l喝icn が で きる.例 えば, 回路番号 3及び 4につ いて,そ れ

ぞれ, 検 出可能 でない故障が 4個 お よび 17個 存在 し てい る. この よ うな結果 は. 回路 の冗長性 な どの検 証

す ぴ

ここでは. 圧縮 した SDF表 現 と して EFF を導 入 し,

'

そ の EFFを用 いた検査系 列生成法を考察 した .

の活 性化条件 を明 らか に し;経路故分 に 1る検査 系列 分による検査系列生成について I.情報処理学会第 生成法を示 した.又. EFFに故障 敢分 を導 入 し, 仮

定 した故障 の検査 系列 の生成につ いて述べた.次 に.

EFFの経 路夜分 と故障故 分 を併用 した検査系 列生成 プ pグラムの実行結 果 について簡単 K:示 した .この プ

i cgc F l

ymp a. u t

n 7 9 ltes hde Proc Co

44I S ky.I LSl^l ' .1 8 t .S

mT

u9 石橋,松#.高札 樹下 :`論崖回路の構造記述関 4.

3 5 .

月 18日再受付 ) 5

0%の検 査系列が得 られ るので, 回路 の検証 な どに有用 であ ると思 われ る.

数の一分割法 -.昭 55九州遠大 く昭和 5年 10月 15日受付.56年 2

6 9 6

しか しなが ら, 回路 の経 路 の数 が多 くなる と検査系

F

衰2 被検査回路の構造

回路．

番号

ゲート 数

信号 線数 入力数

   L 出力数

96

70

107 118

264 177 312 331

14

91410 8584

 （W） 5∫の故障P（8富のによる故障微分を行い．

∫，〔5−、）（X）＝1を満たす入力を生成する．

 4．2 実行結果と評価

 作成したプログラムを100ゲート程度からなる回路 に対して実行した結果の一部を表ユに示す．プログラ ムはFORTRANで記述され，おおよそ2，000ステッゾ である．使用計算機は九州大学大型計算機セソター FACOM M−200である．

 ここで述べたプログラムを用いると，検出率ω0％

の検査系列が得られる．表匙の中で回路番号3，4の それが乱00％でないのは被検査回路に検出可能でない 故障が存在するためである．このような検出可能でな い故障をすべて知ることは困難であるため，これまで，

あまり検出率が恥00％の実行結果は得られていないよ うである．しかしながら，EFFの故障微分という概 念を用いると，検出可能である故障のすぺての検査系 列が得られると同時に検出可能でない故障も知ること ができる．例えば，回路番号3及び4にっいて，それ ぞれ，検出可能でない故障が4個および17個存在し ている．このような結果は，回路の冗長性などの検証 に利用できると考えられ有用であろう．

5．む す び

 ここでは．圧縮したSDF褒現としてEFFを導入し，

そのEFFを用いた検査系列生成決を考察した．

 まず，EFFに経路微分という概念を定義し，経路 の活性化条件を明らかにしi経路微分による検査系列 生成滋を示した・又，EFFに故障微分を導入し，仮 定した故障の検査系列の生成にっいて述べた．次に，

EFFの経路微分と故障微分を併用した検査系列生成 プログラムの実行結果にっいて簡単に示した．このプ ログラムを用いると検出率ユ00％の検査系列が得られ るので，回路の検証などに有用であると思われる．

 しかしながら，回路の経路の数が多くなると検査系

696

電子通信学会論文誌、 81／8Vo且．J64−DNα8 列生成時間が大きくなると考えられるので，EFFの．

分割表現を導入することなどが考えられるが㎎，『これ らは今後の課題である．なお，本研究は一部文部省科 学研究費（課題番号一般C455匙46）にょる．

         文    献

 ω Cha㎎， H．Y．． Maming， E．G． and Metze， G．：

   昌Fault diagnosis of digitai systems騨， Jq軸    Wi ley＆S㎝s，1㏄．（1970）．

 ｛21Friedman． A。D． a【KI Meロon， P．R．： Fau且t    detection in digita且circuits摩， Prentice−

   Ha皇置（1971）嘔

 〔3】B爬uer．・M．A． and Friedman， A．D．：昌Diagno8 is    ＆ fe且iable design of digital sygtems鱒。

   Computer Science Press（1976）．

 （4〕 Roth，」．P．： Diagms亘s of automata failures：

   aca且cuius and a method脚．1BM Res．＆

   Dev．．10．pp．278−291（Ju匙y 1966）．

 ｛5｝樹下，高松，柴田：『 構造記述関数を用いた組合せ    回路の故障検査法 ，信学技報，罵C79・71（1980−

   02）．

【6｝

σ［

18｝

｛9［

qo

u

ua

㎝

口o

巳9

Poage，」。F。；°DerivaUon of optimum tests to detect fau且ts in combinatiQnal circuits露，

P即oc． Syπ1p． Math． Theoτy of Automata，

Polytechnic lnstitute of Brookl胆， pp．483弓 528（1963）．

Armstro㎎， D．B．：引On finding a nearIy mini−

mal set of fault detection test3 for combi−

nationa且且㎎ic nets ， 1EEE Trans． E且ectron．

Comput．，罵C−15，1，PP．66073（Feb．1966）．

Clegg， F．W．：4Use of SPOOF s in the ana且ysi8 0f faulty且ogic networks．， I EEE Trans．

Compuし，G−22，3，pp，229−234（March 1973）．

Hayes．」．P．：露Test generation usi㎎equiva lent norma且foms膚，」． Des． Autom．＆Fault−

To且erant Comput．，3，3−4，PP．131−154（1979）．

Si，S．℃． and Susskind， A．K．；°A method for obtai聰i㎎SPOOF ゴ，1EEE TrIms．

Comput。．σ一24，5，pp．560−562（May 1975）．

Se且且ers Jr．， F。F．，Hsiao， M．Y． aM Beamson． L．W．： Ana且yzi㎎eπors with the Boolean d i ffefencゼ， IEEE Trans． Comput．，

G膚17，7，pp．676−683（July 1968）．

樹下，高松，柴田，松藤： 構造記述関数の故障徴 分による検査系列生成について゜，情報処理学会第 21回全国大会論文集，p．1097（昭55）．

安居院，内藤： 論理回路の故障診断齢，産報（昭

51）．

Shedletsky， JJ．：嘱De且ay testi㎎LSIl㎎ic膚，

Proc．1978 1nt． Symp． Fau且t−To且erant Comput ing， PP．159−164（Jme 1978）．

石橋，松蕊高松．樹下： 論理回路の構造記述関 数の一分割法鱒，昭55九州連大，534．

（昭和55年10月15日受付，56年2月18日再受付）