カルノー図:視覚的なブール簡略化

TL;DR: カルノー図(K マップ)は真理値表をグレイコードによる 2 次元グリッドへ並べ替え、隣接するセルが 1 つの変数だけ異なるようにします。隣接する 1 を 2 のべき乗の長方形にグループ化することで、代数操作なしに最小の積和形を直接生成できます。K マップは 4 変数までの関数を確実に最小化します。5〜6 変数では Quine-McCluskey 法、それ以上では ESPRESSO スタイルのアルゴリズム合成が引き継ぎます。

ブール法則を使った代数的簡略化は機能しますが、適切なタイミングで適切な因数分解を見抜くことに依存します。一つの機会を逃せば、最適でない結果に終わってしまいます。4 変数以上の式では、可能な操作の数が爆発的に増えます。

カルノー図(K マップ)は、代数的簡略化を視覚的なパターン認識に変えることでこの問題を解決します。1953 年にベル研究所の物理学者モーリス・カルノーが考案したこの図は、真理値表を 2 次元グリッドに並べ、隣接セルが厳密に 1 つの変数だけ異なるようにします。グリッド上で隣接する 1 をグループ化することで、代数操作なしに直接、最小の積和形が得られます。

AND ゲートコンポーネント図

視覚化された真理値表:K マップとは何か

本質的にカルノー図は変装した真理値表です。標準の真理値表が入力と出力を線形・縦方向に並べるのに対し、K マップはそれらを 2 次元のグリッドに並べ替えます。これは見栄えのためだけではありません。K マップの真価は、セルの特定の配置の中にあります。

標準の真理値表では、行は二進カウント(00、01、10、11)に従います。K マップでは、行と列は グレイコード と呼ばれる順序に従います。グレイコード列では、隣接する番号 ── 水平方向に動くか垂直方向に動くかにかかわらず ── 1 ビットだけ異なります。論理的隣接性 と呼ばれるこの性質が、簡略化を駆動するエンジンです。「1」を含む隣接セルをグループ化するとき、変化する(したがって結果に影響しない)変数を視覚的に特定し、それらを除去して最小のブール項を残すのです。

現代の ALU 設計で使われる複雑な 4 変数マップに飛び込む前に、入力 $A$ と $B$ に対する基本的な 2 変数マップを見てみましょう。これは $2^2 = 4$ セルからなり、4 通りの可能なミンタームを表します。

	$B=0$ ( $\overline{B}$ )	$B=1$ ( $B$ )
$A=0$ ( $\overline{A}$ )	$m_0$ ( $\overline{A}\overline{B}$ )	$m_1$ ( $\overline{A}B$ )
$A=1$ ( $A$ )	$m_2$ ( $A\overline{B}$ )	$m_3$ ( $AB$ )

隣接性に注目してください: $m_0$ から $m_1$ への移動では変数 $B$ だけが変化します。 $m_1$ から $m_3$ への移動では変数 $A$ だけが変化します。グリッド上のこの物理的近接性は、ゲート数を減らすために活用できる論理的関係を表しています。

基本論理を実際に見る

グループ化の技術:マップから最小論理へ

K マップ使用の目標は、可能な限り大きな長方形のグループでマップ上のすべての「1」をカバーすることです。ただし条件があります:各グループのセル数は 2 のべき乗(1、2、4、8、16…)でなければなりません。各グループは簡略化された積項に対応し、最終的な最適化済み式は単にそれらのグループの結果を OR で結合した「積和形」となります。

グループ化規則は厳格ですが分かりやすく、機械的に従えば最小の結果が保証されます。

すべての「1」をカバーする:マップ上のすべての「1」は少なくとも 1 つのグループに属す必要があります。グループ化されない「1」があってはなりません。
2 のべき乗のみ:グループは厳密に $2^k$ 個のセル(1、2、4、8、16)を含む必要があります。3、5、6 のグループは作れません。1 が 6 つある領域は、4 と 2 の重なるグループでカバーする必要があります。
グループサイズを最大化する:大きなグループほど多くの変数を消去します。2 のグループは 1 変数を、4 のグループは 2 変数を、8 のグループは 3 変数を消去します。常に最大可能なグループを最初に探します。
重なりは許される:1 つの「1」が複数のグループに属すことは許されます。より大きなグループを作るために重ねを積極的に使いましょう。
長方形のみ:グループは長方形(正方形を含む)を形成する必要があります。L 字、T 字、対角線は無効です。
マップは循環する:左端の列は右端の列と隣接しており、上端の行は下端の行と隣接しています。マップをトーラスとして想像してください ── 4 つの隅は互いに隣接します。

