Mealy_machine
計算理論では、Mealyマシンは有限状態マシンであり、その出力値は現在の状態と現在の入力の両方によって決定されます。これは、出力値が現在の状態のみによって決定されるムーア マシンとは対照的です。Mealy マシンは、決定論 的な有限状態変換器です。状態と入力ごとに、最大で 1 つの遷移が可能です。
コンテンツ
1 歴史
2 正式な定義
3 ミーリーマシンとムーアマシンの比較
4 ダイアグラム
5 例
5.1 単純 5.2 複雑
6 アプリケーション
7 こちらもご覧ください
8 脚注
9 参考文献
10 外部リンク
歴史
Mealy マシンは、1955 年の論文「A Method for Synthesizing Sequential Circuits」でこの概念を発表したGeorge H. Mealyにちなんで名付けられました。
正式な定義
Mealy マシンは6 タプルです( S S
0 Σ Λ T G ) { (S，S_{0}，Sigma ，Lambda ，T，G)}
以下で構成されます。
状態の有限集合 S { S}
開始状態 (初期状態とも呼ばれる)S 0
{ S_{0}}
の要素です S { S}
入力アルファベットと呼ばれる有限集合 Σ { シグマ}
出力アルファベットと呼ばれる有限集合 Λ { ラムダ}
遷移関数T : S × Σ S
{ T:Stimes Sigma rightarrow S}
状態と入力シンボルのペアを対応する次の状態にマッピングします。
出力関数G : S × Σ Λ
{ G:Stimes Sigma rightarrow Lambda }
状態と入力シンボルのペアを対応する出力シンボルにマッピングします。
一部の定式化では、遷移関数と出力関数が 1 つの関数に結合されます。T : S × Σ S × Λ
{ T:Stimes Sigma rightarrow Stimes Lambda }
.
ミーリーマシンとムーアマシンの比較
Mely マシンは状態が少ない傾向が
状態 ( n )ではなくアーク ( n 2 ) での異なる出力。
Moore マシンはより安全に使用できます。
出力はクロック エッジで変化します (常に 1 サイクル後)。
Mealy マシンでは、ロジックが完了するとすぐに、入力の変更によって出力の変更が発生する可能性がこれは、2 つのマシンが相互接続されている場合の大きな問題です。注意しないと、非同期フィードバックが発生する可能性が
Mely マシンは入力に対してより速く反応します。
同じサイクルで反応します。クロックを待つ必要はありません。
Moore マシンでは、状態を出力にデコードするために、より多くのロジックが必要になる場合がつまり、クロック エッジ後のゲート遅延が大きくなります。
ダイアグラム
Mealy マシンの状態図は、出力値を各遷移エッジに関連付けますが、Moore マシンの状態図は出力値を各状態に関連付けます。
入力と出力のアルファベットが両方ともΣの場合、Mealy オートマトンに Helix有向グラフを関連付けることもできます ( S × Σ， ( x ， i ) ( T ( x ， i )， G ( x ， i ) )))) . このグラフは状態と文字の対を頂点とし、各ノードは出次数 1 であり、( x ， i )の後継はオートマトンの次の状態とオートマトンが出力する文字です。 x を設置そしてそれは文字iを読みます。このグラフは、オートマトンがバイリバーシブルである場合、互いに素なサイクルの和集合です。
例
単純
1 つの入力と 1 つの出力を持つ単純な Mely マシンの状態図。(すべての入力値に対して、現在の入力値が前の入力値と異なる場合は 1 を出力し、それ以外の場合は 0 を出力します。)
単純な Mely マシンには、1 つの入力と 1 つの出力が各遷移エッジには、入力の値 (赤で表示) と出力の値 (青で表示) のラベルが付けられます。マシンは状態Siで開始します。(この例では、出力は 2 つの最新の入力値の排他的論理和です。したがって、マシンはエッジ検出器を実装し、入力が反転するたびに 1 を出力し、それ以外の場合は 0 を出力します。)
複雑
より複雑な Mely マシンは、複数の入力と複数の出力を持つことができます。
アプリケーション
Mealy マシンは、暗号マシンの基本的な数学的モデルを提供します。たとえば入力と出力のアルファベットをラテン アルファベットと考えると、指定された文字列 (一連の入力) を暗号化された文字列 (一連の出力) に処理できる Mealy マシンを設計できます。ただし、ミーリー モデルを使用してエニグマを説明することはできますが、状態図は複雑すぎて、複雑な暗号化マシンを設計する実行可能な手段を提供できません。
Moore/Mealy マシンは、クロックのどの時点でも出力するDFAです。最新の CPU、コンピューター、携帯電話、デジタル時計、および基本的な電子デバイス/マシンには、それを制御するためのある種の有限状態マシンが
単純なソフトウェア システム、特に正規表現を使用して表現できるものは、有限状態マシンとしてモデル化できます。自動販売機や基本的な電子機器など、そのような単純なシステムはたくさん
2 つの有限状態マシンの交点を見つけることで、たとえばメッセージを交換する並行システムを非常に簡単な方法で設計できます。たとえば、信号機は、同時に動作するさまざまな信号機など、複数のサブシステムで構成されるシステムです。
アプリケーションの例:
番号分類
タイマーで見る
自動販売機
信号機
バーコードスキャナ
ガスポンプ
こちらもご覧ください
同期回路
ムーア機
アルゴリズム ステート マシン
リチャーズ・コントローラー
脚注
^ Mealy、George H. (1955 年 9月）。「順序回路を合成する方法」。ベルシステムテクニカルジャーナル. 34 : 1045–1079. ドイ: 10.1002/j.1538-7305.1955.tb03788.x . ^ Akhavi 他 （2012)
参考文献
ミーリー、ジョージ H. (1955)。順序回路を合成する方法。ベルシステムテクニカルジャーナル。pp.1045–1079。
ホルコム、WML (1982)。代数オートマトン理論。高度な数学のケンブリッジ研究。巻。1.ケンブリッジ大学出版局。ISBN 0-521-60492-3. Zbl 0489.68046 .
ロス、チャールズ H.、ジュニア （2004)。論理設計の基礎。トムソンエンジニアリング。pp.364–367。ISBN 0-534-37804-8.
アハビ、アリ。クリマン、イネス。ロンバルディア、シルヴァン。マイレス、ジャン。Picantin、Matthieu （2012)。「オートマトン（半）群の有限性問題について」. 代数と計算の国際ジャーナル。22 (6)。arXiv : 1105.4725 . ビブコード: 2011arXiv1105.4725A . Zbl 1280.20038 .
外部リンク
コモンズのMealy マシンに関連するメディア”