[Karnaugh Map] n-variable

개요

Quine-McCluskey Method가 비교적 Karnaugh map에 비해 variable 수가 많을 때 더 유용하긴 하지만,
여전히 과정이 오래걸리는 것은 사실이다.
특히 term은 별로 없으면서 cover하는 minterm이 많은 경우에는 특히 더 오래걸리는 때가 있다.
이런 경우에는 Karnaugh map을 사용하는 편이 더 좋은데,
그것도 6-variable이 넘어가는 경우에는 사용하기가 어려웠다.
하지만 Karnaugh map을 약간만 발전시키면 이 문제를 해결할 수 있다.

예제

예를들어 6-variable의 function이 있다고 하자.
우리는 이를 4-variable Karnaugh map에 나타낼 생각이다.
어떤 6-variable function이 다음과 같이 정의된다고 하자.

여기서의 minterm으로 표시된 것들은 엄밀한 의미의 minterm이 아니라,
A, B, C, D 4개의 variable만 고려했을 경우의 minterm을 의미한다.
즉, G를 실제로 표현했을 때, A'B'C'D' + A'B'CD' + ... 를 의미하는 것이다.
실제로 6개의 variable의 minterm을 제대로 나타내면 E, F도 포함되어있어야 한다.
여기서는 4-variable Karnaugh map에 나타내기 편리하도록 위처럼 정리된 모양으로 주어진 것이다.
위 식은 설명을 위해서 주어진 것이고, 실제 적용에 대해서는 아래에서 추가적으로 설명하겠다.
설명을 이어가면, 이번엔 minterm에 각각 E와 F가 달려있는 것들을 볼 수 있다.
마지막 term은 don't care term들이다. 이제 이를 Karnaugh map에 나타내보면,

(a) 그림을 살펴보면 이제는 1, X 대신 E, F가 표 안에 들어있는 것을 볼 수 있다.
여기서 나타나는 E와 F는 가변적인 minterm으로 생각해야 한다.
이제 여기서 looping을 하기 위해서는 E와 F에 각각 0, 1을 임의로 넣는 방법을 사용하는데,
제일 먼저, E와 F가 0인 경우에 대해서 looping을 시도한다. 그것이 (b)의 그림이다.
다음 E를 1로 놓고 E이외의 나머지 모든 variable은 0으로 설정한다. (단, A,B,C,D는 제외)
그리고 E에 해당하는 minterm이외에 원래 1이었던 minterm들은 X로 바꾼다. 그것이 (c)의 그림이다.
그런 다음 looping을 한다.
마찬가지로 F에 대해서도 같은 방법으로 looping한다.

E, F에 대해서 각각의 looping의 결과는 위에 그림에서도 쓰여 있듯 A'D, AD가 되는데,
이것이 곧바로 term이 되는 것이 아니라, 앞의 E, F variable을 곱해줘야 하는 것을 잊지 말아야 한다.
다시 말해서 (c), (d) 그림에서 얻은 looping의 결과물은 각각 EA'D, FAD가 되는 것이다.
이렇게 해서 얻은 looping들을 모두 모으면 minimum solution이 된다.

G = A'B' + ACD + EA'D + FAD

최종적으로 위와 같은 식을 얻게 되는 셈이다.

일반화

이제 n-variable의 경우에 대해서 생각해보자.
n개의 variable 중 4개를 선택해서 나올 수 있는 조합은 16가지가 된다.
예를 들어, 4개가 만약 A, B, C, D 라면 A'B'C'D', A'B'C'D, ... , ABCD 의 16가지가 되는 것이다.

1. 각각의 조합에 대해서, 나머지 n-4개의 variable을 정리한다.
예를 들면, A'B'C'D'(1 + E + G + H) +  A'B'C'D(E + F) + ... 와 같은 식이다.
하지만 EG, GH와 같은 식으로 정리되어서는 안된다.
정리해서 나오게 된 모든 sum-of-products의 각 모든 term이 independent한 경우는 상관없다.
즉, EF, GH, IJKL 과 같이 겹치는 variable이 없거나, complement 관계가 아닌 경우에는 상관없지만
EG, GH와 같이 같은 variable을 공유한다든지 E, E'와 같이 complement 관계인 경우에는,
map 위에 표시할 수 없게 되므로, 이 방법을 사용할 수 없는 것이다.

2. 4개의 variable을 제외한 모든 variable을 0으로 간주하고 함수식을 쓴 다음,
　 그것을 Karnaugh map으로 나타낸다. 그리고 looping한다.
여기서의 예라면 E, F, G ... 의 variable을 모두 0으로 간주하고 식을 다시 쓴다.
그리고 그것에 대해서 Karnaugh map method를 적용하는 것이다.

3. 4개의 variable을 제외한 모든 variable에 대해서, 하나의 variable만 1으로, 나머지는 0으로 설정한다.
　 마찬가지로 Karnaugh map method를 적용하여 solution을 구한다.
여기서는 E만 1로 놓고, 나머지 F, G, H... 에 대해 0으로 간주한다음 반복한다.
단, 주의할 것은 1로 설정한 variable을 구한 solution에 곱해줘야 한다는 것이다.

4. 4개의 variable을 제외한 모든 variable에 대해서 3을 반복한다.

5. 이렇게 얻은 looping들을 조합해서 minimum solution을 완성한다.

n-variable에 대해서도 Karnaugh map method를 적용할 수 있지만,
완벽하게 모든 경우에 대해서 적용할 수 없다는 한계점이 있는 방법이다.