Classification of sequential circuits based on combinational test generation complexity
Chia Yee Ooi, Hideo Fujiwara · NAIST Digital Library (Nara Institute of Science and Technology) · 2004
Several classes of sequential circuits with combinational test generation complexity have been introduced. However, no general notation is used to define the time complexity of test generation. In this paper, we introduce a new test generation notation that we call τk notation in order to present and clarify the classification of sequential circuits based on the combinational test generation complexity. For a class of sequential circuits, the time complexity of test generation is τk-bounded if it is O(τk(n)) and τk-equivalent if it is Θ(τ k(n)), where τ(n) is the combinational test generation complexity and n is the size of the circuits. Based on τk notation, we reconsider the time complexity of test generation for the existing classes of acyclic sequential circuits including balanced sequential circuits, strongly balanced sequential circuits, and internally balanced sequential circuits. In this paper, we also introduce a new method of design for testability called feedback shift register scan design (FSR scan design) technique, which is extended from the scan design technique. We discuss the time complexity of test generation for the scan designed circuits and the FSR scan designed circuits. We also introduce three classes of sequential circuits, which are τ-equivalent and τ2-bounded. The k-length-bounded testable circuits is identified as a class of sequential circuits with τ2-bounded time complexity if the parameter k is O(n) while k-time-bounded testable circuits and k-time-bounded validity-identifiable circuits are identified as classes with τ-equivalent (τ2-bounded) time complexity if the parameter k is τ(n) (τ2(n)).