카노 맵

파일:K-map 6,8,9,10,11,12,13,14 anti-race.svg

카르노 맵의 예

카르노 맵(영어: Karnaugh map, 간단히 K-map)은 논리 회로 용어로, 불 대수 위의 함수를 단순화하는 방법이다. 불 대수에서 확장된 논리 표현을 사람의 패턴인식에 의해 연관된 상호관계를 이용하여 줄이는 방법이다.

예시

카르노도는 불 대수를 편리하게 단순화하는 방법을 제공한다. 설계대상이 요구하는 입력과 출력의 관계를 진리표로 표현하고 이것으로부터 카르노 맵을 그린다.

논리 기능의 진리표
	A	B	C	D	f(A, B, C, D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

단순화 되지 않은 불대수 표현에서 불 변수 $A$ , $B$ , $C$ , $D$ 에 대해:

$f (A, B, C, D) = \sum_{} (6, 8, 9, 10, 11, 12, 13, 14)$

여기서 $\sum_{}$ 안의 숫자는 최소항 전개(minterm)의 진리표에서 출력이 1이다.

출력 1인 각각의 최소항들을 모두 표시하면:

$f (A, B, C, D) = (\overline{A} B C \overline{D}) + (A \overline{B} \overline{C} \overline{D}) + (A \overline{B} \overline{C} D) + (A \overline{B} C \overline{D}) + (A \overline{B} C D) + (A B \overline{C} \overline{D}) + (A B \overline{C} D) + (A B C \overline{D})$

이것은 단순화되지 않는 불대수이다.

카르노 맵

카르노 맵은 입력변수와 출력을 도식화 하고, 같은 출력의 패턴을 찾아 묶음으로 단순화 한다. 배치에서 변수의 값이 변하도록 서로 묶이도록 배치한다.

파일:K-map minterms A.svg

K-map construction.

이것을 진리표의 출력값을 배치하면:

파일:K-map 6,8,9,10,11,12,13,14.svg

K-map에서 최소항들은 컬러상자로 표시한다. 갈색은 겹친영역이고, 빨간도식은 2×2 그리고 녹색은 4×1.

서로 이웃의 출력끼리 묶어 상자를 만든다. 만약 X가 존재하다면 출력 0이든 1이든 어디에도 포함할 수 있다.

단순화

출력 1을 기준으로 단순화 하면

빨간상자는:

변수 A가 1일 때 1로 출력된다. 따라서 그대로 포함된다.

결국 곱의합(sum-of-products expression) 표현으로 표시하면 $A \overline{C}$ .

같은 방법으로 녹색상자는 A와 B가 유지되고, C는 D 배제된다. B는 0일 때 1로, 보수로 출력이 나타난다. $A \overline{B}$ .

파란상자는 $B C \overline{D}$ .

출력 1이 모두 포함하도록 각각의 상자를 위와 같이 표현하고 모두 곱의합형태로 나타내면 단순화 된 결과가 된다:

$A \overline{C} + A \overline{B} + B C \overline{D}$ .

전체 단순화되지 않는 식:

$f (A, B, C, D) = (\overline{A} B C \overline{D}) + (A \overline{B} \overline{C} \overline{D}) + (A \overline{B} \overline{C} D) + (A \overline{B} C \overline{D}) + (A \overline{B} C D) + (A B \overline{C} \overline{D}) + (A B \overline{C} D) + (A B C \overline{D})$

이것을 카노 맵으로 단순화 하면:

$f (A, B, C, D) = A \overline{C} + A \overline{B} + B C \overline{D}$

역함수

역함수를 구하기 위해서는 1대신 0으로 묶음상자를 만든다.

위와 같은 방법으로:

갈색상자— $\overline{A} \overline{B}$
금색상자— $\overline{A} \overline{C}$
파란상자— $B C D$

역함수로 표시하면:

\overline{F} = \overline{A} \overline{B} + \overline{A} \overline{C} + B C D

드 모르간의 법칙(De Morgan's laws)을 적용하여 합의 곱(product of sums)으로 표시하면:

\overline{\overline{F}} = \overline{\overline{A} \overline{B} + \overline{A} \overline{C} + B C D}

F = (A + B) (A + C) (\overline{B} + \overline{C} + \overline{D})

같이 보기

수리 논리학