# Digital Logic: Karnaugh Map

Staff Emeritus
Gold Member

## Homework Statement

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$$

## 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?

http://img340.imageshack.us/img340/9333/hw14bkmapwm3.th.png [Broken]

#### Attachments

• 8.6 KB Views: 347
Last edited by a moderator:

Related Engineering and Comp Sci Homework Help News on Phys.org
$$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)$$

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?
If you circled the regions on the map like this:
http://img522.imageshack.us/img522/3419/3termswhazardqs5.th.jpg [Broken]
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:
http://img20.imageshack.us/img20/5679/3termswohazardtv7.th.jpg [Broken]
which will give you the simplest expression without hazards:
$$f = w^\prime z^\prime + xyz + wx^\prime z + w^\prime xy + wyz$$

Last edited by a moderator:
If you circled the regions on the map like this:
http://img522.imageshack.us/img522/3419/3termswhazardqs5.th.jpg [Broken]
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:
http://img20.imageshack.us/img20/5679/3termswohazardtv7.th.jpg [Broken]
which will give you the simplest expression without hazards:
$$f = w^\prime z^\prime + xyz + wx^\prime z + w^\prime xy + wyz$$
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).

Last edited by a moderator: