DE10200833A1

DE10200833A1 - Gerät und Verfahren für eine Teststimuliverdichtung

Info

Publication number: DE10200833A1
Application number: DE10200833A
Authority: DE
Inventors: Kwame Osei Boateng
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2001-06-05
Filing date: 2002-01-10
Publication date: 2002-12-12
Also published as: JP2002365346A; US20020184587A1; US7260793B2

Abstract

Basierend auf dem Konzept einer Minimierung wurde ein Verfahren einer statischen Verdichtung für eine digitale Schaltung entwickelt. Das Verdichtungsverfahren ist eine Kombination von zwei Hauptprozeduren: eine für die Auswahl wesentlicher Teststimuli und die andere für die Eliminierung redundanter Teststimuli und ist effektiv beim Minimieren einer beliebigen Menge von Teststimuli, ohne irgendwelche der Teststimulie zu modifizieren.

Description

Hintergrund der Erfindung Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich allgemein auf das Testen digitaler Schaltungen und insbesondere auf ein Gerät zur Verdichtung von Teststimuli und ein Verfahren da für.

Beschreibung der verwandten Technik

Um die Produktion zuverlässiger Digital/Computersysteme sicherzustellen, werden Teststimuli erzeugt, um die Systeme zu testen. Für eine digitale Schaltung kann ein Teststimu lus ein einzelnes Eingabemuster oder eine Sequenz von Ein gabemustern sein, die eine initialisierende Teilsequenz, eine aktivierende oder sensibilisierende Teilsequenz und eine Fortpflanzungsteilsequenz umfaßt. In einigen Fällen ist die sensibilisierende Teilsequenz die gleiche wie die Fortpflanzungsteilsequenz. Im folgenden wird auch der Aus druck "Testvektor" verwendet, um einen allgemeinen Teststi mulus für eine digitale Schaltung zu repräsentieren, und der Ausdruck "Testmenge" wird verwendet, um eine Menge von Testvektoren zu repräsentieren.

Eine wichtige Aufgabe einer Testerzeugung besteht dar in, eine signifikante Fehlerüberdeckung mit den erzeugten Testvektoren für die zu testende Schaltung zu erzielen. Die Erzeugungsalgorithmen sind derart, dass, da es notwendig ist, sich auf eine Fehlerüberdeckung zu konzentrieren, sie Sätze oder Mengen von Testvektoren mit Redundanzen erzeu gen. Diese Redundanzen sind nicht einfach zu detektieren und haben eine große Menge von Testvektoren zur Folge.

Die Kosten einer Anwendung der großen Menge von Test vektoren sind hoch, da die Kosten einer Testanlage mit ih rer Speicherkapazität zusammenhängen. Folglich hat die Zahl von Testvektoren Auswirkungen auf die Kosten eines Tests, der bei der Produktion und Wartung zuverlässiger Digi tal/Computersysteme unabdingbar ist. Speicherkapazität ist einer der Hauptfaktoren, die die Kosten einer Testanlage bestimmen. Großer Speicher bedeutet hohe Kosten. Falls eine verfügbare Testanlage nicht genug Speicherkapazität zum La den aller Testvektoren aufweist, besteht dann die Notwen digkeit, die Testanlage während einer Testanwendung auf die zu testende Schaltung mehr als einmal zu laden. Mehr Test vektoren, als im Speicher der Testanlage enthalten sein können, verlangen eine Speicheraktualisierung (ein erneutes Laden einer Teilmenge der Testvektoren) während einer Test anwendung. Ein erneutes Laden der Testanlage während eines Tests verlängert die Testanwendungstest (TAT) signifikant. Sogar eine einzige Speicheraktualisierung führt zu einem großen Sprung in der Testanwendungszeit. Die lange Testan wendungszeit hat Einfluß auf die Markteinführungszeit der hergestellten IC-(integrierte Schaltungs-)Produkte.

Aus dem vorhergehenden ist evident, daß kleine Testmen gen wünschenswert sind, um Testkosten zu reduzieren und die Markteinführungszeit der zuverlässigen Systeme zu verkür zen. Folglich besteht die Notwendigkeit, eine kleine Zahl von Testvektoren beizubehalten. Reduzieren der Zahl der Testvektoren ohne der Fehlerüberdeckung zu schaden, wird Testverdichtung genannt. Testverdichtungsalgorithmen soll ten Wege finden, ohne Verringern einer Fehlerüberdeckung kleine Testmengen zu erreichen. Mit anderen Worten, die Al gorithmen sollten Zahlen von Testvektoren niedrig halten, während eine möglichst hohe Fehlerüberdeckung beibehalten wird.

Zwei Typen von Verdichtungstechniken existieren - eine dynamische und eine statische Verdichtung. Dynamische Tech niken versuchen, die Zahl von Testvektoren zu reduzieren, während sie gerade erzeugt werden. Oft erfordert eine dyna mische Verdichtung die Modifikation des Testgenerators. Statische Techniken trachten andererseits danach, die Zahl der schon erzeugten Testvektoren zu reduzieren. Folglich ist eine statische Verdichtung ein Nachverarbeitungsschritt zur Testerzeugung. Statische Techniken sind daher von den Testerzeugungsalgorithmen unabhängig und erfordern keine Modifikationen der Algorithmen. Selbst wenn eine dynamische Verdichtung während einer Testerzeugung verwendet wird, kann außerdem eine statische Verdichtung die Größe der er zeugten Testmenge weiter reduzieren. Dies legt nahe, daß eine statische Verdichtung beim Reduzieren der Größe von Testsätzen und daher der nachfolgenden Testkosten effekti ver ist.

Hsiao et al. haben in ihrer Arbeit über Verfahren einer Testsequenzverdichtung für sequentielle Schaltungen in den folgenden Dokumenten berichtet.

(1) M. S. Hsiao und T. Chakradhar, "Partitioning and reordering techniques for static test sequence compaction of sequential circuits," Proc. of the 7th IEEE Asian Test Symposium, S. 452-457, 1998.
(2) M. S. Hsiao und S. T. Chakradhar, "State relaxation based subsequence removal for fast static compaction in se quential circuits," Proc. of Design, Automation, and Test in Europe Conf., S. 577-582, 1998.
(3) M. S. Hsiao, E. M. Rudnick und J. H. Patel, "Fast algorithms for static compaction of sequential circuit test vectors," Proc. of IEEE VLSI Test Symposium, S. 188-195, 1997.
Ihre Verfahren trachten danach, die Sequenzen zu ver kürzen. Pomeranz et al. haben ein Verfahren einer effizien ten Speicherung von Testantworten im folgenden Dokument vorgeschlagen.
(4) I. Pomeranz und S. M. Reddy, "On test compaction objectives for combinational and sequential circuits," Proc. of IEEE International Conference on VLSI Design, S. 279-284, 1998.
Kajihara et al. und Hamzaoglu et al. haben über ihre Arbeit über eine Testmusterverdichtung für Verknüpfungs schaltungen in den folgenden Dokumenten berichtet.
(5) S. Kajihara und K. Saluja, "On test pattern compac tion using random pattern fault simulation," Proc. of IEEE International Conference on VLSI Design, S. 464-469, 1998.
(6) I. Hamzaoglu und J. H. Patel, "Test set compaction algorithms for combinational circuits," Proc. of ACM Inter national Conference on CAD, S. 283-289, 1997.

