It is known that wavepipelined circuits offer high performance, because their maximum clock frequencies are limited only by the path delay differences of the circuits, as opposed to the longest path delays. For proper operation, precision in clock frequency is essential. Using a new representation, Timed Boolean Functions, we derive analytical expressions for valid clocking intervals in terms of topological, 2-vector, and single vector delays, both the longest and the shortest. These intervals take into account both circuit functionality and timing characteristics, thus eliminating the pessimism caused by long and short false paths, and include effects of circuit parameters such as delay variations, clock skews, and setup and hold times of flip flops. In addition, we show that these intervals subsume Cotten's lower bound on valid clock period. Further, we study the problem of computing all enact valid clocking intervals and its computational complexity by demonstrating discontinuity and nonmonotonicity of the harmonic number H(/spl tau/) (the number of valid simultaneous data waves allowed) as a function of the clock period /spl tau/. Finally, we propose algorithms to compute the exact valid intervals for a given set of harmonic numbers and demonstrate performance enhancement of balanced circuits from ISCAS benchmarks with gate delay variations.

The main disadvantage of the path delay fault model is that to achieve 100% testability every path must be tested. Since the number of paths is usually exponential in circuit size, this implies very large test sets for most circuits. Not surprisingly, all known analysis and synthesis techniques for 100% path delay fault testability are computationally infeasible on large circuits. We prove that 100% delay fault testability is not necessary to guarantee the speed of a combinational circuit. There exist path delay faults which can never impact the circuit delay (computed using any correct timing analysis method) unless some other path delay faults also affect it. These are termed robust dependent delay faults and need not be considered in delay fault testing. Necessary and sufficient conditions under which a set of path delay faults is robust dependent are proved; this yields more accurate and increased delay fault coverage estimates than previously used. Next, assuming only the existence of robust delay fault tests for a very small set of paths, we show how the circuit speed (clock period) can be selected such that 100% robust delay fault coverage is achieved. This leads to a quantitative tradeoff between the testing effort (measured by the size of the test set) for a circuit and the verifiability of its performance. Finally, under a bounded delay model, we show that the test set size can be reduced while maintaining the delay fault coverage for the specified circuit speed. Examples and experimental results are given to show the effect of these three techniques on the amount of delay fault testing necessary to guarantee correct operation.>

In current research, the minimum cycle times of finite state machines are estimated by computing the delays of the combinational logic in the finite state machines. Even though these methods deal with false paths, they ignore the sequential and periodic nature of minimum cycle times, and hence may give pessimistic results. In this paper, we first prove conditions under which combinational delays are correct upper bounds on minimum cycle times. Then, we present a sequential approach to compute the minimum cycle times of finite state machines, taking into account the effects of gate delay variations, reachable state space, initial states, unrealizable transitions, multiple cycle false paths, and periodicity of the present state vector sequences. We formulate and solve the problem exactly using Timed Boolean Functions, and give an efficient algorithm to solve for upper bounds of minimum cycle times. The exact formulation with Timed Boolean Functions provides a framework for further improvements on existing algorithms to compute the minimum cycle times. We implemented the algorithm and obtained the tightest bounds known on ISCAS benchmarks. From the experiments, we found that for about 20 % of the circuits (not all shown in section 8), combinational delays, e.g. floating, viability, and transition delays, give pessimistic upper bounds for cycle times by as much as 25%. 1

In this paper, we introduce a new circuit delay model, delay by sequences of vectors, which captures the essence of viability and floating delays. Then, we classify delays of circuits according to both the delay models of the gates making up the circuits and the family of inputs to the circuits. In this classification, we give sufficient conditions under which floating delay is the same as delay by sequences of vectors; these sufficient conditions are true for most practical circuits. This implies that the assumption of arbitrary node values used in the floating delay model is not too conservative. Thus, delay by sequences of vectors (hence, viability and floating delays), transition delay, and cycle time delay have coherent definitions under the same framework. Next, we study the problem of computing the exact circuit delays under both bounded and unbounded gate delay models, for some of which only upper bounds are known. By using a new formulation technique, called Timed Boolean Function, we formulate the problem of computing the exact delays as a mixed Boolean linear programming problem for which we give efficient algorithms to compute the exact delays of combinational circuit for transition delay and delay by sequences of vectors. The algorithms consider a subset of paths at one time and only the paths potentially responsible for the delay of a circuit are considered. Moreover, the core computation of the algorithms are composed of two computationally efficient algorithms: linear programming and BDD manipulations. We next compute floating (or viability) delays with the bounded gate delay model and show that delays by sequences of vectors and floating (or viability) delays are invariant under both bounded and unbounded gate delay models. Finally, we address the effect of gate delay lower bounds on delays of circuits. We demonstrate the effectiveness of the method by giving exact delay results for all ISCAS benchmark circuits (except C6188)

The main disadvantage of the path delay fault model is that to achieve 100% testability every path must be tested.Since the number of paths is usually exponential in circuit size, atl known analysis and synthesis techniques for 100% path delay fault testability are infeasible on most circuits.In this paper, we show that 100'%odelay fault testability is not necessary to guarantee the speed of a combinational circuit.There exist path delay faults which can never impact the circuit delay (computed using arty correct timing analysis method) unless some other path delay faults also affect i~hence these delay faults need not be considered in delay fault testing.Next, assuming only the existence of robust delay fault tests for a very small set of paths, we show how the circuit speed can be selected such that 100% robust delay fault coverage is achieved.

An analysis of valid clock rates in wavepipelined circuits using a technique called timed Boolean functions is presented. It is shown that the valid intervals for the clock period can be disconnected. Thus, it is insufficient to known only the minimum valid clock period in guaranteeing proper operation of pipelined circuits. Analytic expressions for the valid clock intervals in terms of both topological delay and two-vector longest and shortest delays are provided. Also uncertainties arising from manufacturing are taken into account. Some potential difficulties in computing the exact valid clock intervals are illustrated by demonstrating discontinuity and nonmonotonicity of the harmonic number H( tau ) (the number of valid simultaneous data waves allowed) as a function of the clock period tau .>

Properties of the if-then-else directed-acyclic graph (ITE) and its relation to the binary decision diagram (BDD) are investigated. It is shown that, for any given variable ordering, there are fewer exponential ITEs than BDDs, and that, for any function f, the size of its canonical ITE is bounded by 4* the size of its corresponding canonical BDD, i.e. //ITE(f)//>