[Multi-Level Gates] NAND and NOR Gates

개요

지금까지는 AND, OR gate, inverter만 가지고 digitatl logic design을 했다.
여기서는 NAND와 NOR gate에 대해서 소개하고자 한다.
Logic designer는 NAND와 NOR gate를 주로 사용하는데,
일반적으로 속도가 빠르고 AND, OR gate를 쓰는 것에 비해 gate를 적게 쓸 수 있기 때문이다.
게다가. NAND gate로만, 혹은 NOR gate로만 회로를 구성하는 것이 가능하다.
(이것은 이후의 포스트에서 설명한다.)

NAND Gate

Bubble이라고 부르는 작은 동그라미가 gate의 output단에 붙어있다. 
NAND gate는 AND-NOT gate라고 생각하면 된다. (a)와 (b)는 동일한 결과를 갖는다.
살펴보면, AND operation을 한 다음, inverter를 통과한 꼴이라고 할 수 있다.
(a) 또는 (b)의 F를 A, B, C로 나타내면,

F = (ABC)' = A' + B' + C'

n개의 input이 있는 NAND gate라면, input의 complement를 모두 더한 결과가 F에서 나오게 된다.

NOR Gate

NOR gate에서도 마찬가지로 OR gate의 output단에 bubble이 붙어있다.
마찬가지로 NOR gate는 OR-NOT gate라고 생각하면 된다.
(a), (b)는 동일한 결과를 나타내고, F를 A, B, C로 표현하면

F = (A + B + C)' = A'B'C'

가 된다.

Functionally Complete

어떤 logic operation의 집합으로 모든 Boolean function을 서술할 수 있으면,
그것을 functionally complete하다고 한다.
예를 들면, AND, OR, NOT은 확실히 functionally complete라고 할 수 있다. 
Functionally complete한 function은 gate로 만들어 낼 수 있다.
따라서, AND, OR, NOR을 구현한 logic gate의 집합도 역시 functionally complete라고 할 수 있다.
그런데, AND와 NOT만 가지고도 functionally complete가 가능하다.

OR gate를 NOT과 AND gate를 이용해서 구현할 수 있기 때문이다.  (물론 Boolean algebra 상으로도 그렇다.)

만약 어떤 gate가 단독으로 functionally complete하다면,
모든 functionally complete한 gate의 집합은 이 '어떤 gate'로 치환할 수 있게 된다.
NAND gate가 바로 그러한 gate라고 할 수 있다.

위 그림을 보면 NAND gate만 이용해서 NOT, AND, OR gate를 각각 구현한 것을 볼 수 있다.
이후의 포스트에서 AND-OR circuit을 NAND circuit으로 바꾸는 방법에 대해 다룰 예정이다.
한편, NOR gate 역시 같은 성질을 갖고 있다.