Sie haben Verfahren einer statischen Verdichtung entwi ckelt, die darauf zugeschnitten sind, mit früher vorge schlagenen Verfahren zum Erzeugen von kompakten Tests zu sammenzuarbeiten.

Digitale Systeme verwenden sowohl sequentielle als auch Verknüpfungsschaltungen. Verschiedene Testpakete verwenden auch verschiedene Testerzeugungsalgorithmen. Daher besteht für eine allgemeine digitale Schaltung der Bedarf an einem allgemeinen Verfahren einer statischen Testverdichtung, de ren Effektivität von jedem Testerzeugungsalgorithmus voll ständig unabhängig ist.

Zusammenfassung der Erfindung

Eine Aufgabe der vorliegenden Erfindung ist, ein Gerät für eine Teststimuliverdichtung, das zum Testen einer all gemeinen digitalen Schaltung verwendbar ist, und ein Ver fahren dafür zu schaffen.

Das Verdichtungsgerät gemäß der vorliegenden Erfindung enthält eine Auswahlvorrichtung, eine Eliminierungsvorrich tung und eine Ausgabevorrichtung und führt eine Verdichtung einer Menge von Teststimuli für eine digitale Schaltung durch.

Die Auswahlvorrichtung wählt wesentliche Teststimuli aus Teilmengen des Satzes oder der Menge von Teststimuli aus. Ein Fehler in der digitalen Schaltung, der durch einen wesentlichen Teststimulus detektierbar ist, ist durch kei nen anderen Teststimulus in einer gegebenen Teilmenge von Teststimuli detektierbar. Die Eliminierungsvorrichtung eli miniert redundante Teststimuli aus Teilmengen von Teststi muli nach der Auswahl wesentlicher Teststimuli aus jeder Teilmenge. Die Ausgabevorrichtung gibt eine verdichtete Menge mit den ausgewählten wesentlichen Teststimuli aus. Jede zur Auswahlvorrichtung geschickte Teilmenge ist die Obermenge der nächsten Teilmenge, die zur Auswahlvorrich tung geschickt werden soll.

Kurze Beschreibung der Zeichnungen

Fig. 1 zeigt das Prinzip eines Teststimuli-Verdich tungsgeräts gemäß der vorliegenden Erfindung;

Fig. 2 zeigt eine Überdeckungstabelle einer Testmenge;

Fig. 3 zeigt eine partielle Überdeckungstabelle der Testmenge;

Fig. 4 zeigt ein Flußdiagramm eines Verdichtungsprozes ses;

Fig. 5 zeigt ein Flußdiagramm eines Prozesses in der ersten Phase;

Fig. 6 zeigt den ersten Teil eines Flußdiagramms eines Prozesses in der zweiten Phase;

Fig. 7 zeigt den zweiten Teil des Flußdiagramms des Prozesses in der zweiten Phase;

Fig. 8 zeigt die anfängliche Vektor-auf-Fehler- Abbildung;

Fig. 9 zeigt eine aktualisierte Vektor-auf-Fehler- Abbildung;

Fig. 10 zeigt eine weiter aktualisierte Vektor-auf- Fehler-Abbildung;

Fig. 11 zeigt ein Beispiel einer digitalen Schaltung;

Fig. 12 zeigt eine Testmenge für die digitale Schal tung;

Fig. 13 zeigt eine Zusammenfassung der partiellen Über deckungstabelle;

Fig. 14 zeigt ein Modell mit behaftetem Fehler;

Fig. 15 zeigt ein Verzögerungsfehlermodell;

Fig. 16 zeigt die Konfiguration eines Informationsver arbeitungsgerätes; und

Fig. 17 zeigt Aufzeichnungsmedien.

Beschreibung der bevorzugten Ausführungsformen

Die Ausführungsformen der vorliegenden Erfindung werden im folgenden durch Verweisen auf die beigefügten Zeichnun gen ausführlich beschrieben.

Fig. 1 zeigt das Prinzip eines Teststimuli-Verdich tungsgerätes gemäß der vorliegenden Erfindung. Das Verdich tungsgerät enthält eine Auswahlvorrichtung D1, eine Elimi nierungsvorrichtung D2 und eine Ausgabevorrichtung D3 und führt eine Verdichtung einer Menge von Teststimuli für eine digitale Schaltung durch.

Die Auswahlvorrichtung D1 wählt wesentliche Teststimuli unter Teilmengen der Menge von Teststimuli aus. Ein Fehler in der digitalen Schaltung, der durch einen wesentlichen Teststimulus detektierbar ist, ist durch keinen anderen Teststimulus in einer gegebenen Teilmenge von Teststimuli detektierbar. Die Eliminierungsvorrichtung D2 eliminiert redundante Teststimuli aus Teilmengen von Teststimuli nach der Auswahl der wesentlichen Teststimuli aus jeder Teilmen ge. Die Ausgabevorrichtung D3 gibt eine verdichtete Menge mit den ausgewählten wesentlichen Teststimuli aus.

Wenn die Menge von Teststimuli (oder die Teilmenge von Teststimuli von der Eliminierungsvorrichtung D2) gegeben ist, wählt die Auswahlvorrichtung D1 die gegenwärtig iden tifizierbare Menge wesentlicher Teststimuli unter den gege benen Teststimuli aus und läßt sie zur Ausgabevorrichtung D3 und die verbleibenden Teststimuli zur Eliminierungsvor richtung D2 durch. Die Eliminierungsvorrichtung D2 elimi niert die gegenwärtig identifizierbare Menge redundanter Teststimuli, die in der Teilmenge von Teststimuli enthalten sind, die von der Auswahlvorrichtung D1 empfangen wurde, und leitet die verbleibenden Teststimuli zur Auswahlvor richtung D1 zurück. Diese Prozedur setzt sich fort, bis keine Teststimuli übrig sind. Die Ausgabevorrichtung D3 gibt dann die wesentlichen Teststimuli, die von der Aus wahlvorrichtung D1 empfangen wurden, als die verdichtete Menge von Teststimuli aus.

