digital-logic-design

# Digital Logic Design

Digital logic is the subset of electronics where signal values are restricted to a small number of discrete levels (usually two: logic 0 and logic 1). This restriction buys enormous simplification — Boolean algebra replaces differential equations, truth tables replace transfer functions — at the cost of needing to worry about timing, glitches, metastability, and the difference between what the logic says and what the silicon actually does. This skill covers combinational and sequential design in the order a designer typically needs them.

**Agent affinity:** kilby (integrated logic and gate-level implementation), noyce (planar process and mass production of logic families)

**Concept IDs:** elec-combinational-logic, elec-sequential-logic-design

## Boolean Algebra

Digital logic rests on Boolean algebra, where variables take values in {0, 1} and three operations dominate: AND (conjunction, written A * B or A∧B), OR (disjunction, A + B or A∨B), and NOT (negation, A' or ¬A). Several identities make manipulation tractable:

| Identity | Name |
|---|---|
| A + 0 = A, A * 1 = A | Identity |
| A + 1 = 1, A * 0 = 0 | Domination |
| A + A = A, A * A = A | Idempotent |
| (A')' = A | Double negation |
| A + A' = 1, A * A' = 0 | Complement |
| A + B = B + A, A * B = B * A | Commutative |
| (A + B) + C = A + (B + C) | Associative |
| A * (B + C) = A*B + A*C | Distributive |
| (A + B)' = A' * B' | De Morgan |
| (A * B)' = A' + B' | De Morgan |

De Morgan's theorems are the lever that converts NAND-only gate sets to full Boolean expressiveness and back. In CMOS, NAND and NOR are the natural primitives because they come for free from the complementary pull-up/pull-down network.

## Technique 1 — Truth Tables and Canonical Forms

**Truth table.** Exhaustively list every input combination and the desired output. For n inputs there are 2^n rows.

**Sum of products (SoP).** Write the function as the OR of all minterms (product terms) corresponding to rows where the output is 1. Example: F(A, B, C) = A'BC + AB'C + ABC'.

**Product of sums (PoS).** Write the function as the AND of all maxterms (sum terms) corresponding to rows where the output is 0, with each variable negated.

**Worked example.** A three-input majority function has output 1 when at least two inputs are 1. Truth table:

| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

The SoP is F = A'BC + AB'C + ABC' + ABC, which simplifies to AB + AC + BC.

## Technique 2 — Karnaugh Map (K-map) Minimization

A K-map is a two-dimensional arrangement of a truth table where physically adjacent cells differ in exactly one variable. Groups of 1s in powers of two (1, 2, 4, 8...) correspond to product terms where the variables that change within the group drop out.

**Procedure.** Draw the K-map, circle the largest possible groups of 1s that cover every 1 exactly (groups may overlap and may wrap around edges), write each group as a product term, OR them together.

**Worked example (majority function above).** The K-map has four 1s at (ABC) = 011, 101, 110, 111. The groupings produce AB, AC, and BC. The minimal SoP is F = AB + AC + BC — confirming the algebraic simplification above.

**Limits.** K-maps become impractical above five variables. For larger functions use the Quine-McCluskey tabular method or hand it to a synthesis tool.

## Technique 3 — CMOS Gate Implementation

In CMOS, every gate has a complementary pull-up (PMOS) and pull-down (NMOS) network. The pull-down conducts when the pull-up does not, and vice versa, so the output is always connected to either V_DD or GND through a low-resistance path (except during transitions). Static power is near zero — dynamic power dominates, set by C * V^2 * f.

**NAND gate.** Two PMOS in parallel pull up, two NMOS in series pull down. Output is LOW only when both inputs are HIGH.

**NOR gate.** Two PMOS in series pull up, two NMOS in parallel pull down. Output is LOW if either input is HIGH.

**Why NAND and NOR are preferred.** Inverting gates are structurally natural in CMOS. An AND gate is a NAND followed by an inverter — two levels of logic for what could have been one. Good synthesis tools automatically convert AND/OR expressions to NAND/NOR.

## Technique 4 — Combinational Building Blocks

| Block | Function | Typical use |
|---|---|---|
| Multiplexer | Select one of N inputs based on select lines | Data path routing, ROM readout |
| Decoder | One-hot output indicating which of N states is active | Address decoding, FSM state output |
| Encoder | Priority encoding of one-hot input to binary | Interrupt priority, keypad scanning |
| Adder | Binary addition with carry propagation | Arithmetic unit core |
| Comparator | Output 1 if A > B, A = B, or A < B | Sorting, control logic |
| Parity generator | XOR tree producing even or odd parity | Error detection |

These blocks are the lego bricks of digital design. Most real circuits are compositions of multiplexers and decoders with a sprinkle of arithmetic.

## Technique 5 — Flip-Flops and Registers

**D flip-flop.** On the active edge of the clock, captures the value at the D input and holds it on Q until the next active edge. The most commonly used sequential primitive.

**JK flip-flop.** Extension of SR latch that toggles when both J and K are high. Rarely used in modern design; D flip-flops plus combinational feedback can express the same behavior.

**Register.** An array of D flip-flops sharing a common clock, used to hold a multi-bit value.

**Setup and hold times.** A flip-flop requires its input to be stable for t_setup before the clock edge and t_hold after. Violating either causes metastability — the output takes an unbounded time to settle to a valid logic level. This is the central timing constraint in synchronous design.

**Propagation delay.** After the clock edge, the output takes t_CQ to reflect th