Digital Comparator using LUT

[hithesh123]

I'm trying to see the logic utilization in spartan3 for building a 4-input comparator.
For case A>B, if the input is 2bit, the logic utilization is one 4-input LUT. Pretty obvious.
A0,A1,B0,B1 inputs and one Y output.

But for 4-input comparator, the logic utilization is three 4-input LUTs and MUX. But Why???????????????

 

[TonyM]

Before answering, can you use the schematic viewer in Xilinx ISE to see the circuit it synthesized? You might get your answer from that picture.

 

[hithesh123]

Before answering, can you use the schematic viewer in Xilinx ISE to see the circuit it synthesized? You might get your answer from that picture.

Saw the schematic(attached). But still did not understand the logic or the idea behind using three LUT4 and a mux.

 

[TonyM]

The mux is coupled the LUT in a slice. Using the mux gives faster routing than another LUT would. Better routing and more efficient use of circuitry. Using the muxes like that is typical throughout synthesized designs.

Since you haven't got 8-input LUTs, you can't do a 2x4-input comparison in one LUT. So you need LUTs feeding more LUTs.

List out some of the 4-bit values you'll be comparing and look for boundary conditions. Imagine the LUT-less circuit you need for your comparator. Then imagine spreading it across 4-to-1 LUTs. It'll become clear then. You can spell it out to yourself better than we can

 

[hithesh123]

List out some of the 4-bit values you'll be comparing and look for boundary conditions. Imagine the LUT-less circuit you need for your comparator. Then imagine spreading it across 4-to-1 LUTs. It'll become clear then. You can spell it out to yourself better than we can

I tried. While comparing 2-bits and then one bit in the next stage is simple, it adds delays. It requires one LUT4 and two LUT3s.

I just don't understand the implementation in ISE.
The lower 2 bits - you have to compare.
You can compare the MS 2bits.
The MS 2 bits are compared twice?

 

[D.A.(Tony)Stewart]

for n bits you have 2^n combinations of values to compare. so you have n-1 LUT's

 

[hithesh123]

for n bits you have 2^n combinations of values to compare. so you have n-1 LUT's

(n-1) LUTs is fine. But what about the mux.

Anyway for the 4bit case, let's say

1. you compare A0A1 with B0B1, result Y1
2. then you compare A1A2 with B1B2, result Y2
3. Then you compare A2A3 with B2B3, result Y3

The output of the first comparision, is the sel input for the mux. The outputs of second and third comparision are the 2 inputs for the mux.
So, if (first comparison) Y1 is true, then Y2 is selected, else Y3.

But both Y2 and Y3 can be zero, if A=1111 and B=1110. The result will be zero ?

 

[mrflibble]

At first you had me going there. Nice puzzle though.

The circuit in your pdf will work just fine.

Y1 is the 2-bit result from the upper 2 LUTs.

Y2 is the 1-bit result from lower LUT.


pseudo-code because 1) it will give you the idea just fine and 2) I am lazy but mostly 3) no coffee senior! ._.

if (A[3:2] > B[3:2]) { Y1 = 2'b11; }
else if (A[3:2] < B[3:2]) { Y1 = 2'b00; }
else { Y1 = 2'b10; }

Y2 = (A[1:0] > B[1:0]) ? 1'b1 : 1'b0;

result = (Y2) ? Y1[1] : Y1[0]; // magic mushroom mux, problem solved

 

[TonyM]

lut Y22 checks if the a[1:0] is greater than b[1:0].

If a[1:0] > b[1:0], the result is taken from this test: a[3:2] >= b[3:2].

If a[1:0] <= b[1:0], the result is taken from this test: a[3:2] > b[3:2].

The test is for A to be larger than B, for A to win the full comparison.

So if A wins the low bits test, the A high bits must just not lose their test for A to win the full comparison.

But if A loses the low bits test, the A high bits do have to win for A to win the full comparison.

 

[hithesh123]

lut Y22 checks if the a[1:0] is greater than b[1:0].

If a[1:0] > b[1:0], the result is taken from this test: a[3:2] >= b[3:2].

If a[1:0] <= b[1:0], the result is taken from this test: a[3:2] > b[3:2].

The test is for A to be larger than B, for A to win the full comparison.

So if A wins the low bits test, the A high bits must just not lose their test for A to win the full comparison.

But if A loses the low bits test, the A high bits do have to win for A to win the full comparison.

Now things are crystal clear!

 

[TonyM]

No problem, you're welcome

 

[D.A.(Tony)Stewart]

Your MUX needs AND gates with two to n+1 inputs per gate and n+1 gates.
Then there are 3 output MUX gates to select >,=,< for A & B with n bits each.

pour s'amuser, study this.
**broken link removed**

 

[hithesh123]

Just to take this further. I synthesized an 8 bit comparator. ISE consumed 9 LUT4 and 8 MUXes.
Most of the LUT4s were used as LUT2.
I tried doing it myself, I consumed 8 LUT4 and 2 MUXes.
Shouldn't ISE consume less logic in most cases.

I have attached both ise and my implementation.
In my implementation, each output Y needs a LUT4. One for 'greater than', other for 'equal to'. Y22, Y33, Y44 are LUT outputs of 'equal to' comparason.
Y1,Y2,Y3,Y4 are outputs of 'greater than'.
The two IF statements are MUXes.