カルノー図 (K-Map) ソルバー

カルノー図 (K-Map) ソルバーは、2～5変数のブール論理関数を最小化し、色分けされたグループ化によって古典的なカルノー図として簡略化を可視化します。最小項、最大項を入力するか、対話型の真理値表を使用してください。ソルバーは内部でクワイン・マクラスキー法を実行し、すべての主項を見つけ、必須主項をマークし、ステップバイステップの解説付きで最小の積和形 (SOP) または和積形 (POS) の式を生成します。主項チップをクリックすると、それがカバーするセルが点滅し、グループ化によってどのように論理が簡略化されるかを確認できます。

カルノー図とは何ですか？

カルノー図（1953年にモーリス・カルノーによって発明）は、真理値表をグラフィカルに表現したもので、入力変数が1つだけ異なるセルが物理的に隣接するように配置されています。鍵となるのは、行と列のグレイコード順序です。00、01, 11, 10のように、連続するラベルは正確に1ビットだけ異なります。この隣接性により、単一の簡略化された項に結合できる1（または0）のグループを視覚的に特定できます。

n個の入力変数に対して、カルノー図には 2^n 個のセルがあります。4変数のカルノー図は16セルの4×4グリッドであり、5変数のマップは2つの隣接する4×4グリッドとして描かれます。

SOP 対 POS: どちらの形式を選ぶべきか

積和形 (SOP: Sum of Products)

SOPは1のセルをグループ化します。各グループはリテラルの積（AND）になり、すべてのグループが論理和（OR）で結ばれます。例: AB'C + BD。SOPはAND–ORゲートネットワークに直接マッピングされるため、通常はデフォルトとして使用されます。

和積形 (POS: Product of Sums)

POSは0のセルをグループ化します。各グループは反転したリテラルの和（OR）になり、すべての和が論理積（AND）で結ばれます。例: (A + B')(C + D')。関数に0よりも1が多い場合、POSの方が短くなることがよくあります。

このツールは両方の形式を個別に計算します。出力モードを切り替えてリテラル数を比較し、実装にとってより単純な方を選択してください。

カルノー図のグループ化ルール

• 2の累乗のグループのみ: グループには1、2、4、8、または16個のセルが含まれている必要があります。3個や5個のグループは許可されません。
• 長方形の形状: グループ内のセルは長方形を形成する必要があります（水平、垂直、または端をまたぐ）。
• 端の隣接性: 最上行は最下行と隣接し、左端の列は右端の列と隣接しています。これがグレイコード順序が重要である理由です。
• 最大のグループから優先: 大きなグループほど多くの変数を排除し、より短い積項を生成します。8セルのグループは3つの変数を排除し、4セルは2つ、2セルは1つ排除します。
• すべての1をカバーする必要がある: 各1のセル（SOPの場合）または0のセル（POSの場合）は、少なくとも1つのグループでカバーされる必要があります。
• 重複は許可される: より大きなグループにつながる場合、同じ1を複数のグループでカバーしても構いません。
• ドントケアは柔軟: ドントケアをグループに含めることでより大きなグループが作れる場合は含めても構いませんが、必ずしもカバーする必要はありません。

主項と必須主項

主項 (Prime Implicant) とは、それ以上拡張できないグループのことです。それ以上大きくすると、（SOPの場合）0のセルを含んでしまいます。ソルバーは見つけたすべての主項をリストします。その後、必要なすべての最小項をカバーする最小の主項セットである最小被覆 (Minimal Cover) を選択します。

必須主項 (Essential Prime Implicant) とは、特定の最小項をカバーしている唯一の主項である場合に必須とマークされます。すべての最小形式には、すべての必須主項が含まれている必要があります。それらを選択した後、残りの未カバーの最小項は、最も「コストの低い」追加の主項でカバーされます。

ドントケア条件

ドントケア（カルノー図上では X と表示）は、出力が重要ではない入力の組み合わせです。これは、実際の回路で決して発生しないか、値がどうであっても構わないかのいずれかです。アルゴリズムは、より単純な式が得られるように、各Xを0または1のいずれかとして自由に扱うことができます。実際、ドントケアを使用すると、リテラル数が30～60%削減されることがよくあります。現実世界の一般的な例としては、16個の4ビット入力組み合わせのうち10個しか使用しない10進デコーダがあり、組み合わせ10～15がドントケアとなります。

クワイン・マクラスキー法

カルノー図は視覚的な手法ですが、4～5変数を超えると実用的ではなくなります。クワイン・マクラスキー (QM) 法は、それに対応する表形式の手法であり、数学的に厳密でスケーラブルです。このソルバーは内部で QM 法を使用しています：

1. 最小項をバイナリでリストし、1のビット数でグループ化します。
2. 隣接するグループのペアを結合し（1ビットだけ異なるもの）、異なるビットをダッシュに置き換えます。例: 0011 + 0111 → 0-11。
3. それ以上結合できなくなるまで繰り返します。結合できなくなった項が主項です。
4. 主項表を作成します。行が主項、列が必要な最小項です。必須主項（チェックマークが1つしかない列）を特定します。
5. ペトリック法 / 全探索: 残りの未カバー最小項について、それらをカバーする最小の追加主項セットを見つけます。

