Quine-McCluskey 표 형식 방법

이전 장에서는 최대 5 개의 변수까지 불리언 함수를 최소화 할 수있는 편리한 방법 인 K-map 방법에 대해 설명했습니다. 그러나이 방법을 사용하면 변수가 5 개 이상인 Boolean 함수를 단순화하기가 어렵습니다.

Quine-McClukey 표 형식 방법은 주요 함축 개념을 기반으로 한 표 형식 방법입니다. 우리는 알고 있습니다prime implicant 주어진 부울 함수의 다른 제품 (또는 합계) 용어와 결합하여 더 이상 줄일 수없는 제품 (또는 합계) 용어입니다.

이 표 형식 방법은 다음 부울 ID를 반복적으로 사용하여 주요 함축을 가져 오는 데 유용합니다.

xy + xy '= x (y + y') = x.1 = x

Quine-McCluskey 표 방식의 절차

Quine-McClukey 표 형식 방법을 사용하여 부울 함수를 단순화하려면 다음 단계를 따르십시오.

Step 1 − 주어진 최소 항을 ascending order이진 표현에있는 1의 수를 기반으로 그룹을 만듭니다. 그래서at most ‘n+1’ groups 부울 함수에 'n'부울 변수가 있거나 최소 항에 해당하는 이진에 'n'비트가있는 경우.

Step 2 −에 존재하는 최소 용어 비교 successive groups. 1 비트 위치에만 변경이있는 경우이 두 개의 최소 항 쌍을 취하십시오. 이 기호 '_'를 다른 비트 위치에 배치하고 나머지 비트를 그대로 유지합니다.

Step 3 − 모든 것을 얻을 때까지 새로 형성된 용어로 2 단계를 반복합니다. prime implicants.

Step 4 − 공식화 prime implicant table. 행과 열의 집합으로 구성됩니다. 프라임 임 플리 던 트는 행 단위로 배치 할 수 있고 최소 용어는 열 단위로 배치 할 수 있습니다. 각 프라임 임 플리 던트에서 다루는 최소 항에 해당하는 셀에 '1'을 넣으십시오.

Step 5− 각 열을 관찰하여 필수 주요 함의를 찾습니다. 최소 기간이 하나의 주요 함 축사에 의해서만 포함된다면essential prime implicant. 이러한 필수 주요 의미는 단순화 된 부울 함수의 일부입니다.

Step 6− 각 필수 프라임 임 플리 던트의 행과 해당 필수 프라임 임 플리 던트에서 다루는 최소 용어에 해당하는 열을 제거하여 프라임 임 플리 던트 테이블을 줄이십시오. 감소 된 프라임 관련 테이블에 대해 5 단계를 반복하십시오. 주어진 부울 함수의 모든 최소 항이 끝나면이 프로세스를 중지하십시오.

예

하자 simplify Quine-McClukey를 사용하는 다음 부울 함수, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ 표 형식 방법.

주어진 부울 함수는 sum of min terms형태. 4 개의 변수 W, X, Y & Z가 있습니다. 주어진 최소 항은 2, 6, 8, 9, 10, 11, 14 및 15입니다.이 최소 항의 오름차순은 해당 항목에 존재하는 항목 수를 기준으로합니다. 이진수는 2, 8, 6, 9, 10, 11, 14 및 15입니다. 다음 표는 이러한min terms and their equivalent binary 표현.

GA3

그룹 이름	최소 기간	W	엑스	와이	지
GA1	2	0	0	1	0
	8	1	0	0	0
GA2	6	0	1	1	0
	9	1	0	0	1
	10	1	0	1	0
11	1	0	1	1
14	1	1	1	0
GA4	15	1	1	1	1

주어진 최소 항은 이진 등가물에있는 항목의 수에 따라 4 개의 그룹으로 배열됩니다. 다음 표는 가능한merging of min terms 인접한 그룹에서.

GB3

그룹 이름	최소 기간	W	엑스	와이	지
GB1	2,6	0	-	1	0
	2,10	-	0	1	0
	8,9	1	0	0	-
	8,10	1	0	-	0
GB2	6,14	-	1	1	0
	9,11	1	0	-	1
	10,11	1	0	1	-
	10,14	1	-	1	0
11,15	1	-	1	1
14,15	1	1	1	-

인접한 그룹과 1 비트 위치에서만 다른 최소 항이 병합됩니다. 다른 비트는이 기호 '-'로 표시됩니다. 이 경우 세 개의 그룹이 있고 각 그룹에는 2 개의 최소 용어 조합이 포함됩니다. 다음 표는 가능한merging of min term pairs 인접한 그룹에서.

그룹 이름	최소 기간	W	엑스	와이	지
GB1	2,6,10,14	-	-	1	0
	2,10,6,14	-	-	1	0
	8,9,10,11	1	0	-	-
	8,10,9,11	1	0	-	-
GB2	10,11,14,15	1	-	1	-
	10,14,11,15	1	-	1	-

1 비트 위치에서만 다른 연속적인 최소 항 쌍 그룹이 병합됩니다. 다른 비트는이 기호 '-'로 표시됩니다. 이 경우 두 개의 그룹이 있고 각 그룹에는 4 개의 최소 용어 조합이 포함됩니다. 여기에서 이러한 4 분 용어 조합은 두 행에서 사용할 수 있습니다. 따라서 반복되는 행을 제거 할 수 있습니다. 중복 행을 제거한 후 축소 된 테이블은 다음과 같습니다.

그룹 이름	최소 기간	W	엑스	와이	지
GC1	2,6,10,14	-	-	1	0
	8,9,10,11	1	0	-	-
GC2	10,11,14,15	1	-	1	-

인접 그룹의 최소 용어 조합은 1 비트 이상의 위치에서 다르기 때문에 더 이상 병합 할 수 없습니다. 위 표에는 3 개의 행이 있습니다. 따라서 각 행은 하나의 주요 의미를 제공합니다. 따라서prime implicants YZ ', WX'및 WY입니다.

그만큼 prime implicant table 아래에 나와 있습니다.

최소 용어 / 프라임 임 플리 던트	2	6	8	9	10	11	14	15
YZ’	1	1			1		1
WX’			1	1	1	1
WY					1	1	1	1

주요 의미는 행 단위로 배치되고 최소 용어는 열 단위로 배치됩니다. 1은 주요 함축 행과 해당 최소 항 열의 공통 셀에 배치됩니다.

최소 용어 2와 6은 단 하나의 주요 함 축사에 의해 다루어집니다. YZ’. 그래서, 그것은essential prime implicant. 이것은 단순화 된 부울 함수의 일부입니다. 이제이 주요 함축 행과 해당 최소 항 열을 제거합니다. 축소 된 프라임 임 플리 던트 테이블은 다음과 같습니다.

최소 용어 / 프라임 임 플리 던트	8	9	11	15
WX’	1	1	1
WY			1	1

최소 용어 8과 9는 단 하나의 주요 함 축사에 의해 다루어집니다 WX’. 그래서, 그것은essential prime implicant. 이것은 단순화 된 부울 함수의 일부입니다. 이제이 주요 함축 행과 해당 최소 항 열을 제거합니다. 축소 된 프라임 임 플리 던트 테이블은 다음과 같습니다.

최소 용어 / 프라임 임 플리 던트	15
WY	1

최소 기간 15는 단 하나의 주요 암시 자에게만 적용됩니다. WY. 그래서, 그것은essential prime implicant. 이것은 단순화 된 부울 함수의 일부입니다.

이 예제 문제에서 우리는 세 가지 주요 함의를 얻었고 세 가지 모두 필수입니다. 따라서simplified Boolean function 이다

f(W,X,Y,Z) = YZ’ + WX’ + WY.