ロジックの最適化

ロジック最適化は、1 つ以上の指定された制約の下で、指定されたロジック回路の同等の表現を見つけるプロセスです。このプロセスは、デジタル エレクトロニクスおよび集積回路設計に適用されるロジック合成の一部です。

一般的に、回路は、事前に定義された応答遅延を満たす最小のチップ面積に制約されます。特定の回路のロジック最適化の目標は、元の回路と同じ値に評価される最小のロジック回路を取得することです。 ^[1]通常、同じ機能を持つ小さな回路はより安価で、^[2]占有スペースが少なく、消費電力が少なく、レイテンシが短く、予期しないクロストークのリスク、遅延信号処理の危険性、および集積回路上の金属構造のナノスケールレベルに存在するその他の問題を最小限に抑えます。

ブール代数の観点から見ると、複雑なブール式の最適化とは、評価すると最終的に元の式と同じ結果が生成される、より単純な式を見つけるプロセスです。

複雑な回路（論理ゲートなど、多くの要素を持つ回路）の問題は、各要素が物理的なスペースを占め、製造に時間と費用がかかることです。回路の最小化は、集積回路内の複雑なロジックの領域を削減するために使用されるロジック最適化の 1 つの形式である可能性があります。

論理合成の出現により、電子設計自動化(EDA) 業界が直面した最大の課題の 1 つは、与えられた設計記述の最も単純な回路表現を見つけることでした。^{[nb 1]} 2 レベル論理最適化 は、 Quine–McCluskey アルゴリズムの形で長い間存在し、その後Espresso ヒューリスティック論理最小化器が続きましたが、チップ密度の急速な向上と回路記述のためのハードウェア記述言語の広範な採用により、 Logic Friday (グラフィカル インターフェイス)、Minilog、ESPRESSO-IISOJS (多値論理)など、今日存在する論理最適化ドメインが形式化されました。 ^[3]

論理回路の簡略化の方法は、ブール式の最小化にも同様に適用できます。

現在、ロジックの最適化はさまざまなカテゴリに分類されています。

回路表現に基づく

2レベルロジック最適化

マルチレベルロジック最適化

回路特性に基づく

シーケンシャルロジックの最適化

組み合わせロジックの最適化

実行の種類に基づいて

グラフィカル最適化手法

表形式の最適化手法

代数最適化法

グラフィカル手法では、必要な論理関数を、論理変数と関数の値を表す図で表します。図を操作または検査することで、面倒な計算を大幅に削減できます。2 レベル ロジックのグラフィカル最小化手法には、次のものがあります。

• オイラー図（別名オイラー円）（1768年）レオンハルト・P・オイラー（1707年 - 1783年）
• ジョン・ベン(1834–1923)によるベン図(1880 年)
• モーリス・カーノーによるカーノー地図（1953年）

以下にリストされているブール式の最小化（簡略化）と同じ方法を回路の最適化に適用できます。

ブール関数が回路によって指定される場合（つまり、可能な限り最小サイズの等価回路を見つけたい場合）、無制限回路最小化問題は時間計算量において-完全であると長い間推測され、その結果は最終的に2008年に証明されましたが、^[4]カルノー図やクワイン・マクラスキーアルゴリズムなどのプロセスを容易にする効果的なヒューリスティックがあります。 ${\displaystyle \Sigma _{2}^{P}}$

ブール関数を最小化するメソッドには次のものがあります。

• クワイン・マクラスキーアルゴリズム
• ペトリック法

ブール関数の最適な回路表現を見つける方法は、文献ではしばしば正確な合成と呼ばれます。計算の複雑さのため、正確な合成は小さなブール関数に対してのみ扱い可能です。最近のアプローチでは、最適化問題をブールの充足可能性問題にマッピングします。^{[5] [6]これにより、} SATソルバーを使用して最適な回路表現を見つけることができます。

ヒューリスティック法では、確立されたルールを使用して、はるかに大きな問題セットのうち、実際に役立つサブセットを解決します。ヒューリスティック法では、理論的に最適なソリューションは得られないかもしれませんが、役立つ場合は、最小限の労力で必要な最適化のほとんどが実現されます。ロジックの最適化にヒューリスティック法を使用するコンピュータ システムの例としては、Espressoヒューリスティック ロジック ミニマイザーがあります。

