Adders and flip-flops
| English | Chinese | Pinyin |
|---|---|---|
| carry | 进位 | jìn wèi |
| half adder | 半加器 | bàn jiā qì |
| full adder | 全加器 | quán jiā qì |
| flip-flop | 触发器 | chù fā qì |
| ripple-carry adder | 行波进位加法器 | xíng bō jìn wèi jiā fǎ qì |
| bistable | 双稳态 | shuāng wěn tài |
| counters | 计数器 | jì shù qì |
| SRAM | 静态RAM | jìng tài RAM |
| SR flip-flop | SR触发器 | SR chù fā qì |
| JK flip-flop | JK触发器 | JK chù fā qì |
| toggle | 翻转 | fān zhuǎn |
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$.
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
- 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 gates inside an adder
A half-adder's sum bit is an XOR gate and its carry is an AND gate — toggle A and B and watch the truth-table row light up.
In a half adder, the sum output S is produced by which gate?
$S = A \text{ XOR } B$ (1 when the inputs differ); the carry is $A \text{ AND } B$.
In a half adder the carry output C is produced by which single gate?
C is 1 only when both inputs are 1, which is AND. The sum S is 1 when exactly one input is 1, which is XOR.
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
Match each building block to what it does.
Adders add bits (chain full adders for multi-bit addition); flip-flops store a bit (the JK fixes the SR forbidden state).
How does a full adder differ from a half adder?
A full adder adds A, B and a carry-in (so adders can be chained) — built from two half adders plus an OR gate.
Worked example: why a full adder, not two half adders
- Explain why a 4-bit adder is built from full adders rather than half adders.
- Adding two 4-bit numbers column by column, every column except the rightmost may receive a carry from the column to its right, so it has three inputs to add, not two.
- A half adder has no carry-in, so it cannot take that third input, and the carry would simply be lost.
- Only the least significant column has no carry-in, so a half adder would do there; in practice all four are full adders, with the first carry-in tied to 0.
Why must a 4-bit adder use full adders rather than half adders?
A half adder does produce a carry; what it lacks is a carry-in, so it cannot accept the carry arriving from the previous column.
Put the construction of a 4-bit ripple-carry adder in order.
Gates make a half adder, half adders make a full adder, full adders chain into a word-width adder. The carry rippling along is what gives it its name.
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.
A flip-flop is used to:
A flip-flop has two stable states and holds one bit — the building block of registers and SRAM.
A flip-flop is bistable — it has two stable states and remembers one bit — which makes it the building block of registers and SRAM.
Chaining flip-flops gives registers and counters; SRAM cache is built from them (no refresh needed, unlike DRAM).
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=0sets $Q$ to 1.S=0, R=1resets $Q$ to 0.S=0, R=0holds the current state, which is the memory.S=1, R=1is invalid: it asks for set and reset at once.- A JK flip-flop JK触发器 removes that flaw by giving the
1,1input 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
For an SR flip-flop, which statements are correct? Select all that apply.
Toggling on 1,1 is the JK's improvement. On an SR that input asks for set and reset at once and is invalid.
The JK flip-flop's toggle behaviour is what makes it suitable for building counters.
A chain of flip-flops each toggling on its input counts in binary. Clocking them keeps every stage in step.
Worked example: trace an SR flip-flop
- $Q$ is currently 0. Give $Q$ after the inputs S=1 R=0, then S=0 R=0, then S=0 R=1.
- S=1, R=0 sets the output, so $Q$ becomes 1.
- S=0, R=0 holds, so $Q$ stays 1. This is the step that shows it is a memory: the inputs say nothing, and the output persists.
- S=0, R=1 resets, so $Q$ becomes 0. If S=1 and R=1 were applied, the answer is that the input is invalid, not a value.
Marks that slip away
- $S = A \oplus B$ and $C = A \cdot B$: XOR for the sum, AND for the carry. Swapping them loses both marks.
- "Half" means no carry-in, not "half the bits".
- A full adder is two half adders plus an OR, and the OR combines the two carries.
- On an SR flip-flop,
0,0holds and1,1is invalid. The JK's improvement is that1,1toggles.
You've got it
- half adder: two bits in, $S = A \oplus B$ from an XOR and $C = A \cdot B$ from an AND; no carry-in
- full adder: three bits in, built from two half adders plus an OR; chain them, carry-out to carry-in, for a ripple-carry adder
- a flip-flop is bistable and stores one bit; $n$ flip-flops make an $n$-bit register, and they are the cells of SRAM
- SR: set, reset,
0,0holds,1,1invalid · JK:1,1toggles, which is what makes counters, and it is clocked to stay synchronised