Electronic – Generating a circuit that match a given boolean function using bi-decomposition

boolean-algebradigital-logiclogic-gates

I am looking for an step by step explanation of how to get the circuit of an given boolean function using bi-recomposition.

I have a given function like:

f(a,b,c,d)=abc~d+ab~cd+a~bcd+~abcd

The normal ways I know are:

A.) Karnaugh plan:

Truth Table

k-map:

k-map

result:

  1. DNF: f=~abcd + a~bcd + ab~cd + abc~d
  2. KNF: (~a+~b+~c+~d) * (a+b) * (a+c) * (b+c) * (a+d) * (b+d) * (c+d)

DNS in Gates(a~bcd):
DNS for f(abcd)

B.) Second method: minimisation by Quine & McCluskey:

The rsult is also: f=(~abcd)+(a~bcd)+(ab~cd)+(abc~d)

(tool) with input 1: a,b,c,d and 2: [7,11,13,14]

circuit

13 logic gates

C.) Simplifying the function on Wolfram Alpha

The result is: f=(abc)XOR(abd)XOR(acd)XOR(bcd)
result circuit wolframalpha

11 logic gates

(tool used for visualisation: logic.ly)

D.) With bi-decomposition I found this result:

enter image description here

7 logic gates (performance has to be tested by benchmarks)

But how to get there? A step by step explanation / pseudo code is what I am looking for.

Best Answer

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.
enter image description here

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.

bi-decomposition Fig.2 proof

$$ (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 $$

bi-decomposition Fig.3 proof

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:

Related Topic