|
|
|
|
I was just going through my chips again to make sure they are all abstracted properly. It doesn't seem like Xor can be abstracted with And, Or, or Not. Do I need to stick with 4 NAND gates?
|
|
Administrator
|
JustinM wrote
I was just going through my chips again to make sure they are all abstracted properly. It doesn't seem like Xor can be abstracted with And, Or, or Not. Do I need to stick with 4 NAND gates?
You can always implement with Not, And and Or starting with the canonical form of any function.
The book, in fact, shows the canonical form of Xor as figure 1.5 and as the design example in figure 1.6.
An alternate canonical form is the "product of sums" which works like the sum of products canonical form, but you use the zeros in the function to determine the required terms, instead of the ones. This would give you
a xor b = ( a + b)(~ a + ~ b).
Try to think of an implementation using an And, and Or and a Nand.
--Mark
|
|
|
Everything can be made from the combinations of And, Or, Not. The section on "canonical representation" in chapter 1 shows how any function can be represented with And, Or, Not.
xor truth table
=========
a b o
0 0 0
0 1 1 !ab
1 0 1 a!b
1 1 0
!ab + a!b
Or with Polish notation:
Or ( And( Not(a), b ), And(a, Not(b) ) )
So yes it can be done. The above show you one way with 5 Gates. 2 Nots, 2 Ands and 1 Or.
At least for myself the best I can do with Nand is 4 gates to get Xor functionality.
If I use 2xNot, 2xAnd, 1xOr, then total number of Nand used is:
2 Not = 2 Nand
2 And = 4 Nand
1 Or = 3 Nand
Total of 9 Nand to implement the Xor.
So it is possible to do it with And, Or, and Not. But if your And, Or and Not are implemented in Nand then you are far more efficient doing it in Nand.
Hmmm.. This gets me wondering. Is this an always true cost of abstraction? Can anything build from abstracted And, Or, Not's always be build with less gates if ditch all abstraction and use Nand or Nor all the way? Anyone know?
|
|
|
cadet1620 wrote
JustinM wrote
I was just going through my chips again to make sure they are all abstracted properly. It doesn't seem like Xor can be abstracted with And, Or, or Not. Do I need to stick with 4 NAND gates?
You can always implement with Not, And and Or starting with the canonical form of any function.
The book, in fact, shows the canonical form of Xor as figure 1.5 and as the design example in figure 1.6.
An alternate canonical form is the "product of sums" which works like the sum of products canonical form, but you use the zeros in the function to determine the required terms, instead of the ones. This would give you
a xor b = ( a + b)(~ a + ~ b).
Try to think of an implementation using an And, and Or and a Nand.
--Mark
Thank you Mark. I forgot about that figure.
|
|
|
joobcode wrote
Everything can be made from the combinations of And, Or, Not. The section on "canonical representation" in chapter 1 shows how any function can be represented with And, Or, Not.
xor truth table
=========
a b o
0 0 0
0 1 1 !ab
1 0 1 a!b
1 1 0
!ab + a!b
Or with Polish notation:
Or ( And( Not(a), b ), And(a, Not(b) ) )
So yes it can be done. The above show you one way with 5 Gates. 2 Nots, 2 Ands and 1 Or.
At least for myself the best I can do with Nand is 4 gates to get Xor functionality.
If I use 2xNot, 2xAnd, 1xOr, then total number of Nand used is:
2 Not = 2 Nand
2 And = 4 Nand
1 Or = 3 Nand
Total of 9 Nand to implement the Xor.
So it is possible to do it with And, Or, and Not. But if your And, Or and Not are implemented in Nand then you are far more efficient doing it in Nand.
Hmmm.. This gets me wondering. Is this an always true cost of abstraction? Can anything build from abstracted And, Or, Not's always be build with less gates if ditch all abstraction and use Nand or Nor all the way? Anyone know?
Thank you for the lesson. I'll stick with my 4 NAND gates then. :)
|
|
Locked
