加算器とフリップフロップ

How a machine that only knows true and false does arithmetic

• A processor has no adder in the sense of a thing that knows numbers. It has gates that answer true or false, and nothing else.
• Yet $1 + 1 = 10$ falls out of two gates: an XOR gives the sum digit, an AND gives the carry. That is the entire arithmetic unit in miniature, and chaining copies of it adds numbers of any width.
• The other half of a computer is remembering, and one bit of memory is also just gates, wired so that their outputs feed back into their inputs and hold.
• This lesson is the half adder 半加器, the full adder 全加器, and the flip-flop 触发器 that stores a bit.

The half adder

• A half adder adds two single bits, $A$ and $B$, producing a sum $S$ and a carry 进位 $C$.

• Read the columns: $S$ is 1 when exactly one input is 1, which is XOR. $C$ is 1 only when both are 1, which is AND. So $S = A \oplus B$ and $C = A \cdot B$.
• It ignores any carry in, which is why it is only "half" an adder and cannot be chained on its own.

Two gates, and binary addition exists

The full adder

• A full adder adds three bits: $A$, $B$ and a carry-in, producing a sum and a carry-out. $S = A \oplus B \oplus C_{\text{in}}$.
• It can be built from two half adders plus an OR gate: the first half adder adds $A$ and $B$, the second adds that sum to the carry-in, and the OR combines the two carries.
• Chain full adders so that each carry-out feeds the next carry-in, and you have a multi-bit ripple-carry adder 行波进位加法器: four of them add two 4-bit numbers.

The carry is what has to travel, which is why it is called ripple

Worked example: why a full adder, not two half adders

Flip-flops

• A flip-flop is a bistable 双稳态 circuit: it has two stable states, 0 and 1, and it remembers the one it is in. It stores exactly one bit.
• It is the basic element of registers, where $n$ bits means $n$ flip-flops, of counters, and of SRAM 静态RAM cells.
• Unlike an adder, whose output depends only on its inputs now, a flip-flop's output depends on its past inputs. That is what memory means at the circuit level.

SR and JK

• An SR flip-flop SR触发器 has inputs S (set) and R (reset) and outputs $Q$ and $\overline{Q}$, built from two cross-coupled NOR gates.
• S=1, R=0 sets $Q$ to 1. S=0, R=1 resets $Q$ to 0. S=0, R=0 holds the current state, which is the memory. S=1, R=1 is invalid: it asks for set and reset at once.
• A JK flip-flop JK触发器 removes that flaw by giving the 1,1 input a meaning: toggle 翻转, so the output flips to its opposite. That makes it ideal for counters 计数器, since a chain of toggling flip-flops counts in binary.
• A JK is usually clocked: the inputs act only on a clock edge, which keeps every flip-flop in the machine in step.

The invalid input turned into a useful one

Worked example: trace an SR flip-flop

Marks that slip away

You've got it