본문으로 이동
메뉴 여닫기
환경 설정 메뉴 여닫기
개인 메뉴 여닫기
로그인하지 않음
지금 편집한다면 당신의 IP 주소가 공개될 수 있습니다.

카르노 맵(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. 1 이 든 칸만 묶는다(곱의 합 형태). 0 을 묶으면 합의 곱 형태가 나온다
  2. 묶음의 칸 수는 1, 2, 4, 8, 16 처럼 2 의 거듭제곱이고 모양은 직사각형이다
  3. 묶음은 되도록 크게 만든다. 클수록 지워지는 변수가 많다
  4. 묶음 수는 되도록 적게 한다
  5. 한 칸을 여러 묶음에 겹쳐 넣어도 된다
  6. 무관 조건(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개를 넘으면 맵이 여러 장으로 나뉘어 눈으로 묶기 어렵다. 그때는 표를 써서 기계적으로 줄이는 퀸-매클러스키 방법이나 논리 합성 도구를 쓴다.