Digital Logic: Karnaugh Map

  • Thread starter cepheid
  • Start date
  • #1
cepheid
Staff Emeritus
Science Advisor
Gold Member
5,192
36

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:

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

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]
 

Attachments

Last edited by a moderator:

Answers and Replies

  • #2
437
0
[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]
 
  • #3
218
0
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?
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:
  • #4
437
0
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]
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:

Related Threads on Digital Logic: Karnaugh Map

  • Last Post
Replies
5
Views
617
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
670
  • Last Post
Replies
6
Views
12K
  • Last Post
Replies
2
Views
7K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
3
Views
1K
Replies
2
Views
2K
Replies
5
Views
1K
Replies
1
Views
2K
Top