Spectral and information theoretic method of test point, partial-scan, and full-scan flip-flop insertion to improve integrated circuit testability

Abstract

Design for testability (DFT) algorithms, which use both gradient descent and linear programming (LP) algorithms to insert test points (TPs) and/or scanned flip-flops (SFFs) into large circuits to make them testable are described. Scanning of either all flip-flops or a subset of flip-flops is supported. The algorithms measure testability using probabilities computed from logic simulation, Shannon's entropy measure (from information theory), and spectral analysis of the circuit in the frequency domain. The DFT hardware inserter methods uses toggling rates of the flip-flops (analyzed using digital signal processing (DSP) methods) and Shannon entropy measures of flip-flops to select flip-flops for scan. The optimal insertion of the DFT hardware reduces the amount of DFT hardware, since the gradient descent and linear program optimizations trade off inserting a TP versus inserting an SFF. The linear programs find the optimal solution to the optimization, and the entropy measures are used to maximize information flow through the circuit-under-test (CUT). The methods limit the amount of additional circuit hardware for test points and scan flip-flops.