Classification of Sequential Circuits Based on τk Notation and Its Applications

Chia Yee OOI  Thomas CLOUQUEUR  Hideo FUJIWARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.12   pp.2738-2747
Publication Date: 2005/12/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.12.2738
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: VLSI Systems
test generation,  easily testable sequential circuits,  complexity,  design for testability,  synthesis for testability,  

Full Text: PDF(391.4KB)>>
Buy this Article

This paper introduces τk notation to be used to assess test generation complexity of classes of sequential circuits. Using τk notation, we reconsider and restate the time complexity of test generation for existing classes of acyclic sequential circuits. We also introduce a new DFT method called feedback shift register (FSR) scan design technique, which is extended from the scan design technique. Therefore, for a given sequential circuit, the corresponding FSR scan designed circuit has always equal or lower area overhead and test application time than the corresponding scan designed circuit. Furthermore, we identify some new classes of sequential circuits that contain some cyclic sequential circuits, which are τ-equivalent and τ2-bounded. These classes are the l-length-bounded testable circuits, l-length-bounded validity-identifiable circuits, t-time-bounded testable circuits and t-time-bounded validity-identifiable circuits. In addition, we provide two examples of circuits belonging to these classes, namely counter-cycle finite state machine realizations and state-shiftable finite state machine realizations. Instead of using a DFT method, a given sequential circuit described at the finite state machine (FSM) level can be synthesized using another test methodology called synthesis for testability (SFT) into a circuit that belongs to one of the easily testable classes of cyclic sequential circuits.