# Reducing the Number of Logic Gates by Gate Sharing

Truth table :

Circuit :

This circuit is created with K-map so it should have been simplified. Is it possible to reduce the number of logic gates by gate sharing? Are there any rule guiding me to do gate sharing?

In this instance I can see no way of reducing the number of logic gates. You can only "share" gates if the inputs are the same between instances of a gate, or they share a subset of the inputs that could be separated off into another gate.

The only optimization I can see at the moment is:

$$A_1 = D_2 + D_3$$ $$V = D_0 + D_1 + D_2 + D_3$$

can be re-written as:

$$A_1 = D_2 + D_3$$ $$V = D_0 + D_1 + A_1$$

That just reduces an OR gate from 4-input to 3-input.

Looking at the logic functions like that (+ = OR, × = AND, ¬ = NOT, etc) it is just like working with normal algebra, and you can group and simplify as you would with any other formula.

As an exercise, let's look at the $A_0$ output and how it is formed:

$$A_0 = (D_1 × ¬D_2) + (D_3 × ¬D_2)$$

Any repeated terms are candidates for reduction to a single gate - in this case $¬D_2$ is repeated, so that is reduced to one NOT gate (as in your diagram). The same can be done for grouped terms - if you have groups of terms that are atomic (i.e. in the equations $A × B + C$ and $C + A × B$ the term $A × B$ is atomic in that it is the first term evaluated and isn't affected by any other term) then they can be candidates for shared gates as well.

• In general, look at the truth table of the system and see if you can spot truth tables of known gates within the system's table. Pay attention to XOR and NXOR forms, a lot of time they are easy to miss. There are techniques to do gate level sharing optimization after 'formula reduction' however none of them cover everything as far as I know. Commented Jun 14, 2014 at 12:56

The top line of the truth table should read:

     D3  D2  D1  D0       A1  A0  V
|---|---|---|---|----|---|---|---|
0   0   0   0        0   0   0

• Agreed. To have an output of "don't care" implies it is connected to an input that is being ignored, and they're not connected to anything specific. Of course, it could be tri-state, in which case the diagram and the truth table don't match up... Commented Jun 14, 2014 at 16:25