Three problems. Each one gets solved completely before the next one starts, and each one needs exactly one thing you have not seen yet.
Collect the send off. Somebody will have shrunk bar c by hand, and that is problem three.
The hour, in advance.
PROBLEM ONE
A boiler with three sensors
Small enough that you can see the waste by staring at it.
4 AND gates
3 AND gates
PROBLEM TWO
Is the digit prime?
Sixteen rows. Staring stops working, so we need a better way to look.
4 AND gates
2 AND gates
PROBLEM THREE
Bar c of the display
The debt from last session. The better way of looking is still not enough.
9 AND gates
none at all
the shape of each one
State the problem. Write the table. Build it the Class 15 way and count the gates.
Then find what the building method could not see, fix it, and rebuild.
Nothing is left half done. Each problem finishes before the next one is mentioned.
Promise the nine to none now. It sounds impossible and it makes them watch through two other problems to get there.
problem one · state it, then table it
Three sensors on a boiler. Shut it down if at least two say the temperature is too high.
Nobody said the word logic. It is a rule about sensors, said the way a plant engineer would say it.
Three inputs means eight situations, and you decide what happens in each. That is the whole specification.
Four of the eight want a shutdown, so the Class 15 method gives four detectors.
Fill the eight rows aloud with the room. Forty seconds, and it settles that the table is not the hard part.
problem one · built the class fifteen way · click any input
Four detectors, four AND gates, twelve wires into them.
look at it before moving on
Every gate tests all three sensors. The bottom two gates differ by one wire and nothing else.
Sum of products walks down the table writing one detector per row. It never compares two rows.
So it cannot notice a near duplicate, and there are three of them on this board.
Ask them to find the near duplicate pairs on the drawing. They will find at least one unaided.
problem one · take two of the four and line them up
These two agree on everything except s1, and between them they cover both values of it.
so ask the obvious question
Whatever s1 happens to be doing, one of these two detectors fires. Both mean shut down.
So why is anybody testing s1 at all?
Get a student to say the last line before you do. It is the entire hour in one sentence.
NEW TECHNIQUE · THE MERGE
Click the algebra to step through it, then press merge.
remember
Factor out what they share, then a variable or its opposite is always true, then anding with true changes nothing.
Nothing was approximated. All three lines are equalities, proved by Boole in 1847 and made facts about copper by Shannon in 1937.
You never build a circuit to check a simplification. The algebra already settled it.
Click the algebra panel to advance a line at a time, and write each line on the board as it appears.
problem one · the same move fits in three places
Step through them.
The all ones term gets merged three separate times. A term may be reused, and that surprises people.
PROBLEM ONE · SOLVED
Three gates of two inputs, and it reads like the problem statement.
AS BUILT
4
AND gates · 12 wires
SOLVED
3
AND gates · 6 wires
what this problem taught
The merge. Two terms differing in one variable become one term without it.
Read the answer aloud: shut down if one and two agree, or one and three, or two and three. That is the original sentence.
This worked because eight rows fit in your head. The next problem has sixteen.
The minimal form is very often the one a human would have written. Say so, then move on.
problem two · new problem, same method
The pump display drives a small lamp. Light it when the digit showing is prime.
The four wires already carry the digit in binary. The primes below ten are 2, 3, 5 and 7.
Four inputs means sixteen rows, of which ten are digits. Four of those ten want the lamp on.
So again, four detectors. But each one now tests four wires instead of three.
There is no pattern in the primes. That is the point, and it is why nobody can guess this circuit.
problem two · built the class fifteen way · click any input
Four AND gates, sixteen wires into them.
now try what worked last time
Look for two terms differing in exactly one variable. There are sixteen rows and each has four possible neighbours.
That is thirty two pairs to check, on a table written in counting order that scatters them.
It is doable and it is horrible, and at five variables it stops being doable at all.
Give them ninety seconds to try. Some will find one pair. Nobody will be confident they found all of them.
NEW TECHNIQUE · THE MAP
Rearrange the table so that mergeable means touching.
remember
Counting order steps 01 to 10 and changes both bits at once, so those two rows can never merge and sit next to each other anyway.
Gray order changes exactly one bit at every step, so every neighbour is a possible merge.
It also wraps: the last entry is one bit from the first. Half of all mistakes in this topic come from forgetting that.
Frank Gray and Maurice Karnaugh, both at Bell Labs, both in 1953.
Say the wrap twice here and a third time on the next slide.
problem two · the same sixteen rows, laid out in gray order both ways
Now the merges are visible without looking for them.
the rules for circling
Rectangles of 1, 2, 4 or 8 cells. Never 3, never 6, because those do not cover a variable completely.
As large as they will go. Each doubling of a circle deletes one more literal from its term.
Circles may overlap and may wrap round the edges. Overlap is free.
Every 1 must be inside a circle, and no circle may touch a 0.
Click cells to show them a wrap-around circle and a group of four before you settle back on the primes.
PROBLEM TWO · SOLVED
Two gates of three inputs. Sixteen wires became six.
AS BUILT
4
AND gates · 16 wires
SOLVED
2
AND gates · 6 wires
what this problem taught
The map. Gray order turns "differs in one variable" into "shares an edge", and your eye does the search.
Half the gates and a third of the wires, on a problem with no pattern anybody could have guessed.
Check it: 2 and 3 both have w and x off and y on. 5 and 7 both have w off, x on, z on. Two circles, two terms.
Step the inputs through 0 to 9 and confirm the lamp lights on exactly four of them.
problem three · the one you were sent home with
Bar c of the pump display. Lit for nine digits out of ten.
Nine rows want the bar lit, so the Class 15 method gives nine detectors of four wires each.
Thirty six wires, for a bar that is dark for exactly one digit.
Anybody can see this should be smaller. The question is by how much.
Ask what they got by hand. Somebody will have found the one dark digit and inverted it, which is the right instinct.
problem three · nine detectors, built the class fifteen way
This is what nine AND gates of four inputs looks like.
Let it sit. No commentary. The drawing is the argument.
problem three · apply what problem two taught · click any cell
Nine ones and one zero. Three circles cover the lot.
good, and not good enough
Nine AND gates of four inputs became three of two. Thirty six wires became six.
But three gates still feels like too many for a bar that is dark for one digit.
Look at the bottom two rows. Those six cells are inputs 1010 to 1111, which are not digits at all.
Do not move on until somebody notices the six cells are being forced to zero for no reason.
NEW TECHNIQUE · DON'T CARES
Six of those sixteen inputs cannot occur.
The digits are 0 to 9. The combinations 1010 through 1111 are not digits, and the counter driving the display never produces them.
So what should the bar do in those six cases? The honest answer is that nobody cares.
Which means you may pick whichever answer makes the circuit smaller.
remember
Write an X there instead of a 0. It is not an unknown value, it is a free choice you get to make.
When circling, treat an X as a 1 if that lets a circle grow, and ignore it otherwise. You may split them however you like.
Nothing is approximated. Every input that can actually arrive still gets exactly the right answer.
Writing 0 there was over specifying: telling the circuit what to do in cases that never happen, and paying for it in gates.
Over specifying is the phrase to leave them with. It costs real money and it is very easy to do by accident.
problem three · six cells changed from 0 to X · click one back to 0 and watch
Every circle grows to a whole row or column.
remember
Each circle covers eight cells now, so each term is down to a single literal.
A term of one literal needs no AND gate at all. It is a wire straight from a rail to the OR.
Nine AND gates have become zero. What is left is one inverter and one OR gate.
Toggle a single X back to 0 and a circle immediately halves. That is what the free choice was worth.
Do the toggle live. It is the clearest demonstration in the deck of what don't cares actually buy.
PROBLEM THREE · SOLVED
One inverter and one OR gate. Click through all ten digits.
AS BUILT
9
AND gates · 36 wires
WITH THE MAP
3
AND gates · 6 wires
WITH DON'T CARES
0
no AND gates at all
what this problem taught
Don't cares. Inputs that cannot happen are free choices, and free choices make circles bigger.
Read the answer: the bar is lit unless x is off and y is on and z is off, which is the single digit 2.
That is exactly the instinct some of you had by hand. The map is how you get there without guessing.
Check every digit against the display from Class 16. It should be dark on 2 and lit on the other nine.
Three problems, and each one earned one technique.
FROM PROBLEM ONE
The merge
Two terms differing in exactly one variable become one term without it. Three lines of Boole's algebra, and every line is an equality.
FROM PROBLEM TWO
The map
Gray order turns "differs in one variable" into "shares an edge", so finding merges becomes looking rather than searching.
FROM PROBLEM THREE
Don't cares
Inputs that cannot occur are not constraints. Marking them free lets circles grow, and bigger circles mean smaller gates.
and one sentence underneath all three
Sum of products is correct and blind. It writes one detector per row and never compares two rows to each other.
Everything today was a way of doing the comparing it refuses to do.
Put the three names on the board. These are the words they need for the exam and for reading a datasheet.
Apply all three to every bar of the display.
remember
Forty nine AND gates became sixteen. One hundred and ninety six wires into gates became forty two.
Two thirds of the gates gone, and the behaviour did not change by a single row of a single table.
On a four digit pump that is about two hundred gates down to sixty five, on every unit ever manufactured.
Say the manufacturing line out loud. Minimisation is not an aesthetic preference, it is a unit cost.
the same honest limit as class sixteen
A map works because a human eye can take in the whole of it at once.
remember
Five variables means two maps stacked, with adjacency running between the sheets. Six means four. Nobody does eight.
So the merge got mechanised: Quine and McCluskey wrote it as an algorithm in the 1950s, doing exhaustively what you did by eye.
That is exponential too, so real tools use heuristics. The standard one is Espresso, from Berkeley in 1982.
You will never minimise a real circuit by hand. You will read many minimised circuits, and now you know what was done to them.
Same shape as Class 16. The hand method teaches the idea, the tool does the work, and the idea is what lets you read the output.
One thing all three problems quietly assumed.
Every count today was gates, or wires into gates. Fewer is better, and that was the entire measure of a circuit.
But a circuit also takes time. A signal crosses every gate on its path one after another, and each one costs a delay.
Two circuits with the same gate count can be very different speeds.
remember
A minimal circuit is minimal in gate count. Nobody ever promised it was fast.
Sometimes the cheapest circuit is a long thin chain of gates, which is the slowest possible shape.
Next session that becomes the point, and it is why the adder in Class 19 is not built the obvious way.
Do not resolve it. Just make them notice the assumption they have been making for an hour.
Three problems, solved. 4 to 3, 4 to 2, and 9 to none.
The map is only a way of arranging a table so you can see where two terms differ in one variable. All the work is done by three lines of algebra from 1847.
Next session: what a gate costs besides existing, and why the smallest circuit is sometimes the wrong one.
Stop here. Send off: bar d of the display, solved completely. Table, as built, map, don't cares, final gate count.