[Karnaugh Map] Essential Prime Implicants
2012. 2. 18. 21:41
정의
Karnaugh map 상의 홀로 떨어진 1이나 1의 묶음들은 function F의 implicant 라고 한다.
한편 prime implicant란 다른 implicant와 더 이상 결합될 수 없는 것들을 말한다.
다음 Karnaugh map을 보면서 예를 살펴보자.
abc' 와 ab'c'는 implicant지만, prime implicant는 아니다.
ac'와 같이 더 큰 implicant로 합쳐질 수 있기 때문이다.
즉 ac'는 prime implicant라고 할 수 있다.
반면 아래쪽의 a'b'c나 a'cd'는 더 이상 큰 loop로 만들 수 없으므로 prime implicant라고 할 수 있다.
마지막으로 왼쪽 상단의 1은 prime implicant처럼 보일 수 있으나,
adjacency rule을 생각해 봤을 때, 오른쪽 상단의 1이나 왼쪽 하단의 1과 묶일 수 있다.
따라서 prime implicant라고 할 수 없다.
이런 과정을 거쳐 얻게된 minimum sum-of-products expression의 각 term은 곧 prime implicant라고 할 수 있다.
바꿔 말하면, 각 term 중 하나라도 prime implicant가 아닌 expression은
minimum solution이라고 할 수 없는 것이다.
Prime Implicants and Minimum Solution
Karnaugh map 위에서 각각의 1에 대해 항상 하나의 prime implicant만 존재하는 것이 아니다.
위 그림을 잘 살펴보면 대부분의 1이 두개 이상의 prime implicant를 동시에 갖고 있다.
물론 각각의 prime implicant는 더 이상 확장이 불가능해야 한다.
위 그림에서 파란색 배경색이 칠해진 prime implicant만 가지고는 minimum solution을 만들 수 없다.
prime implicant에 포함되지 않은 1이 2개 남아있기 때문이다.
반면 점선이 아닌 선으로 된 prime implicant 3가지는 곧
minimum solution인 F = a'b'd + bc' + ac 를 완성하게 된다.
그렇다면, 어떤 prime implicant를 골라야 한번에 minimum solution을 구할 수 있을까?
Essential Prime Implicant
그림 (a)를 보면, 파란색 바탕으로 되어있는 1들은 단 하나의 prime implicant에만 속해있다.
잘 생각해 보면, 이러한 1들을 포함하는 prime implicant들은 반드시 minimum solution에 포함될 수 밖에 없다.
이러한 1을 포함하지 않고서는 아예 expression 자체가 완성이 되질 않기 때문이다.
이렇게, 파란색 바탕으로 되어있는 1들은 반드시 포함되어야 하며,
이러한 1들을 포함하는 prime implicant를 essential prime implicant라고 한다.
이러한 essential prime implicant들을 우선적으로 선택하고 나서,
남은 1에 대해서 필요한 prime implicant를 취하면 결론적으로 minimum solution을 (b)와 같이 얻을 수 있다.
Example
위 그림과 같이, 파란색 바탕의 1들을 포함하는 essential prime implicant들을 우선적으로 선택 한 다음,
2가지 중 어떤 하나를 선택해도 상관없는 prime implicant를 선택하여 최종적으로 minimum solution을 완성한다.
혹은 looping을 먼저하고
그 loop안에 해당 loop를 essential prime implicant로 만들 수 있는 1이 포함되어있는지 찾아보아도 된다.
Essential prime implicant를 찾기 위해서는 각각의 1에 대해서,
가능한 prime implicant를 찾는 것이다. 만약 여러개가 가능한 경우라면 이는 essential prime implicant가 아니다.
하지만 단 하나의 prime implicant만이 해당 1을 포함할 수 있으면 그것은 essential prime implicant이다.
따라서, 이러한 1을 포함하여 가장 크게 looping을 하고,
그 다음엔 looping이 되지 않은 1들에 대해서 위 작업을 반복한다.
더 이상 looping할 수 없는 순간이 되면, 그 때 남은 1에 대해서 prime implicant를 만들면 된다.
Including 'Don't Care' Case
마지막으로 don't care를 포함하는 Karnaugh map의 경우에는 다음과 같은 순서로 진행한다.
1. 임의의 minterm (즉, map 위의 어떤 1 중 아무것이나)을 고른다.
2. 그 minterm 주변의 1이나 X를 찾는다. 찾아서 가능한한 가장 큰 looping을 한다.
3. 그 looping이 essential prime implicant인지 검사한다.
검사 방법은 반드시 포함해야 하는 1을 포함하는지를 살펴보면 된다.
여기서는 X를 1이라고 생각한다.
4. 1~3번을 더 이상 looping할 것이 없을 때까지 반복한다.
5. 남은 1을 looping함으로써 minimum solution을 구한다.
여기서 설명한 방법은 아마도 Karnaugh map으로 minimum solution을 구할 수 있는
가장 쉽고 빠른 방법일 것이다.