[디지털 논리] 4 카르노 맵(Karnaugh Map)

카르노 맵(Karnaugh Map)

카르노 맵(Karnaugh Map)

카르노 맵은 2개에서 5개 사이의 변수를 가진 불 식을, 불 대수를 이용한 복잡한 수식 전개 대신, 표을 이용하요 논리식을 간소화하는 방법이다

주요 목적

• 최소 2단 회로 설계: 논리식을 시각적으로 표현하여 가장 단순한 형태의 회로 구조를 찾아낸다
• 곱의 합(SOP) 형식: 주로 AND-OR 구조로 연결되는 곱의 합 형태를 만드는 데 최적화되어 있다

간소화의 진정한 의미 단순히 식이 짧아지는 것을 넘어, 하드웨어 설계 관점에서 두 가지 큰 이득이 있다.

• 항(Term)의 개수 최소화: 식에 나타나는 항의 개수가 줄어들면, 회로를 구성할 때 필요한 게이트의 수가 줄어든다
• 리터럴의 개수 최소화: 각 항에 포함된 변수의 수가 줄어들면, 각 게이트에 연결되는 입력 핀의 수가 줄어들어 회로가 더 단순해진다

2-변수 카르노 맵

2개의 변수 $A,B$가 있을 때, 가능한 조합은 4가지이다. 따라서 카르노 맵은 4개의 칸으로 구성된다

카르노 맵에서 가장 중요한 규칙은 이웃한 칸끼리는 단 하나의 변수만 다르다는 것이다. 맵에서 1이 적힌 인접한 칸들을 묶으면, 값이 변하는 변수는 제거되거 값이 고정된 변수만 남게 된다

예제:*

• 진리표

A	B	F
0	0	1
0	1	1
1	0	0
1	0	0
1	1	0

• 카르노 맵 채우기

• 따라서 $F=A^{\prime }{B}^{\prime }+A^{\prime }B=A^{\prime }$

3변수 카르노 맵

3개의 변수 카르노 맵은 8개의 칸을 가진다. 보통 세로로 긴 직사각형 모영으로 그리며, 한쪽에는 변수 a를, 다른 쪽애는 변수 bc를 배치한다

• 세로축의 순서를 보면 00 → 01 → 11 → 10 순서이다. 왜냐하면, 인접한 칸끼리 딱 한 비트만 다르게 만들기 위해서이다. 이렇게 해야 수학적으로 묶어서 변수를 지울 수 있다.
• 순서 때문에 칸 번호가 0,1,3,2,4,5,7,6 순으로 매겨진다
• 순환 인접성: 맵의 맨 위 칸과 맨 아래 칸은 서로 연결되어 있다고 간주한다

예제: $F=\sum m(1,3,5)$

• 최종식: $F=a^{\prime }c+b^{\prime }c$

진리표에서 식 도출하기

• 최종식: $F=a^{\prime }b+b{c}^{\prime }+a{c}^{\prime }$

함수의 카르노 맵 표현

최소항과 최대항의 기입 카르노 맵의 각 칸은 진리표의 한 행과 대응한다

• 최소항 전개: 주어진 함수에 포함된 최소항 위치에 1을 적는다
• 최대항 전개: 주어진 함수에 포함된 최대항 위치에 0을 적는다

예제: $F(a,b,c)=\sum m(1,3,5)=\prod M(0,2,4,6,7)$

곱의 항(Product Term)의 영역 이해

함수를 맵에 그릴 때, 수식의 각 항이 맵의 어느 영역을 차지하는지 아는 것이 중요하다

주어진 함수의 카르노 맵 작성 예시

함수 $f(a,b,c)=ab{c}^{\prime }+b^{\prime }c+a^{\prime }$ 를 맵에 그리는 과정이다

위 세 영역의 합집합이 해당 함수의 카로노 맵이 된다

카르노 맵으로 보는 합의 정리

합의 정리는 수식으로만 보면 헷갈릴 수 있지만, 카르노 맵으로 보면 중복된 다리를 찾는 것과 같다

공식:

$xy+x^{\prime }z+yz=xy+x^{\prime }z$

• $xy$: 오른쪽 열에 위치한 두 개의 $1$을 묶음
• $x^{\prime }z$: 왼쪽 열에 위치한 두 개의 $1$을 묶음
• $yz$ (합의 항, Consensus Term): 이 두 묶음을 가로로 연결하는 ‘다리’ 역할
• 이미 $xy$와 $x^{\prime }z$가 모든 $1$을 커버하고 있기 때문에, 가로로 묶인 $yz$는 중복이다. 따라서 이 항을 제거해도 논리적으로 동일하며 회로는 더 단순해진다

두 가지 최소형을 갖는 함수

카르노 맵은 효율성이 동일한 두 가지 정답이 나올 수 있다

예시: $F=\sum m(0,1,2,5,6,7)$ 이 함수를 맵에 그리면 지그재그 형태로 배치가 된다. 이때 모든 1을 가장 크게 묶는 방법이 두 가지로 나뉜다