この電卓の使い方

1. 変数の数を選択: 2、3、4、または5。カルノー図のグリッドが自動的に適応します。
2. 入力方法を選択:
   • 最小項: F = 1 となるインデックス（例: 1, 3, 5, 7）と、ドントケアを入力します。
   • 最大項: F = 0 となるインデックスを入力します。ソルバーは残りを自動的に1として計算します。
   • 真理値表: 各行をクリックして、出力を0、1、Xの間で切り替えます。手動設計の論理に最適です。
3. SOPまたはPOS出力を選択。切り替えて両方の形式を比較してください。一方が他方より短くなることがよくあります。
4. 「解く」をクリック。各主項が異なる色で表示されたカルノー図が現れます。チップをクリックすると、それがカバーするセルが点滅します。
5. 手順を確認: クワイン・マクラスキー法の内訳により、各主項がどのように導出され、どれが必須であるかが示されます。

計算例: ドントケアを含む4変数関数

F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5) を考えます。

ドントケアがない場合、最小のSOPにはいくつかの項が必要になります。{0, 2} を 1 として扱うことで、ソルバーは 4 セルのグループ A'B' (0, 1, 2, 3 をカバー) を作成できます。5 を 1 として扱うことで、CD のカバー範囲を拡張できます。結果として得られる簡略化は次のようになります：

リテラルはわずか4つです。ドントケアのトリックを使わない場合の10個以上から削減されています。上の「4変数 ドントケア付」クイック例で、この正確な例を読み込むことができます。

なぜブール関数を最小化するのですか？

• ゲート数の削減 = ハードウェアコストの低下、チップ面積の縮小、消費電力の低減。
• 回路の高速化: クリティカルパス上のゲート遅延が減少します。
• ドキュメントの簡素化: 簡潔な式は検証や保守が容易です。
• デジタル設計の基礎: すべての FPGA 合成ツールは、クワイン・マクラスキー法の後継（Espresso-II など）を実行しています。

制限事項と他のツールの使用時期

• 5変数以上: カルノー図は視覚的に乱雑になります。このツールは、2つの4×4マップに分割することで最大5変数までサポートしています。それを超える場合は、クワイン・マクラスキー法の手順に頼るか、ABC / Espresso などの合成ツールを使用してください。
• ハザードとグリッチ: 最小被覆には静的ハザードが含まれる場合があります。ハザードのない設計には、冗長な主項を含める必要があります。このツールはそれらをマークしますが、ハザードカバーを自動的に追加はしません。
• 複数出力の最小化: 複数の関数が変数を共有している場合、共同で最小化（ゲートの共有）を行うことでハードウェアをより小さくできます。このツールは一度に一つの関数を最小化します。

よくある質問

カルノー図とは何ですか？

カルノー図（K-map）は、ブール式を最小化するための視覚的な手法です。隣接するセルが1つの変数のみ異なるように配置されています（グレイコード順序）。1を1、2、4、8、または16のサイズの長方形にグループ化することで、最小の積和形表現を導き出します。

SOPとPOSの違いは何ですか？

SOP（積和形）は1のセルをグループ化し、それらの積項を論理和（OR）で結びます（例：A'B + CD）。POS（和積形）は0のセルをグループ化し、それらの和項を論理積（AND）で結びます（例：(A + B')(C' + D)）。どちらも同じ関数を表しますが、通常どちらか一方がよりコンパクトになります。

ドントケアとは何ですか？なぜ使うのですか？

ドントケア項（Xでマーク）は、出力値が重要ではない入力の組み合わせです。これらは決して発生しないか、値がどうであっても構いません。ソルバーは、より単純な式が得られるように、これらを0または1のいずれかとして扱います。ドントケアを使用すると、多くの場合リテラル数を劇的に削減できます。

主項（プライムインプリカント）とは何ですか？

主項とは、それ以上拡張できない、隣接する1のセルの可能な限り最大のグループ（2の累乗サイズ）のことです。必須主項とは、少なくとも1つの最小項を単独でカバーしている主項であり、すべての最小形式に含まれる必要があります。

クワイン・マクラスキー法はどのように機能しますか？

クワイン・マクラスキー法はカルノー図の表形式版で、多くの変数に適しています。すべての最小項をバイナリでリストし、1の数でグループ化し、正確に1ビットだけ異なるペアを繰り返し結合します。それ以上結合できない項が主項となります。その後、主項表を使用して最小被覆を選択します。

このカルノー図ソルバーは何変数までサポートしていますか？

このツールは2から5変数までサポートしています。5変数のカルノー図は、2つの隣接する4×4マップ（A=0用とA=1用）として表示されます。5変数を超えるとカルノー図は実用的ではなくなるため、より大きな関数にはクワイン・マクラスキー法の手順を使用してください。

参考文献

• カルノー図 — Wikipedia
• クワイン・マクラスキー法 — Wikipedia
• Petrick's Method — Wikipedia (英語)