Combinational logic and look-up tables

Everything an FPGA does with data is built from two kinds of circuit: logic that has no memory and produces an output as soon as its inputs settle, and registers that hold a value until the next clock edge. This lesson covers the first kind, called combinational logic, and the hardware element that implements it, the look-up table. It assumes you have read lesson 01 and nothing more. Lesson 04 covers the registers.

Boolean functions and truth tables

A combinational circuit maps a set of input bits to a set of output bits, with no dependence on anything that happened earlier. Give it the same inputs and you get the same outputs, every time, after a short delay. The mathematics behind it is Boolean algebra, with three basic operations: AND (output 1 only if all inputs are 1), OR (output 1 if any input is 1) and NOT (invert). Two derived operations turn up constantly: XOR (output 1 if an odd number of inputs are 1) and the multiplexer, which is covered later.

The most direct way to describe a Boolean function is to list its output for every possible input. That list is a truth table. For a function of n inputs there are 2 to the power n rows. Here is a 3-input function, the majority function, whose output is 1 when at least two of its inputs are 1:

a	b	c	majority
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Read the output column top to bottom and you get the 8-bit string 00010111. That string is the function. Any other 3-input function is a different 8-bit string, and there are 2 to the power 8, which is 256, possible strings, so there are exactly 256 distinct 3-input Boolean functions. Written as an expression, majority is (a AND b) OR (b AND c) OR (a AND c), but the table and the expression carry the same information.

This observation is the key to the whole lesson. A Boolean function of n inputs is nothing more than a string of 2 to the power n bits. If you can store that string and select one bit of it using the inputs as an address, you have implemented the function.

The look-up table

That is exactly what a look-up table (LUT) is: a small memory whose address lines are the function’s inputs and whose stored contents are the truth table’s output column. A 4-input LUT is a 16-bit memory and can implement any one of 65,536 possible functions. A 6-input LUT is a 64-bit memory and can implement any of 2 to the power 64 functions, about 18 quintillion. The contents are written once, when the bitstream is loaded, and then the LUT behaves as pure combinational logic for the life of the configuration.

Follow the diagram with an example. Suppose the inputs are a=1, b=0, c=1, d=1. The first column of multiplexers uses d to pick the odd-numbered bit of each pair, the second column uses c to pick between pairs, the third uses b, and the final multiplexer uses a. Together they select the bit at address 1011, which is row 11 of the table, counting from 0. In the XOR example that bit is 1, since three of the four inputs are 1. The circuit has looked up the answer rather than computed it, and the delay is the same for every function, typically a few hundred picoseconds in a modern device.

The consequences for you as a designer:

• A LUT does not care how complicated the function is. A 6-input XOR and a 6-input AND cost the same: one LUT, one delay.
• A function of 7 or more inputs needs more than one LUT, in two or more levels, and each level adds delay. A 12-input function needs at least three 6-input LUTs in two levels. The number of LUT levels on a path, not the number of gates you imagine, is what sets its speed.
• A function with fewer inputs than the LUT has wastes the spare inputs, which is why modern devices let one 6-input LUT be split into two 5-input LUTs that share inputs.

AMD devices from the 7 Series onward use 6-input LUTs. Altera’s Stratix, Arria, Cyclone and Agilex families use an adaptive logic module that behaves as one 6-input LUT or two smaller ones. Lattice iCE40 and ECP5 use 4-input LUTs, which is why an ECP5 “LUT count” is not directly comparable to an Artix 7 one. A rough rule is that one 6-input LUT does the work of about 1.5 to 2 4-input LUTs.

Carry chains

Addition is the one function a LUT handles badly. A 4-bit adder’s most significant sum bit depends on all 8 input bits, and a 32-bit adder’s top bit depends on all 64, which would need many levels of LUTs. Every logic block therefore includes a dedicated carry chain: a fast, narrow path that passes the carry from each bit position to the next without going through the general routing. Each bit of the sum uses one LUT (to compute the propagate and generate signals) and one carry cell, and the carry ripples up the chain at a few tens of picoseconds per bit. A 32-bit adder in an Artix 7 fits in 8 slices stacked vertically and adds in about 2 ns.

Synthesis finds carry chains automatically whenever you write +, -, a comparison, or a counter, so you rarely refer to them by name. You will see them in the implemented design as a vertical column of logic cells, and they are the reason counters and adders are placed in straight vertical lines on the floorplan.

Multiplexers

A 2-to-1 multiplexer (mux) selects one of two inputs according to a select bit: out = sel ? b : a. It has three inputs, so it fits in any LUT with room to spare. A 4-to-1 mux has six inputs (four data, two select) and fits in a single 6-input LUT. An 8-to-1 mux needs two 6-input LUTs plus a dedicated mux primitive that AMD puts in every slice for the purpose.

Muxes matter because every if and every case in your HDL becomes one. A 32-bit register that loads from one of four sources is 32 4-to-1 muxes, which is 32 LUTs. A case statement with 16 branches on a 32-bit result is 32 16-to-1 muxes, which is about 160 LUTs. Muxes are where beginner designs quietly grow large.

A combinational block in Verilog and VHDL

