디지털 논리와 회로: 트랜지스터에서 덧셈기까지
컴퓨터가 0과 1만 쓰는 이유에서 출발해, 전기로 여닫는 스위치인 트랜지스터로 논리 게이트를 만들고 NAND 하나만으로 NOT, AND, OR, XOR를 모두 조립해요. 반가산기와 전가산기를 이어 8비트 덧셈기를 완성해 6만 5천여 가지 덧셈을 모두 확인하고, 같은 회로로 뺄셈을 하는 2의 보수, 서로의 출력을 물고 있는 두 게이트가 1비트를 기억하는 래치, 할 일을 고르는 MUX와 작은 ALU까지 쌓아 올려요. 클록과 올림 전파가 속도의 한계를 정하는 이유도 다뤄요.
컴퓨터 과학 이론 트랙의 첫 강의예요. 이 트랙은 "계산이란 무엇이고, 어디까지 가능한가"를 다뤄요. 그 출발점으로 오늘은 계산이 실제로 어떻게 일어나는지 가장 아래층부터 쌓아 올려요. 컴퓨터 기초 트랙에서는 CPU가 명령을 하나씩 실행하는 모습을 흉내 냈고, 수학 기초 트랙에서는 2진수와 논리 연산을 배웠어요. 오늘은 그 둘을 잇는 다리, 2진수 덧셈을 하는 회로를 스위치에서부터 직접 만들어요.
왜 0과 1일까
컴퓨터 안의 신호는 전압이에요. 전압은 원래 연속으로 변하는 값인데, 컴퓨터는 이걸 **높다(1)**와 낮다(0) 두 가지로만 읽어요. 예를 들어 예전 TTL 회로는 0.8V 아래를 0, 2V 위를 1로 읽었어요. 이렇게 두 칸으로 나누고 사이를 넉넉히 비워 두면, 잡음 때문에 전압이 조금 흔들려도 0과 1을 헷갈리지 않아요. 게다가 신호는 회로를 지날 때마다 다시 깨끗한 0과 1로 맞춰져서, 계산을 수십억 번 이어 가도 오차가 쌓이지 않아요. 전압을 열 칸으로 나눠 10진수를 쓴다면 칸 사이가 좁아져서 작은 잡음에도 값이 바뀌어 버려요.
트랜지스터: 전기로 여닫는 스위치
0과 1을 다루는 부품이 트랜지스터예요. 디지털 회로에서 트랜지스터는 스위치예요. 다만 손가락이 아니라 전압으로 여닫아요. 한 단자(게이트)에 전압을 걸면 나머지 두 단자 사이로 전류가 흐르고, 걸지 않으면 끊겨요. 한 스위치의 출력이 다른 스위치를 여닫을 수 있으니, 스위치를 이어서 "이 조건이면 켜고 아니면 끈다"는 논리를 만들 수 있어요.
요즘 칩은 성질이 반대인 두 종류(1을 받으면 켜지는 것과 0을 받으면 켜지는 것)를 짝지어 쓰는 CMOS 방식이에요. 두 개를 짝지으면, 입력이 1일 때는 출력을 0V 쪽에, 0일 때는 전원 쪽에 이어 주는 NOT이 돼요. 네 개로는 두 입력이 모두 1일 때만 0을 내는 NAND를 만들어요. 1971년에 나온 인텔의 첫 CPU 4004에는 트랜지스터가 2,300개쯤 있었는데, 요즘 CPU와 GPU에는 수백억 개가 들어가요.
논리 게이트: NAND 하나로 모두 만들기
트랜지스터 몇 개를 묶어 만든, 0과 1을 받아 0과 1을 내는 부품을 논리 게이트라고 해요. 수학 기초 트랙에서 본 AND, OR, NOT, XOR가 각각 하나의 게이트예요. 놀라운 점은 NAND 하나만 있으면 나머지를 모두 만들 수 있다는 거예요. 파이썬으로 NAND를 만들고, 나머지 게이트는 NAND만 써서 조립해 볼게요. NAND를 몇 개 거치는지도 세어요.
nand_count = 0
def NAND(a, b): # 모든 것의 재료: 둘 다 1일 때만 0
global nand_count
nand_count += 1
return 0 if a and b else 1
def NOT(a):
return NAND(a, a)
def AND(a, b):
return NOT(NAND(a, b))
def OR(a, b):
return NAND(NOT(a), NOT(b)) # 드모르간 법칙
def XOR(a, b):
n = NAND(a, b)
return NAND(NAND(a, n), NAND(b, n))
print(" a b | NAND AND OR XOR")
for a in (0, 1):
for b in (0, 1):
print(f" {a} {b} | {NAND(a, b)} {AND(a, b)} {OR(a, b)} {XOR(a, b)}")
for name, gate, args in [("NOT", NOT, (1,)), ("AND", AND, (1, 1)), ("OR", OR, (1, 1)), ("XOR", XOR, (1, 1))]:
nand_count = 0
gate(*args)
print(f"{name}: NAND {nand_count}개")
a b | NAND AND OR XOR
0 0 | 1 0 0 0
0 1 | 1 0 1 1
1 0 | 1 0 1 1
1 1 | 0 1 1 0
NOT: NAND 1개
AND: NAND 2개
OR: NAND 3개
XOR: NAND 4개
- NOT은 NAND의 두 입력을 하나로 묶은 거예요. 둘이 같은 값이니 1을 넣으면 0, 0을 넣으면 1이 나와요.
- AND는 NAND를 뒤집은 거예요. NAND라는 이름 자체가 Not AND예요.
- OR는 드모르간 법칙 그대로예요. "a 또는 b"는 "a도 아니고 b도 아닌 건 아니다"와 같으니, 입력을 뒤집어서 NAND에 넣어요.
- XOR는 NAND 네 개로 만드는 잘 알려진 조합이에요.
이렇게 한 종류로 모든 논리를 만들 수 있는 게이트를 만능 게이트라고 해요. NOR도 만능 게이트예요. 실제 칩이 한 종류만 쓰는 건 아니지만, "가장 단순한 부품 하나를 반복해서 무엇이든 만든다"는 생각이 디지털 회로의 바탕이에요.
덧셈기: 반가산기에서 8비트까지
2진수 한 자리의 덧셈은 네 가지뿐이에요. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 그리고 1 + 1 = 10(이 자리는 0, 윗자리로 1을 올림)이에요. 이 자리의 합은 두 입력이 다를 때만 1이니 XOR이고, 올림은 둘 다 1일 때만 1이니 AND예요. 이 둘을 묶은 게 반가산기예요. 둘째 자리부터는 아랫자리에서 올라온 올림까지 세 개를 더해야 해서, 반가산기 두 개와 OR 하나로 전가산기를 만들어요. 전가산기 여덟 개를 이으면 8비트 덧셈기예요.
def half_adder(a, b):
return XOR(a, b), AND(a, b) # (이 자리의 합, 윗자리로 올림)
def full_adder(a, b, carry_in): # 아랫자리에서 올라온 올림까지 더해요
s1, c1 = half_adder(a, b)
s2, c2 = half_adder(s1, carry_in)
return s2, OR(c1, c2)
def to_bits(n, width=8): # 아랫자리부터 담아요
return [(n >> i) & 1 for i in range(width)]
def from_bits(bits):
return sum(bit << i for i, bit in enumerate(bits))
def add8(x, y, carry=0): # 전가산기 8개를 줄줄이 이어요
out = []
for a, b in zip(to_bits(x), to_bits(y)):
s, carry = full_adder(a, b, carry)
out.append(s)
return from_bits(out), carry
ok = all(add8(x, y) == ((x + y) % 256, (x + y) // 256) for x in range(256) for y in range(256))
print("256 × 256가지 덧셈이 모두 맞나요?", ok)
for x, y in [(23, 19), (200, 100)]:
nand_count = 0
total, carry = add8(x, y)
print(f"{x} + {y} = {total}, 넘친 올림 {carry} | NAND {nand_count}개를 거쳤어요")
256 × 256가지 덧셈이 모두 맞나요? True
23 + 19 = 42, 넘친 올림 0 | NAND 120개를 거쳤어요
200 + 100 = 44, 넘친 올림 1 | NAND 120개를 거쳤어요
0과 255 사이 두 수의 덧셈 65,536가지를 모두 확인했고, 하나도 틀리지 않았어요. 덧셈 한 번에 NAND 120개(전가산기 하나에 15개씩 여덟 개)를 지나요. 트랜지스터로 치면 480개쯤이에요. 실제 회로는 같은 일을 더 적은 부품으로 하도록 다듬어요.
200 + 100은 300인데 8비트로는 255까지만 담을 수 있어서, 아래 8자리가 나타내는 44만 남고 맨 위의 올림 1은 넘쳐요. 수학 기초 트랙에서 말한 오버플로가 회로에서는 이렇게 생겨요. CPU는 이 넘친 올림을 따로 표시해 두었다가(캐리 플래그), 더 큰 수를 여러 번에 나눠 더할 때 다음 덧셈의 올림으로 넘겨줘요.
뺄셈도 덧셈기로: 2의 보수
뺄셈 회로를 따로 만들 필요는 없어요. y의 비트를 모두 뒤집고 1을 더한 값을 x에 더하면 x - y가 돼요. 뒤집기는 NOT 여덟 개면 되고, "1을 더하기"는 맨 아랫자리에 넣는 올림을 1로 주면 공짜로 돼요.
def sub8(x, y): # x - y = x + (y의 비트를 모두 뒤집은 것) + 1
flipped = from_bits([NOT(b) for b in to_bits(y)])
return add8(x, flipped, carry=1)[0]
def signed(n): # 맨 윗자리가 1이면 음수로 읽어요
return n - 256 if n >= 128 else n
for x, y in [(5, 3), (3, 5), (100, 120)]:
r = sub8(x, y)
print(f"{x} - {y}: 비트 {r:08b}, 그냥 읽으면 {r}, 2의 보수로 읽으면 {signed(r)}")
print("127 + 1을 2의 보수로 읽으면:", signed(add8(127, 1)[0]))
5 - 3: 비트 00000010, 그냥 읽으면 2, 2의 보수로 읽으면 2
3 - 5: 비트 11111110, 그냥 읽으면 254, 2의 보수로 읽으면 -2
100 - 120: 비트 11101100, 그냥 읽으면 236, 2의 보수로 읽으면 -20
127 + 1을 2의 보수로 읽으면: -128
3 - 5의 결과는 비트로 11111110이에요. 그냥 읽으면 254지만, "맨 윗자리가 1이면 256을 뺀 값, 즉 음수로 읽는다"고 약속하면 -2예요. 이 약속이 2의 보수예요. 8비트로 -128부터 127까지 나타내고, 덧셈기 하나로 양수와 음수의 덧셈과 뺄셈을 모두 해요. 0이 하나뿐이라는 것도 장점이에요. 맨 윗자리를 부호로만 쓰는 방식이라면 +0과 -0이 따로 생기거든요.
마지막 줄은 오버플로의 다른 얼굴이에요. 127에 1을 더하면 비트로는 10000000이 되고, 2의 보수로 읽으면 -128이에요. 32비트 정수가 약 21억을 넘으면 음수로 뒤집히는 이유가 바로 이거예요. 파이썬의 정수는 필요한 만큼 자릿수를 늘려서 이런 일이 없지만, C나 자바처럼 정수 크기가 정해진 언어에서는 지금도 일어나요.
기억하는 회로: 래치
지금까지의 회로는 입력이 정해지면 출력이 바로 정해졌어요. 그런데 컴퓨터는 기억도 해야 해요. 방법은 의외로 단순해요. 게이트 두 개가 서로의 출력을 입력으로 받도록 이으면 돼요. NOR 두 개로 만든 이 회로를 SR 래치라고 해요. S(set)를 잠깐 1로 하면 1을, R(reset)을 잠깐 1로 하면 0을 저장해요.
def NOR(a, b):
return NOT(OR(a, b))
def latch(s, r, q): # 두 NOR가 서로의 출력을 입력으로 받아요
q_bar = NOR(s, q)
for _ in range(4): # 신호가 돌다가 자리를 잡을 때까지
q, q_bar = NOR(r, q_bar), NOR(s, q)
return q
q = 0
for s, r, what in [(1, 0, "S를 잠깐 1로: 1 저장"), (0, 0, "둘 다 0이어도 그대로"),
(0, 1, "R을 잠깐 1로: 0으로"), (0, 0, "둘 다 0이어도 그대로")]:
q = latch(s, r, q)
print(f"S={s} R={r} → Q={q} ({what})")
S=1 R=0 → Q=1 (S를 잠깐 1로: 1 저장)
S=0 R=0 → Q=1 (둘 다 0이어도 그대로)
S=0 R=1 → Q=0 (R을 잠깐 1로: 0으로)
S=0 R=0 → Q=0 (둘 다 0이어도 그대로)
둘째 줄과 넷째 줄은 입력이 똑같이 S=0, R=0인데 출력이 달라요. 출력이 지금의 입력만이 아니라 이전에 무슨 일이 있었는지에 따라 정해지는 거예요. 이게 기억이에요. 실제 회로에서는 신호가 두 게이트 사이의 고리를 돌며 스스로를 붙잡고 있어서, 입력을 떼어도 값이 유지돼요. 위 코드는 그 고리를 몇 바퀴 돌려 보는 것으로 흉내 냈어요.
여기에 클록(일정한 간격으로 0과 1을 오가는 신호)을 더해 "박자가 바뀌는 순간에만 새 값을 받아들이게" 만든 게 플립플롭이에요. 플립플롭을 여러 개 나란히 놓으면 CPU 안의 레지스터가 되고요. 컴퓨터 기초 트랙에서 본 메모리 계층도 여기서 이어져요. CPU 캐시에 쓰는 SRAM은 1비트를 트랜지스터 6개로 이루어진 이런 고리 회로에 기억하고, 메인 메모리의 DRAM은 1비트를 트랜지스터 1개와 아주 작은 축전기에 전하로 담아요. 전하는 조금씩 새어 나가서, DRAM은 1초에도 여러 번 내용을 다시 써 줘야 해요(리프레시). 둘 다 전원이 꺼지면 내용이 사라지는 이유예요.
고르는 회로: MUX와 ALU
CPU는 명령에 따라 더하기도 하고 빼기도 해요. 할 일을 고르는 회로가 MUX(멀티플렉서)예요. 선택 신호가 0이면 첫째 입력을, 1이면 둘째 입력을 내보내요. MUX로 덧셈, 뺄셈, AND, OR 중 하나를 고르는 작은 ALU(산술 논리 장치)를 만들어 볼게요.
def MUX(a, b, select): # select가 0이면 a, 1이면 b를 내보내요
return OR(AND(a, NOT(select)), AND(b, select))
def alu(x, y, op): # op 두 비트로 할 일을 골라요
xb, yb = to_bits(x), to_bits(y)
results = {
"add": to_bits(add8(x, y)[0]),
"sub": to_bits(sub8(x, y)),
"and": [AND(a, b) for a, b in zip(xb, yb)],
"or": [OR(a, b) for a, b in zip(xb, yb)],
}
out = []
for i in range(8): # 네 결과를 다 만들어 두고, 자리마다 MUX로 하나를 골라요
low = MUX(results["add"][i], results["sub"][i], op & 1)
high = MUX(results["and"][i], results["or"][i], op & 1)
out.append(MUX(low, high, op >> 1))
return from_bits(out)
for op, name in enumerate(["더하기", "빼기", "AND", "OR"]):
print(f"op={op:02b} ({name}): 12와 10 → {alu(12, 10, op)}")
op=00 (더하기): 12와 10 → 22
op=01 (빼기): 12와 10 → 2
op=10 (AND): 12와 10 → 8
op=11 (OR): 12와 10 → 14
이 ALU는 네 가지 결과를 모두 계산해 두고 마지막에 MUX로 하나만 골라 내보내요. 회로는 전기가 흐르는 순간 모든 게이트가 동시에 일하니, 다 계산해 두고 고르는 쪽이 간단하거든요. op의 두 비트가 바로 명령어의 일부예요. 컴퓨터 기초 트랙에서 흉내 낸 CPU의 ADD 같은 명령은 결국 이런 선택 신호로 바뀌어 ALU에 들어가요. 레지스터에서 값을 꺼내 ALU에 넣고, 결과를 다시 레지스터에 담는 일을 클록에 맞춰 끝없이 반복하는 것, 이게 CPU예요.
클록과 속도의 한계
게이트는 신호를 받자마자 답을 내지 못하고, 아주 짧지만 시간이 걸려요. 그래서 클록의 한 박자는 가장 오래 걸리는 길(임계 경로)의 신호가 끝까지 도착할 만큼은 길어야 해요. 우리가 만든 덧셈기에서는 올림이 문제예요. 255 + 1처럼 올림이 맨 아랫자리부터 맨 윗자리까지 줄줄이 전해지면, 윗자리는 아랫자리의 올림이 도착할 때까지 기다려야 해요. 64비트라면 64단계를 기다려야 하죠. 그래서 실제 CPU는 올림이 생길지를 미리 계산하는 올림 예측 덧셈기(carry lookahead) 같은 방식으로 기다리는 단계를 log 수준으로 줄여요. 알고리즘 트랙에서 본 "하나씩 줄줄이"와 "반씩 나누기"의 차이가 회로에도 그대로 있어요.
거리도 문제예요. 3GHz CPU의 한 박자는 약 0.33나노초인데, 그동안 빛도 10cm쯤밖에 못 가요. 칩 안의 전기 신호는 그보다 느리고요. 칩이 작아야 하고, 트랜지스터를 작게 만들수록 빨라졌던 이유예요. 하지만 작아질수록 열과 전력 문제가 커져서, 요즘은 클록을 올리기보다 코어를 늘리는 쪽으로 발전하고 있어요. 여러 코어를 함께 쓰는 법은 컴퓨터 과학 심화 트랙의 동시성 강의에서 다뤄요.
실습
- NOR만으로 NOT, OR, AND를 만들고 진리표로 확인해 보세요.
to_bits와add8에 자리 수를 받는 인자를 더해 16비트 덧셈기로 늘려 보세요. NAND는 몇 개를 거치게 될까요?- 세 입력 중 둘 이상이 1이면 1을 내는 다수결 회로를 AND와 OR로 만들어 보세요. 전가산기의 올림과 비교하면 무엇을 알 수 있나요?
sub8(0, 1)의 비트를 보고, 2의 보수에서 -1이 왜 11111111인지 설명해 보세요.- 올림이 몇 자리를 연달아 타고 가는지 세는 코드를 더해서, 255 + 1과 1 + 1을 비교해 보세요.
자주 하는 오해
- 컴퓨터가 10진수로 계산한다. 안에서는 모두 2진수예요. 10진수는 사람에게 보여 줄 때 바꾼 모습이에요.
- 음수는 맨 윗자리만 1로 바꾼 것이다. 정수는 보통 2의 보수로 담아요. 8비트에서 -1은 10000001이 아니라 11111111이에요.
- 오버플로는 옛날 이야기다. 크기가 정해진 정수를 쓰는 언어에서는 지금도 조용히 뒤집혀요.
- 클록이 높으면 무조건 빠르다. 한 박자에 명령을 몇 개 처리하는지, 코어가 몇 개인지, 메모리를 얼마나 기다리는지도 속도를 정해요.
- 메모리는 전원을 꺼도 남는다. RAM은 전원이 꺼지면 사라져요. 남는 건 SSD 같은 저장 장치예요.
점검 문제
- 컴퓨터가 신호를 0과 1 두 가지로만 읽는 이유는?
- 디지털 회로에서 트랜지스터는 어떤 역할을 하나요?
- NAND만으로 NOT과 AND를 만드는 방법은?
- 반가산기는 어떤 두 게이트로 만들고, 전가산기는 반가산기와 무엇이 다른가요?
- 8비트 덧셈기로 200 + 100을 하면 44가 나오는 이유는?
- 덧셈기 하나로 뺄셈까지 하는 방법은?
- 래치가 기억을 할 수 있는 이유는?
- 덧셈기의 자리 수가 늘어나면 왜 느려질 수 있고, 어떻게 해결하나요?
정답
- 높음과 낮음 두 칸으로만 나누고 사이를 넉넉히 비워 두면, 잡음으로 전압이 조금 흔들려도 값을 헷갈리지 않기 때문이에요. 게이트를 지날 때마다 깨끗한 0과 1로 다시 맞춰져서 오차도 쌓이지 않아요.
- 전압으로 여닫는 스위치예요. 한 트랜지스터의 출력이 다른 트랜지스터를 여닫을 수 있어서, 이어 붙여 논리를 만들 수 있어요.
- NAND의 두 입력에 같은 값을 넣으면 NOT이 되고, NAND의 출력을 그 NOT으로 다시 뒤집으면 AND가 돼요.
- 합은 XOR, 올림은 AND로 만들어요. 전가산기는 아랫자리에서 올라온 올림까지 세 개를 더해야 해서, 반가산기 두 개와 OR 하나로 만들어요.
- 300은 2진수로 9자리라 8비트에 다 담기지 않아요. 아래 8자리가 나타내는 44만 남고, 맨 위의 올림은 넘쳐요(오버플로).
- 빼는 수의 비트를 모두 뒤집고, 맨 아랫자리에 넣는 올림을 1로 줘서 더해요. 이게 2의 보수를 더하는 것이고, 결과가 뺄셈과 같아요.
- 두 게이트가 서로의 출력을 입력으로 받는 고리가 있어서, 입력을 떼어도 신호가 고리를 돌며 이전 값을 붙잡고 있기 때문이에요.
- 올림이 아랫자리부터 차례로 전해져야 해서 자리 수만큼 기다려야 하기 때문이에요. 올림을 미리 계산하는 올림 예측 덧셈기로 기다리는 단계를 줄여요.
다음 강의
래치는 "지금 상태"와 "들어온 입력"으로 다음 상태를 정하는 회로였어요. 이 생각을 회로에서 떼어 내 수학으로 다듬으면 가장 단순한 계산 모델인 유한 오토마타가 돼요. 다음 강의에서는 오토마타를 직접 만들어 보고, 매일 쓰는 정규 표현식이 사실 오토마타라는 것, 그리고 정규 표현식으로는 절대 할 수 없는 일이 무엇인지 알아봐요.