学ぶ › トピック 4

カルノー図：2・3・4 変数とドントケア条件

読了時間：約 7 分 · bitGateLab チーム

ブール代数でも簡単化はできますが、どの法則を使えばよいかを自分で「見抜ける」かどうかに左右されます。カルノー図は、その探索を目で見てできる作業に変えてくれます。真理値表を、隣り合うセルが一つの変数だけ異なるような格子に並べ直すので、簡単化は 1 のグループを囲む作業になります。この記事では、2、3、4 変数のカルノー図の作り方、正しいグループの作り方（「回り込む」端も含めて）、そしてドントケア条件の活用法を学びます。

基本の考え方：隣のセルとは変数が一つだけ違う

隣接則は AB + AB = A というものでした。一つの変数だけが異なる二つの項は一つにまとまり、その変数が消えます。カルノー図では、辺を共有するどの二つのセルもこの条件を満たすように、最小項を配置します。そのために、行と列の見出しは 2 進数の順 00、01、10、11 ではなく、グレイコードの順、つまり 00、01、11、10 に並べます。隣り合う二つの値の間では 1 ビットしか変化せず、最後と最初（10 と 00）の間でも同じです。そのため、カルノー図は向かい合う端どうしがつながっているかのようにふるまいます。

2 変数と 3 変数のカルノー図

2 変数のカルノー図は 4 セルで、行に A、列に B を割り当てます。3 変数のカルノー図は 8 セルで、行に A、列に BC をグレイコードの順で割り当てます。各セルの中の番号は、対応する最小項を表します。

m3 と m2 がこの順に並んでいることに注意してください。これはグレイコードによるもので、カルノー図を手で埋めるときの間違いの多くは、ここから生じます。

グループ化の規則

• グループに入れられるのは 1（と、あとで説明する X）だけで、0 は決して入れられません。
• 各グループの大きさは 2 のべき乗、つまり 1、2、4、8、16 セルでなければなりません。
• グループは隣接するセルからなる長方形で、端をまたぐ隣接も含みます。斜めは隣接とみなしません。
• 各グループはできるだけ大きくします。2^k セルのグループは k 個の変数を消去します。
• すべての 1 を覆える、できるだけ少ない数のグループを使います。グループどうしは重なってもかまいません。

グループを読むには、変数を一つずつ調べます。グループ内のすべてのセルで同じ値を保つ変数は、項に現れます（1 ならバーなし、0 ならバーつき）。値が変わる変数は消えます。

4 変数のカルノー図と端の隣接

4 変数では、カルノー図は 16 セルになります。行に AB、列に CD を、どちらもグレイコードの順で割り当てます。

左端の列は右端の列と隣り合い、いちばん上の行はいちばん下の行と隣り合います。その結果、四隅（m0、m2、m8、m10）は 4 セルの正しいグループになります。どのセルでも B = 0、D = 0 なので、BD と読めます。

ドントケア条件（X）

入力の組み合わせの中には、決して起こらないものや、出力がどうなっても影響のないものがあります。たとえば BCD の数字では、コード 1010 から 1111 は存在しません。そのような行には X（ドントケア、英語で don't care とも呼びます）を書き、別に d(...) として記しておきます。グループを作るとき、X は、より大きなグループを作る助けになるなら 1 とみなし、そうでなければ無視してかまいません。X を覆う必要はまったくありません。

よくある間違い

• 見出しをグレイコードではなく 2 進数の順（00、01、10、11）に並べる。隣のセルとの違いが一変数だけではなくなり、グループが正しく作れません。
• 3 セルや 6 セルのグループを作る。使えるのは 2 のべき乗だけです。
• 端どうしの隣接や四隅の隣接を忘れる。その結果、グループが必要以上に小さくなります。
• すべてのセルがすでにほかのグループで覆われているグループを追加する。余分なだけで、ゲートが増えます。
• X を無理に覆おうとする。X は、グループを大きくできるときにだけ使います。

シミュレータで試してみよう

カルノー図モジュールは、関数をグレイコードの順に配置し、グループに印を付け、最小の式を書き出します。自分のグループ分けを、ツールが示すものと比べることができます。

1. 4 変数の関数を作り、例 2 の 1 を入力します。
2. まず紙の上で自分でグループを作り、結果を書いておきます。
3. カルノー図に示されるグループと、得られた式を見ます。自分の結果と違っていたら、どのグループが最大になっていなかったのかを確認します。
4. 例 3 を、セル 0、2、5 を X にして入力し、その X を外すと簡単化の結果がどう変わるかを観察します。
5. 結果を回路に変換し、入力を切り替えて、表と一致することを確かめます。

練習問題

1. F(A, B, C) = Σm(0, 2, 4, 6) を簡単化してください。
   解答

   列 BC = 00 と列 BC = 10 は端をまたいで隣り合い、どちらも全部埋まっています。四つのセルすべてで C = 0 なので、F = C です。

2. F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15) を簡単化してください。
   解答

   四隅：BD。中央のブロック m5、m7、m13、m15：BD。F = BD + BD で、これは B と D の XNOR です。

3. F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15) を簡単化してください。
   解答

   行 AB = 01 と行 AB = 11 が 8 セルのグループになります。1 のまま変わらないのは B だけです。F = B。

4. BCD の数字（A が最上位ビット）が 5 以上のときに、出力をオンにします。F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15) を簡単化してください。
   解答

   X を使うと、行 AB = 11 と行 AB = 10 が 8 セルのグループになります：A。ブロック m5、m7、m13、m15 から BD、ブロック m6、m7、m14、m15 から BC が得られます。F = A + BD + BC = A + B(C + D)。

変数が四つか五つを超えると、カルノー図は読みにくくなります。そのような場合のために、表を使った手順であるクワイン・マクラスキー法があります。