Bài giảng Nhập môn Mạch số - Chương 4: Bìa Karnaugh - Nguyễn Thanh Sang

Nội dung text: Bài giảng Nhập môn Mạch số - Chương 4: Bìa Karnaugh - Nguyễn Thanh Sang

1. NHẬP MÔN MẠCH SỐ Chương 4 Bìa Karnaugh 1
2. Nội dung 1. Mạch logic số 2. Thiết kế một mạch số 3. Bìa Karnaugh (bản đồ Karnaugh) 4. Cổng XOR/XNOR 3
3. Tích chuẩn và Tổng chuẩn • Tích chuẩn (minterm): mi là các số hạng tích (AND) mà tất cả các biến xuất hiện ở dạng bình thường (nếu là 1) hoặc dạng bù (complement) (nếu là 0) • Tổng chuẩn (Maxterm): Mi là các số hạng tổng (OR) mà tất cả các biến xuất hiện ở dạng bình thường (nếu là 0) hoặc dạng bù (complement) (nếu là 1) 5
4. Dạng chính tắc (Canonical Form) (tt) • Dạng chính tắc 2: là dạng tích của các tổng chuẩn_0 (Maxterm_0) (tổng chuẩn_0 là tổng chuẩn mà tại tổ hợp đó hàm Boolean có giá trị 0). Fxyz(,,)( xyzxyzxyzxyzxyz )( )( )( )( ) MMMMM 0 2 5 6 7 A B C F 0 0 0 X 0 0 1 0 0 1 0 1 • Trường hợp tùy định (don’t care) 0 1 1 1 1 0 0 0 Hàm Boolean theo dạng chính tắc: 1 0 1 1 F (A, B, C) =  (2, 3, 5) + d(0, 7) (chính tắc 1) 1 1 0 0 1 1 1 X =  (1, 4, 6) . D(0, 7) (chính tắc 2) 7
5. Dạng chính tắc (Canonical Forms) (tt) Tổng các tích chuẩn Tích các tổng chuẩn Sum of Minterms Product of Maxterms Chỉ quan tâm hàng có Chỉ quan tâm hàng có giá trị 1 giá trị 0 X = 0: viết X’ X = 0: viết X X = 1: viết X X = 1: viết X’ 9
6. Ví dụ • Câu hỏi: Trong các biểu thức sau, biểu thức nào ở dạng chuẩn? a. XYZ + X’Y’ b. X’YZ + XY’Z + XYZ’ c. X + YZ d. X + Y + Z e. (X+Y)(Y+Z) • Trả lời: – Tất cảChuẩn 11
7. Ví dụ • Thiết kế một mạch logic số với – 3 ngõ vào – 1 ngõ ra – Kết quả ngõ ra bằng 1 khi có từ 2 ngõ vào trở lên có giá trị bằng 1 13
8. Các bước thiết kế một mạch logic số • Bước 2: chuyển bảng sự thật sang biểu thức logic A B C X Biểu thức SOP cho ngõ ra X: 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Các nhóm AND cho mỗi trường hợp ngõ ra là 1 15
9. Hạn chế của biến đổi đại số • Hai vấn đề của biến đổi đại số 1. Không có hệ thống 2. Rất khó để kiểm tra rằng giải pháp tìm ra đã là tối ưu hay chưa? • Bìa Karnaugh sẽ khắc phục những nhược điểm này – Tuy nhiên, bìa Karnaugh chỉ để giải quyết các hàm Boolean có không quá 5 biến 17
10. 3. Bìa Karnaugh 19
11. Chi phí để tạo ra một mạch logic • Chi phí của một biểu thức Boolean B được biểu diễn dưới dạng tổng của các tích (Sum-of-Product) như sau: Trong đó k là số các term (thành phần tích) trong biểu thức B O(B) : số các term trong biểu thức B PJ(B): số các literal trong term thứ j của biểu thức B 21
12. Bìa Karnaugh • M. Karnaugh, “The Map Method for Synthesis of combinatorial Logic Circuits”, Transactions of the American Institute of Electrical Engineers, Communications and Electronics, Vol. 72, pp. 593-599, November 1953. • Bìa Karnaugh là một công cụ hình học để đơn giản hóa các biểu thức logic • Tương tự như bảng sự thật, bìa Karnaugh sẽ xác định giá trị ngõ ra cụ thể tại các tổ hợp của các đầu vào tương ứng. 23
13. Bìa Karnaugh 2 biến 25
14. Bìa Karnaugh 3 biến Cách 2 Cách 3 Cách 1 Lưu ý: có thể sử dụng cách nào để biểu diễn bìa-K cũng được, nhưng phải lưu ý trọng số của các biến thì mới đảm bảo thứ tự các ô theo giá trị thập phân. 27
15. Bìa Karnaugh 3 biến f (chưa tối ưu) (tối ưu) 29
16. Bìa Karnaugh 3 biến G G G = F’ 31
17. Bìa Karnaugh 3 biến Ví dụ: 33
18. Bìa Karnaugh 4 biến 35 35
19. Hàm đặc tả không đầy đủ (Incompletely Specified Functions) • Giả thuyết: N1 không bao giờ cho kết quả ABC = 001 và ABC = 110 • Câu hỏi : F cho ra giá trị gì trong trường hợp ABC = 001 và ABC = 110 ? We don’t care!!! 37
20. Hàm đặc tả không đầy đủ (tt) (Incompletely Specified Functions) • Tuy nhiên, nếu giả sử F(0,0,1)=1 và F(1,1,0)=1, ta có biểu thức sau: F(A,B,C) = A’B’C’ + A’B’C + A’BC’ + A’BC + ABC’ + ABC A B C F = A’B’(C’ + C) + A’B(C’ + C) + AB(C’ + C) 0 0 0 1 0 0 1 X 1 = A’B’ ·1 + A’B ·1 + AB ·1 0 1 0 1 = A’B’ + A’B + AB 0 1 1 1 1 0 0 0 = A’B’ + A’B + A’B + AB 1 0 1 0 1 1 0 X 1 = A’(B’ + B) + (A’ + A)B 1 1 1 1 + = A’·1 + 1·B = A’ + B So sánh với giả thuyết trước đó: F(A,B,C) = A’C’ + BC, giải pháp nào chi phí ít hơn (tốt hơn)? 39
21. Đơn giản POS (Product of Sum) • Khoanh tròn giá trị 0 thay vì giá trị 1 Ví dụ: f = x’z’ + wyz + w’y’z’ + x’y 41
22. Ví dụ • a'b'c, a'cd', ac' là các prime implicants • a'b'c'd', abc', ab'c' là các implicants (nhưng không phải là prime implicants) 43
23. Tối thiểu biểu thức sử dụng Essential Prime Implicant (EPI) (tt) • Essential prime implicant (EPI): prime implicant có ít nhất 1 ô không bị gom bởi các prime implicant khác 45
24. Tối thiểu biểu thức sử dụng Essential Prime Implicant (EPI) (tt) • Lưu đồ để xác định một minimum SOP sử dụng K-map 47
25. Bìa Karnaugh 5 biến 49
26. Bìa Karnaugh 5 biến 51
27. Bìa Karnaugh 5 biến Phương pháp khác Ví dụ 1 F (31,30,29,27,25,22,21,20,17,16,15,13,11,9,6,4,1,0) 53
28. Bìa Karnaugh 5 biến Ví dụ 1 (tt) F (31,30,29,27,25,22,21,20,17,16,15,13,11,9,6,4,1,0) F = ACDE’ + B’CE’ + BE + B’C’D’ + AB’D’ 55
29. Mạch Exclusive OR (XOR) • Exlusive OR (XOR) cho ra kết quả HIGH khi hai đầu vào khác nhau Output expression: x = AB + AB XOR Gate Symbol 57
30. Ví dụ • Thiết kế một mạch để phát hiện ra 2 số nhị phân 2 bit có bằng nhau hay không 59
31. Bộ tạo và kiểm tra Parity (Parity generator and checker) • Cổng XOR và XNOR rất hữu dụng trong các mạch với mục đích tạo (bộ phát) và kiểm tra (bộ nhận) parity bit 61