コンピュータの電源を切ると、作業中のデータは消えてしまいます。しかし電源が入っている間、CPUは何百億もの「0」と「1」を正確に記憶し、必要なタイミングで読み出しています。この「記憶する」という能力は、どこから生まれるのでしょうか。
電卓で「3 + 5」を計算する場面を想像してください。「3」を入力した後に「+」を押す時点で、電卓は「3」という値をどこかに覚えておかなければなりません。もし回路が「今この瞬間の入力」しか扱えないなら、過去に入力した「3」は消えてしまいます。つまり、まともな計算を行うには、回路に「記憶」の機能が必要です。この記憶を実現する最小単位がフリップフロップであり、フリップフロップを組み合わせて構成される回路が順序回路です。
フリップフロップと順序回路を理解すると、以下のような幅広い分野の基盤が見えてきます。
- コンピュータアーキテクチャ — CPU内部のレジスタ、プログラムカウンタ、パイプラインレジスタはすべてフリップフロップの集合体です。プロセッサがどのように命令を記憶し実行するかの根幹を理解できます
- FPGA・デジタルIC設計 — RTL（Register Transfer Level）設計では、データがレジスタ間をどのように転送されるかを記述します。フリップフロップのタイミング制約を理解しなければ、正しく動作するデジタル回路は設計できません
- 通信システム — 変復調回路のシンボル同期やフレーム同期には、シフトレジスタやカウンタが不可欠です
- 制御システム — デジタル制御器の内部状態は有限状態機械として設計され、フリップフロップで実装されます
本記事の内容
- 組合せ回路と順序回路の本質的な違い（記憶の有無）
- SRラッチの動作原理と禁止状態の問題
- Dフリップフロップ、JKフリップフロップ、Tフリップフロップの特性と使い分け
- セットアップ時間・ホールド時間とタイミング制約
- レジスタ（並列ロードレジスタ・シフトレジスタ）の構成
- カウンタ（同期カウンタ・非同期カウンタ）の設計
- 有限状態機械（ミーリ型・ムーア型）の理論
- 状態遷移図と状態遷移表の書き方
- Pythonによるカウンタと状態機械のシミュレーション
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- デジタル論理回路の基礎 — AND/OR/NOT ゲートの動作、ブール代数、組合せ回路の基本
組合せ回路と順序回路 — 「記憶」の有無が分水嶺
組合せ回路の限界
デジタル回路は、大きく組合せ回路と順序回路の2つに分類されます。この分類は、回路が「過去を覚えているか否か」で決まります。
組合せ回路（combinational circuit）は、現在の入力だけで出力が一意に決まる回路です。AND、OR、NOT ゲート、加算器、マルチプレクサなどが該当します。組合せ回路を数学的に表現すると、出力 $\bm{Y}$ は入力 $\bm{X}$ の関数です。
$$ \bm{Y} = f(\bm{X}) $$
同じ入力を与えれば、いつでも同じ出力が得られます。過去にどんな入力があったかは一切関係ありません。
しかし、これでは困る場面が多々あります。先ほどの電卓の例のように、「以前の入力を覚えておいて、後で使う」という操作ができません。信号機の制御でも、「今は赤だから次は青にする」という判断をするには、「今は赤である」という状態を記憶する仕組みが必要です。
順序回路 — 記憶を持つ回路
順序回路（sequential circuit）は、現在の入力に加えて、回路の内部状態（過去の入力の履歴を反映した情報）によって出力が決まる回路です。数学的に表現すると、出力 $\bm{Y}$ と次の状態 $\bm{S}_{n+1}$ は次のように書けます。
$$ \bm{Y} = g(\bm{X}, \bm{S}_n) $$
$$ \bm{S}_{n+1} = h(\bm{X}, \bm{S}_n) $$
ここで $\bm{S}_n$ は現在の内部状態、$\bm{X}$ は現在の入力です。出力関数 $g$ と次状態関数 $h$ の2つの関数によって、順序回路の振る舞いが完全に記述されます。
この内部状態 $\bm{S}$ を物理的に保持する素子がフリップフロップです。フリップフロップは1ビットの情報（0または1）を記憶でき、外部からの制御信号によってその値を更新します。フリップフロップがなければ順序回路は存在できません。逆に言えば、フリップフロップの動作を理解することが、順序回路の理解の鍵です。
順序回路はさらに、同期式と非同期式に分かれます。同期式順序回路はクロック信号に同期して状態が変化し、非同期式はクロックを使わず入力の変化に即座に反応します。現代のデジタルシステムのほとんどは同期式設計を採用しています。クロックに同期させることで、回路全体のタイミングを統一的に管理でき、設計と検証が格段に容易になるからです。
順序回路の基盤となるフリップフロップを理解するために、まずはその原型であるラッチから始めましょう。
SRラッチ — 記憶の最も原始的な形
フィードバックが記憶を生む
フリップフロップの原理を理解する鍵は、フィードバック（帰還）です。通常、論理ゲートの出力は前方にだけ流れます。しかし、出力を入力に戻すループを作ると、回路は「自分自身の出力を入力として使う」ことになり、状態を保持できるようになります。
日常のアナロジーで考えると、フィードバックによる記憶は「ドアのラッチ（掛け金）」に似ています。ドアのラッチは、一度掛けるとそのまま固定され、外部から操作しない限り状態が変わりません。回路のラッチも同じで、一度セットされた値は、リセット操作を行わない限り保持され続けます。これが「ラッチ」という名前の由来です。
NOR ゲートによるSRラッチ
SRラッチ（Set-Reset Latch）は、2つのNORゲートを交差結合（クロスカップル）した最も単純な記憶素子です。入力は $S$（Set：セット）と $R$（Reset：リセット）の2つ、出力は $Q$ と $\overline{Q}$（Qの補数）の2つです。
NOR ゲートの真理値表を思い出しましょう。NOR ゲートは「どちらの入力も0のときだけ1を出力する」ゲートです。
$$ \text{NOR}(a, b) = \overline{a + b} $$
SRラッチの2つのNORゲートの出力を、それぞれ $Q$ と $\overline{Q}$ とします。各ゲートの入力は次のように交差接続されます。
$$ Q = \overline{R + \overline{Q}} $$
同様に、もう一方の NOR ゲートの出力は次のようになります:
$$ \overline{Q} = \overline{S + Q} $$
この交差接続によって、一方の出力が他方の入力となるフィードバックループが形成されます。
SRラッチの動作
各入力の組み合わせに対する動作を見ていきましょう。
保持状態（$S=0, R=0$）: 両方の入力が0のとき、各NORゲートはもう一方の出力だけで出力が決まります。もし現在 $Q=1, \overline{Q}=0$ なら、$Q = \overline{0 + 0} = 1$、$\overline{Q} = \overline{0 + 1} = 0$ となり、状態が維持されます。逆に $Q=0, \overline{Q}=1$ でも同様に維持されます。つまり、$S=R=0$ では「何もしない」＝現在の状態を記憶し続けます。
セット（$S=1, R=0$）: $S=1$ を入力すると、$\overline{Q} = \overline{1 + Q} = 0$ となります。$\overline{Q}=0$ がもう一方のNORゲートに伝わり、$Q = \overline{0 + 0} = 1$ となります。結果として $Q=1$（セット状態）に確定します。
リセット（$S=0, R=1$）: $R=1$ を入力すると、$Q = \overline{1 + \overline{Q}} = 0$ となります。これがもう一方に伝わり、$\overline{Q} = \overline{0 + 0} = 1$ となります。結果として $Q=0$（リセット状態）に確定します。
禁止状態（$S=1, R=1$）: 両方を1にすると、$Q = \overline{1 + \overline{Q}} = 0$ かつ $\overline{Q} = \overline{1 + Q} = 0$ となり、$Q = \overline{Q} = 0$ という矛盾した状態に陥ります。$Q$ と $\overline{Q}$ は本来互いに補数であるべきなのに、どちらも0になってしまいます。さらに問題なのは、$S$ と $R$ を同時に0に戻したとき、どちらが先に0になるかという微妙なタイミングの差によって、$Q=0$ になるか $Q=1$ になるかが予測不能になることです。この不定性のため、$S=R=1$ は禁止入力と呼ばれます。
これを特性表にまとめると次のようになります。
| $S$ | $R$ | $Q_{n+1}$ | 動作 |
|---|---|---|---|
| 0 | 0 | $Q_n$ | 保持（記憶を維持） |
| 0 | 1 | 0 | リセット |
| 1 | 0 | 1 | セット |
| 1 | 1 | 不定 | 禁止（使用してはならない） |
SRラッチの特性方程式は、禁止入力 $S=R=1$ を除けば次のように書けます。
$$ Q_{n+1} = S + \overline{R} \cdot Q_n \quad (S \cdot R = 0 \text{ の条件下}) $$
この式は「$S=1$ ならセットされ、$R=0$ かつ前の状態が $Q_n$ なら保持される」ことを表しています。
SRラッチは記憶の基本原理を示してくれましたが、禁止状態という厄介な問題を抱えています。また、入力が変化した瞬間に出力が変わるレベルセンシティブな動作であり、クロック信号との同期が取れません。これらの問題を解決するために、フリップフロップが考案されました。まずは最も実用的な D フリップフロップから見ていきましょう。
Dフリップフロップ — 最も実用的な1ビット記憶素子
なぜSRラッチでは不十分なのか
SRラッチには2つの問題がありました。第一に、$S=R=1$ の禁止状態の存在。第二に、入力変化に即座に反応するレベルセンシティブな動作。実際のデジタルシステムでは、「クロック信号の特定のタイミングでだけ値を取り込む」というエッジトリガの動作が求められます。これにより、回路全体を統一されたタイミングで動かすことが可能になります。
Dフリップフロップ（Data Flip-Flop または Delay Flip-Flop）は、これらの問題を一挙に解決した、最も広く使われるフリップフロップです。
Dフリップフロップの動作原理
Dフリップフロップは、入力端子 $D$（Data）とクロック端子 $\text{CLK}$ を持ちます。動作は極めてシンプルで、「クロックの立ち上がりエッジ（0→1の遷移）の瞬間に、$D$ の値を $Q$ にコピーする」だけです。
$$ Q_{n+1} = D_n \quad \text{（クロックの立ち上がりエッジで更新）} $$
これ以上ないほど明快な特性方程式です。$D=1$ なら次のクロックエッジで $Q=1$ に、$D=0$ なら $Q=0$ になります。SRラッチのような禁止状態は存在しません。
| $D$ | $\text{CLK}$ | $Q_{n+1}$ | 動作 |
|---|---|---|---|
| 0 | $\uparrow$ | 0 | 0を記憶 |
| 1 | $\uparrow$ | 1 | 1を記憶 |
| X | それ以外 | $Q_n$ | 保持（変化なし） |
ここで $\uparrow$ はクロックの立ち上がりエッジを、$X$ は「0でも1でもよい（ドントケア）」を表します。
Dフリップフロップの内部構造
Dフリップフロップは、内部的にはマスター-スレーブ構成で実現されることが多いです。前段のマスターラッチがクロックのHighレベルで入力を取り込み、後段のスレーブラッチがクロックのLowレベルで（つまりクロックの立ち下がりエッジで）マスターの値を出力に転送します。この2段構成により、クロックエッジでのみ出力が変化するエッジトリガ動作が実現されます。
Dフリップフロップの考え方をもう少し直感的に表現すると、「写真を撮る」ようなものです。クロックの立ち上がりエッジは「シャッターが切られる瞬間」であり、その瞬間の $D$ の値が「写真」として $Q$ に記録されます。シャッターが切られるまで（次のクロックエッジまで）、どんなに $D$ が変化しても $Q$ は前の写真のまま動きません。
Dフリップフロップは単純明快で使いやすいですが、「セットとリセットを個別に制御したい」「トグル動作をさせたい」という要求には直接応えられません。こうした用途に対応するために、JKフリップフロップとTフリップフロップが考案されました。
JKフリップフロップ — SRの問題を解消した万能型
SRラッチの禁止状態を活用する
JKフリップフロップは、SRラッチの禁止入力（$S=R=1$）の問題を逆転の発想で解決した設計です。SRラッチでは $S=R=1$ を「禁止」としていましたが、JKフリップフロップではこの入力に「トグル（反転）」という有用な機能を割り当てました。
JKフリップフロップの入力は $J$（SRラッチの $S$ に対応）と $K$（$R$ に対応）です。$J=K=1$ のとき、出力は現在の値の反転になります。つまり $Q=0$ なら $Q=1$ に、$Q=1$ なら $Q=0$ に切り替わります。
特性表と特性方程式
| $J$ | $K$ | $Q_{n+1}$ | 動作 |
|---|---|---|---|
| 0 | 0 | $Q_n$ | 保持 |
| 0 | 1 | 0 | リセット |
| 1 | 0 | 1 | セット |
| 1 | 1 | $\overline{Q_n}$ | トグル（反転） |
この特性表から、カルノー図を使って特性方程式を導出しましょう。$J$ と $K$ の2変数に加えて、現在の状態 $Q_n$ も変数として扱います。
$Q_{n+1}$ のカルノー図を描くと、$J=0, K=0$ なら $Q_{n+1} = Q_n$、$J=0, K=1$ なら $Q_{n+1} = 0$、$J=1, K=0$ なら $Q_{n+1} = 1$、$J=1, K=1$ なら $Q_{n+1} = \overline{Q_n}$ です。
これを $Q_n$ の値で場合分けすると、$Q_n = 0$ のとき $Q_{n+1}$ は $J$ の値と一致し、$Q_n = 1$ のとき $Q_{n+1}$ は $\overline{K}$ の値と一致することがわかります。
したがって、特性方程式は次のようになります。
$$ Q_{n+1} = J \cdot \overline{Q_n} + \overline{K} \cdot Q_n $$
この式を読み解くと、「$J=1$ で現在0なら1になる（セット）」かつ「$K=0$ で現在1ならそのまま（保持）」という動作が自然に表現されています。
JKフリップフロップの汎用性
JKフリップフロップが「万能型」と呼ばれるのは、他のフリップフロップの機能をすべて再現できるからです。
- Dフリップフロップとして: $J = D$、$K = \overline{D}$ と接続すれば、$Q_{n+1} = D \cdot \overline{Q_n} + D \cdot Q_n = D$ となり、Dフリップフロップの動作になります
- Tフリップフロップとして: $J = K = T$ と接続すれば、$T=1$ でトグル、$T=0$ で保持の動作になります
- SRフリップフロップとして: $J = S$、$K = R$ で $S \cdot R = 0$ の制約下で使えば、SRフリップフロップと同じ動作です
この汎用性は回路設計の柔軟性を高めますが、現代のデジタル設計ではDフリップフロップが主流です。その理由は、Dフリップフロップが合成ツール（論理合成ソフトウェア）と相性が良く、タイミング解析もシンプルになるためです。JKフリップフロップの知識は、カウンタの設計や既存回路の理解において依然として重要です。
次に、JKフリップフロップの特殊なケースであり、カウンタの基本構成要素となるTフリップフロップを見ていきましょう。
Tフリップフロップ — カウンタの基本構成要素
トグル動作の直感
Tフリップフロップ（Toggle Flip-Flop）は、入力が $T$ の1つだけという最もシンプルなフリップフロップです。$T=1$ のとき出力が反転（トグル）し、$T=0$ のとき出力が保持されます。
日常的なアナロジーとして、壁のスイッチを思い浮かべてください。スイッチを1回押すと照明が点き、もう1回押すと消えます。「押す」という同一の操作が、現在の状態によってON/OFFを切り替えます。Tフリップフロップはまさにこの動作をデジタル回路で実現しています。
特性表と特性方程式
| $T$ | $Q_{n+1}$ | 動作 |
|---|---|---|
| 0 | $Q_n$ | 保持 |
| 1 | $\overline{Q_n}$ | トグル（反転） |
特性方程式は次の通りです。
$$ Q_{n+1} = T \oplus Q_n = T \cdot \overline{Q_n} + \overline{T} \cdot Q_n $$
ここで $\oplus$ はXOR（排他的論理和）演算です。この式は「$T$ と $Q_n$ が異なるとき $Q_{n+1} = 1$、同じとき $Q_{n+1} = 0$」を表しており、$T=1$ のときちょうど $Q_n$ が反転することがわかります。
TフリップフロップをDフリップフロップから構成する
Tフリップフロップは、Dフリップフロップの $D$ 入力に $T \oplus Q$ を接続するだけで実現できます。
$$ D = T \oplus Q $$
$T=1$ のとき $D = \overline{Q}$ となるので、次のクロックエッジで $Q$ が反転します。$T=0$ のとき $D = Q$ となるので、$Q$ が保持されます。
Tフリップフロップの重要な応用は分周器です。$T=1$ に固定すると、毎クロックエッジで出力が反転するので、出力の周波数は入力クロックの $1/2$ になります。これをn段直列に接続すれば $1/2^n$ の分周器が構成でき、カウンタの基本原理に直結します。
ここまで4種類の記憶素子（SRラッチ、Dフリップフロップ、JKフリップフロップ、Tフリップフロップ）の動作を学びました。実際のデジタル回路でフリップフロップを正しく動作させるためには、タイミングに関する重要な制約を理解する必要があります。
セットアップ時間とホールド時間 — タイミング制約の物理
なぜタイミングが重要なのか
フリップフロップの特性表を見ると、クロックの立ち上がりエッジの「瞬間」に $D$ の値を取り込むと説明しました。しかし現実の物理回路では、「瞬間」は文字通りのゼロ時間ではありません。フリップフロップ内部のトランジスタが正しく動作するためには、データ入力 $D$ がクロックエッジの前後で一定時間安定している必要があります。
これは「写真撮影」のアナロジーで理解できます。写真のシャッターが切られる瞬間に被写体が動いていると、写真はブレてしまいます。鮮明な写真を撮るには、シャッターが切られる少し前から少し後まで被写体が静止している必要があります。フリップフロップにおけるタイミング制約も、これとまったく同じ原理です。
セットアップ時間 $t_{su}$
セットアップ時間（setup time）$t_{su}$ は、クロックの有効エッジ（立ち上がりエッジ）の前に、データ入力 $D$ が安定していなければならない最小時間です。
$$ t_{su} = t_{\text{CLK}} – t_{\text{D stable}} $$
ここで $t_{\text{CLK}}$ はクロックエッジの時刻、$t_{\text{D stable}}$ はデータが安定した時刻です。$D$ がクロックエッジの直前 $t_{su}$ 以内に変化すると、フリップフロップは正しい値を取り込めず、メタステーブル状態（0でも1でもない不安定な中間状態）に陥る可能性があります。
ホールド時間 $t_h$
ホールド時間（hold time）$t_h$ は、クロックの有効エッジの後に、データ入力 $D$ が安定し続けていなければならない最小時間です。
セットアップ時間が「シャッターを切る前にじっとしていてください」なら、ホールド時間は「シャッターを切った直後もまだ動かないでください」に相当します。
タイミング制約の数式
クロック周期を $T_{\text{clk}}$ とすると、正しい同期動作のためには次の不等式を満たす必要があります。
組合せ回路の伝搬遅延を $t_{pd,\text{comb}}$、フリップフロップのクロックから出力までの遅延を $t_{pd,\text{FF}}$ とすると、セットアップ制約は次のように書けます。
$$ t_{pd,\text{FF}} + t_{pd,\text{comb}} + t_{su} \leq T_{\text{clk}} $$
この不等式は「フリップフロップの出力が確定し、組合せ回路を伝搬し、次段のフリップフロップのセットアップ時間を満たすまでに、1クロック周期以内に収まらなければならない」ことを意味しています。
この式を $T_{\text{clk}}$ について解くと、動作可能な最大クロック周波数が求まります。
$$ f_{\text{max}} = \frac{1}{T_{\text{clk,min}}} = \frac{1}{t_{pd,\text{FF}} + t_{pd,\text{comb}} + t_{su}} $$
これが回路の最大動作周波数であり、CPUのクロック周波数の上限を決める本質的な要因です。プロセッサの高速化とは、突き詰めればこの式の右辺の各項を小さくする（トランジスタを小さく・高速にする、組合せ回路の段数を減らす）ことに他なりません。
ホールド制約は次のように表されます。
$$ t_{pd,\text{FF}} + t_{pd,\text{comb}} \geq t_h $$
これは「データが次段のフリップフロップに到達するまでの時間が、ホールド時間よりも長くなければならない」ことを意味します。ホールド違反はクロック周波数を下げても解決できない点が厄介で、回路のレイアウト段階でバッファ挿入などの物理的対策が必要になります。
タイミング制約を理解したところで、フリップフロップを複数個組み合わせた実用的な回路を見ていきましょう。まずは、複数ビットのデータを一括して記憶するレジスタです。
レジスタ — 複数ビットを一括管理する
並列ロードレジスタ
レジスタ（register）は、複数のフリップフロップを束ねて $n$ ビットのデータを同時に記憶する回路です。最も基本的な $n$ ビット並列ロードレジスタは、$n$ 個のDフリップフロップを並列に配置し、共通のクロック信号で駆動します。
$$ Q_i^{(n+1)} = D_i \quad (i = 0, 1, \dots, n-1) $$
各ビット $i$ が独立にDフリップフロップの動作をしますが、クロック信号が共通なので、全ビットが同時に更新されます。CPUの汎用レジスタ（x86の EAX, EBX 等）やプログラムカウンタは、まさにこの並列ロードレジスタの構造です。
実用的なレジスタには通常、ロードイネーブル（load enable）信号 $LE$ が追加されます。$LE=1$ のときだけ新しいデータを取り込み、$LE=0$ のときは現在の値を保持します。これは各Dフリップフロップの入力にマルチプレクサを追加することで実現されます。
$$ D_i = \begin{cases} \text{Input}_i & \text{if } LE = 1 \\ Q_i & \text{if } LE = 0 \end{cases} $$
シフトレジスタ — データを直列に移動させる
シフトレジスタ（shift register）は、フリップフロップを直列に接続し、データが1クロックごとに1ビットずつ隣のフリップフロップへ移動する回路です。$n$ ビットの右シフトレジスタでは、各フリップフロップの入力が左隣のフリップフロップの出力に接続されます。
$$ Q_i^{(n+1)} = Q_{i+1}^{(n)} \quad (i = 0, 1, \dots, n-2) $$
$$ Q_{n-1}^{(n+1)} = D_{\text{in}} \quad \text{（シリアル入力）} $$
シフトレジスタは様々な応用を持ちます。
直列-並列変換（Serial-to-Parallel Converter）: 通信回線から1ビットずつ届くデータを $n$ クロックかけてシフトレジスタに取り込み、$n$ ビット揃った時点で並列に読み出します。UART（Universal Asynchronous Receiver/Transmitter）の受信部はまさにこの仕組みです。
並列-直列変換（Parallel-to-Serial Converter）: 逆に、$n$ ビットのデータを並列にロードし、1ビットずつシフトして直列出力します。UARTの送信部がこれに該当します。
巡回シフト（ローテーション）: シフトレジスタの出力を入力に戻すことで、データが環状に循環する巡回シフトレジスタ（リングカウンタ）が構成できます。
線形帰還シフトレジスタ（LFSR）: 特定のビット位置のXORをフィードバック入力とすることで、疑似乱数生成やCRC（巡回冗長検査）の計算に使われるLFSRが構成できます。
レジスタはデータの「保存」と「移動」を担いますが、「数を数える」という動作にはもう一工夫必要です。次は、フリップフロップで数を数えるカウンタの設計を見ていきましょう。
カウンタ — フリップフロップで数を数える
カウンタの基本原理
カウンタ（counter）は、クロックパルスを入力するたびに内部の値が1ずつ増加（または減少）する順序回路です。$n$ ビットカウンタは $0$ から $2^n – 1$ までの値を巡回的に数え上げます。
カウンタの動作を数式で表すと次のようになります。
$$ \text{Count}_{n+1} = (\text{Count}_n + 1) \mod 2^n $$
カウンタはクロック分周器、タイマー、アドレス生成器、シーケンサなど、デジタルシステムのあらゆる場所で使われます。カウンタの設計方法には非同期カウンタと同期カウンタの2つのアプローチがあります。
非同期カウンタ（リプルカウンタ）
非同期カウンタは、最も直感的なカウンタの実現方法です。Tフリップフロップ（$T=1$ 固定）を直列に接続し、各段の出力を次段のクロック入力に接続します。
2進数のカウントアップを考えてみましょう。$000 \to 001 \to 010 \to 011 \to 100 \to \dots$ と進むとき、最下位ビット（LSB）は毎回反転します。2番目のビットはLSBが $1 \to 0$ に変わるとき（つまりLSBの立ち下がりエッジで）反転します。3番目のビットは2番目が $1 \to 0$ に変わるとき反転します。
この規則性に着目すれば、各段のTフリップフロップの $Q$ 出力を次段のクロック入力に接続するだけで、自然にカウンタが構成できます。
非同期カウンタの利点は構造が単純なことですが、重大な欠点があります。各段のフリップフロップの遅延が累積するため、上位ビットの出力が確定するまでに時間がかかります。$n$ ビットの非同期カウンタでは、最上位ビットの確定に最大 $n \cdot t_{pd}$ の遅延が生じます。この累積遅延のため、遷移途中に一時的に誤った値が出力されるグリッチ（glitch）が発生することがあります。たとえば $0111 \to 1000$ への遷移では、各ビットが順次変化するため、一時的に $0110$、$0100$、$0000$ などの中間値が現れる可能性があります。
同期カウンタ
同期カウンタは、全てのフリップフロップに同一のクロック信号を供給し、各段の $T$ 入力を組合せ論理で制御する方式です。全ビットが同時に更新されるため、非同期カウンタのグリッチ問題が解消されます。
$n$ ビット同期バイナリカウンタの設計を考えましょう。ビット $i$ が反転すべき条件は「ビット $0$ からビット $i-1$ までがすべて $1$ であること」です。これは次の論理式で表されます。
$$ T_i = \prod_{k=0}^{i-1} Q_k = Q_0 \cdot Q_1 \cdot \cdots \cdot Q_{i-1} $$
$$ T_0 = 1 \quad \text{（LSBは常に反転）} $$
たとえば4ビット同期カウンタでは次のようになります。
$$ T_0 = 1 $$
ビット1は、ビット0が1のときに反転します:
$$ T_1 = Q_0 $$
ビット2は、下位2ビットがともに1のときに反転します:
$$ T_2 = Q_0 \cdot Q_1 $$
同様に、ビット3は下位3ビットがすべて1のときに反転します:
$$ T_3 = Q_0 \cdot Q_1 \cdot Q_2 $$
同期カウンタの遅延は、フリップフロップの遅延 $t_{pd,\text{FF}}$ に AND ゲートの遅延を加えただけで済み、ビット数に依存しません（キャリールックアヘッド方式を用いた場合）。このため、高速動作が求められる用途では同期カウンタが標準です。
カウンタは「決まったパターンで値が変化する」特殊な順序回路ですが、一般的な順序回路は「任意の状態間を入力に応じて遷移する」能力を持ちます。この一般的な枠組みが有限状態機械です。
有限状態機械 — 任意の順序動作を設計する
有限状態機械とは
有限状態機械（Finite State Machine, FSM）は、順序回路を設計するための一般的で強力な枠組みです。FSMは以下の5つの要素で定義されます。
$$ \text{FSM} = (S, I, O, \delta, \lambda) $$
各要素の意味は次の通りです。
- $S = \{s_0, s_1, \dots, s_{m-1}\}$: 状態の有限集合。$m$ 個の状態があり、$\lceil \log_2 m \rceil$ ビットのフリップフロップで符号化されます
- $I$: 入力アルファベット。入力信号の取りうる値の集合
- $O$: 出力アルファベット。出力信号の取りうる値の集合
- $\delta: S \times I \to S$: 状態遷移関数。現在の状態と入力から次の状態を決定します
- $\lambda$: 出力関数。出力の決まり方によってFSMの型が分かれます
FSMを直感的に理解するには、自動販売機を考えるとよいでしょう。自動販売機は「投入金額」という内部状態を持ち、コインが投入されるたびに状態が変わります。投入金額が商品価格に達すると「商品排出」という出力を生じ、初期状態に戻ります。これはまさにFSMの動作です。
ミーリ型とムーア型
FSMは出力関数 $\lambda$ の定義によって、ムーア型とミーリ型の2つに分類されます。
ムーア型（Moore Machine）では、出力は現在の状態のみに依存します。
$$ \lambda_{\text{Moore}}: S \to O $$
$$ \text{出力} = \lambda(S_n) $$
ムーア型の出力は状態が変わるまで安定しています。信号機はムーア型の典型例で、「赤状態」なら赤が点灯、「青状態」なら青が点灯というように、状態だけで出力が決まります。現在の入力（車両感知センサの値など）は次の状態に影響しますが、出力には直接影響しません。
ミーリ型（Mealy Machine）では、出力は現在の状態と現在の入力の両方に依存します。
$$ \lambda_{\text{Mealy}}: S \times I \to O $$
$$ \text{出力} = \lambda(S_n, X_n) $$
ミーリ型は入力の変化に即座に反応できるため、同じ機能をムーア型より少ない状態数で実現できることが多いです。ただし、入力のグリッチが出力に伝搬するリスクがあるため、出力をフリップフロップで再同期化（リタイミング）する場合もあります。
ムーア型とミーリ型の比較
| 特性 | ムーア型 | ミーリ型 |
|---|---|---|
| 出力の決定要因 | 状態のみ | 状態 + 入力 |
| 出力の安定性 | クロック間で安定 | 入力変化で変動しうる |
| 状態数 | 多め | 少なめ |
| 応答速度 | 1クロック遅れ | 即座（同一クロック内） |
| 出力のグリッチ | なし | あり得る |
| 設計の容易さ | 直感的 | やや複雑 |
ムーア型とミーリ型は理論的に等価であり、一方で実現できるものは他方でも必ず実現できます。ただしムーア型に変換すると状態数が増える場合があります。実際の設計では、出力のタイミング要件やグリッチの許容度に応じて使い分けます。
FSMの設計を具体的に行うには、状態遷移図と状態遷移表という2つの表現手法が欠かせません。次はこれらの設計ツールを詳しく見ていきましょう。
状態遷移図と状態遷移表 — FSMの設計ツール
状態遷移図
状態遷移図（State Transition Diagram, STD）は、FSMの動作をグラフィカルに表現したものです。丸（ノード）が状態を、矢印（エッジ）が遷移を表します。
ムーア型の状態遷移図では、各状態ノードの中に「状態名 / 出力」を記載し、矢印のラベルには遷移の条件（入力値）だけを書きます。ミーリ型では、矢印のラベルに「入力 / 出力」を記載します。
具体例として、「1を3回連続で検出する」パターン検出器をムーア型で設計してみましょう。
- S0: 初期状態（出力: 0） — 「1」がまだ連続していない
- S1: 「1」が1回来た（出力: 0）
- S2: 「1」が2回連続した（出力: 0）
- S3: 「1」が3回連続した（出力: 1） — パターン検出！
状態遷移は次のようになります。
- S0 で入力0 → S0、入力1 → S1
- S1 で入力0 → S0、入力1 → S2
- S2 で入力0 → S0、入力1 → S3
- S3 で入力0 → S0、入力1 → S3（3回以上の連続も検出し続ける）
状態遷移表
状態遷移図を表形式で整理したものが状態遷移表（State Transition Table）です。FSMの完全な仕様を明確に記述でき、回路の論理式導出の基盤となります。
上記のパターン検出器の状態遷移表は次のようになります。
| 現在の状態 | 入力 $X$ | 次の状態 | 出力 $Y$（ムーア型） |
|---|---|---|---|
| S0 | 0 | S0 | 0 |
| S0 | 1 | S1 | 0 |
| S1 | 0 | S0 | 0 |
| S1 | 1 | S2 | 0 |
| S2 | 0 | S0 | 0 |
| S2 | 1 | S3 | 0 |
| S3 | 0 | S0 | 1 |
| S3 | 1 | S3 | 1 |
状態の符号化
状態遷移表が完成したら、各状態を2進数で符号化します。4状態なら2ビット（2つのフリップフロップ）で表現できます。
$$ S0 = 00, \quad S1 = 01, \quad S2 = 10, \quad S3 = 11 $$
符号化後、状態変数を $Q_1 Q_0$ として、次の状態 $Q_1^+ Q_0^+$ と出力 $Y$ を入力 $X$ と現在の状態の関数として求めます。
$Q_0^+$ について、状態遷移表を $X, Q_1, Q_0$ の3変数のカルノー図に展開すると次のようになります。
$$ Q_0^+ = X \cdot \overline{Q_1} \cdot \overline{Q_0} + X \cdot Q_1 \cdot Q_0 $$
$Q_1^+$ についても同様に求めると次のようになります。
$$ Q_1^+ = X \cdot Q_0 $$
出力 $Y$ は次のようになります。
$$ Y = Q_1 \cdot Q_0 $$
これらの論理式をAND/ORゲートとDフリップフロップで実装すれば、パターン検出器の回路が完成します。
ここまでの理論をPythonで実際にシミュレーションして、動作を確認していきましょう。
Pythonでの実装 — カウンタと状態機械のシミュレーション
フリップフロップの基本クラス
まず、各種フリップフロップの動作をPythonのクラスで表現します。これにより、特性表で学んだ動作が実際にコード上で再現されることを確認できます。
import numpy as np
import matplotlib.pyplot as plt
class DFlipFlop:
"""Dフリップフロップ: クロック立ち上がりエッジでDの値を取り込む"""
def __init__(self):
self.q = 0
def clock(self, d):
self.q = d
return self.q
class JKFlipFlop:
"""JKフリップフロップ: J=K=1でトグル"""
def __init__(self):
self.q = 0
def clock(self, j, k):
if j == 0 and k == 0:
pass # 保持
elif j == 0 and k == 1:
self.q = 0 # リセット
elif j == 1 and k == 0:
self.q = 1 # セット
else: # j == 1, k == 1
self.q = 1 - self.q # トグル
return self.q
class TFlipFlop:
"""Tフリップフロップ: T=1でトグル"""
def __init__(self):
self.q = 0
def clock(self, t):
if t == 1:
self.q = 1 - self.q # トグル
return self.q
# 各フリップフロップの動作確認
print("=== Dフリップフロップの動作 ===")
dff = DFlipFlop()
d_inputs = [0, 1, 1, 0, 1, 0, 0, 1]
print(f"D入力: {d_inputs}")
d_outputs = [dff.clock(d) for d in d_inputs]
print(f"Q出力: {d_outputs}")
print("\n=== JKフリップフロップの動作 ===")
jkff = JKFlipFlop()
jk_inputs = [(0,0), (1,0), (0,0), (1,1), (1,1), (0,1), (0,0), (1,0)]
print(f"J,K入力: {jk_inputs}")
jk_outputs = [jkff.clock(j, k) for j, k in jk_inputs]
print(f"Q出力: {jk_outputs}")
print("\n=== Tフリップフロップの動作 ===")
tff = TFlipFlop()
t_inputs = [1, 1, 0, 1, 1, 1, 0, 1]
print(f"T入力: {t_inputs}")
t_outputs = [tff.clock(t) for t in t_inputs]
print(f"Q出力: {t_outputs}")
このコードでは、3種類のフリップフロップに対して入力シーケンスを与え、出力の変化を追跡しています。Dフリップフロップは入力をそのまま出力にコピーし、JKフリップフロップは $J=K=1$ でトグルし、Tフリップフロップは $T=1$ で反転する動作が確認できます。特にJKフリップフロップの $(1,1)$ 入力が2回連続する箇所では、出力が $1 \to 0 \to 1$ とトグルする様子が見て取れます。
フリップフロップのタイミング波形の可視化
フリップフロップの動作を波形として可視化することで、クロックとデータの時間的関係が直感的に理解できます。
import numpy as np
import matplotlib.pyplot as plt
# Dフリップフロップのタイミングシミュレーション
n_cycles = 10
d_input_seq = [0, 1, 1, 0, 1, 0, 0, 1, 1, 0]
# 波形データの生成（各クロックサイクルを細分化）
steps_per_cycle = 100
total_steps = n_cycles * steps_per_cycle
t = np.linspace(0, n_cycles, total_steps)
# クロック信号（50%デューティ比）
clk = np.zeros(total_steps)
for i in range(total_steps):
cycle_pos = (i % steps_per_cycle) / steps_per_cycle
clk[i] = 1 if cycle_pos < 0.5 else 0
# D入力信号（クロックサイクルの途中で変化させて現実感を出す）
d_signal = np.zeros(total_steps)
for i in range(n_cycles):
start = int((i + 0.2) * steps_per_cycle) # サイクルの20%地点で変化
end = int((i + 1.2) * steps_per_cycle) if i < n_cycles - 1 else total_steps
d_signal[start:min(end, total_steps)] = d_input_seq[i]
# Q出力信号（立ち上がりエッジで取り込み）
q_signal = np.zeros(total_steps)
q_val = 0
for i in range(1, total_steps):
# 立ち上がりエッジの検出
if clk[i] == 1 and clk[i-1] == 0:
q_val = d_signal[i]
q_signal[i] = q_val
# 波形プロット
fig, axes = plt.subplots(3, 1, figsize=(12, 6), sharex=True)
fig.suptitle('D Flip-Flop Timing Diagram', fontsize=14, fontweight='bold')
signals = [('CLK', clk, '#4fc3f7'), ('D', d_signal, '#81c784'), ('Q', q_signal, '#ff8a65')]
for ax, (name, sig, color) in zip(axes, signals):
ax.plot(t, sig, color=color, linewidth=2)
ax.fill_between(t, sig, alpha=0.2, color=color)
ax.set_ylabel(name, fontsize=12, fontweight='bold')
ax.set_ylim(-0.2, 1.4)
ax.set_yticks([0, 1])
ax.grid(True, alpha=0.3)
ax.axhline(y=0, color='gray', linewidth=0.5)
ax.axhline(y=1, color='gray', linewidth=0.5)
# クロックの立ち上がりエッジに縦線を追加
for i in range(n_cycles):
for ax in axes:
ax.axvline(x=i + 0.001, color='red', linewidth=0.5, alpha=0.5, linestyle='--')
axes[-1].set_xlabel('Clock Cycles', fontsize=12)
plt.tight_layout()
plt.savefig('d_flip_flop_timing.png', dpi=150, bbox_inches='tight')
plt.show()
このタイミング波形図からいくつかの重要な特徴が読み取れます。第一に、Q出力はクロックの立ち上がりエッジ（赤い破線）でのみ変化しており、エッジトリガ動作が確認できます。第二に、D入力がクロックサイクルの途中で変化しても、Q出力には影響しません。これがまさに「写真のシャッター」の動作です。第三に、Q出力はD入力に対して必ず1クロック遅れて追従しており、Dフリップフロップの「Delay（遅延）」という別名の由来がここに見て取れます。
同期カウンタのシミュレーション
4ビット同期バイナリカウンタをシミュレーションし、各ビットの波形を観察します。
import numpy as np
import matplotlib.pyplot as plt
class SyncBinaryCounter:
"""4ビット同期バイナリカウンタ"""
def __init__(self, n_bits=4):
self.n_bits = n_bits
self.ffs = [TFlipFlop() for _ in range(n_bits)]
self.history = []
def clock(self):
# T入力の計算: T_i = Q_0 * Q_1 * ... * Q_{i-1}
t_inputs = [0] * self.n_bits
t_inputs[0] = 1 # LSBは常にトグル
for i in range(1, self.n_bits):
t_inputs[i] = 1
for k in range(i):
t_inputs[i] &= self.ffs[k].q
# 全フリップフロップを同時に更新（同期動作）
new_q = []
for i in range(self.n_bits):
new_q.append(self.ffs[i].q ^ t_inputs[i])
for i in range(self.n_bits):
self.ffs[i].q = new_q[i]
state = [self.ffs[i].q for i in range(self.n_bits)]
self.history.append(state.copy())
return state
def get_value(self):
val = 0
for i in range(self.n_bits):
val += self.ffs[i].q * (2 ** i)
return val
# 4ビットカウンタのシミュレーション
counter = SyncBinaryCounter(n_bits=4)
n_clocks = 20
values = []
for _ in range(n_clocks):
counter.clock()
values.append(counter.get_value())
# 波形プロット
fig, axes = plt.subplots(5, 1, figsize=(14, 8), sharex=True)
fig.suptitle('4-bit Synchronous Binary Counter', fontsize=14, fontweight='bold')
colors = ['#4fc3f7', '#81c784', '#ff8a65', '#ce93d8']
bit_names = ['Q0 (LSB)', 'Q1', 'Q2', 'Q3 (MSB)']
history = np.array(counter.history)
for i in range(4):
t_plot = np.arange(n_clocks)
# 矩形波として描画
for j in range(n_clocks):
axes[i].plot([j, j+1], [history[j, i], history[j, i]],
color=colors[i], linewidth=2)
if j < n_clocks - 1:
axes[i].plot([j+1, j+1], [history[j, i], history[j+1, i]],
color=colors[i], linewidth=2)
axes[i].fill_between(range(n_clocks), [history[j, i] for j in range(n_clocks)],
step='post', alpha=0.15, color=colors[i])
axes[i].set_ylabel(bit_names[i], fontsize=10, fontweight='bold')
axes[i].set_ylim(-0.2, 1.4)
axes[i].set_yticks([0, 1])
axes[i].grid(True, alpha=0.3)
# カウント値の表示
axes[4].step(range(n_clocks), values, where='post', color='#ffd54f', linewidth=2)
axes[4].set_ylabel('Count', fontsize=10, fontweight='bold')
axes[4].set_ylim(-1, 17)
axes[4].set_yticks(range(0, 17, 2))
axes[4].grid(True, alpha=0.3)
axes[4].set_xlabel('Clock Cycle', fontsize=12)
plt.tight_layout()
plt.savefig('sync_counter_waveform.png', dpi=150, bbox_inches='tight')
plt.show()
print("カウント値のシーケンス:")
print(values)
この波形図から、同期カウンタの動作が2進数の性質と完全に一致していることが確認できます。Q0（LSB）は毎クロックで反転し、Q1はQ0が1→0に遷移するタイミングで反転し、Q2はQ1が1→0に遷移するタイミングで反転しています。これは $2^i$ ごとにビット $i$ が反転する2進数の加算規則そのものです。カウント値のグラフでは、0から15まで直線的に増加した後、16ではなく0に戻る（オーバーフロー）の様子が確認できます。同期カウンタではすべてのビットが同時に変化するため、非同期カウンタで問題となるグリッチは発生しません。
非同期カウンタとの比較
非同期カウンタ（リプルカウンタ）の動作もシミュレーションし、伝搬遅延によるグリッチを可視化します。
import numpy as np
import matplotlib.pyplot as plt
class AsyncBinaryCounter:
"""4ビット非同期（リプル）カウンタ — 伝搬遅延をモデル化"""
def __init__(self, n_bits=4, gate_delay=1.0):
self.n_bits = n_bits
self.gate_delay = gate_delay # 各段の遅延（任意単位）
self.q = [0] * n_bits
self.history = [] # (time, bit_index, new_value)
def simulate(self, n_clocks, clk_period=10.0):
"""非同期カウンタのイベント駆動シミュレーション"""
events = []
for clk_num in range(n_clocks):
# クロックの立ち下がりエッジ（LSBのトグルトリガ）
trigger_time = clk_num * clk_period + clk_period * 0.5
events.append((trigger_time, 0)) # ビット0がトグル
# イベント処理
processed = []
while events:
events.sort(key=lambda x: x[0])
time, bit_idx = events.pop(0)
old_val = self.q[bit_idx]
new_val = 1 - old_val
self.q[bit_idx] = new_val
processed.append((time + self.gate_delay * bit_idx, bit_idx, new_val))
# 上位ビットへの伝搬: 立ち下がりエッジ(1→0)でトグル
if old_val == 1 and new_val == 0 and bit_idx + 1 < self.n_bits:
events.append((time + self.gate_delay, bit_idx + 1))
return processed
# 同期カウンタ vs 非同期カウンタの比較
n_clocks = 16
clk_period = 10.0
gate_delay = 1.2
# 非同期カウンタのシミュレーション
async_counter = AsyncBinaryCounter(n_bits=4, gate_delay=gate_delay)
events = async_counter.simulate(n_clocks, clk_period)
# 細かい時間軸で波形を再構成
dt = 0.05
t_max = n_clocks * clk_period + 5
t_fine = np.arange(0, t_max, dt)
async_waves = np.zeros((4, len(t_fine)))
sync_waves = np.zeros((4, len(t_fine)))
# 同期カウンタの波形（理想的：全ビットが同時に変化）
sync_count = 0
for i, t_val in enumerate(t_fine):
cycle = int(t_val / clk_period)
if cycle > 0 and cycle <= n_clocks:
count_val = cycle % 16
else:
count_val = 0
for bit in range(4):
sync_waves[bit, i] = (count_val >> bit) & 1
# 非同期カウンタの波形（遅延付き）
bit_state = [0, 0, 0, 0]
sorted_events = sorted(events, key=lambda x: x[0])
event_idx = 0
for i, t_val in enumerate(t_fine):
while event_idx < len(sorted_events) and sorted_events[event_idx][0] <= t_val:
_, bit_idx, new_val = sorted_events[event_idx]
bit_state[bit_idx] = new_val
event_idx += 1
for bit in range(4):
async_waves[bit, i] = bit_state[bit]
# カウント値の計算
async_values = np.zeros(len(t_fine))
sync_values = np.zeros(len(t_fine))
for i in range(len(t_fine)):
for bit in range(4):
async_values[i] += async_waves[bit, i] * (2 ** bit)
sync_values[i] += sync_waves[bit, i] * (2 ** bit)
# グリッチの検出（値が理想値と異なる区間）
glitch_mask = async_values != sync_values
fig, axes = plt.subplots(2, 1, figsize=(14, 6), sharex=True)
fig.suptitle('Synchronous vs Asynchronous Counter: Glitch Detection',
fontsize=14, fontweight='bold')
axes[0].plot(t_fine, sync_values, color='#4fc3f7', linewidth=1.5, label='Sync (ideal)')
axes[0].set_ylabel('Count Value\n(Synchronous)', fontsize=10)
axes[0].set_ylim(-1, 17)
axes[0].legend(loc='upper left')
axes[0].grid(True, alpha=0.3)
axes[1].plot(t_fine, async_values, color='#ff8a65', linewidth=1.5, label='Async (ripple)')
# グリッチ区間をハイライト
glitch_regions = np.where(glitch_mask)[0]
if len(glitch_regions) > 0:
axes[1].fill_between(t_fine, -1, 17, where=glitch_mask,
alpha=0.2, color='red', label='Glitch')
axes[1].set_ylabel('Count Value\n(Asynchronous)', fontsize=10)
axes[1].set_ylim(-1, 17)
axes[1].set_xlabel('Time (arbitrary units)', fontsize=12)
axes[1].legend(loc='upper left')
axes[1].grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('sync_vs_async_counter.png', dpi=150, bbox_inches='tight')
plt.show()
# グリッチの統計
glitch_time = np.sum(glitch_mask) * dt
total_time = t_max
print(f"グリッチ発生時間: {glitch_time:.1f} / {total_time:.1f} ({glitch_time/total_time*100:.1f}%)")
この比較図から、非同期カウンタの本質的な問題が視覚的に明らかになります。同期カウンタ（上段）のカウント値は常に正しい階段状の波形を示しますが、非同期カウンタ（下段）では遷移の瞬間に赤くハイライトされたグリッチ区間が現れています。これはビットの変化が下位から上位へ順次伝搬するため、すべてのビットが確定するまでの間に一時的な誤った値が出力されるためです。特に複数ビットが同時に変化する遷移（たとえば $0111 \to 1000$）ではグリッチが大きくなります。高速動作が求められるシステムでは、このグリッチが後段の回路に誤動作を引き起こす可能性があるため、同期カウンタが選択されます。
有限状態機械のシミュレーション — パターン検出器
先ほど設計した「1を3回連続で検出する」ムーア型FSMをPythonでシミュレーションします。
import numpy as np
import matplotlib.pyplot as plt
class MooreFSM:
"""ムーア型有限状態機械の汎用クラス"""
def __init__(self, states, initial_state, transition_table, output_table):
"""
states: 状態名のリスト
initial_state: 初期状態名
transition_table: {(状態, 入力): 次の状態}
output_table: {状態: 出力}
"""
self.states = states
self.current_state = initial_state
self.transition_table = transition_table
self.output_table = output_table
self.state_history = [initial_state]
self.output_history = [output_table[initial_state]]
def step(self, input_val):
"""1クロック分の状態遷移を実行"""
key = (self.current_state, input_val)
if key not in self.transition_table:
raise ValueError(f"未定義の遷移: 状態={self.current_state}, 入力={input_val}")
self.current_state = self.transition_table[key]
output = self.output_table[self.current_state]
self.state_history.append(self.current_state)
self.output_history.append(output)
return self.current_state, output
def simulate(self, input_sequence):
"""入力系列に対してシミュレーションを実行"""
results = []
for inp in input_sequence:
state, output = self.step(inp)
results.append((inp, state, output))
return results
# "1"が3回連続するパターン検出器（ムーア型）
states = ['S0', 'S1', 'S2', 'S3']
transition_table = {
('S0', 0): 'S0', ('S0', 1): 'S1',
('S1', 0): 'S0', ('S1', 1): 'S2',
('S2', 0): 'S0', ('S2', 1): 'S3',
('S3', 0): 'S0', ('S3', 1): 'S3',
}
output_table = {
'S0': 0, 'S1': 0, 'S2': 0, 'S3': 1
}
# テスト入力系列
input_seq = [0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
# シミュレーション実行
fsm = MooreFSM(states, 'S0', transition_table, output_table)
results = fsm.simulate(input_seq)
# 結果表示
print("=" * 60)
print("ムーア型パターン検出器（1が3回連続）のシミュレーション")
print("=" * 60)
print(f"{'Clock':>5} | {'Input':>5} | {'State':>7} | {'Output':>6}")
print("-" * 35)
for i, (inp, state, output) in enumerate(results):
detect_mark = " <-- DETECTED!" if output == 1 else ""
print(f"{i+1:>5} | {inp:>5} | {state:>7} | {output:>6}{detect_mark}")
# 波形プロット
fig, axes = plt.subplots(3, 1, figsize=(14, 7), sharex=True)
fig.suptitle('Moore FSM: Consecutive "111" Pattern Detector', fontsize=14, fontweight='bold')
n = len(input_seq)
x = np.arange(n)
# 入力信号
for i in range(n):
axes[0].plot([i, i+1], [input_seq[i], input_seq[i]], color='#4fc3f7', linewidth=2)
if i < n-1:
axes[0].plot([i+1, i+1], [input_seq[i], input_seq[i+1]], color='#4fc3f7', linewidth=2)
axes[0].set_ylabel('Input X', fontsize=11, fontweight='bold')
axes[0].set_ylim(-0.2, 1.4)
axes[0].set_yticks([0, 1])
axes[0].grid(True, alpha=0.3)
# 状態（数値化して表示）
state_map = {'S0': 0, 'S1': 1, 'S2': 2, 'S3': 3}
state_vals = [state_map[s] for s in fsm.state_history[1:]]
for i in range(n):
axes[1].plot([i, i+1], [state_vals[i], state_vals[i]], color='#ce93d8', linewidth=2)
if i < n-1:
axes[1].plot([i+1, i+1], [state_vals[i], state_vals[i+1]], color='#ce93d8', linewidth=2)
axes[1].annotate(fsm.state_history[i+1], (i + 0.5, state_vals[i] + 0.2),
ha='center', fontsize=8, color='#ce93d8')
axes[1].set_ylabel('State', fontsize=11, fontweight='bold')
axes[1].set_ylim(-0.5, 4)
axes[1].set_yticks([0, 1, 2, 3])
axes[1].set_yticklabels(['S0', 'S1', 'S2', 'S3'])
axes[1].grid(True, alpha=0.3)
# 出力信号
output_vals = fsm.output_history[1:]
for i in range(n):
color = '#ff5252' if output_vals[i] == 1 else '#81c784'
axes[2].plot([i, i+1], [output_vals[i], output_vals[i]], color=color, linewidth=2.5)
if i < n-1:
axes[2].plot([i+1, i+1], [output_vals[i], output_vals[i+1]], color=color, linewidth=2.5)
if output_vals[i] == 1:
axes[2].fill_between([i, i+1], 0, 1, alpha=0.2, color='#ff5252')
axes[2].set_ylabel('Output Y', fontsize=11, fontweight='bold')
axes[2].set_ylim(-0.2, 1.4)
axes[2].set_yticks([0, 1])
axes[2].set_xlabel('Clock Cycle', fontsize=12)
axes[2].grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('moore_fsm_pattern_detector.png', dpi=150, bbox_inches='tight')
plt.show()
この波形図から、ムーア型パターン検出器の動作を確認できます。入力系列の中で「1」が3回以上連続する区間（クロック3-4付近、クロック9-12付近、クロック16-17付近）で出力 $Y=1$ が赤くハイライトされています。注目すべきは、ムーア型の出力が状態のみに依存するため、出力が $Y=1$ になるのは「S3に遷移した後」のクロックサイクルであり、入力の3つ目の「1」が入った瞬間ではなく、次のクロックサイクルで反映される点です。また、「1」が3回連続した後も「1」が続く場合（クロック9-12）、状態はS3に留まり続け、出力も $Y=1$ を維持しています。「0」が入力された瞬間にS0に戻り、検出がリセットされることも確認できます。
ミーリ型FSMとの比較
同じパターン検出をミーリ型でも実装し、ムーア型との出力タイミングの違いを比較します。
import numpy as np
import matplotlib.pyplot as plt
class MealyFSM:
"""ミーリ型有限状態機械の汎用クラス"""
def __init__(self, states, initial_state, transition_table):
"""
transition_table: {(状態, 入力): (次の状態, 出力)}
"""
self.states = states
self.current_state = initial_state
self.transition_table = transition_table
self.state_history = [initial_state]
self.output_history = []
def step(self, input_val):
key = (self.current_state, input_val)
next_state, output = self.transition_table[key]
self.current_state = next_state
self.state_history.append(next_state)
self.output_history.append(output)
return next_state, output
def simulate(self, input_sequence):
results = []
for inp in input_sequence:
state, output = self.step(inp)
results.append((inp, state, output))
return results
# ミーリ型パターン検出器（状態数を1つ少なくできる）
mealy_states = ['S0', 'S1', 'S2']
mealy_transition = {
('S0', 0): ('S0', 0), ('S0', 1): ('S1', 0),
('S1', 0): ('S0', 0), ('S1', 1): ('S2', 0),
('S2', 0): ('S0', 0), ('S2', 1): ('S2', 1), # 3回目の1で検出
}
# テスト入力系列（ムーア型と同一）
input_seq = [0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
# ムーア型（再実行）
moore_states_list = ['S0', 'S1', 'S2', 'S3']
moore_transition = {
('S0', 0): 'S0', ('S0', 1): 'S1',
('S1', 0): 'S0', ('S1', 1): 'S2',
('S2', 0): 'S0', ('S2', 1): 'S3',
('S3', 0): 'S0', ('S3', 1): 'S3',
}
moore_output = {'S0': 0, 'S1': 0, 'S2': 0, 'S3': 1}
# ムーア型FSMクラス（前のセルから再定義）
class MooreFSM2:
def __init__(self, states, initial, trans, out):
self.current_state = initial
self.trans = trans
self.out = out
self.output_history = []
def simulate(self, inputs):
for inp in inputs:
self.current_state = self.trans[(self.current_state, inp)]
self.output_history.append(self.out[self.current_state])
moore_fsm = MooreFSM2(moore_states_list, 'S0', moore_transition, moore_output)
moore_fsm.simulate(input_seq)
mealy_fsm = MealyFSM(mealy_states, 'S0', mealy_transition)
mealy_fsm.simulate(input_seq)
# 比較プロット
fig, axes = plt.subplots(3, 1, figsize=(14, 7), sharex=True)
fig.suptitle('Moore vs Mealy FSM: Output Timing Comparison', fontsize=14, fontweight='bold')
n = len(input_seq)
# 入力
for i in range(n):
axes[0].plot([i, i+1], [input_seq[i], input_seq[i]], color='#4fc3f7', linewidth=2)
if i < n-1:
axes[0].plot([i+1, i+1], [input_seq[i], input_seq[i+1]], color='#4fc3f7', linewidth=2)
axes[0].set_ylabel('Input X', fontsize=11, fontweight='bold')
axes[0].set_ylim(-0.2, 1.4)
axes[0].set_yticks([0, 1])
axes[0].grid(True, alpha=0.3)
# ムーア型出力
moore_out = moore_fsm.output_history
for i in range(n):
color = '#ff5252' if moore_out[i] == 1 else '#81c784'
axes[1].plot([i, i+1], [moore_out[i], moore_out[i]], color=color, linewidth=2.5)
if i < n-1:
axes[1].plot([i+1, i+1], [moore_out[i], moore_out[i+1]], color=color, linewidth=2.5)
if moore_out[i] == 1:
axes[1].fill_between([i, i+1], 0, 1, alpha=0.2, color='#ff5252')
axes[1].set_ylabel('Moore Output', fontsize=11, fontweight='bold')
axes[1].set_ylim(-0.2, 1.4)
axes[1].set_yticks([0, 1])
axes[1].grid(True, alpha=0.3)
# ミーリ型出力
mealy_out = mealy_fsm.output_history
for i in range(n):
color = '#ff5252' if mealy_out[i] == 1 else '#81c784'
axes[2].plot([i, i+1], [mealy_out[i], mealy_out[i]], color=color, linewidth=2.5)
if i < n-1:
axes[2].plot([i+1, i+1], [mealy_out[i], mealy_out[i+1]], color=color, linewidth=2.5)
if mealy_out[i] == 1:
axes[2].fill_between([i, i+1], 0, 1, alpha=0.2, color='#ff5252')
axes[2].set_ylabel('Mealy Output', fontsize=11, fontweight='bold')
axes[2].set_ylim(-0.2, 1.4)
axes[2].set_yticks([0, 1])
axes[2].set_xlabel('Clock Cycle', fontsize=12)
axes[2].grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('moore_vs_mealy_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
print("入力系列: ", input_seq)
print("ムーア型出力: ", moore_out)
print("ミーリ型出力: ", mealy_out)
print(f"\nムーア型: 4状態（S0-S3）を使用")
print(f"ミーリ型: 3状態（S0-S2）を使用 — 1状態少ない")
この比較図から、ムーア型とミーリ型の本質的な違いが明確になります。ミーリ型は「1」が3回連続したまさにそのクロックサイクルで出力が $Y=1$ になるのに対し、ムーア型は1クロック遅れて出力が変化します。これはムーア型の出力が「状態のみ」に依存するため、入力の変化を反映するには一度状態遷移を経る必要があるからです。一方、ミーリ型は「状態 + 入力」で出力が決まるため、即座に反応できます。また、ミーリ型は3状態で実現できている（ムーア型は4状態）ことにも注目してください。「検出状態」を独立の状態として持つ代わりに、S2で入力1が来たときの出力として検出を表現しているからです。
汎用FSMシミュレータ — 状態遷移図の可視化
最後に、任意のFSMの状態遷移をテキストベースで可視化するシミュレータを実装します。
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
def visualize_state_transition_diagram(states, transitions, output_table,
fsm_type='moore', title='FSM'):
"""
FSMの状態遷移図をmatplotlibで描画する
states: 状態名のリスト
transitions: ムーア型 {(state, input): next_state}
ミーリ型 {(state, input): (next_state, output)}
output_table: ムーア型の場合 {state: output}、ミーリ型はNone
"""
fig, ax = plt.subplots(1, 1, figsize=(10, 8))
ax.set_xlim(-2.5, 2.5)
ax.set_ylim(-2.5, 2.5)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title(title, fontsize=16, fontweight='bold', pad=20)
n = len(states)
# 状態を円形に配置
angles = np.linspace(np.pi/2, np.pi/2 - 2*np.pi, n, endpoint=False)
radius = 1.5
positions = {}
for i, state in enumerate(states):
x = radius * np.cos(angles[i])
y = radius * np.sin(angles[i])
positions[state] = (x, y)
# 状態ノードの描画
for state in states:
x, y = positions[state]
circle = plt.Circle((x, y), 0.35, fill=True, facecolor='#263238',
edgecolor='#4fc3f7', linewidth=2)
ax.add_patch(circle)
if fsm_type == 'moore' and output_table:
label = f"{state}\n/{output_table[state]}"
else:
label = state
ax.text(x, y, label, ha='center', va='center', fontsize=11,
fontweight='bold', color='white')
# 遷移の描画
drawn_edges = {}
for (src, inp), val in transitions.items():
if fsm_type == 'moore':
dst = val
label = str(inp)
else:
dst, out = val
label = f"{inp}/{out}"
edge_key = (src, dst)
if edge_key not in drawn_edges:
drawn_edges[edge_key] = []
drawn_edges[edge_key].append(label)
for (src, dst), labels in drawn_edges.items():
label_text = ', '.join(labels)
sx, sy = positions[src]
dx, dy = positions[dst]
if src == dst:
# 自己ループ
angle = np.arctan2(sy, sx)
loop_x = sx + 0.5 * np.cos(angle)
loop_y = sy + 0.5 * np.sin(angle)
ax.annotate('', xy=(sx + 0.3*np.cos(angle+0.2), sy + 0.3*np.sin(angle+0.2)),
xytext=(sx + 0.3*np.cos(angle-0.2), sy + 0.3*np.sin(angle-0.2)),
arrowprops=dict(arrowstyle='->', color='#ff8a65', lw=1.5,
connectionstyle='arc3,rad=2.0'))
ax.text(loop_x + 0.25*np.cos(angle), loop_y + 0.25*np.sin(angle),
label_text, ha='center', va='center', fontsize=9,
color='#ff8a65', fontweight='bold',
bbox=dict(boxstyle='round,pad=0.2', facecolor='#1a1a2e', alpha=0.8))
else:
# 通常の遷移
# 方向ベクトル
dx_v = dx - sx
dy_v = dy - sy
dist = np.sqrt(dx_v**2 + dy_v**2)
ux = dx_v / dist
uy = dy_v / dist
# ノードの端から矢印を描画
start_x = sx + 0.38 * ux
start_y = sy + 0.38 * uy
end_x = dx - 0.38 * ux
end_y = dy - 0.38 * uy
# 逆方向のエッジがある場合は曲げる
reverse_key = (dst, src)
curve_rad = 0.2 if reverse_key in drawn_edges else 0.0
ax.annotate('', xy=(end_x, end_y), xytext=(start_x, start_y),
arrowprops=dict(arrowstyle='->', color='#81c784', lw=1.5,
connectionstyle=f'arc3,rad={curve_rad}'))
mid_x = (start_x + end_x) / 2 + curve_rad * (-uy) * 1.5
mid_y = (start_y + end_y) / 2 + curve_rad * ux * 1.5
ax.text(mid_x, mid_y, label_text, ha='center', va='center', fontsize=9,
color='#81c784', fontweight='bold',
bbox=dict(boxstyle='round,pad=0.2', facecolor='#1a1a2e', alpha=0.8))
plt.tight_layout()
return fig
# ムーア型パターン検出器の状態遷移図
moore_states = ['S0', 'S1', 'S2', 'S3']
moore_trans = {
('S0', 0): 'S0', ('S0', 1): 'S1',
('S1', 0): 'S0', ('S1', 1): 'S2',
('S2', 0): 'S0', ('S2', 1): 'S3',
('S3', 0): 'S0', ('S3', 1): 'S3',
}
moore_out = {'S0': 0, 'S1': 0, 'S2': 0, 'S3': 1}
fig = visualize_state_transition_diagram(
moore_states, moore_trans, moore_out,
fsm_type='moore',
title='Moore FSM: "111" Pattern Detector'
)
plt.savefig('moore_fsm_diagram.png', dpi=150, bbox_inches='tight',
facecolor='#0d1117')
plt.show()
print("状態遷移図を描画しました。")
print("各ノードは「状態名/出力」を表し、矢印のラベルは入力を表します。")
print("S3（出力=1）がパターン検出状態です。")
この状態遷移図により、FSMの全体像が一目で把握できます。S0（初期状態）からS1、S2、S3へと「1」の入力で右に進み、「0」の入力でS0に戻る構造が明確です。S3が自己ループを持つことで、3回以上連続する「1」にも対応しています。状態遷移図はFSMの設計と検証に不可欠なツールであり、複雑なシーケンス制御の仕様を視覚的に把握するために広く使われています。
まとめ
本記事では、フリップフロップと順序回路について体系的に解説しました。
- 組合せ回路と順序回路の違い — 組合せ回路は入力のみで出力が決まるが、順序回路は内部状態（記憶）を持ち、過去の入力履歴を反映した動作が可能
- SRラッチ — 2つのNORゲートの交差結合で記憶を実現する最も原始的な記憶素子。ただし $S=R=1$ の禁止状態が存在
- Dフリップフロップ — クロックエッジでデータを取り込む最も実用的な記憶素子。禁止状態がなく、現代のデジタル設計の標準
- JKフリップフロップ — SRの禁止状態を「トグル」に読み替えた万能型。他のフリップフロップを再現可能
- Tフリップフロップ — トグル動作に特化し、カウンタと分周器の基本構成要素
- セットアップ時間・ホールド時間 — フリップフロップの正しい動作に必要なタイミング制約。最大動作周波数を決定する本質的な要因
- レジスタ — 並列ロードレジスタは $n$ ビットの同時記憶、シフトレジスタはデータの直列転送やLFSRによる疑似乱数生成を実現
- カウンタ — 同期カウンタは全ビット同時更新でグリッチなし、非同期カウンタは構造が単純だが累積遅延とグリッチが問題
- 有限状態機械（FSM） — 順序回路の一般的な設計枠組み。ムーア型は出力が状態のみに依存し安定、ミーリ型は入力にも依存し少ない状態数で即座に応答
- 状態遷移図と状態遷移表 — FSMの仕様を明確に記述する設計ツール。状態の符号化とカルノー図を経て論理式に変換
フリップフロップと順序回路は、レジスタ、カウンタ、状態機械という形でコンピュータのあらゆる場所に遍在しています。本記事で学んだ概念は、CPUアーキテクチャの理解、FPGAプログラミング、通信プロトコルの設計など、幅広い分野への入り口です。
次のステップとして、以下の記事も参考にしてください。
- AD/DA変換器の基礎 — フリップフロップとカウンタを活用したアナログ-デジタル変換の仕組み
- 誤り検出とCRC — シフトレジスタ（LFSR）を用いた巡回冗長検査の実装