[Karnaugh Map] 5-variable
2012. 2. 19. 03:47
형태
5-variable Karnaugh map은 3차원 공간을 생각해야 한다.
왼쪽 그림을 보면, 4-variable Karnaugh map을 3차원 공간에서 위 아래로 펼쳐놓은 형태로
위에는 A=1, 아래는 A=0에 해당한다. 바로 위, 또는 아래의 A는 서로 인접한 것으로 생각한다.
따라서 왼쪽 그림과 같이 위 아래를 looping하는 것이 가능하다.
실제 5-variable Karnaugh map을 위와 같이 3차원으로 그릴 필요는 없고,
오른쪽 그림과 같이 중간에 사선을 그린 형태로 그리면 된다.
오른쪽 그림의 왼쪽을 보면 A 1/0 이라고 되어있는 것을 볼 수 있다.
즉, 사선의 왼쪽은 A=1, 오른쪽은 A=0에 해당하는 칸을 나타낸다.
사선 왼쪽과 오른쪽의 각 16개 칸은 layer 라고 부른다.
Looping
각 case에 대해서 차례로 설명해보면,
먼저 위의 0번과 20번의 minterm을 보자.
그림 상으로는 가까이 위치한것처럼 보이지만 위에서도 설명했듯이
하나는 A=1, 다른 하나는 A=0에 위치해 있으며 각 층에서 같은 위치에 있지 않다.
다시 말해서 0번은 BC=00, 20번은 BC=01에 있기 때문에, 두 개의 variable이 동시에 다른 값을 갖는다.
따라서 두 개의 1은 서로 looping이 불가능하다.
다음 오른쪽의 8개의 1의 loop의 모양은 육면체로 그려져 있는데,
굳이 육면체로 그릴 필요는 없으며, 여기서는 3차원으로 생각하는 것을 돕기 위해 그려 놓은 것으로 생각하면 된다.
이제 육면체가 어떤 term을 나타내는지 살펴 보면,
먼저 사선 왼쪽과 오른쪽을 모두 포함하므로 A는 term에 포함되지 않는다.
그러면 BCDE에서만 생각하면 되고, 이는 곧 4-variable에서와 같다.
공통적으로 B=1, D=0을 갖고 있고, 나머지는 모두 complement를 가지므로,
얻을 수 있는 term은 BD'가 된다.
중간의 4개의 1을 포함하는 loop 역시 두 개의 layer를 동시에 포함하고 있다.
따라서 a에 대해서는 고려해줄 필요가 없고, 나머지는 4-variable에서와 같이 처리하면된다.
마지막으로 맨 아래의 두개의 1을 포함하는 loop는
위의 layer인 A=1에만 포함하므로 term에는 'A'가 포함될 것이다.
마찬가지로 A를 결정한 다음에는 4-variable에서와 같이 처리하면 된다.
즉, 두 개의 layer로 나누어진 variable에 대해 먼저 고려하고 나서, 각 layer를 판단하면 된다.
Essential Prime Implicants
위 Karnaugh map은 아래의 식에 따라 1을 그려놓은 다음 looping을 한 것이다.
파란색 바탕으로 된 칸은 essential prime implicant들을 나타낸 것이다.
16번 minterm과 인접해있는 것을 looping한 것은 P_1로 나타낼 수 있다. 따라서 P_1을 먼저 선택한다.
16번 minterm은 이 이외에 다른 looping에 속할 수 없기 때문에 essential prime implicant가 된다.
이는 곧 P_1은 반드시 F를 나타내는데 쓰이는 term일 수 밖에 없다는 뜻이다.
잘 이해가 안가면 이전의 포스트를 살펴보기 바란다. (참고: http://blastic.tistory.com/195)
이제 P_1에 포함되지 않은 다른 1들을 살펴보자. 3번 minterm 역시 P_2에 속해야만 한다.
마찬가지로 8번 minterm도 P_3에 속해야 하고, 14번 minterm도 P_4에 속해야만 한다.
그렇지 않은 다른 solution이 존재하질 않는다.
이제 마지막으로 3개의 1이 남게된다. 이들이 essential prime implicant가 될 수 없는 이유는 간단하다.
31번의 minterm은 15번의 minterm과 looping이 될수도 있고, 27번과 looping될수도 있다.
27번의 minterm은 25번, 31번 둘 중 하나와 각각 looping이 가능하다.
25번은 9번, 27번과 각각 looping이 된다.
위 예제에는 P_5와 같이 27번과 31번을 묶고, 남은 25번에 대해서 9번 또는 27번과 묶는 방법을 택했다.
위에서 언급했듯이 꼭 위의 방법이 아니더라도 다양한 경우의 수가 발생하는데
결론적으로는 어느것을 선택해도 모두 minimum solution이 된다.
따라서 final solution은 다음과 같이 쓸 수 있다.
P_1~P_5는 각각의 term에 해당하는 looping을 나타내기 위해 임의로 적어둔 것이다.