논리회로설계 05 - SOP vs POS

 

개요

 

논리식을 어떻게 최소화할 것인가? 이번 강의의 핵심 질문입니다. 지난 강의에서 K-map의 기본을 배웠다면, 이번에는 최적화를 기계적이고 체계적으로 수행하는 방법을 다룹니다.

크게 네 가지 주제를 다룹니다. 첫 번째는 K-Map 최적화 방법론으로, Prime Implicant와 Essential Prime Implicant 개념을 중심으로 체계적인 최적화 절차를 설명합니다. 두 번째는 SOP vs POS로, 0을 묶어 Product-of-Sums 형태를 구하는 방법을 다룹니다. 세 번째는 Don't Care 조합으로, 발생하지 않는 입력을 활용해 추가 최적화를 이루는 방법입니다. 네 번째는 조합 논리 빌딩 블록인 MUX, Decoder, Encoder입니다.

---

1. 용어 정리

Literal (리터럴)

변수가 등장하는 것. 참(true) 또는 보수(complemented) 형태 모두 포함합니다.

F = a'b'c + abc + abc'   →   리터럴 6개: a, a', b, b', c, c'

Implicant (함의항)

F = 1이 되게 하는 모든 곱항(product term)입니다. K-map에서 적법하게 묶인 원(circle)이라고 이해하면 됩니다. 꼭 최대 크기일 필요는 없습니다.

Prime Implicant (주함의항, PI)

더 이상 크게 묶을 수 없는, 최대로 확장된 implicant입니다. 단일 minterm이라도 더 크게 묶을 수 없으면 Prime Implicant가 됩니다.

 

 

Essential Prime Implicant (필수 주함의항, EPI)

특정 minterm을 유일하게 커버하는 Prime Implicant입니다. EPI는 반드시 최종 cover에 포함해야 합니다. 반면 Non-Essential PI(NEPI)는 필요에 따라 선택적으로 포함합니다.

 

Cover와 Cost

개념	정의
Cover	F = 1인 모든 경우를 설명하는 implicant들의 집합. 함수의 특정 구현 방식을 의미합니다.
Cost	게이트 수 + 게이트 입력 수 (NOT 게이트는 무시). 예) G = a'b'c' + b'c + ab → cost = 4 + 10 = 14

---

2. K-Map 최적화 방법론

K-map 최적화는 다음 세 단계를 따릅니다. 이 절차를 기계적으로 적용하면 항상 최소화된 결과를 얻을 수 있습니다.

• Step 1: 모든 Prime Implicant를 구한다.
• Step 2: Essential Prime Implicant 집합을 찾는다.
• Step 3: EPI만으로 모든 1을 커버하는지 확인한다. Yes → 완료! / No → 비용 비교 후 NEPI를 추가한다.

NEPI 선택 방법

EPI로 커버되지 않은 1이 남아 있을 때, Non-Essential PI를 어떻게 선택할지 결정하는 방법입니다.

• 임의의 NEPI I를 포함한 경우의 나머지 cover를 결정합니다.
• I를 포함하지 않은 경우의 나머지 cover를 결정합니다.
• 두 cover의 비용(cost)을 비교하여 낮은 쪽을 선택합니다.

예제 1 (3변수: x, y, z)

EPI를 먼저 구하면 x'z, xz'이 나옵니다. 하지만 이 둘만으로는 모든 1을 커버하지 못하므로 NEPI를 선택해야 합니다. 두 가지 cover를 비교한 결과는 다음과 같습니다.

 

 

Cover	구성	Cost
Cover 1	e.p.i: x'z, xz', y'z'	13
Cover 2	e.p.i: x'z, xz', x'y	13

두 cover의 비용이 동일하므로 어느 쪽을 선택해도 무방합니다.

 

 

 

예제 2 (4변수: a, b, c, d)

EPI는 a'b' 하나뿐이고, 나머지 1들을 NEPI로 커버해야 합니다. 두 가지 cover를 비교합니다.

 

 

Cover	함수식	Cost
Cover 1	F = a'b' + a'cd + abc + b'cd'	20
Cover 2 ✓	F = a'b' + bcd + acd'	15

Cover 2의 비용이 더 낮으므로 Cover 2를 선택합니다.

---

3. SOP vs POS

K-map은 기본적으로 SOP(Sum of Products) 형태를 결과로 냅니다. 하지만 POS(Product of Sums) 형태가 더 저렴한 경우도 있습니다. POS를 구하는 방법은 간단합니다.

• 1 대신 0을 묶습니다.
• minterm 대신 maxterm을 사용합니다.

형태	K-map 작업	예시	Cost
SOP	1을 묶음	F = a'b' + abc	10
POS	0을 묶음	F = (a+b')(b+c)(a'+b)	13

두 형태를 모두 구한 뒤 비용이 낮은 쪽을 선택하면 됩니다.

---

4. Don't Care 조합

Don't Care란?

입력 조합이 절대 발생하지 않는 경우, 출력이 무엇이든 상관없습니다. 이런 입력을 Don't Care라고 하며, K-map에서 X로 표시합니다. Don't Care를 잘 활용하면 원을 더 크게 묶어 추가 최적화가 가능합니다.

사용 원칙

• X를 원에 포함시키는 것이 더 크게 묶는 데 도움이 될 때만 포함합니다.
• 불필요하게 X를 포함시키면 항이 늘어나 오히려 비용이 증가합니다.

