状態遷移マシン
簡単な順序回路の例
- 以下の図は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"からカウントすることができる。
（２）ある時刻に４つのリセット付Ｄ−ＦＦにある値が入っているとすると、次の時刻にＤ−ＦＦの値は前の値＋１になればよい。これは、Ｄ−ＦＦの４つの入力が現在の出力＋１になればよいことを示す。
- ＋１をつくる回路を特に、インクリメンタという。以下に４ビット加算器と、４ビットのインクリメンタを示す。
| ４ビット加算器 |
 |
| ４ビットインクリメンタ |
 |
（３）結果的に、４ビットカウンタは以下のようになる。’０’が入力されるフルアダーはハーフアダーで実現できるので、ＦＡをＨＡに変更してます。
宿題６ 学籍番号 名前 日付 を書いて 提出すること。
１） 以下の回路図の状態遷移図を描け
２） １０進数で示すと、０，３，６，９，１２，１５，２，５，８，１１，１４，１，４，７，１０，１３，０、なる順で３ずつ上昇する４ビットカウンターを設計せよ。
３） 以下の回路図の状態遷移図を描け
４） 同じ回路に以下の図に示されるＤ１，Ｄ２波形を入力した時のＦ１，Ｆ２，Ｃ１，Ｃ２，Ｃ３の波形を描け！
但し、Ｆ１，Ｆ２の初期値はともに’０’とする。
５） １０進数で示すと、０，１５，１４，１３，１２，１１、１０，９，８，７，６，５，４，３，２，１，０、のように１ずつ値が現減少する４ビットのカウンタを設計せよ。
今回示した、単純な順序回路は実は携帯電話や衛星ＴＶ放送などのデジタル通信での、伝送エラーを訂正するために用いられている「畳み込み符号器」です。
以上