Digital building blocks: gates, MUX, decoder, adder, flip-flops, registers, clock, tri-state bus

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Write −20 in 8-bit two's complement. from Lesson 0.2.2
• How many bits identify one of 40 registers? from Lesson 0.2.1
• What is Amdahl's upper limit on speedup when a fraction F is improved? from Lesson 0.1.2

1 · The Hook

🎣

A CPU is built from a small box of parts used over and over: gates, multiplexers, decoders, adders, flip-flops and buses. You do not need circuit design here, only what each part does, how many select lines it needs and how long it takes. Every datapath and control-unit question uses these words.

2 · Predict First

🤔

32 registers each want to place their value on one shared wire bundle (a bus) so the ALU can read one of them. What stops two registers from driving the bus at the same time, and how many control signals choose the register if you use a multiplexer instead?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Each register connects through a tri-state buffer that is switched on for only one register at a time; the others are disconnected (high impedance). With a multiplexer, choosing one of 32 inputs needs 5 select lines (2⁵ = 32).

Gates

AND, OR, NOT, XOR, NAND, NOR combine bits. Each gate takes a small time, its gate delay, to produce its output. Adder speed (Lesson 2.1.2) is counted in gate delays.

Multiplexer (MUX)

A 2ᵏ-to-1 MUX has 2ᵏ data inputs, k select lines and one output; the select value chooses which input passes through. For n-bit values, use n MUXes side by side. A CPU uses MUXes to choose ALU inputs and the next PC value.

Decoder

A k-to-2ᵏ decoder has k inputs and 2ᵏ outputs; exactly one output is 1, the one numbered by the input. Uses: decoding an opcode into "this is an ADD" lines, choosing which memory chip responds to an address (Lesson 4.1.4). Often with an enable input: if enable = 0, all outputs are 0.

Adder

A full adder adds three bits a, b, carry-in c: sum = a ⊕ b ⊕ c, carry-out = ab + c(a ⊕ b). Chain n full adders, each carry-out feeding the next carry-in, for an n-bit ripple-carry adder.

Flip-flops, registers, counters

• A flip-flop stores one bit; it takes a new value only at a clock edge (the instant the clock rises, say).
• A register is n flip-flops side by side storing an n-bit word, with a load (enable) signal: when load = 1, the register takes its input at the next clock edge; otherwise it keeps its value.
• A counter is a register that adds 1 at each clock edge (or loads a value). The PC is essentially a counter that can also be loaded (for jumps).

Tri-state buffers and buses

A tri-state buffer outputs 0, 1 or high impedance (Z), which means "disconnected". Many registers can share one bus: each has a tri-state output enable; the control unit turns on exactly one at a time. Two drivers at once is a bus conflict.

Timing in one sentence

In one clock cycle a value leaves a register, passes through gates (MUX, ALU …) and must arrive at the destination register before the next clock edge. The slowest such path sets the clock cycle time. Phase 5 uses this to explain pipelining.

4 · Visual

Only one tri-state buffer is enabled at a time; the others are high-impedance.

5 · Worked Examples

Example 1 Easy

How many select lines does a MUX need to choose one of 64 inputs?

Solution

6 (2⁶ = 64).

Example 2 Medium

A memory system has 8 chips; exactly one responds to each address. What decoder chooses the chip?

Solution

A 3-to-8 decoder: 3 address bits in, one of 8 chip-select lines out.

Example 3 GATE

A ripple-carry adder has 16 full adders; each produces its carry-out 2 gate delays after its carry-in arrives. In the worst case, how long until the last carry is ready, ignoring the first stage's setup?

Solution

The carry must ripple through all 16 stages: 16 × 2 = 32 gate delays. (Lesson 2.1.2 refines this.)

6 · GATE Traps

⚠️

• A 2ᵏ-to-1 MUX has k select lines, not 2ᵏ.
• A decoder has one active output at a time; an encoder does the reverse.
• A register changes only at a clock edge and only if load is on.
• Only one tri-state driver may be enabled on a bus at a time.

7 · Memory Hook

🧠

"MUX picks, decoder points, register remembers, tri-state lets go."

8 · Connect the Dots

These parts are the bricks of the datapath (Phase 2) and of hardwired control (Phase 3). Last lesson of the chapter: memory itself, seen as an array of addressed bytes, with word size, endianness and alignment.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markMUX select lines

How many select lines does a 128-to-1 multiplexer have?

Numerical answer: ________

Q2MCQ1 markDecoder

A 4-to-16 decoder with enable = 1 receives input 1010. Which outputs are 1?

• (A) Outputs 1 and 3
• (B) Outputs 0 to 10
• (C) Only output 10
• (D) None

Q3MCQ1 markFull adder

For a = 1, b = 1, cᵢₙ = 1, a full adder outputs:

• (A) sum 0, carry 1
• (B) sum 1, carry 0
• (C) sum 1, carry 1
• (D) sum 0, carry 0

Q4MSQ2 marksRegisters and buses

Which statements are true?

• (A) A register with load = 0 keeps its value at the clock edge.
• (B) Two registers may drive the same bus in the same cycle if their values are equal.
• (C) A tri-state buffer in the Z state is effectively disconnected.
• (D) The clock cycle must be long enough for the slowest register-to-register path.

Q5NAT2 marksRipple delay

A 32-bit ripple-carry adder: each full adder needs 3 ns to produce its carry-out after its inputs are ready. Worst-case time (ns) for the final carry-out?

Numerical answer: ________

10 · Rule Card

• 2ᵏ-to-1 MUX: k select lines. k-to-2ᵏ decoder: one active output.
• Full adder: sum = a⊕b⊕c, carry = ab + c(a⊕b). Ripple adder: carries pass stage to stage.
• Register = n flip-flops + load; changes only at the clock edge. Counter adds 1 per edge.
• Tri-state: 0, 1 or Z; exactly one driver per bus per cycle.
• Clock cycle ≥ slowest register-to-register path.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

gate delaymultiplexer (MUX)select linesdecoderenablefull adderripple-carry adderflip-flopclock edgeregister with loadcountertri-state bufferhigh impedance (Z)bus conflict

12 · Answer Vault