KAIST CS311 전산기조직 (Spring 2023) 교재: Computer Organization and Design: The Hardware/Software Interface (Patterson & Hennessy, MIPS Edition)
조합 논리 (Combinational Logic)
조합 논리 회로는 현재 입력만으로 출력이 결정되는 회로이다. 내부에 상태(state)를 저장하지 않으므로 같은 입력에는 항상 같은 출력이 나온다. 먼저 조합 논리의 기반이 되는 Boolean Function부터 살펴보자.
Boolean Function
n개의 variable (x, y, z …)이 있을 때, Boolean Function을 표현하는 핵심 용어들은 다음과 같다.
Minterm과 Maxterm
- Minterm: 각각의 variable 또는 그의 complement(x’)를 모두 한 번씩만 사용하여 만든 곱(AND)
- Maxterm: 각각의 variable 또는 그의 complement를 모두 한 번씩만 사용하여 만든 합(OR)
예를 들어 변수가 x, y 두 개일 때:
Minterms (곱): x'y', x'y, xy', xy (2^2 = 4개)
Maxterms (합): x'+y', x'+y, x+y', x+y (2^2 = 4개)
Canonical Form과 Standard Form
- Canonical Form: sum of minterms 또는 product of maxterms로 표현한 Boolean Function
- 모든 term이 모든 variable을 포함해야 한다
- minterm과 maxterm을 사용하므로 not optimal (simplified되지 않은 형태)
- Standard Form: sum of products (SOP) 또는 product of sums (POS)로 표현
- 각 term이 꼭 모든 variable을 포함하지 않아도 된다
- Optimal한 표현 가능 (간소화된 형태)
예) f(x,y,z) = x'yz + xy'z + xyz' + xyz ← Canonical (Sum of Minterms)
f(x,y,z) = yz + xz + xy ← Standard (Sum of Products, 간소화)
Binary Adder
가산기(Adder)는 디지털 회로에서 가장 기본이 되는 산술 연산 블록이다.
Half Adder
두 bit를 더해서 Sum과 Carry out을 도출하는 가장 단순한 가산기이다. Carry in이 없다.
- 입력: x, y
- 출력: S (Sum), C_out (Carry out)
- 논리식: S = x XOR y, C_out = x AND y
- 구성: AND 게이트 1개, XOR 게이트 1개
┌─────────┐
x ──>│ │──> S = x XOR y
│ Half │
y ──>│ Adder │──> C_out = x AND y
└─────────┘
Full Adder
두 bit와 Carry in을 더해서 Sum과 Carry out을 도출한다. Half Adder 2개와 OR Gate 1개로 구성된다.
- 입력: x, y, C_in
- 출력: S, C_out
- 논리식:
- S = (x XOR y) XOR C_in
- C_out = (x AND y) + ((x XOR y) AND C_in)
┌──────────┐
x ──────────────>│ │
│ Half │──> P = x XOR y ──┐
y ──────────────>│ Adder 1 │ │ ┌──────────┐
│ │──> G = x AND y ──│─>│ │
└──────────┘ └─>│ Half │──> S = P XOR C_in
│ Adder 2 │
C_in ───────────────────────────────────────────>│ │──> P·C_in
└──────────┘
│
C_out = G + P·C_in <───── OR <─── G ──────────┘
도출 과정을 자세히 보면:
S = x'y'·C_in + x'y·C_in' + xy'·C_in' + xy·C_in
= (x XOR y)·C_in' + (x XOR y)'·C_in ... 정리하면
= (x XOR y) XOR C_in
C_out = x'y·C_in + xy'·C_in + xy·C_in' + xy·C_in
= (x XOR y)·C_in + xy
= [x AND y] + [(x XOR y) AND C_in]
Ripple-Carry Adder
n-bit Full Adder를 직렬로 연결하여 n-bit 덧셈을 수행한다.
- 입력: A(n-bit), B(n-bit)
- 출력: S(n-bit), C_out(1-bit)
- 구조: 각 Full Adder의 C_out이 다음 Full Adder의 C_in으로 전달
A[0] B[0] A[1] B[1] A[2] B[2] A[3] B[3]
│ │ │ │ │ │ │ │
v v v v v v v v
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐
│ Full │ C[1] │ Full │ C[2] │ Full │ C[3] │ Full │
──│ Adder │─────>│ Adder │─────>│ Adder │─────>│ Adder │──> C_out
│ [0] │ │ [1] │ │ [2] │ │ [3] │
└────────┘ └────────┘ └────────┘ └────────┘
│ │ │ │
v v v v
S[0] S[1] S[2] S[3]
한계: Carry Propagation이 너무 오래 걸린다. 최악의 경우 carry 값이 bit 0부터 bit n-1까지 순차적으로 전파되어야 하므로 O(n) 지연이 발생한다.
Carry Lookahead Adder
Ripple-Carry Adder의 carry propagation 지연을 해결하기 위해, carry를 미리 계산하는 방식이다.
핵심 아이디어는 두 가지 신호를 정의하는 것이다:
- Generate (G_i): G_i = x_i AND y_i — i 단계의 A와 B가 C_out을 발생시키는가? G_i가 1이면 C_in에 무관하게 C_out = 1
- Propagate (P_i): P_i = x_i XOR y_i — i 단계로 들어온 C_in이 C_out으로 그대로 전달되는가? P_i가 1이면 C_in이 그대로 C_out에게 전달
이를 이용하면:
S_i = P_i XOR C_i (= x XOR y XOR C_i)
C_(i+1) = G_i + P_i · C_i
C를 G와 P만으로 전개할 수 있다:
C_1 = G_0 + P_0·C_0
C_2 = G_1 + P_1·C_1
= G_1 + P_1·G_0 + P_1·P_0·C_0
C_3 = G_2 + P_2·C_2
= G_2 + P_2·G_1 + P_2·P_1·G_0 + P_2·P_1·P_0·C_0
C_4 = G_3 + P_3·G_2 + P_3·P_2·G_1 + P_3·P_2·P_1·G_0 + P_3·P_2·P_1·P_0·C_0
Carry Lookahead Generator가 G와 P로만 표현된 C를 병렬로 계산해주는 Unit이다. 이를 통해 carry 계산이 O(1) (게이트 2단계)로 줄어든다.
┌──────────────────────────────┐
G_0, P_0 ──│ │──> C_1
G_1, P_1 ──│ Carry Lookahead Generator │──> C_2
G_2, P_2 ──│ │──> C_3
G_3, P_3 ──│ │──> C_4
C_0 ───────│ │
└──────────────────────────────┘
Decoder
Decoder는 n-bit input binary를 받아 2^n개의 output line 중 하나의 line만 ON 시키는 Unit이다.
- 입력: n-bit binary code
- 출력: 2^n개의 line (하나만 1, 나머지 0)
- 특징: 각 output이 minterm과 같다 — input을 binary code로 해석하고, output은 그에 대응하는 combination
2-to-4 Decoder 3-to-8 Decoder
┌─────────┐ ┌─────────┐
x ──│ │──> D0 = x'y' x ──│ │──> D0 = x'y'z'
│ 2-to-4 │──> D1 = x'y y ──│ 3-to-8 │──> D1 = x'y'z
y ──│ Decoder │──> D2 = xy' │ Decoder │──> D2 = x'yz'
│ │──> D3 = xy z ──│ │──> D3 = x'yz
└─────────┘ │ │──> D4 = xy'z'
│ │──> D5 = xy'z
│ │──> D6 = xyz'
│ │──> D7 = xyz
└─────────┘
Decoder의 output이 minterm과 같으므로, Decoder와 OR 게이트를 조합하면 임의의 Boolean Function을 구현할 수 있다.
Encoder
Encoder는 Decoder의 역 기능이다. 2^n개의 input line 중 ON인 line에 대응하는 n-bit binary를 출력한다.
- 특징: 한 번에 하나의 input line만 ON이어야 한다 (At any time, only one input line has a value of 1)
문제점:
- 만약 input line 중 2개 이상이 동시에 ON이면? → 올바른 binary를 생성할 수 없다
- 만약 모든 input line이 OFF이면? → 0번 line이 ON인 것과 구분 불가
해결:
- Priority Encoder: 높은 우선순위의 input을 우선 처리. 여러 input이 동시에 ON이어도 가장 높은 우선순위의 line에 대응하는 binary를 출력
- Valid Bit: 입력이 하나도 없을 때 Valid = 0으로 설정하여, “입력 없음"과 “0번 line ON"을 구분
Priority Encoder (4-to-2)
I3 ──┐
I2 ──┤ ┌──────────────┐
I1 ──┼──│ Priority │──> Y1, Y0 (2-bit binary)
I0 ──┘ │ Encoder │──> V (Valid bit)
└──────────────┘
우선순위: I3 > I2 > I1 > I0
I3=1 → Y=11, V=1 (나머지 입력 무시)
I2=1, I3=0 → Y=10, V=1
모두 0 → Y=00, V=0
Optimal하지는 않지만, Binary Encoder가 이미 있다면 Priority Circuit만 추가하면 되므로 좋은 설계 방법이다.
Multiplexer (MUX) / Demultiplexer (DEMUX)
Multiplexer (MUX)
**MUX (Data Selector)**는 2^n개의 input data 중 하나를 selection signal로 결정해 output line으로 보내주는 Unit이다.
- n-bit selection signal로 input line 하나를 선택
- 내부적으로 selection signal과 input line을 대응시킬 때 Decoder 사용
- 1개의 MUX는 data를 1-bit까지 밖에 보내지 못한다
4-to-1 MUX
I0 ──┐
I1 ──┤ ┌───────────┐
I2 ──┼──│ │
I3 ──┘ │ 4-to-1 │──> Y
│ MUX │
S1 ──┬──│ │
S0 ──┘ └───────────┘
S1 S0 │ Y
──────┼────
0 0 │ I0
0 1 │ I1
1 0 │ I2
1 1 │ I3
data bus를 MUX로 select하고 싶으면 MUX를 여러 개 사용해야 한다. 예를 들어 2-to-1 MUX를 이용해 4-bit data bus 2개 중 하나를 고르고 싶으면 → 2-to-1 MUX를 4개 사용하면 된다 (각 bit를 MUX로 선택).
Enable Signal: MUX의 기능을 켜고 끄는 Signal이다.
- E = 1: MUX ON → selection signal로 input data 고름
- E = 0: MUX OFF → output을 모두 0으로 설정 (selection signal과 input 모두 무시)
Demultiplexer (DEMUX)
DEMUX는 MUX의 역 기능이다. 하나의 input data를 2^n개의 output line 중 하나로 보내준다.
- n-bit selection signal로 output line 하나를 결정
- selection signal과 output line을 대응시킬 때 Decoder 사용
1-to-4 DEMUX
┌───────────┐
│ │──> F0
I ─────────>│ 1-to-4 │──> F1
│ DEMUX │──> F2
S1 ──┬─────│ │──> F3
S0 ──┘ └───────────┘
S1 S0 │ F0 F1 F2 F3
──────┼────────────────
0 0 │ I 0 0 0
0 1 │ 0 I 0 0
1 0 │ 0 0 I 0
1 1 │ 0 0 0 I
순차 논리 (Sequential Logic)
조합 논리와 달리, 순차 논리(Sequential Logic) 회로는 **현재의 상태(state)**가 출력에 영향을 준다. 따라서 state를 저장하는 memory element가 필요하다.
State-Holding Elements
- 조합 논리(Combinational Logic): output = f(input) — 입력만으로 출력 결정
- 순차 논리(Sequential Logic): output = f(input, state) — 입력 + 현재 상태로 출력 결정
Combinational Logic Sequential Logic
input ──> [Logic] ──> output input ──> [Logic] ──> output
^ │
│ v
[State]
Clock은 주기적인 신호로, 언제 memory element를 update할지 결정한다. Clock이 있어야 회로가 언제 새로운 상태를 저장해야 하는지 알 수 있다.
Latch
Latch는 가장 단순한 1-bit 저장 소자(memory element)이다. Level-sensitive 방식으로 동작한다.
S-R Latch
Set/Reset signal로 1-bit data를 store하는 Unit이다.
S-R Latch (NOR 게이트 구현)
S ──>│\
│ >o──┬──> Q
┌──>│/ │
│ │
│ ┌────┘
│ │
│ v
│ ┌─│──┐
└──│/ │
│ >o─┴──> Q'
R >│\
└────┘
동작 진리표:
S R │ Q (next) 동작
────────┼──────────────────────
0 0 │ Q (유지) 이전 값 유지
1 0 │ 1 Set (Q = 1)
0 1 │ 0 Reset (Q = 0)
1 1 │ ?? ERROR (금지 상태)
S = 1, R = 1인 경우 Q와 Q’가 모두 0이 되어 상호 보완 관계가 깨진다. 이 상태는 사용하지 않는다.
D Latch
Clock Signal과 Data Signal의 조합으로 1-bit data를 store하는 Unit이다. S-R Latch에서 S = C · D, R = C · D’으로 설정한 Latch이다.
D Latch
D ──┬──────>│\
│ │ AND│──> S ──┐
C ─┼──┬──>│/ │ ┌──────┐
│ │ ├──│ S-R │──> Q
│ │ ┌─>│\ │ │Latch │
└──│──>│NOT│ │ └──────┘
│ └───┘──>│\ │
│ │AND│─┘──> R
└─────────>│/
동작:
C D │ Q (next) 동작
────────┼──────────────────────
0 X │ Q (유지) Clock이 0이면 상태 유지
1 0 │ 0 D 값을 저장 (Q = 0)
1 1 │ 1 D 값을 저장 (Q = 1)
D Latch는 Level-sensitive이다: C = 1인 동안 D의 값이 그대로 Q에 반영된다. C = 0이면 이전의 Q 값을 유지한다.
Flip-Flop
Flip-Flop은 Latch와 달리 Edge-sensitive 방식으로 동작하는 1-bit 저장 소자이다. Clock의 edge (rising 또는 falling)에서만 값이 update된다.
D Flip-Flop
D Flip-Flop은 Clock edge(rising or falling)에서 D가 update되는 1-bit data storage Unit이다.
구조: D Latch 2개를 이어붙인 Master-Slave 구조이다.
D Flip-Flop (Master-Slave 구조, Rising Edge Triggered)
Master Slave
┌────────────┐ ┌────────────┐
D ─────────>│ D Latch │───────>│ D Latch │──────> Q
│ (Level: │ │ (Level: │
C ──┬──────>│ C=0 투명) │ ┌──>│ C=1 투명) │
│ └────────────┘ │ └────────────┘
│ │
└──> [NOT] ───────────────┘
동작 원리:
Clock = 0: Master 투명 (D → Master에 저장)
Slave 잠금 (이전 값 유지, Q 변화 없음)
Clock = 1: Master 잠금 (저장된 값 유지)
Slave 투명 (Master 값 → Q에 반영)
Rising Edge (0→1): Master가 잠기고 Slave가 열리면서
Master에 저장된 D 값이 Q로 전달
C (Clock) │ Q (next) 동작
────────────┼──────────────────────
↑ (rising) │ D D 값으로 update
0, 1, ↓ │ Q (유지) 이전 값 유지
핵심: Clock의 rising edge 순간에만 D의 값이 Q로 전달되고, 그 외의 시간에는 Q가 변하지 않는다. 이것이 Level-sensitive인 Latch와의 가장 큰 차이점이다.
Register와 Register File
Register
Register는 D Flip-Flop의 집합으로, N-bit data를 저장하는 Unit이다. Edge-triggered clocking 방식으로 동작한다.
- N-bit data를 저장하려면 D Flip-Flop을 여러 개 묶어서 사용하면 된다
- 일반적으로 Register의 Write는 Rising Edge에서 진행 (Rising Edge D Flip-Flop 사용)
4-bit Register (D Flip-Flop 4개)
D[3] ──> [D FF] ──> Q[3]
D[2] ──> [D FF] ──> Q[2]
D[1] ──> [D FF] ──> Q[1]
D[0] ──> [D FF] ──> Q[0]
^
│
Clock (공통)
Register File
Register File은 Register Number로 접근하는 register의 집합이다. CPU 내부에서 여러 개의 레지스터를 관리하는 핵심 구성요소이다.
Register File 구조
입력: Read Reg Num1, Read Reg Num2,
Write Reg Num, Write Data, RegWrite signal
출력: Read Data1, Read Data2
Read Section — MUX 사용
읽기는 MUX를 사용한다. 모든 Register의 Q(32-bit)를 MUX의 input으로 넣어두고, Read Reg Num을 MUX에 넣어 대응하는 input line을 결정한다.
Read Section (Read Port 1개의 구조)
Reg 0 [32-bit] ──┐
Reg 1 [32-bit] ──┤
Reg 2 [32-bit] ──┤ ┌───────────────┐
... ├──│ 32-to-1 MUX │──> Read Data (32-bit)
Reg 30 [32-bit] ──┤ │ (32개 입력) │
Reg 31 [32-bit] ──┘ └───────────────┘
^
│
Read Reg Num (5-bit)
- 32개의 Register 중 하나를 골라야 하므로 → 5-bit selection signal 필요 (2^5 = 32)
- 32-bit data bus를 output으로 도출해야 하므로 → 32개의 [1-bit 32-to-1 MUX] 사용
- Read Port가 2개라면 MUX가 2세트 필요
Write Section — Decoder 사용
쓰기는 Decoder를 사용한다. Write Reg Num(5-bit)을 Decoder에 넣어 대응하는 하나의 line만 ON 시키고, Write Signal과 AND Gate로 묶어 해당 Register만 Write 가능하게 한다.
Write Section
┌─────────────┐
Write Reg Num ──────>│ 5-to-32 │──> line 0 ──> AND ──> Reg 0 Write Enable
(5-bit) │ Decoder │──> line 1 ──> AND ──> Reg 1 Write Enable
│ │──> ...
│ │──> line 31 ──> AND ──> Reg 31 Write Enable
└─────────────┘
^
RegWrite ────────────────────────────────────┘
(Write Signal)
Write Data (32-bit) ──────────────────────────> 모든 Reg의 D 입력에 연결
(Write Enable된 Reg만 실제 저장)
전체 Register File의 구조를 종합하면:
┌──────────────────────────────────────────────────┐
│ Register File │
│ │
│ Read Reg Num1 ──> [MUX] ──> Read Data1 │
│ Read Reg Num2 ──> [MUX] ──> Read Data2 │
│ │
│ Write Reg Num ──> [Decoder] ──┐ │
│ RegWrite ─────────────────────┼──> Write Enable │
│ Write Data ───────────────────┼──> D inputs │
│ │
│ ┌──────┐ ┌──────┐ ┌──────┐ │
│ │Reg 0 │ │Reg 1 │ ... │Reg 31│ │
│ └──────┘ └──────┘ └──────┘ │
└──────────────────────────────────────────────────┘
정리
디지털 논리 회로는 크게 조합 논리와 순차 논리로 나뉜다.
조합 논리 (Combinational Logic):
- 현재 입력만으로 출력이 결정되며, 상태를 저장하지 않는다
- Boolean Function, Adder, Decoder, Encoder, MUX/DEMUX 등이 이에 해당한다
- Carry Lookahead Adder처럼 병렬 계산으로 성능을 개선할 수 있다
순차 논리 (Sequential Logic):
- 입력과 현재 상태가 함께 출력을 결정하며, 상태를 저장하는 memory element가 필요하다
- Latch(Level-sensitive)와 Flip-Flop(Edge-sensitive)이 기본 저장 소자이다
- Flip-Flop을 묶어 Register를, Register를 모아 Register File을 구성한다
이러한 디지털 논리 요소들은 다음 글에서 다룰 프로세서 설계의 기본 빌딩 블록이 된다. 특히 Register File, MUX, Decoder, Adder는 MIPS 프로세서 datapath에서 핵심적인 역할을 한다.