"카르노 맵(K-Map)"은 논리식을 체계적으로 간소화하는 방법입니다. 지금부터 카르노 맵에 대해서 알아보도록 하겠습니다.
조합 논리 회로 설계 절차
기본적인 조합 논리 회로 설계 절차는 다음과 같습니다.
1. 문제가 제시된다.
2. 입력 신호와 출력 신호에 문자 기호를 정한다.
3. 진리표를 만든다.
4. 각 출력 신호에 대한 간소화된 논리식을 만든다.
5. 논리도를 그린다.
이 과정을 통하여 조합 논리 회로를 설계합니다. 그리고 조합 논리 회로 설계에 필요한 개념들이 있는데, 그것들에 대해서도 알아보겠습니다.
최소항(Minterm)
"최소항"은 "모든 입력 변수를 포함하는 AND 항"을 의미합니다. 예를 들면 A, B, C 이렇게 3개의 입력값이 있을 때, A'BC는 최소항입니다. 그러나 AB' 항은 최소항이 아닙니다. AB'에 C나 C'이 붙어야 최소항이 될 수 있는 것입니다. 즉, 정리하자면 "모든 가능한 입력의 경우의 수 중 하나의 경우"를 의미하는 것입니다.
최대항(Maxterm)
"최대항"은 "모든 입력 변수를 포함하는 OR 항"을 의미합니다. 예를 들면 A, B, C 이렇게 3개의 입력값이 있을 때, A + B + C가 최대항입니다. A' + B + C' 같은 식도 최대항이 됩니다.
카르노 맵(K-map)
카르노 맵은 입력의 개수에 따라 구성 방식이 달라집니다. 주로 변수가 2개일 때, 변수가 3개일 때, 변수가 4개일 때 등을 주로 사용하는데 이번 포스팅에서는 변수가 2개일 때와 변수가 3개일 때만 다루겠습니다.
2개의 입력이 있는 경우
| a | b | f |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
입력이 2개인 경우, K-Map 작성 방법
1. 입력이 2개가 있는 진리표를 K-Map으로 그릴 때, 각각의 입력을 A와 B라고 하면 입력은 출력은 총 4가지가 나오게 됩니다. A가 표현가능한 입력이 2개(A, A'), B가 표현 가능한 입력이 2개(B, B')이기 때문에 그렇습니다.
2. 그리고 출력칸에 최소항의 출력이 1인 곳(진리표에서 출력이 1인 행)을 K-Map에 1로 채웁니다.
| 1 | 1 |
| 1 | 0 |
3. 그리고 K-Map에서 가능한 셀들을 그룹핑합니다. 이때 지켜야 하는 규칙은 다음과 같습니다.
- 이웃한 셀들끼리 묶습니다. 떨어져 있거나 대각선으로 이웃한 항은 지울 수 없습니다.
- 셀들을 2의 지수승 개수(2, 4, 8, 16)로 그룹을 묶습니다.
- 셀들은 반드시 직사각형이나 정사각형의 형태로 묶습니다.
4. 위의 사진은 위의 표를 기준으로 묶어본 사진입니다. (a, b)가 (0, 0) 또는 (0, 1)일 경우는 출력이 1입니다. (진리표를 보면 알 수 있듯이) 이 경우는 b의 값을 고려할 필요 없이 a값이 0인 경우입니다. 그렇기에 첫 번째 값은 A'으로 표현할 수 있습니다. 그리고 (a, b)가 (0, 0) 또는 (1, 0)인 경우에 출력이 1이다. 이 경우는 A의 값에 상관없이 B가 0인 경우입니다. 그렇기에 이 사각형은 B'입니다.
5. 결국 이렇게 묶은 사각형은 A'과 B'의 합집합이기에 A' + B' 로 적을 수 있습니다. 최종적으로 식 정리를 진행하면 다음과 같습니다.
$$ \begin{align} f(a, b) &= \sum(0, 1, 2) \\ &= a'b' + a'b + ab' \\ &= a'b' + a'b + a'b' + ab' \\ &= a'(b' + b) + b'(a' + a) \\ &= a'1 + b'1 \\ &= a' + b' \end{align} $$
3개의 입력이 있는 경우
입력이 2개인 경우는 아주 간단한 케이스이고, 3개의 입력인 경우에 대해서도 알아보겠습니다. 3개의 경우 K-Map의 구성방식은 다음과 같습니다.
| a | b | c | f |
| 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 |
입력이 3개인 경우, K-Map 작성 방법
일단 위의 사진의 K-Map 그림을 보면 알 수 있듯이, 2진수 비트의 순서가 약간 다릅니다. 00, 01, 11, 10으로 되어있는데 2진수의 원래 순서와는 다릅니다. 그 이유는 바로 "셀들을 묶을 때 이웃한 셀들을 묶는데, 이웃한 셀들은 1비트만 달라야 하기 때문입니다.", 이웃한 셀들이 1비트만 달라야 하는 이유는 "1비트만 달라야 묶을 때 해당하는 변수를 1개씩 삭제할 수 있기 때문입니다."
압력이 3개인 경우도 마찬가지로 그루핑을 통해 식을 정리할 수 있습니다. 이때는 2개씩 묶는 경우와 4개씩 묶는 경우로 나뉘어집니다. 묶여지는 그룹의 크기에 따라 변수의 개수가 확연히 줄어들게 됩니다.
그루핑을 할 때 기억해야 할 것은 "하나의 셀이 두 번 이상 사용되더라도 크게 묶는 것이 가장 좋다"는 것입니다.
Don't care 조건
어떤 특정 입력값은 출력값을 고려할 필요가 없기도 합니다. 다른 말로 출력값에 전혀 영향을 미치지 않는 입력값이라는 뜻입니다. 이를 "Don't care 조건"이라고 합니다. 구체적인 예시로는 아까 보았던 입력이 2개일 때의 회로, (a, b)가 (0, 0) 또는 (0, 1)일 경우는 출력이 1입니다. (진리표를 보면 알 수 있듯이) 이 경우는 b의 값을 고려할 필요 없이 a값이 0인 경우입니다. 이 부분이 Don't care를 잘 표현해줍니다.
Don't care 조건은 x로 표현해놓고 포함할 필요가 있을 때 사용하고, 포함할 필요가 없으면 사용하지 않아도 됩니다.즉, 선택적으로 Don't care 조건을 사용하면 됩니다.
