ROM's and Programmable Logic

Introduction

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.

ROM

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:

rom.gif (17764 bytes)

An n x m ROM can store the truth table for m functions defined on log2n variables:

rom-as-tt.gif (11348 bytes)

Example: Implement the following functions in a ROM:

F0 = A

F1 = 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 F0 F1
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:

F0 = AB' + AB

F1 = A'B' + AB

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

rom-imp.gif (52425 bytes)

The image above shows how a 4x3 ROM can be used to implement the two functions F0 and F1. (Note, there is room in the ROM for 3 functions of two variables. F2 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:

combine-lines.gif (23004 bytes)

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

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.

Programmable Logic

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:

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

and-n-or-array.gif (14335 bytes)

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

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 2n 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 F0 and F1.)

Example: Implement the functions F0 F1 we introduced above using a PLA with 2 inputs, 3 product terms, and 2 outputs.

The unprogrammed PLA from the manufacture looks like:

new-pla.gif (14603 bytes)

After programming for the two functions F0 F1 the state of the PLA is:

pla-imp.gif (11438 bytes)

Notice that we only need three AND gates because there are only three unique minterms in the functions F0 and F1. 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 F0 and F1 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:

new-pal.gif (29424 bytes)

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 F0 F1 we introduced above using the PAL given above.

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

F0 = A

F1 = A'B' + AB

After programming for the two functions F0 F1 the state of the PAL is:

pal-imp.gif (40955 bytes)

So, in summary:

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.