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

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:

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):

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]

13 logic gates

C.) Simplifying the function on Wolfram Alpha

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

11 logic gates

(tool used for visualisation: logic.ly)

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

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.

• 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. Commented Nov 6, 2015 at 21:39
• 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.
– Greg
Commented Nov 6, 2015 at 22:05
• 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 Commented Nov 9, 2015 at 13:11
• 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. Commented Nov 14, 2015 at 13:37
• 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. Commented Nov 14, 2015 at 13:51

## 1 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.

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:

• 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? Commented Nov 13, 2015 at 12:29
• @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
– Greg
Commented Nov 13, 2015 at 16:52
• 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. Commented Nov 14, 2015 at 14:01