24
\$\begingroup\$

I have gone through various sources... But I am not quite sure what it is.I want an and gate and the logical equivalent is two inputs feeding to one gate and for Y=AB' the logical equivalent is feeding to one not gate and one and gate. But it is the same LUT for both AND and Y=AB'. I think we store the values as desired in the LUT. Someone elaborate on this

\$\endgroup\$
  • 2
    \$\begingroup\$ Any reason you haven't accepted an answer? \$\endgroup\$ – Ellen Spertus Aug 16 '16 at 20:10
37
\$\begingroup\$

A LUT, which stands for LookUp Table, in general terms is basically a table that determines what the output is for any given input(s). In the context of combinational logic, it is the truth table. This truth table effectively defines how your combinatorial logic behaves.

In other words, whatever behavior you get by interconnecting any number of gates (like AND, NOR, etc.), without feedback paths (to ensure it is state-less), can be implemented by a LUT.

The way FPGAs typically implement combinatorial logic is with LUTs, and when the FPGA gets configured, it just fills in the table output values, which are called the "LUT-Mask", and is physically composed of SRAM bits. So the same physical LUT can implement Y=AB and Y=AB', but the LUT-Mask is different, since the truth table is different.

You can also create your own lookup tables. For example, you could build a table for a complex mathematical function, which would work much faster than actually calculating the value by following an algorithm. This table would be stored in RAM or ROM.

This brings us to viewing the LUTs simply as memory, where the inputs are the address, and the corresponding outputs are the data stored in the given address.

Here's a snapshot from FPGA Architecture by Altera:

enter image description here

\$\endgroup\$
23
\$\begingroup\$

A two input LUT (lookup table) is can be represented generically like this:

enter image description here

A LUT consists of a block of SRAM that is indexed by the LUT's inputs. The output of the LUT is whatever value is in the indexed location in it's SRAM.

Although we think of RAM normally being organized into 8, 16, 32 or 64-bit words, SRAM in FPGA's is 1 bit in depth. So for example a 3 input LUT uses an 8x1 SRAM (2³=8)

Because RAM is volatile, the contents have to be initialized when the chip is powered up. This is done by transferring the contents of the configuration memory into the SRAM.

The output of a LUT is whatever you want it to be. For a two-input AND gate,

Address In ([1:0])      Output

     0  0                 0
     0  1                 0
     1  0                 0
     1  1                 1

For your second example, only the truth table changes:

Address In ([1:0])      Output

     0  0                 0
     0  1                 1
     1  0                 0
     1  1                 0

and finally, A xor B:

Address In ([1:0])      Output

     0  0                 0
     0  1                 1
     1  0                 1
     1  1                 0

So it is not the same LUT in each case, since the LUT defines the output. Obviously, the number of inputs to an LUT can be far more than two.

The LUT is actually implemented using a combination of the SRAM bits and a MUX:

Here the bits across the top 0 1 0 0 0 1 1 1 represents the output of the truth table for this LUT. The three inputs to the MUX on the left a, b, and c select the appropriate output value.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Thanks for that... But I am getting very basic questions here. SRAM bits? I know SRAM.. but SRAM bits? Configuration memory? and could you explain how Y=AB,Y=AB' and Y= A xor B will be implemented with a 2-input LUT? It would be helpful if you explain with a MUX level diagram? I am very thankful for your help on the structure on LUT. What is that R in the diagram> \$\endgroup\$ – Muthu Subramanian May 8 '15 at 9:13
  • \$\begingroup\$ @MuthuSubramanian I have updated my answer which should address all of your questions. \$\endgroup\$ – tcrosley May 8 '15 at 9:59

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.