Công cụ Giải Bản đồ Karnaugh (K-Map)

Công cụ giải bản đồ Karnaugh (K-Map) tối giản hóa bất kỳ hàm logic Boolean nào từ 2 đến 5 biến và trực quan hóa quá trình đơn giản hóa dưới dạng bản đồ K-map cổ điển với các nhóm được mã hóa màu. Nhập minterm, maxterm của bạn hoặc sử dụng bảng chân trị tương tác — công cụ giải sẽ chạy thuật toán Quine-McCluskey bên dưới, tìm mọi tế bào chính, đánh dấu những cái thiết yếu và tạo ra biểu thức Tổng của các Tích (SOP) hoặc Tích của các Tổng (POS) tối thiểu với giải thích từng bước. Nhấp vào bất kỳ thẻ tế bào chính nào để xem các ô mà nó bao phủ nhấp nháy trên bản đồ và hiểu cách việc nhóm các ô giúp đơn giản hóa logic.

Bản đồ Karnaugh là gì?

Bản đồ Karnaugh (được phát minh bởi Maurice Karnaugh vào năm 1953) là một phương pháp đồ họa để biểu diễn bảng chân trị, được sắp xếp sao cho các ô chỉ khác nhau bởi một biến đầu vào sẽ nằm cạnh nhau về mặt vật lý. Bí quyết chính là việc sử dụng thứ tự mã Gray cho các hàng và cột: các nhãn liên tiếp như 00, 01, 11, 10 chỉ khác nhau đúng một bit. Sự kề nhau này cho phép bạn phát hiện trực quan các nhóm số 1 (hoặc số 0) có thể được kết hợp thành một số hạng đơn giản hơn.

Đối với n biến đầu vào, K-map có 2^n ô. Bản đồ K-map 4 biến là một lưới 4×4 gồm 16 ô; bản đồ 5 biến được vẽ dưới dạng hai lưới 4×4 cạnh nhau.

SOP và POS: Nên chọn dạng nào?

Tổng của các Tích (SOP)

SOP nhóm các ô chứa số 1. Mỗi nhóm trở thành một tích (phép AND) của các biến, và tất cả các nhóm được thực hiện phép OR với nhau. Ví dụ: AB'C + BD. SOP thường là mặc định vì nó ánh xạ trực tiếp đến các mạng cổng logic AND–OR.

Tích của các Tổng (POS)

POS nhóm các ô chứa số 0. Mỗi nhóm trở thành một tổng (phép OR) của các biến nghịch đảo, và tất cả các tổng được thực hiện phép AND với nhau. Ví dụ: (A + B')(C + D'). POS thường gọn hơn khi hàm có nhiều số 1 hơn số 0.

Công cụ tính toán cả hai dạng một cách độc lập — hãy chuyển đổi chế độ đầu ra để so sánh số lượng biến và chọn dạng nào đơn giản hơn cho việc triển khai của bạn.

Quy tắc nhóm ô trong bản đồ Karnaugh

• Chỉ nhóm theo lũy thừa của 2: các nhóm phải chứa 1, 2, 4, 8 hoặc 16 ô. Một nhóm có 3 hoặc 5 ô là không hợp lệ.
• Hình dạng chữ nhật: các ô trong một nhóm phải tạo thành một hình chữ nhật (theo chiều ngang, chiều dọc hoặc bao quanh các cạnh).
• Tính kề nhau bao quanh: hàng trên cùng kề với hàng dưới cùng; cột ngoài cùng bên trái kề với cột ngoài cùng bên phải. Đây là lý do tại sao thứ tự mã Gray lại quan trọng.
• Ưu tiên các nhóm lớn nhất trước: các nhóm lớn hơn sẽ loại bỏ được nhiều biến hơn, tạo ra các số hạng tích ngắn hơn. Một nhóm 8 ô loại bỏ 3 biến; nhóm 4 ô loại bỏ 2 biến; nhóm 2 ô loại bỏ 1 biến.
• Mọi số 1 phải được bao phủ: ít nhất một nhóm phải bao phủ mỗi ô chứa số 1 (đối với SOP) hoặc ô chứa số 0 (đối với POS).
• Cho phép chồng lấp: cùng một số 1 có thể được bao phủ bởi nhiều nhóm nếu điều đó giúp tạo ra các nhóm lớn hơn.
• Don't-care rất linh hoạt: chúng có thể được đưa vào nhóm nếu việc đó tạo ra các nhóm lớn hơn, nhưng không bắt buộc phải bao phủ chúng.

Tế bào chính và Tế bào chính thiết yếu