• 두 식 모두 항의 개수와 리터럴의 개수가 동일하다
• 하드웨어 비용 측면에서 우열을 가릴 수 없으므로, 두 식 모두 최소형으로 인정된다

카르노 맵의 그룹화 원칙

효율적인 간소화를 위해 반드시 지켜야 할 기본 규칙들이다

2/4/8… 단위 그룹화: 인접한 최소항들을 반드시 $2^n$개 단위로 묶어야 한다

• 그룹은 항상 직사각형 형태여야 한다
• 2개를 묶으면 변수 1개가 제거되고, 4개를 묶으면 2개, 8개를 묶으면 3개의 변수가 식에서 사라진다

그룹 크기의 최대화: 인접한 최소항들을 포함할 수 있는 가장 큰 크기의 그룹을 만들어야 리터럴이 최소화된다

• 예: 2개씩 두 번 묶는 것보다 4개로 한 번에 묶는 것이 훨씬 유리하다

중복의 최소화: 모든 1을 포함하기 위해 그룹이 겹치는 것은 필수적이지만, 불필요하게 많이 겹치는 것은 피해야 한다

4-변수 카르노 맵

변수가 4개로 늘어나면 총 16개의 칸이 필요하다

• 상하좌우 인접성(adjacent)뿐만 아니라, 네 모서리의 칸들도 서로 인접한 것으로 간주하여 하나의 그룹으로 묶을 수 있다

예제 1: 최소항 전개 간소화 함수: $f_1=\sum m(1,3,4,5,10,12,13)$

맵의 중앙과 경계를 활용해 4개 묶음 1개, 2개 묶음 1개와 1개 묶음 1개를 도출했다. 따라서 간소화 결과는: $f_1=b{c}^{\prime }+a^{\prime }{b}^{\prime }d+a{b}^{\prime }c{d}^{\prime }$이다

예제 2: 모서리 항과 8개 묶음 활용 함수: $f_2=\sum m(0,2,3,5,6,7,8,10,11,14,15)$

네 모서리의 1들을 하나로 묶어 항을 만든다. 8개 묶음 항 하나와, 2개 묶음 하나를 도출했다. 간소화 결과는: $f_2=c+b^{\prime }{d}^{\prime }+abd$이다

예제 3: 기존 논리식의 수정 및 최적화 이미 만들어진 식을 카르노 맵을 통해 더 간단하게 고치는 과정이다 원래 식: $f(a,b,c,d)=acd+a^{\prime }b+d^{\prime }$

맵에 그려본 결과, acd항이 사실은 인접한 1들과 합쳐져 더 큰 그룹인 ac로 묶일 수 있음을 알수 있다. 따라서 최종 최적화 식은 $f=ac+a^{\prime }b+d^{\prime }$이다

무관 조건(Don’t Care Condition, $X$)

무관 조건은 그룹을 묶을 때 필요에 따라 1로 간주하여 포함할 수도 있고, 0으로 간주하여 무시할 수도 있다. X를 적절히 포함하면 그룹의 크기를 더 크게 만둘 수 있어, 결과 식의 리터럴 개수가 줄어든다

예시: 함수: $f=\sum m(1,3,5,7,9)+\sum d(6,12,13)$

• X를 포함하지 않으면 $b^{\prime }{c}^{\prime }d$가 되지만, ‘X’를 포함하여 더 크게 묶으면 $c^{\prime }d$로 식이 훨씬 간단해진다. 따라서 간소화된 식은 다음과 같다. $f=a^{\prime }d+c^{\prime }d$

합의 곱(POS) 형식

지금까지 1을 묶어 곱의 합을 구했다면, 0을 묶으면 합의 곱 형식을 얻을 수 있다. 결과적으로 가장 간단한 최소 합의 곱(POS) 형식을 도출할 때 사용한다

과정: 맵에서 0인 칸들을 가장 크게 묶어 $f^{\prime }$(보수)의 식을 구한다. 구해진 $f^{\prime }$식에 드모르간의 법칙을 적용하여 전체 보수를 취한다

예시: $f^{\prime }=y^{\prime }z+wx{z}^{\prime }+w^{\prime }xy$

보수를 취한 취종 POS 식은: $f=(y+z^{\prime })(w^{\prime }+x^{\prime }+z)(w+x^{\prime }+y^{\prime })$

함축항(Implicants)과 주함축항(Prime Implicants)

효율적인 묶기를 위해 그룹의 자격을 정의하는 용어이다

함축항(Implicants): 맵상에서 단일 1또는 하나로 묶일 수 있는 1들의 모든 그룹을 말한다

주함축함(Prime Implicants, PI): 더 이상 다른 항과 결합하여 변수를 줄일 수 없는 가장 큰 형태의 함축이다

최소 곱의 합과 필수 주함축함

논리식을 최소화할 때는 모든 주함축항을 다 쓰는 것이 아니라, 모든 1을 덮을 수 있는 최소한의 묶음만 선택해야 한다

