Digital logic, defined

Binary is the base-2 number system: every value is encoded as a sequence of 0s and 1s. Digital electronics represent these as two voltage levels (LOW and HIGH), making binary the natural language of computers.

A bit is the smallest unit of digital information — a single 0 or 1. Eight bits make a byte. Every digital signal, value, and instruction is ultimately a sequence of bits.

A digital signal uses defined voltage ranges to represent discrete values, typically 0 (LOW) and 1 (HIGH). A voltage between the valid ranges has an undefined logic level and may be interpreted unpredictably; metastability is a related but distinct state that can occur inside a sequential element.

A truth table is a complete enumeration of every possible input combination of a digital function and the output it produces. For an n-input gate it has 2ⁿ rows. Truth tables define what a circuit *does*, independent of how it is built.

An active-high signal asserts its function at logic 1; an active-low signal asserts it at logic 0. Designers choose active-low conventions for reasons such as transistor topology, wired logic, and desired power-up or reset behavior; a bar over the signal name or a pin bubble commonly marks the convention.

A logic gate is a digital component that computes a Boolean function of its inputs. The seven most common gates are AND, OR, NOT, NAND, NOR, XOR, and XNOR. Gate networks are a standard abstraction for digital circuits ranging from comparators to processors.

An AND gate outputs 1 only when all of its inputs are 1; otherwise it outputs 0. Boolean expression: Y = A · B. The AND gate models the "all conditions must be met" pattern that appears in safety interlocks, multi-key locks, and address decoders.

An OR gate outputs 1 if at least one input is 1, and 0 only when every input is 0. Boolean expression: Y = A + B. The OR gate models the "any condition is sufficient" pattern used in alarm circuits and multi-source triggers.

A NOT gate (inverter) takes a single input and produces its logical complement: 0 becomes 1, and 1 becomes 0. Boolean expression: Y = A̅. NOT gates are essential for active-low signals, output negation, and converting between dual gate families.

A NAND gate is an AND gate followed by a NOT — it outputs 0 only when all inputs are 1. Boolean expression: Y = (A · B)̅. NAND is functionally complete, so every Boolean function can be built from NAND gates alone, and it maps efficiently to common CMOS transistor structures.

A NOR gate is an OR followed by a NOT — it outputs 1 only when every input is 0. Boolean expression: Y = (A + B)̅. Like NAND, NOR is functionally complete; the Apollo Guidance Computer famously implemented most of its logic with integrated NOR gates.

An XOR (exclusive-OR) gate outputs 1 when its inputs differ and 0 when they match. Boolean expression: Y = A ⊕ B. XOR is a standard primitive for binary-adder sum bits, parity checking, and many error-detection schemes.

An XNOR gate is the complement of XOR — it outputs 1 when its inputs are equal. Boolean expression: Y = (A ⊕ B)̅. XNOR is the comparator primitive: a stack of XNORs followed by an AND tells you whether two binary words are identical.

A buffer is a single-input, single-output gate that reproduces its input logic value at its output. Buffers provide electrical drive, isolate loads, improve signal edges, and, in tri-state form, disconnect a driver from a shared node.

A tri-state buffer has three output states: 0, 1, and high impedance (Z). When disabled, its output presents a high impedance, allowing multiple devices to share a bus if control logic ensures that at most one drives the bus at a time. Other interconnects use multiplexers or point-to-point links instead.

A universal gate is one from which any Boolean function can be built. NAND and NOR are the two binary Boolean operators that are individually functionally complete. Practical standard-cell designs use them alongside inverters, compound gates, and other optimized cells.

A set of gates is functionally complete if every possible Boolean function can be expressed using only those gates. {AND, OR, NOT}, {NAND}, and {NOR} are each functionally complete. Functional completeness is the formal property that justifies calling NAND/NOR "universal".

Boolean algebra is the mathematics of two-valued logic, defined by George Boole in 1854. It uses three primitive operations — AND (·), OR (+), and NOT (̅) — and a small set of laws (identity, null, complement, absorption, De Morgan, distributive) to manipulate logical expressions.

De Morgan's Laws state that (A · B)̅ = A̅ + B̅ and (A + B)̅ = A̅ · B̅. They allow any AND-OR circuit to be rewritten as a NAND-only or NOR-only circuit, which is why they sit at the heart of CMOS gate-level optimization.

Sum of Products is a canonical Boolean form: an OR of AND-terms (minterms), one minterm per row of the truth table where the output is 1. SOP maps directly to a two-level AND-OR or NAND-NAND circuit.

