Dark Mode

21 votes

Best answer

After drawing a circuit for a question, how can i be sure that this is the most optimal way..

I mean how can i be sure that there is no other way that gives me even less number of gates...

i am facing the same problem for finding minimum number of states of a dfa of a given situation..

Need help in this aspect.. Thanks in advance

6

18 votes

Using the intuitive way,

XOR (A,B) = A' B + A B'

So, for using NAND Gates, we use double complement method:

XOR (A,B) = ( (A' B + A B' ) ' ) ' = ( (AB') ' . (AB') ' )'

Now in order to implement A' and B' we will have to use two NAND Gates and then two more to implement (A' B)' and (AB') '. And at last 1 more NAND Gate to implement ( (A' B)' . (AB') ' )'. Hence all in all we Will be using 5 NAND Gates. This WONT WORK !

Hence we have to think of an OPTIMIZED Solution !

Therefore we use a new method to obtain (AB') ' and (AB') ' using lesser number of Gates.

Using NAND gates we directly have (AB)' . Now we can make use of this and obtain (AB') ' and (AB') ' using lesser number of gates:

We see : (A B') ' = ((AB)'.A) ' And (A' B) ' = ( (AB)'.B ) '

Hence the equation can be reduced to :

XOR(A,B) = ( ( (AB)'.B ) ' . ((AB)'.A) ' ) '

This solution would require 4 Gates only. Hence Logically we can arrive at this solution.

XOR (A,B) = A' B + A B'

So, for using NAND Gates, we use double complement method:

XOR (A,B) = ( (A' B + A B' ) ' ) ' = ( (AB') ' . (AB') ' )'

Now in order to implement A' and B' we will have to use two NAND Gates and then two more to implement (A' B)' and (AB') '. And at last 1 more NAND Gate to implement ( (A' B)' . (AB') ' )'. Hence all in all we Will be using 5 NAND Gates. This WONT WORK !

Hence we have to think of an OPTIMIZED Solution !

Therefore we use a new method to obtain (AB') ' and (AB') ' using lesser number of Gates.

Using NAND gates we directly have (AB)' . Now we can make use of this and obtain (AB') ' and (AB') ' using lesser number of gates:

We see : (A B') ' = ((AB)'.A) ' And (A' B) ' = ( (AB)'.B ) '

Hence the equation can be reduced to :

XOR(A,B) = ( ( (AB)'.B ) ' . ((AB)'.A) ' ) '

This solution would require 4 Gates only. Hence Logically we can arrive at this solution.