アルゴリズミックステートマシン
プログラミングの方法

アルゴリズミックステートマシン（ASM）は、有限ステートマシン（FSM）を設計するための手法です。1960年からカリフォルニア大学バークレー校（UCB）のトーマス・E・オズボーンによって開発され、 [1] 1968年にヒューレット・パッカードに導入・実装され、1967年から形式化・拡張され、1970年からクリストファー・R・クレアによって論文が執筆されました。 [2] [3] [4]デジタル集積回路の図を表すために使用されます。ASM図は状態図に似ていますが、より構造化されているため、理解しやすいです。ASMチャートは、デジタルシステムの順次動作を記述する方法です

ASM法

ASM法は次のステップで構成されています。

1.疑似コードを使用して、デバイスの望ましい動作を記述するアルゴリズムを作成します
2.擬似コードをASMチャートに変換します。
3. ASMチャートに基づいてデータパスを設計します
4 .データパスに基づいて詳細な ASM チャートを作成します。
5.詳細なASMチャートに基づいて制御ロジックを設計します

ASMチャート

ASMチャートは、状態名、状態ボックス、決定ボックス、条件付き出力ボックスという4種類の基本要素の相互接続で構成されています。長方形で表されるASMの状態は、通常の状態図または有限ステートマシンの1つの状態に対応します。ムーア型の出力はボックス内にリストされています

州名

州名：州名は円の中に示され、円は左上隅に配置されます。または、円なしで州名が配置されます

状態ボックス

状態ボックス：状態の出力は四角いボックス内に示されます

ASMチャートで使用される決定ボックス

決定ボックス：ひし形は、指定された条件/式がテストされ、それに応じて終了パスが選択されることを示します。条件式には、FSMへの1つ以上の入力が含まれます。1つの入力と2つの出力（真と偽）を持つひし形で示されるASM条件チェックは、2つの状態ボックス間、別の決定ボックス、または条件付き出力ボックスへの条件付き転送に使用されます。決定ボックスには、テストされる条件式が含まれ、条件式にはFSMへの1つ以上の入力が含まれます。

条件出力ボックス

条件出力ボックス：楕円はMealy型の出力信号を示します。これらの出力は、状態だけでなくFSMへの入力にも依存します

データパス

RTL演算を用いて回路の所望の動作を記述したら、データパス構成要素を導出できます。RTLプログラムで値が割り当てられるすべての変数は、レジスタとして実装できます。変数に値を割り当てる際に実行される機能演算に応じて、その変数のレジスタは、単純なレジスタ、シフトレジスタ、カウンタ、または組み合わせ論理ブロックを前置したレジスタとして実装できます。レジスタに関連付けられた組み合わせ論理ブロックは、加算器、減算器、マルチプレクサ、またはその他の組み合わせ論理機能を実装できます。

詳細ASMチャート

データパスが設計されると、ASMチャートは詳細ASMチャートに変換されます。RTL表記は、データパスで定義された信号に置き換えられます

参照

