Sequential Logic

3.1 Background

1) Combinational Logic

Combinational Logic: 현재 입력값만으로 출력이 결정되는 논리 회로.

$$out=f(in)$$

예를 들어 다음 회로들은 combinational logic이다.

• And
• Or
• Mux
• Adder
• ALU

Meaning: 같은 입력이 주어지면 시간과 관계없이 항상 같은 출력을 만든다.

---

2) Sequential Logic

Sequential Logic: 현재 입력뿐 아니라 이전 상태에 따라 출력이 결정되는 논리 회로.

개념적으로

$$out(t) = f(in(t-1),out(t-1))$$

형태로 생각할 수 있다.

Meaning: 이전 값을 기억할 수 있기 때문에 register, memory, counter를 만들 수 있다.

---

3) State

State: sequential circuit이 현재 기억하고 있는 정보.

Combinational circuit에는 지속적으로 저장되는 state가 없지만 sequential circuit에는 state가 존재한다.

Meaning: 컴퓨터가 이전 계산 결과나 데이터를 기억할 수 있게 하는 핵심 개념이다.

---

3.2 Clock

1) Clock

Clock: 컴퓨터 내부의 시간 진행을 일정한 주기로 표현하는 신호.

일반적으로

$$0 \rightarrow 1 \rightarrow 0 \rightarrow 1 \rightarrow \cdots$$

처럼 반복된다.

책에서는 두 상태를 다음과 같이 표현하기도 한다.

• tick
• tock

Meaning: 컴퓨터의 sequential component들이 상태를 변경하는 시점을 통일한다.

---

2) Clock Cycle

Clock Cycle: 하나의 tick과 다음 tock를 포함하는 완전한 시간 단위.

각 clock cycle을 하나의 discrete time unit으로 취급할 수 있다.

$$t=0,1,2,3,\ldots$$

Meaning: 연속적인 실제 시간을 컴퓨터가 처리하기 쉬운 단계별 시간으로 나눈다.

---

3) Synchronization

Synchronization: 여러 sequential component가 같은 clock에 맞춰 상태를 변경하는 것.

컴퓨터 전체의 DFF들은 동일한 master clock을 공유한다.

Meaning: CPU, register, memory 등의 상태 변경이 일정한 시점에 이루어지도록 한다.

---

3.3 Data Flip-Flop

1) DFF

Data Flip-Flop (DFF): 이전 clock cycle의 입력값을 현재 출력하는 가장 기본적인 sequential element.

기능은

$$out(t)=in(t-1)$$

이다.

입력:

in

출력:

out

Meaning: 입력을 한 clock cycle 동안 기억한 뒤 다음 cycle에 출력한다.

---

2) Time Delay

DFF의 가장 중요한 특징은 입력과 출력 사이에 한 단계의 시간 지연이 존재한다는 것이다.

time t-1          time t

in = 1
   ↓
  DFF
              → out = 1

즉,

$$out(t) \neq in(t)$$

가 아니라 기본적으로

$$out(t)=in(t-1)$$

이다.

Meaning: 이 시간 지연 덕분에 이전 상태를 저장하는 회로를 만들 수 있다.

---

3) Primitive DFF

이 책에서는 DFF 내부 구현을 직접 만들지 않고 primitive gate로 취급한다.

즉,

Boolean Logic
      +
     DFF
      ↓
Sequential Logic

구조로 진행한다.

Meaning: flip-flop 자체의 복잡한 feedback과 clock 구현은 추상화하고 그 위에서 memory system을 만든다.

---

3.4 Feedback

1) Feedback Loop

Feedback: 회로의 출력을 다시 자신의 입력 경로로 연결하는 구조.

개념적으로

       ┌──────────────┐
       │              │
       ▼              │
     input → DFF → output
                 │
                 └────────

형태이다.

Meaning: 이전 출력을 다시 입력으로 사용하여 상태를 유지할 수 있다.

---

2) Feedback in Combinational Logic

Combinational circuit에서 단순한 feedback은 문제가 될 수 있다.

out → input → out → input → ...

즉 출력이 자기 자신에 즉시 의존하게 된다.

Meaning: 시간 지연이 없는 회로에서는 feedback이 불안정하거나 정의되지 않은 동작을 만들 수 있다.

---

3) Feedback in Sequential Logic

DFF가 포함되면 feedback에 한 clock cycle의 delay가 생긴다.

$$out(t) \rightarrow in(t) \rightarrow out(t+1)$$

따라서 현재 출력은 즉시 자기 자신에 의존하지 않는다.

Meaning: DFF가 feedback loop를 안전하게 사용할 수 있도록 시간 경계를 만든다.

---

3.5 Bit Register

1) Bit

Bit Register: 하나의 bit를 저장하는 1-bit memory cell.

입력:

in
load

출력:

out

동작은

$$load(t-1)=1 \Rightarrow out(t)=in(t-1)$$

이고,

$$load(t-1)=0 \Rightarrow out(t)=out(t-1)$$

이다.

Meaning: load 신호에 따라 새로운 값을 저장하거나 기존 값을 유지한다.

---

2) Load Bit

Load: 새로운 입력값을 저장할지 결정하는 control bit.

load = 0
→ 현재 값 유지

load = 1
→ 새로운 in 저장

Meaning: register의 write enable 역할을 한다.

---

3) Bit Register Structure

1-bit register는 기본적으로 다음 구조로 생각할 수 있다.

             ┌───────────────┐
             │               │
             ▼               │
in ──────── Mux ───── DFF ───┴── out
             ▲
            load

Mux가 선택하는 것은

load = 0 → 기존 out
load = 1 → 새로운 in

이다.

Meaning: Chapter 1의 Mux와 DFF를 조합하면 실제 저장 기능을 만들 수 있다.

---

3.6 Register

1) Register

Register: 여러 bit로 이루어진 하나의 word를 저장하는 sequential circuit.

Hack computer에서는 16-bit register를 사용한다.

입력:

in[16]
load

출력:

out[16]

기능:

$$load(t-1)=1 \Rightarrow out(t)=in(t-1)$$ $$load(t-1)=0 \Rightarrow out(t)=out(t-1)$$

Meaning: 하나의 16-bit 값을 기억한다.

---

2) Register Construction

16-bit register는 16개의 Bit register를 병렬로 배치하여 만들 수 있다.

in[0]  → Bit → out[0]
in[1]  → Bit → out[1]
in[2]  → Bit → out[2]

...

in[15] → Bit → out[15]

모든 Bit register는 동일한 load 신호를 사용한다.

Meaning: 1-bit storage cell을 병렬화하면 word 단위 저장 장치를 만들 수 있다.

---

3) Word

Word: register 또는 memory가 한 번에 저장하고 처리하는 고정 길이 bit 집합.

Hack에서는

$$1\ word=16\ bits$$

이다.

Meaning: CPU와 memory가 기본적으로 처리하는 데이터 단위이다.

---

3.7 Random Access Memory

1) RAM

Random Access Memory (RAM): 여러 register를 배열 형태로 구성하고 address를 이용해 원하는 register에 직접 접근하는 memory.

RAM의 주요 입력은 다음과 같다.

• in
• address
• load

출력은

• out

이다.

Meaning: 많은 word 중 원하는 하나를 address를 통해 읽거나 쓸 수 있다.

---

2) Memory Size and Width

RAM에는 두 가지 중요한 크기 개념이 있다.

Width: 하나의 register가 저장하는 bit 수.

Size: register의 개수.

예를 들어

RAM8

은 8개의 16-bit register를 가진다.

RAM8

size  = 8 words
width = 16 bits

Meaning: width는 word의 크기이고 size는 저장 가능한 word의 개수이다.

---

3) Address

Address: RAM 내부의 특정 register를 선택하는 번호.

