07 Quine-McCluskey 최소화 알고리즘

Presentation on theme: "07 Quine-McCluskey 최소화 알고리즘"— Presentation transcript:

1 07 Quine-McCluskey 최소화 알고리즘
Implicant: 간략화되거나 최소화될 항. PI(Prime Implicant) : 카르노 맵에서 최대 크기로 묶어서 만들어진 곱의 항. EPI(Essential Prime Implicant) : PI중에서 유일한 PI PI와 EPI는 카르노 맵을 조사하여 결정. PI의 집합이란 함수를 구성하는 각 최소항을 모두 포함하며, 각 최소항은 PI집합 중에 최소한 한 개의 PI에는 포함된다. Prime Implicant Essential Prime Implicant

2 07 Quine-McCluskey 최소화 알고리즘
QM(Quine-McCluskey) 방법은 많은 변수, 특히 변수가 6개 이상일 때 유용한 방법 QM 방법은 최소 SOP 식으로 만들어 진다. QM 방법의 과정 진리표에서 최소항을 모두 찾는다. 최소항 중에서 입력 변수에 1이 나타나는 개수에 따라서 인덱스(index)를 매겨 그룹을 만든다. 각 그룹간에 1비트만 다른 항들을 찾아서 간략화하며, 간략화에 사용된 항들은 표시한다. 이 과정을 반복하여 더 이상 간략화되지 않을 때까지 반복한다. 간략화 과정이 끝나고 표시되지 않은 항들이 PI가 된다. 중복된 PI를 찾기 위하여 차트를 만들고, EPI를 찾는다. EPI에 포함되는 PI들을 제거한다. EPI에 포함되지 않은 항들에 대해서 최소 개수의 SOP 식을 찾는다.

3 07 Quine-McCluskey 최소화 알고리즘
QM 방법은 간단하게 2단계로 이루어진다. 단계 1 : 을 적용하여 가능한 한 많은 변수들을 제거한다. 결과 항들은 PI가 된다. 단계 2 : PI 차트를 이용하여 함수를 PI의 최소 집합들로 표현한다. QM 방법을 이용한 간략화 과정

4 07 Quine-McCluskey 최소화 알고리즘
2. 기본 규칙 QM 방법은 규칙 을 반복 적용하여 최소화한다. 함수의 각 항들은 2진 형태(0과 1)로 표현하고, 변수가 제거된 곳은 대시(-)를 사용한다. : 101로 표현. (A=1, B=0, C=1) : 010로 표현. (A=0, B=1, C=0) : 10-로 표현. (A=1, B=0, C= ) : 1-1로 표현. (A=1, B=, C=1)

5 07 Quine-McCluskey 최소화 알고리즘
QM 방법을 이용한 간략화 과정 두 항을 결합하기 위한 QM 방법의 첫 번째 규칙은 오직 한 비트만 다를 때 제거된다는 것이다. 첫 번째 규칙을 적용하기 위해서 minterm 항들을 서로 1의 개수에 따라서 재배열한다. minterm 항을 2진 형태로 표현하여 1의 개수에 따라서 인덱스를 매기며, 인덱스 0, 인덱스 1, 인덱스 2 등으로 나열한다. 두 자리가 다르기 때문에 결합될 수 없다 A B C D A B C D ? 변수가 결합되는 경우 변수가 결합되지 못하는 경우

6 07 Quine-McCluskey 최소화 알고리즘
QM 방법에서의 인덱스 A B C D 10진 표기 index 0 index 1 1 2 4 8 index 2 3 5 6 9 10 12 index 3 7 11 13 14 index 4 15

7 07 Quine-McCluskey 최소화 알고리즘
예 인덱스 0의 000과 인덱스 1의 010은 가운데 비트 하나만 다르므로 결합될 수 있으며, 0-0이 된다. 인덱스 1의 010과 인덱스 2의 101은 서로 인접한 인덱스이지만 두 개 이상의 비트가 다르므로 결합할 수 없다. A B C 10진 표기 index 0 index 1 1 2 4 index 2 5 index 3 7

8 07 Quine-McCluskey 최소화 알고리즘
3. QM 방법을 이용한 간략화 첫 번째 과정 minterm 10진 2진 index 0 0 0 1 0 0 1 4 1 0 0 5 1 0 1 2 Column 1 index decimal A B C (0) 0 0 0 1 (1) (4) 0 0 1 1 0 0 2 (5) 1 0 1

9 07 Quine-McCluskey 최소화 알고리즘
두 번째 과정 세 번째 과정 Column 1 index decimal A B C (0) 0 0 0  1 (1) (4) 0 0 1 1 0 0 2 (5) 1 0 1 Column 2 index decimal A B C (0,1) (0,4) 0 0 - - 0 0 1 (1,5) (4,5) - 0 1 1 0 - Column 1 index decimal A B C (0) 0 0 0  1 (1) (4) 0 0 1 1 0 0 2 (5) 1 0 1 Column 2 index decimal A B C (0,1) (0,4) 0 0 - - 0 0  1 (1,5) (4,5) - 0 1 1 0 - Column 3 decimal A B C (0,1, 4,5) - 0 - (0,4,1,5)