Gemäß solch einem Verdichtungsgerät werden verschiedene Hierarchien wesentlicher Teststimuli, die für die Detektion aller durch die ursprüngliche Testmenge detektierbaren Feh ler unabdingbar sind, aus der gegebenen Testmenge extra hiert. Da dieses Verdichtungsverfahren von dem Testerzeu gungsalgorithmus vollkommen unabhängig ist, ist es beim Durchführen statischer Verdichtungen von Teststimuli effek tiv, die durch einen beliebigen Erzeugungsalgorithmus er zeugt wurden.

Die Auswahlvorrichtung D1 und die Eliminierungsvorrich tung D2 in Fig. 1 entsprechen z. B. einer Kombination der CPU (zentralen Verarbeitungseinheit) 51 und des Speichers 52, die in Fig. 16 dargestellt sind, welche später be schrieben wird. Die Ausgabevorrichtung D3 in Fig. 1 ent spricht z. B. der Kombination der CPU 51 und des Speichers 52, der Ausgabevorrichtung 54 oder der Netzwerkverbindungs vorrichtung 57, die in Fig. 16 dargestellt sind. Die we sentlichen Teststimuli entsprechen den im folgenden be schriebenen Testvektoren.

In den folgenden Ausführungsformen wird die Aufgabe der statischen Verdichtung einer Menge von Teststimuli (Test vektoren) als ein Problem einer minimalen Überdeckung for muliert. In der Tat findet das Verdichtungsgerät die mini male Teilmenge der ursprünglichen Teilmenge, die alle Feh ler detektieren (überdecken oder erfassen) kann, die in der Zielschaltung detektierbar sind, durch die ursprüngliche Testmenge, ohne irgendeinen der Testvektoren zu modifizie ren. Das von dem Verdichtungsgerät verwendete Verfahren ist eine intelligente Kombination von zwei Hauptprozeduren: ei ne für die Auswahl von wesentlichen Testvektoren und die andere für die Eliminierung von redundanten Testvektoren.

Das Verdichtungsgerät verwendet eine Datenstruktur, die es möglich macht, Speicher verbrauchende Matrizen zu ver meiden, die mit dem Konzept einer minimalen Erfassung ver bunden sind, wodurch eine effiziente Laufzeit sicherge stellt wird. Um sicherzustellen, daß die Lösung des Mini mierungsproblems die minimale Testmenge ist, wird bei der Eliminierung von redundanten Testvektoren ein Sortieralgo rithmus verwendet. Das Grundkonzept der statischen Verdich tung lautet wie folgt:
Definition 1:
Die Menge aller Fehler, F_Menge, die in der Schaltung C durch eine Menge T von Testvektoren detek tierbar sind, bildet die Überdeckung von T_Menge. Eine die Überdeckung von F_Menge durch T_Menge darstellende Tabelle wird die Überdeckungstabelle von T_Menge genannt.

Definition 2:
Der Fehler f in der Schaltung C sei durch ei nen ersten Testvektor t_ep einer Testmenge T_Menge detektierbar. Falls kein anderer Testvektor von T_Menge f detektiert, ist dann t_ep ein wesentlicher Vektor von T_Menge, und der Fehler f ist ein wesentlicher Fehler von C bezüglich T_Menge.

Das Konzept einer minimalen Überdeckung ist ein wohlbe kannter Algorithmus, der in einer Logikoptimierung oft ver wendet wird. Der Algorithmus weist einen Nachteil insofern auf, als er großen Speicherplatz erfordert.

Man berücksichtige, daß die Menge T = {t₁, t₂, t₃, t₄, t₅, t₆, t₇} von Testvektoren alle behafteten Fehler auf Lei tungen L₁, L₂, L₃, L₄, L₅, L₆ überdeckt, welche einen Teil ei ner Schaltung C bilden. Die entsprechende Fehlermenge sei F = (f₁, f₂, f₃, f₄, . . ., f₁₁, f₁₂), und die Überdeckungstabelle von T sei wie in Fig. 2 dargestellt. In dieser Überde ckungstabelle gibt das Symbol "×" im Schnittpunkt der Reihe t_i und der Spalte f_j an, daß ein Vektor t_i einen Fehler f_j unter der Einzelfehlerannahme (f_j ist der einzige Fehler in der zu testenden Schaltung) detektiert. Aus der Tabelle kann man erkennen, daß t₃, t₅, t₆, t₇ wesentliche Vektoren von T entsprechend den wesentlichen Fehlern f₉, f₁₀, f₁₁, f₁₂ sind. Wenn t₃, t₅, t₆, t₇ aus T entfernt werden und alle Feh ler, die sie überdecken, aus der ursprünglichen Überdeckung F entfernt werden, haben wir die in Fig. 3 dargestellte Si tuation. Keiner der in F übrigen Fehler (f₁ und f₃) ist be züglich der aktualisierten Testmenge T = {t₁, t₂, t₄} we sentlich.

Wenn die verbleibenden Testvektoren t₁, t₂, t₄ in T auf ihre Überdeckung der verbleibenden Fehler (in dieser Rei henfolge) geprüft werden, wird festgestellt, daß t₄ redun dant ist. Wenn der identifizierte redundante Testvektor t₄ gelöscht wird, wird f₃ ein wesentlicher Fehler bezüglich T = {t₁, t₂}, und t₂ wird der entsprechende wesentliche Vek tor. Auswählen des wesentlichen Vektors t₂ aus T und Ent fernen der durch ihn detektierbaren Fehler aus der Menge F = {f₁, f₃} leert F. Der verbleibende Testvektor t, in T wird somit ebenfalls gelöscht. Folglich ist nun die verdichtete Testmenge CT = {t₂, t₃, t₅, t₆, t₇} ohne die Vektoren t₁, t₄.

Im wesentlichen besteht dieses Verfahren darin, eine statische Verdichtung durch einige wenige Wiederholungen der Auswahl wesentlicher Vektoren und Löschen identifizier ter redundanter Vektoren auszuführen. Dieser Nutzen des Verdichtungsverfahrens wird wie folgt dargestellt.

Lemma 1:
Mit Verweis auf eine gegebene Menge von Feh lern in einer Schaltung C weist eine beliebige Testmenge T ohne wesentliche Vektoren mindestens einen Testvektor t auf, der bezüglich der Menge T = T\{t} redundant ist.

