20260709_4_tmp

20260702_4

---

今日の位置づけ（Ch13 の何をやっているか）

いま設計しているのは「具体的なゲート配線」より先に、状態機械（状態遷移）の仕様である。

1. 問題文を理解する（いつ Z=1 か）
2. 状態を定義する（何を覚えているか）
3. 遷移（矢印）を全部決める
4. 出力を決める
5. （後で）状態割当 → 次状態式 → 回路

カウンタと同じ「順序回路＝有限状態機械」の道具だが、状態の意味は「個数」ではなく 「入力系列のどの途中まで来たか（末尾・条件）」 であることが多い。

	カウンタ	系列検出器（Ch13）
状態の意味	だいたい数値（0,1,2,…）	パターンの進み具合・条件の組
覚えたいこと	何回クロックが来たか	目標系列のどこまで一致したか 等
遷移	ほぼ規則的（+1 など）	入力ビットで分岐

---

前提の読み方：矢印の「分数」と Z=1 の見え方

Mealy の矢印ラベルは分数ではない

入力 / 出力

例: S2 --1/1--> S1 の意味

• いま S2 にいる
• 入力 X=1 が来た
• その瞬間 出力 Z=1
• 次状態は S1

書き方	型	意味
矢印に 0/1	Mealy	入力0のとき出力1でその遷移
状態の中に S3 / Z=1	Moore	その状態にいるだけで Z=1（矢印は入力のみ）

「系列が最終的に1を出す」をどう見るか

遷移だけ追うと「いつ Z=1 か」が見えなくなる。理由は、長い検出条件が図では 1本の矢印（Mealy）または1状態（Moore）に圧縮 されているから。

図を開いたらこの順:

1. 先に検出ポイントをマークする
   • Mealy: すべての矢印から /1 だけ 探す
   • Moore: Z=1 の状態 を探す
2. その出発状態の意味を読む（「あと1入力で完成」など）
3. サンプル入力を表で1本トレースする
4. 細かい遷移の穴埋めはその後

Mealy 101 検出のトレース例（復習）

時刻	状態	入力	矢印	Z	次状態	意味
1	S0	1	1/0	0	S1	末尾「1」
2	S1	0	0/0	0	S2	末尾「10」
3	S2	1	1/1	1	…	101 完成

→ 途中はだいたい /0。最後に踏む /1 が検出イベント。

---

13.1 復習：系列検出器（101）の要点

系列検出器: 入力ビット列の中から指定パターン（例: 101）を検出し、検出時に Z=1。

• 入力 X はクロックの合間にだけ変化する、と仮定
• オーバーラップあり（例: 10101 の最後の 1 を次の系列の先頭に再利用可）

Mealy（状態3つ）

状態	意味
S0	まだ何も始まっていない
S1	末尾が 1
S2	末尾が 10

stateDiagram-v2
    direction LR
    S0: S0
    S1: S1
    S2: S2

    S0 --> S0: 0/0
    S0 --> S1: 1/0
    S1 --> S2: 0/0
    S1 --> S1: 1/0
    S2 --> S0: 0/0
    S2 --> S1: 1/1

• Z=1 は S2 で X=1 の矢印だけ（1/1）
• 回路例: $A^{+}=X^{\prime }B$,; $B^{+}=X$,; $Z=XA$

Moore（状態4つ）

出力は状態だけなので「101検出済み」状態 S3 が必要 → 状態数が1つ増える。

stateDiagram-v2
    direction LR
    S0: S0 / Z=0
    S1: S1 / Z=0
    S2: S2 / Z=0
    S3: S3 / Z=1

    S0 --> S0: X=0
    S0 --> S1: X=1
    S1 --> S2: X=0
    S1 --> S1: X=1
    S2 --> S0: X=0
    S2 --> S3: X=1
    S3 --> S2: X=0
    S3 --> S1: X=1

Mealy vs Moore（系列検出）

	Mealy	Moore
状態数	少ない（3）	多い（4）
出力タイミング	入力とほぼ同時	1クロック遅れがち
図での Z=1	矢印の /1	状態の Z=1

---

13.2 More Complex Design Problems

