왜 11편만으로는 부족한가

11편에서는 2·3·4변수 함수의 진리표가 정확히 하나의 값(0 또는 1)으로 빠짐없이 채워져 있다고 가정하고 카르노맵 묶음 절차를 배웠다. 그런데 실제 시험 문제와 실제 회로 설계에는 세 가지 상황이 더 있다.

첫째, 입력 조합 중 일부는 애초에 나타날 일이 없거나, 나타나도 출력이 무엇이든 상관없는 경우가 있다(예: BCD 코드는 09만 쓰므로 1015는 나타나지 않는다). 둘째, 변수가 5개로 늘어나면 11편의 $4\times4$ 격자 하나로는 모든 조합을 담을 수 없다. 셋째, 회로 하나가 출력을 여러 개 내야 하는 경우, 출력마다 따로따로 최소화하면 게이트를 낭비하게 된다.

쉽게 말하면: 이 편은 “진리표가 완벽하게 채워진 4변수 이하 함수”라는 11편의 편안한 조건을 하나씩 깨뜨리면서, 그래도 카르노맵으로 최소식을 구하는 방법을 익히는 편이다.

무관항(don’t care): 채워지지 않은 칸을 자유롭게 쓴다

쉽게 말하면: 무관항은 “이 입력은 절대 안 들어오거나, 들어와도 결과가 상관없으니, 간소화에 유리한 쪽으로 마음대로 0 또는 1을 골라도 되는 칸”이다.

무관항(don’t care condition)은 진리표에서 값이 확정되지 않은 입력 조합을 말한다. 표에는 보통 d 또는 X로 표시한다. 18~21편에서 SR 플립플롭의 금지 입력, JK 여기표, 카운터의 미사용 상태를 다룰 때 이미 이 개념을 여러 번 활용했는데, 이번 편에서는 그 근거가 되는 카르노맵 처리 방법을 정식으로 정리한다.

무관항이 생기는 대표적인 상황은 두 가지다.

• 입력 자체가 나타나지 않는 경우: 07편에서 배운 BCD 코드는 4비트로 09만 표현하므로, 4비트 조합 중 10101111(10~15)은 정상적인 BCD 입력으로 절대 나타나지 않는다.
• 출력이 나타나도 결과가 중요하지 않은 경우: 특정 조건에서는 그 출력값을 다음 단계에서 아예 쓰지 않아, 0이 나오든 1이 나오든 시스템 전체에 영향이 없는 경우다.

예제: BCD 홀수 판별 회로

4비트 BCD 입력 $A,B,C,D$(A가 최상위 비트)가 홀수인지 판별하는 함수 $F$를 만든다고 하자. BCD 숫자가 홀수라는 것은 마지막 비트 $D$가 1이라는 뜻이므로, 실제로 나타나는 홀수는 1, 3, 5, 7, 9다.

• $\sum m(\cdots)$: 반드시 출력이 1이어야 하는 최소항
• $d(\cdots)$: BCD로는 나타나지 않아 무관항으로 두는 최소항(10~15)

4변수 카르노맵에 옮기면 다음과 같다(행은 $AB$, 열은 $CD$, 둘 다 그레이 코드 순서).

결과 해석: 놀랍게도 최소식은 $F=D$, 리터럴 하나뿐이다. 이는 “BCD 숫자가 홀수인가”라는 질문이 결국 “마지막 비트가 1인가”와 완전히 같은 질문이기 때문이며, 무관항 6개(10~15)를 전부 1로 채워도 되는 자유를 얻었기 때문에 이렇게까지 줄어들 수 있었다. 만약 무관항을 활용하지 못하고 $\sum m(1,3,5,7,9)$만으로 간소화했다면 $D$ 하나로 줄지 않고 더 긴 식이 나왔을 것이다(직접 확인해보면, 무관항 없이는 $CD=01$ 열과 $CD=11$ 열 중 $AB=11$ 행이 확정된 값이 없어 8칸 전체 묶음을 만들 수 없다).

