回路の検査：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞回路の検査

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

回路の検査

デニス・シャシャ

　大量の電子回路をあまり信用のおけない業者から受け取った。どの線がどの素子につながっているかは目で確認できるし，素子が何であるかも書き込まれている。問題は「正しく書かれているか」だ。できるだけ少ないテストで，素子が正しく組み込まれているかを検査したい。回路中の素子はANDとORの２種類だけで，いずれも２つの入力に応じて１つの出力値を出す。入力と出力の対応表を下に示す。
　AND素子の出力が１なのは入力がともに１のときだけであり，OR素子の出力が１なのは入力の少なくとも１つが１のときだ。

ウォーミングアップ問題

　まずはウォーミングアップ問題だ。回路の配置が下のようだったとしよう。OR素子（素子３）は実際にはAND素子の疑いがある。AND素子（素子１，２）も実はOR素子なのかもしれない。テストでは，回路の入力A，B，C，Dのそれぞれに１か０を与えて，出力E，Fの値を調べることができる。回路中の論理素子が正しいか否かを１回だけのテストで判定したい。どのような値を入力して，どのような値が出力されればよいのか。

ウォーミングアップ問題の答え

答えは，入力Aに１，Bに０，Cに１，Dに１を与えることだ。素子２が本当にAND素子ならば，その出力は０だ。素子１が本当にAND素子なら，出力Eは０になり，素子３がOR素子なら出力Fは１になる。しかし，素子がどれか１つでも違っていると，出力E，Fがそれぞれ０と１になることはない。

　今月の問題では，まず下の４素子回路を考える。この回路の最少テスト回数は何回か。そしてそのときの入力および出力は何か。次に，同じ配置ですべての素子がAND素子と書かれているとき，同じ問題に答えよ。最後に上の３素子回路に戻って，この配置で３素子に対するすべてのAND，ORの組み合わせを考える。このうち，１回のテストで確認できるのはどのような組み合わせか。

	山崎秀記（やまさき・ひでき）

	一橋大学商学部教授。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Verifying Your Circuits （SCIENTIFIC AMERICAN January 2004）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved