20260716_4


順序回路の設計手順

教科書 Morris Mano “Digital Design” Ch15 の設計手順(Design Procedure, p.167)を日本語でまとめる。

例として使うのは BCD→3増し符号変換器(Code Converter)。BCD(0〜9)を入力し、3を加えた excess-3 符号(3〜12)を出力する。入出力ともに LSB(最下位ビット)からシリアル に受け渡す。

各ステップの先頭に「何を(入力)→ どう操作して何が出るか(出力)」を書いたので、今やってる作業の位置を確認しながら読んでほしい。


全体の流れ

flowchart LR
    A["① 状態図/状態表"] --> B["② 状態削減"]
    B --> C["③ 2進数割当"]
    C --> D["④ 遷移表"]
    D --> E["⑤ 論理式導出(K-map)"]
    E --> F["⑥ 回路実現"]
    F --> G["⑦ 動作検証"]

① 状態図・状態表の導出

入力: 問題文(自然言語)
操作: 入力系列と出力系列の関係を読み取り、状態と遷移を抽出
出力: 状態図(グラフ)+ 状態表(テーブル)

この記号の意味
状態今までの入力をどこまで覚えているか
遷移次の入力でどうなるか
出力そのときに何を出すか

コツ

先に状態図を描く方がやりやすい。「入力が来たらどこに遷移するか」「そのとき何を出力するか」を時系列で追いながら描く。

Code Converter の入出力関係

時刻BCD入力 X(LSB first)excess-3出力 Z(LSB first)
t02^0(最下位ビット)2^0
t12^12^1
t22^22^2
t32^3(最上位ビット)2^3

例えば BCD=0101(5)なら excess-3=1000(8)。LSB first で送るとき:

  • t0: X=1 → Z=0
  • t1: X=0 → Z=0
  • t2: X=1 → Z=0
  • t3: X=0 → Z=1

この対応を満たすように状態を設計する。

状態図(全16状態)

図が大きいので、まず全体像をフローチャートで示す。時間は左→右に進む。

flowchart TD
    subgraph t0[t0 時刻目]
        A["A"] -->|"0/1"| B["B"]
        A -->|"1/0"| C["C"]
    end

    subgraph t1[t1 時刻目]
        B -->|"0/1"| D["D"]
        B -->|"1/0"| F["F"]
        C -->|"0/0"| E["E"]
        C -->|"1/1"| G["G"]
    end

    subgraph t2[t2 時刻目]
        D -->|"0/0"| H["H"]
        D -->|"1/1"| L["L"]
        E -->|"0/1"| I["I"]
        E -->|"1/0"| M["M"]
        F -->|"0/1"| J["J"]
        F -->|"1/0"| N["N"]
        G -->|"0/1"| K["K"]
        G -->|"1/0"| P["P"]
    end

    subgraph t3[t3 時刻目 → Aに戻る]
        H -->|"0/0, 1/1"| A
        I -->|"0/0, 1/1"| A
        J -.->|"0/0, 1/1 (dc)"| A
        K -.->|"0/0, 1/1 (dc)"| A
        L -.->|"0/0, 1/1 (dc)"| A
        M -->|"0/1, 1/0"| A
        N -.->|"0/1, 1/0 (dc)"| A
        P -.->|"0/1, 1/0 (dc)"| A
    end

Note

  • 実線(-->)は確定した遷移、点線(-.->)は don’t care(実際にはどっちでもいいが一応書いている)
  • 状態数16、遷移数32。各状態が「何ビット目を処理中か+そこまでの入力パターン」を表している
  • t3 の出力は、BCD が 0〜9 であることを前提に don’t care を含む(BCD は 1010〜1111 を使わないため)

対応する状態表(Table 15-2)

時刻現在状態次状態(X=0)次状態(X=1)Z(X=0)Z(X=1)
t0ABC10
t1BDF10
CEG01
t2DHL01
EIM10
FJN10
GKP10
t3HAA01
IAA01
JAA01
KAA01
LAA01
MAA10
NAA10
PAA10

なぜ状態図から状態表へ?

状態図は直感的だが、機械的に比較・削減するには表形式の方が扱いやすい。だから一旦表に書き直す。


② 状態数の削減

入力: 状態表(16状態)
操作: 行マッチング → 含意表
出力: 最小状態表(7状態)

なぜ削減するのか

状態数 m に対して必要なFFの数 n は 2^(n−1) < m ≤ 2^n。状態を1つでも減らせればFFが1個減るかもしれず、回路が小さく安く速くなる。

Step 1:行マッチング

行マッチングの操作はシンプルだ。
「次状態と出力が完全に同じ行を探して、1つにまとめる」

