Programmable Arrays of Logic Gates

Integrated circuit (IC) manufacturers have been phenomenally successful in packing millions of transistor switching elements into microcomputers. We see how this technology can be exploited to reduce the component count of the digital system in this section.

4.1.1 Motivation for Programmable Logic

The key is to find logic building blocks that are sufficiently general purpose to be used in many designs. It is easy to identify generally useful building blocks with primitive structures, such as a handful of gates imple-menting an AND-OR-Invert structure. But such building blocks reduce the component count by only a modest amount. We could get a significant reduction if we could use a building block that contained the equivalent of hundreds of gates. But what should this building block look like?

The ingenious solution to this dilemma is to arrange the AND and OR gates (or NOR or NAND gates) into a generalized array structure whose connections can be personalized or programmed to implement a specific function. Such general-purpose logic building blocks are called PALs (programmable array logic) or PLAs (programmable logic arrays).

4.1.2 PALs and PLAs

Figure 4.1 shows a general block diagram for an array logic component. Such components are multi-input/multi-output devices, typically organized into an AND subarray and an OR subarray. The AND subarray maps the inputs into particular product terms, depending on the programmed connections. The OR subarray takes these terms and ORs them together to produce the final sum of products expression.

Example A PLA device can implement a modest collection of functions of considerable complexity. This complexity is determined by the number of inputs, the number of product terms (number of AND gates), and the number of outputs (number of OR gates) that the PLA can -support.
For example, a typical TTL field-programmable logic array (FPLA) might have 16 inputs, 48 product terms, and 8 outputs. In a package with 24 data pins, this PLA contains the equivalent of forty-eight 16-input AND gates and eight 48-input OR gates. When you consider that a 12-data-pin SSI package gives you only four 2-input gates, you can see the real package efficiency of array logic.

Suppose you want to implement the following Boolean equations, defined for A, B, and C:

We can characterize them by the number of variables (A,B,C), the unique product terms (A, , , , ), and the functions (F0, F1, F2, F3). These correspond to the number of inputs to the AND array, the number of outputs from the AND array (which are the inputs to the OR array), and the number of outputs from the OR array. To implement these functions, you would need (at least) a 3-input, 5-product term, 4-output PLA device.

A convenient way to describe the functions is by a personality matrix, a minor reformulation of the truth table, shown in Figure 4.2. It describes which input literals should be connected to each AND gate to form the desired product term (1 = asserted variable, 0 = complemented variable, - = no connection), and which of these should be ORed together to form the final outputs (1 = connect product term to OR, 0 = no connection). Rows determine product terms; columns represent inputs and outputs. A product term participates in more than one function if there is more than one 1 in its row in the personality matrix's output columns.

In Figure 4.2, it is easy to see that , , and A are used by more than one function.

Gate-Equivalent Representation Figure 4.3 and Figure 4.4 show gate-equivalent diagrams of the implementation of our example functions in programmable array logic. Figure 4.3 shows the array before programming, with all possible connections between inputs and gates prewired "at the factory." You personalize the array by using a hardware device called a programmer.

The details of the programming process depend on the particular integrated circuit. A frequently used technique places fuses between all possible inputs to a gate and the gate itself. A fuse is an electrical connection specially designed to break down or "blow" under high current. By placing a high current across selected fuses, the programmer hardware breaks those connections. The programmer software analyzes your Boolean equations to determine which fuses should be blown and which should be left alone. Figure 4.4 shows the same array after it has been personalized.

Figure 4.5 gives a commonly used notation for representing the topology of array logic. You should interpret the single wires entering the AND and OR gates as representing multiple inputs. The X's represent the fuse locations.
Example Now let's consider the design of a function generator of three inputs. The circuit should implement the logic functions AND, OR, NAND, NOR, XOR, and XNOR:

Figure 4.6 shows how this collection of functions is implemented in a PLA. The terms ABC and are shared among more than one output function. ABC is used to implement F1, AND, and F5, XOR, while is used by F4, NOR, and F6, XNOR.

4.1.3 The Difference Between PLAs and PALs

