The core-based design style of integrated circuits (ICs) helps to manage the development challenges brought by the ever increasing complexity of integrated systems and the ever tighter time-to-market. Nevertheless, test-related problems are still far away from having a unitary and satisfactory solution, especially in the system on a chip (SOC) context. For the test of ICs two reference approaches are available: external testing and built-in selftest (BIST), out of which a variety of hybrid test strategies are obtained by test resource partitioning (TRP). The final goal is to provide advantageous tradeoffs of the test evaluation indicators like: test development and application cost, hardware overhead, fault coverage, etc. BIST offers support for in-field, on-line, burn-in and at-speed test that is indispensable for delay fault testing. Moreover, tradeoffs between fault coverage, hardware overhead and test length are possible. External testing is characterized by flexibility, reduced hardware overhead and high fault coverage for a given test length. Deterministic logic BIST (DLBIST) is an attractive test strategy, since it combines the advantages of deterministic external testing and pseudo-random logic BIST (LBIST). Unfortunately, previously proposed DLBIST methods are unsuited for large ICs, since computation time and memory consumption of the DLBIST synthesis algorithms increase exponentially, or at least cubically, with the circuit size. In this work, a novel procedure for the development of the so-called bit-flipping DLBIST scheme is proposed, which has nearly linear complexity in terms of both computation time and memory consumption. This new method is based on the use of Binary Decision Diagrams (BDDs). The efficiency of the employed algorithms is demonstrated for industrial designs containing up to 2M gates. The embedded test sequences obtained by mapping deterministic cubes to pseudo-random sequences are also evaluated with respect to the coverage of non-target defects, which are modeled with the help of resistive bridging faults. The experimental results prove that both deterministic cubes and pseudo-random sequences are useful for detecting non-target defects. Moreover, possible tradeoffs between test length, hardware overhead, fault coverage and nontarget defect coverage are analyzed. This work additionally presents the results of extending the bit-flipping DLBIST scheme such that it also supports the transition fault testing besides the stuck-at fault testing. Transition faults model defects which are responsible for the incorrect operation of the core under test (CUT) at the desired speed. The importance of these defects is continuously enhanced by the ever increasing clock rates and integration density of today s circuits. Experimental results obtained for large industrial benchmark designs are reported. No pure DLBIST approach for the test of delay faults in circuits with standard scan design has been published so far. In order to decrease the logic overhead of DLBIST, an innovative way of constructing efficient implementations for the involved Boolean functions (e.g. bit-flipping functions) is presented. A key feature of these functions is their incomplete specification which is based on large don t care sets (sets of input assignments for which it does not matter whether they are mapped to 0 or 1 ). Reduced ordered Binary Decision Diagrams (ROBDD) are used for representing and manipulating the involved functions and multi-level implementations are obtained based on the use of free BDDs (FBDD). Experimental results show that for all the considered functions, implementations are found with a significant reduction of the gate count as compared to a state-of-the-art multi-level synthesys tool (SIS [Sen92]) or to methods offered by a state-of-the-art BDD package. This performance is due to a reduction of the node count in the corresponding FBDDs and a decrease in the average number of gates needed to implement the FBDD nodes. The experimental results obtained for large industrial benchmark designs show that DLBIST may be well suited for use in special segments of IC development, like the ones dealing with security chips or hard cores., System on a Chip (SOC) sind komplexe Systeme mit Millionen von Transistoren auf einer einzelnen integrierten Schaltung (engl. integrated circuit (IC)). Solche ICs enthalten in der Regel verschiedene Komponenten und Technologien, wie beispielsweise Speicher, Prozessoren, anwendungsspezifische Logik, Hochfrequenzund Analogmodule. Um die Kosten der Entwicklung zu reduzieren, werden immer häufiger vorentworfene Funktionsblöcke verwendet (engl. core-based design). Dieser Entwurfsstil stellt eine große Herausforderung an die Testverfahren dar. Das Hauptziel eines jeden Testverfahrens ist es, einen Kompromiss zwischen den Testkosten und der Testqualität (Produktqualität) zu finden. Wichtige Kriterien für den Test von ICs sind: Testentwicklungskosten, Testapplikationskosten, zusätzlicher Bedarf an Schaltungsfläche, Fehlererfassung, etc. Zu den Anforderungen, die an die heutigen IC Testverfahren gestellt werden, gehören spezifische Anforderungen, die auf die verschiedenen Typen von Modulen abgestimmt sind. Zudem besteht zunehmender Bedarf an Verzögerungstests, in-field und on-line Tests. In den traditionellen Testverfahren werden die ICs normalerweise extern mit speziellen Testautomaten (engl. automated test equipment (ATE)) getestet. Die externen Testverfahren zeichnen sich durch hohe Flexibilität, relativ geringen zusätzlichen Bedarf an Schaltungsfläche und hohe Fehlererfassung für eine bestimmte Testlänge aus. Die zunehmende Komplexität und der wachsende Umfang der Testdaten machen die Durchführung externer Tests immer schwierig. Die Qualität der Fehlererfassung wird durch die Unzugänglichkeit der internen Blöcke verringert. Außerdem ist es sehr teuer, mit ATEs die maximal mögliche Taktfrequenz moderner ICs zu messen. Diese Probleme werden durch die hohe Komponentendichte sowie die Anwendung verschiedener Technologien in der SOC-Fertigung vergrößert, so dass Messmethoden mit externen Testautomaten ungenau, und das ATE selbst sehr teuer wird. Selbsttestverfahren (engl. built-in self-test (BIST)) sind dem oben genannten Verfahren in Bezug auf die erwähnten Problemen überlegen. Mit BIST können online, in-field, burn-in und at-speed Tests realisiert werden. In-field Tests werden für periodische Wartungen verwendet, burn-in Tests sind wichtig für die Steigerung der Produktqualität und Zuverlässigkeit und at-speed Tests sind notwendig um die Verzögerungsfehler zu finden. Außerdem sind Kompromisse zwischen der erreichten Fehlererfassung, dem zusätzlichen Bedarf an Schaltungsfläche und der Testlänge möglich. Neben den externen und den Selbsttestverfahren gibt es noch verschiedene Arten von Testverfahren, die auf test resource partitioning (TRP) basieren. Deterministic logic BIST (DLBIST) ist eine sehr attraktive Teststrategie, weil sie die Vorteile von deterministischen externen Testverfahren und pseudozufälligen logic BIST kombiniert. Die bisher vorgeschlagenen DLBIST Verfahren können nur bei kleineren Entwürfen angewendet werden, da die Laufzeit und der Speicherbedarf der Hardwaresynthese exponentiell oder wenigstens kubisch mit der Schaltungsgröße steigen. Es gibt zwei grundlegende DLBIST Verfahren: store and generate Verfahren und test set embedding Verfahren. Bei dem store and generate Verfahren werden die Testmuster in einer komprimierten Form auf dem Chip gespeichert und darauf ein Dekompressionsalgorithmus angewendet. Bekanntere Beispiele dieser DLBIST Methode basieren auf Kodierung durch rückgekoppelte Schieberegister (engl. LFSR), Multipolynom Reinitialisierung und Faltender Zähler (engl. folding counter). Bei Test set embedding Verfahren werden pseudozufallsgenerierte Muster durch deterministische Muster ergänzt. Bekannte test set embedding Verfahren sind die bitflipping und bit-fixing Verfahren. Bei diesen beiden DLBIST Verfahren werden Testmustergeneratoren eingesetzt, die eine gute Fehlererfassung ermöglichen. Die Besonderheit dieser Testmustergeneratoren ist ein Logikmodul, das eine bit-flipping Funktion (BFF), beziehungsweise bit-fixing Funktion (BFX), durchführt. Die Implementierung dieser Testmustergeneratoren umfasst zwei Schritte: (1) die Abbildung einer Reihe deterministischer Testmuster zu einer Folge von Pseudozufalltestmustern und (2) die Synthese des Logikmoduls, welches die Abbildung durchführt. In dieser Arbeit wird ein neues Verfahren für den Aufbau der bit-flipping DLBIST Hardware vorgeschlagen. Die BFF beschreibt das Einbetten von deterministischen Testmustern zu einer pseudozufälligen Testfolge, die durch einen LFSR und eventuell einen Phasenschieber (engl. phase shifter) erzeugt wird. Die Suche nach einem effizienten deterministischen Testmuster-Einbettungsverfahren mit geringem zusätzlichem Bedarf an Schaltungsfläche ist eine schwierige Aufgabe. Ein Beitrag dieser Arbeit ist eine skalierbare Lösung, sowohl für die Abbildung von deterministischen Testmustern (d.h. die Generation von BFF), als auch für die Logiksynthese der resultierenden BFF [Ghe04]. Ein ATPG Werkzeug wird verwendet, um deterministische Testmuster für alle Fehler zu erzeugen, die nicht durch die pseudozufällige Testfolge entdeckt werden. Diese deterministischen Testmuster enthalten eine große Zahl nicht spezifizierter Bits (engl. don’t care (DC) bits). Ein Pseudozufallstestmuster wird jedem dieser deterministischen Testmuster zugeteilt, so dass die Größe der resultierenden BFF minimiert wird. In Anbetracht eines deterministischen Testmusters werden nur diejenigen Pseudozufallstestmuster untersucht, die eine minimale Zahl von unpassenden (engl. conflicting) Bits enthalten. Um weiter die Abbildung von Testmustern zu optimieren, wird eine Kombination von folgenden Maßnahmen verwendet: · Minimierung der Taktzyklen, die sowohl zusammenpassende (engl. matching) als auch unpassende Bits enthalten. Dadurch wird versucht den Logikanteil, der bei der BFF Implementierungen für unterschiedliche Prüfpfade gemeinsam benutzt wird, zu maximieren. · Minimierung der Zahl von Prüfpfaden, die sowohl zusammenpassende als auch unpassende Bits pro eingebettetem Testmuster enthalten. Dies erhöht die Optimierungsmöglichkeiten für die BFF Implementierung jedes Prüfpfades. Das neue Verfahren stützt sich auf die Effizienz und die Kompaktheit der BDD-basierten Funktionsdarstellung und hat eine beinahe lineare Komplexität in Bezug auf Laufzeit und Speicherbedarf. Die Effizienz des neuen Verfahrens wird für industrielle Schaltungen bis zu einer Größe von 2 Millionen Gattern nachgewiesen. Mit der neuen Einbettungsmethode sind Verbesserungen mehrerer Größenordnungen, verglichen mit den vorherigen Verfahren sowohl in Bezug auf den Laufzeitbedarf, als auch in Bezug auf den Speicherbedarf, erreichbar. Die neue DLBIST Hardware-Synthese hat jetzt denselben Laufzeit- und Speicherverbrauch wie die anderen benötigten Verfahrensschritte, ATPG und Fehlersimulation. Die Laufzeitverbesserungen können auch dazu verwendet werden, um noch bessere Lösungen in Bezug auf den zusätzlichen Bedarf an Schaltungsfläche und Fehlererfassung zu erhalten. Ein anderer Beitrag dieser Arbeit ist eine Studie zur Wirksamkeit des bit-flipping DLBIST im Test von nicht modellierten Defekten [Eng05]. Die widerstandsbehafteten Brückenfehler (engl. resistive bridging faults) wurden verwendet, um nicht modellierte Defekte zu simulieren. Experimentelle Ergebnisse zeigen, dass sowohl deterministische als auch pseudozufällige Testmuster nützlich sind, um nicht modellierte Defekte zu testen. Außerdem werden mögliche Kompromisse zwischen der Testlänge, zusätzlichem Bedarf an Schaltungsfläche, Fehlererfassung und Erfassung der nicht modellierten Defekte analysiert. Es zeigt sich, dass durch die Erhöhung der Anzahl von Testmustern die Defekterfassung erhöht und der zusätzliche Bedarf an Schaltungsfläche bedeutend reduziert wird. Das vergrößert die Attraktivität der vorgeschlagenen DLBIST Architektur und reduziert den Bedarf an teuren ATEs. Diese Arbeit enthält auch eine Erweiterung der entwickelten bit-flipping DLBIST Architektur, so dass neben Haftfehlern auch Übergangsfehler testbar werden. Die Übergangsfehler (engl. transition faults) sind eine Art von Verzögerungsfehler und modellieren Defekte, die für eine nicht funktioniernde Schaltung bei der verwendeten Taktfrequenz verantwortlich sind. Die Bedeutung dieser Defekte wird durch die jeweils zunehmende Taktrate und Integrationsdichte heutiger Schaltungen ständig erhöht. Es ist bis jetzt kein DLBIST Verfahren für die Prüfung der Übergangsfehler veröffentlicht worden. Die Besonderheit der Tests von Übergangs- und allgemeinen Verzögerungsfehlern besteht in der Notwendigkeit, Paare von Testmustern und nicht einzelne Testmuster, wie im Falle von Haftfehlern, anzuwenden. Es wird in diesem Verfahren das erste Testmuster jedes Paares genau wie im Fall von Haftfehler-Test erzeugt, und die Schaltungsantwort auf das erste Testmuster wird als zweites Testmuster verwendet (engl. functional justification). Da bei diesem Test Testmusterpaare verlangt werden, ist die zufällige Fehlererfassung bedeutend kleiner als für Haftfehler. Um das Einbetten von Testmustern effizienter zu machen, wird ein spezielles Modul, correction logic (CRL) genannt, eingeführt. Das CRL-Modul wird genau wie das BFF-Modul synthetisiert. Die Ausgangssignale des CRL-Moduls müssen während der scan-Taktzyklen, entsprechend jedem Testmuster, unverändert bleiben. Da sich einige der Eingangssignale während der scan-Taktzyklen ändern, werden die Ausgangssignale des CRL-Moduls in einem Flipflop gespeichert. Dieses Flipflop kann nur dann beschrieben werden, wenn ein neues Testmuster in den Prüfpfad gescannt wird. Das Flipflop wird durch das scan enable- Signal gesteuert, das benutzt wird, um die scan-Flipflops zwischen scan mode und functional mode zu schalten. Um die Größe des CRL und BFF zu beschränken, werden die deterministischen Testmuster am Ende der pseudozufälligen Testfolge eingebettet. Die Länge der pseudozufälligen Testfolge, die modifiziert werden kann, ist ein Bruchteil der ganzen Testlänge. Um die Bits in der pseudozufälligen Testfolge davor zu bewahren, gekippt (engl. flipped) zu werden, werden die Ausgangssignale des BFF mit der Hilfe eines UND-Gatters pro Prüfpfad auf Null gesetzt. Die geringere pseudozufällige Testbarkeit von Übergangsfehlern relativ zu den Haftfehlern verlangt bedeutend längere Testmusterfolgen. Diese eignen sich sowohl zum Begrenzen des zusätzlichen Bedarfs an Schaltungsfläche als auch für eine verbesserte Erfassung von modellierten und nicht modellierten Defekten. Experimentelle Ergebnisse für große Industrieschaltungen zeigen mögliche Kompromisse zwischen der Testlänge, zusätzlichem Bedarf an Schaltungsfläche und Fehlererfassung auf. Ein weiterer Beitrag dieser Arbeit ist ein Logikoptimierungswerkzeug, das verwendet wird, um die Implementierung des BFF zu verbessern. Dieses Logikoptimierungswerkzeug ist besonders zur Implementierung von unregelmäßigen und unvollständig spezifizierten Booleschen Funktionen geeignet. In diesem Fall bedeutet die Unregelmäßigkeit einer Booleschen Funktion, dass ihre Eingaben, deren Abbild ‘1’ ist, zufällig über dem Definitionsraum verteilt sind. Unvollständige Spezifizierung beruht auf Inputs, für die es gleichgültig ist, ob sie auf ‘0’ oder ‘1’ abgebildet werden. Beispiele für diese Art von Funktionen sind: BFF, BFX und die so genannte X-Maskierungsfunktion (XMF). Alle diese Beispiel-funktionen werden in verschiedenen test set embedding Verfahren verwendet. Für solche Funktionen werden effiziente mehrstufige Logikimplementierungen erzeugt. Diese Logikimplementierungen können sehr gut mit Hilfe ungeordneter BDDs (FBDDs) modelliert werden. Das Problem wird auf die Synthese eines minimalen FBDD reduziert. Dies wird durch den Ansatz zweier verschiedener Methoden erreicht: (a) auf DC-basierte Knotenzahlreduzierung und (b) Verteilung des Definitionsraumes der Zielfunktion in eine reduzierte Zahl von Subräumen, die entweder zu ‘0’ oder zu ‘1’ abgebildet werden können. Heuristiken werden verwendet, um fast optimale Teilungen des Definitionsraums in solchen Subräumen zu finden und folglich die Anzahl der Knoten und Pfade der resultierenden FBDD-artigen Implementierungen zu minimieren. Außerdem ist diese Näherung auch im Stande, unter Anwendung des DC-Raumes, die Gatteranzahl zu reduzieren, die in der Implementierung jeder Knotenfunktion erscheint. Verglichen mit den im CUDD-Paket enthaltenen Methoden (restrict-Operator und Umstellung von BDD Variablen), liefert das FBDD-basierte Verfahren Logikimplementierungen, deren Schaltungsbeschreibungen ungefähr 70% weniger Logikoperatoren benötigen. Diese Schaltungsbeschreibungen, erzeugt mit beiden Verfahren, wurden mit dem Synopsys Design Compiler synthetisiert. Infolgedessen konnte man erkennen, dass das FBDD-basierte Verfahren den zusätzlichen Bedarf an Schaltungsfläche um einen Faktor zwischen zwei bis drei verbessert und die Laufzeit bedeutend reduziert wird. Des Weiteren kann beobachtet werden, dass das vorgeschlagene Verfahren besser skaliert und einen größeren Nutzen aus der DC-Menge zieht als das bekannteste mehrstufige Synthesewerkzeug SIS. Insgesamt zeigen die experimentellen Ergebnisse für große industrielle Schaltungen, dass das bit-flipping DLBIST Verfahren für verschiedene Segmente der IC Tests verwendet werden kann, z.B. für die jenigen die sich mit Sicherheitschips (z.B. Smart-Cards) oder mit Hardcores befassen. Am Ende dieser Arbeit werden einige Ideen vorgeschlagen, um die hier präsentierte Forschung fortzusetzen.