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, or the voltage on some point in a circuit.
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.
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.
In addition to these, the functions nand and nor are commonly used. While we think of nand as being the same as a not operation composed with an and operation, in fact, the popularity of the nand function in digital design arises from the fact that nand is usually realized as a primitive function, and the and operation is frequently implemented in hardware as a not operation attached to the output of a nand gate.
The standard 2-input functions are:
A B | A and B | A nand B | A or B | A nor B | A xor B | A equ B -----+---------+----------+--------+---------+---------+--------- 0 0 | 0 | 1 | 0 | 1 | 0 | 1 0 1 | 0 | 1 | 1 | 0 | 1 | 0 1 0 | 0 | 1 | 1 | 0 | 1 | 0 1 1 | 1 | 0 | 1 | 0 | 0 | 1The xor operator is known as exclusive or, in English, and the equ operator is known as equals. 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 bIn the above, the overbar is used as a symbol 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 |------- --------|______|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.
The and, or, nand, nor and not logical operators all have conventional symbols that are distinguished by their shape and require no labels. These are crudely approximated below:
____ _____ --------| \ --------\ \ | AND )------- ) OR )------- --------|____/ --------/____/ ____ _____ --------| \ --------\ \ |NAND )O------ )NOR )O------ --------|____/ --------/____/ |\ NOT _____ | \ -------\\ \ --------| >O--------- ))XOR )------- | / -------//____/ |/In general, a "bubble" on any input or output of the symbol for a gate indicates a not operation, and a triangle by itself represents a buffer or amplifier. Thus, by DeMorgan's law, the following two symbols are equivalent:
____ _____ --------| \ -------O\ \ | )O------ ) )------- --------|____/ -------O/____/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 is 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
input A B | | o-- o-- | _|_ | _|_ | \ / | \ / | O | O | | | | ___ -|--|----|--|--| \ | | | | | | | | | )O-|-|-----|-|-- -|--|----|--|--|___/ | | | | | | | | ___ | | | | -|--|----|--|--| \ | | | | | | | | | )O-|-|-----|-|-- -|--|----|--|--|___/ | | | | | | | | ___ | | | | -|--|----|--|--| \ | | | | | | | | | )O-|-|-----|-|-- -|--|----|--|--|___/ | | | | | | | | ___ | | | | -|--|----|--|--| \ | | | | | | | | | )O-|-|-----|-|-- -|--|----|--|--|___/ | | | | | | | | _|_|_ _|_|_ | | | | | | | | \___/ \___/ O O | | | | X Y outputsNote 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.
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 outputsAs a rule, when reading schematic diagrams, lines indicate interconnecting wires. Where two lines cross, they are assumed not to be connected unless the intersection is marked with a dot (we use an o for this dot here, while we use O for the bubble indicating inversion). If lines indicating wires meet in a T configuration, they must be connected, even if the dot is absent. If one wire is interrupted by the other, or if one wire is shown with a semicircular arc where it crosses the other, the artist has gone out of the way to draw attention to the fact that they are not connected.
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 outputsThis 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. 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 0The 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 0We 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 outputsIn 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 this combinational circuit optimization. Unfortunately, optimization of an N input combinational logic function requires O(2^{n}) 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.
Logic circuits with feedback are sequential circuits. Consider the following:
_ ___ R --------| \ | )O---o--- Q --|___/ | _ | ___ | S -----|--| \ | _ | | )O-o-|--- Q --|--|___/ | | | | | | | ---------- | ---------------Here, treat Q and Qbar as distinct letters and, for the moment ignore the fact that the bar means negation.
We can describe the above circuit by a system of boolean equations:
_ _ Q = Q nand R _ _ Q = Q nand SFor some combinations of values of Rbar and Sbar, 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 solution)In the case of [Rbar Sbar] = [1 1], an attempt at solution merely simplifies our two equations to:
_ _ Q = Q nand 1 = not Q _ Q = Q nand 1 = not QThere are two solutions to this set of 2 Boolean equations in 2 unknowns, [Q Qbar] = [1 0] is one, and [Q Qbar] = [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 Qbar] by setting the inputs [Rbar Sbar] to [0 1] or to [1 0] and then, if we shift [Rbar Sbar] 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 [Rbar Sbar] = [0 0], the circuit is an excellent memory circuit.
RS 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 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 input in the flipflop whenever the C 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 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 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 optimizaiton is not a subject of discussion. Take a good digital logic course if you wish to optimize the function of digital circuits.