ミーリーグラフを使って順序回路を解析する

あるきっかけで状態遷移図が研究で必要となり,Mealy Graph(ミーリーグラフ)についてちょっと勉強したので備忘録代わりに記事に残しておきます.

Mealy Graphでは,順序回路に対する「入力」「状態」「出力」を考慮して,入力の値により状態が遷移し出力が決まるというもの.なんか,制御理論の状態方程式と似てますね.このMealy Graphを使うと,順序回路の動作も理解しやすいとか.

なんかいい例題がないかと思って色々テキストを調べましたが,これが意外と少ない.最近の教科書では全然ダメです.ネットで調べてみましたが,ネットでもあまりないですね.状態遷移図を使うことってあまりないのだろうか?

それで英語のページを検索したところ結構見つかりました.その中から1ついい例題があったので,解析してみたいと思います.

解析対象はこの回路(引用はこちら

入力は\(X\),出力は\(Y\)です.パッと見ただけでは何をしてる回路なのかさっぱり分かりません.これをMealy Graphで表現して動作を理解しようというのが今回の目的です.

先ずはJK-FFの入力の方程式です.上のFFを1,下のFFを0と添え字を打つことにします.

\begin{eqnarray}
J_1 &=& Q_1\overline{X}\\
K_1 &=& Q_1+X\\
J_0 &=& Q_0+X\\
K_0 &=& \overline{X}
\end{eqnarray}

それで,状態遷移表を書きます.JK-FFの特性方程式は,
\[
Q'=J\overline{Q} + \overline{K}Q
\]
なので(脚注1)
\begin{eqnarray}
Q_0' &=& (Q_1+X)\overline{Q_0} + \overline{\overline{X}}Q_0\\
&=& Q_1\overline{Q_0} + \overline{Q_0}X + Q_0 X\\
Q_1' &=& Q_0\overline{X}\overline{Q_1} + \overline{(Q_0+X)}Q_1\\
&=& \overline{Q_1}Q_0\overline{X} + Q_1\overline{Q_0}\overline{X}
\end{eqnarray}

となり,この式を使って状態遷移表を書きます.

たとえば,\(Q_0'\)について見ると,項は\(Q_1\overline{Q_0}\)と\(\overline{Q_0}X\)と\(Q_0 X\)の3つ.したがって,表の\(Q_1, Q_0, X\)の並びでみると,それぞれの項は10*,*01,*11の3つ(*はdon't care).したがって,\(Q_0'=1\)となるのは,\(Q_1, Q_0, X\)の3つ値の組み合わせが,100,101,001,011,111となる5箇所ということになります.


ここまで完成したら,あとは簡単.Mealy Graphで表現すると,

ここで,状態Aは\(Q_1=0, Q_0=0\),状態Bは\(Q_1=0, Q_0=1\),状態Cは\(Q_1=1, Q_0=0\),状態Dは\(Q_1=1, Q_0=1\)を表しています.

これを元に回路の動作を考察すると,\(Y=1\)はAからスタートしてどういう状態のときかと考えます.出力\(Y\)が1となるのは,唯一状態DからBへ遷移したときです.それでは,状態Aから始まって状態Dに至るまでどんな状態遷移が考えられ,それによる入力シーケンスはどのようなものか考察します.

ストレートにD→Bに至る状態遷移は,A→B→C→D→Bです.そのときの入力シーケンスは,1→0→0→1ということになります.途中で戻る場合もありますので,そのようなケースを考えると,たとえば,A→B→C→B→B→B→C→D→Bも考えられます.このときの入力シーケンスは,1→0→1→1→1→0→0→1となりますが,やはり最後に1→0→0→1が現れるので\(Y=1\)となります.つまり,\(X\)が1001のシーケンスで入力された時,出力が\(Y=1\)となる回路ということが分かります.

注意が必要なのは,Dで1が入力されると,状態は1001となって出力は\(Y=1\)となりますが,ここで状態Aに戻るのではなく,Bに戻るのがポイント.これは,1→0→0→1→0→0→1の場合,前半で1001のシーケンスが現れてますが,後半でも1001のシーケンスが現れてます.このような場合に1001が2回現れているという解釈をしていることによります.これを2回という解釈をしない場合はDからAに戻ると思います.

このような動作は,さすがに回路図を見ただけでは分からないですよね.

【脚注1】
JK-FFの真理値表を書くと,

こうなりますので(ただし,\(Q' = Q(t+1)\)),主加法標準形により\(Q'\)を書き下すと,
\begin{eqnarray}
Q'&=&\overline{Q}J\overline{K} + \overline{Q}JK + Q\overline{J}\overline{K} + QJ\overline{K}\\
&=&\overline{Q}J(\overline{K}+K) + Q\overline{K}(\overline{J}+J)\\
&=&\overline{Q}J + Q\overline{K}
\end{eqnarray}
となります.