Universal gate란?
Boolean expression을 구현하는 기본 gate는 대표적으로 NOT, AND, OR이 있다. 이 세 가지 게이트로 모든 boolean expression을 구현할 수 있다. Universal gate는 한 종류만으로 모든 boolean expression을 구현할 수 있는 게이트를 말한다. (2-input) NAND, NOR, MUX 등이 있다.
기본 컨셉은 다음과 같다.
하나의 게이트로 NOT, AND, OR을 모두 만들 수 있다면, 모든 boolean expression을 만들 수 있다. 즉 universal gate이다.
증명
Boolean Expression으로 구현해보자. 2 개의 입력 X, Y에 대한 출력 Z는 다음과 같다. 식의 꼴에 익숙해져야 한다.
- NOT 연산 Z = ~X
- AND 연산 Z = X • Y
- OR 연산 Z = X + Y
- NAND 연산 Z = ~(X • Y)
- NOR 연산 Z = ~(X + Y)
NOT, AND, OR의 식을 변형해서 NAND와 NOR의 꼴로 바꿔주면 결국 NAND와 NOR로 모든 논리가 구현이 가능하다는 의미이다. 아래의 방법들만 알아도 모든 논리회로는 NAND 혹은 NOR만으로 이루어진 회로로 바꿀 수 있다.
NAND로 NOT 구현
Z = ~X = ~(X • X)
NAND 양쪽에 모두 X를 넣으면 ~X가 출력된다.
NAND로 AND 구현
Z = X • Y = ~[~( X • Y )]
AND의 식에 NOT 두 번을 해주면 NAND + NOT이 된다.
NAND로 OR 구현
Z = X + Y = ~(~X • ~Y)
드모르강의 법칙을 이용한다. 각 입력을 NOT 해주고 NAND에 집어넣는다.
NOR로 NOT 구현
Z = ~X = ~(X+X)
NOR 양쪽에 모두 X를 넣으면 ~X가 출력된다.
NOR로 AND 구현
Z = X • Y = ~( ~X + ~Y )
드모르강의 법칙을 이용한다.
NOR로 OR 구현
Z = X + Y = ~[ ~( X + Y ) ]
OR 연산에 NOT을 두 번 적용한다.
회로도에서 쉽게 변환하기
회로도에서 곧바로 게이트를 변환하는 방법을 알아보자. 다음의 두 가지만 잘 알면 된다. 잘 보면 알겠지만 드모르강의 법칙을 게이트로 구현한 것이다. 게이트 종류를 바꾸고 앞, 뒤에 버블을 달아준다.
예시 문제를 풀어보자. Z = A + B•C + D•E•(~F) 의 논리회로이다. NAND 만으로 구현할 것이다.
우선 OR 게이트를 드모르강 법칙을 통해 NAND로 바꿔주자.
NAND의 입력단에 붙은 버블을 이전 게이트의 출력단에 붙인다.
AND3B1의 버블은 inverter로 따로 분리시킨다.
이처럼 임의의 로직 회로를 NAND 만으로 표현할 수 있다. 이제 더 나아가서 모든 게이트를 2-input NAND로 바꿔보자. 위의 그림에서는 가장 아래쪽의 NAND가 3-input이기 때문에 2-input으로 바꿔야 한다.
3-input 게이트를 2-input 게이트로 변환
위의 내용만 알아도 모든 논리회로를 NAND, NOR로 변환할 수 있다고 했다. 이제는 특히 입력이 2개인 NAND, NOR 게이트만 사용해서 모든 논리회로를 변환해보자.
3-input AND를 2-input NOR로 표현
Z = A • B • C = ~( ~A + ~B ) • C = ~[( ~A + ~B ) + ~C] = ~[~{ ~( ~A + ~B ) } + ~C]
드모르강 법칙을 자유자재로 구사할 수 있어야 한다. 식만 보고는 쉽게 알기 어렵지만 잘 살펴보면 아래의 3단 구조로 이루어진 것을 알 수 있다.
이를 논리회로로 그려보면 다음과 같다.
3-input AND를 2-input NAND로 표현
Z = A • B • C = ~{~( A • B )} • C = ~[~{ ~( A • B ) • C }]
3-input NAND를 2-input NAND로 표현
Z = ~(A • B • C) = ~[~{~(A • B)} • C ]
3-input NAND gate를 2-input NAND gate의 조합으로 바꿀 수 있으므로 input이 아무리 많아도 모두 2-input NAND gate의 조합으로 바꿀 수 있다. NOR도 마찬가지이다.
위의 예시 문제에서 가장 아래쪽의 3-input NAND를 2-input NAND로 분리시키면 최종적으로 아래와 같이 된다.
