[Multi-Level Gates] Design of 2-Level Circuits Using NAND and NOR Gates

AND-OR Forms

 
AND-OR circuit는 3가지의 form으로 변환이 가능하다.
Function은 sum-of-products 형태여야 한다.
먼저 기본적으로 F = A + BC' + B'CD 가 주어졌다고 하자.
이 식은 기본적으로 DeMorgan's law를 이용해서 나머지 3가지로 변환이 가능하다.

이러한 식은 곧바로, 위 그림과 같이 구현이 가능하다.
AND-OR으로 부터 NAND-NAND, OR-NAND, NOR-OR 꼴로 변형되었다. 
잘 살펴보면 알 수 있듯이, 기본적으로 gate나 gate input의 위치는 그대로지만,
gate input은 complement가 들어가기도 하고, gate의 종류도 바뀐다.
어찌됐든, 4가지 모두로 결국 같은 function이 구현된다.

OR-AND Forms

OR-AND circuit 역시 3가지의 다른 form으로 변환이 가능하다.
마찬가지로 F를 DeMorgan's law를 이용해 열심히 가지고 놀다보면 된다.
기본적으로 F는 product-of-sums 형태여야 한다.
Function은 F = (A + B + C)(A + B' + C')(A + C' + D) 와 같이 주어졌다고 할 때,

와 같이 변환된다.

NAND-NOR Case

물론 위의 8가지 form 이외에도 존재할 수 있는 case가 있다.
다음을 살펴보자.

NAND-NOR circuit을 이용해 literal의 곱을 나타냈다.
바꾸어 말하면, 위의 8가지 이외의 form으로는
일반적인 sum-of-products나 product-of-sums의 function을 나타낼 수 없다는 뜻이다.

Designing a Minimum 2-level NAND-NAND Circuit

NAND와 NOR gate는 집적회로 구성에 즉각 사용될 수 있어 가장 일반적으로 사용된다.
모든 variable과 그의 complement를 input으로 이용할 수 있다고 가정했을 때,
어떤 function F를 NAND gate로 구성하는 순서는 다음과 같다.

1. F에 대한 minimum sum-of-products를 구한다.
2. AND-OR circuit을 구성한다.
3. 모든 gate를 NAND gate로 바꾸고, 나머지는 그대로 둔다.
　 단 output gate에 다른 literal이 낑겨 들어가는 경우에는 complement를 넣어준다.

위 순서를 그림으로 나타내면,

Gate가 모두 NAND gate로 바뀌었으며, 왼쪽의 gate input은 변화가 없지만 오른쪽의 gate input,
즉, output gate의 input인 l_1, l_2 등은 complement로 바뀌어 있는 것을 볼 수 있다.

Designing a Minimum 2-level NOR-NOR Circuit 

NOR gate역시 NAND gate와 마찬가지로 다음과 같은 순서를 통해 NOR-NOR circuit을 얻을 수 있다.

1. F에 대한 minimum product-of-sums를 구한다.
2. OR-AND circuit을 구성한다.
3. 모든 gate를 NOR gate로 바꾸고, 나머지는 그대로 둔다.
　 단 output gate에 다른 literal이 낑겨 들어가는 경우에는 complement를 넣어준다.

NAND-NAND circuit 구성과 거의 흡사하다.