논리회로설계 04 - 카르노 맵(K-map)

 

개요

 

논리식을 어떻게 회로로 만드느냐보다 중요한 것이 있습니다. 바로 어떻게 더 좋은 회로를 만드느냐입니다. 이번 강의는 그 질문에 집중합니다.

크게 세 가지 주제를 다룹니다. 첫 번째는 NAND / NOR 게이트로, AND·OR·NOT보다 실제 하드웨어에서 왜 더 많이 쓰이는지를 설명합니다. 두 번째는 최적화와 트레이드오프로, 회로의 비용(size)과 속도(delay)를 어떻게 평가하는지를 다룹니다. 세 번째는 카르노 맵(K-map)으로, 논리식을 시각적으로 빠르게 간소화하는 방법을 설명합니다.

---

1. NAND / NOR 게이트

NAND와 NOR란?

AND·OR·NOT 외에도 자주 쓰이는 기본 게이트가 있습니다. NAND는 AND 출력에 NOT을 붙인 것이고, NOR는 OR 출력에 NOT을 붙인 것입니다. 회로 기호에서는 출력 쪽에 작은 동그라미(inversion bubble)로 NOT을 표현합니다.

게이트	논리식	진리표 (입력 x1=1, x2=1 일 때)
NAND	(x1 · x2)' = x1' + x2'	출력 = 0 (나머지는 모두 1)
NOR	(x1 + x2)' = x1' · x2'	출력 = 0 (입력 중 하나라도 1이면 0)

 

 

왜 NAND / NOR를 쓸까?

트랜지스터 수준에서 NAND와 NOR는 AND·OR보다 구현이 더 단순합니다. CMOS 회로에서 AND 게이트는 사실 내부적으로 NAND 뒤에 NOT을 붙인 구조입니다. 즉 NAND가 더 기본적인 구성 요소입니다. 그래서 실제 반도체 설계에서는 AND·OR 대신 NAND·NOR로 모든 회로를 구현합니다.

 

 

드모르간 정리와의 연결

드모르간 정리는 NAND·NOR 게이트가 어떻게 동작하는지를 정확히 설명합니다.

• NAND: 입력들을 각각 NOT한 뒤 OR하는 것과 같습니다. → (x1·x2)' = x1' + x2'
• NOR: 입력들을 각각 NOT한 뒤 AND하는 것과 같습니다. → (x1+x2)' = x1'·x2'

이 덕분에 SOP(합의 곱) 형태의 어떤 논리식도 NAND 게이트만으로 구현할 수 있고, POS(곱의 합) 형태는 NOR 게이트만으로 구현할 수 있습니다. AND-OR 회로 사이의 연결에서 생기는 이중 반전(x'' = x)이 서로 상쇄되기 때문입니다.

---

2. 설계 예시 — 자연어를 논리식으로

실제 설계는 자연어로 된 요구사항에서 출발합니다. 변수를 정의하고, 논리식으로 표현한 뒤, 회로를 만드는 흐름입니다.

예시 1: 안전벨트 경고등

"운전자가 착석(p=1)했고, 열쇠가 꽂혀 있고(k=1), 안전벨트를 매지 않았을 때(s=0) 경고등을 켠다."

w = p AND NOT(s) AND k
  = p · s' · k

 

 

예시 2: 자동 슬라이딩 도어

 

"문이 강제로 닫혀 있지 않을 때(c=0), 수동으로 열고 있거나(h=1), 사람이 감지되면(p=1) 문을 열어라."

 

f = hc' + h'pc'

  ← 불 대수로 간소화 →

f = c'h + c'h'p
  = c'(h + h'p)        (분배 법칙)
  = c'((h + h') · (h + p))  (OR의 AND에 대한 분배)
  = c'(1 · (h + p))   (보수 법칙)
  = c'(h + p)          (항등 법칙)

4개의 게이트가 필요했던 회로가 불 대수 간소화를 통해 2개로 줄었습니다. 같은 기능을 더 적은 게이트로 구현할수록 비용이 줄고 속도가 빨라집니다.

 

---

 

3. 최적화와 트레이드오프

