カルノー図とドントケアの条件

真理値表を実装コストにつなげる

真理値表^{i真理値表 可能な入力組合せをすべて列挙し、各組合せの出力を記した表です。時間に伴う変化は波形で別途確認します。 詳しく見る}が機能を定義するのに対し、論理最小化はそれをどの式で実装するかを決める段階です。入力が三つの場合、最小項番号を A が最上位ビットの二進数 ABC で定義します。

例えば最小項 4 は ABC=100 です。列挙されていない 0・2・6 では出力は 0 です。五つの積項をそのまま実装する代わりに、一つのビットだけが異なる項をまとめられます。

カルノー図は並び順を変えた真理値表です

列を BC=00、01、11、10 の順に配置します。これは隣の列との間で一つのビットだけが変わるグレイコード順です。左端と右端も隣接します。

グループは長方形で、セル数は $1,2,4,8,\ldots$ でなければなりません。0 のセルを含めると機能が変わります。同じ 1 を複数グループに含めることは許されます。

1. C=1 の二列、四つのセルをまとめると、A と B が変わっても出力は 1 です。残る項は C です。
2. A=1 の行の BC=00 と 01 をまとめると、C だけが変わります。残る項は $A\overline B$ です。
3. 二つのグループを OR すると、すべての 1 を覆い、すべての 0 を避けられます。

元の定義と最小化した式を八つの入力で照合してください。式が短くなったことと機能が同じことを、別々に確認する習慣が大切です。

次の流れは、上のカルノー図の二つのグループを式に変える過程です。C のグループでは A と B が、二セルのグループでは C が変わるので、それらの変数を項から除きます。

ドントケアは最適化の自由であり、入力の仮定です

システムの取り決めにより ABC=000 は決して入らないと仮定します。このセルを X にすると、必要に応じて 0 または 1 として使えます。B=0 の四セルをまとめると、さらに簡単な式になります。

新しい式は ABC=000 で 1 です。元の完全な真理値表とは異なります。したがって「同じ回路」と言うには、入力が 000 ではないという条件を含める必要があります。初期化中やエラー回復中に 000 が現れるなら、この最適化はシステム要求を壊すおそれがあります。

式の最小化とチップの最小化は異なります

リテラルの少ない式が、特定の標準セルライブラリで面積・遅延・電力まで常に最適とは限りません。負荷・ファンアウト・使用可能な複合ゲート・配線・グリッチが結果に影響します。ここでは機能等価性と入力の仮定を明確にし、物理コストは合成・タイミング結果で判断します。

参考資料：MIT OpenCourseWare — Combinational Logic

実習 · グループの重なりとドントケアの条件を確かめる

1. C のグループを押します。四セル内で A と B がともに変わるため、C だけが残ります。
2. A·¬B のグループを押します。m4 と m5 を覆い、m5 は C のグループと重なります。重なりは許されますが、0 のセルを含めてはいけません。
3. m0 を二度押し、0 → 1 → X と変えます。X になると d(0) を含む不完全な仕様になります。B=0 のグループが広がり、式は $C+\overline B$ になります。
4. m0 をもう一度押して 0 に戻します。元の要求を復元したので、大きなグループは消えるはずです。

グループの選択は値の変更ではありません。すべての 1 を覆う式全体は維持し、今見ている一つの項だけを枠で強調します。ここでの「最小」は積項数を優先し、次にリテラル数で判断します。解が複数ある場合はその一つを表示します。