Chapter 02

불 대수와 논리 게이트

1장에서 우리는 연속적인 전압을 0과 1 두 칸으로 나누기로 약속했다. 그 약속 위에서는 회로가 하는 일을 "0과 1을 받아 0과 1을 내놓는 함수"로 적을 수 있다. 1854년 조지 불이 논리를 대수로 적는 방법을 만들었고, 80여 년 뒤 클로드 섀넌이 그 대수가 스위치 회로를 그대로 묘사한다는 것을 보였다. 이 장에서는 트랜지스터를 잠시 잊고 함수 자체를 다룬다. 진리표를 식으로 바꾸고, 식을 줄이고, 줄인 식을 게이트로 짓는다. 그리고 식으로는 완벽한 회로가 실제로는 잠깐씩 틀린 값을 내는 이유, 해저드까지 들여다본다.

일곱 가지 기본 게이트의 진리표와 불 대수 법칙을 익히고, 드모르간 정리를 버블 밀기로 적용한다.
진리표에서 SOP·POS 정규형을 쓰고, 카르노 맵과 Quine–McCluskey 방법으로 최소 2단 식을 구한다.
NAND·NOR의 범용성과 MUX·디코더·LUT 같은 조합 빌딩 블록이 임의의 함수를 만드는 방식을 이해한다.
게이트 지연 때문에 생기는 정적 해저드를 파형으로 확인하고, 합의항으로 없앤다. 2단과 다단 논리의 비용을 비교한다.

논리 게이트와 진리표

디지털 회로에서 다루는 함수는 모양이 단순하다. 입력 $n$개가 각각 0 또는 1이므로 가능한 입력 조합은 $2^n$개뿐이고, 각 조합에서 출력이 0인지 1인지만 적으면 함수가 완전히 정해진다. 이 목록이 진리표(Truth table)다. 이런 함수를 불 함수(Boolean function)라 하고, 불 함수를 계산하는 가장 작은 회로 단위가 논리 게이트(Logic gate)다.

기본 게이트는 일곱 가지다. 하나를 뒤집는 NOT, "모두 1이면 1"인 AND, "하나라도 1이면 1"인 OR, 그 둘의 출력을 뒤집은 NAND와 NOR, "서로 다르면 1"인 XOR와 그 반대인 XNOR. 출력 끝의 작은 동그라미, 즉 버블(Bubble)이 "뒤집는다"는 표시다. 아래 갤러리에서 입력 칩이나 진리표 칸을 눌러 보자. 선의 색이 논리값이다. 1은 초록, 0은 회색으로, 이 책 전체에서 같은 뜻으로 쓴다.

그림 2-1. 해 보기일곱 게이트가 같은 입력 A, B를 공유한다. 아무 카드의 입력 칩(A=0)을 누르거나 진리표 띠의 칸을 누르면 입력이 바뀌고, 모든 게이트의 출력이 함께 바뀐다. 진리표 띠의 강조된 칸이 지금 입력 조합이다. NAND는 AND의, NOR는 OR의, XNOR는 XOR의 출력을 정확히 뒤집은 것임을 확인해 보자.

불 대수에서는 AND를 곱셈처럼, OR를 덧셈처럼 적는다. 실제로 0과 1만 놓고 보면 AND는 곱셈과 똑같고, OR는 "1+1=1"이라는 점만 빼면 덧셈과 닮았다. NOT은 변수 위에 줄을 긋는다.

$$\text{AND: } A\cdot B \qquad \text{OR: } A+B \qquad \text{NOT: } \overline{A} \qquad \text{XOR: } A\oplus B = A\overline{B}+\overline{A}B$$

$\cdot$은 흔히 생략해 $AB$로 쓴다. 우선순위는 NOT → AND → OR 순서다. 즉 $A+BC$는 $A+(B\cdot C)$다. NAND는 $\overline{AB}$, NOR는 $\overline{A+B}$, XNOR는 $\overline{A\oplus B}$다.

XOR는 특별한 대접을 받을 만하다. 두 비트가 "다르다"를 검출하므로 비교기에 쓰이고, 1비트 덧셈의 합 비트가 정확히 $A\oplus B$다(11장). 입력을 여러 개로 늘린 XOR는 1의 개수가 홀수인지 짝수인지를 알려 주는 패리티(Parity) 회로가 된다.

3입력 XOR

$Y = A\oplus B\oplus C$는 여덟 가지 입력 조합 중 언제 1일까? 2입력 XOR를 두 번 이어 붙였다고 생각하고 답해 보자.

답 보기

1의 개수가 홀수일 때, 즉 001, 010, 100, 111의 네 경우에 1이다. XOR는 결합 법칙이 성립하므로 몇 개를 어떤 순서로 이어도 "1이 홀수 개인가"를 계산한다. 뒤 절의 카르노 맵에서 이 함수는 어떤 두 칸도 묶을 수 없는 체크무늬로 나타난다. 2단 논리로는 가장 비싼 함수다.

2입력 함수는 모두 16가지

