devices the techniques were tailored to gate networks of the type described above. The term gate was already
in use in the forties to denote the logical elements discussed earlier.
There are very many good references on Boolean algebra and we may quote only a selected few of them.
Suffice it to mention the texts by Hill and Peterson [1974], Kohavi [1978], and Hohn [1966]. These books give
a sufficiently rigorous formulation of the subject, tailored to the analysis and the design of combinational
networks. In addition, like most of the earlier books, Hohn’s and Kohavi’s texts also contain a discussion of
the Boolean techniques used in connection with relay circuits. (Some of the more recent works completely
omit this topic, which has been but totally overshadowed by the impressive development of electronic networks.)
The reader interested in studying the relation of switching algebra to Boolean algebras in general is referred to
Preparata and Yeh [1973] for an elementary introduction.
Defining Terms
Boolean algebra: The algebra of logical values enabling the logical designer to obtain expressions for digital
circuits.
Boolean expressions: Expressions of logical variables constructed using the connectives and, or, and not.
Boolean functions: Common designations of binary functions of binary variables.
Combinational logic:Interconnections of memory-free digital elements.
Switching theory:The theory of digital circuits viewed as interconnections of elements whose output can
switch between the logical values of 0 and 1.
Related Topic
79.2 Logic Gates (IC)
References
G. Boole, An Investigation of the Laws of Thought, New York: Dover Publication, 1954.
F.J. Hill and G.R. Peterson, Introduction to Switching Theory and Logical Design, New York: Wiley, 1974.
F.E. Hohn, Applied Boolean Algebra, New York: Macmillan, 1966.
Z. Kohavi, Switching and Finite Automata Theory, New York: McGraw-Hill, 1978.
F.P. Preparata and R.T. Yeh, Introduction to Discrete Structures, Reading, Mass.: Addison-Wesley, 1973.
C.E. Shannon, “A symbolic analysis of relay and switching circuits,” Trans. AIEE, vol. 57, pp. 713–723, 1938.
81.2 Logic Circuits
Richard S. Sandige
Section 81.2 deals with two-state (high or low, 1 or 0, or true or false) logic circuits. Two-state logic circuits
can be broken down into two major types of circuits: combinational logic circuits and sequential logic circuits.
By definition, the external output signals of combinational logic circuits are totally dependent on the external
input signals applied to the circuit. In contrast, the output signals of sequential logic circuits are dependent on
all or part of the present state output signals of the circuit that are fed back as input signals to the circuit as
well as any external input signals if they should exist. Sequential logic circuits can be subdivided into synchro-
nous or clock-mode circuits and asynchronous circuits. Asynchronous circuits can be further divided into
fundamental-mode circuits and pulse-mode circuits. Fig. 81.15 is the graphic classification of logic circuits.
Combinational Logic Circuits
The block diagram in Fig. 81.16 illustrates the model for combinational logic circuits. The logic elements inside
the block entitled combinational logic circuit can be any configuration of two-state logic elements such that the
output signals are totally dependent on the input signals to the circuit as indicated by the functional relationships
in the figure.
? 2000 by CRC Press LLC
The logic elements can be anything from relays with their slow on and off switching action to modern off-
the-shelf integrated circuit (IC) transistor switches with their extremely fast switching action. Modern ICs exist
in various technologies and circuit configurations such as transistor-transistor logic (TTL), complementary
metal-oxide semiconductor (CMOS), emitter-coupled logic (ECL), and integrated injection logic (I
2
L), just to
name a few.
The delays in the outputs of the model in Fig. 81.16 represent lumped delays, that is, worst-case delays
through the longest delay path from the inputs to each respective output of the combinational logic circuit.
FIGURE 81.15 Graphic classification of logic circuits.
FIGURE 81.16 Block diagram model for combinational logic circuits.
? 2000 by CRC Press LLC
The lumped delays provide an approximate measure of circuit speed or settling time (the time it takes an output
signal to become stable after the input signals have become stable).
Figure 81.17 illustrates the gate-level method (random logic method) of implementing a binary to seven-
segment hexadecimal character generator suitable for driving a seven-segment common cathode LED display
like the one in Fig. 81.18.
The propagation delays of logic circuits are seldom shown on logic circuit diagrams; however, these delays
are inherent in each logic element and must be considered in systems designs. This gate-level combinational
logic circuit converts the binary input code 0000 though 1111 represented on the signal inputs D(MSB) C B
A(LSB) to the binary code on the signal outputs OA through OG. These outputs generate the hexadecimal
characters 0 through F when applied to a seven-segment common cathode LED display. Each of the signal lines
D, , through A, must be capable of driving the number of gate inputs shown in the brackets (fan-out
requirement) to both the high-level and low-level required voltages. The output equations for the circuit in
Fig. 81.17 are the minimum sum of products (SOP) equations for the 1’s of the functions OA though OG,
respectively, represented by the truth table in Table 81.4.
A more efficient way (in terms of package count) to implement the same combinational logic function would
be to use a medium-scale integration (MSI) 4- to 16-1ine decoder with gates as illustrated in Fig. 81.19. The
tildes are used as in-line symbols for the logical complements of D0 through D15 as recommended by IEEE.
FIGURE 81.17Gate-level logic circuit for binary to seven-segment hexadecimal character generator.
D A
? 2000 by CRC Press LLC
The decoder circuit in Fig. 81.19 requires only 8 IC packages compared to the gate-level circuit in Fig. 81.17
which requires 18 IC packages. Functionally, both circuits perform the same. The output equations for the
circuit in Fig. 81.19 are the canonical or standard SOP equations for the 0’s of the functions OA though OG,
respectively, represented by the truth table (Table 81.4). The gates shown in Fig. 81.19 with more than four
inputs are eight-input NAND gates with each unused input tied to V
CC
via a pull-up resistor (not shown on
the logic diagram).
An even more efficient way to implement the same combinational logic function would be to utilize part of
a simple programmable read only memory (PROM) circuit such as the 27S19 fuse programmable PROM in
Fig. 81.20. An equivalent architectural gate structure for a portion of the PROM is shown in Fig. 81.21. The
X’s in Fig. 81.21 represent fuses that are left intact after programming the device. The code for programming
the PROM or generating the truth table of the function can be read either from the truth table (Table 81.4) or
directly from each line of the circuit diagram in Fig. 81.21 (expressed in hexadecimal: 7E, 30, 6D, 79, 33, 5B,
5F, 70, 7F, 7B, 77, 1F, 4E, 3D, 4F, and 47) beginning with the first line, which represents binary input 0000,
FIGURE 81.18Seven-segment common cathode LED display.
TABLE 81.4Truth Table for Binary to Seven-Segment Hexadecimal Character Generator
Binary Inputs Seven-Segment Outputs
D C B A OA OB OC OD OE OF OG Displayed Characters
00001111110 0
00010110000 1
00101101101 2
00111111001 3
01000110011 4
01011011011 5
01101011111 6
01111110000 7
10001111111 8
10011111011 9
10101110111 A
10110011111 b
11001001110 C
11010111101 d
11101001111 E
11111000111 F
? 2000 by CRC Press LLC
down to the last line, which represents binary input 1111. The PROM solution for the combinational logic
circuit is optimum since it represents a maximum efficiency by requiring only a single IC package.
Programmable logic devices (PLDs), such as PROM, programmable array logic (PAL), and programmable
logic array (PLA) devices, are fast becoming the preferred devices when implementing combinational as well
as sequential logic circuits. This is true because these devices (a) use
less real estate on a pc board, (b) shorten design time, (c) allow design
changes to be made more easily, and (d) improve reliability because
of fewer connections.
Figure 81.22 shows a PAL16L8 implementation for the binary to
seven-segment hexadecimal character generator that also requires just a
single IC package. The fuse map for this design was obtained using the
software program PLDesigner-XL. Karnaugh maps are handy tools that
allow a designer to easily obtain minimum SOP equations for either the
1’s or 0’s of Boolean functions of up to four or five variables; however,
there are a host of commercially available software programs that pro-
vide not only Boolean reduction but also equation simulation and fuse
map generation for PLDs and field programmable gate arrays (FPGAs).
PLDesigner-XL (trademark of Minc, Incorporated) is an example of
a premier commercial software package available for logic synthesis
for PLDs and FPGAs, for both combinational logic and sequential
logic circuits.
FIGURE 81.19Decoder logic circuit for binary to seven-segment hexadecimal character generator.
FIGURE 81.20PROM implementation
for binary to seven-segment hexadecimal
character generator.
? 2000 by CRC Press LLC
Sequential Logic Circuits
A sequential logic circuit is a circuit that has feedback such that the output signals of the circuit are functions
of all or part of the present state output signals of the circuit in addition to any external input signals to the
circuit. The vast majority of sequential logic circuits designed for industrial applications are synchronous or
clock-mode circuits.
Synchronous Sequential Logic Circuits
Synchronous sequential logic circuits change states only at the rising or falling edge of the synchronous clock
signal. To allow proper circuit operation, any external input signals to the synchronous sequential logic circuit
must generate excitation inputs that occur with the proper setup time (t
su
) and hold time (t
h
) requirements
relative to the designated clock edge for the memory elements being used. Synchronous or clock-mode sequen-
tial logic circuits depend on the present state of memory devices called bistables or flip-flops (asynchronous
sequential logic circuits) that are driven by a system clock as illustrated by the synchronous sequential logic
circuit in Fig. 81.23.
With the availability of edge-triggered D flip-flops and edge-triggered J-K flip-flops in IC packages, a designer
can choose which flip-flop type to use as the memory devices in the memory section of a synchronous sequential
logic circuit. Many designers prefer to design with edge-triggered D flip-flops rather than edge-triggered J-K
flip-flops because D flip-flops are (a) more cost efficient, (b) easier to design with, and (c) more convenient
since many of the available PAL devices incorporate edge-triggered D flip-flops in the output section of their
architectures. PAL devices that contain flip-flops in their output section are referred to as registered PALs (or,
in general, registered PLDs). The synchronous sequential logic circuit shown in Fig. 81.24 using edge-triggered
D flip-flops functionally performs the same as the circuit in Fig. 81.23.
FIGURE 81.21PROM logic circuit.
? 2000 by CRC Press LLC
Notice that in general more combinational logic gates will be required for D flip-flop implementations
compared to J-K flip-flop implementations of the same synchronous sequential function. Using a registered
PAL such as a PAL16RP4A would only require one IC package to implement the circuit in Fig. 81.24. The
PAL16RP4A has four edge-triggered D flip-flops in its output section, of which only two are required for this design.
Generally speaking, synchronous sequential logic circuits can be designed much more easily (considering
design time as the criteria) than fundamental-mode asynchronous sequential logic circuits. With a system clock
and edge-triggered flip-flops, a designer does not have to worry about hazards or glitches (momentary error
conditions that occur at the outputs of combinational logic circuits), since outputs are allowed to become stable
before the next clock edge occurs. Thus, sequential logic circuit designs allow the use of combinational hazardous
circuits as well as the use of arbitrary state assignments, provided the resulting combinational logic gate count
or package count is acceptable.
FIGURE 81.22PAL16L8 implementation for the binary to seven-segment hexadecimal character generator. (Source: PAL
Device Data Book, Advanced Micro Devices, Sunnyvale, Calif., 1988, p. 5–46.)
? 2000 by CRC Press LLC
Asynchronous Sequential Logic Circuits
Asynchronous sequential logic circuits may change states any time a single input signal occurs (either a level
change for a fundamental mode circuit or a pulse for a pulse mode circuit). No other input signal change
(either level change or pulse) is allowed until the circuit reaches a stable internal state. Latches and edge-
triggered flip-flops are asynchronous sequential logic circuits and must be designed with care by utilizing
hazard-free combinational logic circuits and race-free or critical race-free state assignments. Both hazards and
race conditions interfere with the proper operation of asynchronous logic circuits. The gated D latch circuit
FIGURE 81.23Synchronous sequential logic circuit using positive edge-triggered J-K flip-flops.
FIGURE 81.24Synchronous sequential logic circuit using positive edge-triggered D flip-flops.
FIGURE 81.25Fundamental-mode asynchronous sequential logic circuit.
? 2000 by CRC Press LLC
illustrated in Fig. 81.25 is an example of a fundamental-mode asynchronous sequential logic circuit that is used
extensively in microprocessor systems for the temporary storage of data.
Quad, octal, 9-bit, and 10-bit transparent latches are readily available as off-the-shelf IC devices for these
types of applications. For proper asynchronous circuit operation, the signal applied to the data input D of the
fundamental-mode circuit in Fig. 81.25 must meet a minimum setup time and hold time requirement relative
to the control input C, changing the latch to the memory mode when C goes to 0. This is a basic requirement
for asynchronous circuits with level inputs, i.e., only one input signal is allowed to change at one time. Another
restriction requires letting the circuit reach a stable state before allowing the next input signal to change.
An example of a reliable pulse-mode asynchronous sequential logic circuit is shown in Fig. 81.26. While the
inputs to asynchronous fundamental-mode circuits are logic levels, the inputs to asynchronous pulse-mode
circuits are pulses. Pulse-mode circuits have the restriction that the maximum pulse width of any input pulse
must be sufficiently narrow such that an input pulse is no longer present when the new present state output
signal becomes available. The purpose of the double-rank circuit in Fig. 81.26 is to ensure that the maximum
pulse width requirement is easily met, since the output is not fed back until the input pulse is removed, i.e.,
goes low or goes to logic 0. The input signals to pulse-mode circuits must also meet the following restrictions:
(a) only one input pulse may be applied at one time, (b) the circuit must be allowed to reach a new stable state
before applying the next input pulse, and (c) the minimum pulse width of an input pulse is determined by the
time it takes to change the slowest flip-flop used in the circuit to a new stable state.
Defining Terms
Asynchronous circuit:A sequential logic circuit without a system clock.
Combinational logic circuit:A circuit with external output signal(s) that are totally dependent on the external
input signals applied to the circuit.
Fan-out requirement:The maximum number of loads a device output can drive and still provide dependable
1 and 0 logic levels.
Hazard or glitch:A momentary output error that occurs in a logic circuit because of input signal propagation
along different delay paths in the circuit.
Hexadecimal:The name of the number system with a base or radix of 16 with the usual symbols of 0 …
9,A,B,C,D,E,F.
Medium-scale integration:A single packaged IC device with 12 to 99 gate-equivalent circuits.
Race-free state assignment:A state assignment made for asynchronous sequential logic circuits such that no
more than a one-bit change occurs between each stable state transition, thus preventing possible critical races.
Sequential logic circuit:A circuit with output signals that are dependent on all or part of the present state
output signals fed back as input signals as well as any external input signals if they should exist.
Sum of products (SOP): A standard form for writing a Boolean equation that contains product terms (input
variables or signal names either complemented or uncomplemented ANDed together) that are logically
summed (ORed together).
Synchronous or clock-mode circuit:A sequential logic circuit that is synchronized with a system clock.
FIGURE 81.26Double-rank pulse-mode asynchronous sequential logic circuit.
? 2000 by CRC Press LLC
Related Topic
79.2 Logic Gates (IC)
References
Advanced Micro Devices, PAL Device Data Book, Sunnyvale, Calif.: Advanced Micro Devices, Inc., 1988.
ANSI/IEEE Std 91-1984, IEEE Standard Graphic Symbols for Logic Functions, New York: The Institute of Electrical
and Electronics Engineers, 1984.
ANSI/IEEE Std 991-1986, IEEE Standard for Logic Circuit Diagrams, New York: The Institute of Electrical and
Electronics Engineers, 1986.
K.J. Breeding, Digital Design Fundamentals, 2nd ed., Englewood Cliffs, N.J.: Prentice-Hall, 1992.
F.J. Hill and G.R. Peterson, Introduction to Switching Theory & Logical Design, 3rd ed., New York: John Wiley,
1981.
M.M. Mano, Digital Design, 2nd ed., Englewood Cliffs, N.J.: Prentice-Hall, 1991.
E.J. McCluskey, Logic Design Principles, Englewood Cliffs, N.J.: Prentice-Hall, 1986.
Minc, PLDesigner-XL, The Next Generation in Programmable Logic Synthesis, Version 3.5, User’s Guide, Colorado
Springs: Minc, Incorporated, 1996.
R.S. Sandige, Modern Digital Design, New York: McGraw-Hill, 1990.
Further Information
The monthly magazine IEEE Journal on Solid-State Circuits presents papers discussing logic circuits, for example,
“Automating the Design of Asynchronous Sequential Logic Circuits,” in its March 1991 issue, pp. 364–370.
The monthly magazine IEEE Transactions on Computers presents papers discussing logic circuits, for example,
“Concurrent Logic Programming as a Hardware Descriptive Tool,” in its January 1990 issue, pp. 72–88.
Also, the monthly magazine Electronics and Wireless World presents articles discussing logic circuits, for
example, “DIY PLD,” in its June 1989 issue, pp. 578–581.
81.3 Registers and Their Applications
B.R. Bannister and D.G. Whitehead
The basic building block of any register is the flip-flop, but, just as there are several types of flip-flop, there are
many different register arrangements, and an idea of the vast range and their interrelationships is given in Fig. 81.27.
The simplest type of flip-flop is the set-reset flip-flop which can be constructed simply by cross-connecting
two NAND/NOR gates. This forms an asynchronous flip-flop in which the set or reset signal determines both
what the flip-flop is to do and when it is to operate. In fact, if a state change is required, the flip-flop begins
to change state as soon as the input change is detected. This flip-flop is therefore useful as a latch which is used
to detect when some event has occurred, and is often referred to as a flag since it indicates to other circuitry
that the event has occurred and remains set until the controlling circuitry responds by resetting it.
Flags are widely used in digital systems to indicate a change of state and all microprocessors have a set of
flags which, among other things, are used in deciding whether a program branch should or should not be
made. Thus the 8086 family of microprocessors [Intel, 1989], for example, has a group of nine flags—three
control flags used to control particular modes of operation of the processor and six status flags indicating
whether certain conditions have resulted from the most recent arithmetic or logical instruction: zero, carry,
auxiliary carry, overflow, sign and parity. For convenience, although they all act independently, these flags are
grouped together into what is known as the flag register or program status word register.
Gated Registers
The more conventional meaning of register applies to a collection of identical flip-flops which are activated as
a set rather than individually. They are, in general, available as four-bit or eight-bit and are used in multiples
of eight bits in most cases. It is the number of flip-flops in each register that determines the width of the data
? 2000 by CRC Press LLC
bus in a microprocessor or other bus-based system and that is used to describe the microprocessor. The Z80,
for instance, is said to be an eight-bit processor, indicating that the working registers are eight bits wide. The
bit values in the register may represent a numerical value in standard fixed point binary, floating point, or some
other coded form. Alternatively, they may indicate some logical pattern such as the settings of switches used
in an industrial controller.
In order to control when the flip-flops set or reset we must make use of synchronous flip-flops, leaving the
D or J-K inputs to determine what the flip-flop is to do logically, that is to set or reset. In all bus-organized
systems it is necessary to control when the data held in the register is fed on to the output bus. This is usually
achieved by means of three-state (3S) gates at the register outputs which are disabled, that is, set to their high-
impedance state, until the data is required.
A multi-register, bus-structured digital system will have the nth bit of each register connected to bit n of the
data bus at both the input and output of the register. In order to transfer data from one register to another,
or, more strictly, to transfer a copy of the contents of one register to another register, the output gates of the
source register must be enabled so that the data is fed on to the bus. This data becomes available at the inputs
of all registers and is latched in under the control of the appropriate input signals. It is important in the design
of the sequencing circuitry that only one set of register output gates can be enabled at any time, although the
data can be latched into as many registers as required.
The signal controlling the input to the register is applied to all flip-flops simultaneously and its action depends
on the type of flip-flop used. Edge-triggered flip-flops set or reset according to the value on the data inputs at
the time the control signal changes. These registers are sometimes known as staticizers. After the few nanosec-
onds required for the flip-flops to settle to their new values, the register content is available at the output gating.
The correct operation of the circuitry depends upon certain timing criteria being satisfied and minimum values
are quoted by the manufacturers. Each is the smallest time above which the device is guaranteed to operate
correctly, but in practice the device probably functions satisfactorily with smaller time intervals on at least some
of the parameters. The main timing constraints occur at the inputs to the flip-flops and are illustrated in
Fig. 81.28. The interval preceding the active transition of the control input is the setup time, t
su
, during which
the data signal must be held steady; t
h
is the hold time and is the interval during which the data signal must
be retained following the active transition of the control input; t
w
is a minimum pulse width indication which
applies to the control inputs such as the clock, reset, and clear. The clock pulse width is usually quoted both for
the high state and for the low and is related to the maximum clocking frequency of the flip-flops used in the register.
FIGURE 81.27The register family.
? 2000 by CRC Press LLC
An alternative flip-flop is the transparent latch, an interesting development of the simple latch. When enabled
by a control signal, C, by setting C high or “1”, the latch becomes a transparent section of the data path and
the data value at the input simply reappears at the output. When the control signal disables the latch, that is
C is low or “0”, however, the last value applied to the latch is “frozen” and held until the control signal is taken
high again. The 74LS373, Fig. 81.29(a), consists of eight transparent latches with a common control input
labeled ENABLE. The 74LS374, Fig. 81.29(b), is a typical eight-bit register using positive edge-triggering for
all flip-flops. It includes 3S output gates designed specifically for driving highly capacitive loads, such as are
found in bus-organized systems, and which respond to an output control signal operating quite independently
of the flip-flops. Typical minimum timing figures for the 74LS373 and 74LS374 are shown in Fig. 81.29(c) and
the waveforms occurring for the two different types of register are illustrated in Fig. 81.29(d).
An extended form of transparent operation is provided in addressable latches such as the eight-bit 74LS259.
As well as being able to store successive bits arriving at a single input, D, in the eight addressable latches, using
a three-bit address, any latch can be selected for output so that the device can also act as a 1-of-8 decoder or
demultiplexer. Four modes of operation are possible under the control of the enable and clear inputs. In the
addressable latch mode the single-addressed latch acts transparently, with all other latches retaining their
previous states. When in the memory mode all latches retain their previous states and are unaffected by address
or data inputs. In the decode mode the output of the addressed latch follows the level at the D input, and in
the clear mode all outputs are set low.
Shift Registers
There are essentially two modes of operation for a register, either serial or parallel, and those we have considered
so far have operated in parallel mode. Parallel operation affects the entire group of bits held in the register
during a single clock pulse. In serial operation data bits are inputted (or outputted) sequentially to (or from)
the register, one bit for every clock pulse.
A register which has the facility to move the stored bits one place at a time left or right under the control
of the clock pulse is called a shift register (Fig. 81.30).
Shift registers are normally implemented by means of D, S-R or J-K flip-flops. As an example, the 74LS165A
is shown (Fig. 81.31), consisting of eight S-R-type flip-flops with clock, clock inhibit, and shift/load control
inputs. The different functions are tabulated in Fig. 81.32.
Data presented to the eight separate inputs is loaded into the register in parallel when the shift/load input
is taken low. Shifting occurs when the shift/load input is high and the clock pulse is applied, the action taking
place on the low-to-high transition of the clock pulse. Registers are available which switch on the other clock
edge. For example, the 74LS295A, which is a four-bit shift register with serial and parallel operating modes,
carries out all data transfers and shifting operations on the high-to-low clock transition. This device also
provides 3S operation. Selection of the mode of operation is carried out by suitable combinations of the MODE
SELECT inputs.
Large-capacity shift registers make use of charge-coupled devices (CCD). These are MOS devices in which
data bits are stored dynamically as charge between gate and substrate on what is effectively a distributed multi-gate
FIGURE 81.28Control timing parameters.
? 2000 by CRC Press LLC
MOS transistor. Consider the diagram (Fig. 81.33) depicting a section through part of an n-type substrate
which has a series of very closely spaced gate electrodes separating the drain and source of a “stretched” MOS
transistor. Using gate “G” and the first storage gate a charge packet of electrons can be introduced into the
structure. The overlapping clock pulses allow this charge packet to be moved along the array. At the drain the
presence of a charge under the final storage gate is detected by a change in current. Steady-state operation of
this type of register is not possible since thermally generated carriers (leakage current) will ultimately cause
stationary charge, held beneath a storage gate, to leak away. The result is a minimum operating shift frequency
of around 20 kHz. The maximum length of the CCD shift register is limited by the charge transfer efficiency;
each time the charge packet is transferred between storage gates a fraction is lost. The transfer efficiency also
FIGURE 81.29(a) 74LS373 and (b) 74LS374. (c) Typical minimum timing values and (d) I/O waveforms for the
￠LS373/374.
? 2000 by CRC Press LLC
reduces as the frequency increases, limiting the maximum shift frequency to typically 10 MHz for a 256-bit
register. The CCD register is structurally a very simple device and large storage arrays are possible. Devices are
available operating from two-, three- and four-phase clocks.
Transfer of data between registers is an important operation in all digital systems and sometimes the data
may be modified during the transfer. For example, in an addition routine the contents of one register will be
added to the contents of another, the resulting sum then being returned to one of the two registers. Parallel or
serial addition could be used, but the example shown in Fig. 81.34 is that of a serial adder. The registers could
each be made up of two 74LS295A devices as previously described. The data to be added is transferred to the
two shifting registers, A, B, using parallel loading of data into the registers, carried out prior to the application
of the shift clock pulses shown.
On the falling edge of each clock pulse the data is right-shifted one place. The resultant sum of the two bits
plus any carry bit is, on the same clock edge, entered back into register A. The D-type flip-flop is used to delay
the carry bit until the next add time: Data entered at D does not appear at Q until the falling edge of the clock
pulse has occurred, and at such time it is, therefore, too late to modify the previous addition. At the end of the
FIGURE 81.30Shift register operation.
FIGURE 81.31The 74LS165A shift register. (Source: TTL Data Book, Vol. 1, Texas Instruments, Inc.)
FIGURE 81.32Operating modes for 74LS295A.
? 2000 by CRC Press LLC
addition process, when all the data bits have been shifted through the registers, register A contains the sum,
and register B is unchanged.
A single shift register can be arranged to provide its own input by means of feedback circuits, and its action
then becomes autonomous, since the only external signal required is the clock signal. There are only a finite
number of states of the feedback shift register (FSR), and the output sequence from the register will, therefore,
repeat with a cycle length not greater than 2
n
bits, where n is the number of flip-flops in the register. This
property can be used to create a counter known as a Johnson counter in which the shift register has the J and
K inputs of the first stage fed directly from the Q￠ and Q outputs, respectively, of the last stage. This simple
form of feedback leads to the name twisted-ring counter, and the result is the generation of a creeping or stepping
code with 2n different states. This form of counter is convenient only when the count is small, as the number
of flip-flops quickly becomes excessive, but is ideal for a simple decade counter. Unlike standard binary decade
counters, the Johnson decade counter requires five flip-flops but no additional feedback circuitry. Gating needed
to detect specific settings of the counter is also very simple [Bannister and Whitehead, 1987].
Another set of sequences is obtained if the feedback arrangements are restricted to the use of exclusive-OR,
that is modulo-2 functions, and, by correct choice of function, the linear feedback shift register (LFSR) so
formed generates a maximal length sequence, or m-sequence. A maximal length sequence has a length of 2
n
– 1
bits (the all-zeros state is not included, since the mod-2 feedback would not allow any escape from that state,
so the sequence has a 0 missing) with useful properties of repeatable randomness and is, therefore, described
as a pseudorandom binary sequence (PRBS). The number of maximal length sequences for a register of length
n, and the feedback arrangements to achieve them, are not at all obvious, but have been worked out for a large
number of cases [Messina, 1972]. A 4-bit LFSR will produce only one maximal length sequence, but a 10-bit
register can produce 30 distinct m-sequences, and a 30-bit register produces no less than 8,910,000 distinct
sequences!
Shift registers can be used in parallel to form a first-in, first-out (FIFO) memory. These are typically 128 ′
8-bit register memories with independent input and output buses. At the input port, data is controlled by a
FIGURE 81.33The CCD register.
FIGURE 81.34The serial adder using shifting registers.
? 2000 by CRC Press LLC
shift-in clock operating in conjunction with an input ready signal which indicates whether the memory is able
to accept further words or is now full. The data entered is automatically shifted in parallel to the adjacent
memory location if it is empty and as this continues the data words stack up at the output end of the memory.
At the output port, data transfers are controlled by a shift-out clock and its associated output ready signal. The
output ready signal indicates either that a data word is ready to be shifted out or that the memory is now empty.
FIFOs can easily be cascaded to any desired depth and operated in parallel to give any required word length.
This type of memory is widely used in controlling transfers of data between digital subsystems which operate
at different clock rates and is often known as an elastic buffer.
Register Transfer Language
The transfer of data between registers is described using a simple notation termed the register transfer language
or RTL. For data transferred from register A to register B we write: B ? A. The symbol ? is called the transfer
operator. Note that this statement does not indicate how many bits are to be transferred. To define the size of
the register we declare the size thus: A[8], B[16], here defining an 8-bit register and a 16-bit register. If the
action to be taken is the transfer of the most significant bit (7th bit) of register A to the least significant bit
(bit 0) of register B, then we write: B[0] ? A[7]. Usually data is transferred by the control signal or a clock
pulse. If such a signal is designated “C,” then we would describe the action by C: B ? A.
Returning to the serial adder circuit shown earlier, we could describe the register transfers thus:
A[8],B[8],D[1]
C: A[7] ? A[0] % B[0] % D[0], B[7] ? B[0], D[0] ? Carry
Here in the declaration statement we refer to the D-type flip-flop as a single-bit register. Simultaneous processes
are separated by a comma; sequential processes would be separated by a semicolon. The symbol “%” is the
exclusive-or (XOR) operator. Other logical operations include NOT, AND, OR. The AND operation is also
called the masking operation because it can be used to remove (or select) specific sections of data from a register.
Thus the operation A[8] ? A[8] &3CH will result in the most significant two bits and the least significant two
bits of the eight-bit register A being set to zero. Note that 3CH refers to the hexadecimal number 3C, i.e.,
00111100 in binary. Some other terms commonly used are as follows:
D ? A￠ transfer the complement of A to D
A ? A + 1 increment A
A[8:15] ? B[8:15] transfer bits 8 through 15 from B to A
In order to differentiate between arithmetic and logical operations it is usual to represent OR and AND by
~ and ‘. Table 81.5 lists some typical RTL examples that include arithmetic, bit-by-bit logic, shift, rotate, scale
and conditional operations. It is assumed that the three registers are set initially to A = 10110, B = 11000 and
C = 00001.
Input/Output Ports
The working registers provided in microprocessors may be thought of as high-speed extensions to the memories
used for storing programs and data. The random access memories (RAM) themselves are also arrays of registers,
though the form of circuit used differs considerably from the more conventional register. The need to transfer
data in and out of the system has led manufacturers to produce special registers which are further extensions
to the internal memory and are known as input and output ports. One of the simplest of input/output ports
is the Intel 8212 (Fig. 81.35). This has two modes of operation selected by the mode input, MD. With MD at
0 the device acts as an input port and a peripheral unit can enter data on the DI lines by sending a high strobe
? 2000 by CRC Press LLC
signal, STB. When the central processor is ready for the data it selects the port by setting the correct address
bits on the device select inputs. This enables the 3S output buffers and data is routed to the processor data bus
via the DO lines. This device also includes a service request flip-flop to generate an interrupt signal to the
processor when the data is ready. In the alternative mode of use, with the mode input at 1, the device select
logic routes data from the processor, now connected to the DI inputs, so the 8212 acts as an output port. The
data is immediately available to the peripheral unit on the DO lines, as the 3S output buffers are permanently
enabled. A more sophisticated range of input and output facilities is provided by most microprocessor manu-
facturers in the form of programmable input/output ports or peripheral interfaces. These are special registers
with appropriate buffers and additional built-in control and status registers to facilitate proper system operation.
The majority of input/output devices use 3S bidirectional buffers which switch to the high-impedance state
when not enabled. Some input/output ports, however, such as the 8051 family of microcontrollers and deriv-
atives, are provided with quasi-bidirectional ports. In this construction, each port pin has an internal pull-up
transistor, as shown in Fig. 81.36. For the port pin to be operative as an input the port latch must contain a 1,
so that the output FET driver is turned off. (All port latches in the 8051 are set by the reset function.) Under
this condition, the pin voltage is pulled high but can be taken low by an external signal when required. These
inputs can, therefore, be driven in a normal way by TTL and MOS circuits and can also cope with open-collector
or open-drain circuits using the pull-up transistors as load resistors.
Yet more flexible capabilities are provided in the Rockwell 6522 versatile interface adapter (VIA), which, in
addition to two 8-bit bidirectional input/output ports, contains two 16-bit programmable timer/counters and
TABLE 81.5Typical RTL Examples
Type of Operation Meaning Register Bits after Operation
General
A
3
? A
2
Bit 2 of A to bit 3 of A = 11110
A
3
? B
4
Bit 4 of B to bit 3 of A = 11110
A
1–3
? B
1–3
Bits 1 through 3 of B to bits 1 through 3 of AA = 11000
A
1,4
? B
1,4
Bits 1 and 4 of B to bits 1 and 4 of A = 10100
A
1–3
? B
z
Groups of bit Z of B to bits 1 through 3 of A = 11000
Arithmetic
B ? 0 Clear B = 00000
A ? B
2
+ C Sum of B and C to AA = 11001
A ? B – C Difference B – C to A = 10111
C ? C + 1 Increment C by 1 C = 00010
Logic
A ? B ‘ C Bit-by-bit AND result of B and C to AA = 00000
A ? B ~ C
4
OR operation result of B with bit 4 of C to A = 11000
C ? Complement C = 11110
B ? + 1 2’s complement of B = 01000
B ? A % C XOR operation result of A and C to B = 10111
Serial
B ? sr B Shift right B one bit B = 01100
B ? sl B Shift right B one bit B = 00110
B ? sr2 B Shift right B two bits B = 00110
B ? rr B Rotate right B one bit B = 01100
B ? rl2 B Rotate left two bits B = 00011
B ? scr B Scale B one bit (shift right with sign bit unchanged) B = 11100
B ? scl B Scale B one bit (shift left with sign bit unchanged) B = 10000
B, C ? sr2 B, C Shift right concatenated B and C two bits B, C = 0011000000
Conditional
IF (B
4
= 1) If bit 4 of B is a 1, then C is cleared C = 00000
C ? 0
IF (B 3 C)If B is greater than or equal to C, then B is cleared and C is set to 1 B = 00000
B ? 0, C
1
? 1 C = 00011
Initial values: A = 10110, B = and C = 00001.
C
B
11000
z
123
? 2000 by CRC Press LLC
a serial data port using a serial-parallel, parallel-serial shift register. (See internal register summary in Fig. 81.37)
Each line of the input/output ports, A and B, can be individually programmed as an input or an output by
means of data direction registers, DDRA and DDRB, respectively, which “mirror” the ports. That is, a bit in the
data direction register set at 1 causes the corresponding bit of the port to act as an output, with a value
determined by the output latch setting. If the bit in the data direction register is set at 0, this causes the
corresponding bit of the port to act as an input, and incoming data may be latched into an internal register
under the control of a special peripheral control line, CA1 or CB1. Data may be written into register bits which
are programmed as inputs but the output signal is unaffected. The input latching may be enabled or disabled.
When reading a peripheral port with the latching disabled, the value read is the current value on the input pin;
with the latching enabled, the value read is the value which existed at the input pin when the active transition
occurred at the control input.
The interval timer/counters can operate in a variety of modes and are retriggerable so that an interrupt signal
is generated either once, when the interval expires, or continually, when subsequent intervals expire. If an
external output is required, it can be either a one-shot output or a squarewave, with the output changing level
each time the interval count is completed. The main timer/counter consists of two 8-bit latches operating in
FIGURE 81.35The Intel 8212. (Source: Microprocessor Component Handbook, Intel Corp.)
? 2000 by CRC Press LLC
conjunction with a 16-bit counter. The latches store the data which is to be loaded into the counter and are
loaded sequentially, since 16 bits are required for the counter but the data bus is only 8 bits wide. When loading
the counter with a specific value, the low-order byte is actually routed to the low-order 8-bit latch. Then, when
the high-order byte is supplied, it is simultaneously written into both the high-order 8-bit latch and the high-
order counter byte, and the low-order byte is also transferred from the latch to the counter. Countdown then
begins on the next clock pulse. This method ensures that the correct 16-bit value is loaded, but it also means
that the current count value can be modified, during counting if required, by writing to the counter, or the
subsequent counts can be modified by writing to the latches.
The shift register performs serial data transfers in and out of a given pin under the control of an internal
modulo-8 counter. When all the necessary control registers and interrupt handling registers are included with
the data direction registers, together with the ports and counters of direct interest to the user, the device requires
a total of 16 registers. These are individually addressed using four register select pins, RS0–RS3.
FIGURE 81.36 Intel 8051 quasi-bidirectional port.
FIGURE 81.37 Internal register summary of Rockwell 6522 VIA. (Source: Synertek Data Book.)
? 2000 by CRC Press LLC
Counters
A register can be loaded with any combination by applying the correct bit pattern to the input data lines and
activating the control line. As with the feedback shift registers, it is then only a small step to arrange that the
register itself provides the input data by use of feedback connections and, if other circuitry is included to
increment the value each time, we have a synchronous counter. The 74L5191 (Fig. 81.38) is a programmable
counter which retains the facility for parallel loading of external data.
Each output may be preset to either level by entering the data at the inputs while the LOAD signal is low.
The outputs change to the new values independently of the count pulses, and counting continues when pulses
FIGURE 81.38The 74LS191 programmable counter.
? 2000 by CRC Press LLC
are applied to the clock input. The master-slave flip-flops are triggered by a low-to-high transition of the clock.
The “terminal count” and “ripple clock” outputs facilitate cascading of several counters. The ripple clock
carry/borrow output signal, RCO, is a pulse equal in length to the clock pulse when the counter overflows or
underflows, that is, when it is incremented from 1111 or decremented from 0000. By using this signal to reload
the value at the data inputs we create a counter of modulus less than 16. Figure 81.39, for example, shows the
arrangement to give a modulo-5 count, by reloading 1011 each time the ripple clock pulse occurs.
Registered ASICs
Developments in application-specific integrated circuits (ASICs) and field-programmable gate arrays (FPGAs)
over recent years have provided digital system designers with a wide range of flexible devices which can be
programmed for the specific job in hand. The vast majority of digital subsystems involve sequential logic to a
greater or lesser extent, and the array manufactures have provided most devices with registers at either input
or output and, sometimes, at both. The Altera EP512 is a good example, and its input structure is shown in Fig. 81.40.
The device has eight programmable inputs in which each may be configured as any one of the following:
Synchronous D-type flip-flop (register)
Asynchronous D-type flip-flop (register)
Synchronous latch
Asynchronous latch
Flowthrough latch (transparent latch)
The internal latch enable (ILE) input carries the clock when synchronous mode is selected, whereas asyn-
chronous mode control signals are generated internally. The EP512 contains 12 macrocells and the input/output
architecture provides each macrocell with over 50 possible configurations. Each I/O unit can be individually
configured for combinatorial or registered output, with the output polarity also programmable. Four different
types of flip-flops (D, T, J-K, S-R) can be implemented in each I/O unit, for either synchronous or asynchronous
operation.
Standard Graphic Symbols
The use of standardized graphical symbols is becoming widespread and the family of registers have their own
coherent set of symbols. Two representative examples are given in Fig. 81.41. As shown, the eight-bit shift
register is designated SGR8. The direction of shift is given by the arrow. The “1D” is part of a notation called
dependency notation. Clock input C1 controls the inputs labeled 1D, of which only one of four is shown. The
reset “R” and the clock are common to all units and are shown as inputs to the common block. The external
reset line carries a polarity symbol which indicates that a low signal must be applied to reset the 4-bit register.
For further details see the References at the end of this section.
FIGURE 81.39Programmable counter giving modulo-5.
? 2000 by CRC Press LLC
Defining Terms
Autonomous operation: Operation of a sequential circuit in which no external signals, other than clock
signals, are applied. The necessary logic inputs are derived internally using feedback circuits.
Input/output port: A form of register designed specifically for data input-output purposes in a bus-oriented
system.
Linear feedback shift register (LFSR): An autonomous feedback shift register in which the feedback function
involves only exclusive-OR operations.
Parallel operation: Data bits on separate lines (often in multiples of eight) are transferred simultaneously
under control of signals common to all lines.
Register: A circuit formed from several identical gated flip-flops or latches and capable of storing several bits
of data.
Serial operation: Data bits on a single line are transferred sequentially under the control of a single signal.
Related Topic
79.3 Bistable Devices
FIGURE 81.40 Input arrangements of the Altera EP512. (Source: Altera Data Book, 1988.)
FIGURE 81.41 Standard graphic symbols. (Source: ANSI/IEEE Std. 91-1984.)
? 2000 by CRC Press LLC
References
Altera, Data Book, 1988.
B.R. Bannister and D.G. Whitehead, Fundamentals of Modern Digital Systems, London: Macmillan, 1987.
IEEE, Standard Graphic Symbols for Logic Functions, ANSI/IEEE Std. 91-1984, New York, 1984.
Intel Corporation, 8086/8088 User’s Manual.
Intel Corporation, Microprocessor and Peripheral Handbook.
E.L. Johnson and M.A. Karim, Digital Design, Boston: PWS Engineering, 1987.
I. Kampel, A Practical Introduction to the New Logic Symbols, Boston: Butterworth, 1985.
A. Messina, “Considerations for non-binary counter applications,” Computer Design, vol. 11, no. 11, Nov. 1972.
Synertek, Data Book.
Texas Instruments, Inc., TTL Data Book.
Further Information
The monthly journal IEEE Transactions on Computers regularly has articles involving the design and application
of registers and associated systems. Further information can be obtained from IEEE Service Center, 445 Hoes
Lane, P.O. Box 1331, Piscataway, NJ 08855-1331.
The IEE Proceedings-E, Computers and Digital Techniques, published bi-monthly by the Institution of Elec-
trical Engineers (Michael Faraday House, Six Hills Way, Stevenage, Herts. SG1 2AY UK), is also a useful source
of information on the application of register devices.
81.4 Programmable Arrays
Martin Bolton
Programmable arrays or programmable logic devices (PLDs) are general-purpose combinational or sequential
digital components whose ultimate function is determined by the designer. They leave the manufacturer in an
unprogrammed state. The configurations of internal switches are fixed after the particular logic function for
the PLD has been prepared and checked using a computer-aided design package appropriate for the PLD family
used. PLDs belong to the family of application-specific integrated circuits (ASICs).
PLDs are manufactured today in most digital integrated circuit technologies—principally CMOS and bipolar
silicon, and gallium arsenide. The programmable switches themselves can be fuses, antifuses, floating-gate
MOSFETs, and RAM cells. The floating-gate devices can usually be erased and reprogrammed, while the RAM-
based devices can be reconfigured dynamically. Most PLDs have to be programmed with the aid of a program-
mer, a unit which is able to deliver the appropriate sequences of programming pulses which configure the PLD’s
arrays of switches in the pattern specified by the user. Some PLDs can be programmed by sending a data stream
to the device in its application environment. This is in-system programming.
There are today two major classes of PLDs—those based on the programmable logic array (PLA) and field-
programmable gate arrays (FPGAs). PLA technology is the oldest and is now restricted to the less complex
circuits. FPGAs, on the other hand, are a more recent technology and are able to implement complex systems
equivalent to networks of several thousand logic gates. The first part of this section will explain the principles
of PLA-based PLDs; the second will introduce the concepts of FPGAs. A final section will briefly cover the
requirements of computer-aided design for programmable logic.
PLA-Structured Devices
It is possible to represent any Boolean function in the form of a sum of products. For example, the expressions
for the outputs of a full adder can be represented as:
SUM = ABC + ABC + ABC + ABC (81.14)
CARRY = AC + AB + BC (81.15)
? 2000 by CRC Press LLC
where A, B, and C are the inputs. The first equation has four product terms, or products; the second has three.
A PLA enables functions expressed in this form to be directly implemented. Each product term is generated
by a gate which can be programmed to form the AND of any subset of the inputs and their complements, while
subsets of products can be summed in a set of programmable OR gates. The programmable gates are constructed
in the form of arrays, with the input lines being orthogonal to the product lines, which are themselves orthogonal
to the output lines, as shown in Fig. 81.42.
This PLA has three inputs, five product terms, and two outputs. Each input is fed into the first array, the
AND array, in true and complement form. This enables any product to be formed. The products are all fed
into the OR array. A cross at an intersection indicates a connection. Notice that some products are used to
contribute to both outputs. The ability to share product terms in this way is an important feature of the PLA.
The product terms which make up the inputs to the OR gate for the SUM output are those given in Eq. (81.14).
The equation for the CARRY output has been modified for use in this PLA which also has programmable
output inversions, indicated by the two exclusive-OR gates. The modified equation for the inverse of CARRY,
which now shares some products with the first function, is
CARRY = ABC + ABC + ABC + ABC (81.16)
Only one new product is now required instead of the three which would have been required without the
double negation of the CARRY function.
A PLA is able to implement any set of combinational logic functions, limited only by the number of inputs,
number of outputs, and number of product terms. A memory also has this ability, but since in this type of
device every combination of inputs is decoded and mapped to a unique set of outputs (via a memory word),
the number of inputs handled cannot be as great as with a PLA of similar physical size, since a PLA does not
decode every input combination. However, where the set of functions to be implemented would require too
many products for a practical PLA, a memory, or a multiple-level network, would have to be used.
An important economy is possible by making use of the fact that for many sets of functions the OR array
is not needed for the sharing of products between outputs. Figure 81.43 shows an example of such a function,
a multiplexer. Such a function can be implemented by a PLA with only an AND array; the OR array has
degenerated into a set of OR gates. The drawback is that the PLA is no longer universal, because a fixed allocation
of products to OR gates has to be chosen. PLAs of this structure have become known as PAL devices or just
PALs. (The term “PAL,” which stands for “programmable array logic,” is a trademark of Advanced Micro
Devices, Inc.). There are many applications where the product term sharing capability of the full PLA is wasted,
and a PAL-based solution is more economical. Also, because there is only one programmable array, the
propagation delay will generally be smaller. Address decoding in microprocessor systems is a very common
application of combinational PAL devices.
FIGURE 81.42A full adder implemented in a PLA with programmable output inversion.
? 2000 by CRC Press LLC
PAL devices are available in a wide variety of sizes. Because there is a fixed allocation of products to outputs
in a simple PAL device, more different types are needed than in the case of PLAs. This limitation has lately
been overcome to some extent in some devices by allowing a limited allocation of products between adjacent outputs.
The flexibility of PAL-structured PLAs can be enhanced by adding controllable three-state output drivers,
as shown in Fig. 81.44. The drivers, controlled by additional product terms (or control terms), allow those pins
to which they are connected to act as either inputs, outputs, or both. This feature allows a single device to be
used in a wider range of applications than would be possible with a device with a fixed allocation of inputs
and outputs. Note also the polarity control, similar to that in the PLA of Fig. 81.42.
The array structures introduced above can be extended by adding clocked flip-flops to the outputs of the
arrays to create general-purpose sequential circuits. A PLA extended in this way is known as a sequencer, whose
generic structure is shown in Fig. 81.45.
The outputs, which are produced by the OR array, feed either directly to the pins (indicated by Ob in the
figure) or to flip-flop inputs (NSa, NSb, and Oa, where “NS” stands for “next state”). The flip-flop outputs are
fed back either into the AND array (PSa and PSb, where “PS” stands for “present state”) or to pins (PSb and
Oa￠). The sequencer’s primary inputs to the PLA AND array are labeled I. Not every sequencer device will have
FIGURE 81.43A four-bit multiplexer implemented in a PAL-structured programmable array.
FIGURE 81.44PAL-structured programmable array with output controls.
? 2000 by CRC Press LLC
all of these paths in its structure. Sequencers are characterized by number of inputs, number of flip-flops, and
number of outputs.
A sequencer such as that shown above allows the direct implementation of a synchronous finite state machine
with both Moore-type (PSb) or the Mealy-type outputs (Oa￠, Ob). The transitions between states in the
behavioral specification of the state machine map directly into the product terms of the sequencer.
PAL-structured arrays are also manufactured with clocked flip-flops attached to the array outputs. These are
often known as registered PALs. State machine descriptions map less naturally into these arrays, but this fact is
of less importance nowadays with the reliance on computer-aided design. Registered PALs find wide use in the
data paths of digital systems, where special-purpose registers, counters, and data routing functions are needed.
Some PAL devices have enhancements such as the exclusive-ORing of outputs to make them more useful in
these applications.
Just as a combinational PAL device can be made more general purpose by the addition of a controlled output,
a sequential one can be generalized by adding programmable macrocells to the array outputs. The output
macrocell of the 22V10 device, the first of the generic PAL devices to be introduced, is shown in Fig. 81.46.
The modes of this macrocell are controllable by two dedicated bits S1 and S0, programmed into the device,
and by a product term controlling the three-state driver. The four possible configurations determined by the
programming of S1 and S0 are:
00: registered output, active low, fed back into array
01: registered output, active high, fed back into array
10: combinational input/output, active low
11: combinational input/output, active high
FIGURE 81.45The structure of a sequencer.
FIGURE 81.46The output macrocell of the 22V10 PAL device.
? 2000 by CRC Press LLC
This form of PAL device is now very widely used and has the advantage that many fewer device types are
needed to handle a range of applications. The fastest devices have combinational propagation delays in the 5-
to 10-ns range and maximum clock frequencies in excess of 100 MHz.
The single-array devices described so far cannot be extended in size indefinitely; it is difficult to efficiently
use large arrays, and the long internal lines required cannot be driven fast enough while maintaining a reasonable
power consumption. For these reasons many PLD architectures based on partitioned arrays and switching
matrices have been introduced. There is not space to elaborate on these here. A number of these designs are
described in Moore and Luk [1991]. However, the most important high-complexity array structure, the FPGA,
is introduced in the next section.
Programmable Gate Arrays (FPGAs)
Gate arrays are semicustom devices based on an array of simple cells selected from a library surrounded by an
interconnection network. In conventional gate array technology, the interconnection pattern is defined by
metallization layers applied at the final stage of manufacture. FPGAs dispense with this final stage by possessing
a fixed interconnection network which includes programmable crosspoint switches, as shown in Fig. 81.47. The
cells, instead of being selected from a library, are generic and have programmable function. The price for doing
this is a lower logic density and higher resistance interconnections, with concomitant effect on speed of
operation. Nevertheless, this disadvantage is more than overcome by the short design turnaround times achiev-
able. A major tradeoff in gate array architecture is between cell complexity and interconnection channel capacity.
This remains the case with FPGAs.
Each logic cell in an FPGA is a small programmable logic block which will usually contain one or more flip-
flops. Typically these cells will have up to ten inputs and a smaller number of outputs.
Computer-Aided Design for Programmable Arrays
As programmable devices become more complex, the capabilities of the computer-aided design support become
more and more important. Small PLA and PAL devices can be programmed from a manually created table,
but this method is error-prone and cannot be recommended. The earliest widely available design aid for
programmable logic was the compiler known as PALASM. This was able to translate the functional specification
of a device, expressed in the form of Boolean equations, into the device programming specification for a PAL
FIGURE 81.47Interconnection structure in an FPGA.
? 2000 by CRC Press LLC
device. It also allowed the function of the device to be simulated. Other manufacturer-specific compilers for
the simpler PLDs have been produced, but nowadays these needs can be served by one of the very capable
Boolean language-based universal compilers.
Recognizing the need for design entry based on schematics, the manufacturers of the more complex PLDs
and FPGAs began to offer this alternative; in fact for FPGAs this is an easier option for the design tool writer.
Schematics for a PLD describe the interconnection of a collection of notional primitive cells.
Converting a language-based description into the layout of an FPGA is an application of logic synthesis, a
technology which has evolved independently of programmable logic design tools, but which has now converged
with them. However, programmable devices offer new problems to the designer of general-purpose design tools
due to the great variety of architectures now existing for the complex devices. Programmable logic design tools
are now becoming more integrated into mainstream computer-aided design systems and are starting to adopt
the same standards, for example use of the VHDL language for specification.
Defining Terms
Field-programmable gate array (FPGA): A PLD which consists of a matrix of programmable cells embedded
in a programmable routing mesh. The combined programming of the cell functions and routing network
define the function of the device.
Programmable array logic (PAL) device: A PLA with no OR array, but instead a fixed set of OR gates into
which are fed sets of product terms. (“PAL” is a trademark of Advanced Micro Devices, Inc.)
Programmable logic array (PLA): A PLD which consists of an AND array forming logical products of the
input literals and an OR array which sums these products to form a set of output functions.
Programmable logic device (PLD): An integrated circuit which is able to implement combinational and/or
sequential digital functions which are defined by the designer and programmed into the device.
Sequencer: A PLA which has a set of flip-flops for storage of outputs which can be fed back into the PLA as
inputs, enabling the implementation of a finite state machine.
Related Topics
25.3 Application-Specific Integrated Circuits ? 81.2 Logic Circuits
References
R.C. Alford, Programmable Logic Designer’s Guide, Indianapolis: H.W. Sams, 1989.
J. Birkner and V. Coli, PAL Handbook, 2nd ed., New York: McGraw-Hill, 1981.
M.J.P. Bolton, Digital Systems Design with Programmable Logic, Wokingham, England: Addison-Wesley, 1990.
G. Bostock, Programmable Logic Handbook, London: Collins, 1987 (also published as Programmable Logic
Devices: Technology and Applications, New York: McGraw-Hill, 1988).
J.D. Broesch, Practical Programmable Circuits: A Guide to PLDs, State Machines and Microcontrollers, San Diego:
Academic Press, 1991.
P.K. Lala, Digital Systems Design with Programmable Logic Devices, Englewood Cliffs, N.J.: Prentice-Hall, 1990.
W.R. Moore and W. Luk, Eds., FPGAs, Abingdon, England: Abingdon EE&CS Books, 1991.
D. Pellerin and M. Holley, Practical Design Using Programmable Logic, Englewood Cliffs, N.J.: Prentice-Hall,
1991.
Further Information
Programmable logic is a fast-moving field, with many vendors continually introducing new devices and
improved versions of existing architectures. The magazines Electronic Design, EDN, and Computer Design carry
regular announcements of new programmable logic hardware and software products and often print articles
illustrating applications and design methods. All of the vendors publish application notes which are the best
source of device-specific design information.
? 2000 by CRC Press LLC
81.5 Arithmetic Logic Units
Bill D. Carroll
Arithmetic logic units (ALUs) are combinational logic circuits that can perform basic arithmetic (addition or
subtraction) or logical (AND, OR, NOT, etc.) operations on two m-bit operands. ALUs may be constructed
from standard integrated circuits or programmable logic devices and are available as single-chip medium-scale
integrated circuits. Integrated ALUs may be cascaded to form longer word lengths than are available in a single
device.
This section covers the design of arithmetic and logic circuits in sufficient detail for the reader to design and
implement basic arithmetic logic units and to understand the operation and utilization of commercial ALU
chips. The reader wanting more details or more in-depth discussion of the subject is referred to the References
and other sources given at the end of the section.
In the material that follows, it is assumed that operands are signed n-bit binary numbers with the left-most
bit representing the sign (0 for positive and 1 for negative) when discussing arithmetic operations/circuits.
Negative numbers will be represented in two’s complement form. Recall that the two’s complement of an n-bit
number A is A￠ + 1 where A￠ represents the bit-wise complement of A. Unsigned n-bit binary numbers are
assumed for logic operations/circuits.
Basic Adders and Subtracters
The basic building block for most arithmetic circuits is the full adder. A full adder is a logic circuit that produces
the two-bit sum (S and C) of three one-bit binary numbers (X, Y, and Z). Table 81.6 shows the truth table and
logic equations of a full adder. A logic symbol and a gate-level realization of a full adder are shown in Fig. 81.48.
The addition of two n-bit binary numbers (X = x
n–1
. . . x
1
x
0
and Y = y
n–1
. . . y
1
y
0
) can be accomplished with
n full adders cascaded as shown in Fig. 81.49. Such a circuit is called a ripple-carry adder since carries produced
TABLE 81.6Full Adder Truth Table and Logic Equations
XYZSC
00000
00110S = XYZ + XY￠Z￠ + X￠YZ￠ + X￠Y￠Z
01010
01101
10010C = XY + XZ = YZ
10101
11001
11111
FIGURE 81.48Full adder.
? 2000 by CRC Press LLC
by lower-order stages must propagate or ripple through the higher-order stages before the addition operation
is complete.
Ripple-carry adders are simple in both operation and structure but are slow since in the worst case (X = 1
. . . 11 and Y = 0 . . . 01) a carry produced in the least significant full adder must propagate through all the
more significant ones. The worst-case add time, t
add
, is given below where t
pd
is the propagation delay introduced
at each stage.
t
add
= nt
pd
This assumes that all addend bits are presented to the adder simultaneously. It is important to note that in the
least significant full adder, t
pd
represents the time to compute c
1
from x
0
and y
0
and in the most significant full
adder the time to compute s
n–1
after c
n–1
is received. In the intermediate stages, t
pd
is the time needed to compute
c
i+l
from c
i
. The propagation delay is approximately equal to the delay of a three-level logic circuit which is
consistent with the realization of a full adder given in Fig. 81.48.
Subtraction can easily be performed by adding the minuend to the negative of the subtrahend. In a two’s
complement number system, X – Y can thus be obtained by computing X + Y￠ + 1. The ripple-carry adder
described above can be easily modified to perform this computation by placing inverters on the Y inputs of
each full adder and by making the carry-in (c
0
) equal to 1. The resulting two’s complement subtracter is shown
in Fig. 81.50.
A device that can perform either addition or subtraction can be built by replacing the inverters in the
subtracter with exclusive-OR gates and using the carry-in (c
0
) as a control signal. The resulting two’s complement
adder/subtracter is shown in Fig. 81.51. The device will function as a ripple-carry adder when c
0
= 0 and as a
two’s complement subtracter when c
0
= 1.
FIGURE 81.49Ripple-carry adder for two n-bit binary numbers.
FIGURE 81.50Two’s complement subtracter.
FIGURE 81.51Two’s complement adder/subtracter.
? 2000 by CRC Press LLC
High-Speed Adders
Several different adder designs have been developed for performing high-speed addition. These include carry
lookahead adders (CLAs), carry-completion adders, conditional-sum adders, and carry-select adders. Carry
lookahead adders have gained wide acceptance in the design of ALUs due to the speed obtained and because
they can be conveniently implemented in integrated circuit form.
This material covers only the carry lookahead approach. However, before beginning that discussion, let’s
briefly explain why fully parallel adders are not feasible. Addition is a combinational process so it is theoretically
possible to construct a 2n-bit “full-adder” that can be realized by a three-level combinational logic circuit and
that can perform addition of two n-bit numbers in the time equal to the delay of the circuit. However, such
circuits are too costly in terms of gate fan-in to be implemented for reasonable values of n. Carry lookahead
is a practical and effective compromise between fully parallel adders and ripple-carry adders. The block diagram
of a four-bit CLA is shown in Fig. 81.52(a).
CLAs are based on the observation that a carry-out (c
i
) of the ith stage of a full adder is produced by either
the propagation of the carry-in (c
i–1
) through the ith stage or the generation of a carry in the ith stage. This
can be seen in the following logic equations for c
i
:
c
i
= x
i–1
y
i–1
+ x
i–1
c
i–1
+ y
i–1
c
i–1
= x
i–1
y
i–1
+ (x
i–1
+ y
i–1
)c
i–1
= g
i–1
+ p
i–1
c
i–1
where g
i
= x
i
y
i
and p
i
= x
i
+ y
i
are the generate and propagate terms, respectively, for stage i for i = 0 to n – 1.
The carry equations for an n-bit adder can be derived by repeatedly applying the above equation. The
following set of equations results for the n = 4 case:
c
1
= g
0
+ p
0
c
0
c
2
= g
1
+ p
1
g
0
+ p
1
p
0
c
0
c
3
= g
2
+ p
2
g
1
+ p
2
p
1
g
0
+ p
2
p
1
p
0
c
0
c
4
= g
3
+ p
3
g
2
+ p
3
p
2
g
1
+ p
3
p
2
p
1
g
0
+ p
3
p
2
p
1
c
0
The carry equations can be realized by three-level combinational logic circuits to form the carry lookahead
logic block shown in Fig. 81.52(a). The sum (s
i
) bits for the ith stage of an adder can be written in terms of g
i
,
p
i
, and c
i
and generated by the logic circuit given in Fig. 81.52(b). This completes the description of the four-
bit CLA.
FIGURE 81.52Carry lookahead adder.
? 2000 by CRC Press LLC
Now let’s examine the add-time, t
add
, for a CLA. Assume that both addends are applied to the CLA simul-
taneously and that c
0
= 0. Also, let t
pd
represent the propagation delay of a three-level logic circuit. There are
two components that contribute to the add time. First, the three-level carry lookahead logic must produce the
carries. This takes t
pd
. Then, the summation unit must produce the final values of the sum bits. This step takes
a time equal to the propagation delay of the exclusive-OR gate in the summation unit which is t
pd
since an
exclusive-OR gate can be realized as a three-level combinational logic circuit. Hence, the add time for a CLA is
t
add
= 2t
pd
The above result indicates that the add time of a CLA is not only much faster than a ripple-carry adder but
is also independent of the length (n) of the addends. Hence, one might conclude that CLAs are the final answer
to the high-speed adder problem. However, a closer look at the set of carry equations given above quickly
reveals that the equations become progressively more complex in the number of product terms and literals.
Therefore, fan-in constraints will eventually limit the practicality of realizing the equations in three-level logic.
The actual limit is technology dependent. Standard single-chip medium-scale ALUs typically handle four-bit
operands, although longer lengths are certainly feasible with today’s technology.
CLAs may be cascaded to produce an adder for longer operands. Figure 81.53 shows a cascade of four 4-bit
CLAs to produce a 16-bit adder. Carries are produced using carry lookahead logic within each CLA stage but
must propagate between stages in a manner reminiscent of a ripple-carry adder. Hence the add time of cascaded
CLAs is dependent on the number of stages in the cascade. The four-stage adder shown in Fig. 81.53 has a
worst-case add time of 5t
pd
. In general, the add time of an m-stage cascade is (m + 1)t
pd
.
The carry lookahead approach can be applied at a higher level to eliminate the propagation of carries between
CLA stages or blocks. This approach uses block carry lookahead adders (BCLAs) and block carry lookahead
(BCL) logic as shown in Fig. 81.54. A BCLA is a CLA modified to produce block carry propagate (P) and block
carry generate (G) outputs instead of a carry-out. BCL logic is a combinational logic circuit that generates
block carries (C
j
) for each BCLA from the P and G outputs of lower-order BCLAs and c
0
. Logic equations for
the block carry logic can be derived by repeated application of the following equations for a typical block:
C
j
= G
j
+ P
j
C
j–1
where
G
j
= [g
3
+ p
3
g
2
+ p
3
p
2
g
1
+ p
3
p
2
p
1
g
0
]
j
and
P
j
= [p
3
p
2
p
1
p
0
]
j
FIGURE 81.53Cascaded carry lookahead adders.
FIGURE 81.54Block carry lookahead adders.
? 2000 by CRC Press LLC
BCLAs and block carry logic units are available in standard medium-scale integrated circuits. Extension of
the carry lookahead concept to k levels is possible in theory. However, more than three levels is usually not
practical.
Multifunction Arithmetic Logic Units
Devices that can provide a variety of addition, subtraction, and logical operations can be easily designed around
the adders/subtracters presented in the previous sections. The logic diagram of the first two stages of an n-bit
multifunction ALU is given in Fig. 81.55. Operand inputs for the device are X = x
n–1
. . . x
1
x
0
and Y = y
n–1
. . .
y
1
y
0
and the output is S = s
n–1
. . . s
1
s
0
. The function performed on the operand(s) is determined by the values
of the control inputs k
2
, k
1
, k
0
, and c
in
as shown in Table 81.7. The given realization is based on a ripple-carry
adder for simplicity of presentation. However, the same design approach can be used with other adders such
as carry lookahead.
Standard Integrated Circuit ALUs
The devices described above are generic in nature but are similar in function and realization to many com-
mercially available integrated circuit products. Representative products are summarized in Table 81.8.
FIGURE 81.55Multifunction ALU.
TABLE 81.7Functions Performed by the Multifunction ALU
Control Inputs
k2 k1 k0 cin Result Function
0000S = X Transfer X
0001S = X + 1 Increment X
0010S = X + Y Addition
0011S = X + Y + 1 Add with carry in
0100S = X – Y – 1 Subtract with borrow
0101S = X – Y Subtraction
0110S = X – 1 Decrement X
0111S = X Transfer X
1 0 0 . . . S = X OR Y Logical OR
1 0 1 . . . S = X OR Y Exclusive-OR
1 1 0 . . . S = X AND Y Logical AND
1 1 1 . . . S = NOT X Bit-wise complement
? 2000 by CRC Press LLC
Defining Terms
Arithmetic logic unit (ALU): A combinational logic circuit that can perform basic arithmetic and logical
operations on n-bit binary operands.
Block carry lookahead adder (BCLA): An adder that uses two levels of carry lookahead logic.
Carry lookahead adder (CLA): A high-speed adder that uses extra combinational logic to generate all carries
in an m-bit block in parallel.
Full adder (FA): A combinational logic circuit that produces the two-bit sum of three one-bit binary numbers.
Ripple-carry adder (RCA): A basic n-bit adder that is characterized by the need for carries to propagate from
lower- to higher-order stages.
Related Topic
81.1 Combinational Networks and Switching Algebra
References
J. Gosling, Design of Arithmetic Units for Digital Computers, New York: Springer-Verlag, 1980.
K. Hwang, Computer Arithmetic: Principles, Architecture, and Design, New York: John Wiley and Sons, 1979.
M.M. Mano, Digital Logic and Computer Design, Englewood Cliffs, N.J.: Prentice-Hall, 1979.
V.P. Nelson, H.T. Nagle, B.D. Carroll, and J.D. Irwin, Digital Logic Circuit Analysis and Design, Englewood Cliffs,
N.J.: Prentice-Hall, 1995.
E.E. Swartzlander, Jr., Ed., Computer Arithmetic, Volume I, Los Alamitos, Calif.: IEEE Computer Society Press,
1980.
E.E. Swartzlander, Jr., Ed., Computer Arithmetic, Volume II, Los Alamitos, Calif.: IEEE Computer Society Press,
1990.
TTL Data Book, Texas Instruments, Inc., Dallas, Texas, 1988.
J.F. Wakerly, Digital Design Principles and Practices, 2nd ed., Englewood Cliffs, N.J.: Prentice-Hall, 1994.
S. Waser and M.J. Flynn, Introduction to Arithmetic for Digital Systems Designers, New York: CBS College
Publishing, 1982.
Further Information
The reader wanting information on the theoretical aspects of computer arithmetic is referred to the IEEE
Transactions on Computers, a monthly publication of the Institute for Electrical and Electronics Engineers, Inc.,
445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855-1331.
More information on the specifications and applications of integrated circuits can be found in the data books
and application notes published by electronics manufacturers such as Texas Instruments, Motorola, and
National Semiconductor.
Discussions of multiplication, division, and floating-point arithmetic can be found in numerous textbooks
on computer architecture.
TABLE 81.8 Typical Integrated Circuit Arithmetic and Logic Devices
Part Number Function Features
74LS181 4-bit multifunction (16) ALU BCL outputs
74LS182 Carry lookahead generator Use with 74LS181 for BCL
74LS183 Full adder Two per package
74LS283 4-bit binary adder Internal CL
74LS381 4-bit multifunction (8) ALU BCL outputs
74LS382 4-bit multifunction (8) ALU Ripple-carry output
? 2000 by CRC Press LLC
