Design and analysis of combinational and sequential digital circuits using Boolean algebra, truth tables, K-maps, CMOS gate implementation, flip-flops, registers, counters, and finite state machines. Covers De Morgan's theorems, canonical sum-of-products and product-of-sums forms, minimization techniques, propagation delay, setup and hold times, metastability, synchronous design discipline, and FSM encoding. Use when designing, minimizing, verifying, or debugging any circuit whose signals take only discrete logic values.
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
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) = AB + AC | 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.
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.
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.
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.
| 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.
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 the captured value. All timing budgets are sums of t_CQ + combinational delay + t_setup, which must be less than the clock period.
Definition. A finite state machine has a finite set of states, a set of input signals, a transition function from (state × inputs) to next state, and an output function from state (Moore) or (state × inputs) (Mealy).
Design procedure.
State encoding trade-offs:
| Encoding | Bits for N states | Next-state complexity | Output complexity |
|---|---|---|---|
| Binary | ceil(log2(N)) | Complex | Complex |
| One-hot | N | Simple | Simple |
| Gray | ceil(log2(N)) | Medium | Complex |
One-hot is usually preferred for FPGAs (flip-flops are cheap) and binary for ASICs (routing and area matter). The reason Kilby's original integrated circuit mattered so much is that these trade-offs only became economic when hundreds of gates per chip were possible.
The single most important rule in practical digital design: every flip-flop in the system should be clocked by the same clock signal, or by clock signals derived from a common root through known-good synchronization paths.
Why. Multiple independent clocks create clock domain crossings where metastability can occur. Asynchronous resets create their own release-time issues. Gated clocks hide timing from the synthesis tool.
The synchronous discipline:
| Mistake | Why it fails | Fix |
|---|---|---|
| Combinational loop | Latches form; timing indeterminate | Break the loop with a flip-flop |
| Missing else branch in RTL | Unintended latch inferred | Always assign every signal in every path |
| Asynchronous handshakes without synchronizers | Metastability propagates | Double-flop the incoming signal |
| State machines with undefined reachable states | Hangs after power-up glitch | Define a default next-state assignment |
| Gated clocks in RTL | Synthesis complications, timing violations | Use clock-enable inputs instead |
| Mixing blocking and nonblocking assignments | Race conditions in simulation | Blocking for combinational, nonblocking for sequential |
| Depending on propagation delay for pulse width | Varies with process, voltage, temperature | Generate pulse widths with counters |