09 Asynchronous Sequential Circuits

This chapter covers sequential circuits that operate without a clock signal — changes in state are triggered directly by input changes rather than clock edges. The fundamental mode of operation is introduced, where only one input may change at a time and the circuit must reach a stable state before the next change. Analysis involves flow tables (the asynchronous equivalent of state tables) with stable and unstable states. Synthesis follows a procedure: primitive flow table → merged flow table → state assignment → next-state and output equations. State reduction techniques for asynchronous circuits are presented. Critical races and state assignment problems are addressed, including one-hot encoding as a race-free alternative. The chapter thoroughly covers hazards: static hazards (1-hazards and 0-hazards), dynamic hazards, and their elimination through redundant terms. A complete vending machine controller example ties all concepts together.

本章介紹不依靠時脈訊號運作的非同步循序電路 (asynchronous sequential circuit)——狀態的改變由輸入訊號直接觸發，而不是由時脈邊緣引發。首先介紹基本模式 (fundamental mode)：每次只允許一個輸入改變，且電路必須在下一次輸入變化前先抵達穩定狀態。分析以流程表 (flow table)進行——它是狀態表 (state table) 的非同步對應物，含有穩定狀態與不穩定狀態。合成則依循固定流程：原始流程表 → 合併流程表 → 狀態指派 → 推導下一狀態與輸出方程式。本章亦說明非同步電路的狀態縮減技巧。臨界競爭 (critical race) 與狀態指派問題也被詳細討論，並介紹 one-hot 編碼作為避免競爭的替代方案。書中徹底剖析冒險 (hazards)：靜態 1 冒險 (static 1-hazard)、靜態 0 冒險 (static 0-hazard)、動態冒險 (dynamic hazard)，以及如何透過添加冗餘項加以消除。最後以一個完整的販賣機控制器範例貫穿所有概念。

Fundamental Mode Flow Tables Stable / Unstable States Races & State Assignment Static / Dynamic Hazards Hazard-Free Design One-Hot Encoding Vending Machine Example
9.1EasyTier 1?R✓
Define the fundamental mode of operation for asynchronous circuits. What constraints are placed on the inputs?
9.4MediumTier 1?R✓
Explain what a critical race is. Give an example of a state assignment that causes a critical race and show how to fix it.
9.6EasyTier 1?R✓
Define static 1-hazard, static 0-hazard, and dynamic hazard. Which one is most common in two-level SOP circuits?
9.12MediumTier 1?R✓
Design a Muller C-element: output becomes 1 when both inputs are 1, becomes 0 when both are 0, and holds its state otherwise. Derive using asynchronous design techniques.
9.20HardTier 1E?R✓
Reduce a 12-row primitive flow table (Figure 9.32) by first applying the partitioning procedure, then constructing a merger diagram for the resulting flow table, and finally merging compatible rows. Show successive reductions until no further merging is possible.
Context: Example 9.8 — full two-step reduction of a 12-row primitive table

Setup. Figure 9.32 is a primitive flow table with 11 rows labeled $A, B, C, D, E, F, G, H, J, K, L$ (the letter $I$ is skipped to avoid confusion with the digit 1) — one stable state per row — driven by inputs $w_2 w_1$. Outputs are 0 or 1 per row.

Reproduced Figure 9.32 (bold = stable state in that row, "—" = don't-care):

State$w_2 w_1$=00=01=10=11$z$
AAFC—0
BAB—H1
CG—CD0
D—F—D1
EG—ED1
F—F—H0
GGBJ—0
H—LEH1
JG—J—0
K—BEK1
LAL—K1

The reduction proceeds in two distinct stages: (i) partitioning to find equivalent states that can be renamed without affecting don't-cares, then (ii) a merger diagram to combine compatible states even when they aren't strictly equivalent.

Stage 1 — Partitioning procedure

  1. Initial partition $P_1$: group rows that have the same output AND their don't-care entries fall in the same columns. The textbook identifies three candidate equivalence pairs: $(A, G)$, $(B, L)$, $(H, K)$. All other rows are distinct, so
$$P_1 = (AG)(BL)(C)(D)(E)(F)(HK)(J)$$
  1. Refine by successors. For each candidate pair, check whether their next-state successors land in the same blocks of $P_1$ for every input column. Successors of $(A, G)$ split across different blocks → $A$ and $G$ are NOT equivalent → split. Successors of $(B, L)$ and $(H, K)$ all stay in single blocks → keep as equivalent pairs. New partition:
$$P_2 = (A)(G)(BL)(C)(D)(E)(F)(HK)(J)$$
  1. Iterate until stable. Repeating the successor test on $P_2$ yields $P_3 = P_2$ — convergence. So merge $B \leftarrow B+L$ and $H \leftarrow H+K$. Result: 10-row table (Figure 9.33).

Stage 2 — Merger diagram (compatibility, not equivalence)

Two rows are compatible (mergeable) if their specified next-state entries don't conflict — don't-cares can absorb any value, and same-stable-state pairs always agree. Build a graph where each row is a vertex and each compatible pair is an edge. Find a clique cover (a set of cliques whose union is all rows); each clique becomes one merged row.

For Figure 9.33 the merger diagram suggests:

  • $B$ and $H$ can merge → new row $B$ ($B \cup H$)
  • $D$ and $E$ can merge → new row $D$ ($D \cup E$)
  • $A$, $F$, $C$, $G$, $J$ have multiple compatibility options — typical trial-and-error step

Successive reductions with one such cover give 12 → 10 → 6 → ... rows. The final answer depends on which compatible-pair groupings you pick (this is generally NP-hard for arbitrary flow tables, but small instances are tractable).

Why two stages?

  • Partitioning finds logically equivalent states. Merging them is "free" — same don't-cares preserved, no flexibility lost.
  • Merger finds compatible (not equivalent) states. Merging them resolves don't-cares one specific way, sacrificing flexibility but reducing state count further.

Doing partitioning first preserves maximum flexibility for the merger stage, often producing a smaller final state count than running merger alone.

Practical workflow: for hand work, start with the partition (deterministic — no choices), then sketch the merger diagram and try a couple of clique covers. The minimum-state table is the merger's clique cover with fewest cliques.

— example 9.8
9.35HardTier 1E?R✓
Derive a hazard-free minimum-cost SOP implementation for $f(x_1,\ldots,x_5) = \sum m(2,3,14,17,19,25,26,30) + D(10,23,27,31)$. Find the minimum-cost prime-implicant cover, then add any extra prime implicants needed so that every pair of adjacent 1s in the K-map is covered by some product term.