+ Post New Thread
Results 1 to 13 of 13
  1. #1
    Full Member level 6
    Points: 2,819, Level: 12
    Achievements:
    7 years registered

    Join Date
    Nov 2009
    Location
    lax
    Posts
    324
    Helped
    1 / 1
    Points
    2,819
    Level
    12

    Digital Comparator using LUT

    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???????????????

  2. #2
    Full Member level 1
    Points: 625, Level: 5

    Join Date
    Jun 2012
    Posts
    111
    Helped
    30 / 30
    Points
    625
    Level
    5

    Re: Digital Comparator using LUT

    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.



    •   Alt18th June 2012, 19:55

      advertising

        
       

  3. #3
    Full Member level 6
    Points: 2,819, Level: 12
    Achievements:
    7 years registered

    Join Date
    Nov 2009
    Location
    lax
    Posts
    324
    Helped
    1 / 1
    Points
    2,819
    Level
    12

    Re: Digital Comparator using LUT

    Quote Originally Posted by TonyM View Post
    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.



  4. #4
    Full Member level 1
    Points: 625, Level: 5

    Join Date
    Jun 2012
    Posts
    111
    Helped
    30 / 30
    Points
    625
    Level
    5

    Re: Digital Comparator using LUT

    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



  5. #5
    Full Member level 6
    Points: 2,819, Level: 12
    Achievements:
    7 years registered

    Join Date
    Nov 2009
    Location
    lax
    Posts
    324
    Helped
    1 / 1
    Points
    2,819
    Level
    12

    Re: Digital Comparator using LUT

    Quote Originally Posted by TonyM View Post

    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?



  6. #6
    Advanced Member level 5
    Points: 34,060, Level: 45
    Achievements:
    7 years registered Created Blog entry Created Album pictures
    SunnySkyguy's Avatar
    Join Date
    Sep 2007
    Location
    Richmond Hill, ON, Canada
    Posts
    6,600
    Helped
    1652 / 1652
    Points
    34,060
    Level
    45
    Blog Entries
    7

    Re: Digital Comparator using LUT

    for n bits you have 2^n combinations of values to compare. so you have n-1 LUT's
    A good design question lists your overall requirements™ The best question deserves a better answer. ™
    ... Tony Stewart EE since 1975



    •   Alt19th June 2012, 03:52

      advertising

        
       

  7. #7
    Full Member level 6
    Points: 2,819, Level: 12
    Achievements:
    7 years registered

    Join Date
    Nov 2009
    Location
    lax
    Posts
    324
    Helped
    1 / 1
    Points
    2,819
    Level
    12

    Re: Digital Comparator using LUT

    Quote Originally Posted by SunnySkyguy View Post
    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 ?



  8. #8
    Advanced Member level 5
    Points: 14,946, Level: 29
    mrflibble's Avatar
    Join Date
    Apr 2010
    Posts
    2,724
    Helped
    686 / 682
    Points
    14,946
    Level
    29

    Re: Digital Comparator using LUT

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

    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! ._.

    Code:
    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



  9. #9
    Full Member level 1
    Points: 625, Level: 5

    Join Date
    Jun 2012
    Posts
    111
    Helped
    30 / 30
    Points
    625
    Level
    5

    Re: Digital Comparator using LUT

    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.


    1 members found this post helpful.

  10. #10
    Full Member level 6
    Points: 2,819, Level: 12
    Achievements:
    7 years registered

    Join Date
    Nov 2009
    Location
    lax
    Posts
    324
    Helped
    1 / 1
    Points
    2,819
    Level
    12

    Re: Digital Comparator using LUT

    Quote Originally Posted by TonyM View Post
    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!


    1 members found this post helpful.

    •   Alt19th June 2012, 13:55

      advertising

        
       

  11. #11
    Full Member level 1
    Points: 625, Level: 5

    Join Date
    Jun 2012
    Posts
    111
    Helped
    30 / 30
    Points
    625
    Level
    5

    Re: Digital Comparator using LUT

    No problem, you're welcome



  12. #12
    Advanced Member level 5
    Points: 34,060, Level: 45
    Achievements:
    7 years registered Created Blog entry Created Album pictures
    SunnySkyguy's Avatar
    Join Date
    Sep 2007
    Location
    Richmond Hill, ON, Canada
    Posts
    6,600
    Helped
    1652 / 1652
    Points
    34,060
    Level
    45
    Blog Entries
    7

    Re: Digital Comparator using LUT

    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.
    A good design question lists your overall requirements™ The best question deserves a better answer. ™
    ... Tony Stewart EE since 1975



  13. #13
    Full Member level 6
    Points: 2,819, Level: 12
    Achievements:
    7 years registered

    Join Date
    Nov 2009
    Location
    lax
    Posts
    324
    Helped
    1 / 1
    Points
    2,819
    Level
    12

    Re: Digital Comparator using LUT

    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.



--[[ ]]--