1
\$\begingroup\$

For a boolean function, after drawing K-map we got that function in the form of the sum of products (minimal representation) but problem is that when we implement that minimal representation we use only "AND" and "OR" gates. Is this gate implementation also minimal regarding the number of used logic gates? In other words, for a given minimal function in the sum of products form can we further decrease the number of logic gates using NOR, XOR, etc. instead of ANDs and ORs.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ Sure. An adder implemented with XOR uses less gates than AND and OR. It's likely to be just as many transistors, since the XOR is correspondingly more complex. \$\endgroup\$
    – stark
    May 10, 2022 at 20:04
  • \$\begingroup\$ Minimal SOP is not necessarily minimal from the gates perspective. Even with the same type of gates. For example AB + AC will take 3 gates to implement, while equivalent A(B+C) - only two. \$\endgroup\$
    – Eugene Sh.
    May 10, 2022 at 20:10
  • \$\begingroup\$ And just to stir the "minimal" pot, here's Konrad Zuse's full adder. Note that it only uses two "logic gates." (Those "gates" were the fundamental building block unit.) \$\endgroup\$
    – jonk
    May 10, 2022 at 20:13
  • \$\begingroup\$ Thank you all, well, are there certain techniques for reducing, or do we have to look for them? \$\endgroup\$
    – Ekrem_Abi
    May 10, 2022 at 20:18
  • \$\begingroup\$ Reducing the boolean function is a good start. Then you might want to compare the SOP vs POS forms. From there I am not aware of any manual formal techniques, just intuition based. Surely, computer tools exist, but I believe these will be heuristic-based for any non-trivial system. \$\endgroup\$
    – Eugene Sh.
    May 10, 2022 at 20:22

1 Answer 1

3
\$\begingroup\$

For a boolean function, after drawing K-map we got that function in the form of the sum of products (minimal representation) but problem is that when we implement that minimal representation we use only "AND" and "OR" gates.

The old PAL/GAL devices were based on AND/OR logic grids, which directly maps SOP.

Is this gate implementation also minimal regarding the number of used logic gates?

No, not at all. For example, \$Z=A B+B C\$ would have the following k-map and implementation using SOP AND/OR logic:

enter image description here

But could just as well be implemented as POS OR/AND logic as \$Z=\left(A+C\right)B\$:

enter image description here

In other words, for a given minimal function in the sum of products form can we further decrease the number of logic gates using NOR, XOR, etc. instead of ANDs and ORs.

The above shows that it can be reduced even without including NOR, XOR, etc.

But, in general, logic can often also be further reduced using additional options such as XOR, NOR, NAND, etc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.