Phương pháp bảng Quine-McCluskey

Trong chương trước, chúng ta đã thảo luận về phương pháp K-map, đây là một phương pháp thuận tiện để tối thiểu hóa các hàm Boolean lên đến 5 biến. Tuy nhiên, rất khó để đơn giản hóa các hàm Boolean có nhiều hơn 5 biến bằng cách sử dụng phương pháp này.

Phương pháp bảng Quine-McClukey là một phương pháp dạng bảng dựa trên khái niệm hàm ý nguyên tố. Chúng ta biết rằngprime implicant là một số hạng tích (hoặc tổng), không thể giảm hơn nữa bằng cách kết hợp với bất kỳ số hạng tích (hoặc tổng) nào khác của hàm Boolean đã cho.

Phương pháp dạng bảng này rất hữu ích để lấy các hàm số nguyên tố bằng cách sử dụng lặp lại nhận dạng Boolean sau đây.

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

Quy trình của Phương pháp bảng Quine-McCluskey

Hãy làm theo các bước sau để đơn giản hóa các hàm Boolean bằng phương pháp bảng Quine-McClukey.

Step 1 - Sắp xếp các số hạng tối thiểu đã cho trong một ascending ordervà tạo các nhóm dựa trên số lượng nhóm có trong biểu diễn nhị phân của chúng. Vì vậy, sẽ cóat most ‘n+1’ groups nếu có 'n' biến Boolean trong một hàm Boolean hoặc 'n' bit trong hàm nhị phân tương đương với số hạng min.

Step 2 - So sánh các điều khoản tối thiểu có trong successive groups. Nếu chỉ có một thay đổi ở vị trí một bit, thì lấy cặp của hai số hạng min đó. Đặt ký hiệu '_' này ở vị trí bit khác nhau và giữ nguyên các bit còn lại.

Step 3 - Lặp lại bước 2 với các thuật ngữ mới được hình thành cho đến khi chúng ta hiểu hết prime implicants.

Step 4 - Lập công thức prime implicant table. Nó bao gồm tập hợp các hàng và cột. Hàm nguyên tố có thể được đặt trong hàng khôn ngoan và số hạng nhỏ nhất có thể được đặt trong cột khôn ngoan. Đặt '1' vào các ô tương ứng với các số hạng tối thiểu được bao hàm trong mỗi hàm ý nguyên tố.

Step 5- Tìm hàm số nguyên tố cần thiết bằng cách quan sát từng cột. Nếu số hạng tối thiểu chỉ được bao phủ bởi một hàm ý nguyên tố, thì nó làessential prime implicant. Các hàm số nguyên tố cần thiết đó sẽ là một phần của hàm Boolean đơn giản hóa.

Step 6- Giảm bảng hàm ý nguyên tố bằng cách loại bỏ hàng của mỗi hàm số nguyên tố cơ bản và các cột tương ứng với các số hạng tối thiểu được bao hàm trong hàm ý nguyên tố cần thiết đó. Lặp lại bước 5 cho bảng hàm ý nguyên tố rút gọn. Dừng quá trình này khi tất cả các số hạng tối thiểu của hàm Boolean đã cho kết thúc.

Thí dụ

Hãy để chúng tôi simplify hàm Boolean sau, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ bằng Quine-McClukey phương pháp bảng.

Hàm Boolean đã cho nằm trong sum of min termshình thức. Nó có 4 biến W, X, Y & Z. Các số hạng tối thiểu đã cho là 2, 6, 8, 9, 10, 11, 14 và 15. Thứ tự tăng dần của các số hạng tối thiểu này dựa trên số hạng tử có trong chúng tương đương nhị phân là 2, 8, 6, 9, 10, 11, 14 và 15. Bảng sau đây cho thấy nhữngmin terms and their equivalent binary các đại diện.

GA3

Tên nhóm	Điều khoản tối thiểu	W	X	Y	Z
GA1	2	0	0	1	0
	số 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