5변수 카르노맵: 표 두 장을 겹쳐서 읽는다

쉽게 말하면: 5변수 카르노맵은 4변수 카르노맵 두 장을 준비해서, 다섯 번째 변수가 0인 경우와 1인 경우로 나눈 뒤, 두 표에서 같은 자리에 있는 칸끼리도 서로 이웃하는 것으로 취급하는 방법이다.

11편에서 배운 $4\times4$ 격자는 4변수까지만 담을 수 있다. 변수가 5개($A,B,C,D,E$)로 늘어나면, $E=0$일 때의 $4\times4$ 표와 $E=1$일 때의 $4\times4$ 표를 각각 그린 뒤 나란히(또는 포개서) 놓는다. 두 표 모두 행은 $AB$, 열은 $CD$를 그레이 코드 순서로 놓는다는 점은 4변수 카르노맵과 완전히 같다.

핵심은 인접성 규칙이 하나 더 늘어난다는 것이다.

• 각 표 안에서는 11편에서 배운 규칙(가로·세로 그레이 코드 인접, 원통 구조)이 그대로 적용된다.
• 추가로, $E=0$ 표와 $E=1$ 표에서 정확히 같은 위치(같은 $AB$, 같은 $CD$)에 있는 두 칸도 서로 이웃한 것으로 취급한다. 두 칸은 $A,B,C,D$ 값이 완전히 같고 $E$만 0과 1로 다르기 때문에, 정확히 1비트 차이라는 카르노맵 인접 조건을 만족한다.

이 두 번째 규칙을 “두 표를 포개면 겹치는 자리끼리 이웃”이라고 기억하면 쉽다. 종이 두 장을 겹쳐 들었을 때 완전히 겹치는 칸이 바로 그 규칙이 말하는 이웃이다.

예제 1: 두 표를 모두 쓰는 8칸 묶음

다음 함수를 5변수 카르노맵으로 간소화해보자.

먼저 각 최소항을 이진수로 풀어 $B, C$ 값만 확인한다. $A,B,C,D,E$ 순서로 $16A+8B+4C+2D+E$이므로, $m_0=00000$, $m_1=00001$, $m_2=00010$, $m_3=00011$은 모두 $B=0,C=0$이고, $m_{16}=10000$, $m_{17}=10001$, $m_{18}=10010$, $m_{19}=10011$도 모두 $B=0,C=0$이다. 즉 이 여덟 최소항은 $A,D,E$ 값과 관계없이 $B=0,C=0$인 모든 경우를 나열한 것이다.

$E=0$ 표 (행 $AB$, 열 $CD$, $D=0$인 칸만 해당 열에 값이 들어감. $m_0,m_2,m_{16},m_{18}$이 $E=0$)

$E=1$ 표 ($m_1,m_3,m_{17},m_{19}$가 $E=1$)

결과 해석: 5변수 함수였지만 최소식은 리터럴 단 2개다. 이 묶음은 한 표 안의 원통 구조(행 인접) 와 두 표 사이의 포개기(E 인접) 를 동시에 활용한 8칸 묶음이며, 5변수 카르노맵의 핵심 기술을 그대로 보여준다.

예제 2: 한 표 안에서만 묶이는 경우

모든 묶음이 두 표에 걸치는 것은 아니다. 다음처럼 최소항이 한쪽 표에만 있으면 그 표 안에서만 묶는다.

$m_{26} = 11010$($A=1,B=1,C=0,D=1,E=0$), $m_{30}=11110$($A=1,B=1,C=1,D=1,E=0$)이며, 둘 다 $E=0$이므로 $E=1$ 표에는 아무 값도 없다. 두 최소항은 $C$ 자리만 다르고 나머지($A=1,B=1,D=1,E=0$)는 완전히 같으므로 2칸 묶음이 된다.

필수 프라임 임플리컨트: 반드시 골라야 하는 묶음

쉽게 말하면: 어떤 최소항을 커버하는 방법이 딱 하나의 묶음뿐이라면, 그 묶음은 무조건 최종 답에 들어가야 한다.

