Early completion on:
[Wikipedia]
[Google]
[Amazon]
Early completion is a property of some classes of
This diagram shows a 5-bit ripple carry adder in action. There is a five-stage long carry path, so every time two numbers are added with this adder, it needs to wait for the carry to propagate through all five stages.
By switching to dual-rail signalling for the carry bit, it can have each stage signal its carry out as soon as it knows. If both inputs to a stage are 1, then the carry out will be 1 no matter what the carry in is. If both inputs are 0, then the carry out will be zero. This early completion cuts down on the maximum length of the carry chain in most cases:
Two of the carry-out bits can be known as soon as input arrives, for the input shown in the picture. This means that the maximum carry chain length is three, not five. If it uses dual-rail signalling for inputs and outputs, it can indicate completion as soon as all the carry chains have completed.
On average, an ''n''-bit asynchronous ripple carry adder will finish in O(log n) time. By extending this approach to
Self-timed carry-lookahead adders
by Fu-Chiung Cheng, Stephen H. Unger, Michael Theobald. Digital electronics {{electronics-stub
asynchronous circuit
Asynchronous circuit (clockless or self-timed circuit) is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circuit ...
. It means that the output of a circuit may be available as soon as sufficient inputs have arrived to allow it to be determined. For example, if all of the inputs to a mux have arrived, and all are the same, but the select line has not yet arrived, the circuit can still produce an output. Since all the inputs are identical, the select line is irrelevant.
Example: an asynchronous ripple-carry adder
Aripple carry adder
An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they are ...
is a simple adder circuit, but slow because the carry signal has to propagate through each stage of the adder:
This diagram shows a 5-bit ripple carry adder in action. There is a five-stage long carry path, so every time two numbers are added with this adder, it needs to wait for the carry to propagate through all five stages.
By switching to dual-rail signalling for the carry bit, it can have each stage signal its carry out as soon as it knows. If both inputs to a stage are 1, then the carry out will be 1 no matter what the carry in is. If both inputs are 0, then the carry out will be zero. This early completion cuts down on the maximum length of the carry chain in most cases:
Two of the carry-out bits can be known as soon as input arrives, for the input shown in the picture. This means that the maximum carry chain length is three, not five. If it uses dual-rail signalling for inputs and outputs, it can indicate completion as soon as all the carry chains have completed.
On average, an ''n''-bit asynchronous ripple carry adder will finish in O(log n) time. By extending this approach to carry look-ahead adder
A carry-lookahead adder (CLA) or fast adder is a type of electronics adder used in digital logic. A carry-lookahead adder improves speed by reducing the amount of time required to determine carry bits. It can be contrasted with the simpler, b ...
s, it is possible to add in O(log log n) time.
External links
Self-timed carry-lookahead adders
by Fu-Chiung Cheng, Stephen H. Unger, Michael Theobald. Digital electronics {{electronics-stub