Tools + Simulatorsnanase.cc / tools

カルノー図

真理値表

16 行

ABCD の数 0〜9 で光るセグメント a〜g(10〜15 は X)

入力
出力
7
番号ABCDabcdefg項
00000
10001
20010
30011
40100
50101
60110
70111
81000
91001
101010
111011
121100
131101
141110
151111

出力を押して 0 → 1 → X、行を押してその入力を回路へ

カルノー図

出力
ABCD00011110000111101001131204151716X12X13X15X141819X11X10
1まとめる値0XDon't Care(0 でも 1 でもよい)

最小の解 1 通り
項 4ゲート 5入力 10 本3 段

1 のまとまり 1 つが AND 1 個、それを OR でまとめる形

回路

CAA0B0BC0D0Da

入力を押して切り替え

  1. 11 の行が最小項

    ABC000111100100000001

    1 の行 1 つが AND 1 個(A · B · C)

  2. 2となりは 1 変数だけ違う

    ABC000111100100000000

    並びは 00・01・11・10(グレイコード)

  3. 3まとめると変数が減る

    ABC000111100100000011

    A · B · C + A · B · C = A · B

  4. 4大きさは 1・2・4・8

    ABCD00011110000111100000011001100000

    4 マスで 2 変数、8 マスで 3 変数が消える

  5. 5端は反対の端のとなり

    ABCD00011110000111101001000000001001

    四隅の 4 マスも 1 つのまとまり

  6. 6X はまとめやすい方へ

    ABC000111100100001XX1

    X を 1 とみなすと A だけ

  7. 70 をまとめると和積形

    ABC000111100101110111

    0 のまとまりが OR、全体を AND で

  8. 8解が 2 通りのことも

    ABC000111100111010111

    どの 1 も 2 つの主項で覆える形

動作原理と式

真理値表と標準形

出力が 1 になる行ごとに、入力をすべて並べた積の項(最小項)を作り、それらを OR でまとめると、どんな真理値表も式になります(主加法標準形)。0 になる行ごとに和の項(最大項)を作って AND でまとめた形が主乗法標準形です。どちらも正しい式ですが、項と変数が多く、回路も大きくなります。

Y=A·B·C+A·B·C+A·B·C+A·B·C

まとめると変数が減る

A·B·C+A·B·C=A·B·(C+C)=A·B

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]
  • 最小は、項の数が少なく、同じなら変数の数が少ない解。同じ大きさの解はすべて挙げる

ハザードを消す項

Y=A·B+A·C+B·C

最小の式では、となりどうしの 1 が別々の項に入ることがあります。その 2 マスの間で入力を変えると、一方の項が 0 になってから他方が 1 になるまでの一瞬、出力が 0 になります(静的ハザード)。2 マスを両方覆う項(上の式の B·C)を足すと消えます[6]。「ハザード対策の項」はこの項を破線で足します。

NAND だけ・NOR だけ

積和形の AND と OR をどちらも NAND に替えても、同じ働きの回路になります。和積形の OR と AND は NOR に替えられます。

出典

  1. カルノー図M. Karnaugh, The map method for synthesis of combinational logic circuits, Transactions of the AIEE, Part I, 72(5), 593–599, 1953
  2. 図で真理値表をまとめる方法(ベイチ図)E. W. Veitch, A chart method for simplifying truth functions, Proceedings of the ACM National Meeting, 127–133, 1952
  3. 主項と、主項で式を覆う考え方W. V. Quine, The problem of simplifying truth functions, The American Mathematical Monthly, 59(8), 521–531, 1952
  4. 主項を表の上で機械的に求める方法E. J. McCluskey, Minimization of Boolean functions, Bell System Technical Journal, 35(6), 1417–1444, 1956
  5. 主項の組を論理式で数え上げる方法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
  6. ハザードと、それを消す項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 マスを両方覆う主項のうち大きいもの

関連ツール