# What are some of the basic FPGA synthesis algorithms mapping to LUT?

I am trying to look up easy to understand papers that help explain how logic functions are mapped onto LUT. For e.g. if I have c = (a+b)*c -d how is this mapped on to LUT or if a counter is designed how is the same mapped etc.

A LUT is a memory (Look. Up. Table). It implements logic truth tables by using the memory address as the input bits, and the memory data output as the output bits.

By way of example, for a 4-bit up counter: at address 4'b0000 is stored 4'b0001; at address 4'b0001 is stored 4'b0010; ... ; at address 4'b1011 is stored 4'b1100; and so forth. The outputs are registered and fed back to the inputs, so on every clock the cycle repeats and the counter output increments.

Markt's answer is correct. If you're curious how the synthesis algorithms actually work I'd point you to the work of De Micheli at EPFL. He was very instrumental in VLSI synthesis http://icwww.epfl.ch/~demichel/. He wrote a great book on the subject: http://icwww.epfl.ch/~demichel/publications/mcgraw/index.html It might be a bit more dense than what you're looking for, but it's an excellent text.

The precise mapping depends on the type of LUT implemented. A very common configuration is a LE with a 16 entry LUT (4 inputs), split into two halves to get two outputs. Each of the half LUTs looks similar to this:

simulate this circuit – Schematic created using CircuitLab

The LE configuration contains the values coming in from the left (table data), as well as some values that get applied to other gates around the LUT, for example a selection flag that can pull the third input from a neighbouring LE's upper half of the table. That way, you can easily implement an adder:

left    right   cin     out     cout
0       0       0       0       0
0       0       1       1       0
0       1       0       1       0
0       1       1       0       1
1       0       0       1       0
1       0       1       0       1
1       1       0       0       1
1       1       1       1       1


The cout signal of the table for bit 0 is connected to the cin signal of bit 1, so you get a full adder with carry.

Subtraction adds the two's compliment of the right hand side value, and multiplication adds the left hand side value shifted by N bits to the left if bit N is set in the right hand side value (so a 9x9 multiplier needs a 9 bit adder, an 8-bit adder, a 7 bit adder, ...).

These operations may be combined if there is a more optimal packing of tables -- for example I can represent the two's complement needed for subtraction in the lookup table for the adder. That optimization is a hard problem, and often no optimal solution exists -- but finding one that matches timing requirements is usually enough.

Mapping c=(a+b)*c-d requires combinatorial logic for (a+b)*c-d, and a register stage that saves the value of c. The register needs an additional signal to trigger the update, otherwise you'd end up with (a+b)*((a+b)*c-d)-d rather quickly.