[Karnaugh Map] 4-variable

Location of Minterms on Karnaugh Map

Variable이 4개인 경우에는 보통 정사각형 모양으로 Karnaugh Map을 그리기 위해
variable을 두 개씩 나누어 행과 열에 배치한다.
3-variable에서와 같이 여기서도 행과 열을 각각 00, 01, 11, 10으로 배치했다.
그 결과 각 칸의 decimal notation은 위와 같게 된다.
예를 들어 14인 칸에 대해서, 14는 2진수로 1110 으로 표현되므로, A=1, B=1, C=1, D=0 인 칸임을 알 수 있다.
이외에 특기할 만한 사항이 없으므로 곧바로 예제를 살펴보도록 하자.

Getting Minimum Expression

다음을 Karnaugh map에 그리고 minimum expression인지 확인하라.

f(a,b,c,d) = acd + a'b + d'

위 식을 Karnaugh map으로 그려보면 아래와 같다.

그림에 표시된것을 보면 알 수 있듯이, acd, a'b, d'에 해당하는 1은 위와 같이 표시할 수 있다.
1을 어떻게 배치할 것인가를 차근차근 설명해 보면,

(a)
먼저 'acd'라는 term은 a=1, c=1, d=1 이어야 하고, b = 0 or 1 이어야 한다.
쉽게 이야기 하면, acd에 포함되지 않은 variable은 0, 1을 모두 포함하고 있어야 하고, 
포함된 variable은 1이어야 한다. 따라서 위 그림처럼 15번과 11번칸에 1을 넣어야 한다.

(b)
마찬가지로 생각하면, a'b는 a=0, b=1이어야 하고, 나머지는 0 또는 1이면 된다.
위 그림에서는 위아래로 길게 뻗은 loop에 해당한다.

(c)
d' 는 d=0 에 해당하는 모든 칸에 1을 넣어야 한다.
cd중 d=0인 행은 00, 10이다. 이 행 전체에 1을 넣으면 된다.
3-variable의 예제에서도 볼 수 있듯이, 인접한 것 같이 보이지는 않지만,
실제로는 인접해 있고, 위와 같이 looping을 할 수 있다.

Minimum expression을 위한 가장 중요한 2가지는 다음과 같다.
1. Looping을 최대한 크게 한다.
2. Loop의 개수를 최소화한다.

Looping의 가장 작은 단위는 두 개의 1을 묶는 것이다.
하지만 looping이 작을 수록 expression에 필요한 variable은 많다.
4-variable의 경우에는 3개의 variable이 필요하다.
위에서 봤던 d'는 8개의 1을 묶었고, 이는 단지 1개의 variable로 표현되는 것이다.
따라서 우리는 항상 looping에 가능한 많은 1을 넣어야 한다.

다음으로 loop의 개수는 가능한한 작게 해야 한다.
Loop가 많을 수록 term의 갯수가 많아진다.
이는 곧 OR operation이 많아짐을 뜻한다. 따라서 줄일 수 있을만큼 많이 줄이는 것이 좋다.

이제 위의 예제를 다시 살펴보자.
잘 보면 acd의 loop의 아래에 있는 두개의 1로 확장시킬 수 있다.
이러한 방법으로 loop를 가능한 크게 만들어 줄 필요가 있다.
그러면 acd 대신 'ac'라는 term을 얻을 수 있다. 

이 이상으로 minimum expression을 얻는것이 불가능하므로,
최종적으로는 f = ac + a'b + d' 를 얻는다. 

Some Examples

(a)
Looping이 불가능한 예제를 보여주고 있다.
오른쪽 아래의 1은 looping을 할 수 있는 인접한 1을 찾을 수 없다.
이런 경우는 looping을 하지 않은 채로 두면 되고, 이러한 term은 그냥 그대로 써주면 된다.
이 예제에서는 ab'cd'에 해당한다.

(b)
b'd'라는 term은 각각의 corner의 1을 looping하고 있다.
4-variable에서의 adjacency는 행, 열을 가리지 않기 때문에, 위와 같은 looping이 가능하다.
이를 잊고 한쪽 방향에서의 adjacency만 고려하면 위쪽의 두개의 1만 looping하게 될 수 있는데,
그렇게 되면 minimum expression을 얻을 수 없다.

Karnaugh Map with 'Don't Cares'

Karnaugh map은 don't care를 처리할 때에도 상당히 유용하게 사용할 수 있다.
Don't care를 잘 활용하면 expression을 상당히 줄일 수도 있지만,
이전의 예제에서는 각각의 경우를 모두 따져 하나하나 비교해가면서 하는 방법 뿐이었다.
그렇다면 Karnaugh map에서는 어떠한가?
고민할 것 없이 X를 곧바로 해당 위치에 써 넣는다.
그런 다음 X가 1이 되면 minimum expression이 될 만 하다 싶으면 X를 1로 생각하고 looping하면 된다.
term이 늘어난다든지, 각 term의 variable의 개수를 줄일 가능성이 없는 X는 그냥 0으로 생각하면 된다.
위 예제에서는 13번 칸에 해당하는 X를 1로 고려함으로써 c'd라는 term을 완성했다. 
만약 이를 제대로 고려하지 않으면, 9번과 1번을 adjacency로 보고 b'c'd를 건져낼 수 밖에 없다.

Find a Minimum Product-of-sums

이전 포스트에서도 잠깐 언급했듯이 0을 묶는 방법도 물론 가능하다.
이 경우에는 우리가 일반적으로 얻던 sum-of-products 형태의 expression이 아닌 product-of-sums를 얻게 된다. 
위 Karnaugh map을 잘 살펴보면 알 수 있듯이 1을 묶게 되면 4개의 term이 나오게 된다.
정리해보면 f = x'z' + wyz + w'y'z' + x'y 이다.

0을 묶는 방법으로 f를 구하기 위해서 0을 묶은 모습은 위 그림이 된다.
만약 1을 묶었다면 위 그림에서 얻을 수 있는 term은 각각 y'z, wxz', w'xy 이다.
하지만 우리는 0을 묶었기 때문에 이를 product-of-sums로 생각해야 한다.
즉 각각의 term의 complement를 구해야 한다.
따라서 각각은 (y'z)' = (y + z'), (wxz')' = (w' + x' + z), (w'xy)' = (w + x' + y') 가 된다. 

최종적으로 f = (y + z')(w' + x' + z)(w + x' + y') 이다.
Sum-of-products로 나타낸 f는 OR operation이 3번, AND operation이 6번 사용된 반면
product-of-sums로 나타낸 f는 OR operation이 5번, AND operation이 2번 사용되었다.
실제 회로를 구현한다고 가정한다면 product-of-sums로 나타낸 f를 구현하는 편이 효율적이라고 할 수 있다.