Hello

I have to design a comparator circuit which compares two 8-bit numbers and has two outputs min and max (for the greater and the smaller number). I know how to code it in VHDL, but I need to implement it using 4-input LUTs only on paper. I have spent two days trying to figure out how I will do it and cannot come up with an answer.

Any help/direction will be awesome!

 

Using LUTs and only LUTs?

How many outputs does each LUT have?

If you could use a single LUT, how many inputs and outputs would you need?

 

Using only 4-input LUTs. Each LUT has only one output.
I can't use a single 16-input LUT because I need to have a total of 16 outputs (2 x 8 bit).

 

Using only 4-input LUTs. Each LUT has only one output.
I can't use a single 16-input LUT because I need to have a total of 16 outputs (2 x 8 bit).

Yes, you would need a 16-input LUT. Keep in mind that a LUT is just a bank of memory, such as SRAM, and can have as many outputs as you like. So you would need a 16-output LUT.

So how many bits of memory would be needed using a 16 x 16 bit LUT?

How many 4 x 1 bit LUTs would be required to have this same amount of memory?

Do you understand how you would use a LUT like that to implement your function?

The next question is whether we can figure out a way to implement the function with fewer bits of memory.

 

16 x 16 LUT - I do not know how this can be implemented. I understand the comparator from programmer's perspective - in code everything is clear.
One 4-input LUT uses 4*4=32 bits of memory, am I correct?

 

16 x 16 LUT - I do not know how this can be implemented. I understand the comparator from programmer's perspective - in code everything is clear.
One 4-input LUT uses 4*4=32 bits of memory, am I correct?

If you have 4 inputs, how many different input possibilities are there?

If you have 1 output, then how many bits of memory are needed per possible input?

 

I think I have made a mistake.
4 inputs means 2 to the power of 4 possible combinations - 16. But I don't know the answer of the second question.

 

You have 16 possible input combinations. Each combination produces one bit of output. How much memory is required to store all of the possible outputs?

 

64 bits?

 

LUTs are memory arrays, but that doesn't mean that this is a memory programming problem. There is another approach to this. Design a circuit that meets the problem description - something that compares two 8-bit values, something that makes a decision based on that result, and something that steers data based on that decision.

ak

 

Hi, what would be the combinations logic used in each look up table? A magnitude digital comparator? How do we get the circuit to stop comparing the rest of the values once it finds one bit is larger than the corresponding bit in the compared number?





(Moderator's note: This necropost is approved since some of the thread's participants are still around and the original discussion ended.)

 

How do we get the circuit to stop comparing the rest of the values once it finds one bit is larger than the corresponding bit in the compared number?

Why would you want to do that? If you were using a 1-bit comparator in a serial manner that would save you some clock cycles, but magnitude comparison using LUTs is a parallel process. Comparing all bits takes the same amount of time as comparing only some bits, and is far less complex to implement.

ak

 

Why would you want to do that? If you were using a 1-bit comparator in a serial manner that would save you some clock cycles, but magnitude comparison using LUTs is a parallel process. Comparing all bits takes the same amount of time as comparing only some bits, and is far less complex to implement.

ak

Would a sequential 8 bit comparator not be slower than a parallel 8 bit comparator? I was needing to implement a sequential method but I'm unsure of how to pick the output number with the sequential design?

 

Would a sequential 8 bit comparator not be slower than a parallel 8 bit comparator?

Pretty much by definition, yes. No matter how fast the clock is, 9 clock cycles always will be slower than 3 or 4 gate propagation delays.

Other than as an instructional exercise, I can't think of any reason for a sequential multi-bit comparator. If you wanted the circuit to terminate as soon as the outcome was known, then comparing the two values starting with the LSB, or starting with the MSB, would be two very different circuits.

ak

 

Pretty much by definition, yes. No matter how fast the clock is, 9 clock cycles always will be slower than 3 or 4 gate propagation delays.

Other than as an instructional exercise, I can't think of any reason for a sequential multi-bit comparator. If you wanted the circuit to terminate as soon as the outcome was known, then comparing the two values starting with the LSB, or starting with the MSB, would be two very different circuits.

ak

Yes it really is just an instructional exercise, what confuses me is if A = 1000 0000 and B = 0111 1111 then only the MSB of A will be greater than the MSB of B but all other bit values will be B is greater than A. So how do I for instance create a multiplexer circuit to decide that the A value should be selected?