Recap of exercise 6.1. The FSM detects the input sequence 101 on input $w$ and asserts $z=1$ when the sequence completes. Overlapping is allowed — e.g., on $w = 1,0,1,0,1$ the detector should fire twice: at position 3 (first "101") and at position 5 (second "101", reusing the "1" at position 3).

Moore state diagram (4 states):

• A — initial / no useful prefix. $w=0 \to A$, $w=1 \to B$. $z=0$.
• B — last input was 1. $w=0 \to C$, $w=1 \to B$. $z=0$.
• C — last two inputs were "10". $w=0 \to A$, $w=1 \to D$ (sequence complete). $z=0$.
• D — sequence "101" just detected. $w=0 \to C$ (the new "0" plus the trailing "1" from D forms "10"), $w=1 \to B$ (overlap — the trailing "1" of D plus the new "1" makes B). $z=1$.

Overlapping comes from D\'s transitions: the "1" that completed the sequence is reused as the prefix of the next attempt.

State table with 2-bit Gray-style binary assignment $A=00, B=01, C=10, D=11$:

Next-state equations (D flip-flops):

$Y_1$ K-map by inspection — $Y_1 = 1$ only in cells where $w=1$ (regardless of present state):

$Y_2$ K-map — $Y_2 = 1$ in cells: $(w=0, y_2 y_1 = 01)$, $(w=0, y_2 y_1 = 11)$, $(w=1, y_2 y_1 = 10)$. Group: the first two cells share $\overline{w}\,y_1$; the third is $w\,y_2\,\overline{y_1}$.

Output: $z = 1$ only in state D = 11.

Implementation: 2 D flip-flops + a few gates. Total cost: 1 buffer ($Y_1 = w$ — no logic), 1 AND2 + 1 AND3 + 1 OR2 ($Y_2$), 1 AND2 ($z$) ≈ 5 gates / 9 inputs. Modern synthesis tools would derive this exactly.

Verification. Trace input $w = 1,0,1,0,1$ starting in A:

Two "101" detections at cycles 2 and 4 — overlap correctly detected.

Recap of exercise 6.3 (Moore version). The FSM outputs $z=1$ once it has received at least three consecutive 1s on input $w$. As soon as a 0 arrives, the run breaks and the count resets.

Moore state diagram — 4 states:

• A — no 1s pending. $w=0 \to A$, $w=1 \to B$. $z = 0$.
• B — saw one 1. $w=0 \to A$, $w=1 \to C$. $z = 0$.
• C — saw two consecutive 1s. $w=0 \to A$, $w=1 \to D$. $z = 0$.
• D — saw three or more consecutive 1s. $w=0 \to A$, $w=1 \to D$ (stay). $z = 1$.

The Moore output is a function of state alone, so distinguishing "saw 3" from "saw ≥3" requires a separate "detection" state D where $z=1$ is registered.

Mealy version — 3 states:

• A — no 1s. $w=0/0 \to A$, $w=1/0 \to B$.
• B — saw one 1. $w=0/0 \to A$, $w=1/0 \to C$.
• C — saw two consecutive 1s. $w=0/0 \to A$, $w=1/\mathbf{1} \to C$ (output 1 on the third 1; stay in C as long as 1s continue, firing $z=1$ on every additional 1).

Notation $w/z$ means input/output on the transition. The Mealy form fires $z=1$ on the transition from C to itself when $w=1$, so we don\'t need a separate "saw three" state — the third 1\'s effect is registered as the output of the very transition that observes it.

Mealy state diagram (return arrows from B and C to A are routed at distinct depths so they never overlap):

Verilog (Mealy, 3 states) — combinational output uses both state and input $w$ on the C→C transition:

module mealy_three_ones (
  input  clock, resetn, w,
  output reg z
);
  reg [1:0] y;
  parameter A = 2'b00, B = 2'b01, C = 2'b10;

  // single always block: state register + registered Mealy output
  always @(posedge clock or negedge resetn) begin
    if (!resetn) begin
      y <= A;
      z <= 1'b0;
    end else begin
      case (y)
        A:       begin y <= (w ? B : A); z <= 1'b0; end
        B:       begin y <= (w ? C : A); z <= 1'b0; end
        C:       begin y <= (w ? C : A); z <= w;    end  // z=1 on C&&w=1
        default: begin y <= A;         z <= 1'b0; end
      endcase
    end
  end
