Electronic Legos

Last week I started talking about how programmable logic devices have become accessible enough that they are finding their way into all sorts of embedded systems. There are actually quite a few types of programmable devices. You can think of these chips like a child’s construction kit: There are a lot of pieces. You can build an airplane, or a truck, or a house, or anything else by snapping pieces together in different ways. However, each type of device has its own peculiarities, and this time I wanted to look at what’s available.

Regardless of the type of device, they all have some similarities. Perhaps the simplest programmable logic device is a memory chip (like an EPROM or a flash memory). Suppose you have a memory chip that has 256 bytes of memory (that is, it has 8 address lines and 8 data lines). You could think of that chip as an 8-input “truth table.” It could emulate any combination of AND, OR, and NOT logic that had 8 inputs and 8 outputs. A stupid example would be if you wanted to program the chip to be an inverter. You’d simply program the following into the chip:

00000000 -> 11111111
00000001 -> 11111110
. . .
11111111 -> 00000000

With that program, any 8 bits you put in, get inverted at the output. You could just as easily build, say, a 2-bit full adder (a binary adder that has both a sum and carry output). To make it simple, assume the memory device only has two address bits (4 words) and 2-bit words. Otherwise, I’ll have to make a big table. The adder would look like this:

00 -> 00
01 -> 10
10 -> 10
11 -> 01

The leftmost output bit is the sum and the rightmost is the carry. If you notice, the sum bit is really an exclusive or (one bit or the other but not both). In general, anything you can describe as combinatorial (or combinational) logic. That is, a combination of and, or, and invert operations. The real key is that the outputs of a combinatorial circuit depend only on the state of the inputs. If the output depends on previous outputs, that’s a different kind of logic.

In theory, you could represent logic that has previous output dependency (sequential logic) using a memory chip, but in practice it’s usually done differently. But for now, the key idea is that a memory device can simulate an arbitrarily complex combinatorial logic equation.