Product of Sums is the dual canonical form of SOP: an AND of OR-terms (maxterms), one per row of the truth table where the output is 0. POS maps directly to a two-level OR-AND or NOR-NOR circuit.

A Karnaugh map is a graphical method for simplifying Boolean expressions of up to ~6 variables. Adjacent 1-cells are grouped into rectangles whose sizes are powers of two, and each group corresponds to a simplified product term.

A minterm is a product term that is 1 for exactly one row of a truth table. For n inputs there are 2ⁿ possible minterms. ORing the minterms of all output-1 rows gives the canonical SOP expression.

A maxterm is a sum term that is 0 for exactly one row of a truth table. ANDing the maxterms of all output-0 rows gives the canonical POS expression — the dual of the minterm/SOP construction.

Combinational logic is any digital circuit whose outputs depend only on its current inputs, with no memory of previous states. Adders, decoders, multiplexers, and ALUs are combinational. Contrast with sequential logic, which has internal state.

A multiplexer routes one of 2ⁿ data inputs to a single output, controlled by n select lines. Multiplexers are universal function generators: any Boolean function of n inputs can be implemented with a single 2ⁿ-to-1 MUX.

A demultiplexer is the inverse of a MUX: it routes a single input to one of 2ⁿ outputs based on n select lines. DEMUX circuits are how a CPU dispatches data to one of many destination registers or memory banks.

A decoder converts an n-bit binary input into a one-hot output of 2ⁿ lines, asserting exactly one output at a time. Address decoders inside RAM, BCD-to-7-segment converters, and instruction decoders are all decoder circuits.

An encoder converts one asserted line among 2ⁿ inputs into an n-bit binary code. A basic encoder assumes that exactly one input is active; a priority encoder resolves multiple active inputs by selecting the highest-priority one.

Sequential logic is any digital circuit whose outputs depend on both its current inputs and its stored internal state. Latches, flip-flops, registers, counters, and CPUs are all sequential. State is updated on clock edges (synchronous) or on input changes (asynchronous).

A latch is a level-sensitive 1-bit memory element: its output follows its input as long as a control signal (Enable) is asserted. When Enable goes inactive, the latch holds its last value. The SR latch and D latch are the two canonical examples.

An SR latch has two inputs (Set and Reset) and one output. Asserting Set drives the output to 1; asserting Reset drives it to 0; asserting neither holds the previous state. Asserting both is forbidden — the output becomes undefined.

A D latch has a single Data input and an Enable line. When Enable is HIGH the output transparently follows D; when Enable goes LOW, the latch holds whatever value was on D at that moment. The D latch fixes the SR latch's forbidden state.

A flip-flop is an edge-triggered 1-bit memory element: it samples its input around a designated clock transition, typically the rising edge, and holds the captured value between transitions. Its finite setup and hold requirements define the input-capture window used in synchronous timing analysis.

A D flip-flop captures its data input D on each active clock edge and holds that value until the next active edge. Q(t+1) = D. D flip-flops are common storage elements in registers, counters, and pipeline stages.

A JK flip-flop generalizes the SR flip-flop by redefining J=K=1 as a toggle (instead of forbidden). It can hold, set, reset, or toggle, making it the universal building block of synchronous counters and many state machines.

A T (toggle) flip-flop has a single input T: when T=1, the output toggles on each clock edge; when T=0, it holds. T flip-flops are frequency dividers — chain n of them and the last output toggles at f/2ⁿ.

A register is a group of storage elements controlled together to hold an n-bit word. A 4-bit register stores a nibble, and an 8-bit register stores a byte. Registers provide fast state storage throughout digital systems and processor datapaths.

A shift register is a chain of flip-flops in which each Q output feeds the next D input, so on each clock edge the stored bits shift one position. Shift registers convert serial data to parallel (SIPO) and back (PISO).

A counter is a sequential circuit that cycles through a fixed sequence of binary states, advancing on each clock edge. Binary counters count 0,1,2,…,2ⁿ-1; modulo-N counters reset after N states; Johnson and ring counters use shift-register topologies.

A finite state machine is a sequential circuit whose next state depends on its current state and inputs, as defined by a finite set of transitions. FSMs implement protocols, traffic-light controllers, and many processor-control functions.

A half adder adds two single bits and produces a 2-bit result: a sum (XOR of the inputs) and a carry (AND of the inputs). It cannot accept a carry-in, so it can only be the lowest bit of a multi-bit adder.

