Consequences of a Non-Negligible Propagation Delay

This part of the lesson deals with the delay with which logic gates calculate their output, which is not zero. This propagation delay, which we often ignore, has consequences on the maximum clock frequency of any processor.

When logic gates are studied, there are usually two different ways to communicate their functionality.

1. One is the truth table, that is the complete list of outputs given the list of all the possible combinations of inputs. Some examples of this are the nand gate, the truth table of which shows the output only deactivating when the inputs are both on, or the xnor gate, whose output is active only when the two inputs have the same value.
2. The other way of communicating functionality, is the way we just used to describe the truth table of the first two gates, that is a functional description in plain english. This is often preferred for the sake of brevity with gates that have many possible inputs, but a simple rule to calculate the output: this is the case of the incrementer chip here, which has 256 possible inputs, since the input port is 8 bits wide, but its output can simply be described as "the input plus one" for any given input.

Whichever way the gates were described with, there is one further detail that is often omitted or quickly touched upon and not really cared about: the output of each gate is always calculated with a small but measurable delay, with respect to the input variation. This is called propagation delay. Thankfully, this tool is granular enough to show it.

Propagation delay of a simple gate

To observe this delay in action, try to fiddle with the nand gate in the following simulator by inspecting the inputs and the output of the nand gate and then pause the simulation. Zoom in on the monitors so that you can comfortably see each step. Now let us fiddle with the inputs, and try to understand how many steps it takes to calculate the output given any input variation. It takes one step, and you can verify all the combinations by yourself. How long one step is is rather unimportant, it might be one millisecond or one nanoseconds, for our purposes that is not important: it is the smallest time division of the engine of our simulator, and might as well be the smallest time interval we can measure with a logic analyzer, in the real world.

Propagation delay in a simple boolean circuit

We can do the same with the xnor gate. We notice that sometimes the output takes five steps to propagate, as it is the case with inputs changing from zero zero to zero one, and sometimes six steps, as it is the case with inputs changing from zero zero to one one. We can therefore say that the propagation delay of the xnor is six steps. Why then is this value higher than the propagation delay of the nand gate? Let us remember that the nand gate is what is called a universal gate, which means that it can be used to synthesise any other logic gate, like this xnor here, that just so happens to be synthetized out of nand. The longer propagation delay of the xnor, is therefore directly proportional to the complexity of its implementation in nand gates, and we have also verified it being variable with previous input.

Let us spend two minutes for a qualitative analysis, of how the inner structure of the xnor chip results in the propagation delay we observed. We see the inner structure being made of 'and', 'not' and 'or' gates. Internally the not is made of a single nand port with shortcircuited inputs, which means that its propagation delay is the same, one step. The and gate is made of two nand gates in series, so it is rather intuitive that its propagation delay will be two steps. The same can be said about the or gate, which has a maximum of two nand gates in series between any of the inputs and the output. The structure of the xnor gate is slightly more complex, but we only have to understand how to generalize the concept. Each input has two routes towards the output, one that is five steps long and one that is six steps long, as they both pass through a not gate, an or gate, an and gate and only one of the two passes through the first not gate. So without assumptions about the inputs, we can say that the maximum delay of the xnor gate is six steps.

Propagation delay in a complex circuit

Let us now consider the incrementer. You can see inspecting it that its a rather complex circuit, so we expect it to have a rather high maximum propagation delay. How much exactly? Let us set the input to decimal try some values. Zero to one takes 12 steps. 254 to 255 takes 4 steps. 127 to 128 takes many steps.

The exact propagation delay of this chip will be asked to you as an exercise, after this part of this lesson. I invite you to notice, that the carry of each full adder is given as input of the following full adder. You will be asked to reason about what that means for the total propagation delay and if, given this structure, the fact that one input of the adders is always one, somehow changes the delay estimate.

Wrap Up Exercises

1. Conduct a qualitative analysis of the full adder circuit similar to that done for the xnor gate in the previous lesson. What propagation delay do you estimate? Here is an isolated full adder circuit, of which there are many inside the incrementer.

2. Does the overall propagation delay of the incrementer chip change for different inputs? If yes, with which criteria?

Please write your answers on a document, to then submit as PDF in the "Assignments" section. Mind that all answers from the whole Circuit Timing section are to be written on the same document. Feel free to add images to your answers, if it helps to explain something more concisely.