カルノー図

上記の例では、4つの入力変数は16通りの組み合わせが可能であるため、真理値表は16行、カルノー図は16の位置を持ちます。したがって、カルノー図は4  ×  4のグリッド状に配置されます。

カルノー図の上部と左側に表示されている行と列のインデックスは、二進数ではなくグレイコードで並んでいます。グレイコードを用いることで、隣接するセル間で変化する変数は必ず1つだけになります。完成したカルノー図の各セルには、入力の組み合わせに対する関数の出力を表す二進数が格納されています。

カルノー図が作成された後、真理値表の情報に対して、可能な限り最も単純な形式（標準形）を見つけるために使用されます。カルノー図の隣接する 1 は、式を単純化する機会を表します。最終的な式の最小項（minterms）は、カルノー図の 1 のグループを囲むことによって見つけられます。最小項グループは長方形でなければならず、面積は 2 のべき乗（つまり、 1、2、4、8 ...）でなければなりません。最小項の長方形は 、 0 を含まない範囲でできるだけ大きくする必要があります。各グループを大きくするために、グループは重なり合うことができます。以下の例では、最適なグループ分けが緑、赤、青の線で示されており、赤と緑のグループは重なっています。赤のグループは 2  ×  2 の正方形、緑のグループは 4  ×  1 の長方形で、重なり合う領域は茶色で示されています。

セルは、そのセルがカバーする入力の論理値を表す略記法で示されることが多い。例えば、AD は、 AとD が真となる2x2 の領域をカバーするセル、つまり上の図の 13、9、15、11 番のセルを意味する。一方、A D は、 Aが真でDが偽となるセル（つまり、Dが真となるセル）を意味する。

グリッドはトーラス状に接続されているため、長方形のグループが端をまたいで折り返されます（図を参照）。右端のセルは、対応する入力値が1ビットだけ異なるという意味で、実際には左端のセルと「隣接」しています。同様に、最上部のセルと最下部のセルも隣接しています。したがって、A D は有効な用語となり得ます。これは上部のセル12と8を含み、下部に折り返してセル10と14を含みます。同様に、B Dも有効な用語であり、これは4つの角を含みます。

カルノー図が作成され、隣接する1が長方形と正方形のボックスでリンクされたら、各ボックス内でどの変数が変化しないかを調べることで、代数的な最小項を見つけることができます。

赤色のグループについて：

• Aはボックス全体で同じであり、1に等しいので、赤い最小項の代数表現に含める必要があります。
• Bは同じ状態を維持しないため（1から0に変化する）、除外されるべきである。
• Cは変化しません。常に0なので、その補数であるNOT-Cを含める必要があります。したがって、Cを含めるべきです。
• Dは変化するため、除外される。

したがって、ブール積和式の最初の最小項はA Cです。

緑色のグループでは、AとBは同じ状態を維持し、CとDが変化します。Bは0なので、含める前に負にする必要があります。したがって、2番目の項はABとなります。緑色のグループが赤色のグループと重なっても問題ないことに注意してください。

同様に、青色のグループはBC Dという用語を与えます。

各グループの解を組み合わせると、回路の標準形は次のようになります。${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}$。

このようにカルノー図は、

${\displaystyle {\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned}}}$

ブール代数の公理を注意深く適用することによってもこの簡略化を導き出すことは可能であったが、そのためには項の数に応じて指数関数的に時間がかかる。

関数の逆関数は、0をグループ化することで同様の方法で解くことができます。^{[注1 ]}

逆数を表す3つの項はすべて、異なる色の枠線が付いた灰色のボックスで示されています。

• 茶色：A B
• 金：A C
• 青：BCD

これは逆の結果をもたらす。

${\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}$

ド・モルガンの法則を用いることで、和の積を求めることができる。

${\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {BCD}}\right)\\&=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)\end{aligned}}}$

カルノー図は、真理値表に「無関心条件」が含まれる関数の最小化を容易にします。「無関心条件」とは、設計者が出力結果を気にしない入力の組み合わせのことです。したがって、「無関心条件」は、任意の矩形グループに含めることも除外することもできます。どちらにしても、グループが大きくなる方を選びます。通常、カルノー図上ではダッシュまたはXで示されます。

右側の例は、上の例と同じですが、f (1,1,1,1)の値が「不定値」に置き換えられています。これにより、赤い項が下まで展開され、結果として緑の項が完全に削除されます。

これにより、新しい最小値方程式が得られます。

${\displaystyle f(A,B,C,D)=A+BC{\overline {D}}}$