表を縦に見比べながら、同じ振る舞いをする行を探す。

まず I, J, K, L に注目:

状態次状態(X=0)次状態(X=1)Z(X=0)Z(X=1)
HAA01
IAA01
JAA01
KAA01
LAA01

→ 全部同じ! I, J, K, L は H に統合

次に N, P に注目:

状態次状態(X=0)次状態(X=1)Z(X=0)Z(X=1)
MAA10
NAA10
PAA10

→ これも全部同じ! N, P は M に統合

さらに F, G に注目:

状態次状態(X=0)次状態(X=1)Z(X=0)Z(X=1)
EI→HM10
FJ→HN→M10
GK→HP→M10

I→H, J→H, K→H, N→M, P→M に統合したあとで見ると、E・F・G の次状態のパターンが揃う。
→ F, G は E に統合

統合結果(Table 15-3:7状態)

状態次状態(X=0)次状態(X=1)Z(X=0)Z(X=1)
ABC10
BDF→E10
CEG→E01
DHL→H01
EHM10
HAA01
MAA10

統合元→統合先 の矢印で、削減の過程が追える。

flowchart LR
    I0[I] -.-> H1[H]
    J0[J] -.-> H1
    K0[K] -.-> H1
    L0[L] -.-> H1
    N0[N] -.-> M1[M]
    P0[P] -.-> M1
    F0[F] -.-> E1[E]
    G0[G] -.-> E1

Info

16状態 → 7状態。m=7 に対して n=3(2^2=4 < 7 ≤ 2^3=8)なので FFは3個


③ 2進数の割り当て(State Assignment)

入力: 最小状態表(7状態)
操作: 各状態にFFの値の組合せを割り当てる(隣接割当ガイドラインに従う)
出力: 状態コーディング一覧

ガイドライン(14.8節):

  1. 同じ次状態を持つ状態 → 隣接コードに
  2. 同じ入力で遷移する状態 → 隣接コードに
  3. 出力が同じ状態 → 隣接コードに

「よく一緒に現れる状態同士は近くに置く」

Code Converter の割当

グループ分けの根拠:

グループ状態理由
A, B, E, M出力Zのパターンが似ている、次状態のグループが同じ
C, D, H出力Zのパターンが似ている、次状態のグループが同じ
flowchart LR
    subgraph G1[グループ①]
        A --> B
        B --> E
        E --> M
    end
    subgraph G2[グループ②]
        C --> D
        D --> H
    end

割当結果(3ビット Q1 Q2 Q3):

状態Q1 Q2 Q3グループ
A0 0 0
B0 0 1
C0 1 0
D1 1 0
E0 1 1
H1 0 0
M1 1 1
未使用1 0 1

グループ①のコードを見ると…

A(000) → B(001) → E(011) → M(111) と 1ビットずつ変化している。
これが「隣接コード」の効果で、論理式が簡単になる理由でもある。


④ 遷移表の作成

入力: 状態コーディング一覧 + 最小状態表
操作: 状態名をQ1Q2Q3の値に置き換える(機械的置換)
出力: 遷移表

遷移表:

Q1 Q2 Q3状態名次状態(X=0)次状態(X=1)Z(X=0)Z(X=1)
0 0 0A001(B)010(C)10
0 0 1B110(D)011(E)10
0 1 0C011(E)011(E→G)01
1 1 0D100(H)100(H→L)01
0 1 1E100(H)111(M)10
1 0 0H000(A)000(A)01
1 1 1M000(A)000(A)10

Note

状態名から Q1Q2Q3 への置き換えは 機械的作業。ここではまだ論理式は出てこない。
単に「この状態が来たらこのコード」と置き換えているだけ。


⑤ 論理式の導出(K-map)

入力: 遷移表
操作: Q1⁺, Q2⁺, Q3⁺, Z のK-mapを書き、各マスの1をまとめる
出力: D1, D2, D3, Z の論理式

使うFFの種類で方針が変わる:

FFの種類Q⁺ と D/JKの関係難易度
D-FFQ⁺ = D(そのまま)★ 簡単
JK-FFQ⁺ から J と K の両方を決める★★ 普通
T-FFQ⁺ から T(トグル条件)を決める★★ 普通

Code Converter では D-FF を使用。

導出結果:

D1 = Q2'
D2 = Q1
D3 = Q1·Q2·Q3 + X'·Q1·Q3' + X·Q1'·Q2'
Z  = X'·Q3' + X·Q3

D1 = Q2’ と D2 = Q1 が異様に簡単なのは、隣接割り当ての賜物。
「グループ①で1ビットずつ変化」するようにコードを振った結果、D1 は単なるQ2の否定、D2 は単なるQ1の配線になった。


