The paper proposes a combined delay model to manipulate the variance of the delay time of logic elements and a new timing verification method based on the theory of regular expressions. With the delay time of logic elements such as TTL SN7400, the minimum delay time (dm), the maximum delay time (dM), and the typical delay time are specified in the manual, and the delay time of an element is one in the interval between dm and dM. Here we assume a discrete time, and we manipulate the variance of the delay time as a set of output strings corresponding to each delay time. We call the model as the combined delay model. Since many output strings are generated with a single input string, the usual timing simulation method cannot be applied. We propose a timing verification method using a behavior extraction method of logic circuits with respect to a time string set: with respect to the specified input set, the method extracts the output string set of each element in the circuit. We devised (1) a mechanism to keep the correspondence between a primary input string and an output string with respect to the primary input string, (2) a mechanism to manipulate the nondeterminism included in the combined delay model, and (3) an event-driven like data compaction method in representing finite automata. We focused on the hazard detection problem and the verification of asynchronous circuits, and show the effectiveness of our method with medium sized circuit with 100 elements or so. The method includes the state explosion, but the data compaction method and the extraction for only the specified input set are useful to control the state explosion.

Data of system parameters of real systems have some uncertainty and they should be given by sets (or intervals) rather than fixed values. To analyze and design systems contaning such uncertain parameters, it is required to represent and treat uncertainty in data of parameters, and to compute value sets of characteristic polynomials and transfer functions. Interval arithmetic is one of the most powerful tools to perform such subjects. In this paper, Polygon Interval Arithmetic (PIA) on the set of polygons in the complex plane is considered, and the data structure and algorithms to execute PIA efficiently is proposed. Moreover, practical examples are shown to demonstrate how PIA is useful to compute the evaluation of value sets.

The paper describes a parallel algorithm for the manipulation of binary decision diagrams on a shared memory multi-processor system. Binary decision diagrams are very efficient representations of logic functions, and are widely used in computer aided design of logic circuits. Logic operations on logic functions such as AND and OR are reduced to operations on binary decision diagrams representing these functions. Operations on binary decision diagrams are time-consuming in some cases, and a fast manipulation method is needed. As with the manipulation, we focus on the construction of a binary decision diagram from a logic formula, and devised a parallel algorithm for the construction. In the construction, there are many logic operations to be processed, and some of them can be processed in parallel. At first, we introduce an extraction method and a parallel-execution method for such parallelizable operations. This is the parallel execution method for an operation sequence (or a set of operations). To extract more parallelism, we introduce a dynamic expansion method of a logic operation. The dynamic expansion is a method to obtain sub-operations from a logic operation using the modified Shannon's expansion. These sub-operations are executed in parallel and the results of these sub-operations are merged to obtain the result of the original operation. Our parallel algorithm, which is based on the construction of shared binary decision diagrams with the negative edge and the operation cache, is implemented in C on a shared memory multi-processor system Sequent S-81 (CPU 80386 (16 MHz)28, 86.75MB), and applied to multiplier examples and ISCAS benchmarks. The speed-up ratio becomes 14 for multipliers, and becomes 11 for c1908 in ISCAS benchmarks.

The discrete time analysis of logic circuits is usually more efficient than the continuous time analysis, but the preciseness of the discrete time analysis is not guaranteed. The paper shows a method to decide a unit time for a logic circuit under which the analysis result is the same as the result based on the continuous time. The delay time of an element is specified with an interval between the minimum and maximum delay times, and we assume an analysis method which enumerates all possible delay cases under the deisrete time. Our main theorem is as follows: refine the unit time by a factor of 1/2, and if the analysis result with a unit time u and that with a unit time u/2 are the same, then u is the expected unit time.

This paper discuses the simulation of logic circuits with feedback loops for a set of input strings. Logic circuits are modeled as Mealy machines which convert an input string set to an output string set. By the simulation, we obtain a set of output strings which shows the input-output relation of the simulated circuit. The behavior of feedback loops of a logic circuit is shown to be the least-fixed-point on a lattice of string sets. The characteristics of a lattice we have used is also shown in the paper.