最初の項は単にAであり、A Cではないことに注意してください。この場合、ドントケアは項 (緑色の四角形) を削除し、別の項 (赤色の四角形) を単純化し、レースハザード (次のレースハザードのセクションで説明するように黄色の項を削除) を除去しています。

逆の場合については、以下のように簡略化できます。

${\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}D}$

ド・モルガンの法則を用いることで、和の積を求めることができる。

${\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}\,D}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {{\overline {A}}\,D}}\right)\\&=\left(A+B\right)\left(A+C\right)\left(A+{\overline {D}}\right)\end{aligned}}}$

カルノー図は、競合状態を検出して排除するのに役立ちます。カルノー図を使用すると、競合状態は非常に簡単に見つけることができます。なぜなら、マップ上で囲まれた隣接しているが互いに分離している領域間で移動する際に、競合状態が発生する可能性があるからです。ただし、グレイ符号化の性質上、隣接には上記で説明した特別な定義があります。実際には、長方形ではなく、上部、下部、側面を囲むトーラス上を移動していることになります。

• 上記の例では、CとDが両方とも0、Aが1、Bが1から0に変化する（青色の状態から緑色の状態へ移行する）場合に、潜在的な競合状態が発生します。この場合、出力は1のまま変化しないように定義されていますが、この遷移は方程式内の特定の項でカバーされていないため、グリッチ（出力が一時的に0に遷移する）が発生する可能性があります。
• 同じ例には、見つけにくいもう一つの潜在的な不具合があります。それは、 Dが0で、AとBが両方とも1であり、Cが1から0に変化する（青色の状態から赤色の状態に移行する）場合です。この場合、不具合はマップの上部から下部へと一周します。

実際に不具合が発生するかどうかは実装の物理的な性質に依存し、それを気にする必要があるかどうかはアプリケーションに依存します。クロック制御ロジックでは、ロジックがタイミング期限内に目的の値に落ち着けば十分です。今回の例では、クロック制御ロジックは考慮していません。

私たちの場合、追加の項は${\displaystyle A{\overline {D}}}$緑と青の出力状態、または青と赤の出力状態の間の橋渡しをすることで、潜在的な競合の危険性を排除します。これは、隣の図の黄色の領域（右半分の下から上までを囲む部分）として示されています。

この用語はシステムの静的な論理の観点からは冗長だが、このような冗長な、あるいは合意に基づく用語は、競合のない動的なパフォーマンスを保証するためにしばしば必要となる。

同様に、${\displaystyle {\overline {A}}D}$別の潜在的なレースハザードを排除するために、逆数に加算する必要があります。ド・モルガンの法則を適用すると、fの別の積和表現が生成されますが、新しい因子が加わります。${\displaystyle \left(A+{\overline {D}}\right)}$。

以下は、可能なすべての 2 変数、2  ×  2 カルノー図です。各カルノー図には、 の関数としての最小項がリストされています。${\textstyle \sum m()}$そして、レースハザードフリー（前のセクションを参照）の最小方程式。 ミニタームは、マッピングされた変数の最も最小の形式の式として定義されます。 可能なすべての水平方向および垂直方向の相互接続ブロックを形成できます。 これらのブロックは、2 のべき乗 (1、2、4、8、16、32、...) のサイズでなければなりません。 これらの式は、マッピングされるバイナリ式の最小論理変数式の最小論理マッピングを作成します。 以下は、1 つのフィールドを持つすべてのブロックです。

ブロックは、チャートの下、上、左、右にまたがって継続できます。変数最小化のために、チャートの端を超えて折り返すこともできます。これは、各論理変数が各垂直列と水平行に対応しているためです。kマップの視覚化は円筒形と考えることができます。左端と右端のフィールドは隣接しており、上端と下端も隣接しています。4変数のKマップは、ドーナツまたはトーラスの形状で表現する必要があります。kマップによって描画される正方形の4つの角は隣接しています。5変数以上の場合は、さらに複雑なマップが必要です。

• 
  Σ m (0); K = 0
• 
  Σ m (1); K = A ′ B ′
• 
  Σ m (2); K = AB ′
• 
  Σ m (3); K = A ′ B
• 
  Σ m (4); K = AB
• 
  Σ m (1,2); K = B ′
• 
  Σ m (1,3); K = A ′
• 
  Σ m (1,4); K = A ′ B ′ + AB
• 
  Σ m (2,3); K = AB ′ + A ′ B
• 
  Σ m (2,4); K = A
• 
  Σ m (3,4); K = B
• 
  Σ m (1,2,3); K = A' + B ′
• 
  Σ m (1,2,4); K = A + B ′
• 
  Σ m (1,3,4); K = A ′ + B
• 
  Σ m (2,3,4); K = A + B
• 
  Σ m (1,2,3,4); K = 1