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

Question

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.

slebetman · Accepted Answer · 2016-09-28 04:36:12Z

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

jbord39 · Accepted Answer · 2016-09-29 22:34:25Z

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.

Stack Exchange Network

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

2 Answers 2

Linked

Hot Network Questions

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

2 Answers 2

Linked

Related

Hot Network Questions