Lecture 6 Karnaugh map (K-map)

Karnaugh maps (K-maps)
Flat representation of Boolean cubes

K-maps with “don’t cares”  Easy to use for 2– 4 dimensions
 Harder for 5 – 6 dimensions
 Virtually impossible for >6 dimensions

Use CAD tools

Help visualize adjacencies
 On-set elements that have one variable
changing are adjacent
1 2

Karnaugh map (K-map) 2, 3, and 4 dimensional K-maps

Uses Gray code: Only one bit changes

A B F
A
between cells
0 0 0 1 B 0 1
1 0 1 0 0 1 1 F = B'  Example: 00 → 01 → 11 → 10
0 2
AB A
2 1 0 1
1 0 0 A CD 00 01 11 10
3 1 1 0 1 3
AB A
A
0 1 00
B C 00 01 11 10 0 4 12 8
0 0 01
0 2 0 2 6 4 1 5 13 9 D
B 1 1 3
C 1 11
1 3 7 5 3 7 15 11
C
B 10
2 6 14 10

B
3 4

Adjacencies K-map minimization

Wrap–around at edges
Find the least number of subcubes,

 First column to last column each as large as possible, that cover
 Top row to bottom row the ON-set.
AB A 011 111
C 00 01 11 10
010
Make sure subcubes contain 1, 2, 4, or
0 000 010 110 100
0 2 6 4
B C
001
101
8 items (remember the Boolean cube)
C 1 001 011 111 101
1 3 7 5
000 A 100
B

5 6
 Example 1 Example 2

A B C D
A B Cin Cout 0 0 0 0 A
0 0 0 0 A 0 0 1 0 AB
0 0 1 0 AB C 00 01 11 10
Cin 00 01 11 10 0 1 0 0
0 1 0 0 0 1 1 1 0 0 0 1 1 D = A + BC
0 1 1 1 0 0 0 1 0 Cout = AB + BCin + ACin 0 2 6 4
0 2 6 4 1 0 0 1 1
1 0 0 0 1 0 1 1 0 1 1 1
1 0 1 1 1 1 3 7 5
1 0 1 1 1 3 7 5
1 1 0 1 B
1 1 0 1 B 1 1 1 1 111
1 1 1 1 111

B 101
B Cin
Cin
101 000 A
000 A

7 8

Example 3 Finding the complement

AB A
A
C 00 01 11 10 AB F(A,B,C) = Σm(0,4,5,7)
C 00 01 11 10
F(A,B,C) = Σm(0,4,5,7) 0 1 0 0 1 = B'C'+AC
0 2 6 4 0 1 0 0 1
= B'C'+AC 0 2 6 4
1
1
0 3
0 7
1 5
1 1 0 0 1 1 F'(A,B,C) = Σm(1,2,3,6)
1 3 7 5
B = A’C + BC’
B

9 10

Example: 4 variables Exercise

F(A,B,C,D) = Σm(0,3,7,8,11,15)

Minimize F(A,B,C,D) = F(A,B,C) = Σm(0,3,6,7)
F(A,B,C,D) =
Σm(0,2,3,5,6,7,8,10,11,14,15) F(A,B,C) = F’(A,B,C,D) =

Answer: F = C+A'BD+B'D' F'(A,B,C) =

AB A AB
CD 00 01 11 10 0111 1111 CD 00 01 11 10
00 1 0 0 1 00
0 4 12 8
01 0 1 0 0 AB 01
1 5 13 9 C 00 01 11 10
D C D
A
11 1 1 1 1 1000 0 11
C 3 7 15 11 0000 B
10 1 1 1 1 1 10
2 6 14 10

B
11 12
 6-dimensions Incompletely specified functions
CD
K-maps become 3D CD
EF 00 01 11 10
for 5 & 6 variables EF 00
0
01
0
11
0
10
0 00 1 0 0 0
Functions of n inputs have 2n possible
00

01 0 0 1 1
01 0 0 1 1 configurations
AB = 00 AB = 01
11 0 0 1 1
11 1 0 1 1  Some combinations may be unused
10 0 0 0 0
10 1 0 0 0  Call unused combinations “don’t cares”
CD CD  Exploit don’t cares during logic
00 01 11 10 00 01 11 10
EF EF
minimization
00 0 0 0 0 00 0 0 0 0
OUTPUT =
A’BC’D’F’ + 01 0 0 1 1 01 0 0 1 1
 Don’t care ≠ no output
AB = 10
CF + BC’D’E AB = 11
11 1 0 1 1 11 0 0 1 1

There will always be an output signal
10 1 0 0 0 10 13 14
0 0 0 0

Don't cares BCD increment-by-one

INPUTS OUTPUTS

Example: A BCD increment-by-1 A B C D W X Y Z off-set for W: m0–m6, m9
0 0 0 0 0 0 0 1
 Function F computes the next number in 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1
a BCD sequence 0 0 1 1 0 1 0 0
0 1 0 0 0 1 0 1

If the input is 00102, the output is 00112 0 1 0 1 0 1 1 0 on-set for W: m7 and m8
0 1 1 0 0 1 1 1
 BCD encodes decimal digits 0–9 as 0 1 1 1 1 0 0 0
00002–10012 1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0

Don’t care about binary numbers 10102– 1 0 1 0 X X X X
1 0 1 1 X X X X Don't care set for W:
11112 1 1 0 0 X X X X We don't care
1 1 0 1 X X X X about the output values
1 1 1 0 X X X X
1 1 1 1 X X X X
15 16

Don't care notation Example

Minterm expansion
F(A,B,C,D) = Σm(1,3,5,7,9) + d(6,12,13)
W = m7+m8+d10+d11+d12+d13+d14+d15  F = A'D + B'C'D without using don't cares
= Σm(7,8) + d(10,11,12,13,14,15)
 F = A'D + C'D using don't cares
A

Maxterm expansion AB
CD 00 01 11 10
W = M0•M1•M2•M3•M4•M5•M6•M9•D10•D11•D12•D13•D14•D15 Assign X == "1"
00 0 0 X 0
= ΠM(0,1,2,3,4,5,6,9) • D(10,11,12,13,14,15) ⇒ allows a 2-cube rather than a 1-cube
01 1 1 X 1
D

In K-maps, can treat ‘don't cares’ as 0s or 1s 11 1 1 0 0
C
depending on which is more advantageous 10 0 X 0 0
B
17 18