ムーアとミーリマシン
有限オートマトンは、各遷移に対応する出力を持つ場合があります。出力を生成する有限状態マシンには2つのタイプがあります-
- ミーリマシン
- ムーアマシン
ミーリマシン
Mealy MachineはFSMであり、その出力は現在の状態と現在の入力に依存します。
これは、6タプル(Q、∑、O、δ、X、q 0)で記述できます。ここで、−
Q は有限の状態のセットです。
∑ 入力アルファベットと呼ばれる記号の有限集合です。
O は、出力アルファベットと呼ばれる有限の記号セットです。
δ は入力遷移関数です。ここで、δ:Q×∑→Q
X X:Q×∑→Oの出力遷移関数です。
q0任意の入力が処理されるから初期状態である(Q 0 ∈Q)。
ミーリマシンの状態テーブルを以下に示します-
現状 | 次の状態 | |||
---|---|---|---|---|
入力= 0 | 入力= 1 | |||
状態 | 出力 | 状態 | 出力 | |
→a | b | x 1 | c | x 1 |
b | b | x 2 | d | x 3 |
c | d | x 3 | c | x 1 |
d | d | x 3 | d | x 2 |
上記のミーリマシンの状態図は−です。
ムーアマシン
ムーアマシンは、出力が現在の状態のみに依存するFSMです。
ムーアマシンは、6タプル(Q、∑、O、δ、X、q 0)で表すことができます。ここで、−
Q は有限の状態のセットです。
∑ 入力アルファベットと呼ばれる記号の有限集合です。
O は、出力アルファベットと呼ばれる有限の記号セットです。
δ は入力遷移関数です。ここで、δ:Q×∑→Q
X X:Q→Oの出力遷移関数です。
q0任意の入力が処理されるから初期状態である(Q 0 ∈Q)。
ムーアマシンの状態テーブルを以下に示します-
現状 | 次の状態 | 出力 | |
---|---|---|---|
入力= 0 | 入力= 1 | ||
→a | b | c | x 2 |
b | b | d | x 1 |
c | c | d | x 2 |
d | d | d | x 3 |
上記のムーアマシンの状態図は次のとおりです。
ミーリマシン対ムーアマシン
次の表は、ミーリマシンとムーアマシンを区別するポイントを示しています。
ミーリマシン | ムーアマシン |
---|---|
出力は現在の状態と現在の入力の両方に依存します | 出力は現在の状態にのみ依存します。 |
一般的に、ムーアマシンよりも状態が少なくなります。 | 一般的に、ミーリマシンよりも多くの状態があります。 |
出力関数の値は、現在の状態での入力ロジックが実行されたときの遷移と変化の関数です。 | 出力関数の値は、現在の状態と、状態が変化するたびにクロックエッジで変化する関数です。 |
ミーリマシンは入力に対してより速く反応します。それらは通常、同じクロックサイクルで反応します。 | ムーアマシンでは、出力をデコードするためにより多くのロジックが必要になり、回路の遅延が増加します。それらは通常、1クロックサイクル後に反応します。 |
ムーアマシンからミーリマシンへ
アルゴリズム4
Input −ムーアマシン
Output −ミーリマシン
Step 1 −空白のMealyMachine遷移表形式を取ります。
Step 2 −すべてのMooreMachine遷移状態をこのテーブル形式にコピーします。
Step 3− MooreMachine状態テーブルで現在の状態とそれに対応する出力を確認します。状態Qのためならば、私出力メートルでQはどこ、ミーリ・マシン状態テーブルの出力列にコピーし、私は次の状態で表示されます。
例
次のムーアマシンを考えてみましょう-
現状 | 次の状態 | 出力 | |
---|---|---|---|
a = 0 | a = 1 | ||
→a | d | b | 1 |
b | a | d | 0 |
c | c | c | 0 |
d | b | a | 1 |
次に、アルゴリズム4を適用してMealyMachineに変換します。
Step 1 & 2 −
現状 | 次の状態 | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
状態 | 出力 | 状態 | 出力 | |
→a | d | b | ||
b | a | d | ||
c | c | c | ||
d | b | a |
Step 3 −
現状 | 次の状態 | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
状態 | 出力 | 状態 | 出力 | |
=> a | d | 1 | b | 0 |
b | a | 1 | d | 1 |
c | c | 0 | c | 0 |
d | b | 0 | a | 1 |
ミーリマシンからムーアマシンへ
アルゴリズム5
Input −ミーリマシン
Output −ムーアマシン
Step 1− Mealyマシンの状態テーブルで使用可能な各状態(Q i)の異なる出力の数を計算します。
Step 2-チーの全ての出力が同じであれば、状態Qコピー私は。それはn個の異なる出力を持つ場合は、Q休憩私をQとして、n個の状態にでn = 0、1、2......。
Step 3 −初期状態の出力が1の場合、最初に新しい初期状態を挿入して、出力を0にします。
例
次のミーリマシンを考えてみましょう-
現状 | 次の状態 | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
次の状態 | 出力 | 次の状態 | 出力 | |
→a | d | 0 | b | 1 |
b | a | 1 | d | 0 |
c | c | 1 | c | 0 |
d | b | 0 | a | 1 |
ここで、状態「a」と「d」はそれぞれ1と0の出力のみを提供するため、状態「a」と「d」を保持します。ただし、状態「b」と「c」は異なる出力(1と0)を生成します。だから、私たちは分割しますb に b0, b1 そして c に c0, c1。
現状 | 次の状態 | 出力 | |
---|---|---|---|
a = 0 | a = 1 | ||
→a | d | b 1 | 1 |
b 0 | a | d | 0 |
b 1 | a | d | 1 |
c 0 | c 1 | C 0 | 0 |
c 1 | c 1 | C 0 | 1 |
d | b 0 | a | 0 |