Digital Logic & Boolean Algebra

1. Overview

디지털 논리와 불리언 대수(Digital Logic & Boolean Algebra, DLB)는 순수한 수학적 논리를 물리적인 전압(Voltage)의 높낮이로 멱살 잡고 끌어내려, 실리콘 웨이퍼 위에서 실제로 '생각(Compute)'을 수행하는 스위치 덩어리를 만들어내는 하드웨어 공학의 기원점입니다.

학습자는 수학적 명제를 0과 1의 전기 신호로 번역하는 **불리언 대수(Boolean Algebra)**의 정규화 공정을 뜯어보고, 이를 AND/OR/NOT 트랜지스터 게이트로 맵핑하는 **조합 논리(Combinational Logic)**를 해부합니다. 나아가 과거의 신호를 기억하기 위해 출력선을 다시 입력선으로 꼬아 넣는(Feedback) **순차 논리(Sequential Logic)**와 플립플롭(Flip-Flop)의 물리를 통달하여, 수동적인 전선 뭉치를 능동적인 CPU 레지스터(Register)로 진화시키는 회로 설계 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 물리적 스위치 역학 (Switch Mechanics): NMOS/PMOS 트랜지스터를 이용한 논리 게이트 구현, 전파 지연(Propagation Delay).
• 조합 논리 회로 (Combinational Circuits): 카르노 맵(K-Map) 최적화, 가산기(Adder), 멀티플렉서(MUX), 디코더(Decoder), 산술 논리 장치(ALU) 기초.
• 순차 논리와 기억 소자 (Sequential Physics): 상태(State)와 클럭(Clock), SR 래치(Latch), D/T/JK 플립플롭(Flip-Flop), 레지스터(Register).
• 상태 기계 모델링 (FSM Modeling): 밀리/무어 머신(Mealy/Moore Machine), 상태 전이도(State Transition Diagram).

Out-of-Scope

• 프로세서 파이프라인 설계: 여러 개의 명령어를 겹쳐서 실행하는 클럭 동기화 기법 $\rightarrow$ 02-03. Parallel & Multicore Mechanics 영역.
• 아날로그 전자기학: RLC 회로의 과도 응답이나 라플라스 변환, 전자기파 방정식 $\rightarrow$ 전자/통신 공학 고유 영역.

Boundaries

• DLB vs. Mathematics Boolean Algebra (01-02-02): 수학(01-02-02)에서의 불리언 대수가 '어떤 수식을 가장 짧게 압축할 수 있는가(최소화 알고리즘)'에 집중한다면, DLB는 압축된 수식이 '물리적으로 몇 나노초(ns)의 전파 지연(Delay)을 일으키며, 클럭 타이밍을 어긋나게 하진 않는지'를 묻는 극한의 물리 공학입니다.

3. Counterexample

• 클럭 비동기화의 치명적 경합 (Race Condition in Hardware): "플립플롭들이 알아서 동시에 값을 저장하겠지"라고 믿고 클럭 엣지(Clock Edge)를 엄밀하게 맞추지 않는 행위. 회로 선의 길이 차이로 인해 클럭 신호가 나노초(ns) 단위로 늦게 도착하는 '클럭 스큐(Clock Skew)'를 무시하면, A 플립플롭이 값을 뱉기도 전에 B 플립플롭이 쓰레기 값을 읽어버리는 물리적 경쟁 상태(Race Condition)가 터져 칩 전체가 쓰레기가 됩니다.
• 조합 논리 지연 누적 (Deep Combinational Delay): 복잡한 암호화 알고리즘을 짠답시고 AND/OR 게이트를 100층 높이로 쌓아 올리는 설계. 입력 전압이 출력 끝까지 도달하는 전파 지연 시간($t_{pd}$)이 클럭 주기($T$)보다 길어지면(Setup Time 위반), CPU 클럭이 칠 때마다 잘못된 값을 레지스터에 저장하게 되어 시스템이 부팅조차 되지 않는 붕괴가 일어납니다.

4. Prerequisites

• 논리 및 정규화 기초 (Basic): 드모르간의 법칙과 곱의 합(SOP)을 수식으로 풀어내는 수학적 베이스. (01-02-02 BAC)
• 전기 물리 기초 (Recommended): 전압(Voltage), 전류(Current), 저항(Resistance)이 무엇인지 직관적인 중학교 수준의 이해.

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 게이트 물리학과 전파 지연 (Gates & Propagation Delay)