Here is a small, complete, synthesisable module that uses an adder (a carry chain) and a mux. It takes two 4-bit inputs a and b and a select bit. When sel is 1 the output is the 5-bit sum. When sel is 0 the output is a zero-extended to 5 bits. Both versions describe the same hardware.

module add_or_pass (
  input  wire [3:0] a,
  input  wire [3:0] b,
  input  wire       sel,
  output wire [4:0] y
);
  wire [4:0] sum = {1'b0, a} + {1'b0, b};
  assign y = sel ? sum : {1'b0, a};
endmodule

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity add_or_pass is
  port (
    a   : in  std_logic_vector(3 downto 0);
    b   : in  std_logic_vector(3 downto 0);
    sel : in  std_logic;
    y   : out std_logic_vector(4 downto 0)
  );
end entity;

architecture rtl of add_or_pass is
  signal sum : unsigned(4 downto 0);
begin
  sum <= resize(unsigned(a), 5) + resize(unsigned(b), 5);
  y   <= std_logic_vector(sum) when sel = '1' else '0' & a;
end architecture;

Points to notice, which lesson 05 develops properly:

• There is no clock. Everything in the module is a continuous assignment (assign in Verilog, the bare <= outside a process in VHDL), so the outputs follow the inputs after a propagation delay. That is the signature of combinational logic.
• Both versions widen the operands to 5 bits before adding, so that the carry out of bit 3 becomes bit 4 of the result rather than being lost. Verilog does this with concatenation and VHDL with resize. Forgetting the extra bit is the most common adder bug.
• VHDL makes you say that the vectors are numbers (unsigned) before you add them. Verilog treats every vector as an unsigned number unless told otherwise. Both are reasonable choices and both catch people out.

Synthesis will produce 4 LUTs and 4 carry cells for the adder, then 5 LUTs for the 5-bit 2-to-1 mux, and a good tool will merge the mux into the adder’s LUTs so that the whole thing is 5 LUTs and a carry chain. You can check the number in the synthesis report.

Here is a short testbench for the Verilog version, so that you can run it in Icarus Verilog before reading the simulation lesson. The #1 delays give the combinational logic a moment to settle in simulation, since in a simulator nothing happens unless time passes.

`timescale 1ns/1ps
module add_or_pass_tb;
  reg  [3:0] a, b;
  reg        sel;
  wire [4:0] y;

  add_or_pass dut (.a(a), .b(b), .sel(sel), .y(y));

  initial begin
    a = 4'd9; b = 4'd7; sel = 1'b1; #1;
    if (y !== 5'd16) $display("FAIL: 9 + 7 gave %0d", y);
    sel = 1'b0; #1;
    if (y !== 5'd9) $display("FAIL: pass-through gave %0d", y);
    a = 4'd15; b = 4'd15; sel = 1'b1; #1;
    if (y !== 5'd30) $display("FAIL: 15 + 15 gave %0d", y);
    $display("done");
    $finish;
  end
endmodule

Run it with iverilog -g2012 -o add_or_pass.vvp add_or_pass.v add_or_pass_tb.v followed by vvp add_or_pass.vvp. It should print only done.

Glitches and why combinational outputs are not trusted directly

One more property of combinational logic matters before the next lesson. When an input changes, the different paths through the logic settle at different times, and for a few hundred picoseconds the output may take a wrong value before it takes the right one. These transients are called glitches. They are harmless if the output feeds another LUT, because the second LUT will also settle. They are dangerous if the output is used as a clock or a reset, because a glitch on a clock looks like an extra clock edge. The rule that follows, never drive a clock from logic, is one of the synchronous design rules in lesson 04, and the register is the device that hides glitches by sampling only at well-defined moments.

Exercise

1. Write the 16-bit truth table (as a string of bits, address 0000 first) for the 4-input function “exactly two of the inputs are 1”. Count how many 1s it contains.
2. A function of 9 inputs is implemented with 6-input LUTs. What is the smallest number of LUTs that could do it, and how many LUT levels does the critical path cross? Give a reason.
3. Modify add_or_pass so that when sel is 0 the output is the 5-bit difference a - b instead of a pass-through. Keep both versions in agreement, update the testbench to check 9 minus 7 and 7 minus 9, and note what the second result looks like in 5 bits.

Summary

• A Boolean function of n inputs is fully described by a truth table of 2 to the power n bits.
• A LUT stores that truth table in configuration memory and selects one bit with a mux tree. A 4-input LUT is 16 bits, a 6-input LUT is 64 bits, and either implements any function of its inputs in one delay.
• Functions wider than the LUT need multiple levels, and the number of levels sets the delay. Count distinct inputs, not gates.
• Dedicated carry chains make adders, subtractors, comparators and counters fast. Synthesis uses them automatically for +, - and comparisons.
• Every if and case becomes a multiplexer, and wide muxes on wide data are where designs grow.

Further reading

• AMD UG474, 7 Series FPGAs Configurable Logic Block User Guide: the LUT6, carry chain and mux primitives in the devices used on most beginner boards.
• AMD UG901, Vivado Design Suite User Guide: Synthesis: which HDL patterns synthesis recognises as adders, muxes and memories.
• Yosys manual: the abc and synth_* commands show how an open-source tool maps logic to LUTs.
• IEEE 1364-2005, Verilog Hardware Description Language and IEEE 1076-2019, VHDL Language Reference Manual: the language standards.