エスプレッソヒューリスティックロジック最小化ツール

すべてのデジタルシステムは、情報を記憶するためのメモリ要素と、その情報を変換する組み合わせ回路という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カバー）または関数値が無関係な最小項（Don't-CareカバーまたはDCカバー）を組み合わせることにより、プライムインプリカントのセットが構成されます。最後に、出力関数を実現できる最小のプライムインプリカントのセットを見つけるための体系的な手順が実行されます。^{[ 11 ] [ 12 ]}

このクワイン・マクラスキーアルゴリズムはコンピュータプログラムへの実装に非常に適しているものの、処理時間とメモリ使用量の面では依然として効率性に欠ける。関数に変数を追加すると、真理値表の長さが変数の数に対して指数関数的に増加するため、処理時間とメモリ使用量はほぼ倍増する。組み合わせ関数ブロックの出力関数の数を増やす場合にも同様の問題が発生する。したがって、クワイン・マクラスキー法は、入力変数と出力関数の数が限られている関数にのみ実用的である。

この問題に対する別のアプローチは、カリフォルニア大学バークレー校のBraytonらが開発したESPRESSOアルゴリズムで採用されている。^{[ 4 ] [ 3 ]}これは、ヒューリスティックなハザードフリーの2レベル論理最小化問題を解決することを目的とした、リソースとパフォーマンスに優れたアルゴリズムである。 ^{[ 13 ]}

論理関数を最小項に展開するのではなく、このプログラムは、ON、DC、OFF カバー内の積項を表す「キューブ」を反復的に操作します。最小化の結果がグローバル最小値であるとは保証されませんが、実際には非常に近い値に近似され、解は常に冗長性がありません。他の方法と比較すると、この方法は本質的に効率的で、メモリ使用量と計算時間を数桁削減します。その名前は、淹れたてのコーヒーを瞬時に作る方法を反映しています。組み合わせ関数ブロックの変数、出力関数、積項の数にはほとんど制限がありません。一般に、たとえば数十個の変数と数十個の出力関数は容易に処理できます。

ESPRESSOへの入力は、目的の機能を示す機能表です。出力は、選択されたオプションに応じて、機能のオンカバーまたはオフカバーを記述する最小化された表です。デフォルトでは、複数の出力機能間で製品用語が可能な限り共有されますが、各出力機能を個別に処理するようにプログラムに指示することもできます。これにより、PLA（プログラマブルロジックアレイ）やPAL（プログラマブルアレイロジック）などの2レベルロジックアレイでの効率的な実装が可能になります。

ESPRESSOアルゴリズムは非常に優れた成果を上げたため、現在ではほぼすべての論理合成ツールに標準的な論理関数最小化ステップとして組み込まれています。多値論理で関数を実装する場合、最小化結果は因数分解によって最適化され、フィールドプログラマブルゲートアレイ（FPGA）または特定用途向け集積回路（ASIC）といった対象技術における利用可能な基本論理セルにマッピングされます。

オリジナルのESPRESSOプログラムは、カリフォルニア大学バークレー校のWeb サイトから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 ]}

Python EDAは、Espressoロジック最小化のバインディングを含む電子設計自動化のためのPythonライブラリです。^{[ 19 ]}