최소항과 최대항
논리 회로를 최적화할 때, "최소항(Minterm)"과 "최대항(Maxterm)" 개념은 매우 중요하다. 이 두 개념을 통해 "카르노 맵(Karnaugh Map, K-Map)"을 사용하여 불 대수식을 단순화하고 회로의 복잡도를 줄일 수 있다.
최소항(Minterm)
"최소항"은 "모든 입력 변수를 포함하는 AND 항"을 의미한다. 즉, 부울 대수에서 모든 입력 변수를 고려한 후, 그 값에 대해 AND 연산을 수행하는 항을 말하는 것이다. 이는 1개의 조합을 나타내며, 모든 변수의 가능한 값을 포함하고 있기 때문에 최소항은 정확히 하나의 진리값(1 또는 0)을 반환한다.
최소항에 대한 구체적인 정의는 다음과 같다.
- 최소항은 모든 입력 변수를 포함하며, 각 변수는 직접 또는 부정(negation)된 형태로 존재해야 한다.
- 예를 들어, A, B, C라는 3개의 입력값이 있을 때, A'BC는 최소항이다. 이는 A가 0, B가 1, C가 1일 때만 참(1)이라는 것을 의미한다.
- 반면, AB'는 최소항이 아니다. 그 이유는 해당 식이 C 값에 대한 정보를 제공하지 않기 때문이다. 따라서 C 또는 **C'**이 추가되어야 최소항이 된다.
최소항의 합
진리표가 주어졌을 때, 진리표에서 출력이 1이 되는 변수들의 각 조합에 대해 최소항을 형성한 후 각각의 최소항을 "논리합(OR)"으로 묶으면 해당 진리표를 만족하는 정규형 부울함수를 얻을 수 있다. 최소항의 조합으로 만든 정규형 부울함수를 "최소항의 합"이라고 한다.
아래와 같이 진리표가 주어졌다고 하자
| 입력 | $X$ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| $Y$ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |
| $Z$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| 출력 | $F$ | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
출력이 1이 되는 값을 찾고 논리합 형태로 정리하면 다음과 같다.
$$ F(X, Y, Z) = \bar{X}\bar{Y}Z + X\bar{Y}\bar{Z} + XYZ $$
최대항(Maxterm)
"최대항"은 "모든 입력 변수를 포함하는 OR 항"을 의미한다. 최소항과 달리, 부울 대수에서 모든 입력 변수를 고려한 후, 그 값에 대해 OR 연산을 수행하는 항을 말한다. 최대항은 주어진 입력값에 대해 0일 때 참(1)이 되는 식을 나타냅니다.
최대항에 대한 구체적인 정의는 다음과 같다.
- 최대항은 모든 입력 변수를 포함하며, 각 변수는 직접 또는 부정된 형태로 나타난다.
- 예를 들어, A, B, C라는 3개의 입력값이 있을 때, A + B + C는 최대항이다. 이는 A가 0, B가 0, C가 0일 때만 참이 되는 조건을 표현한다.
- 반면, A' + B + C'도 최대항으로, 이는 A = 1, B = 0, C = 1일 때 참을 반환하는 식입니다.
최대항의 곱
반대로, 진리표가 주어졌을 때 진리표에서 출력이 0이 되는 변수들의 각 조합에 대해 최대항을 형성한 후 각각의 최대항을 "논리곱(AND)"으로 묶으면 해당 진리표를 만족하는 정규형 부울함수를 얻을 수 있다. 최대항의 조합으로 만든 정규형 부울함수를 "최대항의 곱"이라고 한다.
아래와 같이 진리표가 주어졌다고 하자
| 입력 | $X$ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| $Y$ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |
| $Z$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| 출력 | $F$ | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
출력이 0이 되는 값을 찾고 논리곱 형태로 정리하면 다음과 같다.
$$ F(X, Y, Z) = (X+Y+Z)(X+ \bar{Y} + Z)(X + \bar{Y} + \bar{Z})(\bar{X} + Y + \bar{Z})(\bar{X} + \bar{Y} + Z) $$
최소항 VS 최대항
최소항과 최대항 둘 다, 모든 가능한 입력의 경우의 수 중 하나의 경우를 나타낸다. 다만, 최소항이 출력이 1인 경우를 나타내는 것과 달리, 최대항은 출력이 0인 경우에 대해 정의된다.
최소항의 경우는 합 형태로, 최대항은 곱 형태로 진리표를 부울함수로 표현할 수 있다. "최소항의 합", "최대항의 곱" 이외에 부울함수를 표현할 수 있는 방법은 없다. 이것이 바로 부울함수의 정규형이다. 이때, 최소항의 합의 보수 표현이 바로 최대항의 곱이다.
카르노 맵 (K-map)
카르노 맵(K-Map)은 논리식을 체계적으로 간소화하는 방법으로 부울 대수를 이용한 논리식 간소화에 비해서 더 직관적이고 편리하다는 장점이 있다. 카르노 맵은 입력의 개수에 따라 구성 방식이 달라진다.
인접 사각형 (Adjacent Squares)
카르노 맵에서 사용되는 중요 개념인 인접 사각형이란, 한 개의 변수만 다르고 나머지 변수는 동일한 두 개의 칸(셀)을 의미한다. 이는 변수 하나만 다를 때 논리식이 간소화될 수 있다는 원리를 기반으로 한다. 이때, 두 개의 사각형(셀)이 인접하기 위해서는 다음 조건 중 하나를 만족해야 한다.
- 변수가 하나만 달라야 한다: 즉, 1비트 차이만 존재해야 함 (그레이 코드 원칙)
- 경계를 넘어 인접할 수 있디: 토러스 구조이기에 맵의 가장자리가 서로 연결되어 있다.
카르노 맵의 종류와 구조
카르노 맵(K-Map)은 변수의 개수에 따라, 2변수 카르노 맵, 3변수 카르노 맵, 4변수 카르노 맵... 등으로 구분된다. 3변수 카르노맵 이상으로 갈수록, 00, 01, 10, 11 2진 계수 순서대로 가는 것이 아니라 인접한 열 사이에는 1비트 차이만 생기도록 해야한다.
2변수 카르노 맵
2변수($X$, $Y$)를 가지는 논리식을 정리할 때 사용하는 카르노 맵으로, 2x2의 형태를 가진다. 형태는 다음과 같다.
3개의 최소항의 합이 다음과 같이 주어진다고 하자.
$$ \begin{align} F &= m_1 + m_2 + m_3 \\[3pt] &= \overline{X}Y + X\overline{Y} + XY \end{align} $$
| 입력 | $X$ | 0 | 0 | 1 | 1 |
| $Y$ | 0 | 1 | 0 | 1 | |
| 출력 | $F$ | 0 | 1 | 1 | 1 |
카르노 맵으로 논리식 간소화를 진행하면 다음과 같다.
입력이 2개인 경우, K-Map 작성 방법
1. 입력이 2개가 있는 진리표를 K-Map으로 그릴 때, 각각의 입력을 $X$, $Y$라고 하면 입력은 출력은 총 4가지가 나오게 된다. $X$가 표현 가능한 입력이 2개$(X, \overline{X})$, $Y$가 표현 가능한 입력이 2개$(Y, \overline{Y})$이기 때문에 그렇다.
2. 그리고 출력칸에 최소항의 출력이 1인 곳(진리표에서 출력이 1인 행)을 카르노 맵에 1로 채우고, 카르노 맵에서 가능한 셀들을 그룹핑한다. 이때 지켜야 하는 규칙은 다음과 같다.
- 이웃한 셀들끼리 묶는다. 떨어져 있거나 대각선으로 이웃한 항은 지울 수 없다.
- 셀들을 2의 지수승 개수(2, 4, 8, 16)로 그룹을 묶는다.
- 셀들은 반드시 직사각형이나 정사각형의 형태로 묶는다.
3. 위의 사진은 위의 표를 기준으로 묶어본 사진이다. $(X, Y)$가 $(1, 0)$ 또는 (1, 1)인 경우에 출력이 1이다. 이 경우는 $Y$와 상관 없이 $X$가 1이 된다. 그리고 $(X, Y)$가 $(0, 1)$, $(1, 1)$일 경우는 출력이 1이다. 이 경우는 $Y$의 값을 고려할 필요 없이 $X$값이 1인 경우이다.
4. 결국 이렇게 묶은 사각형은 $X$과 $Y$의 합집합이기에 $X+Y$ 로 적을 수 있다. 최종적으로 식 정리를 진행하면 다음과 같다.
$$ \begin{align} \overline{X}Y + X\overline{Y} + XY &= \overline{X}Y + X(\overline{Y} + Y) \\[5pt] &= (\overline{X}+X)(Y + X) \\[5pt] &=X + Y \end{align} $$
3변수 카르노 맵
3변수$(X, Y, Z)$ 논리식을 정리할 때 사용하는 카르노 맵으로, 2x4 형태로 구성된다. 경계를 넘어 인접할 수도 있다.
입력이 3개인 경우, K-Map 작성 방법
위의 사진의 K-Map 그림을 보면 알 수 있듯이, 3변수 카르노 맵에서는 $YZ$에 해당하는 부분이 00, 01, 11, 10으로 되어있는데 2진수의 원래 순서인 00, 01, 10, 11와 다르다. 그 이유는 바로 "셀들을 묶을 때 이웃한 셀들을 묶는데, 이웃한 셀들은 1비트만 달라야 하기 때문이다.", 이웃한 셀들이 1비트만 달라야 하는 이유는 1비트만 달라야 묶을 때 해당하는 변수를 1개씩 삭제할 수 있기 때문이다.
압력이 3개인 경우도 마찬가지로 그루핑을 통해 식을 정리할 수 있다. 이때는 2개씩 묶는 경우와 4개씩 묶는 경우로 나뉘어지는데, 묶여지는 그룹의 크기에 따라 변수의 개수가 확연히 줄어들게 된다. 그루핑을 할 때 "하나의 셀이 두 번 이상 사용되더라도 크게 묶는 것"이 더 유리하다.
무관 조건 (Don't care 조건)
어떤 특정 입력값은 출력값을 고려할 필요가 없기도 하다. 다르게 말하면 이는 출력값에 전혀 영향을 미치지 않는 입력값이라는 뜻이다. 이를 "무관 조건(Don't care 조건)"이라고 한다. 구체적인 예시로는 위에서 보았던 입력이 2개일 때의 회로 $(X, Y)$가 $(0, 0)$ 또는 $(0, 1)$일 경우는 출력이 $1$이다. 이 경우는 $Y$의 값을 고려할 필요 없이 $X$값이 $0$인 경우이다. 이 부분은 Don't care를 잘 보여준다.
TIP!
Don't care 조건은 x로 표현해놓고 포함할 필요가 있을 때 사용하고, 포함할 필요가 없으면 사용하지 않아도 된다.
즉, 선택적으로 Don't care 조건을 사용하면 되는 것이다.