Figure 4.5 implies that both the AND and OR subarrays can be personalized in any way the designer wants. Devices with this generality are called programmable logic arrays (PLAs).

However, not all programmable logic supports full programmability. For instance, Monolithic Memories' programmable array logic (PAL) devices have a programmable AND array, but the connections between product terms and specific OR gates are hardwired. The number of product term inputs to an OR gate is usually limited to 2, 4, 8, or 16.

There is a fundamental trade-off in PAL devices between the complexity of the functions in terms of the product terms per OR gate and the number of independent functions the device can implement. The higher the OR gate fan-ins, the fewer the functional outputs from the PAL.

For example, a PAL family might include three alternative devices, each with 16 inputs and 16 product terms, but differing in their OR array organization: four OR gates with 4 inputs each, two OR gates with 8 inputs each, and one OR gate with 16 inputs. The AND subarrays remain completely programmable. Figure 4.7 shows a 4-input/4-product-term/2-output PAL organization with a particular fixed choice for the OR array. In this case, the OR gates are limited to two product terms each.
The key difference between PLAs and PALs is that the former can take advantage of shared product terms and the latter cannot. Let's think back to the function generator design of the previous subsection. Since no product terms can be shared among the PAL outputs, the functions need a PAL that can compute 16 product terms (, are duplicated). A PLA needs to compute only 14 product terms, the number of unique terms. For devices with comparable internal resources, a PLA should be able to implement a more complex collection of functions than a PAL if many product terms are shared.

On the other hand, the PLA will be slower because of the relative resistances of programmable and hardwired connections. Programmable, fuse-based connections have higher resistance than standard wired connections. Thus, signals pass through two programmable connections in the PLA, incurring worse delays than the single programmable connection in the PAL.

4.1.4 Design Examples

We examine two different design examples in this subsection, a code converter and a magnitude comparator. They illustrate the various alternatives for implementing combinational logic in terms of PALs, PLAs, or multilevel logic.

BCD-to-Gray-Code Converter In this example, we will design a code converter that maps a 4-bit BCD number into a 4-bit Gray code number. Each number in a Gray code sequence differs from its predecessor by exactly 1 bit. The circuit has four inputs, A B C D, representing the BCD number, and four outputs, W X Y Z, the 4-bit Gray code word.

The truth table and K-maps for the translation logic are shown in Figure 4.8 and Figure 4.9, respectively.

The prime implicants are circled in Figure 4.9, resulting in the following reduced equations:



Since there are no shared product terms, these functions are best suited for a PAL implementation. The implementation is shown in Figure 4.10.

The PAL contains four 4-input OR gates. You can see that many of the AND gates are being wasted. The same function could be implemented with a less complex PLA, but it would be slower.

The programmable logic approach implements the functions in a single integrated circuit package. Let's consider an equivalent implementation with discrete TTL gates. We will restrict ourselves to NAND gates and inverters only.

The resulting discrete gate circuit is shown in Figure 4.11.

The figure included a parts list at the lower right. We have labeled gates from the same package with the same number. The circuit uses 15 gates partitioned across five packages. Clearly, the programmable logic approach has a big advantage. Of course, only one of the four gates in package 5 is being used, leaving three gates that could be used by other circuits.

Two-Bit Magnitude Comparator Our next task is to design a comparator circuit. The circuit takes two 2-bit binary numbers as inputs, denoted by AB and CD, and computes the four functions AB = CD (EQ), AB ¦ CD (NE), AB < CD (LT), and AB > CD (GT).

Figure 4.9 shows the K-maps for the four functions with boxed prime implicants. This yields the following reduced equations for the output functions:

The functions use 14 product terms, of which 2 terms ( and ) are used twice. Because product terms are shared, a PLA-based implementation is more attractive than the PAL-based method. The programmed PLA is shown in Figure 4.10.

This single-chip implementation compares very favorably with a multichip implementation formed using TTL SSI gates.

It is not unusual for a PAL or PLA implementation to replace 5 to 15 TTL packages of 10 to 30 gates. This is why many real-world designs make extensive use of programmable logic devices. It is an effective way to reduce an implementation's component count and thus its manufacturing costs as well.