Every processor, memory controller, radio baseband and washing-machine timer is built from the same small vocabulary: a handful of logic gates, a clock, and a discipline for reasoning about them. Digital design is the bridge between "a transistor is an analogue switch" and "this chip runs an operating system". This post walks that whole bridge in one pass — number representations, Boolean algebra, gates and their CMOS reality, combinational minimisation, the standard blocks, sequential logic and timing, finite state machines, memory and programmable logic, and finally how all of it is actually written today in a hardware description language.

Learning Outcome

  • Convert between number bases, and explain why two's complement beat its rivals.
  • Manipulate Boolean expressions with the axioms, De Morgan's laws and duality; build any gate from NAND alone.
  • Explain what a CMOS gate physically is, and reason about fan-out, propagation delay and power.
  • Minimise combinational logic with Karnaugh maps (2–4 variables, don't-cares included), fix hazards, and know when to reach for Quine–McCluskey.
  • Assemble adders, comparators, multiplexers, decoders and encoders into an ALU.
  • Distinguish latches from flip-flops, compute a design's maximum clock frequency, and design an FSM end to end in both Moore and Mealy form.
  • Describe SRAM, DRAM, ROM, PLA/PAL and FPGA architecture, then write synthesisable Verilog — FSM and testbench included — and simulate it with free tools.

Chapter 1 — Number systems and codes

Terminology

  • Radix (base) — how many distinct digits a positional system uses.
  • MSB / LSB — most / least significant bit: the leftmost and rightmost bit of a word.
  • Word — a fixed-width group of bits handled as a unit (8, 16, 32, 64 bits).
  • Code — an assignment of bit patterns to things that are not plain numbers (BCD, Gray, ASCII).

Conversion. Binary ↔ octal and binary ↔ hexadecimal are trivial because 8 = 2³ and 16 = 2⁴: group bits in threes or fours from the LSB.

1
2
3
4
binary  101101    = 32 + 8 + 4 + 1  = 45
octal   101 101   -> 55  = 5*8 + 5   = 45
hex     0010 1101 -> 2D  = 2*16 + 13 = 45

Decimal → binary is repeated division by 2 for the integer part (read remainders bottom-up: 45 → 101101) and repeated multiplication by 2 for the fraction, reading the carries top-down: 0.625 → 1, 0.25 → 0, 0.5 → 1 gives 0.101.

Trick: memorise the sixteen hex digits and the powers of two to 2¹⁶. Nearly all "mental arithmetic" in digital design is pattern recognition on those two tables.

Signed representations

Scheme (8-bit) −5 encoded Range Zeros Addition hardware
Sign-magnitude 1000 0101 −127 … +127 two separate compare + subtract path
One's complement 1111 1010 −127 … +127 two adder plus end-around carry
Two's complement 1111 1011 −128 … +127 one ordinary unsigned adder, unchanged

Two's complement won for one reason: the same adder serves signed and unsigned operands — no correction step, no end-around carry, no second zero. Negation is "invert all bits, add one", and the MSB simply carries weight −2^(n−1) instead of +2^(n−1):

1
2
3
  5 = 0000 0101  ->  ~5 = 1111 1010  ->  +1 = 1111 1011 = -5
  check: -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5

Two consequences: sign extension is replication of the MSB, and subtraction is A + (~B) + 1 — one adder, an inverter row, a forced carry-in.

Overflow

Overflow is not the carry-out. For two's-complement addition it occurs iff the carry into the MSB differs from the carry out of the MSB — equivalently, iff both operands share a sign and the result has the opposite one.

1
2
3
4
5
  100 = 0110 0100
 + 50 = 0011 0010
        1001 0110   = 150 unsigned, but -106 as a signed 8-bit value
  carry into bit7 = 1, carry out of bit7 = 0  ->  V = 1

The same bit pattern is a valid unsigned answer, so hardware raises both C and V and lets the instruction set decide which matters.

Fixed point, floating point, and codes

Fixed point declares an implied binary point at a fixed position — a 16-bit Q8.8 value stores the real number times 2⁸ — so arithmetic is ordinary integer arithmetic plus a shift after multiplication: cheap, exact, the default in DSP and control loops. Floating point (IEEE 754 binary32: 1 sign bit, 8 exponent bits biased by 127, 23 stored fraction bits plus an implied leading 1) trades a wider dynamic range for variable absolute precision and considerably more silicon. Use fixed point when the signal range is known, floating point when it is not.

BCD stores each decimal digit in its own 4-bit field (59 → 0101 1001), leaving 1010–1111 unused, because displays, financial arithmetic and legacy instrumentation want exact decimal digits. Its addition needs a correction — if a digit sum exceeds 9, add 6:

1
2
  7 = 0111  +  8 = 1000  ->  1111 (invalid)  + 0110  ->  1 0101 = BCD "15"

Gray code orders values so consecutive ones differ in exactly one bit — 000 001 011 010 110 111 101 100 for three bits — and converts in one line each way: G = B ^ (B >> 1), and back, b[n-1] = g[n-1], b[i] = b[i+1] ^ g[i]. It has three genuine uses: absolute position encoders (a disc read mid-transition is off by at most one, instead of returning garbage as 0111 → 1000 would); Karnaugh map row/column ordering, which is exactly why adjacent cells differ in one variable; and clock domain crossing, where an asynchronous FIFO's Gray-coded pointers sample as either the old or the new value, never a nonsense mixture.

Text is just another code: ASCII is 7-bit (128 code points, 'A' = 0x41, 'a' = 0x61), and UTF-8 encodes Unicode in 1–4 bytes whose single-byte forms are exactly ASCII — which is why ASCII-era hardware and protocols survived the transition.

Chapter 2 — Boolean algebra

Terminology

  • Literal — a variable or its complement (A, A').
  • Product term — a conjunction (AB'C). Sum term — a disjunction (A + B' + C).
  • Dual — swap AND ↔ OR and 0 ↔ 1 throughout, leaving literals alone.

Notation: + is OR, juxtaposition or · is AND, ' is NOT, ^ is XOR.

Law OR form AND form
Identity A + 0 = A A · 1 = A
Null A + 1 = 1 A · 0 = 0
Idempotence A + A = A A · A = A
Complement A + A' = 1 A · A' = 0
Involution (A')' = A —
Commutative A + B = B + A AB = BA
Associative A + (B + C) = (A + B) + C A(BC) = (AB)C
Distributive A + BC = (A + B)(A + C) A(B + C) = AB + AC
Absorption A + AB = A A(A + B) = A
Absorption (2nd) A + A'B = A + B A(A' + B) = AB
De Morgan (A + B)' = A'B' (AB)' = A' + B'
Consensus AB + A'C + BC = AB + A'C (A+B)(A'+C)(B+C) = (A+B)(A'+C)

A + BC = (A + B)(A + C) is the one that catches people: it has no arithmetic analogue. Verify it once from the truth table, then trust it.

Duality: the dual of any Boolean identity is also an identity — which is why every law above has two columns, and why SOP and POS minimisation are the same procedure applied to opposite cells of a K-map.

Watch out: the dual of an expression is not its complement. (A + B) has dual AB and complement A'B'. De Morgan is duality plus complementing the literals.

Worked simplifications

1. Idempotence (X = X + X) lets a term be reused, so replicate ABC twice more. The result is the majority function — 1 when at least two of three inputs are 1 — with four 3-literal terms reduced to three 2-literal ones:

1
2
3
4
F = A'BC + AB'C + ABC' + ABC
  = (A'BC + ABC) + (AB'C + ABC) + (ABC' + ABC)
  = BC(A' + A)   + AC(B' + B)   + AB(C' + C)  =  BC + AC + AB

2. Apply A + BC = (A + B)(A + C) backwards to the first two factors; 3. is De Morgan applied twice:

1
2
3
F = (A + B)(A + B')(A' + C) = (A + BB')(A' + C) = A(A' + C) = AA' + AC = AC
F = ((A + B')·C)' = (A + B')' + C' = A'B + C'

Common pitfall: (AB)' = A' + B', not A'B'. Break the bar, flip the operator. Writing (A+B)' = A' + B' is the single most common error in a first digital-logic exam.

Chapter 3 — Logic gates

Terminology

  • Fan-in / fan-out — inputs a gate has / gate inputs one output drives.
  • Propagation delay (t_pd) — worst-case time from an input change to the resulting output change.
  • Contamination delay (t_cd) — time before which the output is guaranteed not to have started moving.
  • Functionally complete set — a set of gates from which every Boolean function can be built.
1
2
3
4
5
6
7
 A B | AND OR NAND NOR XOR XNOR       A | NOT
-----+------------------------       --+----
 0 0 |  0   0   1    1   0    1        0 |  1
 0 1 |  0   1   1    0   1    0        1 |  0
 1 0 |  0   1   1    0   1    0
 1 1 |  1   1   0    0   0    1

XOR is "the inputs differ", XNOR "the inputs are equal" — making XNOR the natural 1-bit equality comparator. Beyond two inputs XOR generalises to odd parity, which is why parity generators are XOR trees.

NAND and NOR are functionally complete

Tie both inputs of a NAND together and you have an inverter; everything else follows:

1
2
3
4
5
6
NOT A   = A NAND A
A·B     = (A NAND B) NAND (A NAND B)
A+B     = (A NAND A) NAND (B NAND B)     [De Morgan: (A'·B')' = A + B]
A NOR B = NOT(A + B)                     -> 4 NAND gates
A ^ B   = let X = A NAND B, then (A NAND X) NAND (B NAND X)   -> 4 NAND gates

Check the XOR on A=1, B=1: X = 0, A NAND X = 1, B NAND X = 1, 1 NAND 1 = 0. Correct. The NOR duals are just as short: NOT A = A NOR A, A + B = (A NOR B) NOR (A NOR B), A·B = (A NOR A) NOR (B NOR B). This matters commercially — a process only has to characterise one gate cell to build anything.

What a CMOS gate actually is

A static CMOS gate is two complementary transistor networks between the supply rails with the output node between them. The pull-up network is PMOS to VDD (a PMOS conducts when its gate is low); the pull-down network is NMOS to GND (conducts when its gate is high). The two are duals — series in one is parallel in the other — so for any input combination exactly one conducts, the output is always driven, and statically no current flows rail to rail. A NAND2 is two series NMOS below, two parallel PMOS above; a NOR2 is the mirror image. Three consequences:

  1. CMOS gates are naturally inverting. NAND2 and NOR2 cost 4 transistors; AND2 and OR2 cost 6, being the inverting gate plus an inverter. Synthesis tools therefore prefer NAND/NOR/inverter forms — a "cheap" AND-OR schematic is not cheap silicon.
  2. NAND is faster than NOR at equal drive. NOR stacks PMOS in series, and holes have lower mobility than electrons, so that stack must be made wide — costing area and input capacitance. Standard-cell libraries are NAND-heavy for this reason.
  3. A gate input is a capacitor, not a resistor. It draws essentially no DC current.

Fan-out, delay and power

Because inputs are capacitive, CMOS has no hard DC fan-out limit the way bipolar TTL did (where fan-out was a real current budget of order 10–20 unit loads). What fan-out costs in CMOS is time: each load adds capacitance, and delay rises roughly linearly with the load being charged and discharged. Processes are commonly characterised by the FO4 delay — an inverter driving four copies of itself — precisely because it is a load-normalised yardstick. Delay is also asymmetric: t_pLH and t_pHL need not be equal, and datasheets quote both across process, voltage and temperature corners. Design to the maximum; use the contamination delay only for hold checks.

1
2
3
4
P_dynamic ≈ α · C_load · VDD² · f     (charging/discharging node capacitance)
          + short-circuit power       (brief PUN+PDN overlap during a transition)
P_static  = leakage                   (subthreshold + gate-oxide tunnelling)

α is the activity factor — the fraction of cycles in which a node toggles. Three levers fall straight out: lower VDD (quadratic, hence dynamic voltage scaling), lower f, or lower α by clock-gating idle blocks. Static leakage was negligible in older processes and is a first-class problem in modern ones, which is why power gating exists.

Chapter 4 — Combinational design and minimisation

Terminology

  • Combinational circuit — output depends only on present inputs. No memory, no feedback.
  • Minterm (m_i) / maxterm (M_i) — a product term true for exactly one input row / a sum term false for exactly one row.
  • Implicant — a product term that implies the function. Prime implicant (PI) — one that cannot be enlarged further. Essential PI — the only PI covering some minterm.

Canonical forms

Take F(A,B,C) true for rows 1, 3, 5, 7:

1
2
3
SOP: F = A'B'C + A'BC + AB'C + ABC             = Σm(1,3,5,7)
POS: F = (A+B+C)(A+B'+C)(A'+B+C)(A'+B'+C)      = ΠM(0,2,4,6)

The index sets are complements: whatever is not a minterm of F is a maxterm of F. For row i, the minterm takes each variable uncomplemented where its bit is 1; the maxterm does the exact opposite. Both forms implement directly — SOP as two-level AND-OR, POS as OR-AND — and both are usually far from minimal (Σm(1,3,5,7) is just C).

Karnaugh maps

A K-map redraws the truth table so that physically adjacent cells differ in exactly one variable — hence the Gray-code label order 00 01 11 10. Adjacent 1-cells then merge: a group of 2^k cells eliminates k variables. Groups must be rectangles of size 1, 2, 4, 8 …; they may wrap around both edges (the map is a torus); they may overlap; make each as large as possible and keep going until every 1 is covered.

Worked example 1 — three variables, F(A,B,C) = Σm(0,2,4,5,6)

1
2
3
4
5
        BC
   A \  00   01   11   10
   0  |  1  |  0  |  0  |  1  |     m0  m1  m3  m2
   1  |  1  |  1  |  0  |  1  |     m4  m5  m7  m6

The whole 00 and 10 columns (m0, m2, m4, m6) form a group of four, all with C = 0, eliminating A and B: term C'. Cells m4 and m5 (bottom row, columns 00 and 01) have A = 1, B = 0: term AB'. So F = C' + AB'. Both are prime and both essential — C' alone covers m0, m2, m6, and AB' alone covers m5.

Worked example 2 — four variables, F(A,B,C,D) = Σm(0,2,5,7,8,10,13,15)

1
2
3
4
5
6
7
          CD
   AB \  00   01   11   10
   00  |  1  |  0  |  0  |  1  |     m0  m1  m3  m2
   01  |  0  |  1  |  1  |  0  |     m4  m5  m7  m6
   11  |  0  |  1  |  1  |  0  |     m12 m13 m15 m14
   10  |  1  |  0  |  0  |  1  |     m8  m9  m11 m10

The four corners m0, m2, m8, m10 are adjacent — the map wraps both ways — and all have B = 0, D = 0: term B'D'. The centre block m5, m7, m13, m15 all have B = 1, D = 1: term BD. So F = B'D' + BD = (B XNOR D) — sixteen literals in canonical form reduced to one XNOR gate. That is the payoff of the method, and a warning: the right answer here is invisible in the algebra and obvious in the picture.

Don't-care conditions

A don't-care (d) marks an input combination that cannot occur or whose output nobody reads. Treat each independently as 0 or 1 — whichever enlarges a group. Take "the BCD digit is 5 or greater": patterns 10–15 never occur.

1
2
3
4
5
6
7
          CD
   AB \  00   01   11   10
   00  |  0  |  0  |  0  |  0  |
   01  |  0  |  1  |  1  |  1  |    m5, m7, m6 are 1
   11  |  d  |  d  |  d  |  d  |
   10  |  1  |  1  |  d  |  d  |    m8, m9 are 1

The bottom half (rows 11 and 10, eight cells) gives A; m5, m7, m13, m15 (1, 1, d, d) give BD; m6, m7, m14, m15 (1, 1, d, d) give BC. So F = A + BD + BC with the don't-cares, against F = AB'C' + A'BD + A'BC without them — same behaviour on every input that can actually happen, noticeably less hardware.

Trick: don't-cares are free minimisation. Whenever a spec says "unused encoding", "never happens" or "output ignored while valid is low", write d into the truth table rather than picking 0 out of habit.

Essential prime implicants and cyclic maps

Circle every maximal group: those are the prime implicants. Take all essential ones first, then cover what remains as cheaply as possible. Sometimes none is essential — as for F(A,B,C) = Σm(0,1,2,5,6,7):

1
2
3
4
5
        BC
   A \  00   01   11   10
   0  |  1  |  1  |  0  |  1  |
   1  |  0  |  1  |  1  |  1  |

The PIs are A'B', A'C', B'C, AC, AB, BC' — six, each minterm covered by exactly two. This is a cyclic map with two equally minimal solutions, F = A'B' + AC + BC' and F = A'C' + B'C + AB. Neither is more correct; pick whichever shares terms with the rest of the design.

Quine–McCluskey

K-maps stop being drawable past about six variables and stop being reliable past four or five. Quine–McCluskey is the same idea made mechanical so a program can do it: (1) list all minterms and don't-cares as bit patterns, grouped by their number of 1s; (2) compare every term in group k with every term in group k+1, combining any pair that differs in exactly one bit into a term with - in that position, and ticking both parents; (3) repeat until nothing more combines — everything left unticked is a prime implicant; (4) build a prime-implicant chart (PIs as rows, real minterms as columns), select the essential PIs, delete their columns, and solve the remaining covering problem with Petrick's method or a heuristic.

It is exact and exhaustive, and therefore exponential. Real tools (Espresso, and the minimisers inside every synthesis flow) use heuristics — but knowing this shape tells you what your synthesiser is approximating.

Hazards

Minimisation assumes instantaneous gates. A two-level network whose inputs change can produce a brief wrong output — a glitch. A static-1 hazard is an output that should stay 1 dipping momentarily to 0; a static-0 hazard is the mirror image; a dynamic hazard is an output that should change once changing three or more times, which needs multiple reconverging paths of differing delay and so appears in multi-level rather than clean two-level networks.

The classic case is F = AB + A'C. Hold B = C = 1: then F = A + A' = 1 for both values of A, so the output should never move. But when A falls 1→0, AB drops immediately while A'C only rises after the inverter's delay, and for that window the OR sees two zeros. The fix is the consensus term — logically redundant, but it bridges the two groups that previously only touched on the K-map:

1
2
F = AB + A'C + BC

BC is 1 whenever B = C = 1 regardless of A, holding the OR high through the changeover, at the cost of one AND gate.

Watch out: a synthesis tool will happily remove a redundant term as an optimisation. If you need the hazard-free form (asynchronous logic, a latch enable, a clock-gating cell), mark it keep/dont_touch.

In fully synchronous design, glitches are usually harmless — they occur right after a clock edge and need only settle before the next setup window. Hazards become critical exactly where the synchronous discipline does not apply: asynchronous circuits, level-sensitive enables, reset trees and clock networks.

Chapter 5 — Standard combinational blocks

Adders

1
2
3
4
Half adder            Full adder
S = A ^ B             S    = A ^ B ^ Cin
C = A · B             Cout = AB + Cin(A ^ B)  =  AB + ACin + BCin
 
1
2
3
4
5
6
7
 A B Cin | Cout S        A B Cin | Cout S
---------+--------      ---------+--------
 0 0  0  |  0   0        1 0  0  |  0   1
 0 0  1  |  0   1        1 0  1  |  1   0
 0 1  0  |  0   1        1 1  0  |  1   0
 0 1  1  |  1   0        1 1  1  |  1   1

Cout is "at least two of three inputs are 1" — the majority function from Chapter 2 — and S is 3-input odd parity.

Chain n full adders carry-to-carry and you have a ripple-carry adder: small, simple, and with worst-case delay t ≈ (n−1)·t_carry + t_sum, linear in n. At roughly two gate delays per stage a 32-bit ripple adder costs over 60 gate delays, and since the adder normally sits on the critical path it caps the whole design's clock.

Carry-lookahead removes the chain. Per bit, define G_i = A_i·B_i ("generate" — this bit makes a carry regardless of the incoming one) and P_i = A_i ^ B_i ("propagate"). Then C_{i+1} = G_i + P_i·C_i, and expanding the recursion gives every carry as a two-level function of the inputs:

1
2
3
4
5
C1 = G0 + P0·C0
C2 = G1 + P1·G0 + P1·P0·C0
C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0
C4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·C0

One gate delay for all P and G, two more for the carries — constant time. But fan-in grows with block width, so real designs use 4-bit lookahead blocks and apply the same trick a level up on block-level P and G, giving logarithmic delay overall. Carry-select, carry-skip and parallel-prefix adders (Kogge-Stone, Brent-Kung) are variations on trading area for that logarithm.

Subtraction and comparison

Subtraction needs no new datapath. XOR each B input with a SUB signal and feed SUB into Cin: SUB = 0 gives A + B, SUB = 1 gives A + ~B + 1 = A − B. Flags fall out of the same adder — Z = all sum bits zero, N = sum MSB, C = carry out, V = C_n ^ C_{n−1}. A dedicated comparator is simpler: one bit gives A > B : A·B', A < B : A'·B, A = B : A XNOR B. For n bits, equality is the AND of all bit XNORs; magnitude is resolved by scanning from the MSB down to the first position where the bits differ — which is exactly what the chained >, =, < inputs of a cascadable comparator (the 74x85 family) expose.

Multiplexers, demultiplexers, decoders

A 2:1 MUX is Y = S'·I0 + S·I1; a 4:1 MUX is Y = S1'S0'·I0 + S1'S0·I1 + S1S0'·I2 + S1S0·I3. A demultiplexer routes one input to one of 2^k outputs; a decoder is a demux with its data input tied to 1, so its outputs are precisely the minterms of the select inputs — a 2-to-4 decoder with enable is Y0 = E·A'B', Y1 = E·A'B, Y2 = E·AB', Y3 = E·AB.

Because a 2^n:1 MUX with the variables on its selects outputs the truth-table entry those variables address, any n-variable function is one MUX plus constants. Better still, with n−1 selects the data inputs take 0, 1, x or x' for the remaining variable (Shannon expansion). For F(A,B,C) = Σm(1,2,6,7) on a 4:1 MUX with A, B on the selects:

1
2
3
4
5
AB = 00 :  m0=0, m1=1  ->  I0 = C
AB = 01 :  m2=1, m3=0  ->  I1 = C'
AB = 10 :  m4=0, m5=0  ->  I2 = 0
AB = 11 :  m6=1, m7=1  ->  I3 = 1

One MUX and one inverter for an arbitrary 3-variable function — the direct ancestor of the FPGA look-up table in Chapter 8.

Encoders, priority encoders, and the ALU

A plain 2^k-to-k encoder outputs the index of the single active input and misbehaves badly if two are active, or none. A priority encoder fixes both — highest-priority active input wins, plus a valid flag:

1
2
3
4-to-2, I3 highest:   Y1 = I3 + I2      Y0 = I3 + I2'·I1      V = I3+I2+I1+I0
check I3=0, I2=1, I1=1, I0=1  ->  Y1=1, Y0=0  ->  Y = 10 = 2  (highest active index)

This is how interrupt controllers pick a winner and how floating-point normalisers find the leading one.

An ALU is all of these blocks in parallel behind a multiplexer: adder/subtractor, AND, OR, XOR and a shifter fed the same A and B, with OpSel driving a MUX that chooses whose answer escapes and Z/N/C/V taken from the adder. Every unit computes every cycle, which is wasteful in power — real ALUs gate the unused ones — but logically that picture is the whole story.

Chapter 6 — Sequential logic

Terminology

  • Sequential circuit — output depends on present inputs and stored state: combinational logic plus feedback through memory elements.
  • Latch — level-sensitive storage, transparent while its enable is asserted.
  • Flip-flop — edge-triggered storage, sampling only at a clock edge.
  • Setup / hold time (t_su, t_h) — how long data must be stable before / after the clock edge.
  • Clock-to-Q (t_cq) — delay from the clock edge to a valid output.
  • Clock skew — difference in clock arrival time between two flip-flops.

Latches and the transparency problem

Cross-couple two NOR gates for an SR latch: S sets Q, R clears it, S = R = 0 holds, and S = R = 1 is forbidden (both outputs go low, and simultaneous release is a race). Add an enable and a data input for a gated D latch: while EN is high Q follows D; when EN falls, Q freezes.

That transparency is the problem. If the output feeds combinational logic that returns to its own input — exactly what a counter or state register does — the new value races round the loop during the enable window and can update the latch again in the same pulse, advancing the state an unpredictable number of times. The fix is to sample at an instant rather than over an interval: a master-slave pair of latches on opposite clock phases is never transparent in both halves at once, so data advances exactly one stage per edge.

Flip-flop tables

Type Behaviour Characteristic equation
D follows D at the edge Q⁺ = D
JK 0,0 hold · 0,1 reset · 1,0 set · 1,1 toggle Q⁺ = J·Q' + K'·Q
T 0 hold · 1 toggle Q⁺ = T ^ Q
SR 0,0 hold · 0,1 reset · 1,0 set · 1,1 invalid Q⁺ = S + R'·Q, with S·R = 0

Excitation tables answer the design question — "I want this transition, what input do I apply?":

1
2
3
4
5
6
7
Q -> Q+ |  D  |  T  |  J  K  |  S  R
--------+-----+-----+--------+--------
 0 -> 0 |  0  |  0  |  0  x  |  0  x
 0 -> 1 |  1  |  1  |  1  x  |  1  0
 1 -> 0 |  0  |  1  |  x  1  |  0  1
 1 -> 1 |  1  |  0  |  x  0  |  x  0

The x entries are don't-cares, and they are why JK designs used to minimise better than D designs. That advice is now obsolete: FPGA and ASIC cells are D flip-flops, and a synthesiser builds JK or T behaviour from a D flip-flop plus a little logic. Design with D flip-flops.

Timing: where the clock frequency comes from

For a path leaving flip-flop A, crossing combinational logic and arriving at flip-flop B, data must be stable before B's setup window opens. The second inequality is the one beginners forget:

1
2
3
4
5
6
7
8
9
10
T_clk ≥ t_cq(max) + t_comb(max) + t_su + t_skew      (setup / max-delay check)
f_max = 1 / T_clk(min)
 
t_cq(min) + t_comb(min) ≥ t_h + t_skew               (hold / min-delay check)
 
worked: t_cq 0.40, logic 3.10, t_su 0.30, skew 0.20 (ns)
        T_clk ≥ 4.00 ns  ->  f_max = 250 MHz
hold:   t_cq(min) 0.15 + t_cd(comb) 0.10 = 0.25  ≥  t_h 0.20 + skew 0.05 = 0.25
        passes, barely

To go faster you must shorten the longest path — pipeline it, restructure the logic (lookahead instead of ripple), or use faster cells.

Watch out: a hold violation cannot be fixed by slowing the clock — T_clk does not appear in the inequality. The data arrives too early, not too late. Fix it with delay buffers on the data path or by reducing skew. Setup violations are the ones a slower clock cures.

Metastability and synchronisers

A flip-flop whose input changes inside its setup/hold window may go metastable: its output hovers between logic levels for an unbounded time before resolving arbitrarily. This is physics, not a bug to design away, but the probability of still being unresolved after time t_r falls exponentially — MTBF = exp(t_r / τ) / (T0 · f_clk · f_data), where τ and T0 are flip-flop characteristics and f_clk, f_data the sampling and event rates. Because the decay is exponential, buying resolution time is extremely effective — hence the two-flop synchroniser, which gives the first flop almost a full clock period to settle before the second samples it (three stages for very high clock rates or reliability targets). Two rules go with it:

  1. Never synchronise a multi-bit bus bit-by-bit. Each bit resolves independently, so the receiver can latch a combination that never existed. Cross a single-bit flag and use it to qualify a bus held stable (a handshake), Gray-code the value so only one bit changes at a time, or use a proper CDC FIFO.
  2. Synchronise once. Feeding one asynchronous signal into two synchronisers can give the two copies different answers in the same cycle.

Registers and counters

A register is n flip-flops sharing a clock; add a load enable and a mux and it holds or loads. A shift register wires each Q to the next D — serial-in/parallel-out, parallel-in/serial-out, bidirectional, or with taps and XOR feedback as a linear feedback shift register for pseudo-random sequences and CRCs.

Ripple (asynchronous) counter Synchronous counter
Clocking each FF clocked by the previous FF's output all FFs share one clock
Delay cumulative — n · t_cq to settle one t_cq plus next-state logic
Decoding transient wrong states → decoding glitches glitch-free if outputs are registered
Timing analysis painful (generated clocks) straightforward
Use in new designs? almost never yes

Designing a modulo-6 synchronous counter

Count 0→1→2→3→4→5→0 with three D flip-flops Q2 Q1 Q0. States 6 and 7 are unreachable, so their next states are don't-cares.

1
2
3
4
5
6
7
8
9
10
11
 Q2 Q1 Q0 | Q2+ Q1+ Q0+          Minimising each column on a 3-variable
----------+-------------         K-map, using the don't-cares:
  0  0  0 |  0   0   1
  0  0  1 |  0   1   0             D0 = Q0'
  0  1  0 |  0   1   1             D1 = Q2'·Q1'·Q0 + Q1·Q0'
  0  1  1 |  1   0   0             D2 = Q2·Q0'      + Q1·Q0
  1  0  0 |  1   0   1
  1  0  1 |  0   0   0           Check 100: D0=1, D1=0+0=0,
  1  1  0 |  d   d   d           D2 = 1·1 + 0 = 1  ->  101. Correct.
  1  1  1 |  d   d   d

Always finish by checking that the unused states cannot lock up. State 110 gives D2 = 1·1 + 1·0 = 1, D1 = 0 + 1·1 = 1, D0 = 1 → 111; state 111 gives D2 = 1·0 + 1·1 = 1, D1 = 0, D0 = 0 → 100, inside the legal ring. This counter is self-recovering: an illegal state caused by noise or power-up rejoins the sequence within two clocks. When that is not guaranteed, add a reset — which you should do anyway.

Chapter 7 — Finite state machines

Terminology

  • FSM — a sequential circuit given by a finite state set, a transition function and an output function.
  • Moore machine — outputs depend on the current state only.
  • Mealy machine — outputs depend on the current state and current inputs.
  • State assignment — the choice of bit pattern representing each state.
  • Equivalent states — states producing identical output for every input sequence, so mergeable.
Moore Mealy
Output is a function of state state and input
Output timing changes only after a clock edge; one cycle "late" responds in the same cycle
Output glitches none — a decode of registered state possible — input glitches pass through
State count usually more usually fewer or equal
Timing analysis clean input-to-output path crosses the module boundary

Practical guidance: use Moore for anything leaving the module (registered, glitch-free, easy to time), and Mealy inside a module when the one-cycle latency actually matters. A common hybrid is a Mealy machine with registered outputs — which is a Moore machine with extra steps, and often the cleanest of the three.

The flow is always: spec → state diagram → state table → state minimisation → state assignment → next-state and output equations → implementation.

Worked FSM: a "1011" sequence detector

Detect 1011 in a serial bit stream, with overlap (so 1011011 contains two occurrences). Moore version, states named by the longest prefix matched so far:

State Meaning on 0 on 1 Output
S0 nothing matched S0 S1 0
S1 1 S2 S1 0
S2 10 S0 S3 0
S3 101 S2 S4 0
S4 1011 — detected S2 S1 1

The non-obvious transitions are the failure ones, each found by asking what is the longest prefix of the pattern that is a suffix of what I have just seen? S3 on 0 leaves the stream ending 1010, whose longest such suffix is 10 → S2, not S0. S4 on 0 ends 10110 → also S2. S4 on 1 ends 10111, longest such suffix 1 → S1.

For the non-overlapping variant, S4 restarts from scratch: on 0 → S0, on 1 → S1. That single row is the entire difference, and it is worth being explicit about which one the spec wants.

The Mealy version needs only four states, because detection is signalled on the transition into the match rather than by a state representing it:

State on 0 (next / out) on 1 (next / out)
S0 S0 / 0 S1 / 0
S1 S2 / 0 S1 / 0
S2 S0 / 0 S3 / 0
S3 S2 / 0 S1 / 1

Both machines on the same stream — identical detections, one fewer state, and the Mealy output asserting a cycle earlier (high during the cycle in which the final 1 is presented, rather than after it has been clocked in):

1
2
3
4
5
6
input        :  1    0    1    1    0    1    1
Moore state  :  S1   S2   S3   S4   S2   S3   S4
Moore output :  0    0    0    1    0    0    1    <- two overlapping detections
Mealy state  :  S1   S2   S3   S1   S2   S3   S1
Mealy output :  0    0    0    1    0    0    1

State minimisation

Two states are equivalent when, for every input, they give the same output and go to equivalent states. Two mechanical methods: partition refinement (split states into groups by output, then repeatedly split any group whose members transition, on the same input, into different groups, until nothing splits) and the implication chart (a triangular table of state pairs, crossing out pairs with different outputs and iterating on the implied pairs). Neither helps the 1011 detector — its five Moore states all differ — but both matter when a machine is written directly from an informal spec, where duplicate states are common.

State assignment: one-hot vs binary

Binary (encoded) One-hot
Flip-flops for N states ceil(log2 N) N
Next-state logic wider, deeper narrow — often one product term per transition
Output decode a decoder over the state bits a single wire
Best for ASIC, register-poor targets, large N FPGA, small-to-medium N, high f_max

FPGAs have flip-flops in abundance and are limited by logic depth, so one-hot usually wins there and is often what the tool picks regardless of how you wrote it. Gray-coded assignment suits a machine that mostly walks a linear sequence, minimising switching and hence power. Whatever the encoding, write a default branch returning to a safe state — a single upset bit in a one-hot register produces an all-zero or two-hot state that no legal transition covers.

Chapter 8 — Memory and programmable logic

SRAM vs DRAM at the cell level

SRAM DRAM
Cell 6 transistors: two cross-coupled inverters + 2 access transistors 1 transistor + 1 capacitor
Storage a latched, actively driven state charge on a capacitor
Read non-destructive destructive — must be written back
Refresh none while powered yes, every row periodically (tens of ms)
Density low several times denser per bit
Speed fast, low latency slower; row-activate / column-access protocol
Typical use caches, register files, FPGA block RAM main memory

The 6T SRAM cell is a bistable pair of inverters — the same feedback loop as an SR latch — with two pass transistors connecting it to the bit lines when its word line is selected. Being actively driven, it holds indefinitely while powered and reads without disturbance. The 1T1C DRAM cell holds charge that leaks, so reading dumps it onto the bit line where a sense amplifier compares it against a reference and rewrites the row. That destructive read plus refresh is the entire reason DRAM has a complicated protocol and SRAM does not. Both are volatile; neither survives power loss.

The non-volatile family

Type Programmed Erased Granularity Typical use
ROM (mask) at fabrication never — huge-volume fixed firmware
PROM once, by the user (fuses/antifuses) never — one-time configuration
EPROM electrically UV through a quartz window whole chip historical; development parts
EEPROM electrically electrically byte configuration and calibration stores
Flash (NOR) electrically electrically block erase; random reads code storage, execute-in-place
Flash (NAND) electrically electrically page write / block erase mass storage (SSD, SD, eMMC)

NOR gives random reads, so a CPU can fetch instructions directly; NAND gives density and is used where data is streamed. Both wear out as erase cycles degrade the oxide, which is why controllers do wear levelling.

Logic in a ROM, and the programmable arrays

A ROM with n address lines and m data lines is a full truth table for m functions of n variables: its decoder generates all 2^n minterms and the programmed array ORs the selected ones onto the outputs. No minimisation is needed or possible — you store the answer. The cost is exponential in input count (a 16-input function needs a 64K-word ROM), so ROM-based logic suits genuinely irregular functions: character generators, instruction decoders, microcode.

Between hard-wired gates and a full truth table sit the programmable arrays. A PLA has a programmable AND plane and a programmable OR plane — maximum flexibility, slower and more expensive. A PAL has a programmable AND plane and a fixed OR plane (a fixed number of product terms per output) — cheaper and faster; the classic 22V10 added an output macrocell with an optional flip-flop, which is what made PALs usable for state machines. A CPLD is an array of PAL-like blocks joined by global interconnect, with deterministic timing and instant-on behaviour — still the right answer for board glue logic and power sequencing.

FPGA architecture

An FPGA is a sea of configurable blocks plus programmable routing, its configuration held in SRAM and therefore loaded from external Flash at power-up:

  • LUT (look-up table) — a k-input SRAM, typically k = 4 or 6, holding 2^k configuration bits, implementing any function of k variables by storing its truth table. This is the MUX-as-arbitrary-function trick from Chapter 5, made programmable.
  • Flip-flop — one or two per logic cell, after the LUT with an optional bypass. Registers are effectively free, which is why one-hot encoding and deep pipelining suit FPGAs.
  • Carry chain — a dedicated fast path between adjacent cells, so adders and counters skip general routing delay.
  • Routing fabric — wire segments and programmable switch matrices. Routing, not logic, dominates delay, which is why timing closure is a place-and-route problem.
  • Block RAM — hard dual-ported SRAM blocks, usable as RAM, ROM or FIFO. DSP slices — hard multiply-accumulate units.
  • Clock management — PLLs/MMCMs plus dedicated low-skew global clock networks. Always use those networks for clocks; never route a clock through the general fabric.

Chapter 9 — HDL in practice (Verilog)

Terminology

  • HDL — hardware description language. It describes structure and behaviour, from which a synthesiser infers gates. It is not a program.
  • Synthesisable subset — the constructs a synthesis tool can map to hardware. Everything else is simulation-only.
  • RTL — the "registers, and the combinational logic between them" abstraction that synthesisable HDL describes.

The one thing to internalise: HDL is not sequential code. Every assign and every always block in a module is hardware that exists simultaneously and runs continuously. Statements inside an always block are evaluated in order during simulation, but what they describe is a network of gates that settles, not a sequence of steps executing over time. Reasoning "this line runs, then that line runs" produces code that simulates one way and synthesises another — the classic and most expensive bug in the field.

Module, ports, wire and reg

1
2
3
4
5
6
7
8
9
10
11
module full_adder (
    input  wire a,
    input  wire b,
    input  wire cin,
    output wire sum,
    output wire cout
);
    assign sum  = a ^ b ^ cin;
    assign cout = (a & b) | (cin & (a ^ b));
endmodule

assign is a continuous assignment: the left side is recomputed whenever anything on the right changes. It drives a wire and describes combinational logic.

reg is Verilog's most misleadingly named keyword. It does not mean "flip-flop" — it means "a variable assigned inside a procedural block". A reg assigned in always @(*) is combinational logic; a reg assigned in always @(posedge clk) is a flip-flop. SystemVerilog's logic replaces both wire and reg in most contexts, which is one good reason to write -g2012 SystemVerilog where the tools allow it.

Blocking vs non-blocking

1
2
3
4
5
6
7
8
9
10
11
// SEQUENTIAL logic: clocked block, non-blocking <=
always @(posedge clk or negedge rst_n) begin
    if (!rst_n) q <= 1'b0;
    else        q <= d;
end
 
// COMBINATIONAL logic: always @(*), blocking =
always @(*) begin
    y = a & b;
end

Use non-blocking (<=) in clocked blocks and blocking (=) in combinational blocks. Never mix the two in one block, and never drive one signal from two blocks.

Why it matters — the swap, and the accidental latch:

1
2
3
4
5
6
7
8
9
10
11
always @(posedge clk) begin a <= b; b <= a; end  // both read OLD values -> swap
always @(posedge clk) begin a =  b; b =  a; end  // a already updated -> both = old b
 
always @(*) begin                 // BAD: y unassigned on one path -> infers a LATCH
    if (sel) y = a;
end
always @(*) begin                 // GOOD: default first, then override
    y = 1'b0;
    if (sel) y = a;
end

Non-blocking assignments schedule their updates and apply them together at the end of the time step — exactly what a bank of flip-flops does, every flop sampling the values that existed just before the edge. Blocking assignments take effect immediately, modelling a wire rather than a register. Get this backwards and simulation and synthesis disagree; the tools are not obliged to warn you. The latch rule is the same one from Chapter 6 seen from the language side: in a combinational block, assign every output on every path — including a default: in every case. SystemVerilog's always_comb makes the tool check this for you.

An FSM the canonical way

The 1011 Moore detector from Chapter 7, in three-block style: one clocked block for the state register, one combinational block for next-state logic, one for outputs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
module seq_detect_1011 (
    input  wire clk,
    input  wire rst_n,
    input  wire din,
    output reg  found
);
    // S0 nothing, S1 "1", S2 "10", S3 "101", S4 "1011" (detected)
    localparam [2:0] S0 = 3'd0, S1 = 3'd1, S2 = 3'd2, S3 = 3'd3, S4 = 3'd4;
    reg [2:0] state, next_state;
 
    // 1. state register (sequential, non-blocking)
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) state <= S0;
        else        state <= next_state;
    end
 
    // 2. next-state logic (combinational, blocking, fully specified)
    always @(*) begin
        next_state = state;
        case (state)
            S0: next_state = din ? S1 : S0;
            S1: next_state = din ? S1 : S2;
            S2: next_state = din ? S3 : S0;
            S3: next_state = din ? S4 : S2;
            S4: next_state = din ? S1 : S2;
            default: next_state = S0;
        endcase
    end
 
    // 3. output logic (Moore: a function of state only)
    always @(*) begin
        found = (state == S4);
    end
endmodule

Every transition in the table appears exactly once, default recovers from illegal states, and found is a pure decode of the state. For the Mealy form, drop S4 and write found = (state == S3) && din; — noting that found now depends on an input and can therefore glitch. Two-block style (merging blocks 2 and 3) is equally fine, as is one-block style with registered outputs; mixing styles inside one module is how people end up with a signal driven from two places.

A testbench

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
`timescale 1ns / 1ps
 
module tb_seq_detect_1011;
    reg  clk = 1'b0, rst_n = 1'b0, din = 1'b0;
    wire found;
    integer i;
    localparam [15:0] STREAM = 16'b1011011010110000;   // fed MSB first
 
    seq_detect_1011 dut (.clk(clk), .rst_n(rst_n), .din(din), .found(found));
 
    always #5 clk = ~clk;                              // 10 ns period = 100 MHz
 
    initial begin
        $dumpfile("tb_seq_detect_1011.vcd");
        $dumpvars(0, tb_seq_detect_1011);
        @(negedge clk); rst_n = 1'b1;
        for (i = 15; i >= 0; i = i - 1) begin
            din = STREAM[i];
            @(negedge clk);                            // let the posedge sample din
            if (found) $display("t=%0t : detected (bit index %0d)", $time, i);
        end
        $finish;
    end
endmodule

Driving stimulus on the falling edge and checking after the next falling edge keeps the testbench clear of the design's setup and hold windows — a habit worth forming early.

Synthesisable or not

Construct Synthesisable?
assign, always @(*), always @(posedge clk) yes
case, if/else, for with constant bounds (unrolled) yes
localparam, parameter, generate yes
initial blocks no for ASIC; FPGA tools accept them for register initial values
#10 delays, wait, fork/join no — simulation only
$display, $monitor, $finish, $dumpvars no — simulation only
real, dynamic arrays, classes, data-dependent while no

Common pitfall: a #5 delay inside a design module simulates beautifully and synthesises to nothing (or an error). Timing in real hardware comes from the clock and from cell delays, never from delay statements in your source.

A toolchain you can install today

1
2
3
4
5
6
7
8
9
10
11
# simulate and view waveforms
iverilog -g2012 -o sim tb_seq_detect_1011.v seq_detect_1011.v
vvp sim
gtkwave tb_seq_detect_1011.vcd
 
# lint before you ever simulate: catches latches, width mismatches, unused signals
verilator --lint-only -Wall seq_detect_1011.v
 
# synthesise to a generic gate netlist and see the actual cell count
yosys -p "read_verilog seq_detect_1011.v; synth; stat"

Add nextpnr to place and route for the open-toolchain FPGA families (Lattice iCE40 and ECP5), or use the vendor tools — AMD/Xilinx Vivado, Intel/Altera Quartus Prime, Lattice Radiant — whose free editions cover the parts on most dev boards.

Trick: run verilator --lint-only -Wall on every file before simulating. It finds inferred latches, incomplete sensitivity lists and width mismatches in a second, which is faster than finding them in a waveform.

Practice Exercises

Exercise 1 — Representations

(a) Convert 205 decimal to binary, octal and hexadecimal. (b) Write −37 as an 8-bit two's-complement value. (c) Adding the 8-bit signed values 0101 1010 and 0011 0111, does overflow occur?

Solution 
1
2
3
4
5
6
7
8
(a) 205 = 128 + 64 + 8 + 4 + 1 = 1100 1101
    octal 011 001 101 -> 315 (3*64 + 8 + 5 = 205);  hex -> CD (12*16 + 13 = 205)
(b) 37 = 0010 0101 -> invert 1101 1010 -> +1 = 1101 1011
    check: -128 + 64 + 16 + 8 + 2 + 1 = -37
(c) 0101 1010 (+90) + 0011 0111 (+55) = 1001 0001 (145 unsigned)
    carry INTO bit 7 = 1, carry OUT of bit 7 = 0  ->  OVERFLOW
    two positives produced a negative (-111): 145 does not fit in -128..127

Exercise 2 — Algebraic simplification

Simplify F = A'B'C' + A'B'C + A'BC' + AB'C' to minimal SOP using the laws of Chapter 2, then confirm with a K-map.

Solution 
1
2
3
4
5
6
7
8
9
10
11
F = A'B'(C' + C) + A'BC' + AB'C' = A'B' + A'BC' + AB'C'
Reuse A'B'C' by idempotence to pair with each remaining term:
  = A'B' + A'C'(B + B') + B'C'(A + A') = A'B' + A'C' + B'C'
 
K-map check, F = Σm(0,1,2,4):
        BC
   A \  00   01   11   10
   0  |  1  |  1  |  0  |  1  |
   1  |  1  |  0  |  0  |  0  |
   groups: (m0,m1) = A'B'   (m0,m2) = A'C'   (m0,m4) = B'C'

All three are prime and all three essential — m1, m2 and m4 are each covered by only one of them.

Exercise 3 — Karnaugh map

Minimise F(A,B,C,D) = Σm(1,3,5,7,9,13) and state which prime implicants are essential.

Solution 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
          CD
   AB \  00   01   11   10
   00  |  0  |  1  |  1  |  0  |    m0  m1  m3  m2
   01  |  0  |  1  |  1  |  0  |    m4  m5  m7  m6
   11  |  0  |  1  |  0  |  0  |    m12 m13 m15 m14   (m15 is NOT in the list)
   10  |  0  |  1  |  0  |  0  |    m8  m9  m11 m10
 
Group 1: m1, m3, m5, m7   (rows AB=00,01 x columns CD=01,11) -> A=0, D=1 -> A'D
Group 2: m1, m5, m13, m9  (the whole CD=01 column)           -> C=0, D=1 -> C'D
 
F = A'D + C'D = D·(A·C)'
 
Both are essential: A'D alone covers m3 and m7; C'D alone covers m9 and m13.

Exercise 4 — MUX implementation

Implement F(A,B,C) = Σm(0,3,5,6) using a single 4:1 multiplexer with A and B on the select lines.

Solution 
1
2
3
4
5
6
7
8
AB = 00 :  m0 = 1, m1 = 0   ->  I0 = C'
AB = 01 :  m2 = 0, m3 = 1   ->  I1 = C
AB = 10 :  m4 = 0, m5 = 1   ->  I2 = C
AB = 11 :  m6 = 1, m7 = 0   ->  I3 = C'
 
One 4:1 MUX plus one inverter. The function is 1 whenever an even number of
inputs are 1, i.e. F = (A ^ B ^ C)' — three-input XNOR.

Exercise 5 — Timing

A path has t_cq = 0.35 ns, worst-case combinational delay 2.90 ns, t_su = 0.25 ns and skew 0.15 ns. (a) What is f_max? (b) The design must run at 400 MHz — by how much must the logic delay fall, and name two ways to achieve it.

Solution 
1
2
3
4
5
6
7
8
9
10
11
(a) T_clk >= 0.35 + 2.90 + 0.25 + 0.15 = 3.65 ns  ->  f_max = 274 MHz
(b) 400 MHz -> T_clk = 2.50 ns
    logic budget     = 2.50 - 0.35 - 0.25 - 0.15 = 1.75 ns
    reduction needed = 2.90 - 1.75 = 1.15 ns
    1. Pipeline: insert a register partway through the logic cone, splitting it
       into two shorter paths (costs one cycle of latency).
    2. Restructure: replace a linear structure with a tree or lookahead form
       (ripple-carry -> carry-lookahead), or retime across an existing register.
    Slowing the clock is not an option here, and would not have helped a hold
    violation at all.

Exercise 6 — Hazard removal

Show that F = A'B + AC, built as a two-level AND-OR network, has a static-1 hazard, and give the hazard-free implementation.

Solution 
1
2
3
4
5
6
7
8
9
10
11
12
13
Hold B = 1 and C = 1. Then F = A' + A = 1 for both values of A, so F should
never change. But when A rises 0 -> 1, A'B falls as soon as the inverter output
falls, while AC only rises after its AND gate delay. For that window both
product terms are 0 and F dips to 0: a static-1 hazard.
 
On the K-map the groups A'B and AC touch but do not overlap; the cure is the
consensus term that bridges them:
 
    F = A'B + AC + BC        (hazard-free for single-input changes)
 
BC holds the OR high through the changeover. The extra AND gate is logically
redundant, so mark it dont_touch or the synthesiser will delete it.

Exercise 7 — Counter design

Design a synchronous modulo-5 up counter (states 000 through 100) with D flip-flops: write the state table, derive the three next-state equations treating the unused states as don't-cares, and check whether the result is self-recovering.

Exercise 8 — Verilog

Write a synthesisable 4-bit up/down counter with synchronous active-high reset, a load input with 4-bit data_in, and an up direction control. Extend the Chapter 9 testbench pattern to exercise all four behaviours.

Cheat-sheet

What How
Binary → hex; sign-extend group bits in 4s from the LSB; replicate the MSB
Negate (two's complement) invert all bits, add 1
Signed overflow V = carry_in(MSB) ^ carry_out(MSB)
De Morgan (AB)' = A' + B', (A+B)' = A'B'
Absorption A + AB = A, A + A'B = A + B
Consensus AB + A'C + BC = AB + A'C
NOT / OR from NAND A NAND A / (A NAND A) NAND (B NAND B)
K-map column order 00 01 11 10 (Gray), and it wraps
Group of 2^k cells; don't-care eliminates k variables; use as whichever enlarges the group
Static-1 hazard fix add the consensus term
Half / full adder S = A^B, C = AB / S = A^B^Cin, Cout = AB + Cin(A^B)
Subtract with an adder A + ~B + 1 (invert B, Cin = 1)
Lookahead carry G = AB, P = A^B, C_i+1 = G_i + P_i·C_i
n-var function on a MUX variables on selects, truth table on data inputs
D / JK / T flip-flop Q+ = D / Q+ = J·Q' + K'·Q / Q+ = T ^ Q
Setup / hold checks T ≥ t_cq + t_comb + t_su + t_skew; t_cq(min) + t_comb(min) ≥ t_h + t_skew
Cross a clock domain two-flop synchroniser; Gray-code multi-bit values
Verilog sequential vs combinational always @(posedge clk) with <= / always @(*) with =
Avoid an inferred latch default-assign at the top of the block, or default: in the case
Simulate free iverilog -g2012 + vvp + gtkwave

Where to go deeper

  • Computer architecture — the natural sequel. With an ALU, a register file and an FSM controller in hand, a single-cycle then pipelined RISC-V or MIPS datapath is a two-week project.
  • CMOS VLSI — the layer below this post: transistor sizing, logical effort, layout, and where the timing numbers you were handed come from.
  • Static timing analysis and timing closure — constraints, clock trees, multi-corner analysis, false and multi-cycle paths. This is most of the day-to-day work in real FPGA and ASIC flows.
  • Clock domain crossing and asynchronous design — handshakes, async FIFOs, reset synchronisation. The failures are intermittent and expensive; read the literature properly.
  • SystemVerilog and verification — logic, always_ff/always_comb, interfaces, assertions, constrained-random stimulus, UVM.
  • Get a board. An iCE40 or ECP5 runs entirely on the open toolchain; an Artix or Cyclone gets you the vendor flow. Nothing here is properly learned until a blinking LED has been debugged with a logic analyser.

References

  • Digital Design and Computer Architecture — Harris & Harris. The best single bridge from gates to a working processor.
  • Digital Design: Principles and Practices — John F. Wakerly. Thorough on minimisation, hazards and real device families.
  • Digital Design: With an Introduction to the Verilog HDL — Mano & Ciletti. The standard first course.
  • CMOS VLSI Design: A Circuits and Systems Perspective — Weste & Harris. For Chapter 3's transistor-level material and logical effort.
  • Icarus Verilog — free Verilog/SystemVerilog simulator.
  • GTKWave — waveform viewer for VCD files.
  • Verilator — linter and high-speed simulator.
  • Yosys — open-source synthesis; nextpnr for place-and-route.
  • IEEE Standards Association — IEEE 1364 (Verilog) and IEEE 1800 (SystemVerilog).
  • Sunburst Design papers — Clifford Cummings on non-blocking assignments, FSM coding styles and clock domain crossing.

Planned future extensions:

  • A companion post building a single-cycle RISC-V datapath up from the ALU and register file assembled here.
  • Rendered schematic and K-map figures to replace the ASCII diagrams.
  • A downloadable Verilog project (adder, FSM, counter, testbenches) with a Makefile for the Icarus/Verilator/Yosys flow.
  • A dedicated treatment of static timing analysis: constraints, corners, false paths, and how to read a timing report.
  • Asynchronous FIFO design worked end to end, as the practical follow-on to the clock-domain-crossing section.