Karnaugh map (K-map)

앞서 Canonical Form을 사용해서 부울 함수를 논리 게이트로 표현하는 방법을 알려드렸습니다. 그러나 이렇게 얻어진 회로는 불필요한 게이트를 포함할 수 있습니다. 따라서 회로를 더 간단하게 최소화하는, 게이트 레벨 최소화(gate-level minimization)가 필요합니다.

카노 맵 (또는 K-맵)은 부울 함수를 쉽게 최소화할 수 있는 방법입니다. 카노 맵을 사용해서 부울 함수를 최소화하면 더 적은 게이트로 동일한 기능을 구현할 수 있습니다.

카노 맵을 활용한 게이트 레벨 최소화는 아래의 세 단계를 거칩니다.

1. Contruction
2. Grouping
3. Solution

입력의 개수에 따라 카노 맵의 모양이 조금씩 달라지는데요, 입력이 두 개, 세 개, 네 개인 경우를 설명드리겠습니다. 물론 입력이 더 많은 경우에도 카노 맵을 통한 게이트 레벨 최소화가 가능합니다. 그러나 입력이 많아지면 복잡하기도 하고요, 사실 게이트 레벨 최소화는 사람이 하기보다는 설계 툴에서 해주기 때문에 개념을 익히는 것에 초점을 맞추시면 되겠습니다.

2-input K-Map

아래의 진리표를 예로 들겠습니다. 입력은 A, B이고 출력은 F입니다.

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

그냥 함수를 바로 minterm으로 표현한다면 아래와 같을 텐데요,

\[F(A,B) = A'B + AB' + AB\]

카노 맵을 활용해 최소화해보겠습니다.

Step 1. Construction

카노 맵은 네모칸들로 구성됩니다. 모든 입력의 경우를 표현할 수 있도록 직사각형 그림을 그립니다. 입력이 두 개이므로 네모 칸의 개수는 $2^2 = 4$ 개입니다. 그 후 함수를 1로 만드는 조건의 네모 칸($m_1, \space m_2, \space m_3$)을 1로 표시합니다.

Step 2. Grouping

1로 표시된 블록들을 아래의 규칙에 따라 묶어줍니다. 위의 그림에서는 초록색과 파란색 그룹으로 묶었습니다.

1. 하나의 그룹이 최대한 많은 1을 포함하도록 묶습니다. 단, 그룹에 포함된 1의 개수는 2의 거듭제곱 수이어야 합니다. (i.e., 1, 2, 4, 8, ..)
2. 인접한 1들끼리만 묶을 수 있습니다.
   • 위아래 또는 좌우
   • 대각선은 안됩니다.
   • 맨 왼쪽과 맨 오른쪽, 맨 위와 맨 아래도 인접한 블록으로 간주합니다.
3. 최대한 많은 그룹을 찾되, 하나의 그룹이 다른 그룹을 완전히 포함해서는 안 됩니다.
   • 빠진 1이 있거나 그룹이 중복되면 안 된다는 뜻입니다.

이때 만들어진 그룹을 주항(prime implicant)이라고 합니다.

Step 3. Solution

1. 주항들을 product term으로 표현합니다.
   • 초록색
     • A는 1이어야 합니다.
     • B는 어떤 값이든 상관없으므로 무시합니다.
     • 따라서 A로 표현할 수 있습니다.
   • 파란색
     • A는 어떤 값이든 상관없으므로 무시합니다.
     • B는 1이어야 합니다.
     • 따라서 B로 표현할 수 있습니다.
2. 위에서 구한 product term(A와 B)을 모두 더해줍니다.
   • $F(A, B) = A + B$​

3-input K-Map

입력은 A, B, C이고 출력은 F입니다.

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

Step 1. Construction

마찬가지로 모든 입력의 경우를 표현할 수 있도록 직사각형 그림을 그립니다. 입력이 세 개이므로 네모 칸의 개수는 $2^3 = 8$ 개입니다. 함수를 1로 만드는 조건의 네모 칸($m_2, \space m_3, \space m_4, \space m_5$)을 1로 표시합니다. 이때, BC의 순서가 00, 01, 11, 10 인 것에 주의해 주세요. 카노 맵을 그릴 때는 그레이 코드 순서대로 나열해야 합니다.

Step 2. Grouping

2-input 일 때와 동일한 규칙으로 그룹을 묶어줍니다.

Step 3. Solution

1. 묶어준 그룹들을 product term으로 표현합니다.
   • 초록색 그룹
     • A는 0이어야 합니다.
     • B는 1이어야 합니다.
     • C는 어떤 값이든 상관없으므로 무시합니다.
     • 따라서 A’B로 표현할 수 있습니다.
   • 파란색 그룹
     • A는 1이어야 합니다.
     • B는 0이어야 합니다.
     • C는 어떤 값이든 상관없으므로 무시합니다.
     • 따라서 AB’로 표현할 수 있습니다.
2. product term(A’B와 AB’)을 모두 더해줍니다.
   • $F(A, B, C) = A’B + AB’$

4-input K-Map

맨 왼쪽과 맨 오른쪽, 맨 위쪽과 맨 아래쪽도 인접한 블록으로 간주한다는 것에 주의해 주세요.

• 초록색 그룹
  • A는 어떤 값이든 상관없으므로 무시합니다.
  • B는 어떤 값이든 상관없으므로 무시합니다.
  • C는 1이어야 합니다.
  • D는 0이어야 합니다.
  • 따라서 CD’로 표현할 수 있습니다.
• 파란색 그룹
  • A는 어떤 값이든 상관없으므로 무시합니다.
  • B는 0이어야 합니다.
  • C는 어떤 값이든 상관없으므로 무시합니다.
  • D는 0이어야 합니다.
  • 따라서 B’D’로 표현할 수 있습니다.

최소화된 함수는 $F=CD’ + B’D’$입니다.

Logic Minimization using Product of Sums

위에서는 계속 minterm을 사용했었는데요, maxterm도 사용할 수 있습니다. 3-input 한 가지만 예로 들어볼게요.

이번에는 0인 곳들을 그룹으로 묶어줍니다.

• 초록색 그룹
  • C는 무시합니다. $A+B$로 표현할 수 있습니다.
• 파란색 그룹
  • C는 무시합니다. $A’+B’$로 표현할 수 있습니다.

위에서 구한 각 그룹을 곱하면 아래와 같이 최소화된 함수를 구할 수 있습니다.

\[F = (A+B)(A'+B')\]

Don’t Cares

때로는 모든 입력에 대해 출력이 정의되지 않은 경우가 있습니다. 예를 들어, 특정 입력에 대해서는 출력이 어떤 값이든 상관없을 수 있습니다. 특정 상황에서만 동작하는 회로라던가 절대로 정해진 입력 이외에는 다른 입력이 들어오지 않는 경우가 있을 수 있겠죠. 이 경우 출력을 don’t care라고 정의하고 0이나 1이 아닌 X로 표시합니다.

이 경우 don’t care 조건은 필요에 따라 0이 될 수도 있고 1이 될 수도 있습니다. 더 최소화된 로직이 나오도록, 그룹을 가장 크게 만들되 불필요한 그룹이 나오지 않게 적절히 선택해서 사용합니다.