Chapter 2: Combinational Logic Design | 조합 논리 설계 완전 정복

Harris & Harris · Digital Design & Computer Architecture

🔮 Chapter 2: Combinational Logic Design

불리언 대수부터 카르노 맵, 멀티플렉서까지 — 조합 논리 설계의 모든 것

Chapter 1에서 0과 1의 세계에 발을 디뎠다면, Chapter 2는 이 0과 1을 의미 있는 논리 기능으로 조합하는 방법을 다룹니다. 조합 논리 회로(Combinational Logic)는 모든 디지털 시스템의 핵심 빌딩 블록이며, ALU에서 주소 디코딩, 데이터 경로 선택에 이르기까지 어디에나 존재합니다. 이 포스트에서는 교과서의 필수 개념과 수식을 정리하고, 2026년 현재 AI 기반 EDA 도구가 논리 합성(Logic Synthesis)을 어떻게 혁신하고 있는지를 함께 살펴봅니다.

⚡ 1. 조합 논리 vs 순차 논리

디지털 회로는 크게 두 가지로 분류됩니다. 이 구분을 명확히 이해하는 것이 설계의 출발점입니다.

🔗 조합 논리 (Combinational) 출력이 오직 현재 입력에 의해서만 결정됩니다. 내부에 기억 장치(Memory)가 없으며, 같은 입력에 항상 같은 출력을 생성합니다. 논리 게이트, 멀티플렉서, 디코더, 가산기 등이 해당합니다.

🔄 순차 논리 (Sequential) 출력이 현재 입력뿐 아니라 과거 상태(State)에도 의존합니다. 플립플롭, 레지스터, 카운터, 상태 머신 등이 해당하며, Chapter 3에서 자세히 다룹니다.

핵심 구분 기준

조합 논리는 피드백 루프(Feedback Loop)가 없는 회로입니다. 만약 회로에 출력이 다시 입력으로 돌아오는 경로가 있다면, 그것은 순차 논리입니다. 교과서에서는 이를 “acyclic(비순환)”이라고 표현합니다.

📐 2. 불리언 방정식 (Boolean Equations)

조합 논리의 동작은 진리표(Truth Table)로 정의하고, 이를 불리언 방정식으로 변환합니다. 진리표를 수식으로 변환하는 두 가지 표준 형태가 있으며, 각각은 서로 보완적(dual) 관계입니다.

📝 SOP & POS

곱의 합 (SOP, Sum-of-Products) 출력이 1인 행에 해당하는 최소항(Minterm)들을 OR로 결합합니다. 각 최소항은 모든 입력 변수의 AND(곱)입니다. 실무에서 가장 많이 사용되는 형태입니다.

합의 곱 (POS, Product-of-Sums) 출력이 0인 행에 해당하는 최대항(Maxterm)들을 AND로 결합합니다. 각 최대항은 모든 입력 변수의 OR(합)입니다. 특정 경우에 더 효율적인 구현이 가능합니다.

SOP 표기법 Y = ĀB + AB = Σm(1, 3)

POS 표기법 Y = (A + B)(Ā + B) = ΠM(0, 2)

두 형태는 논리적으로 동치이며, 하드웨어 구현의 효율성에 따라 적합한 형태를 선택합니다. SOP는 AND-OR 구조로, POS는 OR-AND 구조로 직접 매핑됩니다. 실제 CMOS 구현에서는 NAND-NAND(SOP 등가) 또는 NOR-NOR(POS 등가) 구조가 사용됩니다.

🧮 3. 불리언 대수 (Boolean Algebra)

불리언 대수는 논리 회로를 수학적으로 최소화하기 위한 도구입니다. 게이트 수를 줄이면 면적, 전력, 지연이 모두 줄어들기 때문에, 이는 실무에서 매우 중요한 과정입니다.

📜 핵심 공리 & 정리

정리	AND 형태	OR 형태
항등(Identity)	B · 1 = B	B + 0 = B
영(Null)	B · 0 = 0	B + 1 = 1
멱등(Idempotent)	B · B = B	B + B = B
보수(Inverse)	B · B̄ = 0	B + B̄ = 1
교환(Commutative)	BC = CB	B + C = C + B
결합(Associative)	(BC)D = B(CD)	(B+C)+D = B+(C+D)
분배(Distributive)	B(C+D) = BC+BD	B+CD = (B+C)(B+D)
흡수(Absorption)	B(B+C) = B	B + BC = B

