Completeness of a simple heuristic

A project log for Libre Gates

A Libre VHDL framework for the static and dynamic analysis of mapped, gate-level circuits for FPGA and ASIC. Design For Test or nothing !

Yann Guidon / YGDESYann Guidon / YGDES 11/16/2020 at 04:380 Comments

The archive contains several tests, including some exhaustive fault injection scans. The scan algorithm ignores all the gates with fewer than 4 inputs because

Let's consider a gate BUF ( input A, output B) with LUT2(0,1):

So as long as the A input is toggled, the Y output will change (or not if there is a fault). This change is propagated by

In conclusion, only gates with 2 or more inputs need a "LUT bit flips" to check the circuit.

This is a stark contrast with verification methods from the 60's where logic was wired (often manually) and the connexions themselves were delicate. Any fault needed to be identified, located and fixed, so the automated systems focused on the observability of each wire, sometimes forcing the addition of extra "observability wires" to circuits.

This old method has been carried over to IC design but the needs have changed: we only need to know if a circuit works correctly, we don't care much about why or where is fails (except for batch reliability analysis) so there is no need to focus on the wires.

However, some inference algorithms are shared because we still have to determine 2 things:

This is where things will be difficult.