Digital Logic: Karnaugh Map

1. Sep 25, 2007

cepheid

Staff Emeritus
1. The problem statement, all variables and given/known data
Draw the schematic circuit diagram that implements the following expression using as few basic gates as possible (AND, OR, NOT, XOR, NAND, NOR).

The prime denotes the complement:

$$f = w^\prime z^\prime + w^\prime xy + wx^\prime z + wxyz$$

3. The attempt at a solution

From the truth table, I drew a Karnaugh Map (attached and linked to below. I'm just wondering whether I did it right. From the K-Map, the resulting simplification is:

$$f = w^\prime z^\prime + w^\prime xy + wx^\prime z + wyz$$

Is there no further simplification?

Attached Files:

• HW1_4b_KMAP.jpg
File size:
8.6 KB
Views:
64
2. Sep 25, 2007

fleem

$$f = w^\prime z^\prime + w^\prime xy + wx^\prime z + wxyz$$

The original equation has 15 operations, removing that last x gives you 14. the following gives you 11. There might be other things you could do, but I don't see any right off.

$$s = xy$$

$$f = w^\prime ( z^\prime + s) + w (x^\prime z + sz)$$

3. Sep 25, 2007

antonantal

If you circled the regions on the map like this:

you would have obtained a simpler expression:
$$f = w^\prime z^\prime + xyz + wx^\prime z$$

BUT this expression, as well as yours, has static hazard.

To eliminate the static hazard there must not be any pair of adjacent but disjointed regions circled on the map. So you must circle the regions like this:

which will give you the simplest expression without hazards:
$$f = w^\prime z^\prime + xyz + wx^\prime z + w^\prime xy + wyz$$

Last edited: Sep 25, 2007
4. Sep 25, 2007

fleem

Just to expand on this a bit, the thing about static hazard theory is that it is difficult to match with practice. This is because each type of gate has a different delay, each type's delay varies differently with temperature, and runs have different delays. Also, the above definition of static hazard either assumes NOT operations are infinitely fast, or that you buffer all signals with either an inverter a non-inverter but never both and assume their delays are equal. In practice, edge sensitive logic is either made synchronous (clocked), run lengths are adjusted accordingly and fingers are crossed, or off-the-shelf programmable ICs are used which are hopefully fairly hazard-less (and fingers are still crossed).