【論理回路】カルノー図とDon't Careの意味と使い方、例題について
1. 論理回路におけるカルノー図
1.1. カルノー図とは？
カルノー図（Karnaugh Map、略してK-map）は、論理回路の簡単化に使用される図です。論理式を簡単にし、より効率的な回路を設計するために使われます。カルノー図を使うことで、複雑な真理値表や論理式を視覚的に整理し、最小限の論理ゲートで実現できる形にすることが可能です。だいたい4変数くらいまでが使われます。一方で、アルゴリズムの効率という面では、クワイン・マクラスキー法が使われます。
例えば、デジタル回路で使われる「AND」「OR」「NOT」などの組み合わせを簡略化する際に利用されます。
1.2. カルノー図の書き方
まず、解きたい論理式に基づいてカルノー図の該当セルに記入します。入力変数の全ての組み合わせを記載し、それに対応する出力を確認します。
出力が1の場合：セルに1を記載。
出力が0の場合：セルに0を記載。
カルノー図上の1を「隣接する1の塊」でまとめます。グループ化した1に基づいて、論理式を簡略化します。共通部分を見つけて、冗長な変数を取り除きます。
2. 2変数の場合
2.1. 書き方
カルノー図の作成は、与えられた真理値をもとに進めます。具体的には、以下の手順でカルノー図を埋めていきます。まず、真理値が与えられている条件を確認します。この条件に基づいて、カルノー図の対応する箇所に真理値を書き込んでいきます。例えば、画像の例では、Aが0、Bが1のときに対応する真理値をカルノー図の該当部分（青いエリア）に真理値を書き込みます。
2.2. 2変数の場合の例題
$$Y=A\cdot B+A\cdot \overline B$$
カルノー図を使って簡単化をしなさい。
これをカルノー図で書くと、
ここで、「1」の部分をグループ化します。この場合、Aが1であれば出力が常に1になることが分かります。そのため、
$$Y=A$$
となります。
3. 3変数の場合
3.1. 書き方
同様に、カルノー図の作成は、与えられた真理値をもとに進めます。ですが、画像の様に、３変数の場合は、片方を二つの変数でまとめる必要があります。ABはグレーコード（Gray Code）の順に並べることで、隣接するセルが1ビットの差異だけになるよう配置します。
画像の例では、Aが0、Bが0、Cが1のときに対応する真理値をカルノー図の該当部分（青いエリア）に真理値を書き込みます。
3.2. 3変数の場合の例題
出力$Y$が3入力$A,B,C$に対して、次のように表されるとします。
$$Y=A\cdot B\cdot C+\overline A \cdot B +A \cdot \overline B+A\cdot B\cdot \overline C$$
カルノー図を使って簡単化をしなさい。
カルノー図を書くと
11と01は$\overline A \cdot B +A \cdot \overline B$の部分であるので、まとめると、$B$になる。
11と10は$\overline A \cdot B +\overline A \cdot B$の部分であるので、まとめると、$A$になる。
したがって、
$$Y =A+B$$
4. 4変数の場合
4.1. 書き方
同様に、カルノー図の作成は、与えられた真理値をもとに進めます。ですが、画像の様に、4変数の場合は、二つの変数でまとめる必要があります。AB、CDの並び順はgray code順になります。
画像の例では、A、B、C、Dが1のときに対応する真理値をカルノー図の該当部分（緑のエリア）に真理値を書き込みます。
4.2. 4変数の場合の例題
出力$Y$が4入力$A,B,C,D$に対して、次のように表されるとします。
$$Y=\overline A\cdot B\cdot \overline C+\overline A\cdot B\cdot D+A\cdot B\cdot \overline C$$
カルノー図を使って簡単化をしなさい。
青色の部分が、$B\cdot\overline C$
赤色の部分が、$\overline A\cdot B\cdot D$
したがって、
$$Y =A+B$$
5. Don’t Care
特定の入力が出力において重要でない場合があります。このような条件は「Don’t Care」と呼ばれ、カルノー図においてグループ化に活用されています。これにより、さらなる簡略化が可能になります。
簡単に言えば、ここの入力は必要ないから無視してもいいよということです。
5.1. 対応する位置
少し話が脱線しますが、10進数で対応する位置をABCD（4ビットの入力）で表します。
Gray codeだから単純に+4ずつして計算していくことができない。
5.2. 10進数の場合の例
よく見られるDon’t Careの条件として、ABCDが0～9の範囲で必要な場合を考えます。このとき、10進数で10以上の入力値は不要とされます。そのため、次のように青色の部分（不要な入力条件）を無視することができます。
5.3. Don’t Careを活用したカルノー図の簡略化
次のようなカルノー図があるとします。0は省略します。
この場合、さきほどのDon’t Careを使える場合
つまり、Don’t Careの部分を1とみなして、$Y=A\cdot B$にすることができます。
5.4. Don’t Careの例題
４変数の場合で求めたカルノー図に対して、15の部分をDon’t Careとした場合、簡単化しなさい。
初期のカルノー図は以下の通りです。
Don’t Careの条件を考慮すると、次のようになります。
となるので、論理回路の出力$Y$は次のようになります。
$$Y=B\cdot \overline C + B\cdot D$$