ディープダイブ:4 変数 K マップ

実世界のシナリオに取り組んでみましょう。CONTROL_UNIT のために、4 ビット入力が特定の条件に一致したときに信号を発する論理を設計しているとします。関数は $F(A,B,C,D) = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15)$ です。

$\Sigma m$ 表記は「2 進入力がこれらの 10 進値に等しいとき出力が HIGH」という略記です。まず 16 セルのグリッドを埋めます。

	$CD=00$	$CD=01$	$CD=11$	$CD=10$
$AB=00$	1 ( $m_0$ )	0	0	1 ( $m_2$ )
$AB=01$	0	1 ( $m_5$ )	1 ( $m_7$ )	0
$AB=11$	0	1 ( $m_{13}$ )	1 ( $m_{15}$ )	0
$AB=10$	1 ( $m_8$ )	0	0	1 ( $m_{10}$ )

ではパターンを探していきましょう。

グループ 1:四隅

$m_0, m_2, m_8, m_{10}$ にある「1」を見てください。マップは水平・垂直の両方で循環するので、これら 4 つの隅は実際には隣接しています! それらは 4 つから成る単一のグループを形成します。

変数 A:0 から 1 へ変化(破棄)。
変数 B:0 のまま( $\overline{B}$ を保持)。
変数 C:0 から 1 へ変化(破棄)。
変数 D:0 のまま( $\overline{D}$ を保持)。
結果: $\overline{B}\overline{D}$

グループ 2:中央のブロック

中央の $m_5, m_7, m_{13}, m_{15}$ に完璧な 2x2 の正方形があります。

変数 A:0 から 1 へ変化(破棄)。
変数 B:1 のまま( $B$ を保持)。
変数 C:0 から 1 へ変化(破棄)。
変数 D:1 のまま( $D$ を保持)。
結果: $BD$

すべての「1」がカバーされました。最終的な簡略化式は次のとおりです:

F = \overline{B}\overline{D} + BD

これは XNOR ゲートのブール定義です ── 8 つの 4 入力 AND ゲートの混雑が、たった 1 つのコンポーネントへと収束したのです。

XNOR ゲートコンポーネント図

XNOR 簡略化回路を試す

よくある落とし穴:グレイコードが譲れない理由

よくある誤りは標準の二進順序 ── 00、01、10、11 ── で K マップを描くことです。やらないでください。

標準二進を使うと隣接性の原則を破ります。01 から 10 への跳躍を見てください。両方のビットが変化します( $0 \to 1$ と $1 \to 0$ )。これら 2 つの隣接セルに「1」がある場合、変数が複数変化しているため簡略化できません。グレイコード列(00、01、11、10)は、マップ上のあらゆるステップが厳密に 1 つの変数の変化を表すことを保証します。これが、視覚的に数学を機能させる「魔法」です。グレイコードがなければ、K マップは混乱を招くテーブルにすぎません;あれば、計算機になるのです。

OSCILLOSCOPE_8CH による検証

デジタル工学でもっとも満足のいく瞬間の一つは、自分の「小さい」回路が「大きな」回路と完全に同じことをすると証明することです。digisim.io 上では、これをリアルタイムで実行できます。

ブルートフォース版を組む:8 つの AND ゲートと 1 つの巨大な OR ゲートを使って元のミンタームを表現します。
最適化版を組む:単一の XNOR ゲート(または等価な 2-AND-1-OR)を下に配置します。
入力を同期する:同じ 4 つの INPUT_SWITCH コンポーネントを両回路に接続します。
解析する:ブルートフォース回路の出力を OSCILLOSCOPE_8CH のチャンネル 1 に、最適化された出力をチャンネル 2 に接続します。

