VLSI Chips – How to Determine Which Chips Are Good

algorithmsc

I have the following problem:

Given n chips [note: these are VLSI chips] out of which majority of chips are good, we need to find one good chip. The only test that we can apply is on a pair of chips that answers if both chips are good or both are bad.
The second part is to find a good chip if some tests might produce a wrong result. Also, the results are systematic meaning that if a pair gives wrong result, it will always give the wrong result.

I have solved the first problem using divide and conquer approach where I reduce the problem set to at least half every time. This can be done by simply performing tests on n/2 distinct pairs every time and keeping those pairs that answer a YES (i.e. both good or bad). I am unable to solve the second part of the problem.

A wrong result means that even if two chips are good or bad, the test might answer a NO. Also note that the percentage of wrong tests is very low.

How can I go about solving this problem?

Best Answer

I think this is a clustering problem: you have two clusters - the good chips and the bad chips. Your test tells you if two chips belong in the same cluster or not - at least under my interpetation of the question you have asked. The reference provided in the answer by Woot4Moo suggests a different question to this.

For the first part of the test, pick one chip and test every other chip against it. You get two clusters of chips - those that are of the same kind as the first chip, and those that are different. The good chips are in the larger cluster, so pick one at random.

For the second part, use n chips for testing, so that for each chip you have an n-bit pattern, saying whether it was in the same cluster as each of the n test chips. Expect to see mostly two sorts of patterns, each the inverse of the other. You can use this to sort the chips into two clusters as before, and hope that the larger cluster is composed of good chips.

Related Topic