» CS 352 Lecture 7 – Karnaugh Maps

CS 352 Lecture 7 – Karnaugh Maps

September 21, 2016 by Chris Johnson. Filed under cs352, fall 2016, lectures.

Dear students,

We start today with a couple more exercises on building circuit diagrams. Let’s do these one a time. Write your diagram down on paper, and then we’ll construct it together up front:

Diagram This #1

You will eat a cheap pizza if it has pepperoni without olives, or if it has olives with neither sausage nor peppers. However, if you paid a lot of money for it, you will eat it no matter what.

Diagram This #2

You will house sit for a friend, provided the friend has a cat—but no dog—or the friend has a dog—but no cat.

Diagram This #3

Inspired by Code, by Charles Petzold: “I want a male cat, neutered, either white or tan; or a female cat, neutered, any color but white. However, if the cat has claws, no deal.”

Diagram This #4

A year is leap if it’s divisible by 4, but not if divisible by 100, unless it’s also divisible by 400.

As we complete each of these, we will tally up how many transistors each requires. How many transistors does an AND gate require? An OR gate? A NOT gate?

We’ve gained some practice at converting boolean expressions to circuits. But suppose you’re sitting in your basement office at the hardware company you’re interning at, and your boss hands you a truth table and says, “Here, make this.” How do you turn a truth table into a boolean expression? This isn’t such a crazy scenario. Sometimes you just know how a circuit is supposed to behave based on its inputs.

One means of conversion is construct the sum of products, or what we’ll call the or of the ands. First draw out your truth table. Let’s use this one as an example:

A	B	Y
0	0	1
0	1	0
1	0	1
1	1	1

Each of these rows can be described with a minterm, which is just the ANDing of the input columns:

A	B	Y	minterm
0	0	1	`!A && !B`
0	1	0	`!A && B`
1	0	1	`A && !B`
1	1	1	`A && B`

The sum of products or the or of the ands is just the ORing of all the minterms that evaluate to 1 for a given circuit. In this case, there are three minterms that are 1, and the resulting boolean expression is:

(!A && !B) || (A && !B) || (A && B)

Let’s try creating sums of products for a couple more circuts:

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

A	B	C	Y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	0	1
0	0	1	0
0	1	1	1
1	0	1	0
1	1	1	0

However, not every boolean expression derived using the sum or products is as simple as can be. When you’re building a hardware component, you’d generally like to use as few transistors as possible. We will discuss Karnaugh maps (or K-maps) as a way to simplify expressions and the hardware that captures their behavior. We’ll create Karnaugh maps for:

The first table above.
The second table above.
The third table above.
The expression !A && B && C || !A && B && !C.
The expression !A && !B && !C || A && !B.

Here’s your TODO list:

Watch the videos below on constructing Karnaugh maps.
On a quarter sheet, draw Karnaugh maps and show the resulting simplifications of these two expressions:
```
A && C || !A && !B && C
!A && !B || !A && B && !C || !(A || !C)
```

See you next class!

Sincerely,