# How can I convert multiple Karnaugh maps into a logic gate circuit?

I'm designing a 8421 BCD to 84-2-1 BCD converter circuit. The truth table is:

Decimal | ABCD | WXYZ
0    | 0000 | 0000
1    | 0001 | 0111
2    | 0010 | 0100
.      .
.      .
.      .
9    | 1001 | 1111


Everything after decimal 9 is a don't care. I started by creating Karnaugh maps for each W, X, Y, Z. From the Karnaugh maps, I found the following equations:

W = (A)(~B)(~C) + (~A)(B)(C+D)
X = (~A)(~C)(~D) + (~A)(~B) + (~B)(D)
Y = (~C)(D)([~A]+[~B]) + (~A)(C)(~D)
Z = (D)([~A]+[~B][~C])


Where multiplication means AND, addition means OR, and ~ means NOT. I'm unsure of how draw a circuit with the appropriate logic gates from here. Do I create a circuit for each letter and then AND all of the outputs together? Do I combine all of the expressions (as in W+X+Y+Z or WXYZ) and simplify the expressions from there, then create a circuit using the new simplified expression? I'm not really interested in what this particular circuit will actually look like, I'm trying to find tackle the more general concept of moving from truth tables to circuit schematics.

Do I combine all of the expressions (as in W+X+Y+Z or WXYZ)

No. What the equations show you are how to derive outputs for four separate pins. If you wanted to combine the four pins you should have done it earlier when coming up with the Karnaugh map (the Karnaugh map would then only have one output instead of four).

First step, treat the four as four separate circuits:

A ─┬───────────────┐
│               │
B ──┬─[NOT]────────[AND]┐
││              │    │
C ────[NOT]──┬─────┘    [OR]── W
││        └[OR]─┐    │
D ────────────┘    │    │
│└──────────────[AND]┘
└──[NOT]────────┘

.... implementation of other circuits left as homework

A ──[NOT]────────┐
│
B ──[NOT]──┐     [OR]─┐
[AND]─┘    │
C ──[NOT]──┘          [AND]── Z
│
D ────────────────────┘


Second step, join A to A, B to B etc.. This is obvious because obviously A is the same as A etc.

A ─┬────┬───────────────┐
│    │               │
B ──┬────┬─[NOT]────────[AND]┐
││   ││              │    │
C ───┬─────[NOT]──┬─────┘    [OR]── W
│││  ││        └[OR]─┐    │
D ────┬────────────┘    │    │
││││ │└──────────────[AND]┘
││││ └──[NOT]────────┘
││││
└───────[NOT]────────┐
│││                 │
└──────[NOT]──┐     [OR]─┐
││           [AND]─┘    │
└─────[NOT]──┘          [AND]─ Z
│                      │
└──────────────────────┘

.... implementation of other circuits left as homework


The circuit should be working at this point but if you're paying attention you may notice that some parts of the W and Z circuits are sharing the same logic. For example, we're using NOT on B and C twice. The next (optional) step is to refactor the circuit and remove redundant/repeated subcircuits and components:

A ───┬──────────────────┐
│                  │
B ────┬─[NOT]──┬────────[AND]┐
││        │        │    │
C ──────[NOT]───┬──┬────┘    [OR]── W
││        ││  │         │
││        ││  [OR]─┐    │
D ─┬───────────────┘    │    │
│ ││        ││       │    │
│ │└─────────────────[AND]┘
│ │         ││       │
│ └──[NOT]─┬─────────┘
│          │││
│          └─────────┐
│           │└─┐     [OR]─┐
│           │  [AND]─┘    │
│           └──┘          [AND]─ Z
└─────────────────────────┘

.... implementation of other circuits left as homework


Other answers describe the academic way of solving such problems. This is excellent for learning the basics.

But in the real world, or your next project, you might have hundreds of inputs/outputs at a time. In this case you may instead use software for the minimization/synthesis.

Since you already have the truth table, you could easily install the plugins for "espresso" and "abc" which are both free programs developed by University of Mass/Berkeley.

espresso documentation

Espresso is a logic minimizer. ABC is a synthesis engine.

If you provide espresso the combined truth table, using it's own format:

         # 2-bit by 2-bit binary adder (with no carry input)
.i 4
.o 3
0000  000
0001  001
0010  010
0011  011
0100  001
0101  010
0110  011
0111  100
1000  010
1001  011
1010  100
1011  101
1100  011
1101  100
1110  101
1111  110


It can provide the minimized equations. It uses a two-step heuristic algorithm, which is actually included in many industry standard tools.

Alternatively, you can also provide ABC (documentation) a boolean representation (as equation, truth tables, and many other formats) as well as a list of gates to use, and it will synthesize the circuit for you in terms of those gates. This includes refactoring and all other sorts of optimization, as you choose.