Beweis:
Man nehme an, daß bei einem Zyklus der Wieder holung die Testvektoren τ₁, τ₂, . . ., τ_i, . . ., τ_N; übrig sind. Man nehme an, daß es keine wesentlichen Vektoren in den verbleibenden Testvektoren gibt. Folglich ist jeder Fehler in der Überdeckung einer Menge der verbleibenden Testvek toren, der durch den Vektor τ_j detektierbar ist, auch durch einen anderen Vektor τ_k (d. h. k ≠ j) in der gleichen Menge detektierbar. Folglich ist zumindest τ_j redundant. Q. E. D.

Lemma 1 zeigt, daß im Prozeß einer wiederholten Anwen dung einer Auswahl wesentlicher Vektoren und des Löschens redundanter Vektoren keine Situation einer Systemverklem mung auftritt, bei der es weder wesentliche Vektoren noch redundante Vektoren gibt.

Eine Verarbeitung der verbleibenden Daten, wie früher (mit Fig. 3) erläutert wurde, kann zu einer nicht-minimalen Lösung führen. Falls z. B. t₂ zufällig nur f₃ detektiert und t₄ zufällig f₁ zusätzlich zu f₃ detektiert, würden dann t₁ und t₂ ausgewählt werden, t₄ als redundant zurücklassend. In diesem Fall wird der Prozeß nur einen Vektor, t₄, eliminie ren. Im Hinblick darauf wird die folgende Verarbeitung durchgeführt, um eine minimale Lösung für das statische Verdichtungsproblem sicherzustellen.

Zuerst wird eine Teilmenge von Teststimuli identifi ziert, die eine gegebene Menge von Fehlern optimal über deckt. Zweitens werden ein oder mehr Teststimuli, die von den identifizierten Teststimuli verschieden sind, als die redundanten Teststimuli eliminiert.

Nach der Auswahl jeder Menge wesentlicher Vektoren ist der erste der verbleibenden n Testvektoren, die zurückzube halten sind, der eine, der die größte Zahl der verbleiben den Fehler in der Menge F detektiert. Der zweite, zurückzu behaltende Vektor ist derjenige, der die größte Zahl der Fehler in der Menge S = F\C₁ detektiert; wo C₁ die Menge von Fehlern in F ist, die durch den ersten zurückbehaltenen Vektor detektierbar sind. Im allgemeinen ist der zurückzu behaltende i-te Vektor derjenige, der die größte Zahl der Fehler in der Menge S = F\Γ detektiert; wo

ist und C_j die Menge von Fehlern in F ist, die durch den zu rückbehaltenen j-ten Vektor detektierbar sind. Diese Verar beitung setzt sich fort, bis Γ = F nach dem k-ten zurückbe haltenen Vektor gilt. An dieser Stelle werden die restli chen (n-k) Vektoren gelöscht, und ein anderer Zyklus be ginnt mit der Auswahl der nächsten Hierarchie von wesentli chen Vektoren.

Eine direkte Anwendung des minimalen Überdeckungsalgo rithmus ist mit einer Matrix für die Überdeckungstabelle von Testvektoren verbunden. Für praktische Schaltungen wird dies eine große Menge an Speicher erfordern, die nicht zur Verfügung stehen kann. Folglich wird diese Situation eine Beschränkung der Anwendbarkeit des Verfahrens auf prakti sche Schaltungen auferlegen. Um dieses Problem zu umgehen, wird der zweidimensionale Datenraum einer Matrix auf den besser verwaltbaren eindimensionalen Datenraum reduziert.

Dies wird wie folgt erreicht.

Zuerst wird jedem Fehler ein Zähler zugeordnet. Jeder Zähler gibt die Zahl von Testvektoren an, durch die der entsprechende Fehler detektierbar ist. Eine Simulation der Zielschaltung wird mit der ursprünglichen Testmenge durch geführt. Für jeden Testvektor werden detektierbare Fehler von den primären Ausgaben aus zurückverfolgt. Jedesmal wenn ein Fehler verfolgt wird, wird der dem Fehler zugeordnete Zähler inkrementiert. Die Testvektoren werden ebenfalls auf die Fehler abgebildet.

In dieser Simulation kann ein in den folgenden Dokumen ten dargestelltes Verfahren angewendet werden. Dieses Ver fahren erleichtert die Extraktion von Information über Feh ler, die durch die ursprüngliche Testmenge überdeckt wer den, ohne eine repetitive Fehlersimulation durchzuführen.

(7) K.O. Boateng, H. Takahashi und Y. Takamatsu, "Di agnosing delay faults in combinational circuits under the ambiguous delay model," IEICE Transaction on Information and Systems, Bd. E82-D, Nr. 12, S. 1563-1571, Dez. 1999.
(8) K.O. Boateng, H. Takahashi und Y. Takamatsu, "Mul tiple gate delay fault diagnosis using test-pairs for mar ginal delays," IEICE Transaction on Information and Sys tems, Bd. E81-D, Nr. 7, S. 706-715, Juli 1998.
(9) N. Yanagida, H. Takahashi und Y. Takamatsu, "Multi ple fault diagnosis by sensitizing input pairs", IEEE De sign & Test of Computers, Bd. 12, Nr. 3, S. 44-52, Sept. 1995.

Alle Fehler mit einem Zähler = 1 sind wesentliche Feh ler, und die jeweiligen Testvektoren, die auf sie abbil deten, bilden die wesentlichen Vektoren. Jedes Mal wenn ein wesentlicher Vektor ausgewählt wird, werden alle Fehler, die er detektiert, aus der Fehlermenge entfernt. Jedesmal wenn ein redundanter Testvektor identifiziert wird, wird auch der Zähler jedes Fehlers in der aktualisierten Fehler menge, auf die er abgebildet wird, dekrementiert.

Fig. 4 zeigt einen Prozeß der statischen Verdichtung, der von dem Verdichtungsgerät durchgeführt wird. Dieser Prozeß weist zwei Phasen auf. In der ersten Phase werden Simulationen durchgeführt, und eine Fehlerverfolgung wird ausgeführt, um die Vektor-auf-Fehler-Abbildung einzurichten (Schritt S1). Während einer Fehlerverfolgung wird ein In krementieren des Fehlerzählers durchgeführt. In der zweiten Phase werden der Prozeß einer Auswahl wesentlicher Vektoren und der Prozeß eines Löschens redundanter Vektoren durchge führt (Schritt S2).

Fig. 5 zeigt einen Prozeß, der in der ersten Phase durchgeführt wird. Zuerst führt das Verdichtungsgerät Simu lationen durch, um die Vektor-auf-Fehler-Abbildung einzu richten, und inkrementiert Zähler, während die Fehler, de nen sie zugeordnet sind, verfolgt werden (Schritt S11). Als nächstes legt das Verdichtungsgerät alle Testvektoren in die Menge T_Menge und alle verfolgten Fehler in die Menge F_Menge (Schritt S12). Das Verdichtungsgerät setzt dann je de der Mengen CT_Menge, T1_Menge und F\C1_Menge auf die leere Menge {} (Schritt S13). Der Prozeß im Schritt S11 ist nicht notwendig, wenn das ähnliche Ergebnis aus einer Test erzeugung erhalten wird.

