Combinational Logic and Physical Composition

1From gates to circuits

One gate does not do much. A NAND gate answers one tiny question: "are both inputs 1?" A calculator, a game console, or a phone answers billions of questions every second. The trick is simple. Plug the output of one gate into the input of another. Keep going until the circuit answers the question you care about.

This week is about one kind of circuit: combinational logic. That means the output depends only on the inputs right now. Same inputs, same output, every time. The circuit has no memory. It does not know what the inputs were a second ago.

• Combinational: a redstone door that opens when the right three levers are flipped. Set the levers, and the door is open or shut. Nothing else matters.
• Not combinational: a redstone build that remembers, like a button that turns a lamp on, then off, then on again with each press. Same button press, different result, because the build remembers the last state. Circuits with memory are called sequential. They come in week 13.

Why gates can be stacked so deep

Notes 06 showed that the CMOS inverter's curve is a cliff. A slightly bad input comes out as a near-perfect output. Notes 01 called this restoration. Every static CMOS gate does it. So the output of each gate is a fresh, clean 0 or 1, no matter how many gates came before it. That is why you can chain thousands of gates and the last one still gets a clean signal.

Redstone works the same way. A redstone torch always puts out a full-strength signal, even if the dust that switched it was weak. Every torch is a fresh start. Keep that idea in mind. It comes back in section 8.

The redstone dictionary, continued

Here are the new rows for this week. The ones from Notes 06 (dust, lever, lamp, torch, merging lines) still hold.

2From truth table to circuit: the recipe

A truth table lists every possible setting of the inputs and writes down what the output should be. With 2 inputs there are 4 rows. With 3 inputs there are 8. Every extra input doubles the rows.

Here is the good news. Any truth table can be turned into a circuit with one simple recipe. No cleverness needed.

1. Find the rows that light the lamp. Circle every row where the output is 1.
2. Build one "row detector" for each circled row. A row detector is an AND gate that fires only for that exact row. Feed it each input directly if that input is 1 in the row, or through a NOT if that input is 0 in the row.
3. OR the detectors together. If any detector fires, the lamp lights.

That's it. The result is called a sum of products. The "products" are the ANDs. The "sum" is the OR. (The words are borrowed from arithmetic: AND on 0s and 1s works like multiplying, and OR works a bit like adding.) Each row detector also has a name: a minterm.

A shorthand we will use: A' means NOT A. A dot means AND. A plus means OR. So A·B'·C means "A is 1, and B is 0, and C is 1".

The lamp stands in for the door. Torches on A and C turn "A is off" and "C is off" into power. B's line goes straight in, because B being on is wrong. Any power into the middle block turns the last torch off.

Now try it yourself. The bench below runs the recipe for any table you click in.

Click a row's input cells to "set the levers" to that row; the circuit shows which detector fires. Click its Y cell to switch that row's output. Dots on a detector's line mark which input lines it listens to. Transistor counts use the gates from Notes 06: NOT 2, NAND or NOR with k inputs 2k, AND or OR with k inputs 2k + 2 (a NAND or NOR plus an inverter). The NAND column is explained in section 3, "Simplified" in section 6.

3NAND does it all

The recipe needs three kinds of gate: NOT, AND, and OR. Here is a surprise. You can build all three out of NAND gates alone. So NAND by itself can build any circuit at all. We say NAND is universal.

• NOT from NAND: tie both inputs together. If both inputs are A, then "NOT (A and A)" is just NOT A.
• AND from NAND: a NAND followed by a NOT (a NAND with tied inputs). The second flip cancels the "N".
• OR from NAND: flip both inputs first, then NAND them. A NAND outputs 1 unless both its inputs are 1. Here that means "unless A and B are both 0". That is OR.

Counted with 4-transistor NAND gates only: NOT 4, AND 8, OR 12. In practice a designer swaps each tied-input NAND for a real 2-transistor inverter.

The neat trick: AND-then-OR equals NAND-then-NAND

Take any recipe circuit: a layer of ANDs, then one OR. Now rebuild it with NANDs, using the moves above. Each AND ends with a NOT. Each OR starts with NOTs on its inputs. In the middle, two NOTs meet. Two flips are no flip, so they cancel. What is left is a layer of NANDs, then one NAND. Same answer, and all those inverters in the middle are gone.

That is the NAND column on Bench 2.1 (inverters on the inputs are still allowed and counted). For the majority vote, the recipe costs 48 transistors as AND–OR and 38 as NAND–NAND. Chips are full of two-level NAND–NAND logic for exactly this reason.

The redstone version: torches and dust are universal too

