Digital Logic Foundations

Programmable Gates and Data Routing

Beyond basic logic gates, digital systems use multiplexers to route data, decoders to select outputs, and flip-flops to store state. This lesson covers combinational data routing circuits.

Beyond Simple Gates: Data Routing

Once you understand basic gates and adders, the next step is building circuits that route and select data. These are fundamental in CPU design, memory addressing, and bus systems.

Multiplexer (MUX)

A multiplexer selects one of many input signals and forwards it to the output, controlled by select lines. A 2-to-1 MUX has 2 data inputs (D0, D1), 1 select line (S), and 1 output (Y).

Y = (D0 · S̄) + (D1 · S)

Select S	Output Y
0	D0 (input 0 is routed to output)
1	D1 (input 1 is routed to output)

An n-bit select line can route 2ⁿ inputs. A 4-to-1 MUX needs 2 select lines.

Analogy: A MUX is like a railway switch — it routes one of many tracks to a single destination, depending on which way the lever points.

Demultiplexer (DEMUX)

The opposite of a MUX. A DEMUX takes one input and routes it to one of many outputs based on the select lines.

1 input → 2ⁿ outputs (controlled by n select lines)

Example: a 1-to-4 DEMUX routes a single data line to one of 4 outputs using 2 select lines.

Decoder

A decoder converts a binary code (n bits) into a one-hot output (exactly one of 2ⁿ outputs goes high). Used for memory address decoding and instruction decoding.

A1	A0	Y0	Y1	Y2	Y3
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

2-to-4 Decoder: 2 input bits → exactly 1 of 4 outputs is high at any time.

Encoder

The inverse of a decoder. An encoder converts a one-hot input to a binary code. Used for priority encoding (e.g., multiple interrupt signals → binary priority number).

2ⁿ inputs (one-hot) → n-bit binary output

Sequential vs Combinational Logic

All circuits covered so far are combinational — output depends only on current inputs. Sequential circuits have memory: output depends on both current inputs and previous state.

Property	Combinational	Sequential
Memory	None	Has state (flip-flops)
Output depends on	Current inputs only	Current inputs + past state
Examples	Gates, adders, MUX, decoder	Registers, counters, RAM
Clock needed?	No	Usually yes

Flip-Flops: Adding Memory

A D flip-flop stores a single bit. On a rising clock edge, it captures the value of its D input and holds it at output Q until the next clock edge.

Q(next) = D (on rising clock edge)

Flip-flops are the building blocks of registers (CPU state), RAM cells, and counters. Chaining n flip-flops creates an n-bit register.

Setup and Hold Time: In real circuits, the D input must be stable for a minimum time before (setup time) and after (hold time) the clock edge for reliable storage.

Summary: Digital Circuit Hierarchy

Level	Component	Function
1	Transistors	Physical switches (on/off)
2	Logic gates (AND/OR/NOT...)	Boolean operations
3	Half/Full adder, MUX, decoder	Arithmetic + data routing
4	Flip-flops, registers	Storage (sequential logic)
5	ALU, memory, control unit	Processor subsystems
6	CPU, RAM, I/O	Full computer system