4
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Just so you know, XOR gates are much less efficient in implementation than most other gates, and AND/OR gates are less efficient than NAND/NOR gates. Simple comparisons of number of gates is not the best metric to use. \$\endgroup\$ – Reinstate Monica Nov 6 '15 at 21:39
  • 1
    \$\begingroup\$ Hint : do an image search or k-map xor. You'll notices a checkerboard pattern. XOR gates are less efficient then other gates, but more efficient then the sum of the parts to match the same functionality. So use XOR gates on when necessary. \$\endgroup\$ – Greg Nov 6 '15 at 22:05
  • 1
    \$\begingroup\$ I can't help with bi-decomposition, but your netlist does an arithmetic \$a+b+c+d==3\$ so you can make it with two adders with carry. The resulting equation is \$((a \:xor \: b) + (c\: xor \:d))(a\:b + c\:d)\$, similar to the one in figure 3. You car read the equation as one of the sums should have carry, and one of the sums should be odd \$\endgroup\$ – NicolaSysnet Nov 9 '15 at 13:11
  • 1
    \$\begingroup\$ Did you ask this because you couldn't afford the [full] paper where you found those results? books.google.com/books?id=M_ZEBAAAQBAJ&pg=PA822 Also, this is not simply bi-decomposition. \$\endgroup\$ – Fizz Nov 14 '15 at 13:37
  • 1
    \$\begingroup\$ By the way, the paper has a free preprint. informatik.tu-freiberg.de/prof2/publikationen/… So -1 for combination of laziness and not disclosing the source. \$\endgroup\$ – Fizz Nov 14 '15 at 13:51
4
+50
\$\begingroup\$

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:

\$\endgroup\$
  • \$\begingroup\$ Thank you a lot for your solution! Just as far as I understood the bi-decomposition takes the boolean function and tries to divide it into sub functions, minimize them and than put it together again. So how to find and generate "good" subfunctions. To solve functions in general with bi-decomposition. Am I right? \$\endgroup\$ – kimliv Nov 13 '15 at 12:29
  • \$\begingroup\$ @kimliv, the full explication was too bit for a comment, so I added it in my answer. In summary, yes, you got the idea; sub-functions \$\endgroup\$ – Greg Nov 13 '15 at 16:52
  • \$\begingroup\$ Actually, the final graphs from the OP's question are take from a more recent paper by Steinbach (without disclosure where they came from). Furthermore that paper contains the full algorithm by which the results were obtained. \$\endgroup\$ – Fizz Nov 14 '15 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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