# Given a set of VLSI chips, how do I determine which are good?

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?

-

## migrated from stackoverflow.comDec 3 '11 at 20:44

This question came from our site for professional and enthusiast programmers.

@talnicolas I am still trying to figure out a good starting point for the second part. – Anna Dec 3 '11 at 19:28
@Anna: Can you throw more light on the second part? what do you mean by a wrong result? ie, what will be the output if I test with one good chip and one bad chip ? – bragboy Dec 3 '11 at 19:29
@Bragboy I have updated the problem statement. – Anna Dec 3 '11 at 19:33
What can we assume about the error rate? – templatetypedef Dec 3 '11 at 19:43
@templatetypedef The error rate is fixed and is small. Can we determine an error rate for which an exact solution will still exists? Or if such a bound doesn't exist, then what might be a possible approximate solution considering that the error rate is small? – Anna Dec 3 '11 at 19:48

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.

-
No hope is necessary. As long as the difference between good chips and bad chips is much larger than the error rate, the larger pile will have the good chips. – Caleb Dec 4 '11 at 13:45

To find the wrong results, I would compare each chip to multiple other chips. If chips 1 and 2 give a wrong result, the likelihood that comparing 1 to 3, 4, 5, and 6 all also giving wrong results in those four comparisons is greatly diminished. Since you know the percentage of wrong results, it's probably possible to do some math to calculate how many comparisons you need to do to completely eliminate the wrong results, or at least reduce it to an acceptable rate. In the real world you'd sure want to do that, and then some -- perhaps balancing the cost of each comparison, the cost of using/shipping bad chips, and needlessly tossing good chips.

You also don't clearly say what happens when you compare good vs. bad (good test and wrong result). A wrong result with bad vs. bad would be YES, wouldn't it? Make sure you cover all scenarios.

-
A good vs bad test and a wrong result will produce a YES. A bad vs bad OR good vs good and a wrong result will produce NO. – Anna Dec 5 '11 at 18:06
Thank you for clarifying. I don't think that changes the approach I recommend...I'm leaving those fine details for you. Multiple tests of a chip to several others is the only way to detect wrong results. – minnow Dec 5 '11 at 21:04

For the first problem I don't think divide and conquer is the best approach. You would just want to walk the list until you found a good pair. An explanation may help here:

``````Starting size = 100
First split = 50/50
Second split = 25,25 / 25,25
Third split = 12,13,12,13/ 12,13,12,13
Fourth split = 6,6,6,7,6,6,6,7/ 6,6,6,7,6,6,6,7
Fifth split = 3,3,3,3,3,3,3,4,3,3,3,3,3,3,3,4/3,3,3,3,3,3,3,4,3,3,3,3,3,3,3,4
etc.
``````

Then we start working on each of those pairs until we find a good one. This is far less efficient than just walking a list for a good pair.

In terms of the second problem this is a general manufacturing problem so solving it is not as straight forward as one would think. The reason why it is hard is that it means that the testing program is inheritently incorrect. It is why when you buy a new laptop it can pass system test and fail to function when you get it home and turn it on. There is not yet a practical answer for this in the real world, so solving it makes you rich (essentially). The following page provides some analysis on the chip problem: chips

-
Thanks for the solution. But I am trying to find a good approximation for the second part. Or an exact solution if it exists (for a very low error rate) – Anna Dec 3 '11 at 19:45
@Anna the exact solution has not yet been released to the public, as far as i know. The link I provided supplies a little bit of analysis on it. – Woot4Moo Dec 3 '11 at 19:48
How do you know which is 'a good pair'? You can only know that a pair is 'same' or 'different'. – Caleb Dec 4 '11 at 13:51
@Caleb it is implied by the question we can only tell if both chips are good or bad. Meaning that there will be no result in the event that there is one of each. Therefore when both are good the machine returns good and when both are bad the machine returns bad. – Woot4Moo Dec 4 '11 at 17:20
I understand it differently: it seems to me that the test returns YES if two chips are the same (either both good or both bad) and NO if the chips are different. – Caleb Dec 4 '11 at 17:32

The test for sameness lets you divide the chips into two piles. Select any chip and test all the others against it, putting the chips into 'same' and 'different' piles (the selected chip goes into the 'same' pile). It doesn't matter whether the selected chip is good or bad -- you have no way to know that until the testing is done. Then use your knowledge about the distribution of good and bad chips to figure out which pile is which.

For part two, realize that your confidence in a given chip increases as it tests 'same' against other chips thought to be good.

-