カルノー図
真理値表から最小の論理式と回路を求めます。出力の 0・1・X を押して切り替えると、カルノー図の囲み・式・回路がその場で変わります。
真理値表
ABCD の数 0〜9 で光るセグメント a〜g(10〜15 は X)
| 番号 | A | B | C | D | a | b | c | d | e | f | g | 項 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | ||||||||
| 1 | 0 | 0 | 0 | 1 | ||||||||
| 2 | 0 | 0 | 1 | 0 | ||||||||
| 3 | 0 | 0 | 1 | 1 | ||||||||
| 4 | 0 | 1 | 0 | 0 | ||||||||
| 5 | 0 | 1 | 0 | 1 | ||||||||
| 6 | 0 | 1 | 1 | 0 | ||||||||
| 7 | 0 | 1 | 1 | 1 | ||||||||
| 8 | 1 | 0 | 0 | 0 | ||||||||
| 9 | 1 | 0 | 0 | 1 | ||||||||
| 10 | 1 | 0 | 1 | 0 | ||||||||
| 11 | 1 | 0 | 1 | 1 | ||||||||
| 12 | 1 | 1 | 0 | 0 | ||||||||
| 13 | 1 | 1 | 0 | 1 | ||||||||
| 14 | 1 | 1 | 1 | 0 | ||||||||
| 15 | 1 | 1 | 1 | 1 |
出力を押して 0 → 1 → X、行を押してその入力を回路へ
カルノー図
1 のまとまり 1 つが AND 1 個、それを OR でまとめる形
回路
入力を押して切り替え
11 の行が最小項
1 の行 1 つが AND 1 個(A · B · C)
2となりは 1 変数だけ違う
並びは 00・01・11・10(グレイコード)
3まとめると変数が減る
A · B · C + A · B · C = A · B
4大きさは 1・2・4・8
4 マスで 2 変数、8 マスで 3 変数が消える
5端は反対の端のとなり
四隅の 4 マスも 1 つのまとまり
6X はまとめやすい方へ
X を 1 とみなすと A だけ
70 をまとめると和積形
0 のまとまりが OR、全体を AND で
8解が 2 通りのことも
どの 1 も 2 つの主項で覆える形
動作原理と式
真理値表と標準形
出力が 1 になる行ごとに、入力をすべて並べた積の項(最小項)を作り、それらを OR でまとめると、どんな真理値表も式になります(主加法標準形)。0 になる行ごとに和の項(最大項)を作って AND でまとめた形が主乗法標準形です。どちらも正しい式ですが、項と変数が多く、回路も大きくなります。
まとめると変数が減る
1 変数だけ違う 2 つの項は、その変数が消えた 1 つの項になります。2 つずつ、4 つずつとまとめるたびに変数が 1 つずつ減ります。まとまりの大きさは 2 のべき乗です。
カルノー図
真理値表の行をマスに並べた図です[1][2]。行と列をグレイコードの順(00・01・11・10)に並べるので、となりのマスは 1 変数だけ違います。右の端と左の端、上の端と下の端もとなりです。1 のマスを、縦と横が 1・2・4 マスの四角でなるべく大きく、なるべく少なく囲むと、囲み 1 つが積の項 1 つになります。0 のマスを囲むと和積形になります。
- 5 入力は A = 0 と A = 1 の 4×4 の図を左右に並べる。2 枚の同じ位置のマスもとなり
- 6 入力は A で上下、B で左右に 4 枚を並べる
- Don't Care(X)は、その入力の組が起きないか、出力をどちらにしてもよい行。囲みを大きくできるときだけ 1(和積形では 0)として使う
主項と最小の解
これ以上大きくできないまとまりを主項と呼びます[3]。最小の式は主項だけで作れます。ある 1 を覆う主項が 1 つしかなければ、その主項は必ず使います(必須主項)。残りの 1 をどの主項で覆うかには、選び方が複数あることがあります。
- このページは、クワイン・マクラスキー法で主項を求める。1 か所だけ違う 2 つの項をまとめる操作を、まとまらなくなるまでくり返す[4]
- 残りの 1 を覆う主項の組は、ペトリック法で数え上げる。「この 1 を覆うのは P1 か P2」を AND でつなぎ、展開した積の項が覆い方の候補になる[5]
- 最小は、項の数が少なく、同じなら変数の数が少ない解。同じ大きさの解はすべて挙げる
ハザードを消す項
最小の式では、となりどうしの 1 が別々の項に入ることがあります。その 2 マスの間で入力を変えると、一方の項が 0 になってから他方が 1 になるまでの一瞬、出力が 0 になります(静的ハザード)。2 マスを両方覆う項(上の式の )を足すと消えます[6]。「ハザード対策の項」はこの項を破線で足します。
NAND だけ・NOR だけ
積和形の AND と OR をどちらも NAND に替えても、同じ働きの回路になります。和積形の OR と AND は NOR に替えられます。
出典
- カルノー図M. Karnaugh, The map method for synthesis of combinational logic circuits, Transactions of the AIEE, Part I, 72(5), 593–599, 1953
- 図で真理値表をまとめる方法(ベイチ図)E. W. Veitch, A chart method for simplifying truth functions, Proceedings of the ACM National Meeting, 127–133, 1952
- 主項と、主項で式を覆う考え方W. V. Quine, The problem of simplifying truth functions, The American Mathematical Monthly, 59(8), 521–531, 1952
- 主項を表の上で機械的に求める方法E. J. McCluskey, Minimization of Boolean functions, Bell System Technical Journal, 35(6), 1417–1444, 1956
- 主項の組を論理式で数え上げる方法S. R. Petrick, A direct determination of the irredundant forms of a Boolean function from the set of prime implicants, AFCRC-TR-56-110, Air Force Cambridge Research Center, 1956
- ハザードと、それを消す項D. A. Huffman, The design and use of hazard-free switching networks, Journal of the ACM, 4(1), 47–62, 1957
このツールで決めたこと
- 入力は 2〜6 個。出力は複数でも、出力ごとに別々に簡単化する(出力の間で項を共有する最適化はしない)
- 主項が多い表では、ペトリック法の途中で項の少ない組を 400 個だけ残して進める。最小を見落とすことがある
- 最小の解は 8 通りまで挙げる
- 回路は 2 段で描く。否定は入力の後ろの NOT で作り、1 変数だけの項はゲートを通さない
- ゲートの数には NOT を含める。段数は入力からランプまでに通るゲートの数の最大
- ハザード対策の項は、となりどうしの 2 マスを両方覆う主項のうち大きいもの