AMAZON multi-meters discounts AMAZON oscilloscope discounts
The construction of most digital systems is a large task. Disciplined designers in any field will subdivide the original task into manageable subunits-building blocks-and will use the standard subunits wherever possible. In digital hardware, the building blocks have such names as adders, registers, and multiplexers.
Logic theory shows that all digital operations may be reduced to elementary logic functions. We could regard a digital system as a huge collection of AND, OR, and NOT circuits, but the result would be unintelligible. We need to move up one level of abstraction from gates and consider some of the common operations that digital designers wish to perform. Some candidates are:
(a) Moving data from one part of the machine to another.
(b) Selecting data from one of several sources.
(c) Routing data from a source to one of several destinations.
(d) Transforming data from one representation to another.
(e) Comparing data arithmetically with other data.
(f) Manipulating data arithmetically or logically, for example, summing two binary numbers.
We can perform all these operations with suitable arrangements of AND, OR, and NOT gates, but always designing at this level would be onerous, lengthy, and error-prone. Such an approach would be comparable to programming every software problem in binary machine language. Instead, we need to develop building blocks to perform standard digital system operations. The building blocks will allow us to suppress much irrelevant detail and design at a higher level. The procedure is analogous to giving the architect components such as doors, walls, and stairs instead of insisting that he design only with boards, nails, and screws.
INTEGRATED CIRCUIT COMPLEXITY
In Section 2, you studied low-level building blocks--AND, OR, and NOT. These come in integrated circuit packages containing a few gates that are not interconnected and that can be used in synthesizing elementary circuits from Boolean algebraic equations. The industry's name for devices of this complexity, containing up to 10 gates, is SSI (small-scale integration). Digital designers find that operations such as those we listed above-(a) to (0-occur in nearly any system design. As a result, manufacturers have provided integrated circuit packages of interconnected gates to perform these operations. Chips that contain from 10 to about 100 gates are called MSI (medium scale integration). Circuits with a nominal complexity of about 100 to 1,000 gates are classified as LSI (large-scale integration), and circuits with more than the equivalent of 1,000 gates are called VLSI (very-large-scale integration). Micro processors and memory arrays are examples of VLSI integrated circuits, as are many special-purpose chips. The boundaries between the categories are only suggestive; in fact, the use of the term LSI as a measure of chip complexity is waning.
Each class of integrated circuit-SSI, MSI, LSI, and VLSI-is important at its appropriate level of design. The digital designer should try to design at the highest conceptual level suitable to the problem, just as the software specialist should seek to use prepackaged programs or a high-level language instead of assembly language when possible. In software programming, the accomplished problem solver has not only a knowledge of Fortran, but also of computer organization, system structure, assembly language, and machine processes. Similarly, to achieve excellence in solving problems with digital hardware, we need skill in using all our tools, from the elementary to the complex.
COMBINATIONAL BUILDING BLOCKS
Combinational and Sequential Circuits
In this section, we will develop a set of building blocks that have hardware implementations of the MSI or LSI level of complexity, and have no internal storage capacity, or "memory." Such circuits, with outputs that depend only on the present values of the inputs, are called combinational. The important class of circuits that depend also on the ,condition of past outputs is called sequential. We will present sequential circuits and sequential building blocks in Section 4. Table 12-1, at the end of Section 12, is a list of useful SSI and MSI integrated circuits.
The Multiplexer
A multiplexer is a device for selecting one of several possible input signals and presenting that signal to an output terminal. It is analogous to a mechanical switch, such as the selector switch of a stereo amplifier (FIG. 1). The amplifier switch is used for selecting the input that will drive the speaker. Except for the moving hand, the electronic analog is easily constructed. We use Boolean variables instead of mechanical motion to select a given input. Consider a two-position switch with inputs A and B and output Y, such as shown in FIG. 2. Introduce a variable S to describe the position of the switch and let S = 0 if the switch is up and S = 1 if the switch is down. A Boolean equation for the output Y is Y = AoS + B-S
Using this equation, we can build an electronic analog of the switch; FIG. 3 is one design. There, S is the select input.
FIG. 1. A mechanical selector switch.
FIG. 2. A two-position mechanical switch.
FIG. 3. Implementation of the electronic switch Y A'S + B'S.
Commercial MSI devices correspond to the more complex switch shown in FIG. 4. The right-hand switch, called an enable (or strobe), acts as a Boolean AND function. If we call the closed position of the enable switch G and the open position G, then
Y = Go(A-S + BoS) (1)
FIG. 4. An enabled selector switch.
FIG. 5 is a schematic for a device based on this equation that behaves like common commercial devices. Such a circuit is called a 2-input multiplexer (mux); its mixed-logic symbol and the representation of Eq. (1) are shown in FIG. 6.
FIG. 7 is a diagram of a typical commercial device, the 74LS157 Quad Two Input Multiplexer. This chip has four 2-input multiplexer units (designated 1 through 4) packaged in a single integrated circuit chip, with each mux sharing a common select input S and a common enable input En.
FIG. 5. An enabled two-position electronic selector switch.
FIG. 6. Mixed-logic multiplexer notations.
FIG. 7. The 74LS157 Quad Two Input Multiplexer.
If we desire to select an output from among more than two inputs, the multiplexer must have more than one select input. The select inputs to a mux form a binary code that identifies the selected data input. One select line has 2^1 = 2 possible values; two select lines allow the specification of 2^2 = 4 different values. For instance, if we have select lines S1 and SO, the pair S1, SO represents a binary number that may identify one of four possible inputs:
S1 so Selected input position
Commercial integrated circuits provide 2-, 4-, 8-, and 16-input multiplexers, with a variety of inverted and non-inverted outputs, separate and common enable inputs, and so on. You should consult the manufacturers' integrated circuit data books for detailed information about these useful devices.
The multiplexer select code represents an address, or index, into the ordered inputs. We may view the data inputs to the mux as a vector or table, and the select lines as an address. A multiplexer is thus a hardware analog of a I-bit software "table look-up." FIG. 8 illustrates the analogy. In systems design, table look-up is an important concept which hardware designers have not exploited to the same extent as programmers. In subsequent sections, you will see many powerful uses of this concept. When you are faced with selecting, looking up, or addressing one of a small number of items, think MUX. Table look-up, or input selection, is convenient for up to 16 inputs, using the appropriate MSI integrated circuit chip. For more than 16 inputs the solution is not as neat but is nevertheless systematic. Suppose that you need to do a look-up in a table of 32 entries. Divide the inputs into groups, say four groups of 8 entries each. Then we may view the 32-element look-up as consisting of two look-ups, one to select the proper group of 8, and the second to pick the correct member of that group. The selection index for the 32-element look-up is a 5-bit binary code of the form S4, S3, S2, S1 , S0. Each group of 8 inputs requires 3 bits for specifying an input and 2 bits for picking the proper group of 8. FIG. 9 shows a realization that uses four 8-input multiplexers and one 4-input mux.
The conventional symbol for a multiplexer shows the inputs as having T = H, but the output may be either high- or low-active, depending on the particular chip. As mixed logicians, we realize that we may present all the inputs in T = L form without affecting the circuit; then the output will be of opposite polarity to that in the conventional symbol for the device. In FIG. 10 we show the two equivalent mixed-logic forms for an element of a 74LS352 Dual Four Input Multiplexer, a circuit whose output polarity is inverted. Changing the polarity of the inputs affects all the input lines and the output (all the data paths) but has no effect on the selection or enabling systems.
FIG. 8. A hardware analog of a software table lookup. A single multiplexer
provides a I-bit lookup. Several multiplexers addressed by a common signal
form a multibit lookup.
(a) Software table lookup (b) Hardware table lookup using multiplexer
The Demultiplexer
A demultiplexer sends data from a single source to one of several destinations.
Whereas the multiplexer is a data selector, the demultiplexer is a data distributor or data router. A mechanical analog is the switch used to route the power amplifier output of an automobile radio either to a front or a rear speaker, as illustrated in FIG. 11. This switch is the same type of two-position mechanical switch shown in FIG. 1. A mechanical switch can transmit a signal in either direction, whereas the electronic analog can transmit data in only one direction.
Since we cannot use a multiplexer in the reverse direction, we are forced to provide a demultiplexer to handle this operation.
FIG. 9. A 32-element table lookup.
FIG. 10. Mixed-logic symbols for the 74LS352 4-input multiplexer.
FIG. 11. A mechanical distributor switch.
The Boolean equations for the switch in FIG. 11 are
Front speaker = DUT-S
Rear speaker = DUT-S
S = T when the switch is down. The electronic gate equivalent of these equations is so simple that no commercially packaged version is available.
The smallest demultiplexer that is available in an integrated circuit package is a dual 4-output device. FIG. 12 is the mixed-logic symbol for one of the two identical and independent demultiplexer elements in the 74LS139 Dual One to-Four Demultiplexer chip. Inputs B and A are the routing controls for the data source. Just as the multiplexer has a binary code for the selection of an input, the demultiplexer has a similar code for selecting a particular output. All the outputs on the demultiplexer must have a value of FALSE except the one selected by the routing code. The selected output will be T or F, following the condition of the input G. The 74LS139 produces a high voltage level at all unselected outputs (T = L), so the mixed-logic symbol must have small circles on the outputs. Since this demultiplexer routes the input data to an output unchanged, there must also be a circle on the demultiplexer input.
FIG. 12. An element of the 74LS139 Dual One-to-Four Demultiplexer.
The truth table for a 4-output demultiplexer and the voltage table for the 74LS139 are
The logic equations for the outputs follow either from the truth table or from the description of the operation of the demultiplexer
Y0 = B-A-G
Y1 = B-A-G
Y2=B-A-G
Y3 = B-A-G
For practice, you may wish to design a mixed-logic SSI circuit for this demultiplexer, using Nand gates and inverters. This circuit has three inputs (B, A, and G) and four outputs Y1.
Eight-output demultiplexer are available as MSI chips. For example, the 74LS42 chip, usually described as a "decoder," functions as a demultiplexer.
FIG. 13 is its symbol, plus the logic equations for each output. There are actually two more outputs on this chip:
Y8 = C-B-A-D
Y9 = C-B-A-D
These outputs do not correspond to any function of the demultiplexer and they do not appear on the mixed-logic symbol. We will encounter them in the next section, when we discuss decoders.
FIG. 13. The 74LS42 demultiplexer and the equations for its outputs.
To summarize, the demultiplexer building block routes a single source to one of several destinations. A routing code is supplied to the control inputs to select the destination.
The Decoder
In digital design, we frequently need to convert an encoded representation of a set of items into an exploded form in which each item in the set has its own signal. The concept of "encoded information" pervades our lives. Encoding is a useful way of specifying a single member of a large set in a compact form.
For instance, every decimal number is a code for a particular member of the set of natural numbers. In everyday affairs, we usually do not need to decode the code explicitly, but sometimes the decoding becomes necessary.
Suppose you walk into a store in a foreign country to buy a coffee cup.
You choose a cup on the shelf, so you tell the clerk that you want the fourth cup from the left. You have used a code (4) to identify the desired cup, but the clerk does not know English and cannot pick out the correct cup. Since the clerk is unable to decode your "4" into a specific item, you point to the cup.
Your pointed finger means "This one." You were forced to decode your code.
Whenever we use a number to designate a particular object, decoding must occur. Usually, we do this implicitly or intuitively, without thinking about it, but sometimes, as in the china shop, the decoding becomes very explicit.
In hardware, codes are frequently in the form of binary numbers and, in most cases, the decoding required to gain access to an item is buried within a building block. For example, an 8-input multiplexer has a 3-bit select code to specify the particular input. We purposely include within the mux the decoding of the select code-the mux building block contains the circuitry to translate "input 4" on the control lines to "this input." In computer programming we specify a memory location by giving its address. In the hardware (the memory unit of the computer), this numeric address must be decoded to gain access to the particular memory cell.
Another common use of codes is in the operation code of a typical computer instruction. Most computers allow only one operation to be specified in each instruction, and the operation code describes the particular operation. In Part II of this book you will study the art of digital design and will participate in the design of a minicomputer modeled after the PDP-8. The PDP-8 instruction has a 3-bit operation code field that specifies one of eight possible operations. For now we will call the 3 bits of this field C, B, and A. The operation codes and their instruction mnemonics are:
From the viewpoint of the computer programmer, the decoding of the operation code is buried inside the computer. But we are studying hardware design, and we must face the decoding problem squarely. To implement this instruction set, we require eight logic variables (AND . .. OP) to control the specific activities of each instruction. Only one of these eight variables will be true at any time. The translation from the operation code into the individual logic variables is a decoding. We could build the decoding circuits from gates, using the methods of the previous sections. For instance, the logic equations for two of the variables are
TAD = C·B·A
JMS = C·B·A
Decoding is so common in digital design that our appropriate posture is to package the decoding circuitry into a logical building block. The decoder building block has the characteristic that only one output is true for a given encoded input and the remaining outputs are false. Integrated circuits for decoders are available in several forms, typically with 2, 3, or 4 inputs. The main limitation on the size of the input code is the number of pins required for the outputs, since the number of outputs grows exponentially with the size of the code. For instance, a 3-bit binary decoder has 8 outputs (2^3 = 8), whereas a full 4-bit binary decoder has 16 outputs (2^4 = 16), requiring a larger integrated circuit package. Decoding a 5-bit binary number would produce 32 outputs-too many for useful packaging as an MSI chip.
The 74LS42 Four-Line-to-Ten-Line Decoder is a typical MSI decoder. This chip will decode a decimal number 0 through 9, expressed as a 4-bit binary code, into one of 10 individual outputs. The binary representation for 9 is 1001; the 4-bit codes from 1010 through 1111 do not arise from the encoding of the decimal numbers. By eliminating 6 of the possible 16 output pins, the 74LS42 circuit can be made to fit conveniently into a 16-pin chip. FIG. 14a is the mixed logic symbol for the 74LS42. The outputs are all low-active (T = L)-a characteristic of most commercial MSI decoders.
FIG. 14. Two uses of the 74LS42 decoder.
The 74LS42 serves as a 3-bit decoder when the high-order bit (D) of the input code is false. The 8 outputs from the resulting 3-bit decoding are Y0 through Y7.
Another important use of the 74LS42 is as an enabled 3-to-8 decoder. The enabling feature is similar to that found on multiplexers in that outputs are always false unless the circuit is enabled. Whenever the D input to the 74LS42 is H, outputs Y0 through Y7 are false, regardless of the condition of the inputs C, B, and A; thus the 8 outputs for the 3-bit code are false and the chip is disabled.
When input D is L, the chip is enabled for 3-bit decoding, and exactly 1 of the 8 outputs YO through Y7 is true. When the normal mixed-logic representation for the decoder is used, the D code bit acts as a disabling or not-enabling signal (with T = H). To use the 74LS42 as an enabled decoder, we usually represent the D input as an enabling signal (with T = L) rather than as a part of the input code. The mixed-logic notation for this enabled 3-to-8 decoder building block is shown in FIG. 14b.
In addition to the 74LS42 chip's uses as a decoder, this same chip serves as a demultiplexer, as we saw in the previous section. In that application, we viewed the A, B, and C inputs as a select code, and the D input as a data signal to be routed to a selected destination. This duality of function is characteristic of decoders and de-multiplexers. In practice, the decoding applications far out number those of demultiplexing.
The Encoder
The converse of the decoding operation is encoding-the process of forming an encoded representation of a set of inputs. This operation does not occur in digital design as frequently as decoding, yet it is of sufficient importance to be a candidate for one of our standard building blocks. In strict analogy with decoding, we should require that exactly one input to an encoder be true. Since there is no way that an encoder building block can enforce this restriction on input signal values, encoders always appear in the form of priority encoders.
This variation, which is more useful than the regular encoder, allows any number of inputs to be simultaneously true, and produces a binary code for the highest numbered (highest-priority) true input.
A well-designed priority encoder should provide some way to denote a situation in which no input is true. There are two approaches to this problem.
Method 1 is to number the input lines beginning with 1 and reserve the output code 0 to indicate that no inputs are true. Method 2 is to number the inputs beginning with 0, but provide a separate output signal which is true only when no input is true. The first method requires fewer output lines but uses up a code pattern to indicate no active inputs. The second method requires an extra output but allows all the code values to represent true conditions at the input.
As a small illustration of priority encoding, consider circuits that produce a 2-bit code from a set of individual inputs. The first method will handle only 3 input lines, whereas the second method accommodates 4 inputs. Here are truth tables for the two styles of priority encoders (remember, X in the truth table means "both values" and - means "don't care"):
Equations for the output variables can be derived by the methods described in Section 1. For instance, the logic equations for the outputs for method 2 are
B = D3·D2 +D3 = D2 + D3
A = D3·D2 ·D1 + D3 = D2·D1 + D3
W = D3·D2 ·D1-D0
Commercial priority encoders come in a variety of forms representing both of these methods, sometimes also having an enabling control input, and occasionally with extra inputs and outputs to permit several chips to be cascaded. Customarily, the inputs and code outputs are low-active (T = L). FIG. 15 is the mixed logic symbol for a typical chip, the 74LS147 Ten-Line-to-Four-Line Priority Encoder, which conforms closely to method 1 above and produces a 4-bit output code, D, C, B, A. The chip has only 9 input lines, not 10 as the name suggests.
The tenth line, corresponding to the output code 0000, is inferred from the absence of any true input.
FIG. 15. The 74LS147 Ten-Line to-Four Line Priority Encoder.
Priority encoders are frequently used in managing input-output and interrupt signals. The encoder produces a code for the highest-priority true signal. This code may serve as an index for branching or for table lookup in a computer program.
The Comparator
Comparators help us to determine the arithmetic relationship between two binary numbers. Occasionally, we need to compare one set of n bits with another reference set of n bits to determine if the first set is identical to the reference set. The proper way to determine identity is with a logical COINCIDENCE operation. For instance, to find if a single bit A is identical to a reference bit B, we use
A.EQ.B = A0B (2)
For a pattern of n bits, we need the logical AND of each such term:
A.EQ.B = (AO 0 BO)-(A1 0 B1)- ... -(An 0 Bn) (3)
We can make an important distinction based on whether the reference set of bits is an unvarying (constant) or a varying pattern. Expanding the single bit Eq. (2) into its AND, OR, NOT form, we have
A.EQ.B = A·B + A'R
If B is constant, this equation can be simplified into one of two forms:
A.EQ.B = A if B = T
A.EQ.B= A if B = F
Consider a comparison of an arbitrary 4-bit A with a fixed 4-bit B T. Equation (3) can be reduced to A.EQ.B = A0·A1·A2·A3
which can be realized with a 4-input AND element.
T, F, F,
If the reference pattern is not fixed, we are stuck with Eq. (3). FIG. 16 is a circuit for 4-bit inputs, using common SSI chips. This type of circuit is a candidate for a building block, and there are MSI chips that perform multibit arithmetic comparisons.
FIG. 16. An SSI implementation of the equality comparison in Eq. (3).
FIG. 17. An 8-bit magnitude comparison using the 74LS85.
We frequently treat arrays of bits as representations of positive binary numbers. Sometimes we need to determine if one such representation A is arithmetically greater than, equal to, or less than another reference pattern B. In addition to chips that perform only the equality comparison, there are also several arithmetic magnitude comparators, which have outputs capable of simultaneously showing the values of the conditions A < B, A = B, and A > B. A common MSI chip of this type is the 74LS85 Four-Bit Magnitude Comparator.
This chip has three status inputs that permit several chips to be cascaded so as to yield comparisons of multiples of 4 bits. FIG. 17 contains the arrangement of 74LS85 comparators to accomplish a comparison of 8-bit quantities P and Q. The status outputs of a comparator stage connect to the corresponding status inputs of the next most significant comparator. The results of the final comparison are available as outputs of the most significant stage. It is necessary to pass to the least significant chip the information that the previous (nonexistent) comparison showed equality; this is done by asserting T (a high voltage) on the A =B.IN pin, and F on the other two.
There are several diagrammatic conventions in FIG. 17. To avoid cluttering functional diagrams, we often show a group of similar signal lines as a single line with a numbered slash across it. The notation for inputs Q7.H, Q6.H, Q5.H, and Q4.H appears as Q7-Q4.H with a "~" mark on the wire. FIG. 17 also contains three other similarly collected groups of inputs. This use of the numbered slash is a widely accepted convention; the numbered slash has nothing to do with inversion.
FIG. 17 forced us to make a choice. We usually desire that signals move toward the right in a circuit diagram, with an output on the left feeding inputs to the right. We also usually wish for the least significant part of numerical information to be on the right and the more significant parts on the left. In this figure, variables Q7-Q0 and P7-P0 represent numbers. We cannot easily accommodate both these goals in the diagram without creating a nightmare of lines, so we usually choose to show the numbers in their customary order rather than adhere to the convention of rightward-moving signals. In practice you will encounter both conventions.
Since FIG. 17 is the first instance of this drafting custom in the book, we have placed arrows on all the signal lines to show the direction of the signals' travel. Although we frequently use arrows in high-level functional diagrams, in most instances we would not use such arrows on an actual circuit diagram; the chip's nomenclature shows which pins are inputs and which are outputs.
A Universal Logic Circuit
We have gates for implementing the specific logic operations AND, OR, EOR, and so on. These gates are useful when we know at the time we design what logic we must implement in a given circuit. But in many applications we must perform various logic operations on a set of inputs, based on command information that is not available when we are designing. The best example is the digital computer, which must be designed to meet the requirements of any of its set of instructions. Just as we may select an input with a multiplexer, so must we be able to select a logic operation with a suitable circuit.
Let the inputs to this circuit be A and B, and the output Z. To select the particular logic operation, we must have some control inputs Si. FIG. 18 shows this black box. We may require that the black box be able to perform any possible Boolean logic function of its two inputs. We routinely use several of these logic functions: AND, OR, NOT, EOR, and COINCIDENCE. As we mentioned in Section 2, there are 16 functions of two variables. They are enumerated in Table 1. Some are already familiar:
Z1 = A·B, Z7 = A +B, Z10 = B
Z6 = A + B, Z9 = A0B Z12 = A
TABLE 1 LOGIC FUNCTIONS OF TWO VARIABLES
There are some others in the table that at first sight appear to be uninteresting but are in fact useful:
Z0 = F Z3 =A Z5 = B Z15 = T
FIG. 18. Inputs and output for the universal logic circuit.
If we can produce such a comprehensive black box, we will have a circuit that can: (a) Ignore both inputs and produce a fixed FALSE or TRUE output (Z0, Z15). (b) Pass input A or input B through the circuit unchanged (Z3, Z5). (c) Perform our important logic functions (Z1, Z6, Z7, Z9, Z10, Z12). (d) Perform the remaining functions of two variables (Z2, Z4, Z8, Z11, Z13, Z14). These last operations include the NAND and NOR logic functions and four variations of the logical implication function that play no important role in our study of digital design but which we list for completeness.
You will see later that such a general-purpose device is a "natural" at the heart of the digital computer. Computers usually operate on two numbers to produce a result. Not only could this device perform useful logic operations upon two inputs, but it could transmit either input, unaltered or inverted. In addition, it could be a source of T and F bit values.
Many designs for producing the 16 Boolean functions are known, but from our viewpoint the most elegant is a single 4-input multiplexer. To produce a function, our circuit must receive a 4-bit code specifying the particular function Z1. The obvious code values are 0 to 15, corresponding to ZO through Z15. Call the code Z.CODE, with the code bits designated Z.CODE0 through Z.CODE3.
Notice, in Table 3-1, how the definition of each function Z1 is exactly the binary representation of the corresponding Z.CODE. In an unusual interpretation of the multiplexer in its table-lookup role, we may use the "data" variables A and B as the select inputs of the mux, and feed the function-specifying code Z.CODE into the data inputs:
Thus we may produce all 16 Boolean functions of two variables with one-half of a 74LS153 Multiplexer chip. This is tight design! The universal logic circuit is elegant, but it is capable of performing logic operations only. If it is to be used as the heart of a computer, it should also be able to perform arithmetic operations. Let us leave our universal logic circuit for a moment and discuss the structure of circuits that can perform arithmetic on binary numbers. Later we will consider circuits that can perform both logic and arithmetic. NEXT>>
PREV. | NEXT
Related Articles -- Top of Page -- Home