• Why to Learn: CPU의 성능(GHz 클럭 속도)이 무한히 오르지 못하고 물리적 한계에 부딪히는 진짜 원인(전기가 선을 타고 흐르는 시간)을 직시하기 위해서입니다.
• What to Learn:
  • Concepts: 논리 레벨(Logic Levels, $V_{IH}, V_{IL}$), 노이즈 마진(Noise Margin).
  • Skills: 전파 지연(Propagation Delay, $t_{pd}$), 팬아웃(Fan-out).
  • Tools: 타이밍 다이어그램(Timing Diagram).
  • Trade-offs: 게이트의 크기를 키워 팬아웃(전류 공급력)을 늘리면 다음 단을 빵빵하게 밀어주지만, 자체 커패시턴스가 커져서 스위칭 속도가 굼떠지는(Delay 증가) 아날로그 전자기학의 딜레마.
• How to Learn:
  • 1단계: 5V 전압 중 3V 이상이면 '1', 1V 이하면 '0'으로 인식하는 논리 레벨의 틈새(Noise Margin)가 전자기파 간섭(EMI)을 방어하는 '아날로그를 디지털로 둔갑시키는 속임수'임을 해부합니다.
  • 2단계: 입력 A가 1로 바뀌고 나서 출력 Y가 0으로 떨어지기까지 걸리는 시간($t_{pd}$)을 타이밍 다이어그램으로 그리며, 소프트웨어의 무한 속도가 하드웨어에서 어떻게 지연(Delay)으로 박살 나는지 뜯어봅니다.
• Implement: 파이썬으로 딜레이가 $5ns$인 AND 게이트 클래스를 만들고, 게이트를 10직렬 연결했을 때 입력 변화가 출력 끝에 도달하기까지 $50ns$가 걸림을 타임스탬프 로깅으로 시뮬레이션하는 하드웨어 에뮬레이터 작성.

Recommended

Core Topic 02: 조합 회로와 하드웨어 레고 조립 (Combinational Circuits)

• Why to Learn: 단순한 AND/OR 게이트 몇 개를 이리저리 납땜(Wiring)하면, 두 이진수를 기계적으로 더하는 계산기(ALU)의 핵심 부품이 만들어지는 마법을 조립하기 위함입니다.
• What to Learn:
  • Concepts: 디코더(Decoder), 인코더(Encoder), 멀티플렉서(Multiplexer, MUX).
  • Skills: 반가산기(Half Adder), 전가산기(Full Adder), 리플 캐리 가산기(Ripple Carry Adder).
  • Tools: Logisim 툴.
  • Trade-offs: 리플 캐리 가산기의 극한의 물리적 면적(트랜지스터 수) 다이어트 효과 vs 하위 비트의 캐리(올림수)가 최상위 비트까지 도달할 때까지 끔찍한 직렬 딜레마($O(N)$ 지연)를 감수해야 하는 속도 희생.
• How to Learn:
  • 1단계: 2개의 입력 신호(S0, S1)를 받아 4개의 데이터(D0~D3) 중 단 하나만 콕 집어 출력선으로 통과시키는 MUX가, 소프트웨어의 if-else 블록을 완벽하게 대체하는 100% 하드웨어 스위치임을 해부합니다.
  • 2단계: XOR 게이트(합)와 AND 게이트(올림수)를 합친 반가산기를 블록으로 삼아 전가산기를 만들고, 이를 $N$개 이어 붙이는 캐리 체인(Carry Chain)의 물리적 구조를 뜯어봅니다.
• Implement: 4비트 이진수 A와 B를 입력받아 전가산기(Full Adder) 객체 4개를 내부적으로 인스턴스화하여, 하위 비트의 캐리가 상위 비트의 캐리-인으로 순차적으로 전달(Ripple)되는 과정을 print 로그로 렌더링하는 가산기 시뮬레이터.

Practical

Core Topic 03: 순차 논리와 메모리의 기원 (Sequential Logic & Flip-Flops)

• Why to Learn: 현재 입력만 보고 출력을 내뱉는(기억 상실증) 조합 회로를 넘어, 출력된 결과를 다시 입력으로 물어뜯어(Feedback) "내가 방금 무슨 값을 가졌었는지"를 기억(Memory)하는 1비트 저장소의 기원을 꿰뚫기 위함입니다.
• What to Learn:
  • Concepts: 상태(State), 클럭 신호(Clock Signal).
  • Skills: SR 래치(Latch), D 플립플롭(Flip-Flop), 셋업/홀드 타임(Setup/Hold Time).
  • Tools: 클럭 엣지(Edge-triggered) 트리거링.
  • Trade-offs: 입력이 바뀌는 즉시 상태가 변하는 래치(Latch)의 무자비한 빠른 속도 vs 타이밍이 조금만 꼬여도 시스템이 미쳐 날뛰는 비동기 리스크 때문에 클럭이 뛸 때(Edge)만 상태를 바꾸도록 플립플롭(D-FF)으로 강제 통제하는 동기식(Synchronous) 안정성.
