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

CHƯƠNG 4: BÌA KARNAUGH
NHẬP MÔN MẠCH SỐ
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 2
Nội dung
 Tổng quan
 Các dạng biểu diễn biểu thức logic
 Thiết kế một mạch số
 Bìa Karnaugh (bản đồ Karnaugh)
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 độ.
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 3
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 4
Nội dung
 Tổng quan
 Các dạng biểu diễn biểu thức logic
Khái niệm tích chuẩn, tổng chuẩn
Dạng chính tắc (Canonical form)
Dạng chuẩn (Standard form)
 Thiết kế một mạch số
 Bìa Karnaugh (bản đồ Karnaugh)
Khái niệm 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)
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 5
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 (Minterms_1)
(tích chuẩn_1 là tích chuẩn mà tại tổ hợp đó hàm Boolean có giá trị 1).
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 6
Dạng chính tắc (Canonical Form)
 Dạng chính tắc 2: là dạng tích của các tổng chuẩn_0 (Maxterms_0)
(tổng chuẩn_0 là tổng chuẩn mà tại tổ hợp đó hàm Boolean có giá trị 0).
0 2 5 6 7
( , , ) ( )( )( )( )( )F x y z x y z x y z x y z x y z x y z
M M M M M
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 7
Tổng các tích chuẩn Sum 
of Minterms
Tích các tổng chuẩn
Product of Maxterms
Chỉ quan tâm hàng có
giá trị 1
Chỉ quan tâm hàng có
giá trị 0
X = 0: viết X X = 0: viết X
X = 1: viết X X = 1: viết X
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 8
Dạng chính tắc (Canonical Form)
Dạng chính tắc (Canonical Form)
 Trường hợp tùy định (don’t care)
 Hàm Boolean theo dạng chính tắc:
F (A, B, C) =  (2, 3, 5) + d(0, 7) (chính tắc 1)
=  (1, 4, 6) . D(0, 7) (chính tắc 2)
A B C F
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
X
0
1
1
0
1
0
X
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 9
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
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 10
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’ 
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 11
 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ả
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 12
Ví dụ
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 13
Nội dung
 Tổng quan
 Các dạng biểu diễn biểu thức logic
 Thiết kế một mạch số
 Bìa Karnaugh (bản đồ Karnaugh)
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
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 14
Thiết kế một mạch số
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ị
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 15
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
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
Biểu thức SOP cho ngõ ra X:
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 16
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ố
nhằm làm giảm số cổng logic cần sử dụng (nhằm làm
giảm chi phí thiết kế)
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 17
Các bước thiết kế một mạch logic số
 Bước 4: Vẽ sơ đồ mạch logic cho
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 18
 Chi phí (cost) để tạo ra một mạch logic số liên quan
đến:
Số cổng (gates) được sử dụng
Số đầu vào của mỗi cổng
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 19
Chi phí thiết kế một mạch logic số
 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 (biến) trong term thứ j của biểu thức B
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved.
Chi phí thiết kế một mạch logic số
𝐶 𝐵 = 𝑂 𝐵 + ෍
𝑗=0
𝐾−1
𝑃𝑗 𝐵
𝑂 𝐵 = ቊ𝑚 𝑛ế𝑢 𝐵 𝑐ó 𝑚 𝑡𝑒𝑟𝑚
0 𝑛ế𝑢 𝐵 𝑐ó 1 𝑡𝑒𝑟𝑚
𝑃𝑗 𝐵 = ቊ
𝑚 𝑛ế𝑢 𝑡𝑒𝑟𝑚 𝑡ℎứ 𝑗 𝑐ủ𝑎 𝐵 𝑐ó 𝑚 𝑙𝑖𝑡𝑒𝑟𝑎𝑙
0 𝑛ế𝑢 𝑡𝑒𝑟𝑚 𝑡ℎứ 𝑗 𝑐ủ𝑎 𝐵 𝑐ó 1 𝑙𝑖𝑡𝑒𝑟𝑎𝑙
 Tính chi phí thiết kế mạch logic số của các biểu thức sau:
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 21
Chi phí thiết kế một mạch logic số
Hạn chế của việc rút gọn bằng biến đổi đại số
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved. 22
 Hai vấn đề của việc rút gọn biểu thức trong bước 3 dùng
các phép biến đổi đại số nhằm giảm chi phí thiết kế:
Không có hệ thống
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
23
11/2/2017 Copyrights 2016 UIT-CE. All Rights Reserved.
Tóm tắt nội dung chương học
 Qua Phần 1 - Chương 4, sinh viên cần nắm những nội
dung chính sau:
Các dạng biểu diễn một biểu thức logic
Quy trình thiết kế một mạch số
Đánh giá chi phí thiết kế của một mạch số
Thảo luận?