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

순서

다음은 multi-level NAND gate circuit을 만드는 과정이다.

1. circuit을 만들기 위해 function을 simpify한다.
2. 1번의 결과로부터 AND와 OR gate로 된 circuit을 만든다. 단 output은 OR gate여야 한다.
3. 2번에서는 AND와 OR가 항상 번갈아 나와야 하고, 같은 종류의 gate가 연달아 나와서는 안된다.
4. 일단 모든 gate를 NAND로 바꾸고, 연결선은 그대로 둔다.
5. output gate를 level 1이라고 했을 때 홀수 level의 gate에 들어가는 literal을 invert해준다. 

이러한 과정을 통해 정말로 multi-level NAND gate circuit이 성립되는지 살펴보려면,
2-level씩 끊어서 이전 포스트에서 설명한 내용을 적용해 보면 된다.

한편 mulit-level NOR gate circuit의 경우에는 위의 방법과 거의 같으며, 
위 방법에서 언급된 OR 대신 AND를, NAND 대신 NOR로 바꿔서 그대로 수행하면 된다.

예제

다음 식에 대해서 AND-OR circuit과 NAND-NAND circuit을 구현하라.

이 예제에서는 F'가 이미 정리된 상태이지만, 그렇지 않은 경우에 대해서는 최대한 정리하도록 한다.

(a)에서는 AND-OR를 이용해 circuit을 구성했다.
Connection 자체의 모양은 바꾸지 않고, gate를 모조리 NAND로 바꾸고,
파란색으로 음영이 된 짝수번째 level의 gate에 들어가는 literal들은 그대로 두고,
이외의 gate의 input으로 사용되는 literal들은 각각 그의 complement가 들어가는 것을 볼 수 있다.
이러한 방법으로 multi-level NAND circuit을 완성할 수 있다.