• How to Learn:
  • 1단계: 두 개의 NOR 게이트의 출력을 서로의 입력으로 꼬아 묶어버린 SR 래치 회로에서, 전원이 끊기기 전까지는 1 또는 0 상태를 무한히 유지하는 쌍안정성(Bistability)의 마법을 해부합니다.
  • 2단계: 클럭 엣지가 치기 직전(Setup Time)과 직후(Hold Time)에는 절대로 입력 데이터(D)가 흔들리면 안 된다는 메타스테빌리티(Metastability, 상태 붕괴) 회피 물리를 뜯어봅니다.
• Implement: 파이썬 제너레이터(Generator)를 사용해 주기적인 0/1 클럭 신호를 방출하고, D-플립플롭 클래스가 클럭의 상승 엣지(Rising Edge)가 감지될 때만 입력값을 자신의 내부 self.state 변수로 래칭(Latching)하여 저장하는 메모리 소자 시뮬레이션.

Advanced

Core Topic 04: 유한 상태 기계 (Finite State Machine, FSM) 설계

• Why to Learn: CPU 안의 컨트롤 유닛(Control Unit)이 "명령어 패치 $\rightarrow$ 디코드 $\rightarrow$ 실행"이라는 거대한 사이클을 어떻게 꼬임 없이 기계적으로 밟아나가는지 그 제어 아키텍처를 마스터하기 위함입니다.
• What to Learn:
  • Concepts: 상태 전이도(State Transition Diagram), 상태 표(State Table).
  • Skills: 밀리 머신(Mealy Machine), 무어 머신(Moore Machine), 원-핫 인코딩(One-Hot Encoding).
  • Tools: Verilog/VHDL FSM 모델링.
  • Trade-offs: 상태값을 이진수 00, 01, 10, 11로 압축하면 플립플롭 개수는 줄어들지만 넥스트 스테이트 조합 논리(AND/OR)가 복잡하게 꼬이는 현상 vs 상태마다 플립플롭을 1개씩 다 박아버리는 원-핫(One-Hot) 인코딩을 쓰면 레지스터는 낭비되지만 디코딩이 필요 없어 클럭 스피드가 극강으로 치솟는 속도전.
• How to Learn:
  • 1단계: FSM이 결국 "현재 상태(플립플롭)"와 "외부 입력"을 두 개의 축으로 받아들여 넥스트 스테이트 조합 논리를 거친 뒤 다시 플립플롭에 덮어쓰는 거대한 '순환 피드백 링'임을 뜯어봅니다.
  • 2단계: 출력이 오직 '상태'에만 의존하여 한 박자 늦지만 매우 안정적인 무어 머신(Moore)과, 출력이 '상태+입력'에 즉시 반응하여 번개같이 빠르지만 노이즈(글리치)에 취약한 밀리 머신(Mealy)의 철학적 차이를 해부합니다.
• Implement: 엘리베이터 상태 전이(1층, 2층, 문 열림, 문 닫힘)를 정의한 상태 전이표(State Table) 행렬을 입력받고, 틱(Tick) 신호와 유저 버튼 입력(Input)이 들어올 때마다 상태를 FSM 규칙에 따라 옮겨가며 현재 상태를 콘솔에 출력하는 하드웨어 제어기 모사 로직.

7. Terminology

8. References

Primary

• [P1] CS2023 - AR/Digital Logic and Digital Systems — Core requirements.
• [P2] SWEBOK v4.0 - Computing Foundations / Digital Logic — Engineering context.

Secondary

• [Digital Design and Computer Architecture] Harris & Harris — Integrated view of logic and arch.
• [Fundamentals of Logic Design] Charles H. Roth — Comprehensive logic theory.

Industry

• [Intel 64 and IA-32 Architectures Software Developer's Manual] — Basic logic in actual ISAs.
• [ASIC/FPGA Design Flows] — Industry optimization standards.

9. Final Checklist

Primary

• 주어진 3변수 논리 게이트 회로를 보고 즉각적으로 진리표를 작성하고 동작을 물리적으로 서술할 수 있는 가? (P1)
• 드 모르간의 법칙을 사용하여 NAND 게이트만으로 OR 연산을 구현하는 회로 구성을 입증할 수 있는 가? (P1)

Secondary

• 카르노 맵에서 특정 묶음이 'Essential Prime Implicant'인지 판별하여 중복된 게이트 제거를 입증할 수 있는 가?
• 전파 지연이 발생했을 때 일시적으로 출력이 튀는 현상(Dynamic Hazard)의 원인을 물리적으로 설명 가능한가?

Industry

• FPGA 설계 시, LUT(Look-Up Table) 소모량을 줄이기 위해 불리언 간소화 기법을 적용한 아키텍처 개선안을 제안할 수 있는 가? (SFIA)
• 고속 연산 장치 설계 시, 'Critical Path'를 분석하여 전체 시스템 클록 속도를 제한하는 병목 게이트를 찾아낼 수 있는 가?