Integer addition is one of the most important operations in digital computer systems because the performance of processors is significantly influenced by the speed of their adders. This paper proposes a self-timed carry-lookahead adder in which the logic complexity is a linear function of n, the number of inputs, and the average computation time is proportional to the logarithm of the logarithm of n. To the best of our knowledge, our adder has the best area-time efficiency which is /spl Theta/(nloglogn). An economic implementation of this adder in CMOS technology is also presented. SPICE simulation results show that, based on random inputs, our 32-bit self-timed carry-lookahead adder is 2.39 and 1.42 times faster than its synchronous counterpart and self-timed ripple-carry adder, respectively, and, based on statistical data gathered from a 32-bit ARM simulator, it is 1.99 and 1.83 times faster than its synchronous counterpart and self-timed ripple-carry adder, respectively.

Pulse-mode handshaking is a form of 2-phase handshaking that uses pulses, instead of transitions, to represent events. It combines the conceptual simplicity of the 2-phase protocol (only two events per handshake) with the level based approach of 4-phase handshaking. Pulse-mode macromodules use a new, more concurrent form of operation than that of traditional pulse-mode systems, called Pulse burst operation (PBO). Pulse-mode handshaking is used in the design of a large set of macromodules that can be used to build cost-effective asynchronous systems. The set includes modules that efficiently implement control operations such as sequencing, selection, iteration, concurrency control and resource sharing. An arbiter and converter modules to interface pulse-mode to traditional 2-phase and 4-phase circuits are also included. A packet switch is designed to demonstrate the viability of pulse-mode macromodules to implement complex, high performance systems.

The various modes of failure of asynchronous sequential logic circuits due to timing problems are considered. These are hazards, critical races and metastable states. It is shown that there is a mechanism common to all forms of hazards and to metastable states. A similar mechanism, with added complications, is shown to characterize critical races. Means for defeating various types of hazards and critical races through the use of one-sided delay constraints are introduced. A method is described for determining from a flow table situations in which metastable states may be entered. A circuit technique is presented for extending a previously known technique for defeating metastability problems in self-timed systems. It is shown that the use of simulation for verifying the correctness of a circuit with given bounds on the branch delays cannot be relied upon to expose all timing problems. An example is presented that refutes a plausible conjecture that replacing pure delays with inertial delays can never introduce, but only eliminate glitches.>

A method was presented by A.L. Ruiz, P.P. Trabado, and J.O. Lopera (see ibid., vol.42, no. 5, p. 591-6, 1993) for efficiently generating the solutions of Boolean equations by using tables (i.e., rectangular arrays or matrices) of 0's, 1's, and dashes to represent Boolean expressions. Some enhancements of their method are presented. First, it is shown how the uniting theorem can be applied directly to simplify tables. Then it is shown how to complement a table, which would make their method (henceforth referred to as RTL) directly applicable to expressions containing complemented subexpressions. The latter result allows the method to be extended from the solution of equations of the form f(X)=1 to equations of the form f(X)=0, and, more generally to equations of the form f(X)=g(X), or to simultaneous equations of the same types.>

A key element (one is tempted to say the heart) of most digital systems is the clock. Its period determines the rate at which data are processed, and so should be made as small as possible, consistent with reliable operation.

A conventional positive-edge-triggered flip-flop (FF) senses and responds to the control input or inputs at the time the clock input is changing from 0 to 1. It does not respond at all to changes in the opposite direction. Negative-edge-triggered FF's behave in a complementary manner. Thus, these FF's can respond at most once per clock pulse cycle. It is proposed that double-edge-triggered (DET) FF's, responding to both edges of the clock pulse would have advantages with respect to speed and energy dissipation.

It is shown that, if a flow table has synchronizing sequences, they can be used, at little added cost, to reduce substantially the average delay in combinational iterative realizations that generate completion signals. This constitutes a generalization of earlier work by Waite. Some quantitative results are presented indicating the extent of speed up to be expected.

The self-synchronizing (SS) sequential circuits proposed by Chuang and Das, as well as by Rey and Vaucher are analyzed and compared. A variation of the latter system is proposed. It is shown that none of the above approaches can be used for unrestricted input change (UIC) operation. Procedures for synthesizing Huffman type asynchronous circuits suitable for UIC operation are improved. Data handling rates for the SS and Huffman type circuits are compared for SIC and MIC operation.

It is shown how any combinational function that can be described by a flow table—or equivalently—is realizable in iterative form—can be realized in tree form. The propagation delay is then proportional to the logarithm of n, the number of inputs, while the logic complexity is a linear function of n. These results are related to various implementations of high-speed binary adders and a proposed new high-speed adder circuit.

The problem of designing asynchronous circuits where the changes in binary input signals occur independently of one another is discussed. If several input changes occur within some interval δ1, the circuit behaves as though the changes were simultaneous. If consecutive changes are spaced by intervals exceeding some longer interval δ2 then the circuit reacts as though a sequence of single changes had occurred. But when the spacing is between these values, the system may react in an unsatisfactory manner unless special attention is paid to the problem during the design process. Constraints imposed by this problem on the row assignment and on the delay elements are derived.

Abstract—A method is presented for realizing any flow table that does not contain essential hazards with a circuit requiring no delay elements for proper operation. The procedure generally requires considerably fewer state variables than did an earlier technique for achieving the same result. It is based on a modification of a method by Tracey for constructing single-transition-time row assignments.

Three results are presented pertinent to the problem of finding minimum-row versions of incompletely specified flow tables for sequential or iterative circuits. 1) Conditions are precisely stated under which preliminary mergers can be made without the danger of ruining opportunities for ultimately finding a minimal-row version. 2) A theorem by McCluskey is generalized to show that for all flow tables if optional entries arise only due to restrictions as to which input states may immediately follow one another, then the reduction problem is relatively simple. 3) A useful heuristic in the form of a diagram illustrating implication relations of 2-member compatibles is introduced as an aid in finding minimal closed sets of compatibles.

An important step in the synthesis of sequential switching circuits is the assignment of binary variable states to represent internal states of the circuit. A formula is derived here which indicates the number of different assignments which can be made for flow tables having a given number of rows. There are only three essentially different assignments possible for a four-row table, and there are 140 for a five-row table.

Given a sequential switching function in the form of a flow table in which some of the entries are unspecified, the problem of reducing the number of rows in that flow table is extremely complex, and cannot, in general, be solved by any simple extension of the methods used for completely specified functions. An analysis of the problem is presented, and a partially enumerative solution is evolved. A rough indication of the efficiency of the given procedures may be obtained from the fact that these techniques have been successfully applied to approximately two dozen tables ranging up to about 15 rows. No solution required more than two hours.