입력이 2개면 진리표는 4행이고, 각 행의 출력을 0이나 1로 고르는 방법은 $2^4=16$가지다. 일반적으로 $n$입력 함수는 $2^{2^n}$가지다. 16개 중 상수(0, 1)가 2개, 한 입력만 보는 함수($A, B, \overline{A}, \overline{B}$)가 4개, AND·OR·NAND·NOR·XOR·XNOR가 6개, 나머지 4개는 $\overline{A}B$처럼 한 입력만 뒤집은 AND와 그 보수(OR형)다. 기본 게이트 몇 종류만으로 16개를 모두 만들 수 있다는 것이 이 장 후반의 주제다.

불 대수의 법칙과 드모르간

식을 다루려면 계산 규칙이 필요하다. 불 대수의 법칙은 대부분 보통 대수와 닮았지만 몇 가지가 다르다. $A+A=A$(멱등), $A+1=1$(영 법칙), 그리고 덧셈이 곱셈 위로 분배되는 $A+BC=(A+B)(A+C)$는 보통 대수에서는 틀린 식이다. 모든 법칙은 쌍대(Duality) 짝을 갖는다. 식에서 AND↔OR, 0↔1을 맞바꾸면 또 하나의 참인 법칙이 나온다.

법칙	OR 형태	AND 형태 (쌍대)
항등	$A+0=A$	$A\cdot 1=A$
영(지배)	$A+1=1$	$A\cdot 0=0$
멱등	$A+A=A$	$A\cdot A=A$
보원	$A+\overline{A}=1$	$A\cdot\overline{A}=0$
이중 부정	$\overline{\overline{A}}=A$
교환	$A+B=B+A$	$AB=BA$
결합	$(A+B)+C=A+(B+C)$	$(AB)C=A(BC)$
분배	$A+BC=(A+B)(A+C)$	$A(B+C)=AB+AC$
흡수	$A+AB=A$	$A(A+B)=A$
결합(Combining)	$AB+A\overline{B}=A$	$(A+B)(A+\overline{B})=A$
드모르간	$\overline{A+B}=\overline{A}\,\overline{B}$	$\overline{AB}=\overline{A}+\overline{B}$
합의	$AB+\overline{A}C+BC=AB+\overline{A}C$	$(A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)$

법칙을 확인하는 가장 확실한 방법은 진리표를 끝까지 써 보는 것이다(완전 귀납(Perfect induction)). 변수가 셋이면 8행이면 된다. 같은 일을 그림으로 하는 도구가 벤 다이어그램이다. 각 원은 그 변수가 1인 영역이고, 칠해진 영역이 식이 1인 입력 조합이다. 양변의 칠한 모양이 같으면 법칙이 성립한다.

법칙 고르기

—

그림 2-2. 해 보기법칙을 고르면 왼쪽 식과 오른쪽 식이 각각 1이 되는 영역이 초록으로 칠해진다. 두 식이 다른 영역이 있으면 빨간 빗금으로 표시된다. 영역을 누르면 그 영역의 입력값과 양변의 값을 보여 준다. "흔한 실수" 두 항목은 일부러 틀린 식이다. 어디서 어긋나는지 찾아보자.

법칙 가운데 회로 설계에서 가장 자주 쓰는 것은 드모르간 정리(De Morgan's theorem)다. 말로 하면 "AND의 부정은 부정들의 OR, OR의 부정은 부정들의 AND"다. 회로로 읽으면 더 쓸모 있다. NAND 게이트는 입력에 버블을 단 OR 게이트와 같고, NOR 게이트는 입력에 버블을 단 AND 게이트와 같다.

$$\overline{A\cdot B}=\overline{A}+\overline{B}, \qquad \overline{A+B}=\overline{A}\cdot\overline{B}, \qquad \overline{X_1X_2\cdots X_n}=\overline{X_1}+\overline{X_2}+\cdots+\overline{X_n}$$

게이트 모양으로는 "몸체를 AND↔OR로 바꾸고, 출력 쪽 버블을 입력 쪽으로 옮긴다(또는 그 반대)". 같은 선의 양 끝에 버블이 하나씩 있으면 두 번 뒤집은 것이므로 지워도 된다.

이 규칙으로 회로도에서 버블을 이리저리 옮기며 식을 바꾸는 기법을 버블 밀기(Bubble pushing)라 한다. 아래 회로는 NAND 세 개로 된 2단 회로다. 단계를 넘기며 마지막 NAND를 드모르간으로 바꾸면 선 양 끝의 버블이 짝지어 사라지고, 익숙한 AND-OR 회로가 드러난다.

—

그림 2-3. 해 보기세 단계를 차례로 눌러 보자. 단계마다 그림은 달라도 어떤 입력에서든 출력 Y는 같다. 입력 버튼이나 회로의 입력 칩을 눌러 확인할 수 있다. ②에서 점선 원으로 표시한 버블 두 개가 한 선의 양 끝에 있으므로 ③에서 함께 지워진다. NOR-NOR는 쌍대로 OR-AND, 즉 $(A+B)(C+D)$가 된다.

결론은 짧다. 2단 NAND-NAND 회로는 AND-OR(SOP) 회로와 같고, 2단 NOR-NOR 회로는 OR-AND(POS) 회로와 같다. CMOS 게이트는 본래 출력을 뒤집는 구조라 NAND·NOR가 AND·OR보다 싸고 빠르다(5장). 그래서 실제 칩의 합성 도구는 식을 AND-OR로 생각하고 회로는 NAND-NAND로 짓는다. 버블 밀기는 그 둘 사이를 오가는 번역기다.

섀넌의 석사 논문

1938년 발표된 클로드 섀넌의 석사 논문은 직렬로 이은 릴레이 접점이 AND, 병렬로 이은 접점이 OR와 같다는 것을 보이고, 불 대수로 전화 교환기 같은 스위치 회로를 설계하고 단순화할 수 있음을 보였다. 같은 논문에 나오는 섀넌 전개 $f = x\cdot f|_{x=1} + \overline{x}\cdot f|_{x=0}$는 어떤 함수든 한 변수로 쪼갤 수 있다는 정리로, 6절의 MUX와 FPGA, 그리고 논리 합성 도구의 BDD(이진 결정 다이어그램)의 바탕이 된다.

진리표에서 식으로: SOP와 POS 정규형

진리표가 주어지면 그 함수를 계산하는 식을 기계적으로 쓸 수 있다. 출력이 1인 행마다 "바로 그 입력일 때만 1"인 곱항을 만든다. 예를 들어 $A=1, B=0, C=1$인 행은 $A\overline{B}C$다. 모든 변수가 한 번씩 (원래 모양이든 뒤집힌 모양이든) 들어간 이런 곱항을 최소항(Minterm)이라 하고, 행 번호를 따서 $m_5$로 부른다. 출력이 1인 행들의 최소항을 모두 OR하면 함수가 된다. 이것이 곱의 합(SOP, Sum of Products) 정규형이다.

거꾸로 출력이 0인 행마다 "바로 그 입력일 때만 0"인 합항, 즉 최대항(Maxterm)을 만들어 모두 AND해도 된다. $A=1,B=0,C=1$에서만 0인 합항은 $\overline{A}+B+\overline{C}$이고 $M_5$로 쓴다. 이것이 합의 곱(POS, Product of Sums) 정규형이다.

$$Y=\sum m(i \mid Y_i=1) = \prod M(i \mid Y_i=0), \qquad m_i = \overline{M_i}$$

다수결 함수(셋 중 둘 이상이 1이면 1)의 예: $Y=\sum m(3,5,6,7)=\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC = \prod M(0,1,2,4)$. 최소항은 정확히 한 행에서만 1이고, 최대항은 정확히 한 행에서만 0이다.

—

그림 2-4. 해 보기진리표의 Y 칸을 눌러 0과 1을 바꾸면 SOP 회로가 바로 만들어진다. 출력이 1인 행마다 3입력 AND가 하나씩 생기고, 마지막 OR가 이들을 모은다. 왼쪽 세로선(레일)은 각 변수와 그 보수(인버터 출력)이고, 점이 찍힌 곳에서 AND 입력으로 갈라진다. 진리표의 A·B·C 칸을 누르면 그 행이 현재 입력이 되어 선 색이 바뀐다. 1이 되는 AND는 언제나 하나뿐이다.

정규형은 진리표를 그대로 옮긴 것이라 틀릴 일이 없지만, 크다. 3변수 다수결 함수의 SOP 정규형은 AND 4개에 리터럴(변수 등장) 12개를 쓰지만, 같은 함수를 $AB+AC+BC$로 쓰면 AND 3개, 리터럴 6개면 된다. 식을 줄이는 열쇠는 결합 법칙 $XA+X\overline{A}=X$다. 한 변수만 다른 두 최소항은 하나로 합쳐지며 그 변수가 사라진다. 예컨대 $ABC+AB\overline{C}=AB$다. 문제는 어떤 쌍을 합칠지 찾는 일인데, 그 일을 눈으로 하게 해 주는 도구가 다음 절의 카르노 맵이다.

정규형은 변수 수에 지수적으로 커진다

$n$변수 함수의 진리표는 $2^n$행이므로 정규형은 최악의 경우 $2^{n-1}$개 이상의 항을 갖는다. 32비트 두 수가 같은지 비교하는 함수(입력 64개)를 진리표로 쓰면 $2^{64}\approx 1.8\times10^{19}$행이다. 실제 설계는 진리표가 아니라 구조(XNOR 32개 + AND 트리)로 적는다. 정규형은 작은 블록에서 식을 얻는 출발점일 뿐이다.

카르노 맵: 식을 눈으로 줄이기

1953년 모리스 카르노가 제안한 카르노 맵(Karnaugh map, K-map)은 진리표를 바둑판으로 다시 배열한 것이다. 요령은 행과 열의 순서를 00, 01, 11, 10으로, 즉 이웃한 두 칸이 한 비트만 다르도록 그레이 코드(Gray code) 순서로 놓는 데 있다. 그러면 결합 법칙으로 합칠 수 있는 최소항 쌍이 맵에서 나란히 붙은 칸으로 보인다. 맨 왼쪽 열과 맨 오른쪽 열도 한 비트만 다르므로 서로 이웃이다. 맵은 사실 도넛(토러스) 표면이다.

최소화 규칙은 다음과 같다.

1인 칸을 $1, 2, 4, 8, \dots$개짜리 직사각형으로 묶는다(가장자리를 넘어 반대편으로 이어져도 된다). $2^k$칸 묶음은 변수 $k$개가 사라진 곱항이 된다.
묶음은 가능한 한 크게 잡는다. 더 키울 수 없는 묶음을 주항(Prime implicant)이라 한다.
모든 1이 적어도 한 묶음에 들도록 하되, 묶음 수는 가능한 한 적게 고른다. 어떤 1을 덮는 주항이 단 하나뿐이면 그 주항은 반드시 들어가야 한다. 이를 필수 주항(Essential prime implicant)이라 한다.
출력이 어떻든 상관없는 입력(예: BCD에서 10~15)은 무관 조건(Don't care, X)으로 두고, 묶음을 키우는 데 도움이 될 때만 1로 쓴다.

SIMULATOR

카르노 맵 최소화기 (Quine–McCluskey + 최소 피복)

변수 개수

최소화 형태

묶음 표시

칸을 누르면

예제

동작

1 / 0 / X 칸—

주항 (필수)—

리터럴: 정규형 → 최소—

2단 게이트: 정규형 → 최소—

최소 해의 수—

—

칸을 누르면 값이 바뀌고, 즉시 Quine–McCluskey 방법으로 모든 주항을 구한 뒤 분기 한정(branch and bound)으로 항 수가 가장 적고 그다음 리터럴 수가 가장 적은 피복을 정확히 고른다. 색 묶음과 식의 색이 서로 대응한다. 가장자리에서 잘린 묶음은 반대편으로 이어진다는 뜻이다. 게이트 수는 인버터를 빼고 AND(리터럴 2개 이상인 항)와 마지막 OR를 센 값이다. POS를 고르면 0을 묶어 합항의 곱을 만든다.

시뮬레이터가 내부에서 쓰는 방법은 1952~1956년 콰인과 매클러스키가 정리한 Quine–McCluskey 방법이다. 카르노 맵의 "눈으로 묶기"를 컴퓨터가 할 수 있게 표로 바꾼 것으로, 두 단계로 이루어진다.

주항 찾기: 최소항(무관 칸 포함)을 1의 개수로 줄 세운 뒤, 한 비트만 다른 쌍을 모두 합쳐 그 비트를 "–"로 바꾼다($0101, 0111 \to 01\!-\!1$). 합쳐진 항끼리 또 합치기를 더 이상 합칠 것이 없을 때까지 반복한다. 한 번도 합쳐지지 못한 항이 주항이다.
피복 고르기: 행이 주항, 열이 1인 최소항인 표를 만든다. 한 열에 표시가 하나뿐이면 그 행이 필수 주항이다. 필수 주항을 고르고 남은 열을 가장 싸게 덮는 조합을 찾는다. 이 단계는 집합 피복 문제라 일반적으로 어렵다. 시뮬레이터는 변수가 4개 이하이므로 남은 경우를 모두 따져 정확한 최소를 구한다.

네 귀퉁이

4변수 맵에서 네 귀퉁이 칸 $m_0, m_2, m_8, m_{10}$만 1이다. 최소 SOP는 몇 개의 리터럴로 쓸 수 있을까? 시뮬레이터에 찍어 보기 전에 예상해 보자.

답 보기

리터럴 2개, $\overline{B}\,\overline{D}$다. 맨 위 행과 맨 아래 행이 이웃이고 맨 왼쪽 열과 맨 오른쪽 열이 이웃이므로 네 귀퉁이는 하나의 2×2 묶음이다. 네 칸 모두 $B=0, D=0$이고 A와 C는 0과 1이 섞여 있어 사라진다. 정규형 리터럴 16개가 2개로 줄었다.

순환 피복과 여러 개의 최소 해

"순환 피복" 예제를 불러오면 여섯 개의 주항 중 필수 주항이 하나도 없다. 어느 1이든 두 주항이 덮고 있어서 출발점이 정해지지 않는다. 이런 경우 최소 해가 여럿일 수 있고(이 예는 2개), 사람이 맵에서 눈으로 찾다가 더 큰 해를 고르기 쉽다. 식이 다르더라도 진리표는 같다. 최소 해는 유일하지 않다.

4변수를 넘어서면

카르노 맵은 5~6변수까지가 사람이 다룰 수 있는 한계다. Quine–McCluskey는 정확하지만 주항 수가 변수 수에 지수적으로 늘 수 있고, 최소 피복은 NP-난해 문제다. 그래서 실제 도구는 1980년대 버클리에서 나온 Espresso 같은 휴리스틱으로 "거의 최소"인 2단 식을 빠르게 찾고, 오늘날 합성 도구는 2단 식보다 다단 논리 그래프(AIG)를 다시 쓰는 방식으로 최적화한다. RTL에서 게이트까지의 흐름은 17장과 시리즈의 DesignBook에서 다룬다.

범용 게이트: NAND 하나면 충분하다

AND, OR, NOT 세 가지만 있으면 어떤 불 함수든 만들 수 있다. SOP 정규형이 그 증거다. 이렇게 모든 함수를 만들 수 있는 게이트 집합을 함수적으로 완전(Functionally complete)하다고 한다. 놀라운 사실은 NAND 하나만으로도 완전하다는 것이다. 두 입력을 묶은 NAND는 NOT이고($\overline{AA}=\overline{A}$), NAND 뒤에 NOT을 달면 AND이며, 입력을 뒤집은 NAND는 드모르간에 의해 OR다. NOT·AND·OR를 만들 수 있으니 무엇이든 만들 수 있다. NOR도 쌍대로 같은 성질을 가진다. 이런 게이트를 범용 게이트(Universal gate)라 한다.

NAND2 개수—

트랜지스터 (NAND만)—

전용 CMOS 셀—

논리 깊이—

그림 2-5. 해 보기함수를 골라 NAND2만으로 지은 회로를 보자. 입력을 바꾸며 내부 선의 값을 따라가 보면 각 NAND가 무슨 일을 하는지 보인다. XOR는 NAND 4개로 만드는 고전적인 구조다. 가운데 NAND의 출력 $\overline{AB}$가 두 번째 단의 양쪽에 함께 쓰인다. 트랜지스터 수는 NAND2 하나를 4개로 센 값이고, "전용 CMOS 셀"은 그 함수를 직접 정적 CMOS로 만들 때의 대략적인 수다.

그렇다면 왜 실제 칩은 NAND만 쓰지 않을까? 범용성은 "만들 수 있다"는 뜻이지 "싸다"는 뜻이 아니다. XOR를 NAND로 지으면 트랜지스터 16개, 3단이지만 전용 XOR 셀은 8~12개로 한두 단이면 된다. 그래서 표준 셀 라이브러리는 수백 종의 셀을 갖추고 합성 도구가 고른다. 그래도 CMOS에서 NAND와 NOR가 기본인 이유는 분명하다. CMOS 게이트는 nMOS가 켜지면 출력을 0으로 끌어내리므로 본질적으로 출력을 뒤집는다. 뒤집는 게이트(NOT, NAND, NOR, AOI)는 트랜지스터 한 단으로 되지만, 뒤집지 않는 AND·OR는 NAND·NOR 뒤에 인버터를 하나 더 붙여야 한다(4장, 5장).

게이트	트랜지스터 수	입력 하나의 게이트 폭 (단위)	입력 커패시턴스 (DG-7)	논리적 노력 g
NOT	2	1 + 1.6 = 2.6	0.21 fF	1
NAND2	4	2 + 1.6 = 3.6	0.29 fF	1.38
NOR2	4	1 + 3.2 = 4.2	0.34 fF	1.62
NAND3	6	3 + 1.6 = 4.6	0.37 fF	1.77
NOR3	6	1 + 4.8 = 5.8	0.46 fF	2.23
AND2 (NAND2 + NOT)	6	3.6	0.29 fF	2단
XOR2 (정적 CMOS / 전송 게이트형)	12 / 8	—	—	약 4

표는 이 책의 기준 공정 DG-7(nMOS 대비 pMOS 구동력 비 $\mu=1.6$, 단위 폭 게이트 커패시턴스 0.08 fF)로 계산했다. 인버터와 같은 구동력을 내도록 크기를 맞추면, NAND2는 직렬 nMOS 두 개를 두 배로 키우고 NOR2는 직렬 pMOS 두 개를 두 배로 키워야 한다. pMOS가 약하기 때문에 NOR의 입력이 더 무겁고($g=1.62$), 그래서 같은 함수라면 NOR보다 NAND를 선호한다. 논리적 노력 $g$가 지연에 어떻게 들어가는지는 6장에서 계산한다.

NOR 게이트로 달에 가다

아폴로 유도 컴퓨터(AGC)의 블록 II는 3입력 NOR 게이트 두 개가 든 집적 회로 약 2,800개로만 만들어졌다. 한 종류의 칩만 대량으로 사서 품질 관리를 하기 쉬웠기 때문이다. 범용 게이트 하나로 컴퓨터 전체를 지은 실제 사례다.

조합 회로의 빌딩 블록: MUX·디코더·다수결·패리티

게이트를 하나하나 고르는 대신, 자주 쓰는 모양을 블록으로 묶어 두면 설계가 쉬워진다. 출력이 현재 입력만으로 정해지는(기억이 없는) 회로를 조합 회로(Combinational circuit)라 한다. 그 대표 블록 네 가지를 만져 보자.

멀티플렉서(MUX): 선택 신호 S로 여러 입력 중 하나를 고른다. 2:1 MUX는 $Y=\overline{S}D_0+SD_1$이다. 데이터 경로의 "갈림길"이다.
디코더(Decoder): $n$비트 주소를 받아 $2^n$개 출력 중 정확히 하나만 1로 만든다. 출력 하나하나가 최소항이다. 메모리의 행 선택에 쓰인다(13장).
다수결(Majority): 셋 중 둘 이상이 1이면 1. 전가산기의 캐리 출력이 바로 이 함수다(11장). 삼중 모듈 중복(TMR)에서 고장 난 하나를 무시하는 투표기로도 쓰인다.
패리티(Parity): XOR 트리로 1의 개수가 홀수인지 계산한다. 오류 검출 코드의 기본이다(16장).

—

그림 2-6. 해 보기블록을 고르고 입력 칩(또는 아래 버튼)을 눌러 보자. MUX에서는 S를 바꾸면 출력이 D0을 따라가다가 D1을 따라간다. 디코더는 어떤 입력에서든 출력 넷 중 꼭 하나만 초록이다. 패리티는 어떤 입력 하나를 뒤집어도 출력이 뒤집힌다.

MUX는 단순한 갈림길 이상이다. 섀넌 전개 $f=\overline{x}f|_{x=0}+xf|_{x=1}$은 정확히 2:1 MUX의 식이다. 한 변수로 MUX를 고르고, 두 입력에는 나머지 변수로 된 더 작은 함수를 넣으면 된다. 이 쪼개기를 끝까지 하면 마지막에는 상수 0, 1만 남는다. 즉 $2^n$:1 MUX의 데이터 입력에 진리표를 그대로 적어 두면 어떤 $n$입력 함수든 된다. 이것이 룩업 테이블(LUT, Look-up table)이고, FPGA가 임의의 회로를 "다시 쓸 수 있게" 구현하는 방법이다.

설정 불러오기

설정 비트 m7…m0—

구현된 함수—

선택된 칸—

그림 2-7. 해 보기3입력 LUT는 설정 비트 8개와 2:1 MUX 7개로 된 나무다. 왼쪽 설정 비트를 눌러 진리표를 바꾸고, 아래쪽 A·B·C 칩을 눌러 입력을 바꿔 보자. 굵은 선이 지금 선택된 경로다. C가 첫 단, B가 둘째 단, A가 마지막 단을 고르므로 선택되는 칸 번호는 $4A+2B+C$다. 회로는 그대로인데 비트 8개만 바꾸면 $2^8=256$가지 함수 중 무엇이든 된다.

FPGA의 LUT

초기 FPGA는 4입력 LUT(설정 비트 16개)를 썼고, 2006년 무렵부터는 6입력 LUT(64비트)가 주류가 되었다. 설정 비트는 SRAM 셀에 저장되므로 전원을 켤 때 비트스트림을 다시 불러온다. LUT 하나는 무엇이든 되는 대신, 같은 함수를 표준 셀로 만든 ASIC보다 면적은 대략 수십 배, 지연과 전력은 몇 배 크다. MUX를 트랜지스터 몇 개로 싸게 짓는 패스 트랜지스터 기법은 7장에서 다룬다.

해저드: 식은 맞는데 출력이 튄다

지금까지는 게이트가 입력이 바뀌는 순간 출력도 바로 바뀐다고 가정했다. 실제 게이트에는 지연이 있다. DG-7 공정에서 게이트 한 단은 대략 FO4 하나, 약 7.5 ps 정도다. 서로 다른 경로를 지난 신호가 조금씩 다른 시각에 도착하면, 정상 상태 값은 바뀌지 않아야 할 출력이 아주 잠깐 반대 값으로 튀었다가 돌아올 수 있다. 이 짧은 펄스를 글리치(Glitch)라 하고, 회로가 글리치를 낼 가능성을 해저드(Hazard)라 한다.

고전적인 예가 $Y=AB+\overline{A}C$다. $B=C=1$이면 식은 $Y=A+\overline{A}=1$로, A가 무엇이든 1이어야 한다. 그런데 A가 1→0으로 떨어지면 $AB$ 항은 AND 지연 뒤에 바로 꺼지지만, $\overline{A}C$ 항은 인버터를 하나 더 거쳐야 켜진다. 그 사이 인버터 지연만큼 두 항이 모두 0이고 Y가 0으로 떨어진다. 출력이 1로 머물러야 할 때 생기는 이 0 펄스가 정적-1 해저드(Static-1 hazard)다. POS 회로에서는 쌍대로 0이어야 할 출력이 1로 튀는 정적-0 해저드가 생긴다.

SIMULATOR

게이트 지연과 정적 해저드 (DG.Circuit 이벤트 시뮬레이션)

회로

합의항 추가

인버터 지연 AND·OR 지연

고정 입력

시각 커서 t

애니메이션

해저드—

글리치 폭—

Y 천이 횟수—

게이트 수—

A는 t=20에서 1→0, t=34에서 0→1로 바뀐다. 시간 단위 1은 대략 FO4 한 번(DG-7에서 약 7.5 ps)으로 보았다. 시뮬레이터는 전송 지연 모델이라 아무리 짧은 펄스도 걸러지지 않고 그대로 전파된다. 실제 게이트는 너무 짧은 펄스를 어느 정도 삼킨다(관성 지연). 위쪽 회로도는 커서 시각의 선 값을 보여 준다. 빨간 띠가 글리치 구간이다.

해저드는 카르노 맵에서 바로 보인다. $AB$와 $\overline{A}C$ 묶음은 $ABC$와 $\overline{A}BC$ 칸에서 서로 이웃하지만, 두 칸을 함께 덮는 묶음이 없다. 입력이 한 묶음에서 이웃 묶음으로 건너가는 순간, 출력을 1로 붙들어 주는 항이 잠깐 비는 것이다. 해결책은 그 경계를 덮는 묶음 $BC$를 하나 더 넣는 것이다. 논리적으로는 쓸모없는 항이지만(합의 정리에 의해 있으나 없으나 식은 같다), $B=C=1$인 동안 A와 상관없이 출력을 1로 잡아 준다.

$$AB+\overline{A}C = AB+\overline{A}C+\underbrace{BC}_{\text{합의항}}$$

합의항(Consensus term)은 $A$와 $\overline{A}$를 가진 두 항에서 그 변수를 지우고 나머지를 곱한 것이다. 2단 SOP 회로에서 모든 이웃한 1 쌍이 적어도 한 묶음에 함께 들어 있으면, 한 입력만 바뀔 때 정적-1 해저드가 없다.

반대 방향 전이

합의항이 없는 SOP 회로에서 A가 0→1로 올라갈 때(t=34)도 글리치가 생길까? 시뮬레이터를 보기 전에 두 항이 언제 켜지고 꺼지는지 따져 보자.

답 보기

생기지 않는다. A가 올라가면 $AB$는 AND 지연 뒤에 바로 켜지고, $\overline{A}C$는 인버터를 거쳐 늦게 꺼진다. 두 항이 겹치는 구간이 생길 뿐 비는 구간은 없다. 해저드는 "먼저 꺼지고 나중에 켜지는" 방향에서만 나타난다. 그래서 같은 회로라도 어느 쪽 전이에서 글리치가 나는지는 지연의 상대적 크기에 달려 있다. 인버터 지연을 0으로 줄여 보면 글리치가 사라지는 것도 확인할 수 있다.

동기 회로에서는 보통 괜찮다, 그러나

클럭에 맞춰 동작하는 동기 회로에서는 조합 논리 출력이 클럭 에지 전에만 안정되면 되므로, 중간의 글리치는 대개 문제가 되지 않는다(10장). 하지만 글리치가 클럭, 비동기 리셋, 래치의 인에이블로 들어가면 잘못된 에지가 생겨 회로 상태가 망가진다. 클럭 게이팅 셀이 래치를 품고 있는 이유다. 또 글리치는 쓸데없이 커패시턴스를 충방전하므로 전력을 낭비한다. 곱셈기처럼 경로 길이가 들쭉날쭉한 회로에서는 글리치 전력이 전체 동적 전력의 상당 부분을 차지하기도 한다(15장).

여러 입력이 동시에 바뀌거나, 다단 회로에서 같은 신호가 세 갈래 이상 다른 지연으로 재수렴하면, 출력이 0→1→0→1처럼 여러 번 흔들리는 동적 해저드(Dynamic hazard)도 생긴다. 이런 것까지 합의항으로 모두 막기는 어렵다. 그래서 디지털 설계의 큰 원칙이 "조합 논리의 글리치는 허용하되, 플립플롭이 클럭 에지에서만 값을 보게 한다"가 되었다.

2단 논리와 다단 논리

SOP와 POS는 입력에서 출력까지 게이트를 두 단만 지나는 2단 논리(Two-level logic)다. 단이 적으니 빠를 것 같지만, 항이 많아지면 게이트의 입력 수(팬인)가 커지고, 팬인이 큰 CMOS 게이트는 직렬 트랜지스터가 길어져 느리다. 게다가 어떤 함수는 2단으로 쓰면 지수적으로 커진다. 식을 공통 인수로 묶어(인수분해) 단을 더 쓰면 게이트 수와 배선이 크게 줄어드는 경우가 많다. 이것이 다단 논리(Multi-level logic)다.

게이트 수 (2단 → 다단)—

게이트 입력 합 (≈ 면적)—

논리 깊이—

최대 팬인—

그림 2-8. 해 보기같은 함수를 2단(위 또는 왼쪽)과 다단(아래 또는 오른쪽)으로 지은 두 회로를 비교한다. 입력을 바꿔 보면 두 출력은 언제나 같다. 처음 두 예는 인수분해로 게이트와 입력 수가 크게 줄면서 최대 팬인도 작아진다. 다수결 예는 반대다. $A(B+C)+BC$로 묶으면 게이트 입력은 조금 줄지만 깊이가 3단으로 늘어난다. 늘 이기는 쪽은 없다.

극단적인 예가 패리티다. $n$입력 패리티는 카르노 맵이 완전한 체크무늬라 어떤 두 1도 묶을 수 없으므로, 최소 SOP가 곧 정규형이다. 반면 XOR 트리로 지으면 게이트 $n-1$개, 깊이 $\lceil\log_2 n\rceil$이면 된다.

입력 수 n	최소 SOP 곱항 수 $2^{n-1}$	SOP 리터럴 수 $n2^{n-1}$	XOR2 트리 게이트 수	XOR 트리 깊이
2	2	4	1	1
4	8	32	3	2
8	128	1,024	7	3
16	32,768	524,288	15	4
64 (ECC 워드)	약 9.2 × 10¹⁸	약 5.9 × 10²⁰	63	6

그래서 실제 합성 도구는 2단 최소화로 시작하더라도 결국 공통 부분식을 뽑아 내고 인수분해해 다단 회로를 만든다. 그다음 무엇을 최적화할지는 목표에 달려 있다. 임계 경로에서는 깊이(지연)를 줄이려 논리를 펼치고, 나머지 경로에서는 면적과 전력을 줄이려 접는다. 게이트 하나의 지연이 팬인과 부하에 따라 어떻게 달라지는지 정량적으로 따지는 방법이 6장의 논리적 노력이고, AND-OR-INVERT 같은 복합 게이트로 2단 논리를 트랜지스터 한 단에 넣는 방법이 5장의 주제다.

깊이와 크기의 줄다리기

같은 덧셈도 리플 캐리 덧셈기(작고 깊다)와 Kogge–Stone 덧셈기(크고 얕다)로 지을 수 있다. 깊이 $O(n)$과 $O(\log n)$ 사이 어디에 설 것인가는 이 장의 2단·다단 비교를 큰 블록으로 옮긴 같은 질문이다(11장).

핵심 정리

$n$입력 불 함수는 $2^n$행 진리표로 완전히 정해지며, 가능한 함수는 $2^{2^n}$가지다. 기본 게이트는 NOT·AND·OR·NAND·NOR·XOR·XNOR이고 버블은 반전을 뜻한다.
불 대수 법칙은 쌍대 짝을 이룬다. 드모르간 정리는 "몸체를 AND↔OR로 바꾸고 버블을 반대쪽으로 민다"로 쓸 수 있고, 2단 NAND-NAND는 AND-OR와 같다.
SOP 정규형은 1인 행의 최소항 합, POS 정규형은 0인 행의 최대항 곱이다. 정규형은 정확하지만 크다.
카르노 맵은 그레이 코드 배열로 합칠 수 있는 최소항을 이웃 칸으로 보여 준다. 주항을 구하고 필수 주항부터 최소 피복을 고르는 과정을 표로 한 것이 Quine–McCluskey 방법이다.
NAND(또는 NOR) 하나로 모든 함수를 만들 수 있다. CMOS 게이트는 본래 반전하므로 NAND·NOR가 가장 싸고, pMOS가 약해 NAND를 더 선호한다. MUX와 LUT도 섀넌 전개로 임의의 함수를 만든다.
게이트 지연이 경로마다 다르면 정적·동적 해저드로 글리치가 생긴다. 카르노 맵에서 이웃한 묶음 사이를 덮는 합의항을 추가하면 정적 해저드가 사라진다.
2단 논리는 얕지만 팬인과 크기가 커질 수 있고, 다단 논리는 인수분해로 작아지지만 깊어질 수 있다. 패리티는 2단으로 지수적, XOR 트리로 선형이다.

확인 퀴즈

Q1. 3입력 NAND의 출력이 0이 되는 입력 조합은 몇 개인가?

NAND는 AND의 반전이다. AND가 1이 되는 경우는 모든 입력이 1인 한 가지뿐이므로 NAND가 0이 되는 경우도 그 한 가지다. 나머지 7개 조합에서는 1이다.

Q2. 드모르간 정리에 따라 $\overline{A+B+C}$와 같은 것은?

OR의 부정은 각 입력 부정의 AND다. 게이트로는 3입력 NOR가 입력에 버블을 단 3입력 AND와 같다는 뜻이다. $\overline{A}+\overline{B}+\overline{C}$는 $\overline{ABC}$, 즉 NAND3이다.

Q3. 4변수 카르노 맵에서 $m_1, m_3, m_9, m_{11}$이 1이고 나머지는 0이다. 최소 SOP는?

1=0001, 3=0011, 9=1001, 11=1011. 네 칸 모두 B=0, D=1이고 A와 C는 0·1이 섞여 있다. 맵에서는 맨 위 행과 맨 아래 행(가장자리로 이어진 행)의 가운데 두 열이 이루는 2×2 묶음이다. 따라서 $\overline{B}D$다.

Q4. FPGA의 6입력 LUT 하나에 필요한 설정 비트 수와, 그것으로 만들 수 있는 서로 다른 함수의 수는?

LUT는 진리표를 그대로 저장한다. 6입력이면 진리표 행이 $2^6=64$개이므로 설정 비트 64개, 각 비트를 자유롭게 고를 수 있으니 $2^{64}$가지 함수가 된다.

Q5. $Y=AB+\overline{A}C$를 2단 AND-OR로 구현했다. B=C=1인 채 A가 1→0으로 바뀔 때 생길 수 있는 글리치를 없애려면 어떤 항을 추가해야 하는가?

$AB$와 $\overline{A}C$의 합의항은 A를 지우고 나머지를 곱한 $BC$다. B=C=1이면 이 항이 A와 무관하게 1을 유지해, 두 항이 바뀌는 사이의 빈틈을 메운다. 합의 정리에 의해 함수 자체는 바뀌지 않는다.

Q6. 2단 논리와 다단 논리에 대한 설명으로 옳은 것은?

패리티의 카르노 맵은 체크무늬라 어떤 두 1도 묶이지 않으므로 $2^{7}=128$개 항이 최소다. XOR 트리는 $n-1$개, 깊이 $\lceil\log_2 n\rceil$이다. 2단 논리도 팬인이 커지면 느려지고, 인수분해는 크기를 줄이는 대신 깊이를 늘리기도 한다(다수결 예).

법칙	OR 형태	AND 형태 (쌍대)
항등	\(A+0=A\)	\(A\cdot 1=A\)
영(지배)	\(A+1=1\)	\(A\cdot 0=0\)
멱등	\(A+A=A\)	\(A\cdot A=A\)
보원	\(A+\overline{A}=1\)	\(A\cdot\overline{A}=0\)
이중 부정	\(\overline{\overline{A}}=A\)
교환	\(A+B=B+A\)	\(AB=BA\)
결합	\((A+B)+C=A+(B+C)\)	\((AB)C=A(BC)\)
분배	\(A+BC=(A+B)(A+C)\)	\(A(B+C)=AB+AC\)
흡수	\(A+AB=A\)	\(A(A+B)=A\)
결합(Combining)	\(AB+A\overline{B}=A\)	\((A+B)(A+\overline{B})=A\)
드모르간	\(\overline{A+B}=\overline{A}\,\overline{B}\)	\(\overline{AB}=\overline{A}+\overline{B}\)
합의	\(AB+\overline{A}C+BC=AB+\overline{A}C\)	\((A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)\)