Một tế bào chính (prime implicant) là một nhóm không thể mở rộng thêm được nữa — nếu mở rộng thêm sẽ bao hàm cả một ô chứa số 0 (đối với SOP). Công cụ giải liệt kê mọi tế bào chính mà nó tìm thấy. Sau đó, nó chọn một tập bao phủ tối thiểu: tập hợp nhỏ nhất các tế bào chính bao phủ mọi minterm bắt buộc.

Một tế bào chính thiết yếu (essential prime implicant) được đánh dấu là THIẾT YẾU khi nó là tế bào chính duy nhất bao phủ ít nhất một minterm cụ thể. Mọi biểu thức tối giản đều phải bao gồm tất cả các tế bào chính thiết yếu. Sau khi chọn chúng, các minterm còn lại chưa được bao phủ sẽ được bao phủ bởi các tế bào chính bổ sung có chi phí thấp nhất.

Điều kiện tùy định (Don't-Care)

Một don't-care (hiển thị là X trên K-map) là một tổ hợp đầu vào mà đầu ra không quan trọng — có thể nó không bao giờ xảy ra trong mạch thực tế hoặc giá trị của nó không gây ảnh hưởng. Thuật toán có thể tự do coi mỗi chữ X là 0 hoặc 1, chọn giá trị nào giúp tạo ra biểu thức đơn giản hơn. Trong thực tế, don't-care thường giúp giảm 30–60% số lượng biến. Một ví dụ thực tế phổ biến: các bộ giải mã chữ số thập phân chỉ sử dụng 10 trong số 16 tổ hợp đầu vào 4 bit, để lại các tổ hợp từ 10–15 làm don't-care.

Thuật toán Quine-McCluskey

K-map là một phương pháp trực quan, nhưng với hơn 4–5 biến, nó trở nên không khả thi. Thuật toán Quine-McCluskey (QM) là phương pháp bảng tương đương — chính xác về mặt toán học và có khả năng mở rộng. Công cụ này sử dụng QM bên trong:

1. Liệt kê các minterm dưới dạng nhị phân, nhóm chúng theo số lượng bit 1.
2. Kết hợp các cặp từ các nhóm kề nhau (khác nhau một bit), thay thế bit khác biệt bằng một dấu gạch ngang. Ví dụ: 0011 + 0111 → 0-11.
3. Lặp lại cho đến khi không còn kết hợp nào khả thi. Các số hạng không thể kết hợp thêm là các tế bào chính.
4. Xây dựng bảng tế bào chính — các hàng là các tế bào chính, các cột là các minterm bắt buộc. Xác định các tế bào chính thiết yếu (các cột chỉ có một dấu kiểm).
5. Phương pháp Petrick / tìm kiếm vét cạn: đối với các minterm còn lại chưa được bao phủ, tìm tập hợp nhỏ nhất các tế bào chính bổ sung để bao phủ chúng.

Cách sử dụng công cụ này

1. Chọn số lượng biến: 2, 3, 4 hoặc 5. Lưới K-map sẽ tự động điều chỉnh.
2. Chọn phương pháp nhập:
   • Minterm: nhập các chỉ số nơi F = 1 (ví dụ: 1, 3, 5, 7) và các don't-care nếu có.
   • Maxterm: nhập các chỉ số nơi F = 0. Công cụ sẽ tự động coi các chỉ số còn lại là 1.
   • Bảng chân trị: nhấp vào từng hàng để chuyển đổi đầu ra giữa 0, 1 và X. Rất phù hợp để thiết kế logic thủ công.
3. Chọn đầu ra SOP hoặc POS. So sánh cả hai dạng bằng cách chuyển đổi — một dạng thường sẽ ngắn hơn dạng kia.
4. Nhấp Giải. Bản đồ K-map sẽ xuất hiện với mọi tế bào chính có màu sắc riêng biệt. Nhấp vào bất kỳ thẻ nào để xem các ô mà nó bao phủ nhấp nháy.
5. Kiểm tra các bước: bảng phân tích Quine-McCluskey cho thấy cách mỗi tế bào chính được tạo ra và cái nào là thiết yếu.

Ví dụ minh họa: Hàm 4 biến với Don't-Care

Xét F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Nếu không có don't-care, SOP tối thiểu sẽ cần nhiều số hạng. Bằng cách coi {0, 2} là 1, công cụ có thể xây dựng nhóm 4 ô A'B' (bao phủ 0, 1, 2, 3). Coi 5 là 1 cho phép nó mở rộng vùng bao phủ của CD. Kết quả tối giản là:

Chỉ còn 4 biến — giảm đáng kể so với hơn 10 biến nếu không sử dụng mẹo don't-care. Bạn có thể tải chính xác ví dụ này bằng nút "4 biến với Don't-Care" ở trên.

Tại sao cần tối giản các hàm Boolean?

• Ít cổng logic hơn = chi phí phần cứng thấp hơn, diện tích chip nhỏ hơn, tiêu thụ điện năng thấp hơn.
• Mạch nhanh hơn: ít độ trễ cổng hơn trên đường dẫn quan trọng.
• Tài liệu gọn sạch: một biểu thức ngắn gọn sẽ dễ kiểm tra và bảo trì hơn.
• Nền tảng của thiết kế kỹ thuật số: mọi công cụ tổng hợp FPGA đều chạy một phiên bản cải tiến của Quine-McCluskey (như Espresso-II).

Hạn chế và khi nào nên dùng công cụ khác

• Trên 5 biến: K-map trở nên rối rắm. Công cụ này hỗ trợ tối đa 5 biến bằng cách chia thành hai bản đồ 4×4. Ngoài mức đó, hãy dựa vào các bước Quine-McCluskey hoặc sử dụng các công cụ tổng hợp chuyên nghiệp như ABC / Espresso.
• Hiểm họa (Hazard) và xung nhiễu (Glitch): một tập bao phủ tối thiểu có thể chứa các hiểm họa tĩnh. Để thiết kế không có hiểm họa, cần bao gồm các tế bào chính dư thừa — công cụ này đánh dấu chúng nhưng không tự động thêm chúng vào tập bao phủ chống hiểm họa.
• Tối giản đa đầu ra: nếu nhiều hàm chia sẻ cùng các biến, việc tối giản chung (dùng chung cổng) sẽ giúp phần cứng nhỏ gọn hơn. Công cụ này chỉ tối giản một hàm tại một thời điểm.

Câu hỏi thường gặp

Bản đồ Karnaugh là gì?

Bản đồ Karnaugh (K-map) là một phương pháp trực quan để tối giản các biểu thức Boolean. Các ô được sắp xếp sao cho các ô kề nhau chỉ khác nhau bởi một biến (thứ tự mã Gray). Việc nhóm các số 1 thành các hình chữ nhật có kích thước 1, 2, 4, 8 hoặc 16 sẽ giúp tìm ra biểu thức Tổng của các Tích tối thiểu.

Sự khác biệt giữa SOP và POS là gì?

SOP (Sum of Products - Tổng của các Tích) nhóm các ô chứa số 1 và thực hiện phép OR các số hạng tích của chúng, ví dụ: A'B + CD. POS (Product of Sums - Tích của các Tổng) nhóm các ô chứa số 0 và thực hiện phép AND các số hạng tổng của chúng, ví dụ: (A + B')(C' + D). Cả hai đều mô tả cùng một hàm nhưng một dạng thường sẽ gọn hơn dạng kia.

Các điều kiện tùy định (don't-care) là gì và tại sao nên sử dụng chúng?

Các số hạng tùy định (được ký hiệu là X) là các tổ hợp đầu vào mà giá trị đầu ra không quan trọng — chúng không bao giờ xảy ra hoặc giá trị của chúng không ảnh hưởng đến hệ thống. Công cụ giải có thể coi chúng là 0 hoặc 1, tùy theo lựa chọn nào tạo ra biểu thức đơn giản hơn. Don't-care thường giúp giảm đáng kể số lượng biến trong biểu thức.

Tế bào chính (prime implicant) là gì?

Tế bào chính là nhóm lớn nhất có thể của các ô chứa số 1 kề nhau (kích thước là lũy thừa của 2) mà không thể mở rộng thêm được nữa. Tế bào chính thiết yếu là tế bào bao phủ duy nhất ít nhất một minterm và phải có mặt trong mọi biểu thức tối giản.

Thuật toán Quine-McCluskey hoạt động như thế nào?

Quine-McCluskey là phương pháp bảng tương đương với K-map, phù hợp cho nhiều biến. Nó liệt kê tất cả các minterm dưới dạng nhị phân, nhóm chúng theo số lượng số 1, và lặp lại việc kết hợp các cặp chỉ khác nhau một bit. Các số hạng không thể kết hợp thêm là các tế bào chính. Một bảng tế bào chính sau đó sẽ chọn ra tập bao phủ tối thiểu.

Công cụ giải K-map này hỗ trợ bao nhiêu biến?

Công cụ này hỗ trợ từ 2 đến 5 biến. Bản đồ K-map 5 biến được hiển thị dưới dạng hai bản đồ 4×4 cạnh nhau (một cho A=0, một cho A=1). Vượt quá 5 biến, K-map trở nên không thực tế; khi đó hãy sử dụng các bước Quine-McCluskey cho các hàm lớn hơn.

Đọc thêm

• Bản đồ Karnaugh — Wikipedia (tiếng Anh)
• Thuật toán Quine-McCluskey — Wikipedia (tiếng Anh)
• Phương pháp Petrick — Wikipedia (tiếng Anh)