Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Sequential logic testing and verification
Ghosh A., Devadas S., Newton A., Kluwer Academic Publishers, Norwell, MA, 1992. Type: Book (9780792391883)
Date Reviewed: Jul 1 1994

Quite a few good texts about combinatorial logic testing are available. Similarly, a number of existing techniques and tools can efficiently synthesize and generate tests for such circuits. Testing sequential circuits and synthesis of these circuits for testability (other than using scan-based techniques, which have an associated area or performance penalty) are much more difficult. Furthermore, it is rare for a book to attempt to cover the formal verification of sequential circuits. Most of today’s methods are still found only in research lab prototype tools and Ph.D. dissertations, not in industrial CAD software or undergraduate project work.

Unfortunately, this book does not improve this situation radically. Both its size and its content show that it is a research monograph. It is fairly systematic, however, and has a good chance to become a text when most of the ample references to recent and prominent papers are replaced by a reasonable amount of material outlining the best approaches and algorithms available in this area. The trouble, however, as is common in disciplines that rely heavily on optimization, is that it is extremely hard to identify which techniques would be most suitable, as most of the problems are computationally hard and require flexible heuristics.

The book, with its obvious orientation toward the needs of the advanced reader, provides an insightful treatment of recent progress in test generation and verification methods for synchronous, sequential logic circuits. At the same time, it provides some introductory material on the relevant terminology. The authors define synthesis for testability, design verification, implementation verification, logic verification, and so on. They introduce sequential test generation (the crucial points being “excitation state,” “state justification,” and “state differentiation”) and test generation approaches (random and deterministic approaches, iterative array-based approaches, and forward and reverse time processing). Finite state machine graph traversal and enumeration techniques are presented. The book also presents binary decision diagrams and traversal techniques based on recursive range computation and transition relations.

In each of these domains, however, readers without a good background would hardly be able to understand the details without referring to a more substantial text. To this end, the book is at least helpful as a pointer to the right source. The examples of circuits, their state transition graphs, and the application of the algorithms for them often help to build some intuition, but this is far from being a sense of confidence. (The abbreviation STG, which is used throughout the book for these graphs, seems like a poor choice, since “STG” has traditionally been used to refer to signal transition graphs, a class of interpreted Petri nets.) For instance, on page 21, some terms are used that are not formally defined, such as concatenation of state graphs, product state graph, and exclusive-or of two state graphs. Similarly, on page 26, the authors do not clearly explain why the machine shown in Figure 2.6 has an initialization problem.

A different example of obscurity is on page 107, where a few techniques are recommended equally, mixed with references to other sources, without any discussion of their advantages and disadvantages. With the obvious similarity of the proposed test generation methods used at the logic level and the register transfer level, it is a bit confusing to see the duplication of definitions of such terms as gate fan-in, fan-out, and transitive fan-out in Section 3.1. A similar thing happens in Section 4.1, where concepts such as valid and invalid states, differentiating sequence, and redundant faults are defined for the second time.

Overall, despite these complaints, I found the book quite enjoyable. It is certainly worth spending a week or so for anyone intending to do research in logic synthesis, testing, and formal verification.

Reviewer:  A. Yakovlev Review #: CR116313
Bookmark and Share
 
Reliability And Testing (B.6.2 )
 
 
Computer-Aided Design (CAD) (J.6 ... )
 
 
Verification (B.6.3 ... )
 
 
VLSI (Very Large Scale Integration) (B.7.1 ... )
 
 
Design Styles (B.6.1 )
 
 
Reliability And Testing (B.5.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Reliability And Testing": Date
Fault tolerant and fault testable hardware design
Lala P. (ed), Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780133082487)
Nov 1 1985
Hardware fault tolerance
Carter W., John Wiley & Sons, Inc., New York, NY, 1986. Type: Book (9789780471845188)
Feb 1 1989
On Computing Signal Probability and Detection Probability of Stuck-At Faults
Chakravarty S., Hunt H. IEEE Transactions on Computers 39(11): 1369-1377, 1990. Type: Article
Jun 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy