3강 듣다 포기했던 디지털 논리회로 다시 시작하기

처음에 3강 정도 듣다가 포기했던 디지털 논리회로 과목에 다시 흥미가 생겼다. '컴퓨터 밑바닥의 비밀'이라는 책을 읽으면서 든 생각을 시작으로 디지털 논리회로의 기초를 정리해봤다.

모든 것은 CPU에서 시작된다

우리가 쓴 코드들은 결국 컴퓨터가 해석할 수 있는 0과 1의 기계어로 변환되어 실행 파일에 담긴다. CPU는 이 명령어를 하나씩 가져와 해석하고 실행하는 일을 반복한다.

'CPU는 명령어를 하나씩 처리하는데, 그럼 여러 프로그램은 어떻게 동시에 돌아가는 걸까?' 이 질문에서 운영체제, 프로세스, 스케줄링 같은 개념이 출발한다.

많은 CS 책이 프로세스는 실행 중인 프로그램, 스레드는 프로세스 실행 흐름의 단위처럼 설명하지만 CS 개념들은 결국 CPU라는 한정된 자원을 어떻게 더 효율적으로 나눠 쓸 것인가라는 질문에서 시작된다는 생각이 들었다.

디지털 논리회로는 더 아래로 내려가 CPU가 실제로 0과 1을 어떻게 처리하는지, 연산 회로가 어떤 식으로 만들어지는지 배우는 과목이다.

우리는 컴퓨터 안에서 어떤 일이 일어나는지 몰라도 사용할 수 있지만

// 마치 돈 내면 그린애플을 주는 함수처럼
function getGreenApple(money: number) {
  // 과정은 몰라도 돼
  return greenApple;
}

이 블랙박스 같은 컴퓨터를 조금씩 이해해보자.

1 + 2 ? // How?

논리 게이트

컴퓨터 안에서 0(꺼짐)과 1(켜짐) 신호를 받아 정해진 규칙대로 하나의 결과를 내보내는 작은 부품이다. 예를 들어 AND 게이트는 두 입력이 모두 1일 때만 1을 내보낸다. 이러한 논리 게이트들을 여러 개 연결해 더 복잡한 판단을 할 수 있는 논리회로를 만든다.

AND 게이트

논리곱이라고도 한다. 모든 입력이 참이면 참을 출력한다. JS의 && 연산자에 해당한다.

$F = X \cdot Y$

OR 게이트

논리합이라고도 한다. 입력 중 하나라도 참이면 참을 출력한다. JS의 || 연산자에 해당한다.

$F = X + Y$

NOT 게이트

논리 부정이라고도 한다. 입력값을 뒤집는다. JS의 ! 연산자에 해당한다.

$F = \bar{X}$

NAND, NOR

NAND는 NOT AND, 즉 AND 게이트의 결과를 반전해 출력한다. !(X && Y)에 해당한다.

$F = \overline{X \cdot Y}$

NOR은 OR의 결과를 반전한다. !(X || Y)에 해당한다.

$F = \overline{X + Y}$

XOR, XNOR

XOR(Exclusive OR)은 배타적 논리합이라고도 한다. 입력이 서로 다를 때만 참(1)을 출력한다. 논리적으로 서로 다른 것을 선택하는 연산이다.

$F = X \oplus Y$

XNOR은 XOR의 반대로, 두 입력이 같을 때 1을 출력한다. 논리적으로 서로 같은 것을 선택하는 연산이다.

$F = \overline{X \oplus Y}$

부울 대수와 부울 함수

부울 대수(Boolean Algebra)는 0과 1의 값을 갖는 논리 변수와 논리 연산을 다루는 대수다. 모든 값을 참 또는 거짓으로 나타내며, AND, OR, NOT을 기본 연산으로 한다.

부울 함수는 부울 대수를 기반으로 입력 값의 조합에 따라 참 또는 거짓을 출력하는 함수다. 하나 이상의 부울 연산 조합으로 구성되며, 세 가지 방법으로 표현할 수 있다.

1. 부울 식(논리식)
2. 진리표
3. 논리 회로도

동일한 진리표를 표현할 수 있는 부울 함수는 여러 개다. 게이트를 적게 쓸수록 회로 제작 비용이 줄어들고, 속도가 빨라진다. 따라서 최대한 간단한 형태로 만드는 게 좋다.

핵심 법칙

1은 true, 0은 false로 프로그래밍에 대입해 생각하면 이해하기 쉽다.

쌍대성 원리

부울 대수에서는 OR과 AND, 참과 거짓을 모두 바꾸면 연산 성질이 그대로 유지된다. 이걸 쌍대성이라고 한다.

$X + 0 = X \quad \iff \quad X \cdot 1 = X$

따라서 위에서 살펴본 핵심 법칙은 이렇게 바꿔도 성립한다.

분배 법칙

$X + Y \cdot Z = (X + Y) \cdot (X + Z)$

이건 일반 산술에서는 성립하지 않는데, 부울 대수에서는 성립한다. 아래 공식에 쌍대성 원리를 적용해 OR을 AND로 바꾼 것이다.

$X · (Y + Z) = X·Y + X·Z$

직접 계산해보면 $(X + Y) \cdot (X + Z) = X \cdot X + X \cdot Z + Y \cdot X + Y \cdot Z$

X·X = X이므로

1 + 아무거나 = 1이므로

$= X \cdot 1 + Y \cdot Z = X + Y \cdot Z$

회로 설계

이제 본격적으로 회로 설계의 흐름을 보자.

[요구사항] - ex) X가 1이고 Y가 0이면 출력값은 1이 되어야 해
   ↓
[진리표]   - 입력 조합과 원하는 출력을 표로 정리한다
   ↓
[정규형]   - 진리표를 식으로 변환한다
   ↓
[표준형]   - 식을 간소화한다
   ↓
[회로 구현] - 게이트로 그린다

정규형: 진리표를 식으로

정규형을 통해 진리표를 식으로 옮길 수 있다. 곱의 합(SOP)과 합의 곱(POS)으로 표현할 수 있는데, 이때 최소항과 최대항이라는 재료를 사용한다.

최소항

이 부분이 조금 헷갈렸는데, 최소항은 식이 짧아서 최소가 아니라 그 항이 1이 되는 입력 조합이 딱 1개라는 뜻이다.

A·B'·C라는 최소항이 1이 되는 조합은 (A=1, B=0, C=1) 하나뿐이며 나머지는 전부 0이다. 모든 변수를 AND로 곱한 형태이며, 진리표에서 0이 나와야 하는 변수에는 NOT을 붙여 주는 식으로 만든다.

최대항

최대항은 그 반대다. 8개 행 중 딱 1개 행에서만 0이고 나머지 7개 행에서는 모두 1이다. 즉 1이 되는 경우가 최대(=7개, 거의 다)라서 최대항이다. 모든 변수를 OR로 합한 형태로 만든다.

곱의 합 (SOP)

출력이 1이 되는 행만 모은다. 각 행마다 그 조합일 때 1이 되도록 항을 하나 만들고(최소항), 항들을 OR로 합친다.

합의 곱 (POS)

출력이 0이 되는 행을 모은다. 각 행마다 그 조합만 막도록 항을 하나 만들고(최대항), 항들을 AND로 묶는다.

비유하자면 시험 점수를 구하는 두 가지 방법과 같다. 맞은 문제 점수를 다 더하는 방식이 SOP이고, 100점에서 틀린 문제 점수를 빼는 방식이 POS다.

이 진리표를 SOP로 표현하면 아래와 같다.

$F = \bar{X} \cdot Y \cdot \bar{Z} + X \cdot \bar{Y} \cdot \bar{Z}$

진리표를 정규형으로 변환하고 간소화를 시작한다.

간소화

대수적 간소화

정규형을 그대로 회로로 만들면 게이트가 많이 필요하고 논리 회로가 복잡해진다. 위에서 살펴본 부울 대수 법칙으로 식을 줄이는 방법을 대수적 간소화라고 하며, 간소화된 식을 표준형이라고 한다.

$X \cdot \bar{Y} \cdot \bar{Z} + X \cdot Y \cdot \bar{Z}$ $= X \cdot \bar{Z} \cdot (\bar{Y} + Y) = X \cdot \bar{Z} \cdot 1 = X \cdot \bar{Z}$

카르노맵

대수적 간소화는 숙련도에 따라 결과가 달라질 수 있고, 어렵다. 그래서 카르노맵이 자주 쓰인다. 카르노맵도 본질적으로는 대수적 간소화를 기반으로 하지만 더 직관적이다. 아래의 원리를 적용해 표로 만든다.

인접한 1들을 묶으면 변하는 변수가 사라지고 공통 변수만 남는다.

3변수인 경우에는 아래와 같이 표현하는데, 도표는 그레이 코드(인접 칸은 변수 하나만 다른 코드) 순서로 배치된다. 그래서 옆에 붙어있는 칸은 자동으로 변수 하나만 다른 관계가 된다.

3변수 카르노맵:

         YZ
        00  01  11  10
   X 0 [  ][  ][  ][  ]
     1 [  ][  ][  ][  ]

카르노맵에서 간소화된 식을 도출하는 과정은 다음과 같다. 나중에 가산기 회로를 만들어보며 실습해보자.

1. 1이 되는 칸을 표시
2. 인접한 1들을 가능한 크게 묶는다 (2, 4, 8 같은 2^n 크기로)
3. 각 묶음에서 변하지 않는 변수만 남긴다
4. 남은 항들을 OR로 합친다

   00 01 11 10
0 [ 1][  ][  ][ 1]

참고로 00과 10은 표에서는 양 끝에 있지만 인접항이다. 원래 카르노맵은 3차원 도넛 형태로 생각해야 정확한데, 표현이 복잡해 2차원으로 펼쳐놓은 것이다.

무관조건

회로가 특정 입력 조합을 절대 받지 않는 경우가 있는데, 예를 들어 BCD 코드(0~9를 4비트로 표현)에서는 1010부터 1111까지 6개 조합이 들어오지 않는다.

BCD 코드:
0000 = 0
0001 = 1
...
1001 = 9
1010 ~ 1111 = 사용 안 함

이런 입력에 대해서는 출력이 0이든 1이든 상관없다. 이걸 무관조건이라고 하는데, 카르노맵에서는 X로 표시한다.

   00 01 11 10
0 [ 1][ 1][ X][  ]
1 [  ][ X][ 1][  ]

X는 우리에게 유리한 방향으로 해석할 수 있다. 묶음을 더 크게 만들 수 있으면 1로 치고, 그렇지 않으면 0으로 친다. 무관조건을 활용해 식을 더 줄일 수 있다. 다만 이 입력은 절대 안 들어온다는 보장이 있을 때 사용해야 한다. 회로는 입력된 모든 것을 처리하기 때문에 어차피 안 들어온다는 전제가 깨지면 무관조건의 의미도 깨진다.

XOR 패턴

카르노맵에서 1이 체스판처럼 배치되면 XOR 패턴이다.

2변수 XOR:        3변수 XOR:
   0 1               00  01  11  10
 0[0 1]           0 [  ][1 ][  ][1 ]
 1[1 0]           1 [1 ][  ][1 ][  ]

XOR은 홀수 개의 입력이 1일 때 1이 되는 odd function 성질을 가진다. 카르노맵에서 이런 패턴을 발견하면 AND-OR로 풀어쓰는 것보다 XOR로 표현하는 게 더 간결하다.

NAND와 NOR: 만능 게이트

부울 함수는 NOT, AND, OR 세 게이트로 다 만들 수 있다. 이걸 함수적 완결성이라고 한다. 이 게이트들의 조합으로 모든 논리식을 표현할 수 있지만, NAND나 NOR은 하나만으로 모든 논리식을 만들 수 있다. 단독으로 함수적 완결성을 가져서 만능 게이트라고 부르기도 한다. 실제 회로는 비용 절약을 위해 대부분 NAND나 NOR로 구성된다.

NAND로 NOT, AND, OR 만들기

NAND로 NOT 만들기

$X \, \text{NAND} \, X = \bar{X}$

NAND로 AND 만들기

$(X \, \text{NAND} \, Y) \, \text{NAND} \, (X \, \text{NAND} \, Y) = X \cdot Y$

NAND로 OR 만들기

$(X \, \text{NAND} \, X) \, \text{NAND} \, (Y \, \text{NAND} \, Y) = X + Y$

정리

1. 논리 게이트는 0과 1만 다루는 회로의 최소 단위다. AND, OR, NOT이 기본이고, NAND, NOR, XOR 같은 파생 게이트가 있다.

2. 부울 대수는 게이트들의 동작을 식으로 다루는 수학 체계다. 같은 동작을 다양한 식으로 표현할 수 있고, 더 짧은 식이 더 적은 게이트로 회로를 만들 수 있게 해준다.

3. 회로 설계는 진리표 → 정규형 → 표준형 → 회로의 흐름을 따른다. 정규형을 이용해 진리표를 식으로 변환하고, 그걸 간소화해 표준형을 구한다. 카르노맵은 간소화를 시각적으로 도와준다.

4. NAND나 NOR 하나만으로 모든 부울 함수를 표현할 수 있다. 그래서 실제 반도체는 대부분 이 두 게이트로 만들어진다.