$n$개의 memory location이 있으면 필요한 address bit 수는

$$\log_2 n$$

이다.

예를 들어 RAM8은

$$\log_2 8=3$$

bit address가 필요하다.

Meaning: binary address를 이용해 특정 memory location을 선택한다.

---

3.8 RAM Read and Write

1) Read

RAM에서 값을 읽으려면 원하는 register의 address를 지정한다.

$$out(t) = RAM[address(t)](t)$$

예를 들어

address = 3

이면

out = RAM[3]

이다.

Read는 combinational operation이다.

Meaning: address를 변경하면 선택된 register의 값이 output으로 나타난다.

---

2) Write

RAM에 값을 쓰려면

in      = 저장할 값
address = 저장할 위치
load    = 1

을 설정한다.

다음 clock cycle에서

$$RAM[address(t-1)](t) = in(t-1)$$

이 된다.

Meaning: RAM read는 즉시 이루어지지만 write는 clock에 맞춰 상태를 변경한다.

---

3.9 RAM Hierarchy

Hack에서는 여러 단계의 RAM을 만든다.

Memory	Number of Words	Address Bits
RAM8	8	3
RAM64	64	6
RAM512	512	9
RAM4K	4096	12
RAM16K	16384	14

Meaning: 작은 memory block을 계층적으로 조합하여 더 큰 memory를 만든다.

---

1) RAM8

RAM8은 8개의 16-bit register로 구성할 수 있다.

               ┌─ Register 0
               ├─ Register 1
               ├─ Register 2
in ────────────┤
               │
               ...
               │
               └─ Register 7

3-bit address가 어떤 register를 선택할지 결정한다.

Meaning: register 배열에 address selection logic을 추가하면 RAM이 된다.

---

2) RAM64

RAM64는 8개의 RAM8로 구성할 수 있다.

RAM64
 ├─ RAM8
 ├─ RAM8
 ├─ RAM8
 ├─ RAM8
 ├─ RAM8
 ├─ RAM8
 ├─ RAM8
 └─ RAM8

RAM64는 6-bit address를 사용한다.

address를 개념적으로

xxx yyy

로 나누면,

• 상위 xxx → 어떤 RAM8을 선택할지 결정
• 하위 yyy → 선택된 RAM8 내부의 register를 결정

한다.

Meaning: address도 계층적으로 분할하여 큰 memory를 선택할 수 있다.

---

3) Recursive Memory Construction

memory hierarchy는 다음과 같이 확장된다.

Bit
 ↓
Register
 ↓
RAM8
 ↓
RAM64
 ↓
RAM512
 ↓
RAM4K
 ↓
RAM16K

Meaning: 동일한 abstraction을 반복적으로 조합하여 큰 memory system을 만들 수 있다.

---

3.10 Address Selection Logic

RAM write에서는 특정 register 하나만 load=1을 받아야 한다.

이를 위해 DMux 계열 회로를 사용할 수 있다.

             address
                ↓
load ──────── DMux
              ↓ ↓ ↓
             R0 R1 R2 ...

RAM read에서는 여러 register 출력 중 하나만 선택해야 한다.

이를 위해 Mux 계열 회로를 사용할 수 있다.

R0 ───┐
R1 ───┤
R2 ───┤ Mux ─── out
... ───┤
       └──── address

Meaning: Chapter 1의 Mux와 DMux가 memory addressing의 핵심 회로가 된다.

---

3.11 Counter

1) Counter

Counter: 저장된 숫자를 일정하게 증가시키는 sequential circuit.

기본 기능은

$$out(t) = out(t-1)+1$$

이다.

Meaning: 시간에 따라 증가하는 상태값을 저장한다.

---

2) Program Counter

Program Counter (PC): 다음에 실행할 instruction의 address를 저장하는 counter.

CPU에서 일반적으로

$$PC \leftarrow PC+1$$

하여 다음 instruction으로 이동한다.

jump가 발생하면 새로운 address를 PC에 저장한다.

