class 18 · hour eighteen of fifty · the logic arc closes
What does a gate cost?
One job today, and everything comes out of it: a chemical plant needs an alarm, and the alarm has a deadline.
Collect the send off. Bar d, solved completely, both gate counts.
one requirement, and it runs through the whole hour
Thirty two sensors. One bell. It must ring inside a single clock cycle.
SENSORS
32
any one of them trips the alarm
OUTPUT
1 bell
an OR of all thirty two
CONTROLLER
3 GHz
one cycle is 333 picoseconds
DEADLINE
333 ps
or the reading is missed
five questions, all from this one job
Does anything take time at all? Every count in Class 17 quietly assumed gates were instant.
Which shape? Two circuits with identical gate counts, and only one meets the deadline.
Can we cheat with one wide gate? The obvious shortcut, and why the silicon refuses.
Keep ringing until an operator acknowledges. A reasonable request that no arrangement of gates can satisfy.
Where did "one cycle" come from? Nothing you have built has any notion of when.
The last two are the walls, and they arrive as ordinary plant requirements rather than as theory.
QUESTION ONE
press run, then change the depth and run again
Does a circuit take any time at all?
GATES IN A ROW
Run it at 2, then at 8. The arrival time tracks the depth exactly, and nothing else about the circuit changed.
so where does the twenty picoseconds actually go
A gate does not decide. It charges.
remember
Class 14 built a gate as two networks of transistors. Whichever one conducts has to move charge onto the wire and into the next gate's input.
Charge moves through resistance into capacitance, so the voltage does not jump. It rises on a curve.
The next gate cannot tell what it is looking at until that curve crosses its threshold. That crossing is the gate delay.
Nothing is deciding anything. It is a bucket filling, and about twenty picoseconds is how long it takes.
This is why depth costs time and width does not. Two gates in a row is two buckets, one after the other.
ANSWER
Yes. About twenty picoseconds a gate, and only the gates in a row count.
what this question taught
Depth. The longest path from any input to any output, counted in gates. The circuit is not finished until that path is.
Gates side by side cost silicon. Gates one behind another cost time. Two different bills, and Class 17 only ever read one of them.
Twenty picoseconds is twenty trillionths of a second. Light travels about six millimetres in that time.
Both circuits here have four gates. Ask which they would rather build before revealing the depths.
QUESTION TWO
start small, with eight sensors instead of thirty two
The gate count is fixed. Does the arrangement matter?
which makes this the perfect test
Every two input gate swallows two signals and returns one, so each gate reduces the count by exactly one.
Eight down to one is seven gates, whatever shape you choose. The bill of materials is fixed before you start.
So Class 17's measure cannot tell any two answers apart. Only the arrangement is left, and it is about to matter enormously.
Let them derive the seven. Each gate eats one signal, eight down to one, therefore seven.
question two · same seven gates, both wired up, one clock · press run
Sensor 0 trips. Watch both bells.
The tree finishes while the chain is still on its fourth gate. Say nothing until both have rung.
ANSWER
Enormously. Six times over, at the size this plant needs.
SENSORS
what this question taught
Shape is a free variable. The gate count is identical for both bars, at every size.
The chain grows with the sensor count. The tree grows with its logarithm, so it barely grows at all.
Step up through the sizes. The chain crosses the deadline somewhere between 16 sensors and 32.
Exactly at 18. A plant that expanded from seventeen sensors to eighteen would have broken its alarm and changed nothing else.
Click up through the sizes slowly. Watching the red bar cross the line is the moment of the hour.
QUESTION THREE
the obvious objection, and it is a good one
Can we dodge the whole problem with one wide gate?
Depth one. Twenty picoseconds, beating even the tree by a factor of five. On paper it is obviously right.
Nothing in Boolean algebra forbids it. An OR of thirty two things is a perfectly good expression.
The objection is not mathematical. It is that Class 14 told you what a gate is made of.
so open the gate up, once
A CMOS gate is a pull up network and a pull down network of transistors in series and parallel.
More inputs means more transistors in one of those chains, and a chain of transistors is a chain of resistors.
This is the one time in the whole course we go back below the abstraction boundary. It is worth it.
They crossed that boundary in Class 14 and were told not to look back. This is the exception, and say so.
FIRST LIMIT · FAN IN
Every extra input is another transistor in the same series stack.
INPUTS
Step it up and watch the delay bar. Doubling the inputs roughly quadruples the delay, so wide gates are not one gate delay.
SECOND LIMIT · FAN OUT
And one output cannot drive an unlimited number of inputs.
remember
Every gate input is a tiny capacitor. Driving eight of them means charging eight capacitors through one transistor.
Delay grows in proportion to how many inputs a signal feeds. This is the fan out.
The fix is a buffer, two inverters that re-drive the signal at full strength, and it costs one more gate delay.
So a signal that goes to many places is slow, and fixing it costs depth. Both bills again.
Fan out is why clock distribution is an entire engineering discipline. Mention it and move on.
ANSWER
No. Past about four inputs, the gate you wanted does not exist.
ONE 32-INPUT OR
does not exist
the stack would be 32 deep
CHAIN OF 31
620 ps
misses the deadline
TREE OF 31
100 ps
fits three times over
what this question taught
Fan in and fan out. Gates cannot be arbitrarily wide, and outputs cannot drive arbitrarily many places.
Together they are why the tree is real engineering and not a puzzle answer. Narrow gates are forced on you, and once they are, shape decides everything.
You now have three costs: how many gates, how deep they stack, and how wide each one is. Every real design trades between them.
Three costs on the board. This is the vocabulary for the whole rest of the course.
QUESTION FOUR
the plant comes back with one more requirement
Can gates remember?
The request: once the bell has rung, keep it ringing until an operator acknowledges.
Perfectly reasonable. A sensor might trip for a microsecond and clear again, and without this nobody would ever know it happened.
Every alarm panel ever built does this. It is not an exotic requirement.
And Class 15 proved every function of bits is buildable. So this should be routine.
try it first
You have thirty one gates already, and you may use as many more as you like, in any arrangement.
Give it a few minutes before turning the page. The failure is not a lack of cleverness.
The next two slides are a machine for showing exactly where it goes wrong, and why no arrangement can fix it.
Three minutes, in pairs. They will reach for feeding the output back, which is exactly right, and is Class 32.
two different mornings at the same plant · press run and watch the marker
Same sensor, same bell, same requirement. Two histories.
Stop at t=2 and ask what is different. Then step to t=3 and ask again. That single step is the whole wall.
WALL ONE · NO MEMORY
Now write those two moments into a truth table.
remember
The circuit has one input, so its table has exactly two rows: sensor quiet, and sensor tripped.
Both histories arrive at the quiet row, and they need different answers there.
A truth table has one output per row. There is nowhere to put the second answer, and no gate you add changes that.
The problem is not the circuit. It is that the required behaviour is not a function of the input at all.
Point at the empty half of the quiet row. That gap is the wall, and no amount of silicon fills it.
ANSWER
No. Not with any number of them, in any arrangement, ever.
what this question taught
The Class 15 proof said function of bits, meaning the output is fixed by the inputs at this instant and by nothing else.
Anything that depends on what happened earlier is not such a function, has no truth table, and was never inside the proof.
That is not a gap. It is the proof being honest about its scope, and nobody read it carefully enough in Class 15.
Every counter, every register, every variable in every program you have written needs exactly this, and cannot have it yet.
The phrase at this instant was always there. Nobody notices it the first time, and that is the lesson.
QUESTION FIVE
go back to the very first slide of the hour
Do gates know what time it is?
Every question so far has been measured against one number: 333 picoseconds, one cycle of a 3 GHz controller.
We have chosen a shape to meet it, and refused a wide gate because of it. It has governed every decision in this hour.
So where does it come from? Point at the thing on your board that produces it.
before you answer
Nothing you have built counts, waits, repeats, or notices that anything has elapsed.
The deadline was handed to you from outside, by a controller nobody in this room has built.
The next slide runs a circuit with no clock at all, and lets you interfere with it whenever you like.
Let somebody try to point at the clock. There is nothing on the board that could be one, and that is the answer.
press the sensor whenever you like · there is no wrong moment
Watch the output. It follows, and then it does nothing.
Flip it at odd moments, mid-transition, twice in a row. Nothing objects, because nothing is keeping time.
ANSWER
No. It is not doing steps. It is settling, and then holding still.
what this question taught
A combinational circuit is one enormous continuously evaluated expression. There is no first, no next, and no again.
The 333 picosecond deadline was imposed from outside. Nothing in your circuit produces a moment or notices one passing.
The two walls are one wall seen from two sides: sequence needs memory of where you are, and memory needs a moment at which to update.
Both are answered by a single idea in Arc 5: a circuit that feeds its own output back, and a clock that says when to look.
Do not hint at the flip flop. Let the impossibility sit unresolved until Class 32.
Six sessions ago you had two switches and a lamp.
what you can do now
Specify any behaviour that depends only on the present, as a table, with no ambiguity anywhere.
Build it mechanically from one kind of gate, and know before you start that it will work.
Make it smaller with three lines of algebra, and know what smaller costs you in time.
And say precisely what it can never do, which is anything involving the word then.
Six hours from a light switch to a method that is complete, bounded, and honest about its boundary.
arc three opens next session
You have representation. You have gates. Now put them together.
Adding is a function of the present, so Class 15 promises it is buildable. The obvious way makes a chain sixty four gates deep, which is 1280 picoseconds, which is nearly four cycles.
You have spent today learning exactly why that is a disaster. Next session: the carry, and why it is the hardest wire in the machine.
Stop here. Send off: the truth table for one column of an addition. Three inputs, two outputs. Class 19 starts from it.