Fig. 6 und 7 zeigen einen Prozeß, der in der zweiten Phase durchgeführt wird. Zuerst findet das Verdichtungs gerät alle gegenwärtigen wesentlichen Fehler (Schritt S21 in Fig. 6) und identifiziert ihre entsprechenden wesentli chen Vektoren (Schritt S22). Als nächstes läßt das Verdich tungsgerät alle durch die identifizierten wesentlichen Vek toren detektierbaren Fehler aus F_Menge fallen (Schritt S23) und überträgt die identifizierten wesentlichen Vekto ren von T_Menge in CT_Menge (Schritt S24). Ob F_Menge leer ist, wird danach geprüft (Schritt S25).

Falls F_Menge leer ist, löscht das Verdichtungsgerät alle Testvektoren in T_Menge als redundante Testvektoren und beendet den Prozeß. Falls F_Menge nicht leer ist, fin det das Verdichtungsgerät in T_Menge den Testvektor rt mit der größten Überdeckung von Fehlern in F_Menge (Schritt S26), legt rt in T1_Menge (Schritt S27) und überträgt alle Fehler in F_Menge, die durch rt detektierbar sind (über deckt werden), in F\C1_Menge (Schritt S28). Ob F_Menge leer ist, wird danach wieder geprüft (Schritt S29).

Falls F_Menge nicht leer ist, werden die Prozesse in und nach Schritt S26 wiederholt. Falls F_Menge leer ist, dekrementiert dann das Verdichtungsgerät für jeden noch in T-Menge verbleibenden Testvektor τ den Zähler des Fehlers in F\C1_Menge, der durch τ detektierbar ist (Schritt S30 in Fig. 7). Als nächstes löscht das Gerät alle Testvektoren, die in T_Menge verbleiben, als redundante Testvektoren (Schritt S31). Das Verdichtungsgerät leert dann F\C1_Menge in F_Menge (Schritt S32) und T1_Menge in T_Menge (Schritt S33) und wiederholt die Prozesse in und nach Schritt S21 in Fig. 6. Gemäß solch einem Verdichtungsprozeß wird die verdichte te Testmenge am Ende einer Verdichtung in CT_Menge gespei chert.

Nach dem Prozeß der ersten Phase werden die Daten der Überdeckungstabelle, die in Fig. 2 dargestellt ist, wie in Fig. 8 gezeigt organisiert. In dieser Datenstruktur geben T_Menge = {t₁, t₂, t₃, t₄, t₅, t₆, t₇}, F_Menge {f₁, f₂, f₃, f₄, . . ., f₁₁, f₁₂} und Pfeile von jedem Testvektor in T_Menge auf Fehler in F_Menge an, daß sie die Fehler überdeckt. Zähler = 1 ist das Kriterium für die Identifizierung we sentlicher Fehler und daher wesentlicher Vektoren, und die Pfeile von wesentlichen Vektoren sind in dicken Linien dar gestellt.

T_Menge, F_Menge und Zähler werden z. B. jeweils in ein dimensionalen Arrays gespeichert, und ein Pfeil von einem Testvektor zu einem Fehler wird durch eine Zeiger-Informa tion wie z. B. einen entsprechenden Index des Arrays von F_Menge repräsentiert. Der Testvektor ist somit dem Fehler zugeordnet.

Nach Auswählen gegenwärtiger wesentlicher Vektoren, Fallenlassen aller Fehler, die sie überdecken, und Aktuali sieren von T_Menge und F_Menge ist die neu aktualisierte Abbildung in Fig. 9 dargestellt. Die verbleibenden Testvek toren können in der Reihenfolge t₁ → t₂ → t₄ geprüft wer den, um zu untersuchen, wie viele der verbleibenden Fehler durch jeden Detektor detektierbar sind. Dies führt zur Identifizierung von t₂ als dem Testvektor mit der größten Überdeckung. Ein Übertragen von t₂ in T1_Menge und f₁ und f₃ in F\C1_Menge leert F_Menge. Daher werden t₁ und t₄ gelöscht, und die Zähler von f₁ und f₃ (die durch t₁ und t₄ detektier baren Fehler) werden dekrementiert. Die aktualisierte T_Menge und F_Menge werden wie in Fig. 10 dargestellt auf gezeichnet, und t₂ ist als ein auszuwählender wesentlicher Vektor übrig. Auswählen von t₂ und Fallenlassen der Fehler in F_Menge, die durch t₂ detektierbar sind, führen zum Lee ren von F_Menge. Daher ergibt die verdichtete Testmenge CT_Menge = {t₂, t₃, t₅, t₆, t₇}.

Fig. 11 zeigt ein konkretes Beispiel der zu testenden Schaltung. Eine Testmenge für die Schaltung ist in Fig. 12 dargestellt. Muster von 16 Testvektoren sind in einer 3- wertigen Logik ausgedrückt, wo "2" die unbekannte Logik repräsentiert. Im folgenden wird F_ti verwendet, um die Menge von Fehlern zu symbolisieren, die durch den Testvektor t_i (i = 1, 2, . . ., 16) detektiert werden, und ein α-behafteter Fehler (α = 0, 1) bei einer Leitung L (L = 1, 2, 3, . . ., 36, 37, 38) wird als L/α repräsentiert.

F_t1 = {1/1; 2/0; 5/0; 6/1; 9/0; 13/1; 15/0; 16/0; 17/0; 18/1; 19/0; 24/1; 25/0; 26/0; 27/0; 29/1; 30/1; 32/1; 33/1; 34/1; 36/1; 38/0}

F_t2 = {1/0; 5/0; 6/0; 13/0; 14/0; 15/0; 16/0; 17/1; 18/1; 19/1; 21/1; 24/1; 25/1; 29/0; 32/0}

F_t3 = {2/1; 4/1; 10/1; 15/1; 18/0; 24/0; 25/0; 29/1; 32/1}

F_t4 = {2/0; 5/0; 10/0; 15/0; 16/0; 18/1; 24/1}

F_t5 = {2/1; 3/1; 4/0; 5/0; 8/1; 9/1; 11/1; 14/1; 15/0; 16/0; 17/0; 18/1; 19/0; 22/1; 24/1; 25/0; 27/1; 29/1; 30/0; 32/1; 34/0; 35/0; 36/0; 37/0; 38/1}

