Programmable logic devices
Inside an FPGA there are no AND or OR gates: there are 16- or 64-bit memories that store truth tables. An AND and the most tangled six-variable function take up the same space.
01From fixed circuit to programmable
With discrete 74-series gates, every design change means a new circuit board. A programmable logic device (PLD) reverses the order: the manufacturer sells an integrated circuit with many generic, unconnected logic resources, and the designer decides afterward, with a configuration file, what function each one performs and how they are connected to each other. The same chip can be a counter in the morning and a motor controller in the afternoon.
The Electronics Technician program’s page on memories and programmable devices introduces the idea. Here we look at how each type is built inside, why the FPGA ended up dominating, and how to get from an HDL file like those in the previous unit to a working chip.
02AND-OR arrays: PROM, PLA and PAL
Every combinational function can be written as a sum of products, so the first PLDs are two planes of gates: an AND plane that forms the products of the inputs and their complements, and an OR plane that sums them for each output. What distinguishes each family is which plane can be programmed:
| Device | AND plane | OR plane | Consequence |
|---|---|---|---|
| PROM | Fixed: all the minterms | Programmable | Any function, but the AND plane grows as \(2^n\): suitable only for few inputs |
| PLA | Programmable | Programmable | The most flexible, and the slowest and most expensive: two planes of fuses in series |
| PAL, GAL | Programmable | Fixed: each output sums a fixed number of products | Fast and cheap; if a function needs more products than are available, it does not fit |
The GAL is the PAL with electrically erasable cells instead of fuses, and it adds to each output a macrocell: a flip-flop that can be used or bypassed, a polarity control, and the ability to feed the output back to the AND plane. With that, a single GAL22V10 can hold a counter or a small state machine, and for years it was the logic glue of every board with a microprocessor.
03CPLD
A CPLD (complex PLD) puts several PAL-type blocks on the same chip and joins them with a central interconnect matrix. It inherits the virtues of the PAL:
- Nonvolatile: the configuration is held in EEPROM or flash cells and the chip works from the first microsecond after power-up.
- Predictable timing: every signal crosses the same matrix, so the input-to-output delay is almost the same for any path and is listed in the datasheet before designing.
Its limit is size: the sum-of-products structure does not scale beyond a few hundred macrocells. Today it is used for startup logic and power-supply sequencing, address decoding, and “glue” tasks where the logic has to be alive before everything else.
04FPGA: truth tables in memory
The FPGA (field-programmable gate array) abandons the sum of products. Its basic element is the LUT (look-up table): a small memory of \(2^k\) bits with \(k\) address inputs. By storing the desired truth table in it, the LUT implements any function of \(k\) variables with the same delay, whether it is an AND or the most tangled function:
With \(k = 4\) that is 16 configuration bits and 65,536 different functions; current families use 6-input, 64-bit LUTs. A function of more variables is split with the Shannon expansion, which separates according to one of the variables and selects with a multiplexer:
Each cofactor is a function of four variables, which fits in a LUT4, and the multiplexer that selects between them is built into the cell. Around the LUTs, the FPGA has:
| Resource | What it is |
|---|---|
| Logic block (CLB, LAB) | A group of LUTs, each with its flip-flop at the output, plus dedicated carry chains for fast addition |
| Interconnect | A grid of programmable wires and switches that takes up most of the silicon and contributes a good part of the delay |
| Block memory (BRAM) | Dual-port blocks of a few kilobits, for FIFOs, tables and buffers |
| DSP blocks | Hardwired multipliers and accumulators, for filters and signal processing |
| PLLs and clocks | Frequency synthesis and low-skew clock trees that reach every flip-flop |
| Input and output blocks | Pins configurable in voltage and standard: LVCMOS, LVDS, sometimes transceivers of several Gb/s |
On the left, the LUT’s 16 memory cells; on the right, the tree of multiplexers that selects one according to the inputs. You choose a function and the LUT is loaded with its truth table, or you click or tap a cell to flip that bit. The four inputs move the highlighted path to the output.
The configuration of all the LUTs, the interconnect switches and the special blocks forms the bitstream. In most FPGAs that configuration lives in SRAM cells: it is lost at power-off and the chip reads it again from an external flash memory at every power-up, which takes between a few milliseconds and a few tenths of a second. There are families with flash-based configuration, which start instantly, and with antifuses, programmable only once and radiation-resistant, for space use.
05Which one to choose
| PAL, GAL | CPLD | FPGA | |
|---|---|---|---|
| Structure | One AND-OR array | Several AND-OR arrays with a central matrix | Thousands to millions of LUTs with grid interconnect |
| Capacity | Tens of gates | Hundreds to a few thousand | Thousands to millions of cells |
| Configuration | Nonvolatile | Nonvolatile | Almost always SRAM, loaded at power-up |
| Delay | Fixed | Fixed and predictable | Depends on placement and routing: it has to be analyzed |
| Typical use | Replacing discrete logic, legacy equipment | Startup, decoding, power-supply sequencing | Signal processing, video, communications, integrated-circuit prototypes |
06From HDL to chip
The manufacturer’s tool takes the description to the device in stages, and each one can fail on its own:
- Synthesis: translates the HDL into a network of generic gates, flip-flops, adders and memories. This is where unwanted latches and optimized-away registers show up.
- Mapping: distributes that network among the device’s resources: LUTs, flip-flops, BRAM, DSP.
- Placement and routing (place and route): chooses which physical cell each element goes in and which wires connect them. It is the slowest stage, and the one that decides the delays.
- Timing analysis: adds up the delays of each path between flip-flops and compares them with the clock period requested in the constraints file. If any path falls short, you have to redesign or lower the frequency, just as with the critical path in the sequential logic unit.
- Bitstream: generates the configuration file and loads it into the chip or its flash.
The constraints file is as much a part of the design as the HDL: it assigns each signal to a pin, sets its electrical standard and declares the frequency of each clock. Without it the tool places the pins at random and does not know what speed it has to meet.
07Where it shows up in electronics
| Case | Why a programmable device |
|---|---|
| Board with a microprocessor | A CPLD generates the chip selects and the power-up order of the supplies |
| Software-defined radio | The FPGA filters and demodulates in parallel samples that arrive at hundreds of millions per second |
| Cameras and video | It receives the sensor, corrects each pixel and converts between interfaces in real time |
| Control of power converters | It generates PWM with nanosecond resolution and protections that act within one cycle |
| Integrated-circuit design | The design is tested on an FPGA before paying for the ASIC fabrication |
| Equipment updated in the field | A new bitstream changes the hardware without changing the board |
08In the lab
With an inexpensive board (those of the iCE40 family work with open-source tools: Yosys, nextpnr and icestorm), describe a counter that makes an LED blink at 1 Hz from the board’s clock. Write the pin file, synthesize, load it and measure the frequency with the oscilloscope.
Synthesize the sequence detector from the previous unit and note how many LUTs and how many flip-flops it uses. Change the state assignment to one-hot and compare the two figures.
Synthesize a 32-bit adder between registers and request an ever higher clock frequency until the timing analysis fails. Open the report and locate the path that falls short: it should be the carry chain.
09Common mistakes
- Forgetting the constraints file. The pins end up wherever the tool wants and the timing analysis does not know what frequency to check.
- Accepting a design as good because it simulates. If the timing analysis shows paths that fall short, on the board it will fail intermittently.
- Generating clocks with logic. Dividing the clock with a counter and using that output as the clock of other flip-flops breaks the clock tree; use the PLL or a clock enable.
- Assuming the FPGA starts instantly. An SRAM FPGA takes time to load its configuration, and in the meantime its pins do not do what the design says.
- Counting gates instead of LUTs. A two-input AND and a complicated six-input function take up the same thing: one LUT.
10Self-assessment
Which plane is programmable in a PAL and which in a PROM?
In the PAL the AND plane is programmed and the OR plane is fixed; in the PROM the AND plane is fixed (it generates all the minterms) and the OR plane is programmed.
How many bits does a six-input LUT have and how many different functions can it implement?
\(2^6 = 64\) bits, and \(2^{64}\), about \(1.8 \times 10^{19}\), different functions.
What configuration value (INIT) does a LUT4 loaded with an AND of its four inputs have?
Only address 1111, number 15, is 1: the value is 16'h8000.
Why does a CPLD have more predictable delays than an FPGA?
Because every signal crosses the same central interconnect matrix; in the FPGA the delay depends on where the tool placed each cell and on the wires it chose to join them.
What happens to the configuration of an SRAM-based FPGA when the power is cut?
It is lost. When power returns, the chip reads the bitstream from an external flash memory, and until it finishes it does not perform the designed function.
11Further reading
- Clive Maxfield. The Design Warrior's Guide to FPGAs. Newnes, 2004. The history of PLDs and the architecture of FPGAs told from the inside, in plain language.
- Stephen Brown and Zvonko Vranesic. Fundamentals of Digital Logic with VHDL Design. 3rd ed., McGraw-Hill, 2009. PLA and PAL arrays and the structure of LUTs, with the Shannon expansion applied to their synthesis.
- Pong P. Chu. FPGA Prototyping by Verilog Examples. Wiley, 2008. The complete flow, from HDL to the board, with constraints, timing analysis and real peripherals.