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

Chương 4 
NHẬP MÔN MẠCH SỐ 
Bìa 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 độ. 
Nội dung 
Mạch logic số 
Thiết kế một mạch số 
Bìa Karnaugh (bản đồ Karnaugh) 
Cổng XOR/XNOR 
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 
 Đị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 
1. Mạch logic số (logic circuit) 
Tích chuẩn và Tổng chuẩn 
Tích chuẩn (minterm): m i 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): M i 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) 
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). 
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). 
Trường hợp tùy định (don’t care) 
H àm Boole an 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 
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? 
XYZ + X’Y’ 
X’YZ + XY’Z + XYZ’ 
X + YZ 
X + Y + Z 
(X+Y)(Y+Z ) 
Trả lời: 
b và d 
Dạng chính tắc (Canonical Forms ) (tt) 
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’ 
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’ 
Ví dụ 
Câu hỏi: Trong các biểu thức sau, biểu thức nào ở dạng chuẩn? 
XYZ + X’Y’ 
X’YZ + XY’Z + XYZ’ 
X + YZ 
X + Y + Z 
(X+Y)(Y+Z) 
Trả lời: 
Tất cả 
Chuẩn 
2. Thiết kế một mạch logic 
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 
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ị 
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: 
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ố 
Các bước thiết kế một mạch logic số 
Hạn chế của biến đổi đại số 
Hai vấn đề của biến đổi đại số 
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 Booleancó không quá 5 biến 
Bước 4: vẽ sơ đồ mạch logic cho 
Các bước thiết kế một mạch logic số 
3. Bìa Karnaugh 
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ó 
Chi phí để tạo ra một mạch logic 
Chi phí của một biểu thức B oolean 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 
P J (B): số các literal trong term thứ j của biểu thức B 
21 
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: 
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. 
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 ( M axterm). 
Với một hàm có n biến , chúng ta cần một bảng sự thật có 2 n hàng, tương ứng bìa Karnaugh có 2 n ô (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 
Bìa Karnaugh 2 biến 
Bìa Karnaugh 3 biến 
Ví dụ: 
(chưa tối ưu) 
(tối ưu) 
(đại số) 
Bìa Karnaugh 3 biến 
Cách 1 
Cách 2 
Cách 3 
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. 
Bìa Karnaugh 3 biến 
Bìa Karnaugh 3 biến 
f 
(chưa tối ưu) 
(tối ưu) 
Bìa Karnaugh 3 biến 
F 
F 
Bìa Karnaugh 3 biến 
G = F’ 
G 
G 
Bìa Karnaugh 3 biến 
Rút gọn chưa tối ưu 
Rút gọn tối ưu 
Ví dụ: 
F = x’z + xy + yz 
F = x’z + xy 
Bìa Karnaugh 3 biến 
Ví dụ: 
Bìa Karnaugh 4 biến 
Khoa KTMT 
Simplify 
F = ac + a’b + d’ 
Bìa Karnaugh 4 biến 
35 
Bìa Karnaugh 4 biến 
36 
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!!! 
Trong trường hợp trên thì chúng ta phải làm thế nào để đơn giản N2? 
Giả sử F(0,0,1) = 0 và F(1,1,0)=0, ta có biểu thức sau: 
Hàm đặc tả không đầy đủ (tt) (Incompletely Specified Functions) 
= A’C’(B’ + B) + (A’ + A)BC 
= A’C’·1 + 1·BC 
= A’C’ + BC 
F(A,B,C ) = A’B’C’ + A’BC’ + A’BC + ABC 
0 
0 
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: 
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)? 
Hàm đặc tả không đầy đủ (tt) (Incompletely Specified Functions) 
F(A,B,C) = A’B’C’ + A’B’C + A’BC’ + A’BC + ABC’ + ABC 
 = A’B’ ·1 + A’B ·1 + AB ·1 
 = A’B’(C’ + C) + A’B(C’ + C) + AB(C’ + C) 
 = A’B’ + A’B + AB 
 = A’B’ + A’B + A’B + AB 
 = A’(B’ + B) + (A’ + A)B 
 = A’·1 + 1·B 
 = A’ + B 
1 
1 
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 
Hàm đặc tả không đầy đủ (tt) (Incompletely Specified Functions) 
Đơ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 
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ể 
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 ) 
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 
Tối thiểu biểu thức sử dụng Essential P rime Implicant (EPI) 
Tối thiểu biểu thức sử dụng Essential P rime 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 
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) 
Tối thiểu biểu thức sử dụng Essential P rime Implicant (EPI ) (tt) 
Lưu đồ để xác định một minimum SOP sử dụng K-map 
Tối thiểu biểu thức sử dụng Essential P rime Implicant (EPI ) (tt) 
Ví dụ 
Step 1: đánh dấu 1 4 
Step 2: đánh dấu 1 5 
Step 3: đánh dấu 1 6 
EPI => A'B được chọn 
Step 4: đánh dấu 1 8 
Step 5: đánh dấu 1 9 
Step 6: đánh dấu 1 10 
EPI => AB'D' được chọn 
Step 7: đánh dấu 1 13 
(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 
Bìa Karnaugh 5 biến 
Bìa Karnaugh 5 biến 
Bìa Karnaugh 5 biến 
Bìa Karnaugh 5 biến 
Ví dụ 1 
Bìa Karnaugh 5 biến 
Phương pháp khác 
Ví dụ 1 (tt) 
Bìa Karnaugh 5 biến 
Ví dụ 1 (tt) 
F = ACDE’ + B’CE’ + BE + B’C’D’ + AB’D’ 
Bìa Karnaugh 5 biến 
4 . Cổng XOR và XNOR 
Mạch Exclusive OR (XOR) 
Exlusive OR (XOR) cho ra kết quả HIGH khi hai đầu vào khác nhau 
x = AB + AB 
Output expression: 
XOR Gate Symbol 
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 
Mạch Exclusive NOR (XNOR) 
Output expression 
x = AB + AB 
XNOR Gate Symbol 
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 
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 
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 
Any question ?