Fri, 16 Sep 2011, 05:14
To my students in 306,
After talking to several students, it is clear to me that I did not get
an important point across.
Recall, we were discussing in class adding two 16-bit 2's complement
numbers A[15:0] and B[15:0] to produce a sum S[15:0], using
16 full adders. We drew the gate implementation of a full adder on
the board. It is Figure 3-15 in the textbook.
We noted that the result S[15:0] is not known until the carry out of bit 0
propagates to the full adder for bit 1, followed by the carry out of bit1
propagates to the full adder for bit 2, ... the carry out of bit 14 propagates
to the full adder for bit 15, and the full adder for bit 15 produces S[15] and
the carry out of 15. See Figure 3-16 for a similar example of this, where
instead we were adding two 4-bit numbers.
The question is: what is going on with the full adder for bit 15 while it
is waiting for the carry out of bit 14? Does it have any input or output
values? Answer: yes! AFTER the power switch is turned on, ALL wires
(we often use the term signals) have voltages (0 corresponding to 0 volts
or 1 corresponding to 2.9 volts) ALL the time. That is, the computer is
an electronic circuit and as soon as the power is turned on, each wire in
that circuit carries a voltage (either 0 or 1). It is NOT the case that
S[15] (for example) is in a vacuum until it gets the carry from bit 14.
It produces a voltage (0 or 1) based on what voltages happen to be on the
three inputs to the full adder A[15], B[15], and the carry input to the
bit 15 full adder.
We do not KNOW what that voltage is because we do not know what random
pattern of voltages exist as a result of the power being turned on. We also
do not CARE what that voltage is because it is not being produced as a result
of the addition. S[15] will be 0 or 1 as a result of the addition only AFTER
the carry bits have propagated their way from bit 0 to bit 1 to ... bit 15.
Until that happens, S[15] can bounce back and forth between having a 0 or a 1
depending on extraneous circuits in the computer. That is fine, since the
only thing we care about is that AFTER the add circuit has completed its work
(i.e., after the carry bits have propagated through), S[15] has the correct
value. We design the cycle time so that the add completes before the end of
the clock cycle, so that the value stored for S[15] at the end of the cycle
is the correct value.
But before the end of the cycle, S[15] could have bounced back and forth
between 0 and 1 multiple times, depending on what extraneous circuitry was
present.
So what is the point? The point is that the computer is an electronic circuit
and when the power is turned on, every wire (signal) carries a voltage 0 or 1.
Gates do not wait for the true values to propagate to them; rather they
produce outputs based on what their inputs happen to be at the moment.
No problem! As those inputs change due to the propagation of outputs from
earlier gates, so too will their outputs change, until finally we reach the
stable situation of all signals have completed their respective propagations.
After that, we have the stable and correct value. The cycle ends AFTER that,
and when it does, those stable and correct values are stored in latches.
A simple example:
----
0 --| | X -----
| OR |------| |
0 --| | | |
---- | AND |---- A
| |
1 --------------| |
-----
Suppose when the power was turned on, for some reason the value at X is 1.
The AND gates has two inputs, both = 1, producing at A, the output 1.
But over time, the result of the OR gate propagates to the AND gate. The
result of the OR gate is 0, which causes the output of the AND to then
become 0, which is the correct result for the circuit above. The AND
gate produces the AND of its two inputs ALL THE TIME. But the value
at A only matters after all the propagations have happened and the output
is in a stable state.
Hope this helps.
Enjoy the weekend. See you on Monday.
Yale Patt