2

I know there have been a lot of questions about lookup tables and their design, but even after reading them and scouring the web, I still don't quite understand how the LUTs are filled with corresponding boolean function's outputs from SRAM.

What is an LUT in FPGA?

The top answer to that question mentions something about using LUT masks. Are LUT masks the key to filling LUTs based on the boolean function from SRAM? Could someone elaborate on LUT masks please?

Also, say we have a 4 input LUT. That means we have 16 outputs, and 65535 possible combinations of outputs (0000000000000000 to 11111111111111). Does that mean all 65535 combinations will be stored in SRAM? And if we had 6 input the number would jump by a lot, and it doesn't seem like all that could be stored in RAM?

I think I may be misunderstanding something fundamental about FPGAs/LUTs horrifically. Any insight would be helpful!

Lokwill
  • 85
  • 7
  • 2
    Why would a 4-input LUT have 65536 possible output combinations? There's only 4 independent inputs, so 16 possible combinations of those. You must've got confused there. – Richard the Spacecat May 25 '20 at 23:16
  • I mean to say, let's assume that F = ABCD, then the outputs for that F look like 0000000000000001, and let's say F = A'B'C'D, then the outputs for that F look like 1000000000000000, and you would have 65536 possible different configurations of F. Is this not relevant to discuss LUTs since each LUTs are linked to a boolean expression through HDL? – Lokwill May 25 '20 at 23:23
  • @Lokwill - there are indeed 64k possible combinations for the bits in the LUT but since there are only 4-bits to address the LUT you only need to store 16 values taken out of the possible 64k values. – Kevin White May 25 '20 at 23:36
  • 1
    You needn't store __all__ of the possible LUT programming patterns, just the one you actually want to use! – Richard the Spacecat May 26 '20 at 00:01

2 Answers2

2

There are indeed 64k possible combinations for the bits in the LUT but since there are only 4 bits to address the LUT (assuming it is organized for 4 input 1 output) you only need to store 16 1 bit values. Which particular ones are stored depend upon the particular expression you have defined in your HDL.

A common usage of a LUT would be used to define a 4 input 1 output expression.

If for example the LUT is defined to output the AND function of the 4 input bits the first 15 locations would be set to zero with the 16th set to 1. The LUT would only output a 1 if all 4 input bits are a '1'.

Kevin White
  • 32,097
  • 1
  • 47
  • 74
  • Hmm, okay. I think I'm still a bit confused about addressing then. Let's say I have two boolean expressions, 1 is F=AB+C, and 2 is F=A'BC+D. Could you explain how the LUTs for these two would be created? – Lokwill May 25 '20 at 23:49
  • @Lokwill, basically write out the truth table for each of those functions (including D as a don't-care input for the 1st one). Now store the Q (output) column as a 16-bit number in the SRAM. – The Photon May 25 '20 at 23:52
  • Usually the LUT will have only 1 output, not 4 - they tend to be N to 1. So if you wanted four outputs controlled by your four inputs, it would take four LUTs each with the same four inputs. – Tom Carpenter May 26 '20 at 00:02
  • @ThePhoton But that's what is confusing me. How is that truth table logic generated based on the boolean expression? I can do it on paper, but how does the FPGA generate the truth table outputs? – Lokwill May 26 '20 at 00:31
  • @Lokwill, The FPGA doesn't know anything about the Boolean logic. "LUT" stands for "look-up table". All it does is use the 4 inputs to address a RAM, from which a single bit is output. If you put values in the RAM that match a certain Boolean logic, that's what you get. But as far as the device is concerned, it was basically just looking up a value in a table, it wasn't implementing a combination of gates. – The Photon May 26 '20 at 01:11
  • I'm still confused tbh, I don't understand how RAM already contains so many possibilities of outputs and how they get there. Do you know of any literature that might help? – Lokwill May 26 '20 at 02:48
  • 1
    @Lokwill it doesn't "already contain so many possibilities" - you *program* a setting into it. Think of it like sixteen 1-bit memories, and a 4-16 address decoder - you program each of the sixteen 1-bit memories with a value - e.g. 1000000000000000 - and then the 4 address inputs select which one out of those 1-bit memories drives the output. – Tom Carpenter May 26 '20 at 09:38
1

Each LUT on Xilinx and Intel (formerly Altera) FPGAs mostly has one output, hence a 4-input LUT stores 16-bit data. You can also instantiate an LUT primitive and store the data you want.

Here is an example in Verilog for 6-input LUTs on Xilinx FPGAs. It sums 6 bits, so the output is 3-bit. I'm instantiating 3 LUT6s (6-input LUTs), where each LUT is for one output.

module adder_6bit(in, out);

input  [5:0] in;
output [2:0] out;

LUT6 #(.INIT(64'h6996966996696996))
    LUT6_0 (.O(out[0]), .I0(in[0]), .I1(in[1]), .I2(in[2]), .I3(in[3]), .I4(in[4]), .I5(in[5]));

LUT6 #(.INIT(64'h8117177E177E7EE8))
    LUT6_1 (.O(out[1]), .I0(in[0]), .I1(in[1]), .I2(in[2]), .I3(in[3]), .I4(in[4]), .I5(in[5]));

LUT6 #(.INIT(64'hFEE8E880E8808000))
    LUT6_2 (.O(out[2]), .I0(in[0]), .I1(in[1]), .I2(in[2]), .I3(in[3]), .I4(in[4]), .I5(in[5]));

endmodule

A 6-input LUT requires a 64-bit data to store, I'm defining it as a parameter (INIT) as seen above. I would need a 16-bit parameter if I instantiated an LUT4 (4-input LUT).