回路の 2 レベル回路表現は厳密には SOP (積和) の観点から回路を平坦化したビューを指しますが (これは設計のPLA実装により当てはまります^{[明確化が必要]) 、マルチレベル表現は任意に接続された SOP、POS (}積和)、因数分解形式などの観点から回路をより一般的に表示します。ロジック最適化アルゴリズムは一般に、回路の構造表現 (SOP、因数分解形式) または機能表現 (二分決定図、代数決定図) のいずれかに基づいて機能します。積和 (SOP) 形式では、AND ゲートが最小単位を形成し、OR を使用してつなぎ合わされますが、積和 (POS) 形式ではその逆になります。POS 形式では、OR の優先順位が AND よりも低いため、OR 項を AND ゲートの下にグループ化するために括弧が必要です。SOP 形式と POS 形式はどちらも回路ロジックにうまく変換されます。

2つの関数F ₁とF _{2 が}あるとします。

${\displaystyle F_{1}=AB+AC+AD,\,}$

${\displaystyle F_{2}=A'B+A'C+A'E.\,}$

上記の 2 レベル表現では、CMOS Rep で 6 つの積項と 24 個のトランジスタが必要になります。

マルチレベルで機能的に同等の表現は次のようになります。

P = B + Cです。

F ₁ = AP + ADです。

F ₂ = A'P + A'Eです。

ここでのレベル数は 3 ですが、項 B + C が共有されるため、 積項とリテラルの合計数は減少します^{[定量化]。}

同様に、組み合わせ回路と順序回路を区別します。組み合わせ回路は、現在の入力のみに基づいて出力を生成します。ブール関係で表すことができます。例としては、プライオリティ エンコーダ、バイナリ デコーダ、マルチプレクサ、デマルチプレクサなどがあります。

シーケンシャル回路は、クロック信号に応じて、現在の入力と過去の入力の両方に基づいて出力を生成します。これは、以前の入力と現在の入力を区別するために使用されます。これらは有限ステート マシンで表すことができます。例としては、フリップフロップやカウンターなどがあります。

回路を最小化する方法はたくさんありますが、これはブール関数を最小化（または簡略化）する例です。回路によって実行されるブール関数は、関数が実装される代数式に直接関係しています。^[7] を表すために使用される回路を考えてみましょう。このステートメントでは、2つの否定、2つの結合、および1つの選言が使用されていることは明らかです。つまり、回路を構築するには、2つのインバータ、2つのANDゲート、および1つのORゲートが必要になります。 ${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}$

この回路は、ブール代数の法則を適用するか、直感を使うことで簡略化（最小化）できます。例では、が偽のときは が真であり、その逆も成り立つと述べているため、これは単に を意味すると結論付けることができます。論理ゲートでは、不等式は単にXOR ゲート（排他的論理和）を意味します。したがって、 です。次に、以下に示す 2 つの回路は、真理値表を使用して確認できるように同等です。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A\neq B}$${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$

• 二分決定図(BDD)
• 気にしない状態
• 主項
• 回路の複雑さ— 回路の複雑さの推定について
• 関数合成
• 関数分解
• ゲートの活用不足
• ロジックの冗長性
• ハーバード最小化チャート(Wikiversity) (Wikibooks)

• リンド、ラリー・フレデリック、ネルソン、ジョン・クリストファー・カンリフ（1977）。シーケンシャルデジタルシステムの分析と設計。マクミラン出版。ISBN 0-33319266-4。（146ページ）
• De Micheli, Giovanni (1994)。デジタル回路の合成と最適化。McGraw - Hill。ISBN 0-07-016333-2。(注: 第 7 章から第 9 章では、組み合わせ 2 レベル、組み合わせ多レベル、および順次回路の最適化について説明します。)
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996].論理合成および検証アルゴリズム. Springer Science & Business Media . ISBN 978-0-387-31005-3。
• Kohavi, Zvi; Jha, Niraj K. (2009). 「4–6」.スイッチングと有限オートマトン理論(第 3 版). Cambridge University Press . ISBN 978-0-521-85748-2。
• Rutenbar, Rob A. マルチレベル最小化、パート I: モデルと方法(PDF) (講義スライド)。カーネギーメロン大学(CMU)。講義 7。2018年 1 月 15 日にオリジナルからアーカイブ(PDF) 。2018年 1 月 15 日に取得。 Rutenbar, Rob A. マルチレベル最小化、パート II: キューブ/コカーネル抜粋(PDF) (講義スライド)。カーネギーメロン大学(CMU)。講義 8。2018年 1 月 15 日にオリジナルからアーカイブ(PDF) 。2018年 1 月 15 日に取得。