The PAL concept was pioneered in the 1970s by Monolithic
Memories
(which has since merged with Advanced Micro Devices,
also known as AMD
). It was based on bipolar fuse technology
developed for programmable ROMs
(all connections are initially
available; "blow" the connections you do not want
).
The primary goal of PAL-based designs was to reduce parts count by replacing
conventional TTL logic with more highly integrated programmable logic. Designers
frequently report that four TTL packages
(10 to 100 "gate
equivalents"
) can be replaced by a single PAL.
PAL-based designs also have the advantage of reduced
parts inventory, since a PAL is a "universal" device. You don't
need a large stock of miscellaneous TTL components. In addition, PALs support
rapid prototyping, because they reduce the number of component-to-component
interconnections. Designers can implement bug fixes and new functions within
the PALs, often without making changes at the printed circuit board level.
10.3.1 PLDs: Programmable Logic Devices
A number of companies have extended the PAL concept by
changing the underlying technology, as well as the component's array of
gates and interconnections. Generically, these components are called programmable
logic devices
(PLDs
), with the more sophisticated
devices called field-programmable gate arrays
(FPGAs
).
We will examine three representative PLD architectures in this section:
Altera MAX, Actel programmable gate array, and Xilinx logical cell array.
10.3.2 Altera Erasable Programmable Logic Devices
Except for very high speed programmable logic, the general
trend has been toward CMOS implementation, with its much higher levels of
circuit integration and lower power demands than bipolar technologies. PALs
were initially based on the same "program once" technology as
bipolar PROMs. Altera pioneered the development of erasable programmable
logic devices
(EPLDs
) based on CMOS erasable ROM
technology. The EPLD can be erased simply by exposing it to ultraviolet
(UV
) light and then reprogrammed at a later time.
Altera EPLDs are equivalent to 100 to 1000 conventional two-input gates,
depending on the model selected.
EPLD Macrocell Architecture The
basic element of the EPLD is the macro-cell, containing an eight-product-term
AND-OR array and several programmable multiplexers. Multiplexers are particularly
easy to implement in MOS technology, so it is no surprise that they are
pervasive in CMOS-based programmable logic.
Figure 10.25 gives a block diagram/schematic view of the macrocell's
contents. Its elements include a programmable AND array, a multiple fan-in
OR gate to compute the logic function with programmable output polarity
(via the XOR gate
), a tri-state buffer driving
an I/O pin, a programmable sequential logic block, and a programmable feedback
section. Depending on the component, an EPLD may contain from 8
(EP300
series
) to 48
(EP1800 series
) such
macrocells, each of which can be independently programmed.
Let's look at each of the programmable elements of the
macrocell. As you will see, it offers more flexibility than any of the PAL
architectures we have seen so far.
The macrocell's AND array is crossed with the true and
complement of the EPLD's dedicated input and clock pin signals and the internal
feedbacks from each of the component's outputs. Crosspoints are implemented
by EPROM connections that are initially connected. Unwanted connections
are broken by "blowing" the appropriate EPROM bits.
The multiplexers allow the feedback, output, and clock
sections to be independently programmed. The MUX selection lines are controlled
by their own EPROM bits. Under MUX control, the combinational function can
bypass the flip-flop on the way to the output. Thus you can program any
output to be either combinational or registered.
Similarly, macrocell feedback into the AND arrays can
come from the registered output or from the external pin. You can program
many of the pins to be either output or input.
Some variations on the macrocell architecture support
dual feedback, making it possible to use the register for internal state
while the pin is used as an independent input. This is an application of
the concept of buried registers mentioned in Section 10.1.3.
The programmable clock section allows you to
(1
)
clock the registers synchronously in groups by a dedicated clock input or
(2
) clock them by a local signal within the macrocell.
Since the latter is a product term, the register's clock signal can be any
combination of inputs or external clocks.
The two possible configurations of the clock multiplexer
are shown in Figure 10.26.
Depending on the value of the bit programmed within the EPROM cell, the
flip-flop is controlled with the global clock while the AND array's product
term selectively enables the output. This is called
synchronous mode
because the output register is clocked by a global clock signal, shared
among all macrocells. This signal can cause all outputs to change at the
same time.
Alternatively, the clock multiplexer can be configured
so a local clock, computed from a distinguished AND array product term,
controls the output register. In this mode, the output is always enabled,
driving the output pin. Since every macrocell can generate its own local
clock, the output can change at any time. This is called
asynchronous
mode.
The register embedded in the macrocell can be configured
as a
D or
T flip-flop, either positive or negative edge-triggered.
Since
J-
K or
R-
S flip-flops can be implemented
in terms of
D or
T flip-flops, they are realized by providing
the appropriate mapping logic in the AND-OR array.
The final programmable element of the macrocell is the
register clear signal. One of the AND array's product terms is dedicated
to provide this function.
Altera MAX Architecture The major
problem with all AND-OR structures is the difficulty of sharing product
terms among macrocells. In a conventional PAL, you cannot share the same
product term across -different OR gates. The term must be repeated for each
output. This can lower the efficiency of the PAL, reducing the number of
equivalent discrete gates it can replace.
As programmable logic devices become even more highly
integrated, the architectures must evolve to provide more area for global
routing of signals. It must be possible to share terms and outputs between
macrocells more easily. Altera has addressed these problems in their
multiple
array matrix (MAX
) family of parts. We describe
the structure of MAX components in this subsection.
Macrocells, similar in structure to Figure 10.25, are
grouped into Logic Array Blocks
(LABs
). Associated
with each LAB is a group of additional product terms, usable by any of the
macrocells within the LAB. These Expander Product Terms make it possible
to implement a function with up to 35 product terms inside a single macrocell.
This compares to only eight terms per function in most PAL families.
In addition, a Programmable Interconnect Array
(PIA
)
can route the LAB's macrocell outputs globally throughout the device. Some
lower-density devices also use the PIA to route the product term expanders.
Figure 10.27 shows the generic architecture of a MAX component,
the EPM5128. The device has eight dedicated inputs
(including
the clock
), 64 programmable I/O pins, eight LABs, 16 macrocells
per LAB
(128 macrocells total-not all macrocells are connected
to an output pin
), and 32 product term expanders per LAB
(256
total
). The dedicated input pins come in along the top and
are distributed to each of the eight LABs. The PIA routes global signals.
All on-chip signals have a connection path to the PIA. Only the signals
needed by a particular LAB are connected to it under EPROM programming.
The newest top-of-the-line Altera MAX component is
the EPM5192. This device contains 192 macrocells organized into 12 LABs.
Altera claims that a single EPM5192 can replace up to 100 TTL SSI and MSI
components or 20 P22V10 PALs
(for the implementation power
of this kind of PAL, see Figure 10.28
).
Altera has under development a 7000 series of parts that organizes the
LABs into multiple rows and columns around the programmable interconnect.
The plan is to develop a chip architecture offering 1500 to 20,000 gate
equivalents.
Figure 10.28 shows more details of the LAB's internal
organization. It consists of an array of macrocells sharing a product term
expander array. All macrocell outputs and I/O block inputs are connected
to the PIA. Selected signals from the PIA are input to the macrocells.
Figure 10.30 gives more details of the implementation
of the expander product terms. The AND array is crossed by the dedicated
inputs and the feedback signals from the macrocells. The expander terms
also form some of the columns of the array. In other words, they appear
like inputs to the macrocells. Any expander term can be shared by all of
the macrocells in the LAB.
If you use expander terms you quickly get into multilevel
logic structures. Optimization techniques such as those in
misII
are absolutely necessary to do a good job of mapping logic onto these structures.
Once you reach devices as complex as the advanced MAX
family, you would be unlikely to try to generate the personality map by
hand. Altera provides an extensive tool set for mapping logic schematics
onto the primitives supported by their EPLD structures.
EEPROM Technology for EPLDs Another
class of erasable PLDs is based on the technology of
electrically erasable
programmable ROM
(EEPROM
). This has two advantages.
First, less expensive packaging can be used because there is no chip window
for the erasing UV light. -Second, crosspoints can be reprogrammed individually,
which can speed up the process if only a small number of changes are needed.
The macrocell and chip architectures are similar to those described in this
section.
10.3.3 Actel Programmable Gate Arrays
Actel programmable logic chips provide what amounts to
a field-programmable gate array structure. The chip contains rows of personalizable
logic building blocks separated by horizontal routing channels. The programming
method is a proprietary "antifuse" technology, so called because
the connector's resistance changes from high to low when a high voltage
is placed across it. This is the opposite of a conventional PAL or PROM
based on fuse technology. The antifuses require a very small area, so the
chip can have more connections than with other technologies. Unlike the
EPLDs, Actel parts can be programmed only once.
The elements of the Actel architecture are I/O buffers,
logic modules, and interconnect.
Figure 10.31 shows a chip "floor plan" or block diagram. Programmable
I/O buffers, and special programming and test logic are along the chip's
edges. The I/O pins can be configured as input, output, tri-state, or bidirectional
buffers, with or without internal latches.
Internally, the building blocks are organized into multiple
rows of l
ogic modules separated by wiring tracks. Each logic module
is an eight-input, one-output configurable combinational logic function
(the internal structure is described in the next subsection
).
You can program the module to implement a large number of two-, three-,
and four-input logic gates, as well as two-level AND/OR and OR/AND gates.
There are no dedicated flip-flops, although
D and
J-
K
storage elements can be constructed from two connected modules.
Horizontal wiring tracks provide the main interconnection.
Although the tracks run across the length of the chip, a given wire can
be partitioned into segments for several interconnections. In addition,
vertical wires pass through the logic modules and span multiple wiring channels.
Four inputs come from the track above the logic module and four from the
track below.
The ACT 1 component family is organized around 25 horizontal
and 13 vertical routing tracks. The arrays contain 1200 to 2000 gates, equivalent
to two- or three-input NAND and NOR functions. Because of the flexibility
of the routing and the personalization of the logic module, Actel claims
these are equivalent to 3000 to 6000 gates in a more typical PLD. A second-generation
family, under development, will have more horizontal and vertical routing
tracks. The new components will contain up to 8000 gates, which Actel claims
are equivalent to 20,000 gates in a conventional PLD.
Actel Logic Module The logic module
is a modified four-to-one multiplexer. Its block structure is shown in Figure
10.32.
D0,
D1,
D2,
D3, SOA, SOB,
S0,
S1 are inputs selected through programmable connections from the
wiring tracks either above or below the logic block.
Y is the single
output. It can be routed to the horizontal tracks through programmable connections.
A remarkable number of logic functions can be implemented
with this simple building block. For example, let's see how the module can
be used to implement a two-input AND gate with inputs
A and
B.
We simply wire
A to
D1, 0 to
D0, and
B
to SOA. Then wire
S0 and
S1 to 0. If
B is 1 then
Y receives
A; otherwise it receives 0. This is essentially
an AND function.
The symmetry of the logic module makes it easy to implement
functions whether the inputs are available above or below the module. For
example, if the inputs to the AND "gate" are not available from
the top of the module, the lower two-to-one multiplexer could easily be
used to implement the function.
The logic module is not limited to implementing combinational
functions. Let's look at how to implement an
-
latch with a single
module. The approach is shown in Figure 10.33.
If
is 0,
Q is set to 0, the output of the upper
two-to-one multiplexer. If
is 1, then
Q is
set to the output from the lower multiplexer. This depends on
. If
is 0, then
Q is set to 1. Otherwise,
Q
is again set to its current value. This is exactly the function of the
-
latch.
Actel Interconnect The routing
of signals through the array is one of the most innovative features of the
Actel architecture. Antifuses are placed wherever a horizontal and a vertical
wire cross, as well as between adjacent horizontal and vertical wire segments.
The interconnection "fabric" and its relation
to the logic modules are shown in Figure 10.34.
The pass transistors and lines controlling their gates are used in programming
to isolate a particular antifuse. Placing a high voltage across the antifuse
establishes a bidirectional interconnection between the two crossing wires.
The logic modules must be carefully placed and then wired
by routing interconnections through the network of antifuses. Because of
the resistance and capacitance associated with crossing an antifuse, speed-critical
signals pass through two antifuses. Most connections can be performed in
two or three hops. The worst case might require four hops.
These concepts are illustrated in Figure 10.35.
Every jog from a horizontal to a vertical wiring track and vice versa
crosses an antifuse. To go from an output to the upper input requires one
jog from horizontal to vertical, a second from vertical to horizontal, and
a final jog to vertical again.
Some wire segments may be blocked by previously allocated
segments. This is shown by the lower logic module input. To get to it, the
output signal jogs vertically to a new horizontal line, to which the input
vertical line can be connected. In general, a horizontal segment is made
longer by jogging to another overlapping segment via an available vertical
wire.
10.3.4 Xilinx Logic Cell Arrays
Xilinx takes another approach to bringing the PLD concept
to higher levels of integration. Their programming method is based on CMOS
static RAM technology: RAM cells sprinkled throughout the chip determine
the personality of logic blocks and define the connectivity of signal paths.
Static RAM circuits are important in integrated circuit technology and will
continue to get denser and faster.
The RAM cells are linked into a long shift register,
and the programming involves shifting in strings of ones and zeros to personalize
the function of the chip. The devices come with an on-board hardwired finite
state machine that allows the program to be downloaded from a standard ROM
part. The Xilinx approach has the advantage of fast reprogrammability, although
the chip loses its program each time it is powered down.
Figure 10.36 shows a portion of the chip architecture of the Xilinx logic
cell array. The major components are I/O blocks
(IOBs
)
and configurable logic blocks
(CLBs
). The programmable
I/O blocks are placed around the periphery, while the CLBs are arrayed in
the central part of the chip. Horizontal and vertical wiring channels separate
the various components. We will examine these components in the following
subsections.
Xilinx currently supports three component families, the
2000, 3000, and 4000 series. We will discuss the 3000 series, the one most
commonly encountered in practice. The XC3020 component contains 64 IOBs
and 64 CLBs arranged in an eight-by-eight matrix. Xilinx claims that the
component contains 2000 equivalent logic gates. The largest member of the
family, XC3090, contains 320 CLBs and 144 IOBs and is claimed to be equivalent
to 9000 two-input gates.
Xilinx I/O Block Figure 10.37 shows the internal
architecture of the I/O block. The inputs to the I/O block are a tri-state
enable, the bit to be output
(OUT
) to the package
pad, and the input and output clocks. The outputs from the block are the
input
(Direct In or Registered In
) signals. The
block contains registers in both the input and output paths. These can be
reset by a global reset signal provided to the block.
First, let's consider how the block can be used when
it is associated with an output pad. The active high or low sense of the
OUT signal and the output enable can be set by internal options, stored
in RAM cells within the block. The output signal can be direct
(combinational
)
or from the dedicated output register
(registered
).
This register is an edge-triggered
D flip-flop.
The slew rate control on the output buffer is used to
slow down the rise time of output signals. It can reduce noise spikes in
designs where large numbers of outputs change at the same time. Outputs
can be fast
(5 ns switching time
) or slow
(30
ns switching time
).
Let's now consider the block with the pad used as an
input. The input signal can come from the dedicated input register or directly
from the input pad. The input register can be an edge-triggered flip-flop
or a transparent latch. The input pull-up is intended for use with unused
IOBs, so that internal signals are not permitted to float. It cannot be
used by the output buffer.
Xilinx CLB Figure 10.38 gives the internal view
of the CLB. It has five general purpose data inputs
(A,
B,
C,
D,
E), one clock
input, one clock enable input, data in
(DIN
),
Reset, and two outputs,
X and
Y. The outputs can be registered
or direct. In addition, the CLB has a combinational function generator,
two storage elements, and five programmable multiplexers.
The function generator takes seven inputs, five from
the programmable interconnect
(A,
B,
C,
D,
E), and two from internal flip-flop feedbacks
(Q1,
Q2
). It also produces two
internal outputs
(F,
G).
Personality RAM bits let us configure the function block
in one of three different ways. With the first option, the function generator
can compute any Boolean function of five variables. The distinct inputs
are
A, one of
B/
Q1/
Q2, one of
C/
Q1/
Q2,
D, and
E. Both
F and
G carry the same
output value. For example, in this mode, a single combinational function
generator can implement a 5-bit odd parity function:
.
With the second option, the function generator can compute
two independent functions of four variables each. The inputs are
A,
one of
B/
Q1/
Q2, one of
C/
Q1/
Q2,
and one of
D/
E.
F and
G carry separate
outputs. In this mode, a single function generator can compute a simple
2-bit comparator. Suppose the two 2-bit numbers are represented as
A,
B and
C,
D, respectively. Then the
greater
than (GT
) and
equal (EQ
)
functions can be computed as follows:
The final option implements certain restricted functions
of more than five inputs. The variable
E selects between two independent
functions, each computed from the inputs
A, one of
B/
Q1/
Q2,
one of
C/
Q1/
Q2, and
D. The three different
options are summarized in Figure 10.39.
The internal flip-flops are positive edge triggered
and can be -controlled by the clock or its complement, depending on the
configuration setting. They share a common clock signal. Their data sources
are the internally generated functions
F and
G or the
DIN input from the interconnect. An active high asynchronous reset signal
can set both registers to zero. When the enable clock input is unasserted,
the flip-flops hold their current state, ignoring the clock signals and
the inputs. The flip-flop outputs,
Q1 and
Q2, are fed
back as inputs to the function generator, making it possible to implement
sequential functions within a single CLB.
The two outputs from the CLB,
X and
Y,
can be driven from the flip-flops or directly from the
F and
G
outputs of the function generator. The CLB organization is reasonably symmetric,
making it possible to interchange the top or bottom inputs/outputs to reduce
the complexity of interblock routing.
CLB Application Examples A small
number of CLBs can implement a wide range of combinational functions.
Figure 10.40 shows a few examples of majority logic and parity checking.
An
n-input majority function asserts a 1
whenever
or more inputs are 1. Clearly, a single CLB can implement
a five-input majority circuit: this is nothing more than a combinational
function of five variables!
Now consider a seven-input majority circuit. This can
be implemented with three CLBs as shown in the figure. The first-level CLBs
count the number of ones in their three inputs, outputting the patterns
00, 01, 10, or 11. Although the first-level CLBs are functions of only three
inputs, they use both of their outputs. The second-level CLB sums its three
sets of inputs
(two 2-bit inputs and one 1-bit input
);
if these equal or exceed four, it asserts the majority output.
Now consider a parity-checking circuit. A single CLB
can implement a 5-bit-wide parity checker, as we have already seen. Cascading
two CLBs, as shown in the figure, yields a nine-input circuit. With two
levels of CLBs, we can extend the scheme to 25-bit-wide parity logic.
As another combinational logic example, consider how
we might implement a 4-bit binary adder. A full adder can be implemented
in a single CLB. The
Cout and
Si outputs are functions
of the three inputs
Ai,
Bi, and
Cin. To get a
4-bit adder, we simply cascade four CLBs. This is shown in Figure 10.41
(a
).
An alternative approach is to use the 2-bit binary
adder as a building block. This circuit has five inputs,
A1,
A0,
B1,
B0, and a
Cin. The outputs
S1,
S0,
and
Cout are each functions of these five variables. Thus, the
2-bit adder can be implemented with three CLBs. To construct a 4-bit adder,
we cascade two 2-bit units for a total of six CLBs. This is shown in Figure
10.41
(b
).
The second implementation may not look attractive, but
it has some advantages. It incurs two CLB delays in computing the 4-bit
sum, one to compute the carry between the low-order 2 bits and the high-order
sums and one to compute the final sums of the high-order bits. This compares
with four CLB delays in the implementation based on the standard full adders.
This example illustrates some of the trade-offs between
CLB resources and delay. The delay through the logic block is fixed, independent
of the function it is implementing. The first approach uses less CLB resources
than the second, but actually is slower.
Obviously, the CLB structure is not limited to combinational
circuits. Because of the two flip-flops per CLB, it is possible to construct
4-bit counters of various kinds using just two CLBs. The CLB inputs are
the current state,
Q3,
Q2,
Q1, and
Q0.
The outputs of the first CLB are the higher-order 2 bits of the counter.
The output of the second is the lower-order 2 bits.
Xilinx Interconnect The Xilinx
chip architecture supports three methods of interconnecting the CLBs and
IOBs:
(1
) direct connections,
(2
)
general-purpose interconnect, and
(3
) long line
interconnections. With direct connections, adjacent CLBs are wired together
in the horizontal or vertical direction. General-purpose interconnect is
used for longer distance connections or for signals with a moderate fan-out.
The long lines are saved for time-critical signals that must be distributed
to many CLBs with minimum signal skew, such as clock signals.
Direct connections provide the fastest, shortest-distance
form of interconnect. Thus, it is important for the software that assigns
logic functions to available CLBs to place related logic in adjacent CLBs.
The
X output of a CLB can be connected to the
B input
of the CLB to its right or the
C input of the CLB to its left.
The
Y output can be connected to the
D input of the CLB
above it and the
A input of the CLB below it.
These direct connections are shown in Figure 10.42.
We show four CLBs, with inputs
A, CE
(clock enable
),
DI
(data in
),
B,
C,
K
(clock
),
E,
D, and
R
(reset
) and outputs
X and
Y.
The relative placement of connection pins on the CLBs is geometrically accurate.
CLB2's
X output is connected to the
B
input of CLB3. The
X output of CLB1 connects to the
C
input of CLB0. All of the
X connections are horizontal. Similarly,
the
Y output of CLB1 is connected to the
A input of CLB3.
The
Y output of CLB2 connects to the
D input of CLB0.
The
Y connections are vertical.
We can also use direct connections to wire CLBs and IOBs.
There are two IOBs next to each CLB along the top or bottom row of the logic
cell array. Along the top, the CLB
A input can be driven from the
output of one IOB, and the CLB
Y output is connected to the other
IOB's input. Along the bottom, the
D input plays the same role
as the
A input along the top.
Along the right edge, the
X output can be connected
to one IOB while the
Y output is connected to either of the adjacent
IOBs. The
C input is driven from one of the IOBs. Along the left
edge, the
B input can be driven from an IOB, and the IOB can be
driven from the
X output. CLBs in the corners can connect to IOBs
in two dimensions.
Interleaved among the checkerboard of CLBs are the horizontal
and vertical wiring channels of the Xilinx general-purpose interconnect.
Each channel contains five wires. At the intersections, a programmable switching
matrix connects the wires, as shown in Figure 10.42. The figure shows a
connection path between the
Y output of CLB0 and the
D
input of CLB1.
The general-purpose interconnect places many restrictions
on what can be connected to what. For example, it is not possible to connect
every switch matrix pin to every other pin. The pin we used, the second
pin from the left on the top, is only connected to the top pins on the left
and the right, the three leftmost pins on the bottom, and the second pin
from the top on the right. As another example of wiring restrictions, the
D input of a CLB can be connected to the second wire in the horizontal
channel but not the top wire. Fortunately, Xilinx's software for placing
and routing the LCA is aware of the restrictions in the wiring fabric and
can hide most of these considerations from you.
The final forms of interconnect are the long lines. There
are two such lines per row and three per column. In addition, a single global
long line is driven by a special buffer and distributed to every column.
It can be connected to the
K input of every CLB.
One more special global signal is not shown in the wiring
diagrams. A global reset line, connected to the chip reset pin, can force
all flip-flops in the LCA to zero, independent of the individual CLB reset
input.
Implementing the BCD-to-Excess-3 Converter with
a Xilinx Logic Cell Array In this subsection, we examine the implementation
of the BCD-to-Excess-3 converter finite state machine using the LCA structure.
The next-state and output equations are
Suppose we adopt a synchronous Mealy implementation
style. Then each of the four functions requires its own flip-flop. Since
no function is more complex than four variables, we can implement each one
in one-half of a CLB.
To give you a feeling for the size of functions that can
be implemented in a Xilinx chip, the smallest configuration contains 64
CLBs. The example finite state machine uses only 1/32 of the CLB resources
of the array.
One critical issue is how to provide reset to the finite
state machine. We will use the global reset signal derived from the dedicated
reset pin on the LCA package. When this signal is asserted, all flip-flops
in the array are set to zero.
Xilinx provides software to map a logic schematic into
a placed and routed collection of CLBs, so designers rarely have to deal
with the array at this level of detail. Still, it is instructive to understand
some of the routing details, because they have a critical effect on performance.
Xilinx permits you to hand route critical nets to tune circuit performance
(or to help the automatic router complete a difficult routing
),
if desired.
Figure 10.43 shows a possible interconnection scheme. It uses global
long lines, horizontal long lines, direct connections, and general--purpose
connections. The global long line is dedicated to the clock signal, which
drives the
K input of the two CLBs. The horizontal long line carries
the clock enable signal
(CE
). Xilinx makes it
possible to attach the horizontal lines to pull-up resistors, so this wire
can always carry a 1. The vertical long lines are not used in this example.
We have placed
Q2 and
Q0 in CLB1, with
Q1 and
Z in CLB2. This partitioning helps to minimize
the use of general-purpose interconnect. CLB1 is implemented without any
external inputs, by exploiting the connections inside the CLB.
Since the flow of signals is horizontal from left to right
and only CLB1's
X output
(Q2
)
can be routed through horizontal direct interconnect, the
Y output
(Q0
) must go through general-purpose
interconnect.
Normally, the
Y output of CLB2
(Z)
would be wired to the vertical channel, eventually reaching an IOB at the
periphery of the array of CLBs. If these CLBs are placed along the top row
of the array, direct connections can be used to make the machine's inputs
and outputs directly available. An input IOB, carrying the machine's
X
input, can be wired to the
A input of CLB2. Also, CLB2's
Y
output, carrying the machine's
Z output, can be connected to an
adjacent IOB configured for output.
Traffic Light Controller
In this section, we will examine several alternative implementations
for the traffic light controller finite state machine. We start by decomposing
the basic machine into its constituent subsystems. Besides the next-state
and output functions, we also need logic for the timing of the lights and
for detecting the presence of a car at the intersection.
10.4.1 Problem Decomposition: Traffic Light State Machine
Of course, there are many possible ways to organize the
components of the traffic light system. Here is the decomposition we will
use:
Controller finite state machine
next state/output combinational functions
state register
- Short time/long time interval counter
- Car sensor
- Output decoders and traffic lights
System Block Diagram A block diagram
description for this decomposition is shown in Figure 10.44.
The controller finite state machine takes as input the Reset, Clk,
TL,
and
TS signals, as well as a synchronized
C signal, and
generates the
ST signal and encoded light signals
(00
= green, 01
= yellow, 10
= red
).
The interval counter subsystem takes Clk, Reset, and
ST as inputs,
generating
TL and
TS as outputs. The car sensor subsystem
has an asynchronous sensor input
C, which it outputs as a synchronized
signal. The light decoders translate the encoded light control signals into
signals to drive the individual lights.
It is reasonable to generate outputs that directly control
the lights, rather than the encoded scheme we have chosen. Since the actual
traffic lights are probably relatively far from the traffic light controller
hardware, the encoded scheme has the advantage of fewer wires that need
to be routed that distance. But the approach requires additional logic to
do the decoding near the lights.
In the way we have drawn Figure 10.44, the finite state
machine is a Mealy machine. Is it synchronous or asynchronous? Because the
inputs
C (sync
),
TS, and
TL
change with the clock, it is a synchronous machine. To be thorough, Reset
should also be synchronized.
In the following subsections, we look at the logic for
the next state and outputs, the car detector, the light decoders, and the
interval timer.
Next-State Logic and Outputs The
finite state machine has six inputs: Reset,
C,
TL,
TS,
and the current state
(Q1,
Q0
);
and seven outputs: the next state
(P1,
P0
),
ST,
H1,0
(encoded highway lights
),
and
F1,0
(encoded farmroad lights
).
An
espresso truth table file, such as that in
Figure 9.21, can be used to specify the transition table for the state machine.
From this, we can generate discrete gate, PAL, or PLA-style logic for the
next state and other outputs.
Car Detector The car detector logic
is much like the debounced switch of Section 6.6.1. A two-position switch
embedded in the road determines whether a car is present. This signal should
be stable during the transition from one setting to the other, and this
calls for a debouncing circuit.
Since a car can arrive at any time, the car detector
is asynchronous with respect to the rest of the traffic light system. To
synchronize the car sense signal, we must pass it through a synchronizer
flip-flop, clocked by the system clock. The circuit is given in Figure 10.45.
Light Decoders The light decoder
circuitry is reasonably straightforward. We can use 2-to-4 decoders, such
as the TTL 74139.
Figure 10.46 contains the necessary logic.
Interval Timer The last major component
is the interval timer, designed to generate the signals
TL and
TS after being set by
ST. We could -implement this in
many ways, perhaps the simplest being to use a counter and external decode
logic. The counter is cleared when
ST is asserted, and
TL
and
TS are asserted by the external logic when the counter counts
up to the appropriate threshold value. For this discussion, we will assume
that TS is asserted when the 4-bit counter reaches 01112 and
TL
is asserted when it reaches 11112. Wider counters can be used for more realistic
interval timings.
Figure 10.47 shows how the logic could be implemented using a 74163 synchronous
up-counter. In the figure, the OR of
ST and RESET is complemented
to reset the counter. When either
ST or RESET is asserted, the
input is asserted, and the counter is set to zero. This
is not strictly necessary: whatever state the counter comes up in when powered
on, it will eventually cycle through the states that cause
TS and
TL to be asserted.
10.4.2 PLA/PAL/ROM-Based Implementation
In this subsection, we will use the best encoding found
in Section 9.3.1: HG
= 00, HY
= 10, FG
=
01, and FY
= 11. This yields an implementation for the next-state
and output functions that requires eight unique product terms:
Any PLA component with five inputs, seven outputs, and
eight product terms could implement these functions.
PLA/PAL Implementation Because
no function is more complex than four product terms, they can also be implemented
by many of the available sequential PALs. For example, in Section 8.5.3
we gave an ABEL description for the traffic light state machine that used
a P22V10 PAL
(see Figure 10.28
). This device has
11 dedicated inputs and 10 programmable input/outputs. When the latter are
programmed as outputs, they can be either registered or combinational. The
OR array varies from 8 to 14 product term inputs, sufficient to implement
any of the functions above. The embedded registers can be reset through
a dedicated reset line that is routed to each output register, so it is
not necessary to include a Reset input signal in the equations.
ROM Implementation A ROM-based
implementation requires a complete tabulation of the state transition table.
With five inputs and seven outputs, this is a 32-word by 8-bit ROM. If Reset
is to be handled by the next-state logic directly, this should be included
as one of the inputs to the ROM, thus doubling its size.
10.4.3 Counter-Based Implementation
Although the two-level implementation just described
is appropriate for a PAL- or PLA-based approach, it is not necessarily the
best strategy when using packaged components such as TTL. The equations
in the preceding subsection require eight 3-input gates
(three
packages
), two 4-input gates
(one package
),
three 2-input gates
(one package
), four inverters
(one package
), and many wires. An MSI-based implementation
could lead to fewer components and certainly fewer interconnections.
Counters, Multiplexers, Decoders If
you examine the traffic light finite state machine carefully, you should
see that a counter could be used to implement the state register. After
all, the machine either holds in its current state or advances to the next
state in a well-defined sequence.
Let's make the state assignment HG
= 00,
HY
= 01, FG
= 10, and FY
= 11. We
will implement the state register with a 74163 synchronous up-counter. An
external reset signal can be wired to the counter's synchronous clear input.
The question now becomes how to implement the counter's
count input.
Figure 10.48 reproduces the state diagram for the traffic controller.
In state HG, the exit condition is
TL C. In HY and FY,
it is
TS. In FG, it is
TL + 
. We could use logic
that takes the relevant condition of the current-state bits and ANDs it
with the appropriate exit condition to form the count signal. Unfortunately,
this would take a fair amount of discrete logic.
A better way is to use a multiplexer to implement the
count signal. We drive a four-to-one multiplexer's selection lines with
the current-state bits,
Q1 and
Q0. The inputs are wired
for the appropriate exit condition. This is shown in Figure 10.49.
The count signal and the start timer signal,
ST, are identical.
As you can see, this approach represents a substantial reduction in package
count.
As one final application of MSI components, it is possible
to drive the traffic lights from signals that have been directly decoded
from the current state. For example, if the machine is in state HG, the
highway lights are green and the farmroad lights are red. Similarly, the
highway lights are yellow and the farmroad lights are red when the machine
is in state HY. Thus the highway green light and yellow light can be decoded
directly from state 0 and 1, respectively, while the farmroad red light
is driven by the OR of these decoded signals. The logic is shown in Figure
10.50.
10.4.4 LCA-Based Implementation
Let's begin with the same set of equations we used for
the PAL/PLA-based implementation. Fortunately, none of the next-state and
output functions are more complex than five variables:
P1 and
ST
are five variables;
P0,
H1,
H0, and
F0
are three variables; and
F1 is one variable. Thus, we can implement
the finite state machine in four and one half CLBs: one CLB each for the
two 5-variable functions, and the remaining five functions grouped two apiece
into the remaining CLBs.
Xilinx provides software that takes as input a schematic
description of a circuit, automatically partitions the logic to the CLB
components, chooses specific CLBs in the logic array to implement this partitioning,
and selects a routing of the interconnections to complete the implementation.
In general, the designer need not know in detail how the schematic is mapped
into the array structure. Nevertheless, to illustrate more about the internal
structure of the LCA, we will perform the partitioning, placement, and routing
by hand
(Xilinx provides an editor that lets you deal with
this level of detail
).
The first step is to map functions onto CLBs, especially
when two functions are to be placed in the same CLB. To make the best use
of the CLB's inputs, we should try to place functions of the same inputs
in the same CLB. For example,
H1 and
H0 are both functions
of
TS,
Q1, and
Q0. These two functions can easily
be placed in the same CLB.
A second goal is to minimize the amount of inter-CLB
routing. For example, it makes sense to place
P0 and
F1
in the same CLB, because the latter is simply a function of the former.
The remaining function,
F0, is placed in a CLB by itself.
The second step maps the five CLBs onto the array to
make best use of direct interconnect and minimum use of global interconnect.
We begin by placing the CLB for
Q1, since both its outputs
X
and
Y will carry the same value. By placing other CLBs above, below,
and to the right of this CLB, we can make good use of many direct connections.
Figure 10.51 shows one possible CLB placement and the routing of the
inputs and state outputs. The
Q1 CLB is placed in the center at
the left. Through direct connections, it drives the
D input of
F0's CLB, the
A input of
ST's CLB, and the
B
input of the
H1,0 CLB. The
Q0 CLB is placed in the upper
right-hand corner. It uses direct connections to drive the
A input
of the
H1,0 CLB.
We must use general-purpose interconnections to get
Q1
to the
Q0 CLB and
Q0 to the left-hand column of CLBs.
The
X output of the
Q1 CLB can be connected to the first
vertical track. This is routed up through the switching matrix. The
B
input on the
Q0 CLB can be connected to this wire.
This interconnection illustrates some of the constraints
on the -general-purpose connections. The
X output can be connected
only to -vertical tracks 1 and 4
(numbered from left to right
),
while the
B input can be connected only to vertical tracks 1, 3,
and 5, as well as horizontal tracks 1 and 5 in the channel below the CLB.
It is not possible to wire up any input or output to any track.
The distribution of
Q0 is somewhat more complicated.
It is initially connected to the third wire of the horizontal channel below
its CLB. The middle switching matrix splits the signals onto the fourth
vertical routing track while simultaneously passing it through on the third
horizontal wire. Let's follow the horizontal distribution first. The
A
input of
Q1's CLB can connect to this wire
(as well
as the first horizontal track and the first and third vertical tracks of
the channel to its left
). The next switching matrix routes
the wire to the third vertical track, where it can be connected to the
E
input
(E can also be connected to the fifth vertical
track and the fifth horizontal track below it
).
Now returning to the vertical distribution of
Q0,
it passes through another switching matrix, which routes it onto the third
vertical track. Since the
ST CLB's
A input is already
directly connected to
Q1, we have to route
Q0 to the vertical
channel to the left of the CLB. The next switching matrix places the signal
on the fourth vertical track. From here it can be connected to the
D
input
(which can also be wired to the third horizontal track
below it
).
The rest of the routing details are to get the
C,
TL, and
TS signals to the appropriate CLB inputs.
TS
is routed along the fifth vertical track in both of the vertical channels
shown in the figure. To keep the routing regular, we wire the
C
input to this track in each of the CLBs
(C can be
wired to vertical tracks 2, 4, and 5 and horizontal tracks 3 and 5 from
the channel above the CLB
), except
Q0's CLB. Recall
from Figure 10.39 that if an internal flip-flop's output is to be used in
computing a function, then one of the
B or
C inputs cannot
be used.
C and
TL are needed only in the computation
of
Q0 and
ST, so we only route them through the leftmost
vertical track.
C follows the fourth and then the third vertical
track, from which it can be wired to
Q1's
D input and
ST's
E input.
TL starts on the second track,
where it splits onto the first and third tracks by the first switching matrix.
This allows it to be connected to the
E input of
Q1 and
the
B input of
ST.
It is worth making a few extra points. First,
Q1's
B input is left floating. This is because the internal flip-flop's
output is used as an input to the internal function generator. Second, the
Q0 and
Q1 CLBs are connected to the global clock line,
and their clock enable inputs are wired to the fifth horizontal track. This
track carries the clock enable signal. The global reset signal puts the
state machine into its starting state.
In general, the designer need not see this level of detail.
So why bother to understand it? Routing decisions can have a serious impact
on performance, and no routing software is perfect, especially given the
complex constraints imposed on the routing task by the Xilinx architecture.
Each traversal of a switching matrix adds 1 to 3 ns to the signal delay.
The worst-case routing for
Q0 passes it through three switching
matrices, and this might represent the critical path in the circuit. By
working at the detailed level of the interconnection fabric, you can do
hand routing for critical signals or force them onto the smaller-delay long
line interconnections.
Counter/Multiplexer It is also
possible to think about our MSI implementation in terms of the primitives
supported by the Xilinx LCA. The basic elements of our MSI approach are
a four-to-one multiplexer and a 2-bit up-counter. Let's see how these map
into CLBs.
We begin with the multiplexer. A general-purpose four-to-one
multiplexer is a function of six variables: its four data inputs and two
control inputs. Fortunately, this is exactly the kind of six-variable function
that can be implemented by a single CLB. Think back to Figure 10.39
(c
).
The CLB can be configured as a two-to-one multiplexer, controlled by input
E, that selects among two functions of four variables. Of course,
each of these functions could be its own two-to-one multiplexer.
This is not the best solution, however. We need a second
CLB just to implement the terms
TL C and
TL +
for input to the multiplexer. On closer examination,
the function we want to implement is really five variables:
TL,
C, TS, Q1, and
Q0. We can implement
this in a single CLB.
Now consider the 2-bit counter that implements the state
register. A full-blown 74163 is not really needed: we never use the load
capability, and we can clear the counter using the global reset signal rather
than a specific clear input. Thus, each bit of the counter is a function
of three inputs: a count signal and the 2-bit current state. This too can
be implemented in a single CLB.
Finally, let's look at the logic to decode the six light
functions from the current state, as we did in the MSI example. All of these
functions are defined over two variables:
Q1 and
Q0. We
can pack two such functions per CLB, for a total of three additional CLBs.
By cleverly using MSI functions rather than discrete
gates, we came up with a five-CLB implementation, including the output decoders.
Many things you have learned about TTL MSI components remain valid in the
new programmable logic technology!
= { w | w ∈ ∑* and δ*(q0, w) 
A }
, 
, EN 
signal has precedence
over 
, which in turn has precedence over EN 
and 
should be unasserted 
is left unasserted
high, 
is asserted low, and EN can be a don't care. The value
to be loaded, 1 0 0, must be available on the C, B, A
signals. The collection of values fill out the ninth row of the state transition
table.
signal is asserted low,
while 
and EN can be don't cares. Rows 7 and 12 of the transition
table provide other examples of these "return to 0" transitions.
, 
, and EN. The espresso
input file is shown in Figure 10.22 and the resulting output file in Figure
10.23. 
signal for a control
function, we need a separate RESET input to place the finite state machine
in state 0 initially. Note that this is a synchronous reset; the reset on
the 74175 quad registers used in some of the finite state machine implementations
in this chapter is asynchronous. To be correctly "synchronous,"
we should include a reset signal as input to the ROM or PLA/PAL next-state
logic 