⑥ 論理回路の実現

入力: 論理式(D1, D2, D3, Z)
操作: 式をゲートで構成(必要に応じてNANDのみに変形)
出力: 回路図(or 回路そのもの)

実現方法の選択肢:

方式特徴
個別ゲート(AND, OR, NOT)自由度が高い、教科書的
NANDゲートのみIC化に適している(NANDは万能ゲート)
ROM / PLA小規模な順序回路向き

Code Converter の場合(NANDのみ):

元の形NANDのみ
D1Q2’Q2’(NOTはNANDの入力短絡で代用)
D2Q1ただの配線
D3Q1Q2Q3 + X’Q1Q3’ + XQ1’Q2’[(Q1Q2Q3)’ · (X’Q1Q3’)’ · (XQ1’Q2’)’]‘
ZX’Q3’ + XQ3[(X’Q3’)’ · (XQ3)’]’

Note

なぜ NAND だけにするか? → 実際のICでは AND + OR より NAND の方が実装しやすい。
式変形のテクニック:A + B = (A’ · B’)‘(ド・モルガンの法則)でAND-OR形式をNAND-NAND形式に変換する。


⑦ 動作検証

入力: 完成した回路
操作: 信号追跡・シミュレーション・実験室テスト
出力: 「正しく動く」という確証

3つの検証方法

方法内容
信号追跡(signal tracing)手または論理プローブで信号を1本ずつ確認
シミュレーションコンピュータ上でタイミング図を確認(図15-11)
実験室テスト実際にICやFPGAに焼いて動かす

テスト手順(p.172)

  1. FFの直接Set/Clear入力を使って、テストしたい状態に設定する
  2. 出力が正しいか確認する
    • Moore型:状態だけで出力が決まる → 状態を設定すれば出力を確認できる
    • Mealy型:状態+入力で出力が変わる → 各入力の組合せごとに出力確認が必要
  3. クロックを入れ、次状態が正しいか確認する
  4. 1〜3を 全状態で繰り返す

Note

テストは「全状態 × 全入力」の網羅が理想だが、状態数が多いと現実的ではない。
→ 現実的には代表的なパス(正常系+境界ケース)を選んでテストする。

伝搬遅延の考慮

順序回路のシミュレーションでは、ゲートやFFの**伝搬遅延(propagation delay)**を考慮する必要がある。遅延には3種類の値がある:

種類意味
標準遅延(nominal delay)通常動作時の典型的な遅延値(例:10ns)
最小遅延(minimum delay)最速で動作した場合(例:5ns)
最大遅延(maximum delay)最悪条件での遅延(例:15ns)

インバータ1個の遅延(図15-10):

  • 入力が変化してから、出力が確定するまでに時間がかかる
  • 実際のICでは温度・電圧・製造ばらつきで遅延が変わる → 最小/最大でシミュレーションしてマージンを確認する

シミュレーションの実例(図15-11, p.23)

教科書の図12-7(JK-FFを使った順序回路)を例に、シミュレーション画面の見方を確認する:

  1. スイッチ(switches) — 入力Xとクロックを手動で切り替えられる
  2. プローブ(probes) — 各信号(A, B, Zなど)の値が表示される
  3. クロックのシミュレーション — Clockスイッチを1→0に戻して1サイクル分の動作を確認

確認する式(図12-7の回路):

A⁺ = JA·A' + KA'·A = X·B·A' + X'·A
B⁺ = JB·B' + KB'·B = X·B' + X'·A'·B
Z  = X·B' + X·A + X'·A'·B (Mealy型)

グリッチとスパイク(図15-12, p.24)

シミュレーションで注意すべき現象。ゲートとFFに遅延があると、一瞬だけ誤った出力(glitch / spike)が現れることがある。

単位遅延モデル(図15-12a):

  • すべてのゲートの遅延を「1単位」と仮定する簡易モデル
  • おおよその動作はわかるが、実際の遅延は反映されない

標準遅延モデル(図15-12b):

  • 各ゲートに現実的な遅延(例:10ns)を割り当てる
  • より正確だが、グリッチが発生しやすくなる

対策:

  • Mealy型の出力はクロックのアクティブエッジ直前の値で判断する
  • アクティブエッジのタイミングではグリッチは既に収まっている(はず)
  • Moore型ならそもそもグリッチは発生しにくい(状態のみで出力が決まるため)

グリッチの見分け方

シミュレーションの波形で、一瞬(数ns)だけ出力が不定になったり0→1→0と変動する部分があったら、それはグリッチ。その瞬間の出力を「正しい出力」として読まないこと。クロックの立ち上がり/立ち下がりの直前の安定した値を読む。

