To synthesize hazard-free asynchronous circuits from Signal Transition Graphs (STGs), we present a new Characteristic Graph (CG) to encapsulate all feasible solutions of the original STG in reduced size, which compares favorably with the state graph approach. Based on CG, we are able to explore the design space, as well as develop a necessary and sufficient condition for hazard-free realization on a predefined general circuit model, which has not yet been reported. The exact optimization for synthesis is shown to be NP hard. A heuristic method is thus proposed which results in efficient solutions while requiring very little CPU time.

Fault simulation is essential to design a high fault-coverage BIST. The simulation is characterized by combinational fault simulation and signature computation with a large amount of test patterns. In this paper, a fast fault simulator BISTSIM for BIST is developed. For the combinational fault simulation, a novel demand-driven logic simulation algorithm is proposed. Moreover, efficient fault propagation methods are incorporated into BISTSIM. The experimental results show that the proposed fault simulator delivers better performance than FSIM; about 2 to 3 times for circuits with a large number of test patterns. For signature evaluation of MISR to determine the aliasing, two efficient simulation methods, bit-array computation and parallel-pattern sequential simulation, are proposed. The resultant BISTSIM outperforms the fast fault simulator HOPE1.1 with an average speedup ratio of 10.

Test set compaction for combinational circuits is studied in this paper. Two active compaction methods based on essential faults are developed to reduce a given test set. The special feature is that the given test set will be adaptively renewed to increase the chance of compaction. In the first method, forced pair-merging, pairs of patterns are merged by modifying their incompatible specified bits without sacrificing the original fault coverage. The other method, essential fault pruning, achieves further compaction from removal of a pattern by modifying other patterns of the test set to detect the essential faults of the target pattern. With these two developed methods, the compacted test size on the ISCAS'85 benchmark circuits is smaller than that of COMPACTEST by more than 20%, and 12% smaller than that by ROTCO+COMPACTEST.>

In this paper, a novel test clock reduction method is proposed to generate a compact test scheme for scan-designed sequential circuits. The method comprises of two phases. First, from a given compact combinational test set, sequential fault propagation is performed after each scan-in operation to propagate the activated faults and simultaneously detect other undetected faults as many as possible. In the second phase, two active overlapping techniques are developed to maximize the overlap between successive scan-in patterns in pure scan mode. The experimental results show that the number of test clocks are reduced to half of full-scan. Furthermore, in comparison with the mix-mode test generator, TARF (1992) requires 54% more test clocks than ours.

Theoretical foundations and a verification procedure based on the transitive lock relation are developed to solve the state coding problem wholly on the signal transition graph (STG) domain for STGs containing multicycle signals and conditional behaviors. The problem considered is realizable state coding, which is a more relaxed requirement than unique state coding. For STGs with multicycle signals, single-cycle transformation is proposed to transform the problem into one with single-cycle signals. For STGs with conditional behaviors, two operations, branch reversing and self-loop unfolding, are proposed to significantly simplify the verification process. The proposed algorithmic approaches have been shown to be successful on over 30 examples from academia and industry.>

The behavior of ordered binary decision diagrams (OBDD) for general Boolean functions is studied. A tight upper bound of (2/sup n//n)(2+ epsilon ) for the worst case OBDD size is derived. Although the size of an OBDD is dependent on the ordering of decision variables, it is shown that almost all functions are not sensitive to variable ordering.>

Article Free Access Share on Automatic synthesis of asynchronous circuits Authors: Kuan-Jen Lin Department of Electrical Engineering, National Taiwan University Department of Electrical Engineering, National Taiwan UniversityView Profile , Chen-Shang Lin View Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 296–301https://doi.org/10.1145/127601.127684Published:01 June 1991Publication History 27citation300DownloadsMetricsTotal Citations27Total Downloads300Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of automatic diagnosis of digital circuits with efficiency is studied. Two improvements over the method of J.C. Madre et al. (1989) are developed to enhance the efficiency of diagnosis. Specifically, the dominance relation in circuit topology is utilized to reduce the search space of possibly correctable gates. In the authors' experiment, the search space is reduced to about one-half. A novel divide-and-conquer technique to determine the correct gate function is proposed.>

In this paper, an interactive verification and diagnosis system for VHDL [Vm88], VVDS, is presented. In VVDS, hybrid simulation, which simulates with both numerical and symbolic data, is implemented to achieve an effective compromise of the enormous quantity of input test data in the conventional simulation and the complexity of symbolic expression in the symbolic execution. To support efficient user interface in the verification and diagnosis process, both on-line programming of commands and micro-probing capability to passively and actively probe any level of design hierarchy are provided.