Meaning: CPU가 다음에 어떤 instruction을 실행할지 결정하는 핵심 register이다.

---

3.12 Hack Program Counter

Hack의 PC는 다음 control input을 가진다.

inc
load
reset

그리고

in[16]
out[16]

을 가진다.

동작 우선순위는 다음과 같다.

reset

$$reset=1 \Rightarrow out=0$$

---

load

$$load=1 \Rightarrow out=in$$

---

inc

$$inc=1 \Rightarrow out=out+1$$

---

Hold

모든 control input이 0이면

$$out(t)=out(t-1)$$

이다.

---

1) PC Priority

Hack PC의 control 우선순위는

reset
  ↓
load
  ↓
inc
  ↓
hold

이다.

즉,

$$reset > load > inc$$

순서로 우선한다.

Meaning: 여러 control signal이 동시에 활성화되어도 결과가 명확하게 정의된다.

---

3.13 Counter Construction

Counter는 기본적으로

Register
+
Incrementer
+
Mux

를 조합하여 만들 수 있다.

                 ┌──── Inc16 ─────┐
                 │                │
                 │                ▼
in ──────────── Mux ──────────── Mux
                ▲                 │
              load               inc
                                  │
                                  ▼
                              Register
                                  │
                                 out

reset logic까지 추가하면 PC를 구성할 수 있다.

Meaning: Chapter 1의 selector와 Chapter 2의 arithmetic circuit을 sequential storage와 결합한 것이다.

---

3.14 Combinational vs Sequential Logic

두 종류의 회로 차이는 반드시 이해해야 한다.

Combinational	Sequential
현재 입력으로 출력 결정	이전 상태도 사용
state 없음	state 있음
clock 필요 없음	clock 사용
feedback 제한적	DFF를 통한 feedback 가능
And, Mux, ALU	Register, RAM, Counter

개념적으로

$$\text{Combinational} : out=f(in)$$ $$\text{Sequential} : out(t) = f(in(t-1),out(t-1))$$

Meaning: combinational logic은 계산을 담당하고 sequential logic은 기억을 담당한다.

---

3.15 Timing

1) Propagation Delay

Combinational circuit에서는 입력 신호가 바뀐 직후 출력이 즉시 완성되는 것이 아니다.

전기 신호가 gate를 통과하는 데 시간이 필요하다.

따라서 ALU 같은 회로의 출력은 짧은 시간 동안 안정되지 않을 수 있다.

Meaning: 실제 hardware에서는 계산 결과가 안정되는 데 시간이 필요하다.

---

2) Clock Period

Clock cycle은 combinational circuit이 계산을 끝내고 출력이 안정될 충분한 시간을 제공해야 한다.

개념적으로

$$T_{clock} > T_{longest\ path}$$

가 되어야 한다.

Meaning: 가장 느린 combinational path가 계산을 끝내기 전에 다음 state update가 발생하면 안 된다.

---

3) State Update

Sequential circuit의 상태는 clock cycle 경계에서 변경된다.

Clock Cycle t

input changes
    ↓
combinational calculation
    ↓
output stabilizes
    ↓
clock boundary
    ↓
state stored

Meaning: clock은 계산 과정과 저장 시점을 분리한다.

---

3.16 Sequential System Structure

일반적인 sequential system은 다음과 같이 볼 수 있다.

           ┌──────────────────┐
           │                  │
           ▼                  │
Input → Combinational Logic → DFF/Register → Output
           ▲                         │
           └─────────────────────────┘

즉,

Stored State
     ↓
Combinational Logic
     ↓
New State
     ↓
Register
     ↓
Stored State

가 반복된다.

Meaning: 현대 CPU와 대부분의 synchronous digital system은 계산과 상태 저장의 반복으로 동작한다.

---

3.17 Hardware Construction Hierarchy

Chapter 3까지의 전체 hardware hierarchy는 다음과 같이 연결된다.

Nand
 ↓
