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

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

1. Tổng quan Chương này sẽ học về: - Phương pháp đánh giá ngõ ra của một mạch logic cho trước. - Phương pháp thiết kế một mạch logic từ biểu thức đại số cho trước. - Phương pháp thiết kế một mạch logic từ yêu cầu cho trước. - Các phương pháp để đơn giản/tối ưu một mạch logic giúp cho mạch thiết kế được tối ưu về diện tích, chi phí và tốc độ. 2
2. 1. Mạch logic số (logic circuit) • Dùng định lý Boolean để đơn giản hàm sau: Tên Dạng AND Dạng OR Định luật thống nhất 1A = A 0 + A = A Định luật không OA = O 1+ A = 1 Định luật Idempotent AA = A A + A = A Định luật nghịch đảo AA 0 A A 1 Định luật giao hoán AB = BA A + B = B + A Định luật kết hợp (AB)C = A(BC) (A+B)+C = A + (B+C) Định luật phân bố A + BC = (A + B)(A + C) A(B+C) = AB + AC Định luật hấp thụ A(A + B) = A A + AB = A Định luật De Morgan AB A B ABAB . 4
3. Dạng chính tắc (Canonical Form) • Dạng chính tắc 1: là dạng tổng của các tích chuẩn_1 (minterm_1) (tích chuẩn_1 là tích chuẩn mà tại tổ hợp đó hàm Boolean có giá trị 1). 6
4. Ví dụ • Câu hỏi: Trong các biểu thức sau, biểu thức nào ở dạng chính tắc? 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: – b và d 8
5. Dạng chuẩn (Standard Form) • Dạng chính tắc có thể được đơn giản hoá để thành dạng chuẩn tương đương – Ở dạng đơn giản hoá này, có thể có ít nhóm AND/OR và/hoặc các nhóm này có ít biến hơn • Dạng tổng các tích - SoP (Sum-of-Product) – Ví dụ: • Dạng tích các tổng - PoS (Product-of-Sum) – Ví dụ : Có thể chuyển SoP về dạng chính tắc bằng cách AND thêm (x+x’) và PoS về dạng chính tắc bằng cách OR thêm xx’ 10
6. 2. Thiết kế một mạch logic 12
7. Các bước thiết kế một mạch logic số • Bước 1: xây dựng bảng sự thật/chân trị 14
8. Các bước thiết kế một mạch logic số • Bước 3: đơn giản biểu thức logic qua biến đổi đại số 16
9. Các bước thiết kế một mạch logic số • Bước 4: vẽ sơ đồ mạch logic cho 18
10. Chi phí để tạo ra một mạch logic • Chi phí (cost) để tạo ra một mạch logic liên quan đến: – Số cổng (gates) được sử dụng – Số đầu vào của mỗi cổng • Một literal là một biến kiểu Boolean hay bù của nó 20
11. Chi phí để tạo ra một mạch logic Ví dụ • Tính chi phí của các biểu thức sau: 22
12. Bìa Karnaugh (bìa K) • Bìa Karnaugh là biểu diễn của bảng sự thật dưới dạng một ma trận các ô (matrix of squares/cells) trong đó mỗi ô tương ứng với một dạng tích chuẩn (minterm) hay dạng tổng chuẩn (Maxterm). • Với một hàm có n biến, chúng ta cần một bảng sự thật có 2n hàng, tương ứng bìa Karnaugh có 2n ô (cell). • Để biểu diễn một hàm logic, một giá trị ngõ ra trong bảng sự thật sẽ được copy sang một ô tương ứng trong bìa K 24
13. Bìa Karnaugh 3 biến Ví dụ: (đại số) (chưa tối ưu) (tối ưu) 26
14. Bìa Karnaugh 3 biến 28
15. Bìa Karnaugh 3 biến F F 30
16. Bìa Karnaugh 3 biến Ví dụ: F = x’z + xy + yz F = x’z + xy Rút gọn chưa tối ưu Rút gọn tối ưu 32
17. Bìa Karnaugh 4 biến F = ac + a’b + d’ Simplify Khoa KTMT 34
18. Bìa Karnaugh 4 biến 36 36
19. Hàm đặc tả không đầy đủ (tt) (Incompletely Specified Functions) • Trong trường hợp trên thì chúng ta phải làm thế nào để đơn giản N2? A B C F Giả sử F(0,0,1) = 0 và F(1,1,0)=0, ta có 0 0 0 1 biểu thức sau: 0 0 1 X 0 0 1 0 1 0 1 1 1 F(A,B,C) = A’B’C’ + A’BC’ + A’BC + ABC 1 0 0 0 1 0 1 0 = A’C’(B’ + B) + (A’ + A)BC 1 1 0 X 0 1 1 1 1 + = A’C’·1 + 1·BC = A’C’ + BC 38
20. Hàm đặc tả không đầy đủ (tt) (Incompletely Specified Functions) Tất cả các ô 1 phải được khoanh tròn, nhưng với ô có giá trị X thì tùy chọn, các ô này chỉ được - xem xét là 1 nếu đơn giản biểu thức theo dạng SOP - hoặc xem xét là 0 nếu đơn giản biểu thức theo dạng POS 40
21. Implicant cơ bản (Prime Implicant) • Implicant: là dạng tích chuẩn của một hàm – Một nhóm các ô 1 hoặc một ô 1 đơn lẻ trên một bìa-K kết hợp với nhau tạo ra một dạng tích chuẩn • Implicant cơ bản (prime implicant): – Implicant không thể kết hợp với bất kì ô 1 nào khác để loại bỏ một biến • Tất cả các prime implicant của 1 hàm có thể đạt được bằng cách phát triển các nhóm 1 trong bìa-K lớn nhất có thể 42
22. Tối thiểu biểu thức sử dụng Essential Prime Implicant (EPI) • Xác định tất cả các prime implicants – Để xác định các prime implicant, các giá trị tùy định (don’t care) được coi như là giá trị 1. Tuy nhiên, một prime implicant chỉ gồm các giá trị tùy định thì không cần cho biểu thức ngõ ra. – Không phải tất cả các prime implicant đều cần thiết để tạo ra minimum SOP • Ví dụ – Tất cả các prime implicants: a'b'd, bc', ac, a'c'd, ab, b'cd (chỉ gồm các giá trị không xác định) – Minimum solution: F = a'b'd+bc'+ac 44
23. Tối thiểu biểu thức sử dụng Essential Prime Implicant (EPI) (tt) 1. Chọn ra tất cả EPI 2. Tìm ra một tập nhỏ nhất các prime implicant gom được tất cả các minterm còn lại (các minterm không bị gom bởi các EPI) 46
24. Ví dụ • Step 1: đánh dấu 14 • Step 2: đánh dấu 15 • Step 3: đánh dấu 16 – EPI => A'B được chọn • Step 4: đánh dấu 18 • Step 5: đánh dấu 19 • Step 6: đánh dấu 110 – EPI => AB'D' được chọn • Step 7: đánh dấu 113 (tại điểm này tất cả EPIs đã được xác định) • Step 8: AC'D được chọn để gom các số 1 còn lại 48
25. Bìa Karnaugh 5 biến 50
26. Bìa Karnaugh 5 biến 52
27. 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) 54
28. 4. Cổng XOR và XNOR 56
29. Mạch Exclusive NOR (XNOR) • Exlusive NOR (XNOR) cho ra kết quả HIGH khi hai đầu vào giống nhau – XOR và XNOR cho ra kết quả ngược nhau Output expression XNOR x = AB + AB Gate Symbol 58
30. TỐI ƯU MẠCH BẰNG CỔNG XOR VÀ XNOR Làm sao tối ưu mạch bằng cổng XNOR 60
31. Any question? 62