問題A（Mealy）: 末尾が 010 または 1001 なら Z=1（オーバーラップあり）

Output Z should be 1 if the input sequence ends in either 010 or 1001 with overlap.

検出が2種類あるので、/1 の矢印も複数になる。

設計の進め方（組み立ての手順）

1. まず 010 だけの部分グラフ（Figure 13-8）
2. 1001 の道を足す（Figure 13-9）
3. 足りない遷移を「末尾の再利用」で埋めて完成（Figure 13-10）

毎回聞く質問:

新しいビットが付いたあと、列の末尾は、既知のどの状態の意味と同じか？
同じ → 既存状態へ / 違う → 新状態

状態の意味（完成形）

状態	Sequence ends in（末尾の意味）
S0	Reset（初期・特別な末尾なし）
S1	0（ただし 10 ではない）
S2	01
S3	10
S4	1（ただし 01 ではない）
S5	100

完成状態図（Mermaid）

検出ポイント（先にマーク）:

• S2 --0/1--> S3 … 末尾が 010 になった瞬間
• S5 --1/1--> S2 … 末尾が 1001 になった瞬間

stateDiagram-v2
    direction LR
    S0: S0 Reset
    S1: S1 ends 0
    S2: S2 ends 01
    S3: S3 ends 10
    S4: S4 ends 1
    S5: S5 ends 100

    S0 --> S1: 0/0
    S0 --> S4: 1/0

    S1 --> S1: 0/0
    S1 --> S2: 1/0

    S2 --> S3: 0/1
    S2 --> S4: 1/0

    S3 --> S5: 0/0
    S3 --> S2: 1/0

    S4 --> S3: 0/0
    S4 --> S4: 1/0

    S5 --> S1: 0/0
    S5 --> S2: 1/1

状態表

現在状態	次状態 (X=0)	次状態 (X=1)	Z (X=0)	Z (X=1)
S0	S1	S4	0	0
S1	S1	S2	0	0
S2	S3	S4	1	0
S3	S5	S2	0	0
S4	S3	S4	0	0
S5	S1	S2	0	1

なぜその遷移か（末尾の再利用）

今の状態	入力	列の末尾の変化	次状態	Z
S2（…01）	0	…010 → 検出。末尾は 10	S3	1
S2（…01）	1	…011 → 末尾は 1（01ではない）	S4	0
S3（…10）	1	…101 → 末尾は 01	S2	0
S3（…10）	0	…100 → 末尾は 100	S5	0
S5（…100）	1	…1001 → 検出。末尾は 01	S2	1
S5（…100）	0	…1000 → 末尾は 0	S1	0
S4（…1）	0	…10	S3	0
S1（…0）	0	…00 → まだ「0」	S1	0

部分図の段階での注:

• S3 の末尾は 10 → S3 で 1 が来たら S2（末尾 01）へ
• S4 で 0 → S3（末尾 10）
• S5 で 1 → 新状態は不要で S2 へ（末尾 01 と同じ）
• S5 で 0 → S1（末尾 0）

サンプルで Z を「見る」

X: 0 1 0        → 末尾 010
Z: 0 0 1

X: 1 0 0 1      → 末尾 1001
Z: 0 0 0 1

X: 0 1 0 0 1    （010 のあと続き）
     └──┘ で一度 Z=1。その後の並びも末尾条件で判定

トレース（010）:

状態	入力	矢印	Z	次
S0	0	0/0	0	S1
S1	1	1/0	0	S2
S2	0	0/1	1	S3

---

問題B（Moore）: 「1の総数が奇数」かつ「連続0が2つ以上あった」とき Z=1

1 の総数が奇数、かつ二つ以上連続する 0 が入力されている場合に 1 を出力する Moore machine（p.138）

系列1本ではなく、2種類の記憶を同時に持つ状態機械:

1. 1 の個数の偶奇（パリティ／mod 2 カウントに近い）
2. 連続 00 が既に起きたか、および「いま末尾が 0 か」（00 達成の途中）

→ カウンタ的な記憶 ＋ 系列検出的な記憶を、状態ラベルにまとめた例。

状態の意味

状態	意味	出力 Z
S0	Reset または even 1’s（00 未達成）	0
S1	Odd 1’s（00 未達成）	0
S2	Even 1’s and ends in 0（00 はまだ完成していない）	0
S3	Even 1’s and 00 has occurred	0
S4	Odd 1’s and 00 has occurred	1
S5	Odd 1’s and ends in 0（00 未達成）	0

• 左半分: Even 1’s 側（S0, S2, S3）
• 右半分: Odd 1’s 側（S1, S5, S4）
• Z=1 は S4 だけ（奇数個の1 かつ 00 達成済み）
• 「偶数個の1」と初期状態は、必要な情報が同じならまとめられる（S0）

組み立て（Figure 13-11 → 13-12 → 13-13）

1. S0（reset/even）と S1（odd 1’s）を作る（1 で往復）
2. 連続0の途中・達成を表す S2, S3 を追加
3. 出力1となる S4（odd かつ 00済み）を追加
4. 奇数側で末尾0の S5 を追加し、未記入の入力をすべて埋めて完成

完成状態図（Mermaid）

stateDiagram-v2
    direction LR

    state "Even 1's" as Even {
        S0: S0 / Z=0
        S2: S2 / Z=0
        S3: S3 / Z=0
    }
    state "Odd 1's" as Odd {
        S1: S1 / Z=0
        S5: S5 / Z=0
        S4: S4 / Z=1
    }

    S0 --> S1: 1
    S1 --> S0: 1
    S0 --> S2: 0
    S1 --> S5: 0
    S2 --> S3: 0
    S2 --> S1: 1
    S5 --> S4: 0
    S5 --> S0: 1
    S3 --> S3: 0
    S3 --> S4: 1
    S4 --> S4: 0
    S4 --> S3: 1

状態表（Moore: 出力列は1つ）

現在状態	次状態 (X=0)	次状態 (X=1)	出力 Z
S0	S2	S1	0
S1	S5	S0	0
S2	S3	S1	0
S3	S3	S4	0
S4	S4	S3	1
S5	S4	S0	0

遷移の直感

から	入力	何が起きるか	へ
S0	1	偶数→奇数	S1
S0	0	末尾0（00は未）	S2
S2	0	連続00達成（偶数のまま）	S3
S2	1	奇数へ（00未）	S1
S3	1	偶数→奇数、00済み → 出力1状態	S4
S4	0	奇数・00済みのまま	S4
S4	1	奇数→偶数、00済み	S3
S1	0	奇数で末尾0	S5
S5	0	奇数のまま00達成 → S4 (Z=1)	S4
S5	1	奇数→偶数	S0

サンプル

条件達成の例: 1 0 0（1が1個＝奇数、その後 00）

状態	入力	次	Z（Mooreは状態の出力）
S0	1	S1	0（S0にいた間）→ 遷移後 S1 も 0
S1	0	S5	0
S5	0	S4	遷移後 Z=1

Mealy と違い、Z=1 は「S4 に入ったあと」 状態に張り付く。

---

設計手順の共通パターン（13.2 で見えたこと）

1. サンプル入出力を自分で書いて問題文を固定する
2. 非ゼロ出力に至る 成功パスの部分グラフ から描く
3. 各状態で 未定義の入力を必ず埋める
4. 矢印を足すたび「既存状態で足りるか？ 新状態か？」
5. サンプル系列で Z が立つか検証

状態の意味は日本語1行で言えるようにしておく（末尾が何か／偶奇と00フラグなど）。

---

今日のまとめ

• Ch13 は 状態図・状態表の導出（設計）。回路式はその後。
• Mealy の a/b は 入力 a のとき出力 b。Z=1 は /1 の矢印。
• Moore の Z=1 は 状態そのもの。
• 13.2A: 二系列（010 or 1001）→ 末尾の種類を状態にしたもの。検出は S2 の 0/1 と S5 の 1/1。
• 13.2B: 偶奇 × 00達成 の組合わせ（カウンタ的＋系列的）。Z=1 は S4 のみ。
• 「遷移はわかるが出力が見えない」→ 先に検出ポイントをマークしてからトレース。

---