参考文献

  1. ^ オズボーン、トーマス・“トム”・E. (2004年11月11日) [1994年]. 「トム・オズボーン自身の言葉による物語」.スティーブ・ライブソンのHP9825ページ（バーニー・オリバーへの手紙）. 2021年2月24日時点のオリジナルよりアーカイブ。2021年2月24日閲覧。
  2. ^ Clare, Christopher "Chris" R. (1971年2月) [1970年11月].アルゴリズムステートマシンの論理設計. Hewlett-Packard Laboratories, USA: Hewlett-Packard . CHMカタログ番号 102650285.（110ページ）[1] （注：1970年と1971年に内部的に数回の改訂が行われました。これは後にMcGraw-Hill社から出版されました。[A]）
  3. ^ Clare, Christopher "Chris" R. (1973) [1972年11月]. Designing Logic Systems Using State Machines. Osborne, Thomas "Tom" E. (initial contributions) (第1版). Electronics Research Laboratory, Hewlett-Packard Laboratories: McGraw-Hill, Inc. ISBN  0-07011120-0 S2CID  60509061 SBN 07-011120-0. ISBN 978-0-07011120-2. ark:/13960/t9383kw8n. 79876543. 2021年2月14日閲覧(vii+114+3ページ) [2][3] (注: この本は1970年のヒューレット・パッカード社内文書に基づいています。[B] )
  4. ^ House, Charles "Chuck" H. (2012年12月24日). 「私たちの周りでパラダイムシフトが起こっていた」(PDF) . IEEE Solid-State Circuits Magazine . 第4巻第4号. スタンフォード大学:電気電子学会. pp.  32– 35. doi :10.1109/MSSC.2012.2215759. eISSN  1943-0590. ISSN 1943-0582. 2013年1月20日時点のオリジナルより アーカイブ(PDF) . 2023年6月30日閲覧。 pp.  2– 3:第2回IEEEマイクロプロセッサワークショップ（現在はアシロママイクロコンピュータワークショップ、またはAMWと呼ばれています）は、1976年4月28日（水）から30日（金）にかけて、カリフォルニア州モントレー近郊で開催されました。[…] 水曜日の夜の講演では、リアプノフ状態変数数学と、HP社でクリス・クレアとデイブ・コクランが大成功を収めた携帯型科学電卓（例えばHP 35 ）向けに開拓した派生技術を用いた、全く異なる設計手法（アルゴリズム・ステート・マシン設計（ ASM））を可能にするツールについて説明しました。 [ … ] 私の主張は、回路設計はもはや要素ごとの問題ではなく、多数のノードにおける「状態の流れ」、つまりデバイスピンの電圧ではなくレジスタの連続的な「ワード」の問題になったということです。つまり、アナログ電圧であれスイッチング電圧であれ、電子電圧はソフトウェア命令と「データ状態」に「負ける」という主張でした。システムは、アナログ信号の歪みやデジタルスイッチング時間ではなく、適切な状態シーケンスに基づいて設計・分析されるようになる、というものでした。 […]出版前の書籍の威力は既に実感していました。クレアの洞察に満ちたASM手法の教科書『ステートマシンを用いたロジックシステムの設計』は、HPデザインコミュニティを席巻しました […]しかし、スタンフォード大学の電気工学部は楽観的ではなく、1974年にクレアの講義を「少し型破りすぎる」としてキャンセルしました […] スタンフォード大学はクワイン＝マクラスキー最小化手法を好みました。ミードのカリフォルニア工科大学の同僚であるアイヴァン・サザーランドは、1977年にサイエンティフィック・アメリカン誌に論文を寄稿しました[…] マイクロエレクトロニクスがコンピューティング理論と実践にもたらす課題について、チップの表面の大部分が「部品」（トランジスタ）ではなく「配線」（導電経路）で占められているため、数十年にわたるロジック設計における最小化理論はもはや無意味になっていると指摘しました […]（4ページ）