F_t6 = {1/0; 2/1; 3/0; 4/0; 5/0; 6/0; 9/1; 11/0; 13/0; 14/0; 15/0; 16/0; 17/1; 18/1; 19/1; 21/1; 22/1; 24/1; 25/1; 27/1; 29/0; 30/0; 32/0; 35/0; 36/0; 37/0; 38/1}

F_t7 = {4/0; 5/0; 15/0; 16/0; 18/1; 24/1; 36/0; 37/0; 38/1}

F_t8 = {5/1; 16/1; 18/0; 24/0; 25/0; 29/1; 32/1}

F_t9 = {5/0; 15/0; 16/0; 18/1; 24/1}

F_t10 = {5/1; 16/1; 18/0; 24/0; 25/0; 29/1; 32/1; 38/0}

F_t11 = {1/0; 2/0; 3/1; 5/0; 6/0; 8/0; 12/1; 13/0; 14/0; 15/0; 16/0; 17/1; 18/1; 19/1; 20/1; 21/1; 24/1; 25/1; 26/1; 29/0; 30/0; 32/0; 35/0; 36/0; 37/0; 38/1}

F_t12 = {1/1; 2/1; 4/0; 5/0; 6/1; 9/1; 13/1; 15/0; 16/0; 17/0; 18/1; 19/0; 22/1; 24/1; 25/0; 27/1; 29/1; 30/0; 32/1; 34/0; 36/0; 37/0; 38/1}

F_t13 = {1/1; 2/0; 5/0; 6/1; 9/0; 13/1; 15/0; 16/0; 17/0; 18/1; 19/0; 24/1; 25/0; 26/0; 27/0; 29/1; 30/1; 32/1; 33/1; 34/1; 36/1; 38/0}

F_t14 = {1/0; 2/0; 3/1; 5/0; 6/0; 8/0; 12/1; 13/0; 14/0; 15/0; 16/0; 17/1; 18/1; 19/1; 20/1; 21/1; 24/1; 25/1; 26/1; 29/0; 30/0; 32/0; 35/0; 36/0; 37/0; 38/1}

F_t15 = {1/0; 2/0; 3/0; 5/0; 6/0; 7/0; 9/0; 12/0; 13/0; 14/0; 15/0; 16/0; 17/1; 18/1; 19/1; 21/1; 24/1; 25/1; 26/0; 27/0; 28/0; 29/0; 30/1; 31/1; 32/0; 35/1; 37/1; 38/0}

F_t16 = {5/1; 16/1; 18/0; 24/0; 25/0; 29/1; 32/1; 38/0}

Bei der Anfangsstufe der zweiten Phase, die in Fig. 6 dargestellt ist, werden t₃, t₄, t₅, t₆, t₁₅ als wesentliche Vektoren identifiziert. Nach Auswählen der wesentlichen Vektoren und Fallenlassen aller Fehler, die sie detektie ren, sind die verbleibenden Daten wie in Fig. 13 darge stellt. F_Menge = {1/1; 5/1; 6/1; 8/0; 12/1; 13/1; 16/1; 20/1; 26/1; 33/1; 34/1; 36/1} am Beginn des Prozesses zur Eliminierung redundanter Vektoren und die Vektoren t₁, t₂, t₇, t₈, t₉, t₁₀, t₁₁, t₁₂, t₁₃, t₁₄, t₁₆ detektieren 6, 0, 0, 2, 0, 2, 4, 3, 6, 4 bzw. 2 der verbleibenden Fehler. t₁ wird zuerst als rt₁ mit C₁ = (1/1; 6/1; 13/1, 33/1; 34/1; 36/1) ausgewählt. F_Menge\C₁ = (5/1; 8/0; 12/1; 16/1; 20/1; 26/1} und Vektoren t₂, t₇, t₈, t₉, t₁₀, t₁₁, t₁₂, t₁₃, t₁₄, t₁₆ detektie ren 0, 0, 2, 0, 2, 4, 0, 0, 4 bzw. 2 der verbleibenden Feh ler. Als nächstes wird t₁₁ als rt₂ mit C₂ = {8/0; 12/1; 20/1; 26/1} ausgewählt. Nun detektieren F_Menge\(C₁∪C₂) = {5/1; 16/1} und Vektoren t₂, t₇, t₈, t₉, t₁₀, t₁₂, t₁₃, t₁₄, t₁₆ 0, 0, 2, 0, 2, 0, 0, 0 bzw. 2 der verbleibenden Fehler. t₈ wird als rt₃ mit C₃ = {5/1; 16/1} ausgewählt. Bei dieser Stufe ist F_Menge (C₁∪C₂∪C₃) = { }; folglich ist C₁∪C₂∪C₃ = F_Menge. Jeder der restlichen Vektoren t₂, t₇, t₉, t₁₀, t₁₂, t₁₃, t₁₄, t₁₆ wird gelöscht nach einem Dekrementieren der De tektionszähler aller Fehler, die er überdeckt, und der ge genwärtige Prozeß einer Eliminierung redundanter Vektoren endet.

Alle Fehler in der F_Menge = {1/1; 5/1; 6/1; 8/0; 12/1; 13/1; 16/1; 20/1; 26/1; 33/1; 34/1; 36/1} wurden wesent lich, und daher bilden rt₁ = t₁, rt₂ = t₁₁ und rt₃ = t₈ die zweite Hierarchie wesentlicher Vektoren. Ein Addieren die ser drei Vektoren zu der früheren Menge wesentlicher Vek toren ergibt die Menge {t₁, t₃, t₄, t₅, t₆, t₈, t₁₁, t₁₅} aus acht Vektoren, die alle die Fehler überdecken, die durch die ursprüngliche Testmenge aus 16 Vektoren detektierbar sind. Folglich halbiert der Verdichtungsprozeß die Testmen ge, während sichergestellt wird, daß sich die Fehlerüberde ckung nicht ändert.

Selbst wenn die oben beschriebenen Beispiele das Modell mit behaftetem Fehler verwenden, kann der Verdichtungspro zeß der vorliegenden Erfindung auf andere Fehlermodelle an gewendet werden. Die Größe eines Teststimulus für eine Ver knüpfungsschaltung hängt vom Testmodell ab. Im folgenden werden zur Veranschaulichung die Modelle mit behaftetem Fehler und Verzögerungsfehler verwendet.