11편까지는 “가장 큰 묶음부터 찾는다”는 요령만 강조했지만, 실제로는 어떤 최소항을 커버하는 유효한 묶음이 여러 개일 때, 어느 것을 최종 답으로 골라야 하는가라는 문제가 남는다. 이때 기준이 되는 것이 필수 프라임 임플리컨트(essential prime implicant)다.

프라임 임플리컨트(prime implicant)란 더 이상 다른 칸과 합쳐 확장할 수 없는, 가장 큰 형태의 묶음을 말한다(13편에서 퀴인-맥클러스키로 이 개념을 표로 다시 정리한다). 이 중에서도 어떤 최소항 하나를 커버할 수 있는 유일한 묶음이 있다면, 그 묶음은 골라도 되고 안 골라도 되는 것이 아니라 반드시 골라야 최종 함수가 원래 진리표와 일치한다. 이런 묶음을 필수 프라임 임플리컨트라고 부른다.

판정 절차

앞서 BCD 홀수 판별 예제에서는 8칸 묶음 $B'C'$ 하나가 모든 1을 커버했으므로 이 묶음 자체가 유일한 필수 프라임 임플리컨트였다. 반면 여러 개의 서로 다른 묶음이 최소항을 나눠 커버해야 하는 경우에는, 어떤 묶음이 필수이고 어떤 묶음이 없어도 되는지(다른 묶음에 완전히 포함되는 중복 묶음인지)를 하나씩 따져야 한다. 변수가 많아 눈으로 이 판정을 하기 어려울 때는 13편에서 배울 프라임 임플리컨트 차트를 표로 만들어 기계적으로 판정하는 방법이 훨씬 안전하다.

다중 출력 함수의 카르노맵: 게이트를 함께 아낀다

쉽게 말하면: 출력이 여러 개인 회로에서는 각 출력을 따로 최소화하기보다, 여러 출력이 공통으로 쓸 수 있는 AND 항을 찾아 게이트 하나를 나눠 쓰는 것이 전체 게이트 수를 더 많이 줄인다.

실제 회로는 출력이 하나뿐인 경우보다 여러 출력을 동시에 만들어야 하는 경우가 많다(예: 15편의 전가산기는 합 $S$와 자리올림 $C_{out}$ 두 출력을 함께 낸다). 각 출력을 따로 카르노맵으로 최소화하면 각자에게는 최소식이 나오지만, 두 출력이 우연히 같은 곱항을 필요로 한다면 그 AND 게이트를 한 번만 만들어 두 출력에 공유해서 연결하는 것이 전체 게이트 수를 더 아낄 수 있다.

예제: 두 출력에서 공통 항 찾기

다음 두 함수를 함께 구현한다고 하자.

$F_1$의 카르노맵과 간소화

$m_1$과 $m_3$을 묶으면($BC=01,11$, $A=0$ 고정) $A'C$가 나오고, $m_1$과 $m_5$를 묶으면($A=0,1$, $BC=01$ 고정) $B'C$가 나온다. $m_3$은 $A'C$로만, $m_5$는 $B'C$로만 커버되므로 두 묶음 모두 필수다.

$F_2$의 카르노맵과 간소화

$m_1$과 $m_5$를 묶으면($A=0,1$, $BC=01$ 고정) $B'C$가 나오고, $m_4$와 $m_5$를 묶으면($A=1$, $BC=00,01$) $AB'$이 나온다. $m_4$는 $AB'$으로만, $m_1$은 $B'C$로만 커버되므로 두 묶음 모두 필수다.

결과 해석: $F_1$과 $F_2$를 각각 독립적으로 보면 서로 다른 함수이지만, 두 최소식 모두 $B'C$라는 같은 항을 포함한다. 실제 회로를 만들 때는 $B'C$를 계산하는 AND 게이트를 딱 한 번만 만들어 두고, 그 출력을 $F_1$의 OR 게이트와 $F_2$의 OR 게이트에 동시에 연결하면 된다.