さらに詳しく

  • Lee, Sunggu (2000) [1999]. 『コンピュータとその他の複雑なデジタル機器の設計』（第1版）. アッパーサドルリバー、ニュージャージー州、アメリカ合衆国: Prentice-Hall, Inc. ISBN 0-13-040267-2 LCCN  99-049967. ISBN 978-0-13040267-7。（14+418ページ）
  • Lee, Sunggu (2000). 『コンピュータ設計：高度なデジタル論理設計の例』Prentice- Hall
  • Lee, Sunggu (2006). 『Advanced Digital Logic Design: Using VHDL, State Machines, and Synthesis for FPGAs』 トムソン社. ISBN 0-534-46602-8。
  • ブラウン、スティーブン・D.；ヴラネシック、ズヴォンコ. VHDL設計によるデジタルロジックの基礎（第1版）
  • ビョルナー、ダインズ（1970年12月） [ 1970年5月4日、1970年4月7日、1970年2月4日]。「フローチャートマシン」。BIT数値数学。10 （4） 。IBM研究所、カリフォルニア州サンノゼ：415–442。doi：10.1007/BF01935563。S2CID 189767592。RJ  -685（No. 13346）。
  • リー、サミュエル・C. (1976). 『デジタル回路と論理設計』 アメリカ合衆国ニュージャージー州エングルウッド・クリフス:プレンティス・ホール社.
  • Santrakul, Krayim (1983). マルチバリューLSI/VLSIロジック設計(PDF) (博士論文). オクラホマ大学. 2016年8月17日時点のオリジナルよりアーカイブ(PDF) . 2021年2月17日閲覧。
  • Schultz, GW (1969年3月). Central Data Systems, Inc.（カリフォルニア州サニーベール）にて執筆. 「複雑なシーケンシャルネットワークの合成のためのアルゴリズム」. Computer Design . 第8巻第3号. マサチューセッツ州コンコード, 米国: Computer Design Publishing Corporation. pp.  49– 55. ISSN  0010-4566. OCLC  828863003. 2021年2月22日閲覧.(7 ページ) (注: この記事は、同誌のその後の号に多数の読者からの投書を引き起こしました。)
  • Schultz, GW (1969). Central Data Systems, Inc.（米国カリフォルニア州サニーベール）にて執筆。「編集者へ」。編集者への手紙。Computer Design . 第8巻、第5～12号。米国マサチューセッツ州コンコード：Computer Design Publishing Corporation。p. 10. ISSN  0010-4566. OCLC  828863003. p. 10: […] 4月号では、RL Dineleyによる積和論理式を扱う簡単な方法を紹介する手紙が掲載されました。[…] D.A. Huffmanはさらに簡単な方法を説いています。この方法は、積和形式のいずれかの因子がゼロの場合、ブール式もゼロになるという認識に基づいています。ヴィーチ図やカルノー図に因子のゼロをプロットするのは、積和式の1を見つけるのと同じくらい簡単です。 […] Dineleyの例 (A+BC)(A+C) を使って説明しましょう。[…] A+BC の結果の零点は、AとBCの両方が零である場所に必ず配置されます。したがって、マップ上に式A * BC (これはA * B + A * Cに等しい) を配置します。同様に、A+C の零点はA * Cに配置され、プロットされます。すべての零点が配置されたら、マップの残りの部分を1で埋めることができます。もう少し形式的に、対象の式の論理補項を代数的に計算し、その結果の式の零点をプロットすることもできます。しかし、単純な積和表現では、補項は目視で記述できます。あるいは、式全体を記述せずに目視で零点をプロットすることもできます。[…] 「まれにしか使用されない変数を含む古典的縮約」1968年10月11日、サンタクララ大学[…] Osborne氏の研究は、私が本稿で提示したものと非常によく似ており、より詳しい情報を求める読者にとって興味深いものとなるでしょう。彼は、低頻度変数の手法を、リードオンリーメモリ（ROM）で構築されたシーケンシャルネットワークの設計に適用する研究を行っていると承知しています。この分野に関する発表はまだありませんので、読者の方で追加情報をご希望の場合は、以下の住所までOsborne氏までご連絡ください。[…] Thomas E. Osborne […] Building 1U […] 1501 Page Mill Road […] Palo Alto, California […] ご一緒に論文を発表する機会をいただき、ありがとうございます。[…] GW Schultz […] Central Data Systems, Inc. […] Sunnyvale, California（1ページ）（注：オズボーンの方法は後にクレアによって出版されました。[B]）
  • Langdon, Jr., Glen G. (1974). 「第4章 相互関係、D. 論理設計とスイッチング理論、3. 設計の出発点としてのフローテーブル」。米国カリフォルニア州サンノゼのIBMコーポレーションで執筆。Ashenhurst, Robert "Bob" Lovett [Wikidataにて] (編) 『論理設計 - 理論と実践のレビュー』 ACM Monograph Series (第1版)。米国ニューヨーク：Academic Press, Inc. - Harcourt Brace Jovanovich Publishersの子会社。p. 149。ISBN 0-12-436550-7. ISSN  0572-4252. LCCN  73-18988. 2021年4月17日にオリジナルからアーカイブ。2021年4月17日閲覧。p. 149: […] 理論を実践に適応させる上で重要な貢献をしたのはシュルツ[20]である。彼は設計者の問題に対する基本的な理解に基づき、「稀な変数」を特定することを要求した。緩く定義されたこれらの変数はすべての内部状態に関連するわけではなく、つまり、すべての状態を定義するために必要というわけではない。本質的に、稀な変数は少数（おそらく1つか2つ）の状態または状態遷移にのみ関連する。シュルツは、設計者がまず言葉で表現された問題を、簡略化された状態遷移グラフに変換することを提案している。内部状態はエンコードされ、次に稀な変数に関する情報が適切な状態遷移に追加されるフリップフロップの入力方程式に対する「第一近似」は、頻出変数のみに基づいて構築されます。シュルツは、これらの方程式を、その後、稀な変数によって制御される遷移を組み込むようにどのように修正できるかを示しています。シュルツの例では、稀な変数はすべて入力信号ですが、この考え方は「稀」とみなされる可能性のある内部状態変数信号にも適用されます。この場合、例えば、稀な内部状態変数フリップフロップは、特定の状況によってセットされ、その後しばらくしてリセットされる可能性があります。フリップフロップの出力は、稀な入力変数として扱うことができます。[…]（ix+1+179+3ページ）
  • ASMチャートの簡単な紹介
  • ASM++: RTL設計のための最新のアルゴリズムステートマシン手法
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algorithmic_state_machine&oldid=1329366857"