INF107

From propagation time to computation time

Because of the physical constraints related to its concrete implementation, the output of a logic gate does not change its state instantaneously when its inputs change.

The propagation time of a gate, denoted by $t_p$, is the time between the change of the value of an input and the stabilization of the value of the gate’s output.

During this time, the value of the gate output may not correspond to the logical function applied on the gate’s current input values. The output value should therefore not be taken into account during this period.

Taking this propagation time into account is important in order to determine the maximum operating speed of the implementation of a logic function and more generally the computation time of any arithmetic function.

Example of the 1-bit adder

Consider again the 1-bit full adder (as introduced in section Addition):

If we assume that each of the basic gates (here the XORs with two inputs, two-input AND and three-input OR) all have a propagation time of $t_p=1\mathrm{ns}$, once the inputs $a_i$, $b_i$ and $r_i$ are stable, the outputs will be stable and correct after 2 ns. The propagation time of this implementation of the 1-bit adder is therefore 2 ns.

Example of the carry-ripple adder

From this 1-bit adder, we construct a simple adder with carry propagation:

Once the inputs $a_0,\dots ,a_3$, $b_0,\dots ,b_3$ and $c_0$ are stable, the outputs $s_0$ and $c_1$ of the first 1-bit adder will be stable after 2 ns. As the $c_1$ input of the second 1-bit adder is only stable after 2 ns, its outputs $s_1$ and $c_2$ will be stable 2 ns later, i.e. after 4 ns.

So for this 4-bit carry-ripple adder, the outputs $s_3$ and $c_4$ will finally be stable after 8 ns. The propagation time, or computation time, of this adder is therefore 8 ns.