|
坏芯片可以任意输出被测试芯片的好坏结果，当坏芯片多余n/2且有“智能”时，所有芯 片的检测结果可以是一样的。当坏芯片数大于n/2的话，那么把芯片分成三个集合：
k个好芯片，定义为集合Gk个坏芯片，定义为集合Hj个坏芯片，定义为集合I 其中n=2k+j，将坏芯片可以联合起来欺骗教授定义为，坏芯片清楚自己所在的集合，清楚自 己所在的测试装置的位置，和与自己放在一起的芯片所在的集合。如此，将测试结果为“芯 片是好的”定义为1，坏的定义为0，每个芯片的测试结果是如下结果中的一种：
B芯片取自GB芯片取自HB芯片取自IA芯片取自Gk-1个(1, 1)k个(x, 0)j个(x, 0)A芯片取自Hk个(0, x)k-1个(x, x)j个(x, x)A芯片取自Ik个(0, x)k个(x, x)j-1个(x, x) 这样只要坏芯片采用如此策略就能使所有芯片的检查结果都相同：
对取自集合H的芯片
在对好芯片测试时，将好芯片污蔑成坏芯片；在与H集合的芯片进行测试时，认为H集合的芯片都是好芯片（包括自身）；在与I集合的芯片进行测试时，在A位时，认为I集合的芯片是坏芯片，在B位时，提 前选择某一芯片认为自己是I集合的成员，并且认为I是好芯片。 对取自集合I的芯片
在B位时，都认为A都是好芯片在A位时，将好芯片污蔑成坏芯片，认为H中芯片是好芯片，认为I中其他芯片是坏芯 片。 采用这种策略时，所有芯片的检测结果都是k-1个(1, 1)，k个(0, 0)，j个(1, 0)。
|