회로를 평가하는 두 가지 기준이 있습니다. 두 기준이 동시에 좋아지면 최적화(optimization), 하나가 좋아지고 다른 하나가 나빠지면 트레이드오프(tradeoff)라고 합니다.

기준	정의	측정 방법
지연 (Delay)	입력이 바뀐 후 출력이 안정될 때까지 걸리는 시간	게이트 딜레이 수 (인버터 제외)
크기 (Size)	트랜지스터의 수 (회로 면적과 비례)	게이트 수 + 게이트 입력 수 (인버터 제외)

 

 

예를 들어 F1 = wxy + wxy'을 F2 = wx로 간소화하면 비용(11→3)과 지연(2→1) 모두 줄어드는 최적화입니다. 반면 G1 = wx + wy + z를 G2 = w(x+y) + z로 변환하면 비용(10→9)은 줄지만 지연(2→3)이 늘어나는 트레이드오프입니다. 자동차를 설계할 때 연비·속도·승차감을 동시에 최고로 만들 수 없는 것과 같은 원리입니다.

 

핵심 정리: 최적화(Optimization)는 모든 기준이 개선되거나 유지되는 변환입니다. 트레이드오프(Tradeoff)는 일부 기준은 좋아지지만 다른 기준은 나빠지는 변환입니다. 설계자는 주어진 요구사항에 따라 두 전략을 선택합니다.

---

4. 카르노 맵 (Karnaugh Map)

왜 카르노 맵이 필요한가?

불 대수 조작은 강력하지만 어떤 규칙을 언제 쓸지 판단하기 어렵고, 항을 합칠 기회를 놓치기 쉽습니다. 카르노 맵(K-map)은 이 과정을 시각적으로 만들어줍니다. 인접한 최소항이 하나의 변수만 다르도록 배치해, 인접한 1들을 묶으면 변수를 자동으로 소거할 수 있습니다.

K-map 일반 절차

• 함수를 SOP 형태(또는 진리표)로 변환한다.
• 해당하는 K-map 셀에 1을 채운다.
• 모든 1을 포함하도록 가장 크고 가장 적은 수의 원을 그린다.
• 각 원에 해당하는 항을 OR로 연결해 최소화된 함수를 만든다.

원(묶음)의 규칙

• 원의 크기는 반드시 1, 2, 4, 8, 16 … (2의 거듭제곱)이어야 합니다. 3, 5, 6, 7개는 불가합니다.
• 원은 맵의 좌우 끝, 상하 끝이 서로 인접한 것으로 취급합니다 (토러스 구조).
• 같은 1을 두 원이 중복해서 포함해도 됩니다. 오히려 더 큰 원을 그릴 기회가 됩니다.
• 불필요하게 중복 포함할 필요는 없습니다. 항이 늘어나 최소화가 안 됩니다.
• 모든 1은 최소한 하나의 원에 포함되어야 합니다.

원과 변수 소거의 관계

원의 크기 (셀 수)	소거되는 변수 수	남는 리터럴 수 (n변수 기준)
1	0	n개
2	1	n-1개
4	2	n-2개
8	3	n-3개

원이 클수록 더 많은 변수가 소거되어 항이 단순해집니다. 그래서 항상 가능한 가장 큰 원을 그려야 합니다.

---

5. 2변수 K-map 예시

2변수 K-map은 2×2 격자입니다. 행은 x1 (0→1), 열은 x2 (0→1) 순서입니다.

x1 \ x2	0	1
0	1	0
1	1	1

x1=0 행의 두 셀을 하나의 원으로 묶으면 x1'이 남습니다. x2=0 열의 두 셀을 묶으면 x2'이 남습니다. 두 항을 OR하면 다음과 같습니다.

F = x1' + x2'

 

---

6. 3변수 K-map

3변수 K-map은 2×4 격자입니다. 열 방향 변수(x2, x3)의 순서가 00 → 01 → 11 → 10인 것이 핵심입니다. 이는 그레이 코드(Gray code) 순서로, 인접한 셀이 정확히 한 비트만 다르도록 배치하기 위해서입니다.

