Boolean reasoning for digital circuits in presence of unknown values : application to test automation

Abstract

The exponential growth in digital VLSI design scale and complexity has been enabled by comprehensive adoption of design automation tools. In the digital domain, design automation from design entry over synthesis, validation, verification to test preparation is based on reasoning about logic functions and their manipulation.

Limited knowledge about the circuit behavior may require that nodes in the circuit are modeled as having an unknown value, for instance when using incompletely specified design models. Circuit nodes also need to be modeled as unknown if their values cannot be controlled during operation or test, or if their value during operation is not known at the time of modeling.

To reflect such unknown values in design automation tools, the algorithms typically employ logic algebras with a special symbol ’X’ denoting the unknown value. However, the reasoning about functions based on such algebras results in an overestimation of unknown values in the model, and an accurate or optimal solution cannot be found. This pessimism in presence of unknown values causes additional costs at different stages of the design and test process and may even reduce product quality.

This work proposes novel, efficient approximate and accurate algorithms for the analysis of the behavior of digital circuits in presence of unknown values. Heuristics and formal Boolean reasoning techniques are combined to achieve short runtimes. The algorithms allow accurate logic and fault simulation as well as accurate automatic test pattern generation in presence of unknown values. The implications to the overhead and effectiveness of design-for-test structures are studied. The proposed algorithms are the first to completely overcome the pessimism of conventional algorithms found in today’s VLSI design automation tools also for larger circuits.

Experiments on benchmark and industrial circuits investigate the pessimism in conventional algorithms and show the increased accuracy achieved by the proposed algorithms. The results demonstrate the benefits of approximate and accurate reasoning in different applications in the VLSI design process, especially in the test automation domain.

Das exponentielle Wachstum der Entwurfskomplexität integrierter Schaltungen wird durch die durchgängige Verwendung von Werkzeugen zur Entwurfsautomatisierung ermöglicht. Für digitale Schaltungsanteile basiert die Entwurfsautomatisierung von der Eingabe über die Synthese, Validierung, Verifikation bis hin zur Testvorbereitung auf der Analyse und Manipulation von Logikfunktionen.

Ist das Schaltungsverhalten nur partiell bekannt, zum Beispiel bei Verwendung unvollständig spezifizierter Modelle, kann über die Werte gewisser Signale keine Aussage getroffen werden. Dies erfordert, dass im Schaltungsmodell entsprechende Signale mit unbekannten Werten modelliert werden. Ebenso müssen Werte von Signalen als unbekannt modelliert werden, wenn ihr Wert während des Betriebs oder der Testdurchführung nicht gesteuert werden kann und zum Zeitpunkt der Modellierung unbekannt ist.

Um diese unbekannten Werte in Entwurfswerkzeugen zu behandeln, verwenden die Algorithmen typischerweise Algebren, die unbekannte Werte mit einem gesonderten Symbol ’X’ darstellen. Allerdings führt die Auswertung und Analyse von Funktionen mit solchen Algebren zu einer Überschätzung von Signalen mit unbekannten Werten im Modell, so dass die exakte oder optimale Lösung im Anwendungsbereich nicht gefunden werden kann. Dieser Pessimismus bei Betrachtung von unbekannten Werten verursacht zusätzliche Kosten während des Entwurfs und des Testprozesses. Im schlimmsten Fall kann sogar die Produktqualität darunter leiden.

In der vorliegenden Arbeit werden effiziente approximative und exakte Algorithmen für die Analyse des Verhaltens digitaler Schaltungen in Gegenwart von unbekannten Werten vorgestellt. Diese Algorithmen verbinden Heuristiken und unterschiedliche formale Analysetechniken, um niedrige Laufzeiten zu erreichen. Die entwickelten Algorithmen erlauben die exakte Logik- und Fehlersimulation, als auch die exakte Testmustererzeugung in Gegenwart von unbekannten Werten. Weiterhin werden die Folgen für den prüfgerechten Entwurf untersucht. Die vorgeschlagenen Algorithmen erlauben erstmals, den Pessimismus in vorherrschenden Algorithmen der Entwurfsautomatisierung vollständig auch für größere Schaltungen zu beseitigen.

Mittels Experimenten anhand von Benchmark- und industriellen Schaltungen wird der Pessimismus in aktuellen Algorithmen untersucht. Die Ergebnisse belegen die Vorteile einer exakten Schaltungsanalyse während des Entwurfs und insbesondere im Bereich der Testautomatisierung.