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

1Chương 4
NHẬP MÔN MẠCH SỐ
Bìa Karnaugh 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
2Tổ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 độ.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
3Nộ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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
4• 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
0 AA 1 AA
BAAB .A B A B 
1. Mạch logic số (logic circuit)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
5Tí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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
6Dạ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).
CuuDuongThanCong.com https://fb.com/tailieudientucntt
7Dạ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 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
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
8Ví 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
9Dạ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’
CuuDuongThanCong.com https://fb.com/tailieudientucntt
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’ 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
11
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
12
2. Thiết kế một mạch logic 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
13
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
14
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ị
CuuDuongThanCong.com https://fb.com/tailieudientucntt
15
• 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ố
CuuDuongThanCong.com https://fb.com/tailieudientucntt
16
• 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ố
CuuDuongThanCong.com https://fb.com/tailieudientucntt
17
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
18
• Bước 4: vẽ sơ đồ mạch logic cho
Các bước thiết kế một mạch logic số
CuuDuongThanCong.com https://fb.com/tailieudientucntt
19
3. Bìa Karnaugh
CuuDuongThanCong.com https://fb.com/tailieudientucntt
20
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ó
CuuDuongThanCong.com https://fb.com/tailieudientucntt
21
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
22
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:
CuuDuongThanCong.com https://fb.com/tailieudientucntt
23
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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
24
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
25
Bìa Karnaugh 2 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
26
Bìa Karnaugh 3 biến
Ví dụ:
(chưa tối ưu)
(tối ưu)
(đại số)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
27
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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
28
Bìa Karnaugh 3 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
29
Bìa Karnaugh 3 biến
f
(chưa tối ưu)
(tối ưu)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
30
Bìa Karnaugh 3 biến
F F
CuuDuongThanCong.com https://fb.com/tailieudientucntt
31
Bìa Karnaugh 3 biến
G = F’
G G
CuuDuongThanCong.com https://fb.com/tailieudientucntt
32
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
33
Bìa Karnaugh 3 biến
Ví dụ:
CuuDuongThanCong.com https://fb.com/tailieudientucntt
34
Bìa Karnaugh 4 biến
Khoa KTMT
Simplify
F = ac + a’b + d’
CuuDuongThanCong.com https://fb.com/tailieudientucntt
35
Bìa Karnaugh 4 biến
35
CuuDuongThanCong.com https://fb.com/tailieudientucntt
36
Bìa Karnaugh 4 biến
36
CuuDuongThanCong.com https://fb.com/tailieudientucntt
37
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!!!
CuuDuongThanCong.com https://fb.com/tailieudientucntt
38
• 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 
A B C F
0 0 0 1
0 0 1 X
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 X
1 1 1 1
+
0
0
CuuDuongThanCong.com https://fb.com/tailieudientucntt
39
• 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)
A B C F
0 0 0 1
0 0 1 X
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 X
1 1 1 1
+
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
40
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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
41
Đơ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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
42
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ể
CuuDuongThanCong.com https://fb.com/tailieudientucntt
43
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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
44
• 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 Prime Implicant (EPI)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
45
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
46
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 Prime Implicant (EPI) (tt)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
47
• 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 Prime Implicant (EPI) (tt)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
48
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
49
Bìa Karnaugh 5 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
50
Bìa Karnaugh 5 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
51
Bìa Karnaugh 5 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
52
Bìa Karnaugh 5 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
53
Ví dụ 1
(31,30,29,27,25,22,21,20,17,16,15,13,11,9,6,4,1,0)F 
Bìa Karnaugh 5 biến
Phương pháp khác
CuuDuongThanCong.com https://fb.com/tailieudientucntt
54
Ví dụ 1 (tt)
(31,30,29,27,25,22,21,20,17,16,15,13,11,9,6,4,1,0)F 
Bìa Karnaugh 5 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
55
Ví dụ 1 (tt)
(31,30,29,27,25,22,21,20,17,16,15,13,11,9,6,4,1,0)F 
F = ACDE’ + B’CE’ + BE + B’C’D’ + AB’D’
Bìa Karnaugh 5 biến
CuuDuongThanCong.com https://fb.com/tailieudientucntt
56
4. Cổng XOR và XNOR
CuuDuongThanCong.com https://fb.com/tailieudientucntt
57
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
58
• 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 + ABXNOR 
Gate 
Symbol
CuuDuongThanCong.com https://fb.com/tailieudientucntt
59
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
60
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
61
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
62
Any question?
CuuDuongThanCong.com https://fb.com/tailieudientucntt