Boolean Gates
 ↓
Mux / DMux
 ↓
Adder / ALU
 ↓
DFF
 ↓
Bit
 ↓
Register
 ↓
RAM
 ↓
Counter

특히 memory hierarchy는

$$\boxed{ DFF \rightarrow Bit \rightarrow Register \rightarrow RAM }$$

으로 정리할 수 있다.

Meaning: 아주 작은 1-bit state element에서 거대한 memory system까지 같은 원리로 확장된다.

---

Essential Study Checklist

반드시 이해하고 기억해야 하는 내용:

1. Combinational circuit은 현재 입력으로 출력이 결정된다.

$$out=f(in)$$

2. Sequential circuit은 이전 상태를 기억한다.

3. State는 sequential circuit이 기억하고 있는 정보이다.

4. Clock은 sequential circuit의 상태 변경 시점을 동기화한다.

5. DFF의 핵심 동작은

$$out(t)=in(t-1)$$

이다.

6. DFF는 한 clock cycle의 time delay를 제공한다.

7. DFF의 time delay 덕분에 feedback loop를 안전하게 사용할 수 있다.

8. Bit register는 하나의 bit를 저장한다.

9. load=1이면 새로운 값을 저장한다.

$$out(t)=in(t-1)$$

10. load=0이면 기존 값을 유지한다.

$$out(t)=out(t-1)$$

11. Bit register는 기본적으로

Mux + DFF

로 구성할 수 있다.

12. 16개의 Bit register를 병렬로 연결하면 16-bit Register를 만들 수 있다.

13. Register는 하나의 word를 저장한다.

14. Hack computer의 word width는 16 bits이다.

15. RAM은 여러 register와 address selection logic으로 구성된다.

16. RAM의 두 핵심 특성은

width = word 크기
size  = word 개수

이다.

17. $n$개의 memory location을 선택하려면

$$\log_2 n$$

개의 address bit가 필요하다.

18. RAM read는 address에 의해 선택된 값을 출력한다.

$$out=RAM[address]$$

19. RAM write는 load=1일 때 다음 clock cycle에서 이루어진다.

20. RAM write selection에는 DMux를 사용할 수 있다.

21. RAM read selection에는 Mux를 사용할 수 있다.

22. memory는 작은 block을 조합하여 계층적으로 확장할 수 있다.

Register
→ RAM8
→ RAM64
→ RAM512
→ RAM4K
→ RAM16K

23. RAM64의 6-bit address는 상위 bit와 하위 bit로 나누어 계층적 address selection에 사용할 수 있다.

24. Counter는 이전 값에 1을 더해 저장하는 sequential circuit이다.

$$out(t)=out(t-1)+1$$

25. Program Counter는 다음 instruction의 address를 저장한다.

26. Hack PC의 주요 control input은

reset
load
inc

이다.

27. PC의 control priority는

reset
→ load
→ inc
→ hold

이다.

28. Counter는

Register
+
Incrementer
+
Mux

의 조합으로 만들 수 있다.

29. Combinational circuit은 계산, sequential circuit은 상태 저장을 담당한다.

30. 실제 digital system에서는 combinational output이 안정될 시간을 확보한 후 다음 clock에서 state를 저장한다.

31. Clock period는 가장 긴 combinational propagation path보다 충분히 길어야 한다.

32. Chapter 3에서 가장 중요한 관계는

$$\boxed{ \text{DFF} \rightarrow \text{Bit} \rightarrow \text{Register} \rightarrow \text{RAM} }$$

이다.

33. Chapter 1부터 Chapter 3까지의 전체 핵심 흐름은

$$\boxed{ \text{Boolean Logic} \rightarrow \text{Arithmetic} \rightarrow \text{State} \rightarrow \text{Memory} }$$

이다.

34. 이 장의 가장 중요한 개념은 DFF가 시간이라는 개념을 회로에 도입하고, 그 위에서 register와 memory를 만들 수 있게 한다는 것이다.