Cryptography Reference
In-Depth Information
17.2.1 Propagation Delays in CMOS Logic Gates
In CMOS logic [419], every gate has a propagation delay, which is inherent in the
existence of capacitances (most often unwanted, i.e. parasitic) within and around it.
Thus, every stimulus at the input of a logic gate requires some time to produce its
effect at the output. The propagation delay depends on many factors.
The most important factor is the function of a given gate. For instance, an AND
gate with one input equal to 0 will evaluate to 0 irrespective of the arrival time of the
second input. This “early evaluation” would not have happened with the same data
configuration on an OR gate [243, 390]. Indeed, an OR gate cannot decide on the
final result before being supplied with the value of its latest input if the fastest ones
are equal to 0.
The propagation time also depends on the shape of the input signals. An input sig-
nal transiting slowly will take longer time to propagate through the gate, since a signal
coming from a long line is likely to have a smooth edge, whereas a well-buffered
signal that has a short interconnect length will probably have a steep transition slope.
Thus the routing also influences the propagation time. The cross-coupling of the
wires also has a subtle effect has a signal's propagation speed and transition speed:
depending on the neighboring wires, any signal can be either slowed down, sped up
or have its waveform modified.
Additionally, some gates can answer in nondeterministic time. One representative
example is the XOR gate that is placed in the situation of an arbiter; this occurs when
the two inputs change almost simultaneously in antinomic directions, e.g. from
(
0
,
1
)
to
. Then, depending on the relative delay between the two inputs, the gate can
start to glitch. The answer time is thus dependent on thermal fluctuations.
The CMOS gates can glitch, which means that some transitions can be generated
even if they are not the final values. Once generated, the glitches propagate and lead to
other glitches. The final value of the computation is taken only after no other changes
occur. Indeed, the digital computations can be modeled as the transmission of events
on an oriented graph: the signal propositions being causal, every computation in a
combinational netlist necessarily converges to a steady state.
To summarize, the propagation time in CMOS logics depends on the data and on
the routing. Furthermore, the longest path for the same input data might not be the
same, because of the nondeterministic behavior of some gates.
(
1
,
0
)
17.2.2 Timing Constraints in Synchronous Logic
In sequential logic, one global signal, called the clock, coordinates all the combi-
national computation in parallel, at the same pace. One implicit condition is that
all the gates are expected to have finished propagating their data when the clock's
rising edge arrives. Of particular importance is the longest path, which determines
the maximal clock frequency. As discussed in the previous subsection, this critical
