N-input AND gate

Discussion in 'VHDL' started by TigerJade, Jul 28, 2005.

  1. TigerJade

    TigerJade Guest

    Hi,
    I'm thinking about to write a N-input AND gate like this:
    signal A : std_logic_vector(N-1 downto 0)
    process (A)
    variable result: std_logic;
    begin
    result := '1';
    for i in N-1 downto 0 loop
    result := result and A(i);
    end loop;
    Y <= result;
    end process;
    But this type of implementation has propagation delay of N AND gates. I
    believe a tree type of AND gates will have only propagation delay of
    log2(N), which is a significant reduction if N is large, although the
    number of AND gates is the same.

    Is it possible using some loop or generate statements to produce a
    tree-type N-input AND gate, which is suitable for for all values of N,
    or even just N = any power of 2.

    Regards,
    TJ
    TigerJade, Jul 28, 2005
    #1
    1. Advertising

  2. TigerJade wrote:


    > Is it possible using some loop or generate statements to produce a
    > tree-type N-input AND gate, which is suitable for for all values of N,
    > or even just N = any power of 2.


    Synthesis does a pretty good job with AND gates.
    Consider describing your design at a higher level
    and see if this is really a problem that
    needs a solution.

    -- Mike Treseler
    Mike Treseler, Jul 28, 2005
    #2
    1. Advertising

  3. TigerJade

    TigerJade Guest

    Thanks.
    I'll see what my systhesis tool can do.
    TigerJade, Jul 28, 2005
    #3
  4. TigerJade

    David Bishop Guest

    TigerJade wrote:

    > Hi,
    > I'm thinking about to write a N-input AND gate like this:
    > signal A : std_logic_vector(N-1 downto 0)
    > process (A)
    > variable result: std_logic;
    > begin
    > result := '1';
    > for i in N-1 downto 0 loop
    > result := result and A(i);
    > end loop;
    > Y <= result;
    > end process;
    > But this type of implementation has propagation delay of N AND gates. I
    > believe a tree type of AND gates will have only propagation delay of
    > log2(N), which is a significant reduction if N is large, although the
    > number of AND gates is the same.


    The function you are looking for is called "and_reduce", and you will
    find a copy in:

    http://www.eda.org/vhdl-200x/vhdl-200x-ft/packages/std_logic_1164_additions.vhd

    It uses recursion, but I've tested it in several synthesis tools.

    In the final version of vhdl-2005 it should be an overload for the "and"
    function.
    David Bishop, Jul 29, 2005
    #4
  5. TigerJade

    TigerJade Guest

    Thanks for the information.
    It looks like the chain-shape AND and the tree-shape AND have the same
    topology aftern synthesis.

    TJ
    TigerJade, Jul 29, 2005
    #5
  6. TigerJade

    Hubble Guest

    >But this type of implementation has propagation delay of N AND gates.

    Really? This is not a structure using and gates as components but
    already an algorithmic destription of the problem inside a process.
    The Y driver will happily deliver the result after one delta. Or did I
    miss somehting here?

    Hubble.
    Hubble, Jul 31, 2005
    #6
  7. Hubble wrote:
    >>But this type of implementation has propagation delay of N AND gates.

    >
    >
    > Really? This is not a structure using and gates as components but
    > already an algorithmic destription of the problem inside a process.
    > The Y driver will happily deliver the result after one delta.


    I think the OP is trying to compare synthesis results
    for different AND algorithms. I agree that in theory
    the algorithm shouldn't make any difference, but I
    don't doubt that real synthesis has some sensitivity
    to it.

    I prefer to spend time describing and simulating
    logical entities and leave the gate level details
    alone. I guess it all depends on what you're doing.

    -- Mike Treseler
    Mike Treseler, Jul 31, 2005
    #7
  8. TigerJade

    TigerJade Guest

    Well. What I did is to write two VHDL architectures with the two
    algorithms and synthesize them separately with Leonardo Spectrum and
    its ADP package for ASIC techniques. After the synthesis, I compared
    the circuits generated by it and the area, timing reports and found no
    difference at all. I guess, it might heavily rely on the synthesis tool
    used.
    TigerJade, Aug 1, 2005
    #8
  9. TigerJade wrote:

    > After the synthesis, I compared
    > the circuits generated by it and the area, timing reports and found no
    > difference at all. I guess, it might heavily rely on the synthesis tool
    > used.


    Thanks for posting your results.
    I guess I would be surprised if any
    of the top synthesis tools performed
    any differently.

    -- Mike Treseler
    Mike Treseler, Aug 1, 2005
    #9
  10. Mike Treseler wrote:
    > TigerJade wrote:
    >
    >> After the synthesis, I compared
    >> the circuits generated by it and the area, timing reports and found no
    >> difference at all. I guess, it might heavily rely on the synthesis tool
    >> used.

    >
    >
    > Thanks for posting your results.
    > I guess I would be surprised if any
    > of the top synthesis tools performed
    > any differently.
    >
    > -- Mike Treseler



    It used to be one of my favourites ;-)

    The most optimum solution is to write it recursively.
    It synthesizes then always to a tree solution.

    If you do the check on the *isolated* circuit the results will probably
    be the same for the loop as for the recursive solution.

    If you do the check on the construction buried in a bunch of other
    functionality , it does make a difference.

    My understanding is that a chain (for loop description) is initially
    synthesized as a chain but can be optimized to a tree again , provided
    that 'not too much logic' is around it.

    The tree (recursive) is initially synthesized as a tree and stays like
    that , independent of surrounding logic.

    Or did synthesis tools improve that much since I left the field ?

    Jos
    Jos De Laender, Aug 2, 2005
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Henning Bahr
    Replies:
    0
    Views:
    1,516
    Henning Bahr
    Aug 18, 2003
  2. Replies:
    3
    Views:
    918
  3. Replies:
    7
    Views:
    3,828
    kunal.bandekar
    May 23, 2011
  4. Weng Tianxiang
    Replies:
    12
    Views:
    1,596
  5. Replies:
    1
    Views:
    579
    Ralf Hildebrandt
    Nov 7, 2007
Loading...

Share This Page