2
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Richard the Spacecat May 25 at 23:16
  • \$\begingroup\$ 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? \$\endgroup\$ – Lokwill May 25 at 23:23
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin White May 25 at 23:36
  • \$\begingroup\$ You needn't store all of the possible LUT programming patterns, just the one you actually want to use! \$\endgroup\$ – Richard the Spacecat May 26 at 0:01
2
\$\begingroup\$

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'.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Lokwill May 25 at 23:49
  • \$\begingroup\$ @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. \$\endgroup\$ – The Photon May 25 at 23:52
  • \$\begingroup\$ 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. \$\endgroup\$ – Tom Carpenter May 26 at 0:02
  • \$\begingroup\$ @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? \$\endgroup\$ – Lokwill May 26 at 0:31
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Tom Carpenter May 26 at 9:38
1
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.