A You are given an FPGA containing many instances of the following 4-input looku

Question

A You are given an FPGA containing many instances of the following 4-input lookup table (LUT) Each LUT can be programmed to compute an arbitrary 4-input logic function. Using only these LUTs, draw a circuit that implements an 8-bit adder. You may connect the inputs of the LUTs to the inputs of your adder, or the outputs of other LUTs. Beside each LUT, write the logic function it implements. How many LUTs did you use? Is this an efficient implementation? Explain your answer. 4LUT f (a,b, c,d) B) Repeat part A with the Virtex 5 6-LUT from the lecture notes. al a2 5LUT a3 a4, a5 a6 fl a2 5LUT a3 f2 a4, a5 a6

Explanation / Answer

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.

Think about the first LUT’s output signal. It is a function of A, B, C, and D only, which means that it has the same value for truth table rows 1 and 2. Suppose it’s a 0 for those inputs.

Next, consider rows 2 and 3. The first LUT’s output has to be constant for these rows, too, because they also share ABCD values. The intermediate output also has to be the opposite for these rows, because the output behavior is different. If the intermediate output was the same for ABCD=0000 and ABCD=0001, the output could not possibly be different for inputs 00000 and 00010. Suppose the intermediate output is a 1 for those inputs.

Notice that the output is not dependent on E for any of the first 4 rows. So whether the first LUT outputs a 0 or 1, the second LUT must not change when E changes. And we know that the first LUT will output both those values for rows 1-4, because it needs to output two different values for the first two row pairs to be any different.

But now one of rows 5 and 6 is impossible! The first LUT output is necessarily the same for those rows, because ABCD don’t change. It looks like the output will have to change with E. This would be a contradiction in the second LUT, because we already confirmed that its output does not change with E.

Another way to prove that this approach doesn’t work is to count configuration bits. We know that a real 5-LUT needs 32 configuration bits. My circuit here has 16 bits in the first LUT, but only uses 4 bits of the second LUT. The second LUT may have 32 configuration bits, but since C and D are tied to ground, any truth table row with non-zero C or D is never going to be used, so its output bit will never matter. There are only 4 rows in the 4-LUT truth table with CD=00, so there are only 4 useful configuration bits. My design has 20 configuration bits that affect its output. That means it can perform 220 different functions, which isn’t enough. A real 5-LUT can perform 232 different functions (each of 32 input combinations can make one of 2 outputs).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.