경우	설명
✅ Good use	X를 포함해 2셀 원을 만들 수 있을 때 → 변수 소거 가능
❌ Bad use	X를 포함해도 원 크기가 커지지 않을 때 → 불필요한 항 추가

 

예제 1 — F = a'bc' + abc' + a'b'c

Don't care 조건: a'bc, abc. K-map에 X를 배치하고 원을 최대로 묶으면 다음과 같습니다.

Don't care 없이: F = a'bc' + abc' + a'b'c  (항 3개)
Don't care 활용: F = a'c + b             (항 2개, 훨씬 단순)

 

예제 2 — 5위치 스위치

5개의 스위치 위치가 xyz로 인코딩될 때, 위치 2·3·4에서 출력 1, 나머지에서 0을 원합니다. 사용하지 않는 입력 000, 110, 111은 Don't care로 처리합니다.

방법	함수식
Don't care 없이	F = x'y + xy'z'
Don't care 활용 ✓	F = y + z'

주의: Don't Care는 반드시 그 입력 조합이 절대 발생하지 않는다는 확신이 있을 때만 사용해야 합니다. 조금이라도 발생 가능성이 있다면 출력을 0으로 고정하는 것이 안전합니다.

 

 

---

5. XOR / XNOR 게이트

AND, OR, NOT, NAND, NOR 외에도 자주 쓰이는 게이트가 있습니다. XOR(exclusive OR)는 입력 중 홀수 개가 1일 때 출력이 1이 됩니다. OR와 비슷하지만 두 입력이 모두 1이면 0이 나온다는 점이 다릅니다. XNOR는 XOR의 출력에 NOT을 붙인 것입니다.

a	b	XOR (a⊕b)	XNOR (a⊕b)'
0	0	0	1
0	1	1	0
1	0	1	0
1	1	0	1

XOR는 덧셈의 합(sum)을 계산하거나 패리티(parity) 체크 등에 활용됩니다. XNOR는 두 입력이 같을 때 1이 나오므로 동치 비교(equality check)에 유용합니다.

---

6. 조합 논리 빌딩 블록

MUX (Multiplexer)

N개의 입력 중 하나를 선택해서 출력으로 내보내는 회로입니다. 선택은 log₂N 비트의 select 신호로 제어합니다. 철도의 선로 전환기와 같은 원리입니다.

MUX 종류	Select 비트 수	논리식
2:1 MUX	1 bit	f = S'·x1 + S·x2
4:1 MUX	2 bits	S1, S0으로 4개 입력 중 선택
8:1 MUX	3 bits	S2, S1, S0으로 8개 입력 중 선택

실사용 예: 자동차 계기판에서 온도(T), 평균 연비(A), 순간 연비(I), 잔여 거리(M) 중 버튼으로 하나를 선택해 표시할 때, 8비트 4:1 MUX 8개를 사용합니다.

DEMUX (Demultiplexer)

MUX의 반대입니다. 1개의 입력을 받아 N개의 출력 중 하나로 전달합니다. MUX와 쌍으로 사용되는 경우가 많으며, 예를 들어 전화 교환기에서 4개의 전화 중 하나를 연결할 때 MUX→회선→DEMUX 구조를 사용합니다.

Decoder

N개의 입력을 받아 2^N개의 출력 중 정확히 하나만 HIGH로 만드는 회로입니다. 이를 One-hot 출력이라고 합니다. Decoder는 내부적으로 모든 minterm을 계산하는 것과 같습니다.

A1	A0	Y3	Y2	Y1	Y0
0	0	0	0	0	1
0	1	0	0	1	0
1	0	0	1	0	0
1	1	1	0	0	0

Encoder

Decoder의 반대입니다. 2^N개의 입력(One-hot) 중 하나가 HIGH일 때, 해당 위치를 N비트 이진수로 출력합니다. 예를 들어 8:3 Encoder는 8개의 입력 중 HIGH인 것의 번호를 3비트로 출력합니다.

네 가지 블록 비교

구분	MUX	DEMUX	Decoder	Encoder
입출력	N:1	1:N	N → 2^N	2^N → N
반대	DEMUX	MUX	Encoder	Decoder
특징	select로 경로 선택	select로 경로 분배	One-hot 출력	One-hot 입력

---

핵심 요약

주제	핵심 내용
K-Map 최적화 절차	① PI 구하기 → ② EPI 찾기 → ③ EPI만으로 커버 완료 여부 확인 → 안 되면 NEPI 비용 비교 후 추가
EPI vs NEPI	EPI: 반드시 포함. NEPI: 비용 비교 후 선택적으로 포함
SOP vs POS	SOP는 1을 묶고, POS는 0을 묶는다. 비용이 낮은 쪽 선택
Don't Care	원을 크게 만들 수 있을 때만 X를 포함. 발생 가능한 입력이라면 사용 금지
XOR / XNOR	XOR: 홀수 개 1일 때 출력 1 (sum, parity). XNOR: 짝수 개 1일 때 출력 1 (equality)
MUX / DEMUX	MUX: N→1 선택. DEMUX: 1→N 분배. log₂N 비트 select 신호 사용
Decoder / Encoder	Decoder: N→2^N, One-hot 출력, 모든 minterm 계산. Encoder: 반대 방향

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