Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 57 ยท Memory and Programmable Logic

PLAs, FPGAs and Lookup Tables

See how programmable logic works: PLA and PAL AND-OR planes, lookup tables, FPGA logic elements and routing, plus a Python LUT mapper that implements any 4-input function.

Every circuit you have designed so far was fixed the moment you chose its gates. To change it, you rebuild the hardware. Programmable logic removes that limit: the chip contains a large, regular supply of logic resources, and you decide how they are connected after manufacturing. The same chip can be a UART today and a video controller tomorrow.

In this lesson we follow the idea from its simplest form (the PLA and PAL, a programmable AND-OR array) to the lookup table (LUT) that powers every modern FPGA. We finish with the central trick of FPGA software: mapping a Boolean function, even one with more than four inputs, onto four-input LUTs. This builds on what you saw in ROM, RAM and Memory Organization: a ROM is a stored truth table, and a LUT is a tiny ROM.

A family of programmable chips

PLA / PAL A programmable AND-OR array.
CPLD Several PLA-like blocks on one chip.
FPGA Thousands of LUTs and flip-flops.
ASIC Fixed custom chip. Cheapest at volume.
1 / 2

The PLA: programmable sum of products

Remember that any Boolean function can be written as a sum of products: AND gates produce product terms, an OR gate adds them. A programmable logic array (PLA) is a chip built exactly that way, with every connection programmable:

  • The AND plane can form product terms from any input or its complement. For each product term you choose which literals take part.
  • The OR plane can add together any set of those product terms to build each output.

Since product terms are shared, a PLA can produce several outputs from one set of terms. Programming a PLA means filling a table: one row per product term, with 1 (use the input), 0 (use the complement) or - (input not used), plus a column per output that says whether the row feeds that output.

A PAL (programmable array logic) is a cheaper variant: the AND plane is programmable but the OR plane is fixed, so each output can use only a fixed number of product terms (say 4 or 8). A function with more terms than that does not fit, no matter how many terms are free elsewhere.

Here is a full adder in PLA form. With inputs a b c the sum is a'b'c + a'bc' + ab'c' + abc and the carry is ab + ac + bc. The model evaluates the planes exactly as the hardware would.

Python A PLA and a PAL capacity check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the sum needs four terms because the XOR of three variables has no simplification. A PAL limited to three terms per output could not build this adder's sum without help.

Lookup tables

PLAs grow quickly with the number of inputs because the AND plane must be able to form any product of them. Modern FPGAs choose a different building block: the lookup table. A k-input LUT is a tiny memory with 2^k one-bit cells. The k inputs are the address, and the stored bit is the function's value. A 4-input LUT holds 16 bits.

The lookup table is exactly the ROM of the previous lesson with a one-bit word. The key consequence is that a k-input LUT can implement every Boolean function of k variables: you just fill the 16 cells with the truth table. How many such functions are there? Each of the 16 cells can be 0 or 1 independently, so 2^16 = 65,536 functions, and a 16-bit number (the configuration) selects among them. The shape of the logic does not matter, because a LUT does not contain gates at all. Complicated, simplified or unsimplified, all functions take one LUT and the same delay.

Python A 4-input LUT holds any function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The mux entry shows that the LUT does not care that d is ignored: unused inputs simply do not change the table. A 3-input function takes a LUT4 with one input tied to a constant.

The FPGA fabric

A field-programmable gate array (FPGA) is a sea of logic elements connected by programmable wiring. A typical logic element contains:

  • one LUT (4 or 6 inputs) that computes a function,
  • one D flip-flop that can store the result,
  • a multiplexer that picks either the LUT output or the flip-flop output.

Around the logic elements sit a programmable routing network (switches that connect the output of one element to the inputs of others), I/O blocks that talk to the pins, and often hard blocks such as block RAM, multipliers and clock managers. The LUT contents, the multiplexer settings and every routing switch are bits in configuration memory, mostly SRAM. Loading these bits, the bitstream, is what "programs" the FPGA, and because SRAM is volatile the bitstream is loaded again at every power-up.

