2. Digital Logic, A Breakneck Review
Part of
the 22C:122/55:132 Lecture Notes for Spring 2004
|
This review is organized in bottom-up fashion! We begin with a look at the binary system, and then work our way up from bits and combinational logic toward the register transfer layer.
In a digital system, any physical condition may be used to represent the values zero and one, also referred to as true or false. We may use, for example, the opening and closing of relay contacts, the presence of or absence of some working fluid in a pipe, the voltage on some point in a circuit, or the displacement of a pushrod. Huge numbers of digital systems have been built using all of these technologies.
In digital electronics, we generally speak in terms of on wires within a circuit. At the electonic level, we must distinguish between several different values:
The point to remember is this: Logic circuits are not perfect digital devices with only 2 signal levels, but they are constructed so that, under normal operating conditions, they behave as if they were 2-level devices, and as a result, we can usually design digital systems without reference to the details of these thresholds and absolute minimum values.
However, this is true only when we do not mix logic circuts from different logic families and it is only true when we do not overload circuits. Each logic family has different thresholds and minimum output values. Some families are fully compatable with each other, others marginally compatable so long as there is not much noise and loads are minimized, and some logic families require special conversion circuitry.
It is noteworthy that many integrated circuits offer TTL compatable inout-output pins, but that the logic used on the chip is quite different; each output pin has, as part of the chip, a level converter to generate TTL levels, and each input pin has, as part of the chip, a level converter to accept TTL levels. These impose a performance cost on the connections between chips, when compared to otherwise identical logical connections from one part of a chip to another part of the same chip.
Within a logic family, there is usually a concept of a unit load. The unit load of a standard input in that logic family is one, and the maximum fanout of a standard output in that logic family is the number of unit loads that may be connected to a single output. In the TTL logic families, most devices have a maximum fanout of at least 10, and chips marketed as drivers typically have fanouts of over 20.
A logician may think in terms of infinite fanout -- that is, that a logic variable can be inspected by any number of users, but in real life, fanout is limited, each user of a variable draws current or otherwise loads the hardware that computes that variable, and therefore, there is a limit on the number of inputs that may be connected to one output.
Special devices called bus drivers or buffers exist in many logic families. These are devices with a fanout limits significantly higher than other members of the family. There are also bus receivers, special devices that impose a load well below the standard unit load of the logic family, and sometimes also have much wider noise margins.
The basic combinational functions of digital logic are the Boolean logic functions and, or and not.
Please refer to http://homepage.cs.uiowa.edu/~dwjones/assem/notes/08arith.html for review material on basic logic gates. When logic is written equationally, the following symbols are commonly used:
a and b ab a*b a×b a&b
a or b a+b a|b
__ ___ ___
a nand b ab a*b a×b ~(a&b)
___
a nor b a+b ~(a|b)
a xor b
_______
a equ b a=b a=b a xor b
In the above, both the overbar and tilde (~) are used
as symbols for not, and it
should be noted that a continuous overbar over all terms of
an expression represents the negation of the entire expression
and not the negation of its component terms. Thus
_____ _ _
a + b is not the same as a + b
_ _ _____
a + b is the same as a * b (DeMorgan's Law)
_ _ _____
a * b is the same as a + b (DeMorgan's Law)
In addition, there are standard logic symbols for these
operaitons. When square boxes are used, the name (or sometimes,
an operator symbol) is shown inside the box:
inputs output
______
--------| |
| NAND |-------
--------|______|
Please avoid box notation in hand-drawn material, and try to stick to the standard symbols illustrated in the other notes cited above.
By longstanding convention, inputs to logic circuits are drawn on the left and outputs on the right, unless the context makes it clear that some other convention is being used.
In practice, it is common to talk about positive logic, in which the "asserted" state is represented by a high signal (nominal +5 in TTL logic) and negative logic, in which the "asserted" state is represented by a low signal (nominal 0 in TTL). Many engineers will attempt to draw circuits so that the circuit symbol used indicates the logical operation being performed, and the bubbles indicate which signals are positive and which are negative logic. Thus, for example, it is common to see this:
____
--------| \
| )O--
--------|____/ | _____
---O\ \
) )-------
____ ---O/____/
--------| \ |
| )O--
--------|____/
Instead of this:
____
--------| \
| )O--
--------|____/ | ____
----| \
| )O------
____ ----|____/
--------| \ |
| )O--
--------|____/
The latter shows the parts actually used (3 nand gates), but
the former is better at expressing the logical operation being
performed, a logical sum of products.
Given any truth-table, it is possible to automatically derive a logic circuit according to the following scheme:
inputs | outputs A B | X Y ----------+---------- 0 0 | 0 1 0 1 | 1 0 1 0 | 1 0 1 1 | 0 1
Specifically, use one not gate per input, one nand gate per row, and one nand gate per output. The row gates need as many inputs as there are inputs to the circuit, and the output column gates need as many inputs as there are 1's in the corresponding column of the circuit. For the example above, this logic circuitry would be arranged as follows:
input
A B
| |
o-- o--
| _|_ | _|_
| \ / | \ /
| O | O The Or Array
| | | | ___ (below)
-|--|----|--|--| \ | | | |
| | | | | )O-|-|-----|-|--
-|--|----|--|--|___/ | | | |
| | | | ___ | | | |
-|--|----|--|--| \ | | | |
| | | | | )O-|-|-----|-|--
-|--|----|--|--|___/ | | | |
| | | | ___ | | | |
-|--|----|--|--| \ | | | |
| | | | | )O-|-|-----|-|--
-|--|----|--|--|___/ | | | |
| | | | ___ | | | |
-|--|----|--|--| \ | | | |
| | | | | )O-|-|-----|-|--
-|--|----|--|--|___/ | | | |
| | | | _|_|_ _|_|_
(above) | | | |
The And Array | | | |
\___/ \___/
O O
| |
| |
X Y
outputs
Note that, while we have described this circuit using only nand gates, by DeMorgan's law, it is exactly equivalent to a sum-of-products structure with and gates for each row and or gates for each output column; this is why the array of interconnections on the left is known as the and array, while the array of interconnections on the right is known as the or array.
Specifically, wherever there is a 1 in in input column of the truth table, connect the un-inverted input for that column to the gate for the corresponding row of the and array, and wherever there is a zero, connect the inverted input to the gate in that row. Then, in the output column, wherever there is a one in the truth table, connect the output of the gate for that row to an input of the gate for that column of the or array.
input
A B
| |
o-- o--
| _|_ | _|_
| \ / | \ /
| O | O
| | | | ___
-|--o----|--|--| \ | | | |
| 0| | 0| | )O-|-|-----o-|--
-|--|----|--o--|___/ |0| |1|
| | | | ___ | | | |
-|--o----|--|--| \ | | | |
| 0| | 1| | )O-o-|-----|-|--
-|--|----o--|--|___/ |1| |0|
| | | | ___ | | | |
-o--|----|--|--| \ | | | |
| 1| | 0| | )O-|-o-----|-|--
-|--|----|--o--|___/ |1| |0|
| | | | ___ | | | |
-o--|----|--|--| \ | | | |
| 1| | 1| | )O-|-|-----|-o--
-|--|----o--|--|___/ |0| |1|
| | | | _|_|_ _|_|_
| | | |
| | | |
\___/ \___/
O O
| |
| |
X Y
outputs
In the above, the truth-table entries have been included at each intersection of row and column. It is common to abbreviate the logic diagram for the above as follows:
input
A B
| |
o-- o--
| _|_ | _|_
| \ / | \ /
| O | O
| | | | ___
| 0| | 0| | \ | |
-|--o----|--o--| )O-|-----o-
| | | | |___/ |0 |1
| | | | ___ | |
| 0| | 1| | \ | |
-|--o----o--|--| )O-o-----|-
| | | | |___/ |1 |0
| | | | ___ | |
| 1| | 0| | \ | |
-o--|----|--o--| )O-o-----|-
| | | | |___/ |1 |0
| | | | ___ | |
| 1| | 1| | \ | |
-o--|----o--|--| )O-|-----o-
| | | | |___/ |0 |1
| | | | _|_ _|_
| | | |
\_/ \_/
O O
| |
X Y
outputs
This shorthand form does not actually suggest that multiple outputs
of the row gates, for example, are connected to the same input of the
output column gates, but rather, it indicates the logical connection
described by the previous figure.
The abberviated form, however, does suggest the actual physical topology of the logic circuit, as implemented on a silicon wafer. Each row gate, for example, has an extended structure spanning all of the wires representing input columns, with a connection from a wire to the underlying row gate sufficing to connect an input. Similarly, each output column gate has a structure that spans the full height of the table. A connection from the conductor connected to the output of the row gate down through an insulating layer to the structure of the column gate suffices to make the logical connection.
Optimization techniques can be used to simplify circuits by eliminating rows from the table, saving one gate per row, but this has no effect on the speed unless fanout considerations are examined! This proves that, in theory, all combinational logic functions can be realized in exactly 3 levels of logic, or 3 gate delays, if each gate has a constant delay.
If no optimization is used, the above algorithm yields a ROM for the indicated function. In this case, if there are n inputs, there will be 2n rows, with the contents of the and array uniquely determined by the number of inputs, so the entire contents of the ROM are specified by the 2n binary numbers that specify the layout of the or array. Each of these numbers has as many bits as there are outputs from the truth table.
If optimization is used, the algorithm yields a PLA or programmable logic array realization of the circuit. Both ROM and PLA realizations of circuits can operate at the same theoretical speed, if fanout is not considered.
Given the truth table for a function, it is sometimes the case that, for some combination of inputs, one or more outputs of the function will not matter, either because they will be ignored by the circuitry they feed, or because that combination of inputs will never occur. We call these don't care outputs, and indicate them using the letter X or sometimes a dash or question mark in the corresponding truth table entry.
Given the truth table for a function, it is sometimes the case that more than one combination of inputs will have the same output, or rather, the ones and zeros in the outputs will be compatable; don't care entries in an output row match anything. If two rows of the truth table have the compatable outputs, and if the two rows have inputs that differ in only one bit, the rows may be combined by simply ignoring the value of that input bit. When rows are combined this way, ignored inputs are indicated using the same don't care notation, that is, X, dash or question mark.
In the hardware realization of a logic circuit, the only row gates (and or nand) that are needed are those where the output column of the circuit contains at least one entry that is one. If all the entries are zero or don't care, the row gate can be omitted.
After omitting unneeded row gates, we may find that some input is never needed in its inverted state. The inverter on the input column may be omitted in this case.
Consider this truth table:
A B | X Y
------+------
0 0 | 1 -
0 1 | - 1
1 0 | 1 0
1 1 | 0 0
The above optimization rules allow this table to be rewritten as:
A B | X Y
------+------
0 x | 1 1
1 0 | 1 0
1 1 | 0 0
We can implement this as:
input
A B
| |
| o--
| | _|_
| | \ /
| | O
| | | | ___
| x| | 0| | \ | |
-|--|----|--o--| )O-o-----o-
| | | | |___/ |1 |1
| | | | ___ | |
| 1| | 0| | \ | |
-o--|----|--o--| )O-o-----|-
| | | | |___/ |1 |0
| | | | | |
| 1| | 1| | |
-|--|----|--|----------|-----|- omitted
| | | | |0 |0 row gate
| | | | _|_ _|_
| | | |
\_/ \_/
O O
| |
X Y
outputs
In this example, a brute-force implementation of the truth table in
digital logic would have taken 8 gates (2 input column inverters,
4 row gates, 2 output column gates) while the optimized version
requires only 5 gates.
The Karnaugh Map (see any elementry text on digital logic) is a graphical tool for optimizing circuits with 4 or fewer inputs (it can be extended to 5 inputs with difficulty). The Quine McCluskey algorithm is the classical general algorithm for combinational circuit optimization. Unfortunately, optimization of an N input combinational logic function requires O(2n) time, simply because it requires examination of every truth table entry. Thus, optimal methods are rarely used for functions with large numbers of inputs.
Tristate logic is not logic that deals in, for example, 1, 0, and -1 as numeric values, or true, false and perhaps as logic values. When this is intended, we will use terms like three-valued logic.
Tristate bus drivers are devices that, in addition to being able to drive their output to one or zero are also able to disconnect their output. Thus, if there are many tristate drivers connected to a bus line, any one of them may drive the line true or false, but if two of them attempt, simultaneously, to drive the line, a problem will arise when one drives the line up while the other drives the line down.
Tristate devices are not essential! It is always possible to replace a bus line with many tristate drivers by an equivalent multiplexor, but such replacements are physically inconvenient. One way of thinking of tristate drivers and bus lines is to think of them as distributed implementations of multiplexors. The classical pictoral representation of a tristate driver is as an amplifier or inverter with a control input:
|\
data in | \ tristate data out
----------| >---------
| /
|/|
control in |
------------
In the absence of bubbles indicating inversion, if the control input is zero, the tristate output is disconnected, while if the control input is one, the tristate output is connected to the data input.
Logic circuits with feedback are sequential circuits. Consider the following:
_ ___
R --------| \
| )O---o--- Q
--|___/ |
_ | ___ |
S -----|--| \ | _
| | )O-o-|--- Q
--|--|___/ | |
| | | |
| ---------- |
---------------
Here, treat Q and Q as distinct letters and, for the moment ignore the fact that the overbar means negation.
You can find better drawings of these sequential circuits at http://homepage.cs.uiowa.edu/~dwjones/assem/notes/11device.html, in the subsection Building Registers, at the Gate Level.
We can describe the above circuit by a system of boolean equations:
_ _
Q = Q nand R
_ _
Q = Q nand S
For some combinations of values of R and S, we can solve these equations. We get the following:
_ _ _
R S | Q Q
-------|-------
0 0 | 1 1
0 1 | 1 0
1 0 | 0 1
1 1 | ? ? (no unique solution)
In the case of [R S] = [1 1], an attempt at solution merely simplifies our two equations to:
_ _ Q = Q nand 1 = not Q _ Q = Q nand 1 = not Q
There are two solutions to this set of 2 Boolean equations in 2 unknowns, [Q Q] = [1 0] is one, and [Q Q] = [0 1] is the other. In general, when there is feedback in a combinational circuit, it can be analyzed in this way, reducing the problem to a set of n equations in n unknowns for each of the possible combinations of external inputs, where there are n bits of feedback.
For the above circuit, note that we can set a value of [Q Q] by setting the inputs [R S] to [0 1] or to [1 0] and then, if we shift [R S] to [1 1], the circuit will stay in that state indefinitely. We call this circuit an RS Flipflop, and we say that we can set the state of the flipflop by a negative pulse on one or the other inputs. So long as we avoide the state [R S] the circuit is an excellent memory circuit; in fact, it is basically the circuit used to store data in a static RAM chip.
We used the names R and S for the inputs to this circuit because these lines are normally one, but if you put a pulse of zero on R, you will reset the flipflop, setting the Q output to zero, and if you put a pulse of zero on S, you will set the flipflop, setting the Q output to one. The names Q and Q for the outputs suggest that the two outputs will always be opposites, as they are so long as the inputs are not both zero. The use of the letter Q is entirely a matter of tradition and has no obvious explanation.
RS or set-reset flipflops are common enough that there is a standard schematic symbol for the circuit:
_______ |_ | ------|R Q|----- | | | | |_ _| ------|S Q|----- |_______|
The R S flipflop circuit is not well matched to the needs of the user, because neither input is equal to the value we wish to store. This motivates the development of the circuit known as a type D latch.
____ _______
D--o------| \ |_ |
_|_ | )O----|R Q|-----
\ / ---|____/ | |
O | ____ | |
--|---| \ |_ _|
| | )O----|S Q|-----
C-----o---|____/ |_______|
With the addition of two nand gates and an inverter, we can store
the value of the D or data input in the flipflop whenever the C or clock
input is high, and remember that value indefinitely when the C input is low.
D latches are commonly used to construct registers in applications
where the exact moment at which the D input is sampled is not
critical. The operation of storing data in such a flipflop is referred to
as latching data in, using a positive pulse on the clock input to do so.
We can also call it clocking the data into the flipflop.
The D latch is frequently drawn using the following symbol:
_______ | | ------|D Q|----- | _ | | _| |_ | | _| ------|>C Q|----- |_______|
When a flipflop symbol contains a little graph of a pulse or other waveform, the graph indicates the nature of the input to the clock terminal C that will cause the flipflop to change state or remember its input. In this case, we have a positive pulse triggered D latch because the positive pulse on the C input causes the D input to appear on the Q output. The clock input to a flipflop symbol is frequently distinguished by the little triangle inside the symbol!
The problem with the D latch is that, if the input changes while the clock pulse is in progress, it is hard to control the value that will be stored. This motivates the development of edge triggered and master slave flipflops. Consider the following:
_______ _______ D | | D' | | ------|D Q|------------|D Q|----- | _ | | _ | | _| |_ | | _| |_ | | _| | _| ---|>C Q|- ---|>C Q|----- | |_______| | |_______| | O | /_\ | | C | | --o--------------------
In the above circuit, because the 2 type D latches have clock inputs that are inverted relative to each other, changes in D never directly affect the output. However, when C is 0, the value of D appears at D', and as C changes from 0 to 1, D' is held constant and transferred to the Q output. Thus, we say that the externally observable state of this flipflop changes on the leading edge of a (positive) pulse on the C input. Because it has 2 stages, we call it a master-slave flipflop, and because its basic behavior is like a D latch, we call it a leading edge triggered master-slave D flipflop. In schematic diagrams, this is frequently abbreviated as:
_______ | | ------|D Q|----- | _ | | _| | | _| ------|>C Q|----- |_______|Here, the little graph inside the box indicates that it is leading-edge triggered. Commercially produced D flipflops are always produced by optimization of the design outlined here. The behavior is the same, but the number of gate delays from input to output is significantly reduced, and the existance of distinct master and slave stages in the flipflop is greatly obscured.
There are also JK flipflops, but their use is largely confined to optimal implementation of sequential circuits such as counters, and as a result, they are not important in this course, where low level digital circuit optimizaiton is not a subject of discussion. Take a good digital logic course if you wish to optimize the function of digital circuits.