8-bit comparator using FPGA

Thread Starter

mojo_risin

Joined Jul 3, 2013
35
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!
 

WBahn

Joined Mar 31, 2012
26,074
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?
 

Thread Starter

mojo_risin

Joined Jul 3, 2013
35
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).
 

WBahn

Joined Mar 31, 2012
26,074
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.
 

Thread Starter

mojo_risin

Joined Jul 3, 2013
35
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?
 

WBahn

Joined Mar 31, 2012
26,074
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?
 

Thread Starter

mojo_risin

Joined Jul 3, 2013
35
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.
 

WBahn

Joined Mar 31, 2012
26,074
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?
 

AnalogKid

Joined Aug 1, 2013
8,540
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
 
Last edited:

Crum

Joined Dec 9, 2017
3
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.)
 
Last edited by a moderator:

AnalogKid

Joined Aug 1, 2013
8,540
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
 

Crum

Joined Dec 9, 2017
3
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?
 

AnalogKid

Joined Aug 1, 2013
8,540
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
 

Crum

Joined Dec 9, 2017
3
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?
 
Top