ロジック最適化

論理最適化とは、指定された論理回路を、一つまたは複数の制約条件の下で等価な表現で表すプロセスです。このプロセスは、デジタルエレクトロニクスや集積回路設計において用いられる論理合成の一部です。

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

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

複雑な回路（論理ゲートなど、多くの要素を持つ回路）の問題点は、各要素が物理的なスペースを占有し、製造に時間とコストがかかることです。回路の最小化は、集積回路における複雑な論理回路の面積を削減するために用いられる論理最適化の一形態と言えるでしょう。

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

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

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

回路は、ブール代数の法則を適用するか、直感を用いることで簡略化（最小化）できます。例では、${\displaystyle A}$の場合に真となる${\displaystyle B}$これは偽であり、その逆もまた、これは単に${\displaystyle A\neq B}$論理ゲートの観点から言えば、不等号は単にXOR ゲート(排他的論理和) を意味します。したがって、${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$すると、真理値表を用いて確認できるように、以下の2つの回路は等価である。

• 二分決定図（BDD）
• 気にしない状態
• 主インプリカント
• 回路の複雑さ― 回路の複雑さの推定について
• 機能構成
• 関数分解
• ゲートの利用率が低い
• 論理冗長性
• ハーバード最小化チャート(Wikiversity) (Wikibooks)

• リンド、ラリー・フレデリック；ネルソン、ジョン・クリストファー・カンリフ（1977）。『逐次デジタルシステムの解析と設計』マクミラン出版。ISBN 0-33319266-4。（146ページ）
• デ・ミケーリ、ジョヴァンニ（1994）。デジタル回路の合成と最適化。マグロウヒル。ISBN 0-07-016333-2。（注：第7章～第9章では、それぞれ組み合わせ2レベル、組み合わせ多レベル、および逐次回路の最適化について解説しています。）
• ハクテル、ゲイリー・D.、ソメンツィ、ファビオ（2006）[1996]。論理合成と検証アルゴリズム。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-0-387-31005-3。
• コハヴィ、ツヴィ。ジャー、ニラジ K. (2009)。 「4～6」。スイッチングと有限オートマトン理論(第 3 版)。ケンブリッジ大学出版局。ISBN 978-0-521-85748-2。
• Rutenbar, Rob A.多段階最小化、パート I: モデルと方法(PDF) (講義スライド)。カーネギーメロン大学(CMU)。講義 7。2018-01-15のオリジナルからアーカイブ(PDF) 。2018-01-15に取得。Rutenbar, Rob A.多段階最小化、パート II: 立方体/コカーネル抽出(PDF) (講義スライド)。カーネギーメロン大学(CMU)。講義 8。2018-01-15のオリジナルからアーカイブ(PDF) 。2018-01-15に取得。