Browsing by Author "Kochte, Michael Andreas"

Now showing 1 - 1 of 1

Open Access
Boolean reasoning for digital circuits in presence of unknown values : application to test automation
(2014) Kochte, Michael Andreas; Wunderlich, Hans-Joachim (Dr. rer. nat. habil.)
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.