POS 간소화 전 과정: 0을 묶어서 곱의 합을 얻는다

쉽게 말하면: SOP를 구할 때는 1이 있는 칸을 묶었다면, POS를 구할 때는 반대로 0이 있는 칸을 묶은 뒤 드모르간 법칙으로 뒤집으면 된다.

10편에서 표준 POS(곱의 합, Product of Sums)를 배웠다. 카르노맵으로 최소 POS를 구하는 절차는 SOP와 접근 방향만 반대다. 함수 값이 0인 칸(즉 $F'$이 1인 칸)을 묶어서 $F'$의 최소 SOP를 먼저 구한 뒤, 드모르간 법칙으로 전체를 뒤집어 POS로 바꾼다.

예제: F(A,B,C) = sum m(0,1,2,3,4)

이 함수는 $F=0$인 최소항이 $m_5, m_6, m_7$ 세 개뿐이다.

결과 해석: $F=(A'+B')(A'+C')$가 최소 POS다. 실제로 대입해서 검산하면, 예를 들어 $m_0(0,0,0)$에서는 $A'+B'=1+1=1$, $A'+C'=1+1=1$이므로 곱은 1이 되어 원래 $F=1$과 일치하고, $m_5(1,0,1)$에서는 $A'+B'=0+1=1$, $A'+C'=0+0=0$이므로 곱은 0이 되어 원래 $F=0$과 일치한다.

자주 출제되는 함정 총정리

• 무관항을 무조건 1로 채우는 착각: 간소화에 도움이 될 때만 1로 채우고, 도움이 안 되면 0으로 두어도 무방하다.
• 5변수 카르노맵에서 두 표 사이의 인접성(포개서 겹치는 자리)을 놓치는 실수: 최상위 변수(이 편의 예제에서는 $E$)로 나눈 두 표에서 같은 위치의 칸도 이웃이라는 점을 빠뜨리면 더 큰 묶음을 놓친다.
• 필요하지도 않은데 억지로 두 표를 함께 묶으려는 실수: 최소항이 한쪽 표에만 몰려 있으면 그 표 안에서만 묶는 것이 맞다.
• 다중 출력 문제에서 공유 가능한 항을 확인하지 않는 실수: 각 출력을 독립적으로만 최소화하면 최소식은 맞아도 전체 게이트 수는 최소가 아닐 수 있다.
• POS 문제에서 1을 묶어 SOP를 구해버리는 실수: POS는 0을 묶어 $F'$의 SOP를 구한 뒤 드모르간 법칙으로 뒤집어야 한다.
• 필수 프라임 임플리컨트 판정 없이 아무 묶음이나 골라 최소식이 아닌 결과를 내는 실수: 어떤 최소항을 커버하는 유일한 묶음인지 반드시 확인하고, 그렇지 않은 묶음(다른 묶음에 완전히 포함되는 묶음)은 제외해야 한다.

핵심 정리

• 무관항(don’t care)은 입력이 나타나지 않거나 출력이 중요하지 않은 칸이며, 간소화에 유리한 쪽으로만 자유롭게 1 또는 0을 선택해 활용한다.
• 5변수 카르노맵은 다섯 번째 변수 값(0/1)으로 나눈 두 장의 4변수 표로 그리며, 각 표 안의 인접성(원통 구조)에 더해 두 표에서 같은 위치에 있는 칸끼리도 서로 이웃으로 취급한다.
• 필수 프라임 임플리컨트는 어떤 최소항을 커버하는 유일한 묶음이며, 최종 최소식에 반드시 포함되어야 한다.
• 여러 출력을 동시에 구현할 때는 각 출력의 카르노맵에서 공통으로 쓸 수 있는 항을 찾아 AND 게이트를 공유하면 전체 게이트 수를 더 줄일 수 있다.
• 최소 POS는 함수 값이 0인 칸을 묶어 $F'$의 최소 SOP를 구한 뒤, 드모르간 법칙으로 전체를 뒤집어서 얻는다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 - 평가영역 
• IEEE Standards