Redstone gives you only two moves: a torch (NOT) and merging dust (OR). Put them together and you get NOR, which is also universal. That is why every redstone computer, every redstone calculator, every giant redstone build you have seen, is "only" torches and dust underneath (plus repeaters, which we meet in section 8). Chip designers lean on NAND instead of NOR. Section 7 explains why.

4Building blocks: XOR, selectors, decoders

A few small circuits show up everywhere. They are worth knowing by name, the way a redstone player knows the standard builds.

XOR: "one or the other, but not both"

XOR (exclusive OR) outputs 1 when its two inputs are different. You have used one at home: the stairway light. There is a switch at the bottom of the stairs and one at the top. Flipping either switch changes the light. That is XOR.

The recipe gives A'·B + A·B': two row detectors and an OR. Here is the classic redstone XOR, which takes a different road to the same table. It builds "A or B" on one line and "not both" on another, and lights the lamp only when both are true.

Middle row: A's and B's lines merge into "A OR B". The vertical line: two torches merge into "A NAND B", crossing over the middle row on a block. The torches on the right combine the two lines, and the last torch lights the lamp only when "A OR B" and "A NAND B" are both on. The two arrow blocks by the levers are repeaters. They let power flow only one way, so the merged OR line cannot leak back and power the other lever's block.

In CMOS, a tuned XOR gate takes about 12 transistors (it needs A' and B' too, so it carries two inverters inside). Built from four NAND gates it takes 16. Either way, XOR is one of the more expensive basic gates. Remember that. Adders are full of XORs.

The selector (multiplexer): "pick one"

A multiplexer, or mux, is a selector switch. It has two data inputs, A and B, and one select input, S. If S = 0, the output copies A. If S = 1, the output copies B. Think of the input button on a TV: it doesn't change the shows, it just picks which one reaches the screen.

The recipe, once simplified, gives Y = A·S' + B·S. In words: "A gets through when S is off; B gets through when S is on." Two row detectors (each a 2-input AND) and an OR.

Top block: powered if A is off or S is on, so its torch means "A and not S". Bottom block: powered if B is off or S is off, so its torch means "B and S". The two torch lines merge into the lamp. Each torch on a block is one row detector, exactly like the lock.

Selectors are everywhere in a processor. "Should the adder get its number from this register or from memory?" That is a mux. In CMOS the NAND–NAND version costs 14 transistors.

The decoder, and the 7-segment display

A decoder takes a binary number in and lights exactly one of its outputs: the one whose number matches. With 2 inputs it has 4 outputs; with 3 inputs, 8. Look closely and you'll see it is just step 2 of the recipe done for every row: one row detector per row, and no OR at the end.

That gives another way to see the recipe: a decoder plus OR gates can build any function. Pick which detectors to OR together, and you have chosen the truth table.

The famous redstone example is the 7-segment display, the kind on an alarm clock. Four levers hold a number from 0 to 9 in binary. Seven lamps form the digit. Each lamp (segment) is its own truth table, and each one is just "OR together the detectors for the digits that use me". Try it below.

The four levers are worth 8, 4, 2 and 1. Pick a segment (a–g) to see which detectors are OR-ed together to drive it. Inputs 10–15 never happen for one digit. Designers call those rows don't-cares: you may treat them as 0 or 1, whichever makes the circuit smaller.

5Adding numbers: half adder, full adder, ripple-carry

Computers add in binary, with only the digits 0 and 1. The columns are worth 1, 2, 4, 8 (each one double the last), instead of 1, 10, 100. So 0101 is 4 + 1 = 5, and 1001 is 8 + 1 = 9.

Adding one column works just like grade school. 0 + 0 = 0. 0 + 1 = 1. And 1 + 1 = 2, which in binary is written 10: write 0 in this column, carry 1 to the next.

The half adder: two bits in

A half adder adds two bits, a and b. It has two outputs: the sum bit for this column, and the carry bit for the next column.

Look at the two output columns. The sum column is XOR. The carry column is AND. A half adder is one XOR and one AND. That's all.

The full adder: three bits in

Every column except the first also has a carry coming in from the column to its right. So a real column adds three bits: a, b, and carry-in. That is a full adder. Two easy ways to see it:

• Built from parts: add a and b with a half adder. Add carry-in to that result with a second half adder. If either half adder made a carry, carry out. So: two half adders and one OR.
• As truth tables: the sum is 1 when an odd number of the three inputs are 1. The carry-out is 1 when at least two are 1. That carry-out is the majority vote from Worked example 2.2!

The ripple-carry adder

