Combinational building blocks
Introduced| English | Meaning |
|---|---|
| decoder/dɪˈkəʊdə/ | A circuit that activates exactly one of its outputs for each binary input code. |
| adder/ˈædə/ | A logic circuit that adds binary numbers. |
| multiplexer/ˈmʌltɪpleksə/ | A circuit that chooses one of several inputs and passes it to its output. |
| combinational logic/ˌkɒmbɪˈneɪʃənl ˈlɒdʒɪk/ | Logic whose outputs depend only on its present inputs, with no memory. |
| full adder/fʊl ˈædə/ | A circuit that adds two bits and a carry-in, giving a sum bit and a carry-out. |
| half adder/hɑːf ˈædə/ | A logic circuit that adds two single binary digits and produces a sum bit and a carry bit. |
| hazard/ˈhæzəd/ | A brief unwanted output pulse caused by unequal delays inside a logic circuit. |
Four drinks, two buttons
- A vending machine picks one of four drinks from two button presses, lights the right number on its display and works out the change.
- Inside are a selector, a decoder and an adder: standard blocks built from gates, reused in nearly every digital system.
The multiplexer selects
- Combinational logic 组合逻辑 has outputs that depend only on the present inputs: no memory. Its most common block is the multiplexer 多路选择器 (MUX).
- A $2^{n}$-to-1 MUX has $n$ select bits. Read the select code as a binary number: it names the data input that reaches the output. With $S_{1}S_{0} = 10$, a 4-to-1 MUX passes $D_{2}$.
A 4-to-1 MUX with select S1S0 = 10 outputs —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The select code names its data input: $10_{2} = 2$, so $D_{2}$ passes. The MUX is a switch and does not look at the data.
The decoder raises one line
- A decoder 译码器 turns $n$ inputs into $2^{n}$ outputs, with exactly one output high: the one numbered by the input code.
- Each output is one minterm of the inputs, so a decoder plus an OR gate can build any function from its truth table.
How many output lines does a decoder with 3 inputs have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$2^{3} = 8$ outputs, one per minterm, with exactly one high at a time.
Half and full adders
- A half adder 半加器 adds two bits: $S = A \oplus B$ and carry $C = A \cdot B$.
- A full adder 全加器 also takes a carry-in: $S = A \oplus B \oplus C_{in}$ and $C_{out} = A \cdot B + C_{in} \cdot (A \oplus B)$. Always $2C_{out} + S = A + B + C_{in}$.
Match each block to what it does.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
These four blocks, plus registers, make up most of a datapath.
Worked example: three ones in
- Set $A = B = C_{in} = 1$. Then $S = 1 \oplus 1 \oplus 1 = 1$ and $C_{out} = 1 + 1 \cdot 0 = 1$.
- Output $C_{out}S = 11_{2} = 3$: three ones in, three out. Checking $2C_{out} + S$ on all 8 rows verifies the circuit.
A full adder at A = 1, B = 1, Cin = 1 outputs —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$2C_{out} + S = A + B + C_{in} = 3 = 2 + 1$: sum bit 1, carry 1. The same check holds on all eight rows.
The ripple adder
- Chain $n$ full adders, each carry-out feeding the next carry-in, and you have an adder 加法器 for $n$-bit numbers.
- $11_{2} + 01_{2}$ ($3 + 1$): the low bits $1 + 1$ give $S_{0} = 0$, carry 1; the high bits $1 + 0 + 1$ give $S_{1} = 0$, carry 1. Output $100_{2} = 4$. The carry must ripple through every stage, which limits the speed.
An n-bit ripple adder is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Each stage feeds its carry to the next: $11 + 01 = 100$ ($3 + 1 = 4$), checked stage by stage. The design scales by repetition, and the carry chain sets its speed limit.
A 4-bit ripple adder adds 1011 and 0110. Including the final carry-out, what is the result in decimal?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$11 + 6 = 17 = 10001_{2}$: four sum bits 0001 and a carry-out of 1.
Hazards: brief glitches
- When an input changes, signals reach the output along paths with different delays. The output can flash the wrong value for a moment: a hazard 冒险.
- The final value is still correct. A glitch matters when something samples it, such as a clock input. An extra, redundant K-map group covering the transition removes it.
A circuit with a hazard settles to the wrong output value.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The steady output is correct; a hazard is only a brief glitch while signals arrive along paths of different delay.
Three common slips
- Reading the MUX backwards. The select bits choose which data input passes; they are not the output value.
- Running the carry the wrong way. Carries flow from the least significant stage upwards.
- Calling a hazard a logic error. The steady output is right; only the transient is wrong.
Recap
- MUX: the select code names the data input. Decoder: one output per minterm.
- Full adder: $2C_{out} + S = A + B + C_{in}$; $n$ chained full adders make an $n$-bit ripple adder.
- Hazards are transient glitches from unequal delays; a redundant group covers them.