카르노 맵
카르노 맵은 지난 포스트에서 다룬 불 대수 법칙들을 이용해 논리식을 간소화하는 방법보다 더 쉽고 빠르게 간소화할 수 있는 방법입니다.
카르노 맵은 함수에서 사용되는 최소항들을 각 칸 에 넣고 표로 만든 것입니다. 입력값이 2일 때는 2^2 = 4개의 칸, 3개일 때는 2^3 = 8 (n개 입력 시 2^n개의 칸)개의 칸을 그리게 됩니다.
카르노 맵은 위와 같이 표로 그립니다. 좌상단에는 입력 변수를 표에 상단, 좌측단은 해당 입력 변수로 오는 값들의 경우의 수를 적습니다.
카르노 맵의 칸을 채우는 방법은 다음과 같습니다.
- 함수의 출력이 1이 되는 칸에는
1 - 그렇지 않은 곳에는
0을 적거나 빈 칸 - 무관항에는
X또는d무관항은 입력값이 1이어도 되고, 0이어도 되는 항을 의미합니다.
즉, 이 입력 값이 무엇이 오더라도 함수 결과에 영향을 주지 않는 최소항을 의미합니다.
2변수 카르노 맵
2변수 카르노맵은 위와같이 4칸의 표로 표현됩니다. (A와 B가 바뀌어도 상관없음)
그리고 A와 B의 입력에 따라 출력이 1이 되는 곳을 1로 채웁니다.
예를 들어 F = AB + A'B'에서 각 입력에 대한 출력 결과는 다음과 같습니다.
| 입력 A | 입력 B | 출력 F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
위 결과에 따라 카르노맵을 그려보면 다음과 같습니다.
카르노 맵 묶기
카르노 맵을 통해 논리식을 간소화하기 위해 가장 중요한 작업으로 묶기 작업이 있습니다.
묶기의 규칙은 다음과 같습니다.
- 출력이 같은 항을 1, 2, 4, 8, 16 개로 묶는다.
- 바로 이웃한 항들끼리만 묶인다.
- 직사각형 또는 정사각형 형태로만 묶는다.
- 가능한 크게 묶는다.
- 중복하여 묶을 수 있다면 중복시켜 묶어 최대한 간소화 한다.
- 무관항은 간소화가 된다면 묶어주고 그렇지 않으면 묶지 않는다.
위 규칙에 따라 다음 카르노 맵을 묶어서 논리식을 간소화해보겠습니다.
다음 카르노 맵의 논리 식은 F = A'B' + A'B + AB'입니다.
- 먼저 출력이
1로 동일한A'를 묶습니다. (빨간색 영역) - 이제 우하단의
+ AB'을 처리해야 하는데A'B'를 중복해서 묵으면B'로 간소화되기 때문에 중복해서 묶습니다. - 이에 따라
F = A' + B'라는 간소화된 논리식을 얻을 수 있습니다.불 대수 법칙을 이용해 간소화 하면 다음과 같습니다.
F = A'B' + A'B + A+B'= A'(B' + B) + B' (A' + A) = A' * 1 + B' * 1 = A' + B'불 대수 법칙을 이용하는 것 보다 카르노 맵을 이용하면 더 빠르게 간소화할 수 있다는 것을 느낄 수 있나요?
3변수 카르노 맵
3변수 카르노 맵은 여러 형태가 있지만 다음과 같이 좌측단에 1변수, 상단에 2변수를 같이 사용하는 형태를 가장 많이 사용합니다.
여기서 중요한 점은 상단의 00, 01, 11, 10은 반드시 이 순서대로 와야한다는 것입니다. 이러한 순서를 지키는 이유는 이웃하는 항들으 차이가 1비트씩만 나도록하기 위함입니다.
3변수 카르노 맵에서 각 이웃항들이 1비트씩 차이나기 때문에 양쪽 끝이 서로 연결되어 있다고 보고 같이 묶을 수 있습니다. (붉은 색 영역)
F = A'B'C' + A'B'C + A'BC + A'BC' + AB'C' + ABC'를 간소화 해보겠습니다.
- 4칸이 성립되는 출력이 1인 것들을 크게 묶어
A'로 간소화 (회색 묶음)A가 0일 때 B와 C는 어떤 값이 오든 출력이 1이므로 A'로 간소화됩니다.
- 마찬가지로 4칸이 성립되며 양끝이 연결된 출력이 1인 것들을 묶어
C'로 간소화 (갈색 묶음)C가 0일 때 A와 B는 어떤 값이 오든 출력이 1이므로 C'로 간소화됩니다.
F = A' + C'라는 식 획득
4변수 카르노 맵
4변수 카르노 맵은 다음과 같이 16칸 짜리 맵을 이용합니다. 3변수 때 처럼 이웃 항이 1비트씩만 차이나도록 00, 01, 11, 10로 지정하고 양끝이 연결되어 있다는 개념을 동일하게 적용하면 됩니다.
선택적 카르노 맵
논리식은 하나의 회로에서 다양한 경우가 나올 수도 있으며 결과는 동일합니다. 카르노맵에서도 이러한 여러 카르노 맵 간소화 중 하나를 선택할 수 있습니다.
위와 같은 카르노 맵에서 두 가지의 선택 옵션이 나타나게 됩니다.
F = A'B + AB' + BC
F = A'B + AB' + AC
두 식의 결과는 카르노 맵으로 봐도, 직접 계산해봐도 동일함을 알 수 있습니다. 이런식으로 하나의 카르노 맵에서 여러 간소화 식이 나올 수도 있습니다.
논리식을 카르노 맵으로 작성하기
이번엔 반대로 논리식을 카르노 맵으로 바꿔보겠습니다.
F = ABC + A'B + A'B'라는 논리식을 카르노 맵으로 작성해보겠습니다.
논리식을 카르노 맵으로 바꿀 때 중요한 점은 논리식을 최소항으로 바꿔주어야 한다는 점 입니다. 위 식은 변수 3개를 받고 있습니다. 따라서 각 항에서 변수가 없는 부분인 A'B, A'B'를 3개의 변수가 모두 있는 식으로 바꿔줍니다.
F = ABC + A'B + A'B' = ABC + A'B(C + C') + A'B'(C + C') = ABC + A'BC + A'BC' + A'B'C + A'B'C' = A'B'C' + A'B'C + A'BC' + A'BC + ABC <- 옮기기 좋게 정렬
이렇게 드러난 항들을 모두 1로 채워 카르노 맵을 그려주면 됩니다.
그려진 카르노 맵을 기반으로 간소화 하면 F = A' + BC라는 식을 얻게 됩니다.