3변수 K-map 예시 1

F(x1, x2, x3): 출력이 1인 행 = {1, 2, 3, 5}

x1 \ x2x3	00	01	11	10
0	0	1	1	1
1	0	1	0	0

x1=0 행의 01, 11, 10 → 3셀이라 안 됨
  → 01, 11 묶기: x1'x3 (2셀)
  → 11, 10 묶기: x1'x2 (2셀)
  → 맵의 좌우 끝 연결: 01(x1=0)과 01(x1=1) 묶기: x2'x3

F = x1'x2 + x2'x3

3변수 K-map 예시 2 — 4개의 인접한 1

x1=1 행의 모든 셀(4개)이 1이면 x1 하나만 남습니다. 4개의 인접한 1은 2개의 변수를 소거합니다.

G = xy'z' + xy'z + xyz + xyz'
  = xy'(z'+z) + xy(z+z')
  = xy' + xy
  = x(y'+y)
  = x

---

7. 4변수 K-map

4변수 K-map은 4×4 격자입니다. 행(ab)과 열(cd) 모두 그레이 코드 순서(00→01→11→10)로 배치됩니다. 좌우 끝뿐 아니라 상하 끝도 인접합니다.

ab \ cd	00	01	11	10
00	m0	m1	m3	m2
01	m4	m5	m7	m6
11	m12	m13	m15	m14
10	m8	m9	m11	m10

4변수 맵은 위상적으로 토러스(도넛) 모양과 같습니다. 맵의 네 모서리가 실제로는 모두 인접해 있습니다. 8개의 인접한 1은 변수 3개를 소거할 수 있습니다.

4변수 K-map 예시

F = a'cd' + a'bc'd + acd' + ac'd'을 간소화합니다.

• K-map에 1을 채우고, 가장 큰 원으로 덮으면 세 묶음이 나옵니다.
• cd' 열 전체(a 무관): cd'
• a=1, d=0인 행: ad'
• a=0, b=1, c=0, d=1인 셀: a'bc'd

F = cd' + ad' + a'bc'd

원래 4개의 항이 3개로 줄었고, 각 항의 리터럴 수도 줄었습니다.

---

8. 대수적 조작을 통한 최적화

K-map 이전에, 불 대수 조작으로 직접 간소화하는 방법도 있습니다. 핵심 기법은 통합 정리(Uniting theorem)를 반복 적용하는 것입니다.

ab + ab' = a(b + b') = a · 1 = a   ← 통합 정리

F = xyz + xyz' + x'y'z' + x'y'z
  = xy(z + z') + x'y'(z' + z)
  = xy + x'y'

한 항을 복제해서 다른 항과 두 번 결합하는 것도 허용됩니다. c + d = c + d + d + d + … 이 되기 때문에, 항을 늘리는 것은 함수를 바꾸지 않습니다. 결합 후 다시 결합하는 연쇄 적용이 가능합니다.

---

핵심 요약

주제	핵심 내용
NAND / NOR	트랜지스터 구현이 단순해 실제 하드웨어의 기본 게이트. SOP → NAND only, POS → NOR only로 구현 가능
드모르간과 NAND/NOR	NAND = NOT-AND = 각 입력 NOT 후 OR / NOR = NOT-OR = 각 입력 NOT 후 AND
최적화 vs 트레이드오프	최적화: 비용·지연 모두 개선. 트레이드오프: 하나가 좋아지면 다른 하나가 나빠짐
K-map 원칙	원의 크기는 2의 거듭제곱. 가장 크고 가장 적은 수의 원. 끝이 인접. 중복 포함 OK
원 크기와 소거	2셀 → 1변수 소거 / 4셀 → 2변수 소거 / 8셀 → 3변수 소거
4변수 맵 특성	상하·좌우 끝도 인접. 토러스 구조. 모서리 4셀도 하나의 원으로 묶을 수 있음
대수 조작 핵심 기법	통합 정리: ab + ab' = a. 항 복제 후 재결합 반복으로 단계적 간소화

Digital Logic Design — Yongsoo Joo (Kookmin Univ. KESL) | Lecture 5 정리