To add 4-bit numbers, line up four full adders, one per column. Each one's carry-out wires into the next one's carry-in, right to left, just like carrying on paper. This is a ripple-carry adder. The redstone calculators people build in Minecraft are this exact circuit, made of torches and dust, often 8 or 16 columns wide.

Column 0 (worth 1) is on the right, as on paper. Each box is a full adder; inside it shows a + b + carry-in and the two-bit answer (carry-out, then sum). Carries are drawn as redstone dust. Every change replays the ripple one column at a time, so you can watch the carry travel. The count assumes a 28-transistor full-adder cell (section 7).

Click Worst case: 1111 + 0001. Column 0 makes a carry. That carry makes column 1 carry, which makes column 2 carry, and so on. The last column cannot know its answer until the carry has walked through every column before it. It is just like a redstone signal walking down a long line of torches, one tick per torch.

6Fewer gates, same answer

The recipe always works, but it is often wasteful. Why care? Every transistor costs three things:

• Area. Chip area is money. More transistors, bigger chip.
• Energy. Every gate input is a tiny capacitor. Each time it flips, you pay the ½CV² from Notes 03. More gates flipping means more energy.
• Time, often. More layers of gates means more waiting (week 8).

Spot the input that doesn't matter

Here is the one idea you need. Find two lit rows that are the same except for one input. The lamp lights in both rows, whether that input is 0 or 1. So that input doesn't matter there. Merge the two detectors into one smaller detector that ignores it.

