6 / 63 · 개념

범용 게이트: NAND만으로 회로 만들기

NAND·NOR의 기능적 완전성을 구성으로 보이고 XOR의 중간 신호를 검증합니다.

“모든 회로”라는 말의 범위

NAND만으로 NOT·AND·OR를 만들 수 있고, 유한한 입력을 갖는 임의의 조합 논리 함수는 이 연산들로 표현할 수 있습니다. 이런 의미에서 NAND는 범용 게이트^{범용 게이트 한 종류의 게이트만 반복해서 임의의 불 함수를 만들 수 있을 때 그 게이트를 범용 게이트라고 합니다. NAND와 NOR가 대표적입니다.}입니다. 저장·클록·배선·전력 조건까지 NAND 하나가 해결한다는 뜻은 아닙니다.

\overline a=\operatorname{NAND}(a,a)

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

같은 입력을 NAND의 두 단자에 연결하면 NOT이 됩니다. AND는 NAND 뒤에서 한 번 더 반전^{부정 0을 1로, 1을 0으로 바꾸는 NOT 연산입니다. 수식 위의 선은 선 아래 식 전체에 NOT을 적용한다는 뜻입니다. 자세히 보기}하고, OR는 드모르간^{드모르간 AND 결과를 반전한 것은 각 입력을 반전한 OR과 같고, OR 결과를 반전한 것은 각 입력을 반전한 AND와 같습니다. 자세히 보기} 법칙을 적용합니다. NOR도 입력을 묶어 NOT을 만들 수 있으며 비슷한 구성으로 범용성을 보일 수 있습니다.

NAND 네 개로 XOR 구성하기

중간 신호를 다음 순서로 정의합니다.

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

공유 중간 신호로 XOR 만들기

첫 NAND: n0 = NAND(a, b)
중간 NAND 두 개: n1 = NAND(a, n0); n2 = NAND(b, n0)
마지막 NAND: y = NAND(n1, n2)

두 번째 단계의 NAND 두 개는 병렬입니다. 총 게이트 수는 4개지만 가장 긴 논리 경로는 3단계입니다. 각 게이트가 최대 2 ns인 단순 모델이면 최대 경로 합은 6 ns입니다. 실제 부하와 배선에 따라 달라지는 것은 별도로 고려합니다.

구성한 네 NAND의 결과를 XOR와 대조하기

XOR · 진리표
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

표의 네 행을 직접 채운 뒤 위 XOR와 비교하세요. 기능 등가는 모든 입력의 출력을 비교한 주장이고, 게이트 수나 전파 지연^{전파 지연 입력이 바뀐 뒤 출력이 올바른 값으로 안정되기까지 걸리는 시간입니다. 논리식의 등가성과 시간 특성은 별개입니다. 자세히 보기}이 같다는 주장이 아닙니다.

직접 생각해 보기

NOR만으로 NOT과 AND를 만드는 식을 쓰세요. AND 구성의 게이트 수와 가장 긴 단계 수는 각각 얼마인가요?

해설 보기

NOT a=NOR(a,a)입니다. AND는 NOR(NOR(a,a), NOR(b,b))입니다. 입력 반전 두 개와 마지막 NOR 한 개로 총 3개, 가장 긴 경로는 2단계입니다.