スイッチを 16 通りの組み合わせすべてで切り替えると、OSCILLOSCOPE_8CH 上の波形は同一になります。しかし伝搬遅延 ( $t_{pd}$ ) を見ると、最適化された回路の方が遥かに速く反応していることに気づくはずです。高速 CPU プロジェクトでは、これらのナノ秒は 1 MHz クロックと 10 MHz クロックの差そのものです。

実世界の応用:教室を超えて

K マップは試験を通過するためだけのものではありません。ハードウェア記述の主役の道具です。

1. ALU 制御論理

典型的な 8 ビット CPU では、ALU(算術論理装置)は「オペコード」に基づいて加算するか、減算するか、ビット単位 AND を実行するかを知る必要があります。このオペコードは 4 ビット幅かもしれません。エンジニアはこの 4 ビットオペコードを受け取って ADDER_8BIT や COMPARATOR_8BIT の特定の制御ラインを起動するデコーダ論理を K マップで設計します。この論理を最小化することで、CPU 性能の決定的なボトルネックである「命令デコード」時間を削減できます。

2. 有限状態機械 (FSM)

信号機制御装置から複雑なプロトコル・ハンドラまで、FSM は「次状態論理」に依存します。この論理は現在の状態(REGISTER に格納)と現在の入力を見て、次の状態がどうあるべきかを決定します。これらの真理値表は急速に巨大化します。K マップは設計者にこれらの信号を経路付ける最も効率的な方法を見つけることを可能にし、最終実装で何十ものゲートを節約することがしばしばあります。

ALU コンポーネント図

よくある落とし穴

避けるべき一般的なミス:

浮いた入力:すべての AND ゲートのすべての入力は何かに繋がれていなければなりません。浮いた入力はシミュレータでは予測可能に振る舞うかもしれませんが、実ハードウェアではノイズを拾います。
循環性の見落とし:角と端を確認してください。最も優美な簡略化のいくつかは、四隅または上下の行をグループ化することから生まれます。
冗長なグループ:すべての 1 がカバーされたら止めましょう。「見栄えがよさそうだから」という理由で追加グループを設けると、回路に不必要なゲートが入り、K マップの目的そのものを損ねます。

ドントケア条件の力

実際の設計の多くでは、特定の入力組み合わせは決して発生しません。たとえば BCD(2 進化 10 進)システムは 4 ビットを使って 0〜9 の数字を表すので、組み合わせ 1010〜1111 は決して現れません。K マップでは、これらの不可能な入力に 0 や 1 ではなく $X$ (ドントケア)を記入します。

ポイントは:大きなグループを形成するのに役立つかどうかに応じて、各 $X$ を 0 または 1 として扱えることです。これらの入力は実際には決して発生しないので、回路がそれらに対して何を出力するかは問題になりません。

例:4 変数関数がセル 0、2、8、10 に 1 を持ち、セル 1 と 3 にドントケアを持つと仮定します。ドントケアなしでは、4 つの 1(隅)は $\overline{B}\overline{D}$ にグループ化されます。しかしセル 1 と 3 を 1 として扱うことで、上端行の 4 つから成るより大きなグループ( $\overline{A}\overline{B}$ )に加えて、元の隅のグループも形成でき、より単純な総合式が得られる可能性があります。ドントケア条件は実設計で総ゲート数を 20〜30% 削減することがしばしばあります。

次のステップへ

本記事はブール代数基礎シリーズの一部です。関連する読み物:

ブール代数の習得 ── K マップのグループ化の背後にある代数的恒等式。
積和形 (SOP) の習得 ── K マップが生む正準形式。
積和形を超えて:和積形 ── 双対の最小化。
ド・モルガンの法則 ── 形式間の変換に使う変換規則。

カルノー図は複雑な代数タスクを視覚的なパズルへと変換します。4 変数までの関数では、最小の SOP(または POS)式を確実に生成します。5〜6 変数でも K マップは使えますが扱いにくく、Quine-McCluskey などのアルゴリズム的手法が引き継ぎます。

工夫例から「ブルートフォース」と「最適化」の回路を両方構築し、オシロスコープで波形が一致するのを観察してみてください。新しい回路を始めるで検証できます。