저번 시간에는 don't care 를 활용하여 더욱 최적화가 되는 경우를 알아 보았다.
하지만 이렇게 don't care 까지 고려한다면 고려 해야 하는 경우의 수가 너무 많아진다.
그리고 이를 사람이 하다보면 실수가 있을 수 밖에 없다.
따라서 최적화 하는 방법을 순서를 나누어 보았다.
이를 three steps of QM method 라고 한다.
총 3단계로 나누어지는데,
1 : prime implicant 를 만든다.
2 : essential prime implicant 를 찾는다.
3 : minimum prime implicant 를 찾는다.
우선 첫번째 단계를 하기 전에 우리가 k-map에서 prime implicant 를 만들었을때를 생각해보자.
k-map 에서는 우선 map을 만들 때에 있어서 HD(hamming distance) 가 1이 되도록 배치시킨 후 인접한, HD 가 1인 값들을 1,2,4,8... 의 크기로 묶었다. 이때 알 수 있는 것이 HD = 1 인 binary들은 # of 1 이 1이라는 것이다. 하지만 이 명제의 역은 성립하지 않는다. 반례로 1010 과 0100은 # of 1 이 1 이지만 인접하지 않아서 HD = 1 이 아니다. 그렇다면 할 수 없는 것인가? 아니다.
이제 부터 알아보자
위는 우리가 최적화 해야 하는 optimized 해야 하는 minterm 을 k-map 이 아닌 표로 나타낸 것이다. d 는 don't care 이다. don't care 도 포함 시켜야 고려 할 수 있는 가짓수가 많아 지기에 포함해야 한다.
이제 각각의 minterm을 묶어야 하는데 가능한 조합을 모두 해보는 것이 아니라 # of 1s 의 차이가 1인 것들 만 묶으면 된다. 그 이유는 HD = 1 인 것들 끼리 묶어야 하는데 HD = 1인 것들은 모두 # of 1s 의 차이가 1이기 때문이다.
따라서 (0,4) (0,8) (4,10) (4,12) ... 이렇게 묶어야 한다. 이렇게 묶어서 합연산을 진행하여 0 + 0 = 1 / 1 + 1 = 1/ 0 + 1 = - 이런 식으로 표현한다. - 의 의미는 merge를 완료 했다는 의미이다. 따라서 나타내어 표를 다시 작성 한다면
위의 그림처럼 나타낼 수 있다. 위의 combined의 의미는 해당 minterm을 묶는데에 성공을 했다는 의미이다. 만약에 combined 가 되지 못했다면 주변에 0밖에 없어서 묶을 수 없다는 의미이다. 하지만 combined 가 체크되지 않았다고 무조건 epi 인것은 아니다.
위는 1에서 2로 묶는 것이기 때문에 -이 하나만 나와야 한다 -의 의미는 합병한다는 의미인데 묶을때 2개 이상을 합병 할 수는 없기 때문이다. 그리고 묶는데 성공 할 때마다 하나씩 합병 되어 사라지므로 # of 1s 0, 1 을 합병하면 # of 1s 0 이되고 # of 1s 1,2 를 합병하면 1이 된다. 그리고 묶는 일을 한번더 진행한다면
위의 그림 처럼 된다. 오른쪽의 그림이 묶는데 성공한 것만 적은 표인데 1개 뿐이 없으므로 멈출 수 밖에 없다.
따라서 epi (0,4,8,12)는 확정이 된다. 그리고 묶지 못한 2개 짜리의 식들은 우선 PI 로 분류할 수 있다.
이제 epi 를 골라야 한다.
epi 를 고를 때에는 이전에 comined가 체크되지 않았던 쌍 들을 고른 후에 커버하는 minterm 들을 표에 표시 한후에 minterm 을 커버하는 prime implicant 가 유일 하다면 그것이 epi 가 된다. 그 후에 cost 를 고려하며 nepi 를 골라야 하는데 이는 다음시간에 알아 보겠다.