• 최소 곱의 합(Minimum SOP): 함수의 주함축항 중 일부를 사용하여 모든 1을 덮는 최소 수의 항으로 구성된 식이다
• 필수 주함축항(Essential Prime Implicants, EPI): 특정 최소항이 오직 하나의 주함축항에 의해서만 덮일 때, 그 주함축항을 필수적이라고 한다. 즉, 이 묶음을 빼면 그 1은 어디에도 포함될 수 없기 때문에 결과 식에 무조건 포함되어야 하는 항이다

논리식 최소화의 일반적 절차(Rule)

가장 효율적인 식을 만들기 위해서는 다음 순서를 따르는 것이 정석이다

• 필수 주함축함 먼저 찾기: 맵을 보고 다른 묶음과 겹치지 않는 독자적인 1을 가진 묶음을 먼저 골라낸다
• 나머지 1 채우기: 필수 주함축항만으로 모든 1이 덮이지 않았다면, 남은 1들을 덮기 위해 가장 효율적인 주함축항을 추가로 선택한다. 이때 여러 선택지가 생길 수 있으며, 이에 따라 위에서 배운 다중 최소형이 발생하기도 한다

무관 조건의 활용

무관조건은 필수 주함축항을 결정할 때 독특한 성질을 가진다

• 그룹 확장용: 더 큰 그룹을 만들기 위해 X를 포함할 수 있다
• 비필수성: X 그 자체는 덮어여 할 의무가 잆으므로, X만 덮고 있는 주함축항은 필수 주함축항이 될 수 없다

예시:

예시에서 $1_6$과 $1_{10}$은 각각 하나의 묶음에만 속해 있으므로 이를 포함하는 항들이 필수(Essential)가 된다

5-변수 카르노 맵

5-변수 맵은 기존 4-변수 맵($B,C,D,E$)의 각 칸을 대각선으로 분할하여 5번째 변수($A$)를 추가한 형태이다

맵의 구성및 인접성

• 대각선 분할: 4-변수 맵의 각 파티션을 대각선으로 나누어 두 개의 항을 배치한다
• $A$ 변수의 할당: 보통 대각선 위쪽은 $A=1$ (1631번 칸), 아래쪽은 $A=0$ (015번 칸)을 나타낸다
• 인접성 규칙: 한 칸 내에 대각선으로 마주 보는 두 항은 서로 인접(Adjacent)한 것으로 간주한다. 즉, 4-변수 맵 두 개를 위아래로 겹쳐 놓았다고 생각하고, 같은 위치에 있는 대각선의 위/아래 칸끼리 묶을 수 있다

묶기 예제

변수가 많아진 만큼 묶음의 형태가 입체적으로 변한다

• $B{D}^{\prime }$: $A$값에 상관없이 $B=1,D=0$인 구역을 크게 묶음
• $CDE$: 대각선 방향으로 인접한 칸들을 활용하여 $C,D,E$가 고정된 영역을 묶음
• $A{B}^{\prime }D{E}^{\prime }$: $A=1$인 영역(대각선 위쪽)에서 특정 조건만 묶음

예시 문제: 주어진 최소항들의 집합 $F(A,B,C,D,E)=\sum m(0,1,4,5,13,15,20,21,22,23,24,26,28,30,31)$을 최적화하는 과정이다

• 음영 처리된 1: 이 1들은 오직 하나의 주함축항에만 포함되므로, 이를 포함하는 묶음들은 필수 주함축항이 된다

최종 논리식: 모든 11을 덮기 위해 선택된 최소한의 항들은 다음과 같다: $F=A^{\prime }B{D}^{\prime }+AB{E}^{\prime }+ACD+A^{\prime }BCE+\{\begin{array}{l}ABC\\ \text{or }{B}^{\prime }CD\end{array}$

• 마지막 항은 동일한 효율을 가지므로 둘 중 하나를 선택할 수 있다

카르노 맵의 또 다른 활용

중복 항 제거

때로는 논리식에 새로운 항을 추가함으로써 기존의 더 복잡한 항들을 제거하여 전체 식을 간소화할 수 있다

합의 정리를 이용한 분석 수식 계산을 통해 중복 항을 찾아내는 방법이다

• 예시 식: $F=ABCD+B^{\prime }CDE+A^{\prime }{B}^{\prime }+BCE$
• 과정:
  • 합의 정리를 적용하여 식의 관계를 분석한다
  • $ABCD$와 $B^{\prime }CDE$ 항이 다른 항들의 조합(합의 관계)에 의해 중복됨을 확인된다
  • 해당 항들을 제거한다
• 최소화 결과: $F=A^{\prime }{B}^{\prime }+BC{E}^{\prime }+ACDE$

5-변수 카르노 맵을 이용한 시각적 분석

복잡한 수식 대신 5변수 맵을 그려서 눈으로 중복을 확인하는 방법이다

• 기입 및 분석:
  • 원래 식의 각 항들을 맵에 배치한다
  • 이때 새로운 항을 추가해 본다
  • 새로운 묶음이 생기면, 기존에 흩어져 있던 영역을 더 효율적으로 덮거나 합의 관계로 대체할 수 있게 된다

예시: