카르노 맵
IT위키
더 많은 작업
카르노 맵(Karnaugh map, K-맵, 카르노 도)은 불 함수의 진리표를 이웃한 칸끼리 변수 하나만 다르게 배열한 격자로 그리고, 1 이 든 칸을 묶어 논리식을 간소화하는 도표이다. 1953년 모리스 카르노(Maurice Karnaugh)가 고안했다.
불 대수의 법칙(XY + XY' = X)을 손으로 하나씩 적용하는 대신 그림으로 한꺼번에 한다. 이웃한 두 칸은 변수 하나만 다르므로 둘 다 1 이면 그 변수를 지울 수 있다. 4·8·16 칸을 한 번에 묶으면 변수 2·3·4 개가 지워진다.
- 2변수는 2×2, 3변수는 2×4, 4변수는 4×4 칸이다
- 행과 열의 순서는 00, 01, 11, 10 이다. 2진수 순서(00, 01, 10, 11)가 아니라 한 비트씩만 바뀌는 그레이 코드 순서다
- 맨 왼쪽 열과 맨 오른쪽 열, 맨 위 행과 맨 아래 행도 이웃이다. 지도를 원통처럼 말아 붙였다고 보면 된다. 네 귀퉁이 칸도 하나로 묶인다
- 1 이 든 칸만 묶는다(곱의 합 형태). 0 을 묶으면 합의 곱 형태가 나온다
- 묶음의 칸 수는 1, 2, 4, 8, 16 처럼 2 의 거듭제곱이고 모양은 직사각형이다
- 묶음은 되도록 크게 만든다. 클수록 지워지는 변수가 많다
- 묶음 수는 되도록 적게 한다
- 한 칸을 여러 묶음에 겹쳐 넣어도 된다
- 무관 조건(don't care, X) 칸은 묶음을 키우는 데 필요할 때만 1 로 본다
묶음 하나를 항 하나로 읽는다. 묶음 안에서 값이 바뀌지 않는 변수만 남기고, 1 로 고정이면 그대로, 0 으로 고정이면 보수(')를 붙인다. 묶음마다 나온 항을 OR(+)로 잇는다.
4변수 함수 F(A, B, C, D) 의 카르노 맵이다(행 AB, 열 CD).
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 |
| 01 | 1 | 1 | 1 | 1 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
- 위 두 행(AB = 00, 01) 여덟 칸 : A 가 0 으로 고정, 나머지는 다 바뀐다 → A'
- 가운데 두 열(CD = 01, 11)과 B = 1 인 두 행(01, 11)의 네 칸 : B = 1, D = 1 로 고정 → BD
- 네 귀퉁이 칸(AB = 00, 10 과 CD = 00, 10 이 만나는 곳) : B = 0, D = 0 으로 고정 → B'D'
따라서 F = A' + BD + B'D' 이다. 맨 위 행의 귀퉁이 칸은 A' 묶음에도 들었지만, 겹쳐 묶어도 되므로 맨 아래 행의 1 두 개를 묶는 데 함께 쓴다.
변수가 5~6개를 넘으면 맵이 여러 장으로 나뉘어 눈으로 묶기 어렵다. 그때는 표를 써서 기계적으로 줄이는 퀸-매클러스키 방법이나 논리 합성 도구를 쓴다.