1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Digital Logic: Karnaugh Map

  1. Sep 25, 2007 #1


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:

    [tex] f = w^\prime z^\prime + w^\prime xy + wx^\prime z + wxyz [/tex]

    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:

    [tex] f = w^\prime z^\prime + w^\prime xy + wx^\prime z + wyz [/tex]

    Is there no further simplification?

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

    Attached Files:

    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Sep 25, 2007 #2
    [tex] f = w^\prime z^\prime + w^\prime xy + wx^\prime z + wxyz [/tex]

    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.

    [tex] s = xy [/tex]

    [tex] f = w^\prime ( z^\prime + s) + w (x^\prime z + sz) [/tex]
  4. Sep 25, 2007 #3
    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:
    [tex] f = w^\prime z^\prime + xyz + wx^\prime z[/tex]

    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:
    [tex] f = w^\prime z^\prime + xyz + wx^\prime z + w^\prime xy + wyz[/tex]
    Last edited by a moderator: May 3, 2017
  5. Sep 25, 2007 #4
    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: May 3, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook