1. 개요
카르노 맵(카노 맵, Karnaugh map, K-map)은 논리 회로를 간소화하기 위해 Maurice Karnaugh가 고안한 방법이다.[1] 카르노 맵은 진리표를 2차원 테이블로 변환한 것을 가리킨다. 미국의 수학자 겸 컴퓨터과학자인 모리스 카르노(Maurice Karnaugh)가 고안했다.카르노 맵을 사용한 논리식 간소화 과정은 다음과 같다.
- 간소화하고자 할 논리 회로의 진리표를 작성
- 진리표를 기반으로 카르노 맵을 작성
- 카르노 맵에서 인접한 셀들은 하나의 변수만 다르도록 배치해야 함 (주로 그레이 코드 사용함)
- 그룹화: 값이 1인 모든 칸들을 직사각형 또는 정사각형 형태로 묶음
- 그룹 크기 (가로 및 세로 길이) 는 1, 2, 4, 8 등 [math(\boldsymbol {2^n})]으로 묶어야 함
- 가능한 한 큰 그룹으로 묶는 것이 최적화에 유리함
- 그룹은 카르노 맵의 경계선을 넘을 수도 있음
- 그룹화를 통해 최소화된 논리식을 생성함
2. 예제
1변수, 2변수의 경우에는 카르노 맵을 만들어야 할 정도로 논리 회로가 복잡하다고 하기 어렵기에 일반적으로 카르노 맵을 사용하지 않는 편이다.2.1. 변수가 3개인 경우 (3변수 카르노 맵)
예를 들어서 [math(\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC)]와 같은 논리식을 가지는 논리 회로가 있다고 가정하자. 이 논리 회로의 진리표를 작성하면 다음과 같다.| A | B | C | 출력 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
이 진리표를 기반으로 카르노 맵으로 작성하면 다음과 같다.
| A \\ BC | 00 | 01 | 11 | 10 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
여기에서 값이 1인 칸을 사각형 그룹으로 묶으면 다음과 같다.
- [math(B=1)]이고, [math(C=1)]인 사각형 → [math(BC)]
A \\ BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1 - [math(A=1)]이고, [math(C=1)]인 사각형 → [math(AC)]
A \\ BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1 - [math(A=1)]이고, [math(B=1)]인 사각형 → [math(AB)]
A \\ BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1
각 그룹에서 도출한 최소 논리식을 OR 연산으로 결합하면, 다음과 같이 간소화된 논리식이 도출된다.
[math(\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC=\mathbf{BC+AC+AB})]
참고로 여기서 가능한 한 큰 그룹에 해당하는 [math(A=1)]이고 [math(B=1)]인 사각형 ([math(AB)]) 대신 비교적 작은 그룹인 [math(A, B, C)]가 각각 [math(1, 1, 0)]인 사각형 [math(AB\overline{C})]를 이용해도 값이 1인 모든 칸을 커버할 수 있지만, 최종 논리식이 [math(\mathbf{BC+AC+AB\overline{C}})] 로 보다 복잡해지기 때문에 최적화 관점에서 추천되지 않는다.
2.2. 변수가 4개인 경우 (4변수 카르노 맵)
예를 들어서 [math(\overline{A}B\overline{CD}+\overline{A}BC\overline{D}+AB\overline{CD}+AB\overline{C}D+ABCD+ABC\overline{D}+A\overline{B}CD+A\overline{B}C\overline{D})]의 논리식을 가지는 논리 회로가 있다고 가정하자. 이 논리 회로의 진리표를 작성하면 다음과 같다.| A | B | C | D | 출력 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
이 진리표를 기반으로 카르노 맵으로 작성하면 다음과 같다.
| AB \\ CD | 00 | 01 | 11 | 10 |
| 00 | 0 | 0 | 0 | 0 |
| 01 | 1 | 0 | 0 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 1 | 1 |
여기에서 값이 1인 칸을 사각형 그룹으로 묶으면 다음과 같다.
- [math(A=1)]이고, [math(C=1)]인 사각형 → [math(AC)]
AB \\ CD 00 01 11 10 00 0 0 0 0 01 1 0 0 1 11 1 1 1 1 10 0 0 1 1 - [math(B=1)]이고, [math(D=0)]인 사각형 → [math(B\overline{D})]
AB \\ CD 00 01 11 10 00 0 0 0 0 01 1 0 0 1 11 1 1 1 1 10 0 0 1 1 - [math(A=1)]이고, [math(B=1)]인 사각형 → [math(AB)]
AB \\ CD 00 01 11 10 00 0 0 0 0 01 1 0 0 1 11 1 1 1 1 10 0 0 1 1
각 그룹에서 도출한 최소 논리식을 OR 연산으로 결합하면, 다음과 같이 간소화된 논리식이 도출된다.
[math(\overline{A}B\overline{CD}+\overline{A}BC\overline{D}+AB\overline{CD}+AB\overline{C}D+ABCD+ABC\overline{D}+A\overline{B}CD+A\overline{B}C\overline{D}=\mathbf{AC+B\overline{D}+AB})]
참고로 여기서 가능한 한 큰 그룹에 해당하는 [math(A=1)]이고 [math(B=1)]인 사각형 ([math(AB)]) 대신 비교적 작은 그룹인 다음 중 하나를 이용해도 값이 1인 모든 칸을 커버할 수 있지만, 다음과 같이 보다 복잡해지기 때문에 추천되지 않는다.
- [math(A, B, C)]가 각각 [math(1, 1, 0)]인 사각형 [math(AB\overline{C})]를 이용할 때
- [math(\mathbf{AC+B\overline{D}+AB\overline{C}})]
- [math(A, B, D)]가 각각 [math(1, 1, 1)]인 사각형 [math(ABD)]를 이용할 때
- [math(\mathbf{AC+B\overline{D}+ABD})]
- [math(A, B, C, D)]가 각각 [math(1, 1, 0, 1)]인 사각형 [math(AB\overline{C}D)]를 이용할 때
- [math(\mathbf{AC+B\overline{D}+AB\overline{C}D})]
3. 중복된 그룹의 제거
카르노 맵에서 사각형 그룹을 묶을 때, 하나의 그룹이 다른 그룹들에 의해 완전히 커버되는 경우가 간혹 생긴다. 이때 완전히 커버되는 중복된 그룹은 논리식을 복잡하게 만들기 때문에 제거하는 것이 좋다. 이런 중복 그룹은 같은 논리식에서 사각형 그룹을 묶는 순서를 다르게 하면 나타나지 않을 수도 있는 경우가 대부분이다.예를 들어, [math(\overline{A}BC+\overline{AB}C+AB\overline{C}+ABC)]와 같은 논리식을 가지는 논리 회로에 대해 카르노 맵을 작성하면 다음과 같다.
| A \\ BC | 00 | 01 | 11 | 10 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
여기에서 값이 1인 칸을 사각형 그룹으로 묶으면 다음과 같다.
- [math(A=0)]이고, [math(C=1)]인 사각형 → [math(\overline{A}C)]
A \\ BC 00 01 11 10 0 0 1 1 0 1 0 0 1 1 - [math(B=1)]이고, [math(C=1)]인 사각형 → [math(BC)]
A \\ BC 00 01 11 10 0 0 1 1 0 1 0 0 1 1 - [math(A=1)]이고, [math(B=1)]인 사각형 → [math(AB)]
A \\ BC 00 01 11 10 0 0 1 1 0 1 0 0 1 1
각 그룹에서 도출한 최소 논리식을 OR 연산으로 결합하면 [math(\mathbf{\overline{A}C+BC+AB})] 가 된다. 그런데 여기서 [math(\overline{A}C)]의 영역과 [math(AB)]의 영역의 합집합은 [math(BC)]의 영역을 완전히 커버하므로, [math(BC)]는 중복된 그룹으로 간주하여 삭제하면 논리식을 [math(\mathbf{\overline{A}C+AB})] 로 간소화할 수 있다.
여기서 사각형 그룹을 묶는 순서를 [math(\overline{A}C)] → [math(AB)] 또는 [math(AB)] → [math(\overline{A}C)] 로 바꾸면 [math(BC)] 그룹을 사각형으로 묶기 전에 1인 칸이 모두 커버되므로 중복 그룹을 방지할 수 있다.
또, 여기서 교환법칙을 이용하여 중복을 제거하기 전의 논리식 [math(\overline{A}C+BC+AB)] 를 [math(AB+BC+C\overline{A})] 로, 중복 제거 후의 논리식 [math(\overline{A}C+AB)] 를 [math(AB+C\overline{A})] 로 바꾸면, 이는 논리 연산의 법칙 중 하나인 합의 법칙 (consensus) 중 [math(AB + BC + CA' = AB + CA')]가 성립함을 보여준다.