[Quine-McCluskey Method] Petrick's Method

개요

Petrick's method는 prime implicant chart로부터 모든 minimum sum-of-products solution을 구하는 방법이다.
Variable의 숫자가 많아질 수록 prime implicant의 숫자도 늘어날 뿐 아니라, 
prime implicant chart 역시 점점 더 복잡해진다.
그러면 minimum solution을 구하기 위해서 많은 시행착오를 겪게 되는데,
좀 더 체계적인 방법으로 minimum solution을 구할 수 있는 것이 Petrick's method라고 할 수 있다.

적용방법

1. prime implicant chart에서 essential prime implicant와 해당 minterm을 제거한다.
2. 각 prime implicant가 있는 줄 마다 P_1, P_2, ... 와 같이 번호를 붙인다.
3. logic function P를 만든다. P는 product-of-sums의 형태이고,
　 각 sum term은 i번째 minterm을 포함하는 row들의 합으로 나타낸다.
4. P를 sum-of-products 형태로 simplify한다.
5. 여기서 도출된 각각의 term은 solution이 될 수 있는데,
　 이 중 적은 수의 variable로 이루어진 term이 minimum solution이다.

Petrick's method 자체는 큰 prime implicant chart에 대해서 매우 지루한 작업이므로,
보통은 컴퓨터 프로그램으로 구현하여 사용한다.
구체적인 적용 방법은 아래 예제에서 자세히 알아보도록 하자.

예제

먼저 각각의 row에 P_1 부터 P_6 까지의 이름을 매긴다.
우리는 어떤 logic function P를 만들어낼 것이다.
이 P는 모든 minterm이 cover되었을 때 항상 1(true)가 되는 그런 함수다.
P_1은 row에 있는 prime implicant가 minimum solution에 포함되었을 때 1의 값을 갖는다고 하자.
마찬가지로 P_2, P_3, ... 에 대해서도 마찬가지라고 가정한다.

다시한번 설명하면, P_i는 어떤 새로운 logic variable으로 정의되는 것이고,
각각의 variable P_i는 해당 row의 prime implicant가 minimum solution에 포함되어있느냐의 여부를 나타낸다.

만약 우리가 minterm 0번을 minimum solution에 포함시키고자 하는 경우에는,
P_1과 P_2가 1이어야 한다. 따라서 이 경우에는, (P_1 + P_2) = 1 이다.
만약 minterm 1번을 minimum solution에 포함시키고자 하는 경우에는 P_1과 P_3이 1이어야 한다.
이 경우에는, (P_1 + P_3) = 1 이 되어야 한다.
이러한 방식으로 모든 minterm에 대해서 각 조합을 만들 수 있다.
그리고 각 조합의 곱은 곧 1이 될 것이다. (각 조합은 각각 1이므로)
정리해보면,

이제 이 식을 sum-of-products 형태로 정리하게 되면,
각 항 중 하나만 1이더라도 전체의 식이 1이 된다.
이 때의 minimum solution은 각 항 중에서 variable이 가장 적은 항을 고르는 것이다.
P를 정리해 보면,

위와 같이 정리가 가능하다.
밑줄 친 term들은 다른 term에 비해서 단지 3개의 variable로 되어있다.
즉, P_1, P_4, P_5의 row를 선택하는 것으로 minimum solution을 얻는 것이 가능하다.
마찬가지로 P_2, P_3, P_6의 row를 선택하는 것 역시 minimum solution을 얻는 것이 가능하다. 
여기서는 2개의 minimum solution이 나오게 되었다.