Velocity Reviews > VHDL > N-input AND gate

# N-input AND gate

Guest
Posts: n/a

 07-28-2005
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

Mike Treseler
Guest
Posts: n/a

 07-28-2005

> 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

Guest
Posts: n/a

 07-28-2005
Thanks.
I'll see what my systhesis tool can do.

David Bishop
Guest
Posts: n/a

 07-29-2005

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

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.

Guest
Posts: n/a

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

TJ

Hubble
Guest
Posts: n/a

 07-31-2005
>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.

Mike Treseler
Guest
Posts: n/a

 07-31-2005
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

Guest
Posts: n/a

 08-01-2005
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.

Mike Treseler
Guest
Posts: n/a

 08-01-2005

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

I guess I would be surprised if any
of the top synthesis tools performed
any differently.

-- Mike Treseler

Jos De Laender
Guest
Posts: n/a

 08-02-2005
Mike Treseler 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