Fig. 14 veranschaulicht das Modell mit behaftetem Feh ler. Ein 0-behafteter Fehler am Ausgang eines UND-Gatters G1 wird ungeachtet des Eingabemusters einen Ausgabewert 0 veranlassen. Um den Fehler zu detektieren, wird ein einzi ges Eingabemuster "1, 1", das versucht, die Ausgabe auf ei ne logische 1 zu setzen, angewendet. Falls die erwartete logische 1 am Ausgang beobachtet wird, existiert kein Feh ler. Auf der anderen Seite wird die Existenz des Fehlers bestätigt, falls der ausgegebene Logikwert 0 ist. Um einen behafteten Fehler zu testen, ist somit ein Teststimulus mit einem Eingabemuster notwendig.

Fig. 15 veranschaulicht das Verzögerungsfehlermodell. Ein Verzögerungsfehler ist die Situation, bei der der Ef fekt von Änderungen, die am Eingang eines Gatters auftre ten, eine längere Zeit in Anspruch nimmt als die erwartete, um sich zum Ausgang fortzupflanzen. Unter dem Übergangsver zögerungsfehlermodell werden Verzögerungsfehler durch Über gang und Zeitsteuerung ausgedrückt. Zwei Fehler, langsames Abfallen und langsames Ansteigen, sind dem Gatterausgang zugeordnet. Um den Fehler langsames Ansteigen am Ausgang eines UND-Gatters G2 zu detektieren, wird zuerst die Ausga be durch das erste Eingabemuster auf die "niedrige" Logik (logische 0) eingestellt, in diesem Fall "0, 1". Als nächs tes wird ein Versuch unternommen, die Ausgabelogik auf "hoch" zu ändern (um einen Anstieg von 0 auf 1 zu veranlas sen), zu einer gewissen Zeit (δ Einheiten) nach der Anwen dung des zweiten Eingabemusters "1, 1". Falls die Ausgabe logik sich in 1 ändert (δ Einheiten nach der Anwendung des zweiten Eingabemusters), existiert der Fehler nicht. An dernfalls wird der Verzögerungsfehler detektiert. Um den einzelnen Fehler zu testen, ist hier ein aus einem Paar Eingabemuster bestehender Teststimulus notwendig.

Um das Verdichtungsverfahren auf eine sequentielle Schaltung anzuwenden, wird eine Sequenz aus initialisieren den, sensibilisierenden und Fortpflanzungsteilsequenzen als einzelner Teststimulus betrachtet.

Auf diese Weise ist das Verdichtungsgerät der vorlie genden Ausführungsformen unter Verwendung eines Informati onsverarbeitungsgerätes (Computer) wie in Fig. 16 gezeigt konfiguriert. Das in Fig. 16 dargestellte Informationsver arbeitungsgerät umfaßt eine CPU (zentrale Verarbeitungsein heit) 51, einen Speicher 52, eine Eingabevorrichtung 53, eine Ausgabevorrichtung 54 und eine externe Speichervor richtung 55, eine Medientreibervorrichtung 56, eine Netz werkverbindungsvorrichtung 57, die durch einen Bus 58 mit einander verbunden sind.

Der Speicher 52 enthält einen ROM (Nurlesespeicher), RAM (Direktzugriffsspeicher) etc. und speichert ein Pro gramm und Daten, die im Verdichtungsprozeß verwendet wer den. Die CPU 51 führt einen notwendigen Prozeß durch Aus führen eines den Speicher 52 verwendenden Programms durch.

Die Eingabevorrichtung 53 kann z. B. eine Tastatur, eine Zeigervorrichtung, ein Berührungsfeld etc. sein und wird beim Eingeben einer Anweisung von einem Benutzer und einer Information verwendet. Die Ausgabevorrichtung 54 kann z. B. eine Anzeige, ein Drucker, ein Lautsprecher etc. sein und wird beim Ausgeben einer Anfrage an den Benutzer und eines Prozeßergebnisses verwendet.

Die externe Speichervorrichtung 55 kann z. B. eine Mag netplattenvorrichtung, eine Optikplattenvorrichtung, eine Vorrichtung für eine magnetooptische Platte, eine Bandvor richtung etc. sein. Das Informationsverarbeitungsgerät speichert das Programm und Daten in der externen Speicher vorrichtung 55 und lädt sie wie notwendig in den Speicher 52, um sie zu verwenden.

Die Medientreibervorrichtung 56 treibt ein tragbares Speichermedium 59 und greift auf die gespeicherten Inhalte zu. Das tragbare Speichermedium 59 kann ein beliebiges com puterlesbares Speichermedium wie z. B. eine Speicherkarte, eine Diskette, eine CD-ROM (Compaktdisk-Nurlesespeicher), eine optische Platte, eine magnetooptische Platte etc. sein. Der Benutzer speichert das Programm und die Daten im tragbaren Speichermedium 59 und lädt sie wie notwendig in den Speicher 52, um sie zu verwenden.

Die Netzwerkverbindungsvorrichtung 57 ist mit einem Kommunikationsnetzwerk wie z. B. einem LAN (Lokalbereichs netzwerk) etc. verbunden und wandelt Daten für die Nach richtenübertragung um. Das Informationsverarbeitungsgerät empfängt das Programm und die Daten wie notwendig über die Netzwerkverbindungsvorrichtung 57 von einer anderen Vor richtung und lädt sie in den Speicher 52, um sie zu verwen den.

Fig. 17 zeigt computerlesbare Speichermedien, die das Informationsverarbeitungsgerät mit einem Programm und Daten versehen können. Das Programm und die Daten, die im tragba ren Speichermedium 59 oder einer Datenbank 61 eines Servers 60 gespeichert sind, werden in den Speicher 52 geladen. Zu dieser Zeit erzeugt der Server 60 ein Fortpflanzungssignal zum Fortpflanzen des Programms und der Daten und überträgt das Signal über ein beliebiges Übertragungsmedium im Netz werk zum Informationsverarbeitungsgerät. Die CPU 51 führt dann das Programm unter Verwendung der Daten aus und führt einen notwendigen Prozeß durch.

Gemäß der vorliegenden Erfindung wird durch Konfigurie ren einer statischen Verdichtung von Teststimuli als Prob lem einer minimalen Überdeckung eine vom Testerzeugungsal gorithmus unabhängige Teststimuliverdichtung realisiert. Diese Verdichtung ist für Teststimuli effektiv, die durch einen beliebigen Erzeugungsalgorithmus für eine allgemeine digitale Schaltung erzeugt werden.

Claims

1. Gerät, das eine Verdichtung einer Menge von Teststi muli für eine digitale Schaltung durchführt, aufweisend:
eine Auswahlvorrichtung (D1), die wesentliche Teststi muli aus Teilmengen der Menge von Teststimuli auswählt, wo bei ein wesentlicher Teststimulus ein Teststimulus ist, der zumindest einen Fehler detektiert, welcher durch keinen an deren Teststimulus in einer der Teilmengen von Teststimuli detektierbar ist;
eine Eliminierungsvorrichtung (D2), die redundante Teststimuli aus Teilmengen von Teststimuli nach Auswahl we sentlicher Teststimuli aus jeder Teilmenge eliminiert; und
eine Ausgabevorrichtung (D3), die eine verdichtete Men ge mit den ausgewählten wesentlichen Teststimuli ausgibt.

