Bản đồ Karnaugh và điều kiện don’t-care

Liên hệ bảng chân trị với chi phí cài đặt

Bảng chân trị^{iBảng chân trị Bảng liệt kê đủ mọi tổ hợp đầu vào và đầu ra tương ứng. Sự thay đổi theo thời gian được kiểm tra riêng bằng dạng sóng. Tìm hiểu thêm} xác định chức năng; tối thiểu hóa logic quyết định dùng biểu thức nào để cài đặt. Với ba đầu vào, định nghĩa số minterm bằng số nhị phân ABC, trong đó A là bit cao nhất.

Ví dụ minterm 4 là ABC=100. Các hàng không được liệt kê là 0, 2, 6; chúng có đầu ra 0. Thay vì luôn cài năm hạng tích riêng, có thể nhóm các hạng chỉ khác một bit.

Bản đồ Karnaugh là bảng chân trị sắp theo thứ tự khác

Xếp cột BC theo 00, 01, 11, 10. Đây là thứ tự mã Gray, trong đó hai cột kề nhau chỉ đổi một bit. Cột ngoài cùng trái và phải cũng kề nhau.

Nhóm phải là hình chữ nhật với số ô $1,2,4,8,\ldots$. Bao gồm ô 0 sẽ đổi chức năng. Một ô 1 được phép thuộc nhiều nhóm.

1. Nhóm bốn ô thuộc hai cột C=1: đầu ra vẫn là 1 khi A và B thay đổi, nên còn hạng C.
2. Nhóm hai ô BC=00 và 01 ở hàng A=1: chỉ C thay đổi, nên còn $A\overline B$.
3. OR hai nhóm sẽ bao phủ mọi ô 1 và tránh mọi ô 0.

Đối chiếu định nghĩa gốc và biểu thức tối thiểu ở đủ tám đầu vào. Cần kiểm tra riêng hai điều: biểu thức ngắn hơn và chức năng vẫn như cũ.

Quá trình này chuyển hai nhóm trên bản đồ thành biểu thức. Trong nhóm C, A và B thay đổi; trong nhóm hai ô, C thay đổi, nên loại những biến đó khỏi hạng.

don’t-care là quyền tối ưu và giả thiết đầu vào

Giả sử quy ước hệ thống bảo đảm ABC=000 không bao giờ xuất hiện. Đặt ô đó là X cho phép dùng như 0 hoặc 1 tùy nhu cầu. Có thể nhóm bốn ô B=0 để có biểu thức đơn giản hơn.

Biểu thức mới bằng 1 tại ABC=000, khác bảng chân trị đầy đủ ban đầu. Vì thế muốn nói “cùng mạch”, phải kèm điều kiện đầu vào không phải 000. Nếu 000 xuất hiện lúc khởi tạo hoặc phục hồi lỗi, tối ưu này có thể vi phạm yêu cầu hệ thống.

Tối thiểu hóa biểu thức khác với tối ưu chip

Ít literal hơn không bảo đảm diện tích, trễ và công suất đều tối ưu trong một thư viện cell cụ thể. Tải, fan-out, cổng phức hợp có sẵn, dây nối và glitch đều ảnh hưởng. Ở bước này cần chắc chắn về tương đương chức năng và giả thiết đầu vào; chi phí vật lý được đánh giá qua tổng hợp và kết quả thời gian.

Đọc thêm: MIT OpenCourseWare — Combinational Logic

Thực hành · Kiểm tra chồng nhóm và điều kiện don’t-care

1. Chọn nhóm C. A và B đều đổi trong bốn ô, nên chỉ còn C.
2. Chọn nhóm A·¬B. Nó bao phủ m4, m5; m5 chồng với nhóm C. Cho phép chồng nhóm nhưng không được chứa ô 0.
3. Nhấn m0 hai lần: 0 → 1 → X. Sau khi thành X, đặc tả không đầy đủ có d(0). Nhóm B=0 mở rộng và biểu thức thành $C+\overline B$.
4. Nhấn m0 thêm một lần để trở về 0. Khi yêu cầu gốc được khôi phục, nhóm lớn hơn phải biến mất.

Chọn nhóm không đổi giá trị. Toàn bộ biểu thức bao phủ các ô 1 vẫn giữ nguyên; khung chỉ nhấn mạnh một hạng đang xem. “Tối thiểu” ở đây ưu tiên số hạng tích, sau đó số literal; nếu có nhiều nghiệm, chỉ hiển thị một nghiệm.