The following model builds two logic elements, gives each a LUT and a flip-flop, wires the outputs back to the inputs, and so turns the pair into a 2-bit counter. There are no gates; the design lives entirely in the configuration bits.

Python Two logic elements make a 2-bit counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The counter counts 0, 1, 2, 3, 0, 1, ... The same two logic elements could be reconfigured into a different circuit by writing different LUT contents and different routing. That is the entire point of an FPGA.

From a design to LUTs: the synthesis idea

Nobody fills in LUTs by hand. A designer writes the circuit in a hardware description language and software does the rest:

flowchart LR
    HDL["HDL design"] --> SYN["Synthesis<br/>to gates and flip-flops"]
    SYN --> MAP["Technology mapping<br/>to LUTs"]
    MAP --> PNR["Place and route<br/>on the chip"]
    PNR --> BIT["Bitstream"]
    BIT --> CHIP["FPGA"]

Mapping decides what goes in each LUT. Place and route decide where each LUT sits and how the wires run.

Technology mapping is the step that fits the logic into LUTs. A function with 4 or fewer inputs takes one LUT. A larger function has to be split. One simple method is Shannon expansion: choose a variable v and write f = v' f0 + v f1, where f0 and f1 are f with v set to 0 and 1. Each cofactor has one input fewer. Repeat until each piece has at most 4 inputs, then combine the pieces with a 2:1 multiplexer (itself a 3-input function, so one LUT). Real mappers are cleverer and share logic, but this method always works.

Python Map a 6-input function onto 4-input LUTs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output shows the price of the simple method: seven LUTs for any 6-input function, whatever it is. The last line of the program points out that a mapper that looks at the function's structure does far better. For parity, the structure is a chain of XORs, so two LUTs are enough. Real FPGA tools hunt for exactly this kind of saving.

Choosing: ASIC, FPGA or microcontroller

An FPGA is slower, larger and uses more power than a custom chip (ASIC) made for the same job, but it costs nothing to change and has no fabrication wait. It is ideal for prototypes, low-volume products and tasks that need massive parallelism. A microcontroller, in contrast, runs software on a fixed processor: cheap and easy, but each instruction takes time. Digital designers choose the point on this spectrum where cost, speed and flexibility balance.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which part of a PAL is fixed rather than programmable?

    A PAL has a programmable AND plane and a fixed OR plane. That is why each output can use only a limited number of product terms.
  2. 2. How many different Boolean functions can a 4-input LUT implement?

    A 4-input LUT has 16 memory cells that can each hold 0 or 1 independently, so there are 2^16 = 65,536 possible truth tables.
  3. 3. What does the bitstream of an SRAM-based FPGA contain?

    The bitstream fills the configuration memory: LUT contents, logic-element options and routing switches. Because SRAM is volatile, it is loaded at every power-up.
  4. 4. A logic element's LUT output is stored in its flip-flop. What does that make possible?

    With the flip-flop in the path, the logic element can hold state. Feedback from flip-flop outputs to LUT inputs makes counters and state machines.
  5. 5. How does Shannon expansion help to map a 6-input function onto 4-input LUTs?

    f = v' f0 + v f1. Each cofactor has fewer inputs, and a 2:1 multiplexer picks between them. Repeating the split reduces any function to LUT-sized pieces.

Summary

  • A PLA has a programmable AND plane and a programmable OR plane; a PAL fixes the OR plane and limits product terms per output.
  • A k-input LUT is a tiny ROM with 2^k cells and implements any function of k variables, so a 4-input LUT can be one of 65,536 functions.
  • An FPGA is an array of logic elements (LUT, flip-flop and a multiplexer) plus a programmable routing network, configured by a bitstream.
  • Synthesis turns an HDL design into gates, technology mapping fits the logic into LUTs, and place-and-route positions and wires them.
  • Shannon expansion maps any larger function onto LUTs; smarter mapping exploits the function's structure to use fewer.

Next: Hardware Description Languages (Verilog and VHDL).