My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
April 13th, 2010, 10:50 PM   #1
Joined: May 2009

Posts: 34
Thanks: 0

VLSI chip testing

Professor Diogenes has n supposedly identical VLSI chips that in principle are capable of testing each other. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Thus the four possible outcomes of a test are as follows:
Chip A says Chip B says Conclusion
B is good A is good both are good or both are bad
other cases... at least one is bad

Consider the problem of finding a single good chip from among n chips, assuming that more than n/2 of the chips are good. Show that floor(n/2) pairwise tests are sufficient to reduce the problem to one of nearly half the size.

Something here doesn't make sense. For example, n=16
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 are my chips
assume that a16 and a15 are bad then i get that the pairs :
a1a2, a3,a4... a15a16 are good but it doesn't reduce the problem to one of nearly half the size. [cuz i don't have n/2 chips to test now].
plz help me
fed2black is offline  

  My Math Forum > Science Forums > Computer Science

chip, testing, vlsi

Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Mr Chip and his Chip Boxes braydonkils Algebra 3 May 15th, 2013 10:00 AM
hypothesis testing tsl182forever8 Advanced Statistics 2 April 27th, 2012 01:53 PM
Analysis Testing Help fengfeng Applied Math 0 July 12th, 2011 11:50 AM
hypothesis testing?? fc_groningen Advanced Statistics 0 February 8th, 2011 04:21 AM
Help with hypothesis testing mintsharpie Advanced Statistics 14 February 6th, 2011 02:14 PM

Copyright © 2019 My Math Forum. All rights reserved.