VLSI chip testing Professor Diogenes has n supposedlyidentical VLSI chips that i

Question

VLSI chip testing Professor Diogenes has n supposedlyidentical VLSI chips that in principle are capable of testingeach other. The professor's test jig accommodates two chips at atime. When the jig is loaded, each chip tests the other and reportswhether it is good or bad. A good chip always reports accuratelywhether the other chip is good or bad, but the answer of a bad chipcannot be trusted. Thus, the four possible outcomes of a test areas follows:

Chip A saysChip B saysConclusion

B is good   A is good   bothare good, or both are bad

B is good   A is bad at least one isbad

B is bad    A is good at least oneis bad

B is bad    A is bad at least oneis bad

a. Show that if more than n/2 chips are bad, the professorcannot necessarily determine

which chips are good using any strategy based on this kind ofpairwise test. Assume

that the bad chips can conspire to fool the professor

Explanation / Answer

Proof: Question a): Let g be the number of good chips and n , g be the number of bad chips. Also, assume n , g ? g . From this assumption we have that we can always ?nd a set G of good chips and a set B of bad chips of equal size g. Now, assume that the set B of bad chips conspire to fool the professor in the following way: for any test made by the professor, they declare themselves as

Related Questions

Navigate

• Browse (All)
• Browse V
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.