⭐ 드 모르간의 법칙 (De Morgan’s Theorem)

논리 최소화에서 가장 빈번하게 사용되는 정리입니다. NAND/NOR 게이트로 변환할 때 핵심적인 역할을 합니다.

De Morgan's Law A · B = Ā + B̄    |    A + B = Ā · B̄

쉽게 외우는 방법: “연산자를 뒤집고(AND↔OR), 각 변수를 보수화(‘ ̄ ’)한다”. 이 법칙 덕분에 NAND 게이트만으로 또는 NOR 게이트만으로 모든 논리 함수를 구현할 수 있으며, 이것이 NAND/NOR가 “범용 게이트(Universal Gate)”로 불리는 이유입니다.

불리언 대수 최소화 예시 // 원본 식 Y = ĀB̄C + ĀBC + AB̄C + ABC // Step 1: C를 공통 인수로 묶기 (분배법칙) Y = C(ĀB̄ + ĀB + AB̄ + AB) // Step 2: 괄호 내부 단순화 = C(Ā(B̄+B) + A(B̄+B)) // 분배법칙 = C(Ā · 1 + A · 1) // 보수: B+B̄=1 = C(Ā + A) // 항등: X·1=X = C · 1 // 보수: A+Ā=1 // 최종 결과: 4개의 3-입력 게이트 → 1개 버퍼! Y = C

🗺️ 4. 카르노 맵 (Karnaugh Maps)

불리언 대수를 손으로 적용하는 것은 오류가 발생하기 쉽고, 최적 해를 놓칠 수 있습니다. 카르노 맵(K-map)은 이 문제를 해결하는 시각적 최소화 기법입니다. 인간의 패턴 인식 능력을 활용하여 최적의 논리식을 직관적으로 찾아낼 수 있습니다.

🔑 K-map의 핵심 원리

▸ 그레이 코드 배열: 인접한 칸은 오직 하나의 변수만 다르도록 00 → 01 → 11 → 10 순서로 배열합니다. 이 덕분에 인접한 1들을 묶으면 해당 변수가 자동으로 소거됩니다.

▸ 2^N 크기 묶음: 1들을 1, 2, 4, 8개 단위의 직사각형으로 묶습니다. 가능한 한 가장 큰 묶음을 만들수록 더 단순한 식이 나옵니다.

▸ 주항(Prime Implicant): 더 이상 확장할 수 없는 가장 큰 묶음입니다. 최소화된 식은 필수 주항(Essential Prime Implicant)들의 합으로 구성됩니다.

3-변수 카르노 맵 예시: F(A, B, C)

진리표: F = 1 일 때 → (A,B,C) = (0,1,0), (0,1,1), (1,1,0), (1,1,1)

A \ BC	00	01	11	10
0	0	0	1	1
1	0	0	1	1

묶음 결과 F = B   (4칸 묶음: A와 C 모두 소거)

❓ Don’t Cares (X)

Don't Care 조건은 특정 입력 조합이 실제로 발생하지 않거나, 출력이 무엇이든 상관없는 경우를 나타냅니다. K-map에서 'X'로 표시하며, 1들을 더 큰 묶음으로 만들 수 있을 때 선택적으로 1로 취급하여 논리를 더 단순화합니다. 실무에서는 BCD 인코딩(10~15는 미사용)이나 특정 제어 신호 조합에서 자주 등장합니다.

🏗️ 5. 조합 논리 빌딩 블록

기본 게이트를 조합하여 만든 범용 모듈들은 디지털 시스템 설계에서 반복적으로 사용됩니다. 이 빌딩 블록들을 이해하면 복잡한 데이터패스를 설계하는 것이 마치 레고 블록을 조립하는 것처럼 체계적이 됩니다.

🔀 멀티플렉서 (Multiplexer, Mux)

멀티플렉서는 데이터 선택기입니다. 선택 신호(Select)의 값에 따라 여러 데이터 입력 중 하나를 출력으로 연결합니다. N비트 선택 신호로 2^N개의 입력 중 하나를 선택할 수 있습니다.

4:1 멀티플렉서 구조

D0

D1

D2

D3

→

4:1 MUX S[1:0]

→

Y

4:1 Mux 불리언 방정식 Y = S̄₁S̄₀D₀ + S̄₁S₀D₁ + S₁S̄₀D₂ + S₁S₀D₃