On Bench 2.1, press Simplified. The bench tries every way of merging rows and keeps the smallest. (On paper, engineers use a grid called a Karnaugh map to spot the merges by eye. You don't need it for this course. The idea is just "find neighbouring rows".)

Some tables can't shrink at all. XOR is the famous one: no two lit rows are neighbours (01 and 10 differ in both inputs). Try XOR on the bench, and the 3-input "odd number of 1s" table too. That is part of why adders, full of XORs, are expensive.

7Physical composition: counting transistors

Now the "physical" half of this week's title. A circuit diagram is a plan. The chip is real transistors, and real transistors take up space. The simplest measure is to count them. Here is the price list, using the gates from Notes 06.

The quick rule: a static CMOS gate with k inputs has 2k transistors, one PMOS and one NMOS per input. Everything else is built from those.

Why designers prefer NAND to NOR

On paper NAND2 and NOR2 cost the same: 4 transistors each. In silicon, NAND wins. Two facts explain it.

• PMOS is the weaker switch. A PMOS of the same size passes only about half the current of an NMOS, because holes move more slowly than electrons (Notes 05). That's why Bench 4.1 in Notes 06 had a "pull-up strength" slider.
• Switches in series are weaker still. Two switches in a row are like two narrow doors one after the other: twice the squeeze, about half the flow. To keep up, each switch in a series stack must be made wider.

Now look where each gate puts its series stack. NAND stacks the NMOS, the strong switches. NOR stacks the PMOS, the weak ones. So a NOR needs very wide PMOS to be as fast as a NAND. Here is the width each transistor needs so the gate is as strong as a basic inverter (NMOS width 1, PMOS width 2):

Total width is a fair stand-in for area, and for how much load the gate puts on whatever drives it. NOR falls behind fast. That's why the NAND–NAND trick from section 3 is the everyday choice.

Fan-in: how many inputs per gate

The number of inputs a gate has is its fan-in. A NAND4 has fan-in 4. Big fan-in means a long series stack, and the table above shows how fast that grows. A long stack is also slow (week 8 shows why). Rule of thumb: keep series stacks to about 3 or 4. Need an 8-input AND? Build it as a little tree: two NAND4s feeding a NOR2. Same answer, smaller gates.

This is also why the 8-input OR that the recipe makes for a big table (try "Always on" on Bench 2.1) would never be built as one gate. It becomes a tree too.

8Fan-out, signal strength, and repeaters

Fan-in counts inputs. Fan-out counts the other way: how many gate inputs one output has to drive. If a gate's output wire runs to 4 other gates, its fan-out is 4.

Redstone first: signal strength

Every redstone player hits this wall. A lever powers the dust next to it at strength 15. Each block of dust after that is one weaker: 14, 13, 12… After 15 blocks the signal is 0, and the lamp at the far end stays dark. The fix is a repeater. It takes any signal of strength 1 or more and sends out a fresh strength 15. The price: each repeater adds a short delay (1 to 4 redstone ticks).

Read the line like text: left to right, then on to the next row. The number on each block is its signal strength. Repeaters are the arrow blocks (each one takes a block of the line). The delay assumes each repeater is on its fastest setting, 1 redstone tick = 0.1 s.

Now chips: the same idea, with one twist

Here the analogy bends, and the bend is the important part. In a chip, the level does not fade like redstone dust. A static CMOS gate always pulls its output all the way to V_DD or to ground in the end (Notes 06 §8). What gets worse with more load is time.

Picture filling buckets with a garden hose. Every gate input on the wire is a small bucket: a tiny capacitor, the gate of a transistor. A long wire adds a few more buckets. The driving gate is the hose. With 1 bucket, it's done in a moment. With 30 buckets, it takes about 30 times as long. The water gets there; it's just slow. Slow edges also spend longer in the forbidden zone from Notes 06 §4, where noise does the most harm.

The fix is the chip's version of a repeater: a buffer. It is a big, strong inverter (or two inverters in a row, if you want the signal right-side up). The small gate only has to fill the buffer's one input bucket. Then the buffer, with its big hose, fills the many buckets fast. And like a repeater, a buffer restores the signal. It is Notes 01's restoration, paid for with energy from the supply, placed where it's needed.

A toy model with made-up units. A size-1 gate filling one load takes 1 unit, and time = loads ÷ driver size. A buffer of size b is itself a load of b on the first gate, then fills the N loads b times faster: time = b + N/b. It ignores each gate's own built-in delay, which makes the extra stage look a little better than it really is. Week 8 replaces this with the real RC model.

Play with it. With 1 or 2 loads, a buffer only adds a step and makes things slower. With 16 loads, a size-4 buffer halves the time. The sweet spot is when each stage drives about 4 times its own size. Designers have a name for a gate driving four copies of itself: a fan-out of 4, or FO4. You will meet it again in week 8 and in Project 2.

9Standard cells, and Project 2

Nobody draws a billion transistors by hand. Real chips are built from a standard-cell library: a catalogue of ready-made gates. Each one is designed once, measured carefully, and then reused millions of times.

• What's in it: INV, NAND2, NAND3, NOR2, AOI21, XOR2, MUX2, full adders, and (later in the course) memory cells.
• Several sizes of each: for example NAND2_X1, NAND2_X2, NAND2_X4. Bigger means wider transistors: stronger drive, but more area and more input load. That is section 8's buffer choice, made for every gate.
• All the same height: so they snap into neat rows, like bricks in a wall. A software tool turns your logic into a list of cells, places them in rows, and draws the wires between them.
• Each cell has a datasheet: its area, how its delay grows with load, how much energy each flip takes, and how much it leaks at rest.

Redstone builders do the same thing. Nobody builds an 8-bit adder torch by torch, eight times over. You build one full-adder module, test it, then copy it seven more times side by side.

How this week feeds Project 2

Project 2 (CMOS Logic: Speed and Energy) asks you to design a small CMOS logic block, simulate it, and measure its delay, its power while switching and at rest, and its noise margins, across several supply voltages and loads. In other words: write the datasheet for one cell. This week gives you the design half.

• Choosing the block: a good Project 2 block is one from this week: a full adder, a 2-to-1 mux, an XOR, or a NAND2 next to a NOR2 for comparison. Check the specification for what is allowed.
• Getting the logic right: start from the truth table, then use the recipe (§2), simplify (§6), and prefer NAND–NAND (§3). Check every row in simulation before you measure anything.
• Counting and sizing: count your transistors (§7). Make the series stacks wider, and say why in your write-up.
• "Across a range of loads": that is fan-out (§8). A natural sweep is your block driving 1, 4, and 16 inverter loads.
• Delay: still coming. Week 8 gives you the RC model, just in time for the due date.

10Self-check

Eight quick questions. Click an answer to see why. Nothing is recorded.

→Before next week

Session 13 is Monday, October 19. Before then:

• Review Notes 07. Sections 2, 5, and 8 most of all.
• On paper, run the recipe for the 3-input "odd number of 1s" table. Then check your answer on Bench 2.1.
• On paper, build XOR from four NAND gates and check all four input rows. (Hint: the first NAND takes A and B. Its output goes into two more NANDs, one paired with A and one with B. The fourth NAND combines those two.)
• On Bench 5.1, find two different input pairs where the carry runs through all four columns.
• Project 2 is in progress. Pick your block, write its truth table, draw it at the transistor level, and count the transistors. Get it simulating, with every input row checked. Set up a load sweep of 1, 4, and 16 inverters.
• Optional: build the 4-bit ripple-carry adder in Logisim Evolution (it's on the course software list) and test it with 1111 + 0001.

§Words to know