Các số hạng tối thiểu đã cho được sắp xếp thành 4 nhóm dựa trên số lượng các số hạng có trong số tương đương nhị phân của chúng. Bảng sau đây cho thấymerging of min terms từ các nhóm liền kề.

GB3

Tên nhóm	Điều khoản tối thiểu	W	X	Y	Z
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	-

Các số hạng min, chỉ khác ở vị trí một bit so với các nhóm liền kề được hợp nhất. Bit khác biệt đó được biểu diễn bằng ký hiệu này, '-'. Trong trường hợp này, có ba nhóm và mỗi nhóm chứa kết hợp của hai số hạng nhỏ nhất. Bảng sau đây cho thấymerging of min term pairs từ các nhóm liền kề.

Tên nhóm	Điều khoản tối thiểu	W	X	Y	Z
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	-

Các nhóm liên tiếp của các cặp số hạng min, chỉ khác nhau ở vị trí một bit được hợp nhất. Bit khác biệt đó được biểu diễn bằng ký hiệu này, '-'. Trong trường hợp này, có hai nhóm và mỗi nhóm chứa các kết hợp của bốn số hạng nhỏ nhất. Ở đây, các kết hợp 4 số hạng tối thiểu này có sẵn trong hai hàng. Vì vậy, chúng ta có thể loại bỏ các hàng lặp lại. Bảng thu gọn sau khi loại bỏ các hàng thừa được hiển thị bên dưới.

Tên nhóm	Điều khoản tối thiểu	W	X	Y	Z
GC1	2,6,10,14	-	-	1	0
	8,9,10,11	1	0	-	-
GC2	10,11,14,15	1	-	1	-

Việc hợp nhất thêm các tổ hợp số hạng min từ các nhóm liền kề là không thể, vì chúng khác nhau ở vị trí nhiều hơn một bit. Có ba hàng trong bảng trên. Vì vậy, mỗi hàng sẽ cho một hàm ý nguyên tố. Do đó,prime implicants là YZ ', WX' & WY.

Các prime implicant table được hiển thị bên dưới.

Điều khoản tối thiểu / Hàm ý chính	2	6	số 8	9	10	11	14	15
YZ’	1	1			1		1
WX’			1	1	1	1
WY					1	1	1	1

Hàm nguyên tố được đặt trong hàng khôn ngoan và số hạng nhỏ nhất được đặt trong cột khôn ngoan. 1s được đặt trong các ô chung của các hàng hàm ý nguyên tố và các cột số hạng tối thiểu tương ứng.

Các số hạng tối thiểu 2 và 6 chỉ được bao hàm bởi một hàm ý nguyên tố YZ’. Vì vậy, nó là mộtessential prime implicant. Đây sẽ là một phần của hàm Boolean đơn giản hóa. Bây giờ, hãy xóa hàng hàm ý nguyên tố này và các cột số hạng tối thiểu tương ứng. Bảng hàm ý nguyên tố rút gọn được hiển thị bên dưới.

Điều khoản tối thiểu / Hàm ý chính	số 8	9	11	15
WX’	1	1	1
WY			1	1

Các số hạng tối thiểu 8 và 9 chỉ được bao hàm bởi một hàm ý chính WX’. Vì vậy, nó là mộtessential prime implicant. Đây sẽ là một phần của hàm Boolean đơn giản hóa. Bây giờ, hãy xóa hàng hàm ý nguyên tố này và các cột số hạng tối thiểu tương ứng. Bảng hàm ý nguyên tố rút gọn được hiển thị bên dưới.

Điều khoản tối thiểu / Hàm ý chính	15
WY	1

Thuật ngữ tối thiểu 15 chỉ được bao hàm bởi một hàm ý chính WY. Vì vậy, nó là mộtessential prime implicant. Đây sẽ là một phần của hàm Boolean đơn giản hóa.

Trong bài toán ví dụ này, chúng tôi có ba hàm số nguyên tố và cả ba hàm ý đều cần thiết. Do đó,simplified Boolean function Là

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