Circuits

Overview

From Expressions to Circuits

A combinational circuit is a network of logic gates with no feedback loops. Given a Boolean expression, we can directly build the corresponding circuit, and vice versa. Understanding this connection is key to digital systems design.

Definition

Combinational Circuit

A combinational circuit has: • Inputs: binary values (0 or 1) • Logic gates: connected in a directed acyclic graph • Outputs: determined entirely by the current inputs (no memory)

The output of any combinational circuit can be described by a Boolean expression.

Example

Full Adder

A full adder takes three 1-bit inputs: x, y, and carry-in (Cᵢₙ), and produces a sum bit S and carry-out Cₒᵤₜ.

S = x ⊕ y ⊕ Cᵢₙ Cₒᵤₜ = (x · y) + (Cᵢₙ · (x ⊕ y))

By chaining n full adders, we build an n-bit ripple-carry adder that adds two n-bit binary numbers.

Definition

Multiplexer (MUX)

A multiplexer selects one of several input signals based on a selector input.

2-to-1 MUX: output = s̄ · I₀ + s · I₁ When s = 0, output = I₀. When s = 1, output = I₁.

A 2ⁿ-to-1 MUX uses n selector bits to choose from 2ⁿ inputs.

Definition

Decoder

An n-to-2ⁿ decoder takes n input bits and activates exactly one of 2ⁿ output lines.

2-to-4 decoder with inputs x, y: Output 0 = x̄ · ȳ (active when xy = 00) Output 1 = x̄ · y (active when xy = 01) Output 2 = x · ȳ (active when xy = 10) Output 3 = x · y (active when xy = 11)

Decoders are used in memory address selection and instruction decoding.

Note

Circuit Optimization

When designing circuits, we optimize for: • Gate count: fewer gates = cheaper to manufacture • Depth: fewer levels of gates = faster computation • Fan-out: each gate output drives a limited number of inputs

Boolean simplification (algebraic or K-map) directly reduces gate count. Multi-level optimization can further reduce complexity by sharing common sub-expressions.