A full adder adds three single bits — two operands plus a carry-in — and produces a 2-bit result: sum and carry-out. Cascading n full adders builds an n-bit ripple-carry adder.

A ripple-carry adder chains n full adders so each carry-out feeds the next carry-in. It is a simple n-bit adder topology, but its worst-case carry delay grows linearly with n, so high-speed designs use faster carry networks such as carry-lookahead or parallel-prefix structures.

An ALU is the combinational unit inside a CPU that performs integer arithmetic (ADD, SUB) and bitwise logic (AND, OR, XOR, NOT). It typically outputs both the result and condition flags (zero, carry, negative, overflow) consumed by branch instructions.

The Program Counter is the register that holds the memory address of the next instruction to fetch. It increments after each fetch and is overwritten by branch and jump instructions to redirect execution.

The Instruction Register is the register that holds the instruction currently being decoded and executed. The Control Unit reads its bit fields (opcode, register addresses, immediate values) to derive control signals.

The Control Unit decodes the instruction in the IR and generates the control signals that orchestrate every other CPU component: which registers to read, which ALU operation to perform, when to write back results, and when to fetch the next instruction.

The fetch-decode-execute cycle is the three-phase loop every von Neumann CPU repeats: fetch the next instruction from memory, decode it to determine the operation, then execute that operation. Modern pipelined CPUs overlap these phases across many instructions.

RAM is volatile read-write memory in which any address can be accessed in roughly the same time. It loses its contents when power is removed. CPU caches, main memory, and register files are all forms of RAM.

ROM is non-volatile memory that retains its contents without power. Mask ROM is fixed during manufacturing, PROM is programmed once, and erasable variants such as EPROM, EEPROM, and flash can be reprogrammed. Boot code, microcode, and lookup tables are commonly stored in ROM-family devices.

A bus is a shared set of wires that carries data, addresses, or control signals between multiple components. Tri-state buffers let many devices share the bus while only one drives it at a time.

A clock is a periodic signal that coordinates state transitions within a synchronous clock domain. Active edges trigger flip-flops, while the clock period limits how much combinational work can complete between captures. A system may contain multiple clock domains or asynchronous logic.

An edge-triggered element changes state only at a specific clock transition — usually the rising edge. This contrasts with level-sensitive (transparent) latches, which follow their input as long as Enable is asserted. Edge-triggering is what makes synchronous design predictable.

Setup time is the minimum interval for which a flip-flop’s data input must be stable *before* the active clock edge. A setup-time violation can cause an incorrect capture or metastability, in which the internal state takes unusually long to resolve to a valid logic level.

Hold time is the minimum interval for which a flip-flop’s data input must remain stable *after* the active clock edge. A hold-time violation, like a setup-time violation, can cause an incorrect capture or metastability.

Propagation delay is the time between an input change and the resulting output change of a gate. Cumulative propagation delay along the longest path in a circuit (the *critical path*) sets the system's maximum clock frequency.

Metastability is a temporary analog state that a bistable element can enter when its setup or hold requirements are violated. Its resolution time is not bounded, but the probability that it persists decreases rapidly with time; synchronizer stages reduce that probability to an acceptable system-specific level rather than eliminating it.

A synchronizer is a chain of flip-flops, often two or more, used to reduce the probability that metastability propagates when a single-bit signal crosses clock domains. The first stage may become metastable; additional resolution time before the next stage makes a persistent failure less likely, but never mathematically impossible.

Clock-domain crossing is the transfer of a signal between circuit regions that use unrelated clocks. Robust CDC design uses techniques suited to the data type, including synchronizers for stable single-bit levels, handshakes for events or buses, and asynchronous FIFOs with Gray-coded pointers for data streams.

Fan-out is the number of gate inputs driven by one output. Each load adds capacitance and can slow signal transitions; exceeding the driver's load specification may violate voltage, slew-rate, or timing requirements. Buffers or replicated drivers reduce high-fan-out loading.

CMOS is the dominant integrated-circuit technology, pairing NMOS and PMOS transistors in complementary structures to achieve low static power. Real CMOS circuits still draw leakage current and consume dynamic power while switching; most modern CPUs, GPUs, and microcontrollers use CMOS processes.

Frequency division derives a lower-frequency periodic signal by toggling or counting transitions of a faster input. A T flip-flop divides by 2; the most significant bit of an n-bit binary counter divides by 2ⁿ; and a modulo-N counter repeats once every N input cycles.