The next three combinational components we will study are: ROM, PLA, and PAL.

ROM's PLA's and PAL's are storage Components. This might seem like a
contradition because earlier we said that combinational components don't have memory. This
apparent contradiction results from an incomplete definition of the term combination
component. A more precise definition is: a combinational component is a circuit that
doesn't have memory *of past inputs*. (The outputs of a combinational component are
completely determined by the current inputs.) The data in the storage components we are
about to study are stored at design time before the component is added to a circuit. The
data stored in sequential circuits comes from the inputs that are received while the
component is active in the circuit.

The storage components that are the topic of this lecture can be used to implement Boolean functions. This may also be the most efficient implementation. If the function is moderately complex a SSI implementation (individual gates) may be expensive in terms of the number of gates that have to be purchased and in terms of the number of connections required to wire them together. When a function is implemented inside a ROM, PLA, or PAL there is only one IC to purchase and fewer connections.

A ROM is a combinational component for storing data. The data might be a truth table or the data might be the control words for a microprogrammed CPU. (This is a topic we will discuss later. Control words in a microprogrammed CPU interpret the macro instructions understood by the CPU.)

A ROM can be programmed at the factory or in the field.

The following image shows the generic form of a ROM:

An n x m ROM can store the truth table for m functions
defined on log_{2}n variables:

Example: Implement the following functions in a ROM:

F_{0} = A

F_{1} = A'B' + AB

Since a ROM stores the complete truth table of a function (or you could say that a ROM decodes every minterm of a function) the first step is to express each function as a truth table.

A B |
F_{0} F_{1} |

0 0 | 0 1 |

0 1 | 0 0 |

1 0 | 1 0 |

1 1 | 1 1 |

For the discussion that follows it may be helpful to keep in mind the canonical form of the function also:

F_{0} = AB' + AB

F_{1} = A'B' + AB

We use a special notation to show the ROM implementation of a function:

The image above shows how a 4x3 ROM can be used to
implement the two functions F_{0} and F_{1}. (Note, there is room in the
ROM for 3 functions of two variables. F_{2} isn't used. I'm showing a ROM with an
unused portion to demonstrate that a ROM may still be the most efficient implementation
even when large sections of the ROM go unused.) You can imagine a decoder inside the ROM
that decodes the inputs A B. Just like the decoder we defined earlier, one output line is
selected for every unique set of inputs. If the selected output line is connected to an OR
gate the function associated with the OR gate will have a value of 1 for the particular
set of inputs.

Note: the image above also shows a new way to indicate multiple connections with a single line. For example:

A single vertical line that intersects 4 horizontal lines represents potentially 4 different lines or connections. This is a notational convenience we will use when talking about ROM's, PLA's, and PAL's because it makes the diagrams much easier to read.

The circles at the intersection of two lines indicates a connection. Connections are either formed at the factory or in the field. If they are formed in the field a special programmable ROM is used. One type of programmable ROM is a ROM that has a fuse at every connection. Fuses at connections not wanted are burned by running high current through the fuse. What is left are the connections that define the data within the ROM.

**Observations**

Not very efficient implementation of sparse functions.

A ROM that implements two functions does not require twice the number of gates as a ROM that implements one function. (The decoder is shared by every output function.)

*Extra for Experts*

ROMs programmed at the factory are called mask ROMS because during fabrication the circuit patterns are determined by a mask. There are several different types of field programmable ROMS:

o PROM (Programmable Read-Only Memory) - This is the type that was discussed above. Connections are fused and burned in the field with a PROM programmer.

o EPROM (Erasable Programmable Read-Only Memory) - This type of ROM can be re-written by shining an ultraviolet light through a window on the IC.

o EEPROM (Electrically Erasable Programmable Read-Only Memory) - Rather than ultraviolet light an extra high voltage is used to re-write the contents of this type of ROM.

o Flash Memory - Instead of requiring extra high voltages flash memory devices work with regular device voltages.

A programmable logic device works like a ROM but is a more efficient solution for implementing sparse output functions. (Not all minterms are decoded.)

There are two types of programmable logic devices:

- PLA (Programmable Logic Array)
- PAL (Programmable Array Logic)

We suggested earlier that a ROM had a decoder inside it. You could visualize this as:

The image above also defines two terms we will use to distinguish between PLA and PAL devices:

AND Array - this is the portion of the device that decodes the inputs. The AND array determines the minterms decoded by the device. A ROM decodes all possible minterms.

OR Array - this is the portion of the device that combines the minterms for the definition of a function.

**PLA**

Now we are ready to define a PLA.

A PLA is a programmable logic device with a programmable AND array and a programmable OR array.

A PLA with n inputs has fewer than 2^{n} AND
gates (otherwise there would be no advantage over a ROM implementation of the same size).
A PLA only needs to have enough AND gates to decode as many unique terms as there are in
the functions it will implement.

Because we can control the AND array and there is a
limit to the number of terms that can be specified in the AND array, it may be more
economical to simplify the function before implementing it with a PLA. If you do simplify
the function and intend to implement with a PAL device you should also keep in mind that
product terms can be shared between functions. (Product sharing is when two functions
share a product term decoded by the AND array. For example, in the image below the product
term AB is shared between F_{0} and F_{1}.)

Example: Implement the functions F_{0} F_{1}
we introduced above using a PLA with 2 inputs, 3 product terms, and 2 outputs.

The unprogrammed PLA from the manufacture looks like:

After programming for the two functions F_{0} F_{1}
the state of the PLA is:

Notice that we only need three AND gates because there
are only three unique minterms in the functions F_{0} and F_{1}. Also,
notice that since we have control over the OR array we can share the minterm AB in the
definitions of both functions.

Note, there may be an advantage to simplifying the
functions before implementing. In the example used here there is no advantage. The
simplified form of the functions F_{0} and F_{1} still require 3 unique
product terms. Because product terms can be shared between functions its important to look
for common product terms when simplifying.

**PAL**

A PAL is a programmable logic device with a programmable AND array and a fixed OR array.

A PAL has a fixed OR array. For example, here is what an unprogrammed PAL might look like straight from the manufacture:

A fixed OR array makes the device less expensive to manufacture. On the other hand, having a fixed OR array means you can't share product terms between functions.

Example: Implement the functions F_{0} F_{1}
we introduced above using the PAL given above.

For this implementation we will need to simplify the
functions F_{0} F_{1} because the PAL we are given has an output function
that can accommodate only one product term. The simplified form of the functions are:

F_{0} = A

F_{1} = A'B' + AB

After programming for the two functions F_{0} F_{1}
the state of the PAL is:

So, in summary:

- A PLA device has a programmable AND and programmable OR array
- A PAL device has a programmable AND and fixed OR array
- (You could also say that a ROM has a fixed AND and programmable OR array)

When implementing with a ROM there is no advantage to minimizing the functions since the input is fully decoded. When implementing with a PLA there may be an advantage to minimizing the expression but you also have to keep in mind that product terms can be shared between functions. So, when you are minimizing one function you need to consider the form of other functions and watch for product terms that can be shared. When implementing with a PAL there may also be some advantages to minimizing the function first. However, since you can't share product terms with a PAL you don't have to consider the form of other functions when minimizing.