2. Gerät nach Anspruch 1, worin die Ausgabevorrichtung eine Teilmenge minimaler Größe der Menge von Teststimuli, welche Fehler überdeckt, die durch die Menge von Teststimuli detektierbar sind, ohne Teststimuli in der Teilmenge minimaler Größe zu modifizie ren, als die verdichtete Menge ausgibt.

3. Gerät nach Anspruch 1, worin die Auswahlvorrichtung die Auswahl wesentlicher Test stimuli aus Teilmengen von verbleibenden Teststimuli nach Eliminierung redundanter Teststimuli aus den Teilmengen hierarchisch wiederholt und die Ausgabevorrichtung die ver dichtete Menge mit den ausgewählten wesentlichen Teststimu li ausgibt.

4. Gerät nach Anspruch 1, worin die Eliminierungsvorrichtung eine Teilmenge von Test stimuli identifiziert, die eine gegebene Menge von Fehlern optimal überdeckt, und einen oder mehrere, von den identi fizierten Teststimuli verschiedene Teststimuli als die red undanten Teststimuli eliminiert.

5. Gerät nach Anspruch 1, ferner aufweisend
eine Speichervorrichtung (52), die eine Information der Menge von Teststimuli, eine Information von Fehlern, welche die Menge von Teststimuli überdeckt, und eine Zeiger-Infor mation speichert, die jedem Teststimulus den durch einen entsprechenden Teststimulus detektierbaren Fehlern zuord net,
worin die Auswahlvorrichtung und Eliminierungsvorrich tung durch Verweisen auf die in der Speichervorrichtung ge speicherte Information eine Auswahl bzw. Eliminierung durchführen.

6. Gerät nach Anspruch 5, ferner aufweisend
eine Simulationsvorrichtung (51 und 52), die eine Simu lation an der digitalen Schaltung mit der Menge von Test stimuli durchführt, um die Fehler zu verfolgen, welche die Menge von Teststimuli überdeckt,
worin die Speichervorrichtung eine Zählerinformation speichert, die jedem Fehler zugeordnet ist und die Zahl von Teststimuli angibt, durch die ein entsprechender Fehler de tektierbar ist, die Simulationsvorrichtung die Zählerinfor mation inkrementiert, wenn der entsprechende Fehler während der Simulation verfolgt wird und die Auswahlvorrichtung ei nen Teststimulus, der einen Fehler mit einer Zählerinforma tion von Eins überdeckt, als einen wesentlichen Teststimu lus auswählt.

7. Gerät nach Anspruch 1, worin das Gerät eine Verdichtung der Menge von Teststimuli durchführt, durch die Fehler eines Modells mit behaftetem Fehler detektierbar sind.

8. Gerät nach Anspruch 1, worin das Gerät eine Verdichtung der Menge von Teststimuli durchführt, durch die Fehler eines Verzögerungsfehlermo dells detektierbar sind.

9. Gerät nach Anspruch 1, worin das Gerät eine Verdichtung der Menge von Teststimuli durchführt, indem eine Sequenz von initialisierenden, sen sibilisierenden und Fortpflanzungsteilsequenzen als ein einzelner Teststimulus betrachtet wird.

10. Computerlesbares Aufzeichnungsmedium (52, 55, 59 und 61), das ein Programm für einen Computer speichert, der eine Verdichtung einer Menge von Teststimuli für eine digi tale Schaltung durchführt, welches Programm den Computer veranlaßt durchzuführen:
Auswählen wesentlicher Teststimuli aus Teilmengen der Menge von Teststimuli, wobei ein wesentlicher Teststimulus ein Teststimulus ist, der zumindest einen Fehler detek tiert, der durch keinen anderen Teststimulus in einer der Teilmengen von Teststimuli detektierbar ist;
Eliminieren redundanter Teststimuli aus Teilmengen von Teststimuli nach Auswahl wesentlicher Teststimuli aus jeder Teilmenge; und
Ausgeben einer verdichteten Menge mit den ausgewählten wesentlichen Teststimuli.

11. Fortpflanzungssignal, das ein Programm zu einem Computer fortpflanzt, der eine Verdichtung einer Menge von Teststimuli für eine digitale Schaltung durchführt, welches Programm den Computer veranlaßt durchzuführen:
Auswählen wesentlicher Teststimuli aus Teilmengen der Menge von Teststimuli, wobei ein wesentlicher Teststimulus ein Teststimulus ist, der zumindest einen Fehler detek tiert, der durch keinen anderen Teststimulus in einer der Teilmengen von Teststimuli detektierbar ist;
Eliminieren redundanter Teststimuli aus Teilmengen von Teststimuli nach Auswahl wesentlicher Teststimuli aus jeder Teilmenge; und
Ausgeben einer verdichteten Menge mit den ausgewählten wesentlichen Teststimuli.

12. Verfahren zum Verdichten einer Menge von Teststimu li für eine digitale Schaltung, umfassend:
Auswählen wesentlicher Teststimuli aus Teilmengen der Menge von Teststimuli, wobei ein wesentlicher Teststimulus ein Teststimulus ist, der zumindest einen Fehler detek tiert, der durch keinen anderen Teststimulus in einer der Teilmengen von Teststimuli detektierbar ist;
Eliminieren redundanter Teststimuli aus Teilmengen von Teststimuli nach Auswahl wesentlicher Teststimuli aus jeder Teilmenge; und
Ausgeben einer verdichteten Menge mit den ausgewählten wesentlichen Teststimuli.

13. Gerät, das eine Verdichtung einer Menge von Test stimuli für eine digitale Schaltung durchführt, aufweisend:
Auswahlmittel (D1) zum Auswählen wesentlicher Teststi muli aus Teilmengen der Menge von Teststimuli, wobei ein wesentliche Teststimulus ein Teststimulus ist, der zumin dest einen Fehler detektiert, der durch keinen anderen Teststimulus in einer der Teilmengen von Teststimuli detek tierbar ist;
Eliminierungsmittel (D2) zum Eliminieren redundanter Teststimuli aus Teilmengen von Teststimuli nach Auswahl we sentlicher Teststimuli aus jeder Teilmenge; und
Ausgabemittel (D3) zum Ausgeben einer verdichteten Men ge mit den ausgewählten wesentlichen Teststimuli.