Loading article…
ESPRESSOロジックミニマイザは、デジタルロジックゲート回路の複雑さを効率的に削減するためのヒューリスティックな特定のアルゴリズムを使用するコンピュータプログラムです。 [1] ESPRESSO-Iは、もともと1982年にIBMでRobert K. Braytonらによって開発されました。 [2] [3]そして1984年にESPRESSO-IIとして改良されました。[4] [5] Richard L. Rudellは後に1986年にその派生版ESPRESSO-MV [6]と1987年にESPRESSO-EXACTを発表しました。[7] [8] [5] Espressoは多くの派生製品に影響を与えています。
導入
電子デバイスは多数のデジタル回路ブロックで構成されており、それらの組み合わせによって必要なタスクが実行されます。製造コストを最小限に抑え、デバイスのパフォーマンスを最大限に高めるには、ロジック ゲート回路の形式でロジック機能を効率的に実装すること(必要以上のロジック ゲートを使用しない) が必要です。
デジタルロジック回路の設計
すべてのデジタル システムは、情報を格納するメモリ要素と、その情報を変換する組み合わせ回路という 2 つの基本機能で構成されています。カウンタなどのステート マシンは、メモリ要素と組み合わせ論理回路の組み合わせです。メモリ要素は標準論理回路であるため、限られた代替回路セットから選択されます。したがって、デジタル機能の設計は、組み合わせゲート回路を設計し、それらを相互接続することにつながります。
一般に、高レベルの抽象化から論理回路をインスタンス化することを論理合成と呼びます。これは手作業で実行することもできますが、通常はコンピューターによる何らかの形式的手法が適用されます。この記事では、組み合わせ論理回路の設計方法について簡単にまとめます。
デジタル ロジック回路の設計の出発点は、ロジック回路が構成するシステム全体の分析から導き出された、その望ましい機能です。説明は、何らかのアルゴリズム形式または論理方程式で記述できますが、表の形式でまとめることもできます。以下の例は、 10 進数の値のバイナリ コードを、ディスプレイの各セグメントを点灯させる信号に変換する7 セグメント ディスプレイドライバーの表の一部を示しています。
数字コードセグメント
ABCDEFG
0 0000 1 1 1 1 1 1 0 -A-
1 0001 0 1 1 0 0 0 0 | |
2 0010 1 1 0 1 1 0 1 FB
3 0011 1 1 1 1 0 0 1 | |
4 0100 0 1 1 0 0 1 1 -G-
5 0101 1 0 1 1 0 1 1 | |
6 0110 1 0 1 1 1 1 1 EC
7 0111 1 1 1 0 0 0 0 | |
8 1000 1 1 1 1 1 1 1 -D-
9 1001 1 1 1 1 0 1 1
実装プロセスは、以下に説明するロジック最小化フェーズから始まります。これは、個別の項を、より少ない変数を含むより大きな項に結合して関数テーブルを簡素化するためのものです。
次に、最小化された結果は因数分解手順によってさらに小さな部分に分割され、最終的にターゲットテクノロジの利用可能な基本ロジックセルにマッピングされます。この操作は一般にロジック最適化と呼ばれます。[9]
古典的な最小化法
古典的なカルノー図を使用してブール関数を手作業で最小化することは、面倒で退屈で、エラーが発生しやすいプロセスです。6つ以上の入力変数には適しておらず、4つまでの変数に対してのみ実用的であり、複数の出力関数の積項の共有はさらに困難です。[10]さらに、この方法は、コンピュータープログラムの形で自動化するのに適していません。ただし、現代の論理関数は一般にそのような少数の変数に制限されず、コストとエラーのリスクが論理関数の手動実装に法外であるため、コンピューターの使用が不可欠になりました。
最初に普及した代替手法は、ウィラード・クワインとエドワード・マクラスキーが開発した表法である。一連の論理関数の真理値表から始めて、関数がアクティブになる最小項（ONカバー）または関数値が無関係な最小項（ドントケアカバーまたはDCカバー）を組み合わせることで、一連の主項が構成される。最後に、出力関数を実現できる最小の主項セットを見つけるための体系的な手順が実行される。[11] [12]
このクワイン・マクラスキー法はコンピュータプログラムに実装するのに非常に適していますが、処理時間とメモリ使用量の点では依然として効率的とは言えません。関数に変数を追加すると、真理値表の長さは変数の数に応じて指数関数的に増加するため、どちらも約 2 倍になります。組み合わせ関数ブロックの出力関数の数を増やすと、同様の問題が発生します。その結果、クワイン・マクラスキー法は、入力変数と出力関数の数が限られている関数にのみ実用的です。
ESPRESSOアルゴリズム
この問題に対する別のアプローチは、カリフォルニア大学バークレー校のブレイトンらが開発したESPRESSOアルゴリズムで採用されています。[4] [3]これは、ヒューリスティックなハザードフリーの2レベルロジック最小化問題を解決することを目的とした、リソースとパフォーマンスを効率的に使用するアルゴリズムです。 [13]
プログラムは、論理関数を最小項に拡張するのではなく、ON カバー、DC カバー、および OFF カバーの積項を反復的に表す「キューブ」を操作します。最小化の結果がグローバル最小値になることは保証されませんが、実際にはこれは非常に近い近似値であり、ソリューションには常に冗長性がありません。他の方法と比較して、この方法は本質的に効率的であり、メモリ使用量と計算時間を数桁削減します。その名前は、淹れたてのコーヒーを瞬時に淹れる方法を反映しています。組み合わせ関数ブロックの変数、出力関数、積項の数にはほとんど制限がありません。一般に、たとえば数十の変数と数十の出力関数を簡単に処理できます。
ESPRESSO への入力は、必要な機能の関数テーブルです。結果は、選択したオプションに応じて、関数のオンカバーまたはオフカバーのいずれかを記述する最小化されたテーブルです。デフォルトでは、積項は複数の出力関数によって可能な限り共有されますが、プログラムに各出力関数を個別に処理するように指示することもできます。これにより、PLA (プログラマブル ロジック アレイ) やPAL (プログラマブル アレイ ロジック) などの 2 レベル ロジック アレイでの効率的な実装が可能になります。
ESPRESSO アルゴリズムは非常に効果的であることが証明されたため、事実上あらゆる現代のロジック合成ツールに標準的なロジック関数最小化ステップとして組み込まれています。マルチレベル ロジックで関数を実装する場合、最小化の結果は因数分解によって最適化され、フィールド プログラマブル ゲート アレイ(FPGA) または特定用途向け集積回路(ASIC)のいずれの場合も、対象テクノロジで利用可能な基本ロジック セルにマッピングされます。
ソフトウェア
エスプレッソ
オリジナルのESPRESSOプログラムは、カリフォルニア大学バークレー校のウェブサイトからCソースコードとして入手できます。最終リリースは1988年のバージョン2.3です。[14] ESPRESSO -ABおよびEQNTOTT （真理値表への方程式）プログラムは、現代のPOSIXシステム向けのESPRESSOの更新バージョンであり、 Cソースコードと同様にDebian Linuxディストリビューション（.deb）ファイル形式で入手できます。最終リリースは2008年のバージョン9.0です。 [15] WindowsおよびC++20互換のものが2020年にGitHubに移植されました。[16]
ロジックフライデー
Logic Friday は、 Espresso や Berkeley Octtools パッケージの別のモジュールである misII にグラフィカル インターフェイスを提供する無料のWindowsプログラムです。Logic Friday を使用すると、ユーザーは論理関数を真理値表、方程式、またはゲート ダイアグラムとして入力し、関数を最小化して、他の 2 つの表現の両方で結果を表示できます。最後のリリースは 2012 年のバージョン 1.1.4 です。 [17]
ミニログ
Minilog は、この Espresso アルゴリズムを利用してロジックの最小化を実現する無料の Windows プログラムです。最大 40 の入力と出力を持つ組み合わせ関数ブロック、または最大 256 の状態を持つ同期ステート マシンの 2 レベル ゲート実装を生成できます。これはPublicad教育設計パッケージ の一部です。
エスプレッソ
ESPRESSO-IISOJS は、単一出力関数用の ESPRESSO-II の JavaScript 実装です。これは、ユニート再帰パラダイムに基づく ESPRESSO-II のさまざまなアルゴリズムに対する追加の最適化手法として、単位伝播を採用しています。もう 1 つの追加機能は、リテラルをいつ発生させるかを制御できるようにすることで、クリーネ論理関数を効果的に最小化するために利用できます。 [18]
参考文献
- ^ ヘイズ、ジョン・パトリック（1993）。デジタルロジックデザイン。アディソンウェスリー。ISBN 0-201-15461-7。
- ^ Brayton, Robert King; Hachtel, Gary D.; Hemachandra, Lane A.; Newton, A. Richard; Sangiovanni-Vincentelli, Alberto Luigi M. (1982). 「ESPRESSO を使用したロジック最小化戦略の比較: 分割ロジックシミュレーション用の APL プログラムパッケージ」。1982年の IEEE 国際回路システムシンポジウムの議事録。米国ニューヨーク州ニューヨーク: IEEE : 42–48。
- ^ ab “Robert K. Brayton; 名誉教授、大学院教授”.カリフォルニア大学バークレー校. 2018-09-23. 2018-09-23時点のオリジナルよりアーカイブ。 2018-09-23に閲覧。
- ^ ab ブレイトン、ロバート・キング、ハクテル、ゲイリー・D.、マクマレン、カーティス・トレイシー、サンジョヴァンニ・ヴィンセンテッリ、アルベルト・ルイージ・M. (1984)。VLSI 合成のためのロジック最小化アルゴリズム (2000 年第 9 刷、第 1 版)。米国マサチューセッツ州ボストン: Kluwer Academic Publishers。ISBN 0-89838-164-9。
- ^ ab Bolton, Martin (1990)。「4.3.3 ESPRESSO-II」。英国ブリストルのブリストル大学で執筆。Dagless, Erik L. (編)。プログラム可能なロジックによるデジタルシステム設計。電子システムエンジニアリングシリーズ (第 1 版)。英国ウォキンガム: Addison -Wesley Publishers Ltd。pp. 112、115–116。ISBN 0-201-14545-6. LCCN 90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r . 2021年4月17日閲覧。
- ^ Rudell, Richard L. (1986-06-05). 「PLA 合成のための多値ロジックの最小化」(PDF)。覚書番号 UCB/ERL M86-65。米国バークレー。
- ^ Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi M. (1987 年 9 月)。「PLA 最適化のための多値ロジック最小化」。IEEE Transactions on Computer-Aided Design。6 ( 5): 727–750。doi : 10.1109 /TCAD.1987.1270318。S2CID 13525177 。
- ^ Rudell, Richard L. (1989 年 4 月). VLSI 設計のための論理合成(博士論文). バークレー:カリフォルニア大学.（エスプレッソ・エグザクト）
- ^ De Micheli, Giovanni (1994).デジタル回路の合成と最適化. McGraw-Hill Science Engineering . ISBN 0-07-016333-2。
- ^ ルーウィン、ダグラス (1985)。ロジックシステムの設計。ヴァン・ノストランド(英国) 。ISBN 0-442-30606-7。
- ^ Katz, Randy Howard ; Borriello, Gaetano (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company . ISBN 0-8053-2703-7。
- ^ Lala, Parag K. (1996). 実践的なデジタルロジック設計とテスト. Prentice Hall . ISBN 0-02-367171-8。
- ^ Theobald, Michael; Nowick, Steven M. (1998). 2レベルハザードフリーロジック最小化のための高速ヒューリスティックアルゴリズムと正確なアルゴリズム。コロンビア大学（レポート）。doi : 10.7916/D8N58V58 。 2021年10月4日閲覧。
- ^ 「Espresso C ソースコード (1988)」。カリフォルニア大学バークレー校。2018年9月21日。2018年9月21日時点のオリジナルよりアーカイブ。 2018年9月21日閲覧。
- ^ 「Espresso-eb / eqntott C ソースコードとプログラム (2008)」。Google Code。2018年9月21日。2018年9月21日時点のオリジナルよりアーカイブ。 2018年9月21日閲覧。
- ^ 「Espresso ヒューリスティック ロジック ミニマイザー C++20 Windows ソース」。GitHub。
- ^ “Logic Friday program (2012)”. sontrak . 2018年9月21日. 2013年10月22日時点のオリジナルよりアーカイブ。 2018年9月21日閲覧。
- ^ 「Espresso-IISOJS」。GitHub。
さらに読む
- エッシャーマン、ベルンハルト (1993 年 5 月)。Funktionaler Entwurf Digitaler Schaltungen - Methoden und CAD-Techniken [デジタル回路の機能設計 - 方法と CAD テクニック]。 Springer-Lehrbuch (ドイツ語)。スプリンガー・フェルラーグ。 136–137、140–141ページ。ISBN 9-783540-56788-2. ISBN 3-540-56788-7 .