You have a method that builds any function of bits. Today you point it at four real problems, watch each one get built, and find the exact place it stops working.
Everything in this hour gets built in full. No gate counts without the gates.
The method has no judgement in it. So what is left to get wrong?
FIRST
Noticing
Most problems do not announce that they are truth tables. A display, a vote, a payment check. We build three of them.
THEN
The wall
One innocent question whose table has eighteen quintillion rows. The method is still correct and completely unusable.
SO
Structure
Build the smallest version, then repeat it. The big table never gets written and nothing is lost.
the three questions that decide it
Is the set of inputs fixed and finite? Is every input a yes or a no? Is every output a yes or a no?
Three yeses means it has a truth table, and Class 15 already proved it is buildable.
What the problem is about never matters. Petrol, votes, money. The circuit does not know.
Put the three questions on the board now and leave them there for the hour.
problem one
Three sensors on a boiler. Shut down if at least two say the temperature is too high.
Nobody said the word logic. It is a rule about sensors, written the way an engineer would say it out loud.
Three inputs, so eight rows. Fill in what each row should do and you are finished specifying.
Four rows want a shutdown, so the circuit needs four detectors.
Have them fill the eight rows aloud before the next slide. It takes about forty seconds.
click any input to test it
Built. Four AND gates and one OR.
remember
Every gate on that board came from one row of the table. Nobody thought about what a majority means.
Now read the table again as arithmetic: the output is 1 exactly when the three inputs add up to two or more.
Which makes this the carry out of one column of an addition. You will build it again in Class 19 and not recognise it unless you hear this now.
A voting circuit and a carry are the same object. Say it, do not develop it.
problem two · click a digit, or click any bar
A digit on a petrol pump. Four wires in, seven bars out.
remember
Four inputs are the digit in binary. Seven outputs are the seven bars.
Each bar has its own column, so this is seven truth tables sharing one set of inputs.
Nobody was clever. Somebody wrote down which bars light for each digit.
Click bar e first, then bar c. The difference between them is the whole of the next two slides.
the cheapest bar · click any input to test it
Bar e lights for four digits. Four detectors.
remember
Four inputs now, so every detector needs four taps instead of three. The gates got wider, and the method did not change at all.
This is one bar out of seven, on one digit out of four on the pump display.
Set the inputs to 0110, which is six, and watch the one gate fire. Then 0111, which is seven, and nothing does.
the dearest bar · same method, same day, no cleverness available
Bar c lights for nine digits. Nine detectors.
Let this one just sit there for ten seconds. It is the argument for Class 17 and it needs no words.
Seven bars, seven of those circuits, sharing four inputs.
remember
Forty nine AND gates and seven ORs for one digit, before anyone tries to make it smaller. A four digit pump is around two hundred.
Bar c lights for nine digits out of ten. It would obviously be cheaper to detect the one digit it is dark for and invert that. Nine gates become one.
The procedure cannot see that, because it has no judgement in it. That was the whole point in Class 15, and this is what it costs.
Six of the sixteen input combinations are 1010 to 1111. Those are not digits and never arrive, and we built for them anyway.
Two seeds here for Class 17: shared terms, and the six rows that never happen. Plant both, explain neither.
problem four · the same question, wider
Are these two int values equal?
Two bits against two bits is four inputs and sixteen rows. Still fine, and you could do it in the margin.
Eight against eight is sixteen inputs and 65,536 rows. You would not, but a program could.
Then the doubling does what doubling does.
width
input bits
rows to write
1 bit
2
4
2 bits
4
16
4 bits
8
256
8 bits
16
65,536
16 bits
32
4,294,967,296
32 bits
64
18,446,744,073,709,551,616
Read the last row out loud in full. It lands differently spoken than written.
At one row a second, writing that table takes 584 billion years.
The universe has been going for fourteen billion. You would need forty of them, back to back, to finish the specification.
And the method is still correct. Every one of those rows would be right. It is simply of no use whatsoever.
Do not let them conclude the method was wrong. Correct and useless at the same time is the honest reading.
So stop trying to build a thirty two bit thing.
Ask instead what the smallest version of the question is.
Is one bit equal to one bit. Two inputs, four rows, and it fits on the back of a receipt.
Now use thirty two of them, and require that all thirty two agree.
remember
The four row table got written. The eighteen quintillion row table never did, and never will.
Nothing was given up. The wide circuit is exactly correct, because each narrow one is and the wiring is.
It works because equality decomposes cleanly. Each bit pair can be judged without knowing anything about its neighbours.
Not every problem is that kind. Addition is not, and that is why Class 19 is hard.
The last bullet is the one that matters. Ask what a carry does to independence.
so build that instead · click any input to test it
Is one bit equal to one bit? Two rows want a 1.
remember
Two detectors: both zero, or both one. Four rows, written in about ten seconds.
The circuit already has a name, which is XNOR, and Class 13 built it out of two staircase switches.
That is the whole specification. Now the question is what to do with thirty two of them.
Same question, same method, and it will be unrecognisable in two slides.
click any bit to change it
One cell, built once, pasted across the width.
remember
Every cell is the identical two gate circuit from four slides ago. It compares one bit pair and passes the running answer along.
To make it thirty two wide you paste in twenty four more. Nothing is redesigned and no table is written.
Change one bit anywhere and that cell goes dark, and the chain carries the failure all the way to the end.
Break a bit in the middle and trace the chain with a finger. The failure travels right and never left.
Specify by table. Build by structure.
The table is how you say exactly what you want, with no ambiguity anywhere. Structure is how you get it built without ever writing the table out.
Every circuit for the rest of this course is made this way. The adder, the ALU, the register file, the processor.
This is the sentence to leave on the board for the rest of the arc.
Four problems, four circuits, and every one is bigger than it needs to be.
Nine gates for a bar that is nearly always lit. Correctness is settled. Size is not, and size is what a chip is actually made of.
Next session: making it smaller, and the ninety year old algebra that does it.
Stop here. Send off: find the cheapest circuit you can for bar c by hand, and bring the gate count. No method, just staring at it.