# Electronic Legos

November 04, 2011

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>