멀티플렉서의 강력한 점은 모든 논리 함수를 구현할 수 있다는 것입니다. N-입력 논리 함수는 2^N:1 Mux로 구현 가능하며, 진리표의 출력값을 데이터 입력에 연결하고 변수를 선택 신호에 연결하면 됩니다. 이것이 FPGA의 LUT(Look-Up Table) 구현의 기본 원리이기도 합니다.

🔓 디코더 (Decoder)

디코더는 N개의 입력을 받아 2^N개의 출력 중 정확히 하나만 활성화(One-hot)하는 회로입니다. 메모리 주소 디코딩에서 필수적이며, 어떤 최소항 집합이든 디코더 + OR 게이트 조합으로 구현할 수 있습니다.

SystemVerilog - 2:4 디코더 module decoder_2to4 ( input logic [1:0] a, // 2-bit 입력 input logic en, // Enable 신호 output logic [3:0] y // 4-bit one-hot 출력 ); always_comb begin y = 4'b0000; if (en) y[a] = 1'b1; // a 값에 해당하는 비트만 1 end endmodule

SystemVerilog - 4:1 멀티플렉서 module mux4 ( input logic [3:0] d, // 4개 데이터 입력 input logic [1:0] s, // 2-bit 선택 신호 output logic y // 출력 ); assign y = d[s]; // s 값으로 d 중 하나 선택 endmodule

⏱️ 6. 타이밍과 지연 (Timing & Delays)

이상적인 논리 게이트는 입력 변화에 즉시 반응하지만, 실제 게이트는 물리적 한계로 인해 지연(Delay)이 발생합니다. 이 지연을 정확히 이해하지 못하면 칩이 오동작할 수 있으므로, 타이밍 분석은 디지털 설계의 핵심 역량입니다.

🐢 전파 지연 (t_pd) 입력 변경 후 모든 출력이 최종 값에 도달하는 데 걸리는 최대(Worst-case) 시간. 회로의 동작 주파수를 결정하는 핵심 파라미터입니다.

🐇 오염 지연 (t_cd) 입력 변경 후 어떤 출력이라도 기존 값을 잃기 시작하는 최소(Best-case) 시간. 홀드 타임(Hold Time) 위반 분석에 사용됩니다.

왜 두 가지 지연이 모두 중요한가?

회로 전체의 전파 지연은 가장 긴 경로(Critical Path)에 의해 결정되며, 이것이 최대 동작 주파수를 제한합니다. 오염 지연은 가장 짧은 경로에서 문제가 되며, 이것이 너무 작으면 다음 단의 레지스터에서 홀드 타임 위반이 발생합니다. 따라서 STA(Static Timing Analysis)에서는 t_pd(셋업 체크)와 t_cd(홀드 체크) 둘 다 검증해야 합니다.

직렬 경로의 전파 지연 t_pd(total) = t_pd1 + t_pd2 + ... + t_pdN

직렬 경로의 오염 지연 t_cd(total) = t_cd1 + t_cd2 + ... + t_cdN

글리치(Glitch)도 중요한 타이밍 문제입니다. 서로 다른 경로 지연 때문에 입력이 동시에 도착하지 않으면, 출력이 최종 값으로 안정되기 전에 순간적으로 잘못된 값으로 전환될 수 있습니다. 이를 정적 위험(Static Hazard)이라고 하며, K-map에서 인접하지 않은 주항 사이에 발생합니다. 해결책은 중복 항(Consensus Term)을 추가하는 것입니다.

🚀 7. 2026년 산업 동향: AI가 바꾸는 논리 합성

Chapter 2에서 배운 불리언 최소화와 논리 게이트 매핑은 실무에서 논리 합성(Logic Synthesis)이라는 EDA 도구 단계에서 자동으로 수행됩니다. RTL(Register Transfer Level) 코드를 게이트 수준의 네트리스트로 변환하는 이 과정에서 K-map 원리와 불리언 대수가 핵심 알고리즘으로 작동합니다.

디지털 설계 흐름 (Design Flow)

RTL
HDL 코딩

→

Logic
Synthesis
Ch.2 핵심!

→

Gate
Netlist

→

Place
& Route

→

GDS-II
Tapeout

2026 UPDATE

🤖 AI 기반 EDA — 논리 합성의 새로운 패러다임

2026년 현재, EDA 업계의 3대 기업(Synopsys, Cadence, Siemens EDA)은 AI를 핵심 무기로 논리 합성 도구를 혁신하고 있습니다. 이들 3사가 글로벌 EDA 시장의 약 75%를 점유하고 있으며, AI 기반 최적화 경쟁이 치열합니다.

▸ Synopsys DSO.ai & Synopsys.ai Copilot: 강화 학습(RL)과 생성형 AI(GenAI)를 결합하여 합성 설정을 자동 최적화합니다. 2025년에는 완전 자율 설계 워크플로우를 지원하는 차세대 시스템을 발표했으며, 엔지니어링 작업을 수일에서 수시간으로 단축하는 성과를 보이고 있습니다.

▸ Cadence Cerebrus & Allegro X AI: ML 기반 설계 공간 탐색(Design Space Exploration)으로 PPA(Power, Performance, Area) 최적 조합을 자동으로 탐색합니다. 신호 무결성(Signal Integrity) 최적화까지 AI가 처리합니다.

▸ Siemens Questa One + Agentic AI: 2026년 3월, Siemens는 검증 플랫폼 Questa One에 에이전틱 AI를 통합했습니다. 설계 검증 자동화에 새로운 자율 워크플로우를 도입하고 있습니다.

📊 EDA 시장 성장과 교과서 지식의 연결

글로벌 EDA 시장은 2024년 약 167억 달러에서 2025년 183억 달러로 성장했으며, AI 반도체 설계 수요에 힘입어 연평균 9% 이상의 성장이 지속될 전망입니다. 특히 논리 합성(Logic Synthesis), 타이밍 분석(STA), 검증(Verification) 자동화가 핵심 성장 영역입니다.

Chapter 2에서 배운 불리언 최소화가 실무에서 어떻게 적용되는지 정리하면:

교과서 개념	EDA 도구에서의 적용	대표 도구
불리언 최소화, K-map	Technology-independent 최적화 → Quine-McCluskey, ESPRESSO 알고리즘	Synopsys Design Compiler, Cadence Genus
SOP/POS, 범용 게이트	Technology mapping: 최적화된 논리를 셀 라이브러리의 NAND/NOR 등에 매핑	Synopsys Fusion Compiler
MUX의 논리 함수 구현	FPGA LUT(Look-Up Table) 구현. 6-입력 LUT이 현대 FPGA의 표준	AMD Vivado, Intel Quartus
tpd, tcd, 크리티컬 패스	STA(Static Timing Analysis): 셋업/홀드 체크, 클럭 스큐 분석	Synopsys PrimeTime, Cadence Tempus
글리치/정적 위험	글리치-프리 클럭 멀티플렉싱, CDC(Clock Domain Crossing) 검증	Synopsys SpyGlass, Cadence JasperGold

Synopsys + Ansys 합병의 의미

2025년 7월, Synopsys가 약 350억 달러에 Ansys를 인수하며 EDA 역사상 최대 규모의 합병이 완료되었습니다. 이로써 논리 합성(Synopsys)과 다물리 시뮬레이션(Ansys)이 통합되어, “Silicon-to-Systems” 설계 플랫폼이 현실화되고 있습니다. 특히 멀티다이(Multi-die) 고급 패키징 설계를 위한 통합 솔루션이 2026년 상반기 출시 예정입니다.

📋 핵심 요약

주제	핵심 포인트	연관 공식/도구
조합 vs 순차	조합: 현재 입력만 → 출력. 피드백 루프 없음	—
불리언 방정식	SOP(Minterm의 합), POS(Maxterm의 곱)	Y = Σm(...) | Y = ΠM(...)
불리언 대수	드 모르간 법칙이 핵심. NAND/NOR 범용 게이트	AB=Ā+B̄
카르노 맵	그레이 코드 배열, 2N 묶음, Don't Care 활용	ESPRESSO, Quine-McCluskey
빌딩 블록	Mux = 데이터 선택, Decoder = 주소 디코딩	FPGA LUT = Mux 기반
타이밍	tpd(최대, 셋업 체크) + tcd(최소, 홀드 체크)	PrimeTime, Tempus
2026 EDA 트렌드	AI 기반 합성(DSO.ai, Cerebrus), Synopsys+Ansys 합병	시장 $183B+ (2025)

📚 Reference: Harris, D.M. & Harris, S.L. — Digital Design and Computer Architecture, 2nd Ed. (2012)  |  2026 EDA Data: Synopsys, Cadence, Siemens 공식 발표 및 업계 분석 기반

SoC Design Engineer Blog  ·  socdesignengineer.blogspot.com