Dato un set di chip VLSI, come posso determinare quali sono buoni?

Penso che questo sia un problema di cluster: hai due cluster: i chip buoni e quelli cattivi. Il tuo test ti dice se due chip appartengono allo stesso cluster o meno - almeno sotto il mio interpetation della domanda che hai chiesto. Il riferimento fornito nella risposta di Woot4Moo suggerisce una diversa domanda a questo.

Per la prima parte del test, scegli un chip e prova ogni altro chip contro di esso. Ottieni due cluster di chip, quelli che sono dello stesso tipo del primo chip e quelli che sono diversi. I buoni chip sono nel cluster più grande, quindi sceglierne uno a caso.

Per la seconda parte, usa n chip per il testing, in modo che per ogni chip tu abbia un pattern n-bit, dicendo se si trovava nello stesso cluster di ciascuno dei n chip di test. Aspettatevi di vedere per lo più due tipi di modelli, ciascuno l'inverso dell'altro. Puoi usarlo per ordinare i chip in due cluster come prima, e sperare che il cluster più grande sia composto da buoni chip.

Per trovare i risultati sbagliati, vorrei confrontare ogni chip con altri chip diversi. Se i chip 1 e 2 danno un risultato errato, la probabilità che il confronto tra 1, 3, 4, 5 e 6 dia anche risultati errati in questi quattro confronti è strongmente diminuita. Poiché si conosce la percentuale di risultati errati, è probabilmente possibile eseguire alcuni calcoli matematici per calcolare quanti confronti è necessario eseguire per eliminare completamente i risultati errati o almeno ridurli a un tasso accettabile. Nel mondo reale ti piacerebbe farlo, e poi un po '- forse bilanciando il costo di ogni confronto, il costo dell'uso / spedizione di chip scadenti e gettando inutilmente chip buoni.

Inoltre non si dice chiaramente cosa succede quando si confronta bene con il cattivo (buon test e risultato errato). Un risultato errato con bad vs. bad sarebbe YES, no? Assicurati di coprire tutti gli scenari.

Per il primo problema, non credo che dividere e conquistare sia l'approccio migliore. Vorresti solo percorrere l'elenco fino a quando non hai trovato una buona coppia. Una spiegazione può aiutare qui:

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.    

Quindi iniziamo a lavorare su ciascuna di queste coppie finché non ne troviamo una buona. Questo è molto meno efficiente di una semplice lista per una buona coppia.

In termini di secondo problema, questo è un problema di produzione generale, quindi risolverlo non è così semplice come si potrebbe pensare. Il motivo per cui è difficile è che ciò significa che il programma di test è ereditamente errato. È per questo che quando acquisti un nuovo laptop può superare il test di sistema e non funzionare quando lo si porta a casa e accenderlo. Non c'è ancora una risposta pratica per questo nel mondo reale, quindi risolverlo ti rende ricco (essenzialmente). La seguente pagina fornisce alcune analisi sul problema del chip: chip

Il test dell'identità ti consente di dividere i chip in due pile. Seleziona qualsiasi chip e metti alla prova tutti gli altri contro di esso, mettendo i chip in pile "uguali" e "differenti" (il chip selezionato va nella stessa pila). Non importa se il chip selezionato è buono o cattivo - non hai modo di saperlo fino a quando il test non viene eseguito. Quindi usa le tue conoscenze sulla distribuzione di chip buoni e cattivi per capire quale pila è quale.

Per la seconda parte, renditi conto che la tua fiducia in un dato chip aumenta mentre prova lo stesso contro altri chip che si ritiene siano buoni.