boolean-algebralogic-gates
Given I am still learning how to do these Boolean Algebra, I was wondering if someone could tell me if I am on the right track.
All work is pictured. I figured that the circuit drawn is the actual circuit and not simplified using the Karnaugh map. Also does that have 3 gates technically or just two?
Any help is appreciated!
EDIT: I know this is wrong but I am not sure where I went wrong. Has to be in the Karnaugh map but I dont understand why or where.
The overal trick to the bi-decomposition solution is with identfying XORs.
A 4 variable XOR of \$X \oplus Y \oplus X \oplus W\$ generates the below Karnaugh map (k-map). Notice the checkerboard pattern.
Except the final row and column, it lines up with your k-map. Therefor we can use the 4 variable XOR as a base and mask the the undesired ones. With your table, you want to mask ones when \$\bar{A}\bar{D}\$ or \$\bar{B}\bar{C}\$. The inverse (when you allow ones) is then the equation \$\overline{\bar{A}\bar{D}+\bar{B}\bar{C}}\$ which is simplified to \$(A+D)(B+C)\$, proof below.
$$ \overline{\bar{A}\bar{D}+\bar{B}\bar{C}} \\ \equiv (\overline{\bar{A}\bar{D}})(\overline{\bar{B}\bar{C}}) \\ \equiv (\overline{(\bar{A})}+\overline{(\bar{D})})(\overline{(\bar{B})}+\overline{(\bar{C})}) \\ \equiv (A+D)(B+C) $$ Add in the XOR and get \$(A \oplus B \oplus C \oplus D)(A+D)(B+C)\$. This is 4 gates; one 4-input XOR, two 2-input OR, and one 3-input AND. If everything is turned to 2-input gates, then it becomes 7 gates; three XOR, two OR, and two AND. This matches the bi-decomposition Fig.2.
$$ (A \oplus B \oplus C \oplus D)(A+D)(B+C) \\ \equiv ((A \oplus B) \oplus (C \oplus D))(A+D)(B+C)\\ \equiv (((A \oplus B) \oplus (C \oplus D))(A+D)) (B+C) \, \, \# \, as \, 2-input \, gates $$
The bi-decomposition Fig.3 uses an approach that grabs the smallest XOR; \$A \oplus B\$ and \$C \oplus D\$, then gate out the Rest. \$(A \oplus B)CD\$ and \$AB(C \oplus D)\$. Finally ORing them together \$(A \oplus B)CD + AB(C \oplus D)\$. Then convert to 2-input gates \$((A \oplus B)C)D + A(B(C \oplus D))\$. This now matches Fig.3.
$$ grp0 = (A \oplus B)CD \, \, \# \, first \, smallest \, XOR \, group \\ grp1 = AB(C \oplus D) \, \, \# \, second \, smallest \, XOR \, group \\ grp0 + grp1 = (A \oplus B)CD + AB(C \oplus D) \\ \equiv ((A \oplus B)C)D + A(B(C \oplus D)) \, \, \# \, as \, 2-input \, gates $$
I had to lookup the definition of "bi-decomposition", and my explication is too big to fit in a comment. "Bi-decomposition" used to be called "grouping"; which I vaguely remember my professor calling it many years ago. The process is to taking a function and composing it as sub-functions. This approach is piratically useful where the only neighboring 1s on a K-map are diagonal. XOR/XNOR then express the sub-functions.
The best online description I found are:
I am going to work through this to the best of my ability - according to the excellent hint in the answer from Tom Carpenter's answer.
We start with
\$X = A_2 \overline A_1 + \overline Q_1 A_2 + Q_1 \overline A_2 A_1\$
which we can write as
\$ X = A_2(\overline A_1 + \overline Q_1) + Q_1 \overline A_2A_1 \$
and hence
\$ X = A_2(\overline{\overline{\overline A_1 + \overline Q_1}}) + Q_1 \overline A_2A_1 \$
then we can remove line redundancy and apply de Morgan's rule
\$ X = A_2(\overline{ A_1 Q_1}) + Q_1 \overline A_2A_1 \$
now add two more bars over the entire statement
\$ X = \overline { \overline { A_2(\overline{ A_1 Q_1}) + Q_1 \overline A_2A_1 }}\$
and then reapply de Morgan's rule
\$ X = \overline { \overline { A_2(\overline{ A_1 Q_1})} \cdot \overline {Q_1 \overline A_2A_1 }}\$
We can then draw this out as:
This is just 5 gates, and going through the truth table seems to show that the functionality is as required.
Best Answer
What constitutes one single gate is open to interpretation. Other than that, use the algebra right there:
AB + BC = F
Factor B to give:
F = B (A + C)
This equates to one AND gate and one OR gate.