Delay-insensitive minterm synthesis

Last updated
Dims gate.png
Dims latch.png

Within digital electronics, the DIMS (delay-insensitive minterm synthesis) system [1] is an asynchronous design methodology making the least possible timing assumptions. Assuming only the quasi-delay-insensitive delay model the generated designs need little if any timing hazard testing. The basis for DIMS is the use of two wires to represent each bit of data. This is known as a dual-rail data encoding. Parts of the system communicate using the early four-phase asynchronous protocol.

The construction of DIMS logic gates comprises generating every possible minterm using a row of C-elements and then gathering the outputs of these using OR gates which generate the true and false output signals. With two dual-rail inputs the gate would be composed of four two-input C-elements. A three input gate uses eight three-input C-elements.

Latches are constructed using two C-elements to store the data and an OR gate to acknowledge the input once the data has been latched by attaching as its inputs the data output wires. The acknowledge from the forward stage is inverted and passed to the C-elements to allow them to reset once the computation has completed. This latch design is known as the 'half latch'. Other asynchronous latches provide a higher data capacity and levels of decoupling.

DIMS designs are large and slow but they have the advantage of being very robust.

  1. D. E. Muller, “Asynchronous logics and application to information processing,” Proc. Symp. Application of Switching Theory in Space Technology, H. Aiken and W. F. Main, Ed. , pp. 289-297, 1963.

Further reading

Related Research Articles

Digital electronics Electronic circuits that utilize digital signals

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.

VHDL Hardware description language

The VHSIC Hardware Description Language (VHDL) is a hardware description language (HDL) that can model the behavior and structure of digital systems at multiple levels of abstraction, ranging from the system level down to that of logic gates, for design entry, documentation, and verification purposes. Since 1987, VHDL has been standardized by the Institute of Electrical and Electronics Engineers (IEEE) as IEEE Std 1076; the latest version of which is IEEE Std 1076-2019. To model analog and mixed-signal systems, an IEEE-standardized HDL based on VHDL called VHDL-AMS has been developed.

Verilog, standardized as IEEE 1364, is a hardware description language (HDL) used to model electronic systems. It is most commonly used in the design and verification of digital circuits at the register-transfer level of abstraction. It is also used in the verification of analog circuits and mixed-signal circuits, as well as in the design of genetic circuits. In 2009, the Verilog standard was merged into the SystemVerilog standard, creating IEEE Standard 1800-2009. Since then, Verilog is officially part of the SystemVerilog language. The current version is IEEE standard 1800-2017.

In automata theory, sequential logic is a type of logic circuit whose output depends not only on the present value of its input signals but on the sequence of past inputs, the input history as well. This is in contrast to combinational logic, whose output is a function of only the present input. That is, sequential logic has state (memory) while combinational logic does not.

In electronics and especially synchronous digital circuits, a clock signal oscillates between a high and a low state and is used like a metronome to coordinate actions of digital circuits.

ATPG is an electronic design automation method/technology used to find an input sequence that, when applied to a digital circuit, enables automatic test equipment to distinguish between the correct circuit behavior and the faulty circuit behavior caused by defects. The generated patterns are used to test semiconductor devices after manufacture, or to assist with determining the cause of failure. The effectiveness of ATPG is measured by the number of modeled defects, or fault models, detectable and by the number of generated patterns. These metrics generally indicate test quality and test application time. ATPG efficiency is another important consideration that is influenced by the fault model under consideration, the type of circuit under test, the level of abstraction used to represent the circuit under test, and the required test quality.

In Boolean algebra, any Boolean function can be put into the canonical disjunctive normal form (CDNF) or minterm canonical form and its dual canonical conjunctive normal form (CCNF) or maxterm canonical form. Other canonical forms include the complete sum of prime implicants or Blake canonical form, and the algebraic normal form.

Propagation delay is the length of time taken for a signal to reach its destination. It can relate to networking, electronics or physics. Hold time is the minimum interval required for the logic level to remain on the input after triggering edge of the clock pulse.

A delay-insensitive circuit is a type of asynchronous circuit which performs a digital logic operation often within a computing processor chip. Instead of using clock signals or other global control signals, the sequencing of computation in delay-insensitive circuit is determined by the data flow.

In digital electronics, a synchronous circuit is a digital circuit in which the changes in the state of memory elements are synchronized by a clock signal. In a sequential digital logic circuit, data are stored in memory devices called flip-flops or latches. The output of a flip-flop is constant until a pulse is applied to its "clock" input, upon which the input of the flip-flop is latched into its output. In a synchronous logic circuit, an electronic oscillator called the clock generates a string (sequence) of pulses, the "clock signal". This clock signal is applied to every storage element, so in an ideal synchronous circuit, every change in the logical levels of its storage components is simultaneous. Ideally, the input to each storage element has reached its final value before the next clock occurs, so the behaviour of the whole circuit can be predicted exactly. Practically, some delay is required for each logical operation, resulting in a maximum speed limitations at which each synchronous system can run.

