状態遷移マシン
順序回路と組み合せ回路（教科書６．１，６．２）
- 入力信号によって、その出力が一義的に決まる回路は組み合せ回路であった。
- これに対して、回路の中にフリップフロップやラッチ等を含んで、回路が内部に状態を持つ回路を
「順序回路」もしくは「状態遷移マシン」という。
- 本講義では、状態をD-FFに保持し、そのD-FFの状態はクロック信号の立ち上がりエッジで変化する順序回路を取り扱う。
- 教科書ではJ-Kフリップフロップを主に用いているが、D-FFが最も簡単であるので、D-FFのみを使用する。
簡単な順序回路の例
- 以下の図はD-FF ２個とEXOR（排他的論理和）ゲートからなる順序回路である。
- 回路の内部の状態はＤフリップフロップに記憶される。
- このＤフリップフロップの値は入力データＤＩＮがシフトしてきたものであり、状態の遷移の方法は最も単純である。
- ２入力EXORゲートは半加算器にも使用されるゲートであり、入力の２つのビットを加算して、その結果を２で割ったあまりに対応する。
- 真理値表を書くと以下のようになる。
| 入力 |
|
出力 |
| 入力A |
入力B |
|
EXORゲートの出力 |
| ０ |
０ |
|
０ |
| ０ |
１ |
|
１ |
| １ |
０ |
|
１ |
| １ |
１ |
|
０ |
- この順序回路のデータ入力端子DINに ０，１，０，０，１，１の順にCLOCKに同期して以下の図のようにデータを入力すると、１段目のD-FFの出力F1と、２段目のD-FFの出力F2は以下のように変化する。
- 回路から明らかなように、F1は入力データを１サイクル遅らせたものになり、F2はF1を１サイクル遅らせたものとなる。
- C1、C2はDIN、F1、F2からEXORでそれぞれ計算される。
ここで注目すべきことは、
- 回路には２つのD-FFがあり、F1とF2はそれぞれ’０’もしくは’１’の値を保持するので、組み合せれば計４種類の状態を持つことになる。
- 図のt=2とt=3のサイクルでは同一の入力データ’０’が入力されているが、出力(C1,C2)=(0,1)と(1,1)であり、入力データが同じでも出力データは異なる。これが、組み合せ回路との相違である。
状態遷移表
- 先ほどのt=2の時に(F1,F2)=(1,0)であり、その時にDIN=0を入力したので、(C1,C2)=(0,1)となる。
- また、t=3の時には、(F1,F2)=(0,1)である。
- ということでこのような関係を表に書くことができる。
| t=nの時の状態 |
t=n+1の時の状態F1、F2 |
t=nの時の出力C1,C2 |
| F1 |
F2 |
入力DIN |
入力DIN |
| ０ |
１ |
０ |
１ |
| ０ |
０ |
０ |
０ |
１ |
０ |
０ |
０ |
１ |
１ |
| ０ |
１ |
０ |
０ |
１ |
０ |
１ |
１ |
０ |
０ |
| １ |
０ |
０ |
１ |
１ |
１ |
０ |
１ |
１ |
０ |
| １ |
１ |
０ |
１ |
１ |
１ |
１ |
０ |
０ |
１ |
- ここで、t=nの時の状態を示しているが、t=nの時とはt=nのサイクルで値等がすべて安定した時の値であり（t=nサイクルの後半の方の値）これはすなわち、t=n+1になる時のクロックの立ち上がりの瞬間の値を言う。（これは重要です。）
状態遷移図
- また、状態遷移表を以下のような状態遷移図を用いて表すこともできる。
- ここで、○は状態を表し、４つの状態があることがわかる。
- また、矢印で各入力データに対する状態の遷移を示す。
- その時に、出力データ矢印の横に示されている。
同期式４ビットカウンタの設計
- ４ビットすなわち、"0000",
"0001", "0010", ...,
"1111", "0000", ... と言うように数字を数えるカウンタを設計する。
- １０進法で示すと、0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 0, 1, ...のように数える。
- カウンターは単純な機能であるが、マイクロプロセッサのプログラムカウンタや、パソコンのメインメモリのリフレッシュカウンター等、色々なところに用いられている。
- プログラムカウンタとは、実行すべき命令のアドレスを示すカウンタ
- パソコンのメインメモリに使われているＤＲＡＭ（ディーラム）は、定期的に内容を書き直さないとデータが消えてしまう。リフレッシュカウンタは、この定期的なデータの書き直し（リフレッシュ）を指示する。
（１）今回、初期値を設定するためにリセット（ＲＥＳＥＴ）端子付D-FFを用いる。
| リセット付Ｄ−ＦＦシンボル |
リセット付Ｄ−ＦＦの動作波形 |
 |
 |
- リセット入力がＨＩＧＨであれば、クロックに関係なく、データ出力は’０’となる。
（２）４ビットの値を保持する必要があるので、リセット付Ｄ−ＦＦを４つ用いる。下図のように、それぞれのＤ−ＦＦは２進数の各桁に対応する。リセットを’１’にすれば、４つのＤ−ＦＦの出力は’０’となるので、"0000"からカウントすることができる。
（２）ある時刻に４つのリセット付Ｄ−ＦＦにある値が入っているとすると、次の時刻にＤ−ＦＦの値は前の値＋１になればよい。これは、Ｄ−ＦＦの４つの入力が現在の出力＋１になればよいことを示す。
- ＋１をつくる回路を特に、インクリメンタという。以下に４ビット加算器と、４ビットのインクリメンタを示す。
| ４ビット加算器 |
 |
| ４ビットインクリメンタ |
 |
（３）結果的に、４ビットカウンタは以下のようになる。’０’が入力されるフルアダーはハーフアダーで実現できるので、ＦＡをＨＡに変更してます。
クイズ７ 学籍番号 名前 日付 を書いて 提出すること。
１） 以下の回路図の状態遷移図を描け
２） １０進数で示すと、０，３，６，９，１２，１５，２，５，８，１１，１４，１，４，７，１０，１３，０、なる順で３ずつ上昇する４ビットカウンターを設計せよ。
宿題７ 学籍番号 名前 日付 を書いて 提出すること。
１） 以下の回路図の状態遷移図を描け
２） 同じ回路に以下の図に示されるＤ１，Ｄ２波形を入力した時のＦ１，Ｆ２，Ｃ１，Ｃ２，Ｃ３の波形を描け！
但し、Ｆ１，Ｆ２の初期値はともに’０’とする。
３） １０進数で示すと、０，１５，１４，１３，１２，１１、１０，９，８，７，６，５，４，３，２，１，０、のように１ずつ値が現減少する４ビットのカウンタを設計せよ。
今回示した、単純な順序回路は実は携帯電話や衛星ＴＶ放送などのデジタル通信での、伝送エラーを訂正するために用いられている「畳み込み符号器」です。
以上