메뉴
[Quine-McCluskey Method] Determination of Prime Implicants

2012. 2. 21. 23:30

개요

Karnaugh map은 비교적 적은 숫자의 variable에 관해서 정리할 때 유용하다.
하지만, variable의 갯수가 많아지는 경우에는 컴퓨터를 사용해야 한다.
Quine-McCluskey method는 Karnaugh map에 비해서 비교적 컴퓨터 프로그래밍에 적합하다.

Quine-McCluskey method는
minterm expansion (각 term이 모든 variable을 포함하는 sum-of-products expression 형태)으로부터
minimum solution을 구하는 과정에 사용되고, 다음의 2개의 step을 거친다.

1. XY + XY' = X의 식을 기본으로 하여, 가능한한 많은 variable을 줄이도록 한다. 
  결과에 나온 term들을 prime implicant라고 한다.
2. prime implicant chart를 이용해서 최소한의 prime implicant만으로 이루어진 set (minimum set)을 구한다.

이번 파트에서는 Quine-McCluskey method 이 어떻게 성립하는지, 적용되는지 살펴보도록 하겠다.




Finding Prime Implicants

Quine-McCluskey method를 적용하기 위해서는 먼저 모든 prime implicant를 찾아야 한다.
그러기 위해서는 모든 minterm을 서로 비교해서, XY + XY' = X 형태로 합칠 수 있는 것은 합쳐야 한다.
비교횟수를 최소화 하기 위해서는 각 mintemr의 1의 갯수에 따라서 minterm을 분류해야 한다.
예를 들어 다음과 같은 minterm의 조합이 있다고 하자.

f(a,b,c,d) = \sum m (0,1,2,5,6,7,8,9,10,14)


위의 식은 다음과 같이 정리해 볼 수 있다.


각각의 그룹이름은 minterm을 2진수로 표현했을 때의 1의 개수를 의미 한다.
즉, group 0은 0000만이 가능하고, group 1에는 1이 한개만 포함되어있는 0001, 0010, 1000이 포함되는 식이다.
위와 같이 정리하고 나서, 인접한 그룹끼리 차례로 묶는다.
다음의 표를 살펴보자.


Column 1은 우리가 위에서 보았던 그 표와 동일하다.
Column 1을 작성한 다음에는 차례로 column 2를 작성해야하는데,
작성하는 방법은 다음과 같다.

1. 차례로 인접하는 그룹 두 개를 선택해서 각 그룹의 원소 중 하나씩 고른다.
  처음에는 group 0, 1를 고른 다음 2~3번을 수행한다. 나머지 group에 대해서도 순서대로 한다.
2. 중복되는 숫자 또는 대쉬(dash, -)가 3개면 겹치지 않는 숫자를 -으로 바꾸어 표시하고,
  겹치는 숫자는 그대로 표시하여 새로운 column에 써내려간다.
  만약 두 개의 숫자가 겹침이 가능한 경우에는 체크(v)표시를 한다.
3. 가능한 모든 쌍을 찾아 반복한다. 이 쌍들은 곧 다시 하나의 group이된다. (마찬가지로 체크(v)표시를 한다.)
  더 이상 선택할 이전 단계의 group이 없으면 4번으로 간다.
4. 그룹의 숫자가 가능한 적어질 때 까지 새로 생성된 group을 바탕으로 반복한다.


Column 2의 첫번째 줄을 살펴보면 0,1을 묶어서 000-로 표시한 것을 볼 수 있다.
즉 column 1에서 group 0과 group1 에 있는 0 (0000)과 1 (0001)은
각각 2, 3, 4번째 자리 숫자가 동일하며 1번째 자리 숫자(LSB)가 0, 1로 다르다.
따라서 000은 그대로 남고, 1번째 자리 숫자를 dash로 표현했다. 
나머지 숫자 쌍들에 대해서도 모두 검사하면 3개의 쌍을 발견할 수 있다.

다음 차례로는 group 1과 group 2의 숫자들을 검사한다.
Column 2의 2번째 group의 첫번째 줄을 보면 1,5를 묶어서 010-으로 표시한 것을 볼 수 있다.
여기서도 위의 과정을 반복한 것이다. 물론, 조합이 불가능한 경우에 대해서는 쓸 수 없다.
예를 들어 5와 8의 경우 서로 겹치는 숫자가 2번째 자리 숫자 뿐이므로 겹칠 수 없다. 

이런 식으로 반복을 거치면, 새로운 3개의 group이 만들어지게 된다.
이러한 group들은 또 다시 column 3에서 조합을 시도해 봐야 한다.
여기서는 dash로 표현한 것들도 중복되는지 체크해야 한다.
예를 들어, 0-00 과 0-01 이라면, 0-0-로 조합이 되는 것이다. 

모든 쌍에서 조합이 불가능한 경우에는,
즉, 새로운 column을 만들어 낼 수 없는 수준까지 계속되는 경우에는 중단한다.

그리고 column 3을 살펴 보면, 숫자들 순서가 다를 뿐 동일한 term이 겹쳐있는 경우가 생긴다.
이런 경우에는 동일한 term들 중 하나를 삭제한다.

이 모든 과정을 거쳤을 때, 체크표시가 없는 term들이 곧 prime implicant가 된다.
예를 들어  column 1에서 체크되지 않은 숫자는 없고,
column 2에서 체크되지 않은 숫자들은 0-01, 01-1, 011- 이고,
column 3에서 체크되지 않은 숫자들은 -00-, -0-0, --10 이다. 
각각을 term으로 바꾸면, a'c'd, a'bd, a'bc, b'c', b'd', cd'의 6개가 된다.

즉, 최종적으로 f = a'c'd + a'bd + a'bc + b'c' + b'd' + cd' 가 된다.
그러나 이것은 prime implicant의 합일 뿐이고, 이것이 minimun solution이 되지는 못한다.

minimum solution을 구하는 것은 prime implicant chart 를 통해서 할 수 있으며,
다음 포스팅에서 다루도록 하겠다.