N input digital function require minimum how many gates

[dll_fpga]

hi
say for eg:
5 input digital function require minimum how many gates to implement in hardware?Also what is the maximum no of gates for the same?
How can we calculate the max and min gates for an n input function
please explain

please give the relevant proofs..if available

 

[Prashanth.vinnakota]

I feel that the question is incomplete.

Maximum number of product terms possible with 5 inputs are 32. There can be a number of AOI gates combination which leads to that output function. Also there can be gates with different "fan in" and "fan out" capabilities. This can be solved only if the fan in and fan out for each basic gates are mentioned.

- - - Updated - - -

There are PLDs (PROMs, PLAs and PALs) available for doing this.

Fixed or programmable AND array, OR array implements this.

- - - Updated - - -

Fixed AND array is capable of generating all the product terms while a fixed or programmable OR array takes these product terms for implementing each of its output function.

 

[dll_fpga]

i prakash ,
i need an approximate no
for eg:ab+cd
being a 4 input function is implemented with 3 gates
(2 and and 1 or)

I feel that the question is incomplete.

Maximum number of product terms possible with 5 inputs are 32. There can be a number of AOI gates combination which leads to that output function. Also there can be gates with different "fan in" and "fan out" capabilities. This can be solved only if the fan in and fan out for each basic gates are mentioned.

- - - Updated - - -

There are PLDs (PROMs, PLAs and PALs) available for doing this.

Fixed or programmable AND array, OR array implements this.

- - - Updated - - -

Fixed AND array is capable of generating all the product terms while a fixed or programmable OR array takes these product terms for implementing each of its output function.

 

[Prashanth.vinnakota]

Pls Mention the fan in of AND, OR gates. Also other universal gates if used.

 

[dll_fpga]

let us take fanin as 3 and below

Pls Mention the fan in of AND, OR gates. Also other universal gates if used.

 

[Prashanth.vinnakota]

Considering fanin=2 for a 2 input function we require a maximum of:
2 NOT Gates
4 AND Gates
7 OR Gates

Let me know if you understood this.

- - - Updated - - -

This is for a single output function.

 

[dll_fpga]

please let me know how u have calculated this

Considering fanin=2 for a 2 input function we require a maximum of:
2 NOT Gates
4 AND Gates
10 OR Gates

Let me know if you understood this.

- - - Updated - - -

This is for a single output function.

 

[Prashanth.vinnakota]

Considering fanin=3 for a 3 input function we require a maximum of:
3 NOT Gates
20 AND Gates
13 OR Gates

- - - Updated - - -

- - - Updated - - -

please let me know how u have calculated this

- - - Updated - - -

Also we considered SOP implementation with AOI Combinations only.

- - - Updated - - -

Considering fanin=4 for a 4 input function we require a maximum of:
4 NOT Gates
72 AND Gates
28 OR Gates

- - - Updated - - -

Considering fanin=5 for a 5 input function we require a maximum of:
5 NOT Gates
232 AND Gates
62 OR Gates

I will explain how these numbers arised later.

- - - Updated - - -

The general formula for calculating the maximum number of gates(with fan in = no of inputs = n) required for implementing an output with n-inputs is:
No. of NOT Gates = n
No. of AND Gates = 2^ + (nCn-1)*2^(n-1) + (nCn-2)*2^(n-2) + .................. + (nC2)*2^2
No. of OR Gates = (No. of AND gates + 2n)/n + (No. of AND gates + 2n )/n^2 + .......................