endmodule

Comparison:

Key takeaways:

• Mealy reduces state count by folding "I just detected the event" into the transition output rather than into a dedicated state. Saves exactly one state in this case (4 → 3).
• Flip-flop count doesn\'t always go down with state count — both versions need 2 flip-flops because $\lceil \log_2 3 \rceil = \lceil \log_2 4 \rceil = 2$.
• Mealy output $z$ can change in the middle of a clock cycle when $w$ changes — Moore $z$ only changes at clock edges. If glitch-free output is required, Moore is safer; if minimum latency from input to output matters, Mealy wins.

The three-block style separates an FSM into three distinct always blocks, each with one focused responsibility. It cleanly mirrors the FSM's conceptual decomposition into a state register, a next-state function, and an output function:

The three blocks at a glance:

Skeleton for the "last two inputs = 01" Mealy detector (2 states):

module detect_01_mealy (
  input  clk, resetn, w,
  output reg z
);
  reg y, Y;
  parameter A = 1'b0,   // have not just seen a 0
            B = 1'b1;   // last input was 0

  // ── Block 1: state register ─────────────────────────────
  always @(posedge clk or negedge resetn) begin
    if (!resetn) y <= A;
    else         y <= Y;
  end

  // ── Block 2: next-state logic (combinational) ───────────
  always @(*) begin
    case (y)
      A: Y = (w == 1'b0) ? B : A;   // saw a 0 → go to B
      B: Y = (w == 1'b0) ? B : A;   // saw 0 again → stay; saw 1 → done, return to A
      default: Y = A;
    endcase
  end

  // ── Block 3: output logic (Mealy — uses state AND input) ──
  always @(*) z = (y == B) && (w == 1'b1);
endmodule

Why split it up:

• Each block is locally readable. Block 1 is boilerplate; Block 2 is the state-transition table; Block 3 holds the output rule.
• Blocking vs non-blocking is unambiguous. Block 1 always uses <=; Blocks 2 & 3 always use =. Mixing them in a single block is the most common synthesis-vs-simulation mismatch.
• Easy Moore ↔ Mealy switch. Only Block 3 changes; the register and transitions stay put.
• Synthesis-friendly. Tools immediately recognize the pattern and infer flip-flops + combinational cones cleanly.

Variants: some authors merge Blocks 2 & 3 into one combinational always @(*) (a "two-block" style). Others reduce Block 3 to a single assign when the output is a one-state Moore decode. The invariant: state register stays sequential and isolated; everything else is combinational and explicitly labeled.

You are given a state-assigned table — a state table where each abstract state has already been replaced by a concrete bit pattern. The job is to convert that abstract description into three Boolean expressions that you could wire up with logic gates and flip-flops.

How to read the table:

• $y_2 y_1$ = the current values of two state flip-flops (the FSM has 4 states, so $\lceil\log_2 4\rceil = 2$ flip-flops).
• Next state ($Y_2 Y_1$) = the bit pattern that should be loaded into the flip-flops on the next clock edge, listed for each input condition $w=0$ and $w=1$.
• $z$ = the output, here Moore-style — depends only on present state, not on $w$.

Notation like "$00 \to 10/11$" reads: when present state is 00, next state is 10 if $w=0$, or 11 if $w=1$.

Why "using D flip-flops" matters: a D flip-flop has the property $Q^+ = D$ — whatever you put on the D input becomes the output after the next clock edge. So if you want next-state bit $i$ to equal $Y_i$, you simply connect the combinational signal $Y_i$ to the D input of flip-flop $i$. No conversion through excitation tables is needed (unlike JK or T flip-flops, which require an extra translation step).

What you must produce — three Boolean expressions:

1. $Y_2 = D_2 = f(w, y_2, y_1)$ — the combinational logic feeding flip-flop 2.
2. $Y_1 = D_1 = f(w, y_2, y_1)$ — likewise for flip-flop 1.
3. $z = f(y_2, y_1)$ — the output decode (no $w$ since this is Moore).

Recommended procedure:

1. Expand the 4-row table into an 8-row truth table indexed by $(w, y_2, y_1)$.
2. Build a 3-variable K-map for each output column $Y_2$, $Y_1$, $z$.
3. Read off minimum SOP (or POS) from each K-map.
4. Sketch the circuit: two D flip-flops, with combinational gates implementing each $Y_i$ feeding into the corresponding $D_i$, and a small output decoder for $z$.

Sanity-check at the end: plug each row of the original table into your equations — every row's $Y_2 Y_1$ and $z$ should match. If they all match, the equations are correct (whether or not they're minimum). Then verify your K-map groupings are the largest possible to confirm minimality.

The swap operation: swap contents of registers R1 and R2 using R3 as temp storage. Three transfers in sequence: R3 ← R2, then R2 ← R1, then R1 ← R3.

FSM: Moore-type, 4 states, started by a one-cycle pulse on input w:

• A — idle, all outputs 0; stays in A while w=0, transitions to B when w=1
• B — assert R2out=1, R3in=1 (so R3 latches R2 on next edge); always advances to C
• C — assert R1out=1, R2in=1 (R2 latches R1); always advances to D
• D — assert R3out=1, R1in=1, Done=1 (R1 latches old R2); always returns to A

State diagram:

Straightforward state assignment (book convention): $A=00$, $B=01$, $C=10$, $D=11$ on $(y_2, y_1)$. With D flip-flops, the textbook derives:

What problem 6.14 asks: redo the next-state and output expressions with C and D swapped in the assignment ($A=00$, $B=01$, $C=11$, $D=10$). Compare the gate count to the original assignment — different state assignments produce algebraically different equations, often with different costs. The textbook lesson: state assignment is a non-trivial optimization knob.

One-hot encoding = each state gets its own dedicated flip-flop, and exactly one is 1 ("hot") at any moment.

Comparison for a 4-state FSM (A, B, C, D):

Trade-off:

Applied to the swap FSM ($y_1{=}A, y_2{=}B, y_3{=}C, y_4{=}D$):

Y1 = (y1 & ~w) | y4    // stay in A while w=0; come back from D
Y2 = y1 & w            // A→B when w=1
Y3 = y2                // B→C  (unconditional)
Y4 = y3                // C→D  (unconditional)
R2out = R3in = y2      // outputs come "for free"
R1out = R2in = y3
R3out = R1in = Done = y4

Each next-state expression is one tiny product term — that's the win. The cost is using 4 flip-flops instead of 2.

When to use which: Binary when area / FF count is the bottleneck. One-hot when you want simpler logic, faster combinational paths, and "free" state-output decoding — the standard choice on FPGAs where flip-flops are plentiful but routing/depth is the limit.

Figure 6.51 — original state table (7 states, Moore output $z$ depends only on present state):

Partitioning procedure (each $P_k$ groups states whose $k$-step successors stay in the same block):

• $P_1 = (ABCDEFG)$ — start with everything in one block.
• $P_2 = (ABD)(CEFG)$ — split by output: $z=1$ in $\{A,B,D\}$, $z=0$ in $\{C,E,F,G\}$.
• $P_3 = (ABD)(CEG)(F)$ — within $(CEFG)$: 1-successors are $(E,C,D,G)$. $D$ is in a different block (it's in $\{A,B,D\}$), so $F$ (whose 1-successor is $D$) splits off.
• $P_4 = (AD)(B)(CEG)(F)$ — within $(ABD)$: 1-successors are $(C,F,G)$. $F$ is in its own block, so $B$ (whose 1-successor is $F$) splits off.
• $P_5 = P_4$ — no further splits, partitioning is done.

Equivalence classes: $\{A,D\}, \{B\}, \{C,E,G\}, \{F\}$ — four classes, so the minimized FSM has 4 states. Rename $\{A,D\} \to A$ and $\{C,E,G\} \to C$ to obtain Figure 6.52:

Implementation savings: $\lceil\log_2 7\rceil = 3$ flip-flops shrink to $\lceil\log_2 4\rceil = 2$. The merged states have indistinguishable behavior — any input sequence produces the same output sequence whether you start in $A$ or $D$, or in any of $C, E, G$.

分割程序是一種系統化方法，用來找出等價狀態——也就是對所有可能的未來輸入序列都表現相同的狀態，並將它們合併。兩個狀態等價的條件是：(1) 它們有相同的輸出，且 (2) 對每一種輸入，它們的下個狀態也彼此等價。此程序逐步精煉分割，直到達到不動點 (fixed point)。

演算法：

1. $P_1$：把所有狀態放進同一個區塊 (block)。
2. $P_2$：依照輸出把狀態分組。輸出 $z$ 不同的狀態不可能等價。
3. $P_{k+1}$：對 $P_k$ 中的每個區塊，檢查所有輸入下的下個狀態。若同一區塊內兩個狀態的下個狀態落在 $P_k$ 的不同區塊，則它們不等價，必須再拆成更小的子區塊。
4. 停止條件：當 $P_{k+1} = P_k$（不再有新的分割）時停止。最終分割中的每個區塊就是一組等價類別——把同一區塊的狀態合併為單一狀態即可。

為什麼有效（非正式證明）：若兩個狀態 $X$ 和 $Y$ 不等價，必定存在某個輸入序列能區分它們——也就是經過若干步後抵達輸出不同的狀態。分割程序在第 $k$ 步追蹤的是：「只看前 $k$ 個輸入時，哪些狀態仍無法被區分」。當不再有新的區別出現時，精煉就停止；此時的分割恰好等於行為等價類。

小範例：假設：

• $P_1 = (ABC)$
• $P_2 = (AB)(C)$——依輸出分割（C 的 $z$ 不同）。
• $P_3$：在 $(AB)$ 中，$w=1$ 的後繼狀態為 $(B,C)$，分別落在 $P_2$ 的不同區塊——所以 $A$ 與 $B$ 必須分開。$P_3 = (A)(B)(C)$。
• $P_4 = P_3$——完成。三個區塊各自獨立 → 無法再合併；此 FSM 本身已經最小化。

為什麼要做？每減少一個狀態通常能省下一個或多個正反器（因為 FF 數量為 $\lceil\log_2 N ceil$），而且推導出來的下一狀態方程式與輸出方程式會有更少的最小項——電路更小、更快。對於手工設計的 FSM 來說，這個程序也能找出設計者誤以為不同、但其實重複的多餘狀態。

套用至問題 6.19：先畫出販賣機 FSM 的初始狀態圖（包含 "0¢", "5¢", "10¢", "15¢", "20¢"，若允許兩個一角硬幣連續投入則還有 "25¢"），再以此程序合併行為相同的狀態（例如「20¢——找零 5¢」狀態，若機器在下一輪投幣時會重置找零紀錄，可能等價於「5¢」狀態）。

Specification: output $z=1$ whenever the previous two values of input $w$ were both 0 or both 1; otherwise $z=0$.

FSM: Moore-type, 5 states (A reset, B/D = "saw a 0/1", C/E = "saw 00/11"):

State diagram (output is the digit after the slash):

Why exactly 5 states? The machine must remember three things: just-reset, just-saw-0, just-saw-1, plus the "00" / "11" run-detection states. Tracking only "last input" (3 states: A, B, D) isn't enough — you need to distinguish "first 0 ever" (B) from "second 0 in a row" (C) to decide whether $z$ goes high.

What problem 6.25 asks: instead of the single 5-state machine, build two parallel FSMs — one detects "two consecutive 0s" (3 states), the other detects "two consecutive 1s" (3 states). OR their outputs to get the combined $z$. The lesson: parallel decomposition often produces simpler FSMs than a single monolithic one (6 flip-flops total split between two machines vs. 3 flip-flops for the 5-state version, but with simpler next-state logic per machine).

The arrows labeled w=0 / w=1 in any state diagram are conditions, not events. The actual event that changes the state in a synchronous FSM is the rising edge of the clock.

What happens during one clock cycle:

• Between edges: the combinational next-state logic continuously evaluates $Q' = \delta(Q, w)$ — but the state register holds its current value $Q$. The arrow labels say "if $w=$0 during this cycle, the next state will be C; if $w=$1, the next state will be D".
• At the rising edge: the state-register flip-flops sample $Q'$ (whatever the next-state logic was producing in the cycle just ending) and load it. $Q$ jumps to $Q'$.

So an arrow "B → C on $w=$0" really means: "if the FSM is in state B and $w=$0 during a clock cycle, then at the rising edge that ends that cycle, the state register loads C."

What the input does: $w$ doesn't cause the transition — it selects which transition will happen at the next clock edge. Changes to $w$ between edges only matter if $w$ is at the right level when the edge fires (must satisfy setup/hold times).

Consequences:

• An input pulse shorter than a clock cycle may be missed — $w$ could be back to 0 by the next edge.
• In a Moore FSM, $z = f(Q)$ — output changes only when $Q$ changes, i.e. only at clock edges (synchronous output).
• In a Mealy FSM, $z = f(Q, w)$ — output can change mid-cycle when $w$ changes (asynchronous-looking output).

Mnemonic: the state diagram is a rulebook, not a movie. It says "in state X, if input is Y at the next clock edge, go to state Z." The clock is the implicit metronome that turns rules into transitions.

Figure 6.89 is an improved state assignment for the same 5-state "00 or 11" detector that Example 6.12 uses. The straightforward assignment in Figure 6.88 wastes the natural don't-cares; the improved one assigns codes so that $y_3$ acts as a "have we left reset?" flag — once the machine leaves state A, $y_3$ stays 1 forever.

Improved state assignment:

With D flip-flops, the textbook derives:

Since $Y_3 = 1$ always (after leaving reset), $y_3$ collapses to a constant and the FSM reduces to two flip-flops + the trivial $y_3$ — much cheaper than the Figure 6.88 assignment.

What problem 6.27 asks: redo the implementation using JK flip-flops instead of D. For each state bit $y_i$, derive $J_i$ and $K_i$ such that the next state matches.

JK excitation table (the recipe for converting present→next into $J,K$):

Apply this row-by-row to every (present-state, $w$) combination in the table above to get a 10-row excitation table; then K-map-minimize each of $J_1, K_1, J_2, K_2, J_3, K_3$. Don't-care entries (the unused codes 001, 010, 011 and the don't-cares from the JK recipe) make the K-maps very loose — minimum-cost JK expressions are typically simpler than the corresponding D expressions for the same FSM.

Same specification as Example 6.12 (output 1 when previous two inputs were both 0 or both 1), but realized as a Mealy FSM. The Mealy form needs only 3 states instead of 5 because the output can depend on the current input as well as the state — so we don't need separate "saw 00" / "saw 11" states; the output fires on the transition itself.

States and transitions:

• A — after reset, no relevant prior input. w=0 → B / z=0; w=1 → C / z=0
• B — last input was 0. w=0 → B / z=1 (00 detected); w=1 → C / z=0
• C — last input was 1. w=0 → B / z=0; w=1 → C / z=1 (11 detected)

State table (transitions show next-state / output):

Textbook state assignment ($y_2 y_1$): A=00, B=01, C=11. Code 10 is unused (don't-care). The clever bit: $y_1$ becomes a "have we left reset?" flag — once we leave A, $y_1$ stays 1, so $Y_1 = 1$ is the next-state equation. Effectively only one real flip-flop ($y_2$) is needed.

Why Mealy is more compact here: the Moore version (Example 6.12) needs separate states C and E to register "I've seen 00" / "I've seen 11" because Moore output is a function of state alone. Mealy fires its output the moment the qualifying input arrives, so the run-detection states aren't needed.

What problem 6.29 asks: write Verilog using the combinational always block style — both next-state and output are set inside always @*, with a separate always @(posedge clk) block for the state register. The Mealy nature means $z$ depends on both state and $w$, so $z$'s assignment lives in the same combinational block where state transitions are decided.

module mealy_seq (input w, clk, rst,
                  output reg z);
    parameter A = 2'b00, B = 2'b01, C = 2'b11;
    reg [1:0] state, next;

    always @(posedge clk or posedge rst)  // state register
        if (rst) state <= A;
        else     state <= next;

    always @* begin                        // next-state + output
        z = 1'b0;
        case (state)
            A: next = w ? C : B;
            B: begin next = w ? C : B; z = (w == 1'b0); end
            C: begin next = w ? C : B; z = (w == 1'b1); end
            default: next = A;
        endcase
    end
endmodule