10 07 Quine-McCluskey 최소화 알고리즘
예제 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal A B C D (0)  1 (1) (2) (8) 2 (3) (5) (10) (12) 3 (7) (13) 4 (15) Column 2 index decimal A B C D (0,1) (0,2) (0,8)  1 (1,3) (1,5) (2,3) (2,10) (8,10) (8,12) 2 (3,7) (5,7) (5,13) (12,13) 3 (7,15) (13,15) Column 3 decimal A B C D (0,1,2,3) (0,2,1,3) (0,2,8,10) (0,8,2,10) (1,3,5,7) (1,5,3,7) (5,7,13,15) (5,13,7,15)

11 07 Quine-McCluskey 최소화 알고리즘
IMPLICANTS 1 2 3 5 7 8 10 12 13 15 X (X) 1 – 0 0 Essential

12 07 Quine-McCluskey 최소화 알고리즘
예제 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal a b c d (0) 1 (1) (2) (8) 2 (3) (6) (9) 3 (7) (14) 4 (15)

13 07 Quine-McCluskey 최소화 알고리즘
Column 1 index decimal a b c d (0)  1 (1) (2) (8) 2 (3) (6) (9) 3 (7) (14) 4 (15) Column 2 index decimal a b c d (0,1) (0,2) (0,8)  1 (1,3) (1,9) (2,3) (2,6) (8,9) 2 (3,7) (6,7) (6,14) 3 (7,15) (14,15) Column 3 index decimal a b c d (0,1,2,3) (0,1,8,9) 1 (2,3,6,7) 2 (6,7,14,15)

14 07 Quine-McCluskey 최소화 알고리즘
IMPLICANTS 1 2 3 6 7 8 9 14 15 X (X) Essential

15 07 Quine-McCluskey 최소화 알고리즘
예제 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal a b c d 없음 1 (1) (2) (4) 2 (3) (5) (9) 3 (7) 4 (15)

16 07 Quine-McCluskey 최소화 알고리즘
Column 1 index decimal a b c d 1 (1) (2) (4)  2 (3) (5) (9) 3 (7) 4 (15) Column 2 index decimal a b c d 1 (1,3) (1,5) (1,9) (2,3) (4,5)  2 (3,7) (5,7) 3 (7,15) Column 3 index decimal a b c d 1 (1,3,5,7) (1,5,3,7) 2 없음

17 07 Quine-McCluskey 최소화 알고리즘
IMPLICANTS 1 2 3 4 5 7 9 15 X (X) Essential

18 07 Quine-McCluskey 최소화 알고리즘
예제 무관항 조건을 가진 다음 식을 QM방법을 이용하여 간략화 하여라. Column 1 index decimal a b c d (0)  1 (1) (2*) (4) (8) 2 (3*) (6) (9*) 3 (14) 4 (15) Column 2 index decimal a b c d (0,1) (0,2*) (0,4) (0,8)  1 (1,3*) (1,9*) (2*,3*) (2*,6) (4,6) (8,9*) 2 (6,14) 3 (14,15) Column 3 index decimal a b c d (0,1,2*,3*) (0,2*,4,6) (0,8,1,9*) 1 없음 2

19 07 Quine-McCluskey 최소화 알고리즘
IMPLICANTS 1 4 6 8 14 15 X (X) Essential

20 07 Quine-McCluskey 최소화 알고리즘
예제 QM방법을 이용하여 POS 형태로 간략화 하여라. Column 1 index decimal a b c d 1 (2*)  2 (3*) (5) (9*) (10) (12) 3 (7) (11) (13) Column 2 index decimal a b c d 1 (2*,3*) (2*,10)  2 (3*,7) (3*,11) (5,7) (5,13) (9*,11) (9*,13) (10,11) (12,13) Column 3 index decimal a b c d 1 (2*,10,3*,11) 2 없음

21 07 Quine-McCluskey 최소화 알고리즘
IMPLICANTS 5 7 10 11 12 13 (X) X Essential

22 07 Quine-McCluskey 최소화 알고리즘
예제 다음 식을 QM방법을 이용하여 SOP 형태로 간략화 하여라. Column 1 index decimal a b c d (0)  1 (1) (2) (8) 2 (5) (6) (9) (10) 3 (7) (14) Column 2 index decimal a b c d (0,1) (0,2) (0,8)  1 (1,5) (1,9) (2,6) (2,10) (8,9) (8,10) 2 (5,7) (6,7) (6,14) (10,14) Column 3 index decimal a b c d (0,1,8,9) (0,2,8,10) (0,8,1,9) (0,8,2,10) 1 (2,6,10,14) (2,10,6,14)

23 07 Quine-McCluskey 최소화 알고리즘
IMPLICANTS 1 2 5 6 7 8 9 10 14 X (X) Essential