Publication
Synthesis for Testability: Polynomial Test Pattern Generation for KFDD Circuits
Martha Schnieber; Rolf Drechsler
In: 28th Euromicro Conference Series on Digital System Design (DSD). Euromicro Conference on Digital System Design (DSD-2025), September 10-12, Salerno, Italy, 2025.
Abstract
Today, circuits are used in various safety-critical
systems, therefore yielding a high demand for reliable systems.
Consequently, a lot of research is conducted to improve the
testability of designs by increasing the test coverage or reducing
the required test time. In this context, provable computational
bounds are crucial to ensure fast test pattern generation. Previous
works proved polynomial test set generation for Binary Decision
Diagram (BDD) circuits. Later, the testability of Kronecker
Functional Decision Diagrams (KFDDs) was assessed, as KFDDs
can exponentially reduce the required logic. However, the test
set generation for KFDD circuits generally requires exponential
resources. In this paper, we present a technique to derive circuits
from KFDDs, for which a complete test set under the Cellular
Fault Model (CFM), as well as the Stuck-At Fault Model (SAFM),
can be generated within polynomial resources. The derived circuit
is linear in size regarding the KFDD size, and in contrast to
previously derived KFDD circuits, no redundant faults can occur,
yielding fully testable circuits under CFM and SAFM. In our
evaluation, the complete test set generation was up to 50 times
faster than the previous exponential method, clearly showcasing
the advantages of our polynomial approach.