Asynchronous circuit is a sequential digital logic circuit that doesn't use a global clock circuit or signal generator to synchronize its components. instead, the components are driven by handshaking which indicates completion of the instructions. Handshaking works by simple data transfer protocols. Many synchronous circuits were developed in early 1950s as part of bigger asynchronous systems. Asynchronous circuits and theory surrounding is a part of several steps in integrated circuit design, a field of digital electronics engineering.

C-element

In digital computing, the Muller C-element is a small binary logic circuit widely used in design of asynchronous circuits and systems. It outputs 0 when all inputs are 0, it outputs 1 when all inputs are 1, and it retains its output state otherwise. It was specified formally in 1955 by David E. Muller and first used in ILLIAC II computer. In terms of the theory of lattices, the C-element is a semimodular distributive circuit, whose operation in time is described by a Hasse diagram. The C-element is closely related to the rendezvous and join elements, where an input is not allowed to change twice in succession. In some cases, when relations between delays are known, the C-element can be realized as a sum-of-product (SOP) circuit. Earlier techniques for implementing the C-element include Schmidt trigger, Eccles-Jordan flip-flop and last moving point flip-flop.

Metastability (electronics)

Metastability in electronics is the ability of a digital electronics system to persist for an unbounded time in an unstable equilibrium or metastable state. In digital logic circuits, a digital signal is required to be within certain voltage or current limits to represent a '0' or '1' logic level for correct circuit operation; if the signal is within a forbidden intermediate range it may cause faulty behavior in logic gates the signal is applied to. In metastable states, the circuit may be unable to settle into a stable '0' or '1' logic level within the time required for proper circuit operation. As a result, the circuit can act in unpredictable ways, and may lead to a system failure, sometimes referred to as a "glitch". Metastability is an instance of the Buridan's ass paradox.

Static timing analysis (STA) is a simulation method of computing the expected timing of a synchronous digital circuit without requiring a simulation of the full circuit.

In digital logic design, an asynchronous circuit is quasi delay-insensitive (QDI) when it operates correctly, independent of gate and wire delay with the weakest exception necessary to be turing-complete.

The primary focus of this article is asynchronous control in digital electronic systems. In a synchronous system, operations are coordinated by one, or more, centralized clock signals. An asynchronous system, in contrast, has no global clock. Asynchronous systems do not depend on strict arrival times of signals or messages for reliable operation. Coordination is achieved using event-driven architecture triggered by network packet arrival, changes (transitions) of signals, handshake protocols, and other methods.

In digital logic, a hazard is an undesirable effect caused by either a deficiency in the system or external influences in both synchronous and asynchronous circuits. Logic hazards are manifestations of a problem in which changes in the input variables do not change the output correctly due to some form of delay caused by logic elements This results in the logic not performing its function properly. The three different most common kinds of hazards are usually referred to as static, dynamic and function hazards.

A digital delay generator is a piece of electronic test equipment that provides precise delays for triggering, syncing, delaying and gating events. These generators are used in many types of experiments, controls and processes where electronic timing of a single event or multiple events to a common timing reference is needed. The digital delay generator may initiate a sequence of events or be triggered by an event. What differentiates it from ordinary electronic timing is the synchronicity of its outputs to each other and to the initiating event.

Timing closure is the process by which a logic design consisting of primitive elements such as combinatorial logic gates and sequential logic gates is modified to meet its timing requirements. Unlike in a computer program where there is no explicit delay to perform a calculation, logic circuits have intrinsic and well defined delays to propagate inputs to outputs. In simple cases, the user can compute the path delay between elements manually. If the design is more than a dozen or so elements this is impractical. For example, the time delay along a path from the output of a D-Flip Flop, through combinatorial logic gates, then into the next D-Flip Flop input must satisfy the time period between synchronizing clock pulses to the two flip flops. When the delay through the elements is greater than the clock cycle time, the elements are said to be on the critical path. The circuit will not function when the path delay exceeds the clock cycle delay so modifying the circuit to remove the timing failure is an important part of the logic design engineer's task. Critical path also defines the maximum delay in all the multiple register-to-register paths, and it need not be greater than the clock cycle time. After meeting the timing closure, one of the method to improve the circuit performance is to insert a register in between the combinational path of the critical path. This might improve the performance but increases the total latency of the circuit.

Flip-flop (electronics) Electronic circuit with two stable states

In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic. Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems.