20260709_4

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）→ 末尾の種類を状態にしたもの。
• 13.2B: 偶奇 × 00達成 の組合わせ（カウンタ的＋系列的）。
• 13.3: 状態図作成の手順（Guidelines）。Sliding vs Disjoint window。
• 13.4: シリアルデータ変換（NRZ→マンチェスタ）。
• 13.5: 複数入力の表記法 + 完全指定の性質（OR=1, AND=0）。
• 13.6: 不完全指定状態表。don’t care は状態簡約の素材料。
• 「遷移はわかるが出力が見えない」→ 先に検出ポイントをマークしてからトレース。

**

$$F\cdot F^{\prime }R=0,F\cdot F^{\prime }{R}^{\prime }=0,F^{\prime }R\cdot F^{\prime }{R}^{\prime }=0$$

→ 同じ入力で2つの矢印が同時に発火しない。重複がない。

入力4通りで表にすると一目瞭然

F	R	F	F’R	F’R’	該当矢印
0	0	0	0	1	③ だけ ✓
0	1	0	1	0	② だけ ✓
1	0	1	0	0	① だけ ✓
1	1	1	0	0	① だけ ✓

各行に「1」が ちょうど1つ → 完全指定 ✓

違反したらどうなるか

違反	起こること	回路への影響
OR ≠ 1（穴あり）	ある入力で遷移先がわからなくなる	MUX の入力が欠ける
AND ≠ 0（重複あり）	ある入力で2つの遷移先に迷う	MUX の入力が重複する

---

14---

13.3 Guidelines for Construction of State Graphs（状態図作成の手引き）

状態図をゼロから作るときの 手順書。

手順（6ステップ）

1. サンプル入出力を書く — 問題文を正確に理解する
2. リセット条件を決める — Sliding（オーバーラップ）or Disjoint（窗口ごとリセット）
3. 出力が1になる道（成功パス）だけ先に描く
4. 「何を覚えるか」で状態を決める — 末尾の段階ごとに状態
5. 矢印を追加するたびに「新状態か既存か」を判断
6. 検証 — 各状態から各入力への遷移が1本ずつあるか + サンプルで確認

Disjoint windows vs Sliding windows

	Sliding window	Disjoint window
別名	オーバーラップあり	オーバーラップなし
仕組み	1ビットずつずらして検出	Nビットごとにリセット
リセット	なし	窓口幅ごと
例	13.1〜13.2	13.4

---

13.4 Serial Data Code Conversion（シリアルデータ符号変換）

背景: シリアル通信の符号方式

符号	ルール	特徴
NRZ	0→0, 1→1	単純だがクロック回復が困難
NRZI	0→変化なし, 1→反転	クロック回復がやや容易
RZ	1→前半だけ1	クロック回復が容易だが帯域が広い
Manchester	0→01, 1→10	クロック＋データ同時伝送

NRZ → Manchester 変換（Mealy, Disjoint窗口）

3状態で設計。出力式: $Z=B+X{A}^{\prime }$

---

13.5 Alphanumeric State Graph Notation（複数入力の状態図表記法）

複数入力変数があるとき、0/1の代わりに 変数名 を矢印ラベルに使う。

Mealy版の表記法

$X_i{X}_j/Z_p{Z}_q$ — 入力 $X_i$ と $X_j$ が同時に1のとき出力 $Z_p$, $Z_q$ が1。

• -（ダッシュ）は don’t care
• 値が1の入出力ラベルだけ書く

完全指定の性質

• Property 1: OR = 1 — 穴がない（全カバー）
• Property 2: AND = 0 — 重複がない（排他）
• 両方成り立つ = 完全指定 = 各入力に対する遷移がちょうど1本

---

13.6 Incompletely Specified State Tables（不完全指定状態表）

入力系列に制約があるとき、don’t care（-）が生まれる。

• BCDパリティ検出器: 1010〜1111はBCDでない → don’t care
• Disjoint系列検出器: 1/2文字目の出力は不要 → don’t care

不完全指定の don’t care は 状態簡約（Ch14） で大幅に簡約できる素材。

---

Ch14 状態表の簡約と状態割当

14.1 Elimination of Redundant States（冗長状態の除去）

行マッチング

1行 = 1状態 の状態表において、「次状態と出力がすべて同じ行」を 探して統合する。

なぜこれで等価と言えるか

2つの状態 H と I が同じ行 = すべての入力で同じ動きをする = 外から見分けがつかない → H ≡ I（等価）。

やること

1. 状態表を見る
2. 行ごとに「次状態列＋出力列」を比較する
3. 完全に相同な行 → その状態は等価 → 1つにまとめ、他方を削除
4. 次状態の参照を書き換え
5. 書き換え後に また相同な行ができていないか 確認 → あればさらに統合

具体例

状態	次状態(X=0)	次状態(X=1)	Z(X=0)	Z(X=1)
F	H	I	0	0
G	H	I	0	0
H	A	A	0	0
I	A	A	0	0

• F と G が同列 → F ≡ G
• H と I が同列 → H ≡ I
• G → F に置き換え、I → H に置き換え

→ 冗長な状態を削除した結果、Ch13 の完成図（Fig.13-15）と同じになる。

---

14.2 Equivalent States（等価な状態）

定義

2つの状態 p と q が 等価（p ≡ q） とは、入力系列に対する出力系列がすべて同じ とき。

定理 14.1（等価の判定条件）

状態 p と q が等価 iff、すべての単一入力 X に対して:

$$\lambda (p,X)=\lambda (q,X)ext且つ\delta (p,X)\equiv \delta (q,X)$$

• $\lambda (p,X)$: 状態 p で入力 X のときの出力
• $\delta (p,X)$: 状態 p で入力 X のときの次状態

ポイント: 次状態は 等価であればいい（同一である必要はない）。

例: D ≡ G だが、次状態は H と N（同一でない）→ それでも等価（H ≡ N だから）

---

14.3 Implication Table（含意表）

行マッチングで見つからなかった等価な状態を 体系的に見つける 方法。

手順

1. 全状態対のマス表 を作る（横: a〜g、縦: b〜h）
2. 出力が異なる状態対 → に×をつける（不等価確定）
3. 出力が同じ状態対 → 次状態のペアをマスに記入（含意条件）
4. ×の連鎖: マス i-j に含意ペア m-n があるとき、m-n が×なら i-j も×
5. × が追加されなくなるまで繰り返す
6. × がないマス → その状態対は等価

なぜこれをやるか

行マッチングは「即座に相同な行」しか見つからない。
含意表は 「次状態が等価ならこの状態対も等価」 という連鎖を追える。

例: D と G が等価か？

• D の次状態: H(X=0), I(X=1)
• G の次状態: N(X=0), P(X=1)
• → 「H≡N かつ I≡P なら D≡G」（含意条件）
• H≡N, I≡P が確認されれば D≡G

---

今日のまとめ（Ch13 + Ch14）

Ch13:

• 状態図・状態表の導出（設計）
• Mealy: 矢印に 入力/出力、Moore: 状態に Z=
• 系列検出、複雑な設計、窗口の種類、シリアル変換、不完全指定

Ch14:

• 状態簡約 = 冗長な状態を削除する
• 行マッチング: 直接比較で相同行を統合（第1段階）
• 含意表: 次状態の等価連鎖を追って体系的に判定
• 等価の条件: すべての入力で出力が同じ かつ 次状態が等価