Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

N input digital function require minimum how many gates

Status
Not open for further replies.

dll_fpga

Full Member level 3
Joined
Mar 9, 2011
Messages
185
Helped
19
Reputation
38
Reaction score
19
Trophy points
1,298
Location
kerala,India
Activity points
2,416
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
 
Last edited:

Prashanth.vinnakota

Advanced Member level 4
Joined
Apr 16, 2012
Messages
107
Helped
23
Reputation
46
Reaction score
22
Trophy points
1,298
Location
India
Activity points
1,868
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

Full Member level 3
Joined
Mar 9, 2011
Messages
185
Helped
19
Reputation
38
Reaction score
19
Trophy points
1,298
Location
kerala,India
Activity points
2,416
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

Advanced Member level 4
Joined
Apr 16, 2012
Messages
107
Helped
23
Reputation
46
Reaction score
22
Trophy points
1,298
Location
India
Activity points
1,868
Pls Mention the fan in of AND, OR gates. Also other universal gates if used.
 

Prashanth.vinnakota

Advanced Member level 4
Joined
Apr 16, 2012
Messages
107
Helped
23
Reputation
46
Reaction score
22
Trophy points
1,298
Location
India
Activity points
1,868
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.
 
Last edited:

dll_fpga

Full Member level 3
Joined
Mar 9, 2011
Messages
185
Helped
19
Reputation
38
Reaction score
19
Trophy points
1,298
Location
kerala,India
Activity points
2,416
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

Advanced Member level 4
Joined
Apr 16, 2012
Messages
107
Helped
23
Reputation
46
Reaction score
22
Trophy points
1,298
Location
India
Activity points
1,868
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^(n) + (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 + .......................
 
Last edited:

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top