アルゴリズムステートマシン

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

ASM メソッドは次の手順で構成されます。

1.疑似コードを使用して、デバイスの望ましい動作を記述するアルゴリズムを作成します

2.疑似コードをASM チャートに変換します。

3. ASMチャートに基づいてデータパスを設計します

4.データパスに基づいて詳細な ASM チャートを作成します

5.詳細なASMチャートに基づいて制御ロジックを設計します

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

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

状態ボックス:状態の出力は四角形のボックス内に表示されます。

決定ボックス:ダイヤモンドは、指定された条件/式がテストされ、それに応じて終了パスが選択されることを示します。条件式には、FSM (有限状態マシン) への 1 つ以上の入力が含まれます。1 つの入力と 2 つの出力 (真と偽) を持つダイヤモンドで示される ASM 条件チェックは、2 つの状態ボックス間、別の決定ボックス、または条件付き出力ボックスへの条件付き転送に使用されます。決定ボックスには、テストされる指定された条件式が含まれ、式には FSM の 1 つ以上の入力が含まれます。

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

RTL操作を使用して回路の目的の動作を記述したら、データパス コンポーネントを導出できます。RTL プログラムで値が割り当てられるすべての一意の変数は、レジスタとして実装できます。変数に値を割り当てるときに実行される機能操作に応じて、その変数のレジスタは、単純なレジスタ、シフト レジスタ、カウンター、または組み合わせロジック ブロックが先行するレジスタとして実装できます。レジスタに関連付けられた組み合わせロジック ブロックは、加算器、減算器、マルチプレクサ、またはその他の種類の組み合わせロジック機能を実装できます。

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

• フローチャート
• ドラコンチャート
• ミーリーマシン
• ムーアマシン
• マップ入力変数(MEV)

• 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 』。Thomson。ISBN 0-534-46602-8。
• Brown, Stephen D.; Vranesic, Zvonko . VHDL 設計によるデジタル ロジックの基礎(第 1 版)。
  • Brown, Stephen D.; Vranesic, Zvonko (2004)。『VHDL 設計によるデジタル ロジックの基礎(第 2 版)』。McGraw Hill。ISBN 978-0-07-249938-4。
  • Brown, Stephen D.; Vranesic, Zvonko (2009)。『VHDL 設計によるデジタルロジックの基礎』（第 3 版）。McGraw Hill。ISBN 978-0-07-352953-0。
• Bjørner, Dines (1970 年 12 月) [1970-05-04, 1970-04-07, 1970-02-04]. 「フローチャート マシン」. BIT 数値数学. 10 (4). IBM 研究所、カリフォルニア州サンノゼ: 415–442. doi :10.1007/BF01935563. S2CID  189767592. RJ-685 (No. 13346).
• Lee, Samuel C. (1976).デジタル回路とロジック設計. 米国ニュージャージー州イングルウッドクリフス: Prentice-Hall .
• Santrakul, Krayim (1983). マルチバリュー LSI/VLSI ロジック設計(PDF) (博士論文). オクラホマ大学。2016-08-17にオリジナルからアーカイブ(PDF)されました。2021-02-17に取得。
• Schultz, GW (1969 年 3 月)。米国カリフォルニア州サニーベールの Central Data Systems, Inc. で執筆。「複雑なシーケンシャル ネットワークの合成のためのアルゴリズム」。コンピュータ デザイン 。第 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 による、積和論理式を扱う簡単な方法を説明した手紙を掲載しました。 […] さらに簡単な方法がDA Huffmanによって教えられています。この方法は、積和形式のいずれかの因子がゼロの場合、ブール式がゼロになることを認識することに基づいています。Veitch図またはKarnaugh マップに因子のゼロをプロットすることは、積和式の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 氏の研究は、この記事で私が紹介したものと非常によく似ているため、さらに情報を探している読者にとって興味深いものとなるでしょう。彼は、まれな変数の手法を、読み取り専用メモリから構築されたシーケンシャル ネットワークの設計に適用する研究を行ったと理解しています。彼はこの分野についてまだ何も発表していないため、読者で追加情報をご希望の場合は、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 モノグラフ シリーズ (第 1 版)。米国ニューヨーク: Academic Press, Inc. - Harcourt Brace Jovanovich 出版社の子会社。p. 149。ISBN 0-12-436550-7. ISSN  0572-4252. LCCN  73-18988. 2021-04-17 にオリジナルからアーカイブ。 2021-04-17に取得。 p. 149: […] 理論を実践に適応させる上で重要な貢献をしたのがシュルツ[20]である。彼は設計者の問題の基本的な理解を利用し、「まれな変数」を特定することを要求している。大まかに定義すると、これらの変数はすべての内部状態に関係するわけではなく、つまり、すべての状態を定義するのに必要というわけではない。本質的に、まれな変数は少数（おそらく1つか2つ）の状態または状態遷移にのみ関係する。シュルツは、設計者がまず言葉の問題を、縮小された状態遷移グラフに変換することを提案している。内部状態がエンコードされ、次にまれな変数に関する情報が適切な状態遷移に追加される。フリップフロップの入力方程式の「最初の近似」は、頻繁な変数のみに基づいて作成されます。シュルツは、これらの方程式をその後変更して、まれな変数によって制御される遷移を組み込む方法を示しています。シュルツの例では、まれな変数はすべて入力信号ですが、この考え方は「まれ」と見なされる可能性のある内部状態変数信号にも適用されます。この場合、たとえば、まれな内部状態変数フリップフロップは、特定の状況によって設定され、後でリセットされる可能性があります。フリップフロップの出力は、まれな入力変数として扱うことができます。[…](ix+1+179+3ページ)

• ASMチャートの簡単な紹介
• ASM++: RTL 設計のための最新のアルゴリズム ステート マシン手法