2012. 3. 1. 00:57
개요
Input과 output 사이에 직렬로 연결되는 gate의 최대 개수는 gate의 level의 개수에 따른다.
따라서, sum-of-products 또는 product-of-sums의 형태로 되어있는 function은 곧,
2-level gate circuit로 귀결된다.
일반적으로, gate가 flip-flop output으로 부터 나오는 case에서는
모든 variable과 그의 complement는 circuit input으로 사용할 수 있다. (flip-flop은 이후에 다루게 됨)
이러한 이유 때문에, inverter는 보통 level로 카운트 하지 않는다.
앞으로는 다음의 용어를 사용할 것이다.
1. AND-OR circuit
AND gate가 OR gate 다음에 이어지는
2-level circuit
(AND gate가 input과, OR gate가 output과 연결되어있음)
2. OR-AND circuit
OR gate가 AND gate 다음에 이어지는 2-level circuit
(OR gate가 input과, AND gate가 output과 연결되어있음)
3. OR-AND-OR circuit
두 개의 OR gate level 사이에 AND gate level이 끼어있는 3-level circuit
4. AND gate와 OR gate로 이루어진 circuit은 gate에 특별한 순서가 없음
AND-OR circuit의 level의 숫자는 보통 sum-of-products을 factoring(인수분해)할 수록 많아지고,
OR-AND circuit의 level의 숫자는 product-of-sums를 multiplying out(전개)할 수록 많아진다.
Gate level의 개수는 logic designer에게 중요한데, level이 증가할 수록 일반적으로 gate를 덜 사용할 수 있다.
그러나 level이 많아지면 그만큼 delay가 생기게 된다.
Gate의 숫자와 gate의 input과, circuit level은 expression을 살펴봄으로써 곧바로 파악할 수 있다.
예제
어떤 expression이 주어졌을 때, 괄호 안에서부터 차례로 gate를 만들어가나면 된다.
앞서 언급했듯이 gate의 숫자, gate input의 숫자, level의 숫자를 파악해 보면,
여기서는 6개의 gate, 13개의 gate input, 4개의 level로 되어있는 것을 볼 수 있다.
Gate input은 밖으로 튀어나와있는 variable만 체크하는 것이 아니라,
각 gate를 개별적으로 보고 input의 개수를 모두 파악해야 한다.
한편, 동일한 식을 multiplying out 하는 방법으로 circuit을 변형할 수 있다.
중복되는 gate (D + E)를 사용해서 3-level로 circuit을 구현한 모습이다.
Gate의 개수는 6개로 동일하지만, gate input의 개수가 상당히 많아졌다. (19개)
적용
이제 실제 expression을 이용해서
AND-OR circuit, OR-AND-OR circuit, OR-AND circuit, AND-OR-AND circuit을 구현해보자.
위와 같이 주어졌을 때, 먼저 f에 대한 Karnaugh map을 그려서 sum-of-products 형태로 정리한다.
위 그림에서는 1로도 looping을 하고 0으로도 looping을 했는데,
각각을 따로 생각하도록 한다. 0으로 looping한 것은 product-of-sums의 형태를 위해서 만들어 놓은 것이다.
자세한 것은 이후에 설명하도록 하고, 1을 looping한 것으로부터 f를 구했다.
이를 곧바로 AND-OR circuit으로 그려볼 수 있다.
여기서 factoring을 함으로써, f = c'd(a' + b) + cd'(a + b) 를 만들수 있고,
이것으로 곧바로 OR-AND-OR circuit을 그릴 수 있다.
한편, AND gate를 output에 위치시키는 방법, 즉 OR-AND circuit을 이용함으로써,
gate의 숫자를 줄이거나 gate input을 줄일 수 있다.
그러기 위해서는 위에서 0의 looping을 통해
를 얻고 여기에 DeMorgan's law를 적용하면,
를 얻는다. 이는 곧바로 OR-AND circuit realization이 가능하다.
여기서 AND gate의 3-level circuit을 얻으려면 (X + Y)(X + Z) = X + YZ를 이용하여
를 얻고, 이로써 AND-OR-AND circuit을 만들 수 있다.
이 예제에서는 가장 좋은 2-level circuit은 OR-AND circuit,
가장 좋은 3-level circuit은 OR-AND-OR circuit으로 나타났다.
일반적으로 minimum solution을 얻기 위해서는
AND gate output의 circuit과 OR gate output의 diagram을 둘 다 그려보는 수밖에 없다.
한편 만약 f'가 n개의 level으로 이루어져 있다면, f역시 n개의 level으로 이루어져 있게 된다.
따라서, f를 n-level의 AND gate output의 circuit으로 만들고 싶으면,
한가지 방법으로, n-level의 OR operation이 output level에 있는 expression을 구해서
DeMorgan's law를 사용하면 된다.