シフトレジスタによる同期入力生成(図15-13, p.26)

テスト時に、入力系列をクロックに同期させて1ビットずつ送り込むには、シフトレジスタを使う。

テスト入力系列 → [シフトレジスタ] → 1ビットずつクロック同期で出力 → 被試験回路

仕組み:

  1. テストしたい入力パターン(例:BCD=0101をLSB firstで)をシフトレジスタにパラレルロード
  2. クロックごとに1ビットずつシフトして被試験回路へ送る
  3. 被試験回路の出力を観測する

これで「クロックに同期した正しいタイミング」で入力を与えられる。

同期回路(Synchronizer, 図15-14, 15-15, p.27-28)

順序回路のテストで厄介なのが、非同期入力の扱い。スイッチの手動操作など、クロックと無関係に変化する入力をそのままFFに入れると、セットアップ時間違反メタステーブルが起きる可能性がある。

1段D-FFによる同期化(図15-14)

非同期入力X → [D-FF(クロック同期)] → 同期化されたX'
  • クロックの立ち上がりエッジでXを取り込み、Xₛとして出力
  • ただしXの変化がセットアップ時間直後だと、FFが「0か1か確定しない」状態になることがある(メタステーブル

2段D-FFによる同期化(図15-15)← より安全

非同期入力X → [D-FF1] → Q₁ → [D-FF2] → 確定した同期出力Xₛ
  • 1段目のFFでメタステーブルが起きても、1クロック待つことでQ₁が確定する
  • 2段目のFFは確定したQ₁を取り込む → 確実に同期化できる
  • 代償:入力が反映されるまでに1クロックの遅延が生じる

なぜ必要なのか?

  • テスト中にスイッチを押すタイミングはクロックと無関係
  • 非同期入力をそのまま使うと予測不能な動作を引き起こす
  • 必ず同期回路を通してからFFに入れる

Tip

この2段FF同期化は、テスト時だけでなく実際の回路設計でも常套手段
異なるクロック領域間の信号受け渡しでは必ず使う。

反復回路(Iterative Circuits)との関係

反復回路と順序回路は表裏一体

空間方向に展開するか(反復回路)、時間方向に展開するか(順序回路) の違いでしかない。

flowchart LR
    subgraph Iter[反復回路=空間方向]
        direction LR
        C1[Cell 1] -->|信号を直接渡す| C2[Cell 2]
        C2 --> C3[Cell 3]
    end
    subgraph Seq[順序回路=時間方向]
        direction LR
        F1[FF 1] -->|クロックで読み出し| F2[FF 2]
        F2 --> F3[FF 3]
    end

そもそも反復回路とは

同一の組合せ回路(セル)を規則正しく並べ、セル間の信号を直接配線で隣へ渡す方式。桁上げのような「前の桁の計算結果を次の桁で使う」処理に適している。

例1:並列加算器(Parallel Adder, 図4-3)

構造: 全加算器(FA)を n 個並べただけ。各FAは xi, yi, ci(桁上げ入力)を受け取り、si(その桁の和)と ci+1(次の桁への桁上げ)を出力する。

flowchart LR
    subgraph FA0[FA0(最下位)]
        direction LR
        x0[x0] & y0[y0] --> FA0_core["全加算器"]
        c0["c0=0"] --> FA0_core
        FA0_core --> s0[s0]
        FA0_core --> c1[c1]
    end
    subgraph FA1[FA1]
        direction LR
        x1[x1] & y1[y1] --> FA1_core["全加算器"]
        FA1_core --> s1[s1]
        FA1_core --> c2[c2]
    end
    subgraph FA2[FA2]
        direction LR
        x2[x2] & y2[y2] --> FA2_core["全加算器"]
        FA2_core --> s2[s2]
        FA2_core --> c3[c3]
    end
    c1 --> FA1_core
    c2 --> FA2_core

ポイント: ci+1 が次のFAの ci に直結されている。これが反復回路の典型——セル間の信号(桁上げ)が配線で直接伝搬する。

速さの話: 桁上げがLSBからMSBまで伝搬するのに時間がかかる(桁上げ伝搬遅延)。ただし、4ビット加算器なら4個のFAを使うが、一度に全ビット計算できるのはメリット。

逐次加算器(Serial Adder, 図12-12)との対比

並列加算器と逐次加算器は同じ全加算器を使いながら、桁上げの扱いだけが違う

並列加算器(反復回路)逐次加算器(順序回路)
FAの数n個(ビット数と同じ)1個だけ
桁上げの伝搬配線で直接 → セル間を信号が走るD-FFに記憶 → 次のクロックで取り出す
速度1クロックで完了(ただし桁上げ伝搬に時間)nクロック必要
回路規模大きい(FA×n)小さい(FA×1+FF×1)
消費電力多い少ない

ユーザーの直感が正しい:

  • 「加算器をたくさん繋げて加算」→ 並列加算器(反復回路)
  • 「桁上げをうまく次回の入力につなげる」→ 逐次加算器(順序回路)

この2つは相互変換可能。逐次加算器のFFを取っ払って配線で直結すれば並列加算器になるし、並列加算器のセル間をFFで区切れば逐次加算器になる。これが教科書の言う「反復回路と順序回路は表裏一体」。

例2:比較器(Comparator, 図15-6〜15-9)

2つの n ビット2進数 X, Y を比較し、大小関係を判定する回路。

考え方: 上位の桁から順に見ていき、最初に異なるビットが現れた時点で大小が決まる(辞書順と同じ)。

セル1個の動作

各桁のセルは「上位ビットの比較結果」と「この桁の xi, yi」から、次のセルに渡す比較結果と最終判定出力を決める。

3状態(S0, S1, S2):

状態意味
S0上位を全部比較したけど、まだどちらとも言えない(X=Y)
S1上位で X>Y が確定した
S2上位で X<Y が確定した

状態遷移のルール:

現在の状態xi=yi(等しい)xi<yi(ここで負け)xi>yi(ここで勝ち)
S0(X=Y)次の桁にS0を渡すS2(X<Y確定)S1(X>Y確定)
S1(X>Y)S1のまま(確定は変わらない)S1のままS1のまま
S2(X<Y)S2のままS2のままS2のまま

→ つまり一度 X>Y か X<Y が確定したら、それ以降の桁では何が来ても状態は変わらない。

状態表(Table 15-4)

現状態xiyi=00011110出力
S0S0S2S0S1Z2(X=Y)
S1S1S1S1S1Z3(X>Y)
S2S2S2S2S2Z1(X<Y)

2ビット符号化と遷移表(Table 15-5)

S0=00, S1=01, S2=10 と割り当てる(11は未使用)。

現状態 (a,b) と入力 (xi,yi) から次状態 (a⁺,b⁺) が決まる:

a b00011110
0000100001
0101010101
1010101010

論理式の導出(p.171)

K-map を回すと、驚くほどシンプルな式になる:

a⁺ = a + x'·y·b'
b⁺ = b + x·y'·a'

出力:

Z1 = a'·b (X<Y)
Z2 = a'·b'(X=Y)
Z3 = a·b' (X>Y)

Note

出力の式は状態 (a,b) だけで決まる。つまり比較器のセルは本質的に Moore型

反復回路版の構成(図15-7, 15-8)

初期状態は a1=0, b1=0(S0:X=Y)。各セルで計算した a⁺, b⁺ を次のセルに直接渡す。最上位セルの出力が最終判定。

x1y1 → Cell1 → a2,b2 → Cell2 → a3,b3 → ... → Cell_n → Z1,Z2,Z3

順序回路版(図15-9)

全く同じ論理式を、D-FFの入力に使う。

flowchart LR
    subgraph SeqComp[順序回路版の比較器]
        direction LR
        X["xi, yi"] --> Logic["組合せ回路<br>a⁺=a+x'y b'<br>b⁺=b+xy' a'"]
        Logic --> FF["D-FF<br>(現在の状態 a,b)"]
        FF -->|"次クロックで更新"| Logic
        Logic --> Z["Z1,Z2,Z3"]
    end

FFからフィードバックがかかっているだけで、式は全く同じ。これが「反復回路と順序回路は表裏一体」の実体だ。

反復回路 vs 順序回路 まとめ

反復回路順序回路
実装セルを横に n 個並べるセル1個+FFで状態を保持
信号の流れセル間を直接配線FF→組合せ→FF(クロック同期)
メリット高速(1クロック)省ハードウェア(1セルでOK)
デメリットビット数に比例して回路増大nビットでnクロック必要
変換セル間をFFで区切れば順序回路にFFを取って配線すれば反復回路に

CADツールの活用

現代では設計の大部分をCADツールが自動化する:

  • 論理式の生成・最小化
  • PLDのビットパターン生成
  • 回路図取り込み(schematic capture)
  • シミュレーション
  • 論理合成(HDL → ゲートレベル)
  • テスト生成・IC設計・PC基板配線

中身の理解は必要

HDLで書けば自動合成される時代だが、合成結果の良し悪しを判断できるかどうかは、手計算の設計手順を理解しているかにかかっている。