메뉴
[Multi-Level Gates] Design of 2-Level, Multi-Output Circuits

2012. 3. 6. 01:45

필요성

여러개의 함수를 동일한 variable을 이용해서 나타내고자 하는 경우,
circuit은 제각각 구현하더라도, gate를 중복해서 사용하면 좀 더 효율적일 것이다. 

4개의 input과 3개의 output이 있는 다음 함수를 circuit으로 구현해 보자.


먼저 각 함수를 구현하기 위해서 Karnaugh map을 그린다.


각 함수는 위와 같이 looping할 수 있다. 이를 이용해서 circuit을 구현하면,


위와 같이 그릴 수 있다. 위와 같이 하면 9개의 gate와 21개의 input이 필요하다.
이제 이 circuit을 좀 더 간단히 하고자 한다.
먼저, circuit을 바로 바라봤을 때, 'AB'를 만드는 AND gate가 중복되어 있는 것을 볼 수 있다.
따라서 둘 중 하나를 없애고 없앤 쪽의 connection을 남은 하나의 'AB'와 연결하면
1개의 gate와 2개의 input이 줄어들게 된다.

한편, ACD와 A'CD의 gate를 통해서 CD = ACD + A'CD 를 구현할 수 있다. 따라서
CD 역시 제거가 가능하다.


최종적으로 위와 같이 circuit의 규모를 줄였다. 7개의 gate와 18개의 input이 사용되었다.
F_2는 ABC' + A'CD + ACD로 구현되어, minimum sum-of-products 라고 할 수 없다.
A'CD, ACD는 F_2에서 prime implicant라고 할 수 없다.
바꾸어 말하면, multiple-output circuit을 구현하는데 있어서
prime implicant를 구하고 minimum solution을 구하는 것은 큰 의미가 없다.
하지만, 위의 경우와 마찬가지로, gate의 숫자를 줄이는 것은 필요하다.



Directly Using Karnaugh Map

Karnaugh map이 아래와 같이 그려지는 함수 f_1, f_2, f_3이 있다고 하자.


먼저 각 Karnaugh map에 대해서 원래 하던대로 looping을 해 볼 수 있을 것이다.
하지만 map을 살펴보면 이것이 가장 좋은 solution이 아니라는 것을 알 수 있다.
먼저 f_2에 있는 a'bd, f_3에 있는 abd, ab'c'는 f_1에도 존재한다.
abd와 a'bd를 이용해서 우리는 f_1의 ad를 만들 수 있다. 
또한 f_1에서, 중복되는 ab'c'를 택하면, ab'를 제거해도 된다.
따라서 minimal solution는 다음과 같이 쓸 수 있다.


중복되는 gate는 밑줄로 표시했다.
Multiple-output circuit에 대해서는 Karnaugh map의 best solution이
항상 전체의 minimal solution이 되지는 않는다는 것을 다시 한 번 강조한다.



Determination of Essential Prime Implicants for Multiple-Output Realization

Minimum 2-level multiple-output circuit을 구현하기 위한 첫번째 단계로
essential prime implicant를 구하는 것이 요구된다. 
하지만 어떤 함수에서는 essential prime implicant인 것이 다른 함수에서는 그렇지 않을 수도 있다.
바로 이전 예제에서 f_1에 bd는 f_1에서는 essential prime implicant이지만, 다른 함수에서는 그렇지 않다.
그 이유는 f_1에서 essential prime implicant를 구성했던 minterm들 중 하나가
다른 함수의 일부에서 동시에 존재하기 때문이다.


위 그림을 살펴보자. (b)를 보면, f_1은 c'd + abd 로 이루어져 있다.
c'd는 f_1에 대해 essential 하다. f_2를 살펴보면 c'd에 해당하는 minterm들은 존재하지 않는다.
그러나 abd를 보면, 15번의 minterm이 f_2에, 다른 모양으로 looping되어있다.
따라서 abd는 essential하다고 할 수 없다.

다른 예제를 살펴보자.


f_1에서 2번과 5번의 minterm은 f_2에서 존재하지 않는다.
2번의 minterm을 cover할 수 있는 prime implicant는 a'd'이므로,
a'd'는 essential prime implicant가 된다. 
마찬가지 방법으로 5번의 minterm을 cover할 수 있는 prime implicant는 a'bc'이므로,
이 역시 essential prime implicant가 된다. 

이제 f_2를 기준으로 살펴보자. 1번과 12번의 minterm은 f_1에서 존재하지 않는다.
따라서, 이들을 포함하는 looping 역시 essential prime implicant가 되는 것이다.
결론적으로는 (b)와 같은 best solution을 얻게 되는 것이다.

정리하면, 어떤 함수에 있는 minterm이 다른 모든 함수에서 존재하지 않는 경우
이 minterm을 포함하는 prime implicant는 essential prime implicant라고 할 수 있다.
물론, 반드시 circuit으로 구현될 필요가 있다.
이러한 essential들을 먼저 구한 다음에 나머지에 대해서 정리하면 된다.