Giáo trình kỹ thuật xung- số phần 4

Chia sẻ: Nguyễn Thị Hồng Ngọc | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

108
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

CHƯƠNG I HỆ THỐNG ĐẾM VÀ KHÁI NIỆM VỀ MÃ 1.1 HỆ THỐNG SỐ ĐẾM 1.1.1 Hệ đếm 1.1.1.1 Khái niệm Hệ đếm là tập hợp các phương pháp gọi và biểu diễn các con số bằng các ký hiệu có giá trị số lượng xác định gọi là chữ số. 1.1.1.2 Phân loại

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình kỹ thuật xung- số phần 4

Phần 2: Kỹ thuật số 78
CHƯƠNG I HỆ THỐNG ĐẾM VÀ KHÁI NIỆM VỀ MÃ 1.1 HỆ THỐNG SỐ ĐẾM 1.1.1 Hệ đếm 1.1.1.1 Khái niệm Hệ đếm là tập hợp các phương pháp gọi và biểu diễn các con số bằng các ký hiệu có giá trị số lượng xác định gọi là chữ số. 1.1.1.2 Phân loại Phân thành 2 loại: a. Hệ đếm theo vị trí: Là hệ đếm mà trong đó giá trị số lượng của chữ số còn phụ thuộc vào vị trí của nó đứng trong con số/ Ví dụ: 2008 (Hệ thập phân), 1111 (Hệ nhị phân) b. Hệ đếm không theo vị trí Là hệ đếm mà trong đó giá trị số lượng của chữ số không phụ thuộc vào vị trí của nó tương ứng trong con số Ví dụ: Hệ đếm La mã: I, II, V,… 1.1.2 Cơ số của hệ đếm Nếu một hệ đếm có cơ sở là N thì một con số bất kỳ trong hệ đếm đó sẽ có giá trị trong hệ thập phân thông thường như sau: A = a n −1 .N n −1 + a n −2 .N n − 2 + ... + a1 N 1 + a 0 .N 0 Trong đó ak là các chữ số lập thành con số (k = 0, 1 … n-1) và 0 < ak < N-1 Sau đây là một số hệ đếm thông dụng: + Hệ đếm mười (thập phân): có cơ sở là 10, các chữ số trong hệ đếm này là: 0, 1, 2, 3, 4, 5, 6, 7, 8 và 9. Ví dụ: con số 1278 = 1.103 + 2.102 + 7.101 + 8.100 biểu diễn một nghìn hai trăm bảy mươi tám đơn vị theo nghĩa thông thường + Hệ đếm hai (nhị phân): có cơ sở là 2, các chữ số trong hệ đếm này là 0 và 1 ví dụ: 1011 trong hệ nhị phân sẽ biểu diễn giá trị 79
A = 1.23 + 0.22 + 1.21 + 1.20 = 11 trong hệ đếm 10 thông thường + Hệ đếm mười sáu (thập lục phân – hexa): có cơ sở là 16 với các chữ số: 0, 1, 2, 3,4, 5, 6, 7, 8, 9, A, B, C, D, E và F Ví dụ: 8E trong hệ đếm hexa sẽ biểu diễn giá trị A = 8.161 + 14.160 = 142 trong hệ đếm 10 thông thường + Hệ đếm tám (bát phân – octa): có cơ sở là 8 với các chữ số 0, 1, 2, 3, 4, 5, 6 và 7. Ví dụ: con số 12 trong hệ octa biểu diễn giá trị A = 1.81 + 2.80 = 10 trong hệ đếm thông thường Bảng đối chiếu 16 con số đầu tiên trong các hệ đếm trên Hệ 10 Hệ 2 Hệ 16 Hệ 8 0 0000 0 0 1 0001 1 1 2 0010 2 2 3 0011 3 3 4 0100 4 4 5 0101 5 5 6 0110 6 6 7 0111 7 7 8 1000 8 10 9 1001 9 11 10 1010 A 12 11 1011 B 13 12 1100 C 14 13 1101 D 15 14 1110 E 16 15 1111 F 17 80
1.1.3 Đổi cơ số 1.1.3.1 Đổi từ cơ số d sang cơ số 10 Về phương pháp, người ta triển khai con số d dưới dạng đa thức theo cơ số của nó. Ví dụ: A(2) = 1101, đổi sang thập phân là: 1101 = 1.23 + 1.22 + 0.21 + 1.20 = 13(10) 1.1.3.2 Đổi cơ số 10 sang cơ số d Về nguyên tắc, người ta lấy con số trong cơ số chia liên tiếp cho cơ số d đến khi thương số bằng không thì thôi. Ví dụ: Kết luận: Gọi d1, d2, …, dn lần lượt là số dư của phép chia số thập phân cho cơ số d lần thứ 1,2,3,4,…,n thì kết quả sẽ là dndn-1…d1, nghĩa là số dư sau cùng là bit có trọng số cao nhất, còn số dư đầu tiên là bit có trọng số nhỏ nhất 1.2 HỆ ĐẾM NHỊ PHÂN VÀ KHÁI NIỆM VỀ MÃ 1.2.1 Hệ đếm nhị phân 1.2.1.1 Khái niệm Hệ đếm nhị phân còn gọi là hệ đếm cơ số 2 là hệ đếm mà trong đó người ta chỉ sử dụng hai ký hiệu 0 và 1 để biểu diễn tất cả các số. Hai ký hiệu đó gọi chung là bit hoặc digit và nó đặc trưng cho mạch điện tử có hai trạng thái ổn định. Một nhóm 4 bit gọi là nibble Một nhóm 8 bit gọi là byte Một nhóm nhiều bytes gọi là từ (word) Xét số nhị phân 4 bit: a3a2a1a0. Biểu diễn dưới dạng đa thức theo cơ số của nó là: a3a2 a1a0 = a3 .23 + a2 .22 + a1.21 + a0 .20 Trong đó: 81
20, 21, 22,23 được gọi là các trọng số - a0 được gọi là bit có trọng số nhỏ nhất, hay còn gọi bit có ý nghĩa nhỏ nhất. - a3 được gọi là bit có trọng số lớn nhất, hay còn gọi bit có ý nghĩa lớn nhất. - Như vậy, với số nhị phân 4 bit a3a2a1a0 mà trong đó mỗi chữ số ai chỉ nhận được 2 giá trị {0,1}, lúc đó ta có 24 = 16 tổ hợp nhị phân 1.2.1.2 Các phép tính trên số nhị phân a. Phép cộng Để cộng hai số nhị phân người ta dựa trên quy tắc cộng như sau: b. Phép trừ 82
c. Phép nhân d. Phép chia 1.2.2 Khái niệm về mã 1.2.2.1 Đại cương Trong đời sống hàng ngày, con người giao tiếp với nhau thông qua một hệ thống ngôn ngữ quy ước nhưng trong máy tính chỉ xử lý các dữ liệu nhị phân. Do đó, một vấn đề đặt ra là làm thế nào tạo ra một giao diện dễ dàng giữa người và máy tính, nghĩa là máy tính thực hiện được những bài toán do con người đặt ra. Để thực hiện điều đó, người ta đặt ra vấn đề mã hoá dữ liệu. Như vậy, mã hoá là quá trình biến đổi những ký hiệu quen thuộc của con người sang những ký hiệu quen thuộc với máy tính. 83
Các lĩnh vực mã hoá gồm: Số thập phân - Ký tự - Tập lệnh - Tiếng nói - Hình ảnh…. - 1.2.2.2 Mã hoá số thập phân a. Khái niệm Trong thực tế để mã hoá số thập phân, người ta sử dụng các số nhị phân 4 bit. Ví dụ: 0 0000 1 0001 2 0010 Việc sử dụng các số nhị phân để mã hoá các số phập phân gọi là các số BCD (Binary Code Decimal) b. Phân loại Khi sử dụng số nhị phân 4 bit để mã hoá các số thập phân tương ứng với 24 = 16 tổ hợp mã nhị phân phân biệt. Do việc chọn 10 tổ hợp trong 16 tổ hợp để mã hoá các ký hiệu thập phân từ 0 đến 9 mà trong thực tế xuất hiện nhiều loại mã BCD khác nhau. Mặc dù tồn tại nhiều loại mã BCD khác nhau nhưng người ta chia làm 2 loại chính: BCD có trọng số và BCD không có trọng số. - Mã BCD có trọng số: gồm có mã BCD tự nhiên, mã BCD số học. Mã BCD tự nhiên đó là loại mã mà trong đó các trọng số thươbngf được sắp xếp theo thú tự tăng dần. Ví dụ: Mã BCD 8421, mã BCD 5421 Mã BCD số học là loại mã mà trong đó có tổng các trong số luôn bằng 9. - Mã BCD không có trọng số: là loại mã không cho phép phân tích thành đa thức theo cơ số của nó. Ví dụ: Mã Gray, Mã Gray thừa 3 Đặc trưng của mã Gray là loại bộ mã mà trong đó 2 từ mã nhị phân đứng kế tiếp nhau bao giờ cũng chỉ khác nhau 1 bit. Ví dụ: Mã Gray: Còn đối với mã BCD 8421: 2 → 0011 84
3 → 0010 3 → 0011 Các bảng dưới đây trình bày một số loại mã thông dụng: Bảng 2: BCD tự nhiên và mã Grây Chú ý: Mã Grây được suy ra từ mã BCD 8421 bằng cách: các bit 0,1 đứng sau bit 0 (ở mã BCD 8421) khi chuyển sang mã grây thì được giữ nguyên, còn các bit 0,1 đứng sau bit 1 (ở mã BCD 8421). Khi chuyển sang mã grây thì được đổi ngược lại, nghĩa là từ bit 1 thành bit 0 và bit 0 thành bit 1. 1.2.2.3 Mạch nhận dạng số BCD 8421 85
y = 1: a3a2a1a0 không phải số BCD 8421 - Y = 0: a3a2a1a0 là số BCD 8421 - BCD 8421 thì ngõ ra y = 1, nghĩa là bit a3 luôn bằng 1 và bit a1 hoặc a2 bằng 1 y = a3 .(a1 + a 2 ) = a3 .a1 + a3. a 2 Phương trình logic: Sơ đồ logic: 1.2.2.4 Các phép tính trên số BCD a. Phép cộng Số thập phân là 128 thì: Số nhị phân là: 10000000 - Số BCD là: 0001 - 0010 1000 Do số BCD chỉ có từ 0 đến 9 nên đối với những số thập phân lớn hơn, nó chia số thập phân thành nhiều đềcác, mỗi đềcác được biểu diễn bằng số BCD tương ứng. 86
b. Phép trừ Bù 1 là bit 0 thành 1, bit 1 thành 0 Bù 2 bù 1 cộng thêm 1 Xét các trường hợp mở rộng: Thực hiện trừ 2 số BCD đềcác mà số bị trừ nhỏ hơn số trừ - Mở rộng cho cộng và trừ 2 số BCD nhiều đềcác. - 87
CHƯƠNG II ĐẠI SỐ BOOLE Trong mạch số các tín hiệu thường cho ở hai mức điện áp 0(v) và 5(v). những linh kiện điện tử dùng trong mạch số làm việc ở một trong hai trạng thái (tắt hoặc thông). Do vậy để mô tả mạch số người ta dùng hệ nhị phân (Binary) hai trạng thái trong mạch được mã hoá tương ứng là "1" hoặc "0". Hệ nhị phân thể hiện được trạng thái vật lý mà hệ thập phân không thể hiện được. Môn đại số mang tên người sáng lập ra nó - Đại số Boole còn được gọi là đại số logic. 2.1 MỘT SỐ ĐỊNH NGHĨA - Biến logic: Đại lượng biểu diễn bằng ký hiệu nào đó chỉ lấy giá trị "1" hoặc "0". - Hàm logic: Biểu diễn nhóm các biến logic liên hệ với nhau thông qua các phép toán logic, một hàm logic cho dù là đơn giản hay phức tạp cũng chỉ nhận giá trị hoặc là "1" hoặc là "0". 2.2 CÁC PHÉP TOÁN CƠ BẢN CỦA ĐẠI SỐ BOOLE Bởi vì các đại lượng chỉ có hai trạng thái nên đại số Boole rất khác đại số thường và dễ tính toán hơn. Ở đại số Boole không có phân số, số thập phân, số ảo, số phức, căn số… mà chỉ thực hiện chủ yếu 3 phép tính toán cơ bản sau: • Phép OR • Phép AND • Phép phủ định NOT Các phép tính trên áp dụng cho logic 0 và 1: 88
2.3 CÁC ĐỊNH LÝ CỦA ĐẠI SỐ BOOLE 2.3.1 Định lý • Một biến số • Giao hoán • Phối hợp • Phân phối • Một số đẳng thức hữu dụng • Định lý De Morgan 89
Các định lý của đại số Boole được chứng minh hay kiểm chứng bằng nhiều cách. Các cách chứng minh hay kiểm chứng này tương đối đơn giản, người đọc có thể tự chứng minh hay kiểm chứng. 2.3.2 Các phương pháp biểu diễn hàm logic 2.3.2.1 Giản đồ Venn Còn gọi là giản đồ Euler, đặc biệt dùng trong lãnh vực tập hợp. Mỗi biến logic chia không gian ra 2 vùng không gian con, một vùng trong đó giá trị biến là đúng (hay=1), và vùng còn lại là vùng phụ trong đó giá trị biến là sai (hay=0). Thí dụ: Phần giao nhau của hai tập hợp con A và B (gạch chéo) biểu diễn tập hợp trong đó A và B là đúng (A AND B) 2.3.2.2. Bảng sự thật Nếu hàm có n biến, bảng chân lý có n+1 cột và 2n + 1 hàng. Hàng đầu tiên chỉ tên biến và hàm, các hàng còn lại trình bày các tổ hợp của n biến trong 2n tổ hợp có thể có. Các cột đầu ghi giá trị của biến, cột cuối cùng ghi giá trị của hàm tương ứng với tổ hợp biến trên cùng hàng (gọi là trị riêng của hàm). Thí dụ: Hàm OR của 2 biến A, B: f(A,B) = (A OR B) có bảng chân lý tương ứng. Hai hàm logic có cùng một bảng chân lý thì được coi là tương đương với nhau. A B f(A,B) = A OR B 0 0 0 0 1 1 1 0 1 1 1 1 - Xây dựng bảng sự thật: Có thể xây dựng bảng sự thật từ: hàm logic đã cho hoặc từ bài toán thực tế. 90
Nhận xét: Một hàm logic chỉ tương ứng với duy nhất một bảng sự thật (chân lý), nhưng ngược lại, một bảng sự thật có thể tương ứng với nhiều hàm logic. Ví dụ: Một ngôi nhà có 3 công tắc, người chủ nhà muốn bóng đèn sáng khi cả 3 công tắc đều hở, hoặc khi công tắc 1 và 2 đóng còn công tắc thứ 3 hở. Hãy xây dựng bảng sự thật cho bài toán này. Bước 1: Gọi 3 công tắc lần lượt là A, B, C. Bóng đèn là Y. Trạng thái công tắc đóng là logic 1, hở là 0. Trạng thái đèn sáng là logic 1 và tắt là 0. Bước 2: Từ yêu cầu bài toán ta có bảng sự thật: 2.3.2.3 Biểu diễn bằng biểu thức đại số Với các kí hiệu hàm, biến và các phép tính giữa chúng. Có hai dạng giải tích được sử dụng là. + Dạng tuyển chính quy: Nếu mỗi số hạng chứa đầy đủ mặt các biến. + Hội chính quy: Nếu mỗi thừa số chứa đầy đủ mặt các biến. + Hội không chính quy: chỉ cần ít nhất một thừa số không chứa đầy đủ mặt các biến. Thí dụ: f(X,Y,Z) = X . . + X Y Z + X YZ + XYZ (tuyển chính quy) YZ f(X,Y,Z) = X . . X Y Z + X YZ + X Z Y+ (tuyển không chính quy) f(x,y,z) = (X +Y + Z).(X + Y + Z).( X + Y + Z ). (hội chính quy). (hội không chính quy). f(x,y,z) = (X +Y +Z).(Y + Z).(Z + Y + X ). a. Dạng tuyển chính quy: Định lý Shannon: Mọi hàm logic có thể được khai triển theo 1 trong các biến dưới dạng tổng của 2 tích logic như sau: F(A,B, . . . , Z) = A.F(1,B, . . . , Z) + A .F(0,B, . . . ,Z). 91
Ví dụ: Hàm 2 biến: F(A,B) = A.F(1,B) + A .F(0,B). (*) F(1,B) = B.F(1,1) + B .F(1,0) F(0,B) = B.F(0,1) + B .F(0,0) Với F(0,0), F(0,1), F(1,0), F(1,1). được gọi là các hàm thành phần.Thay các hàm F(1,B), F(0,B) vào (*) ta được: F(A,B) = A.B.F(1,1) + A .B.F(0,1) + A. B .F(1,0) + A . B .F(0,0) (**) Như vậy : Hàm 2 biến → Khai triển 4 số hạng (22) Hàm n biến → khai triển 2n số hạng Từ biểu thức (**) ta có nhận xét sau: - Nếu giá trị của hàm thành phần = "1" → Số hạng là tích của các biến. - Nếu giá trị của hàm thành phần = "0" → ta loại số hạng đó. A B C Z =f(A,B,C) 0 0 0 0 0 F(0,0,0) 1 0 0 1 1 F(0,0,1) 2 0 1 0 1 F(0,1,0) 3 0 1 1 1 F(0,1,1) 4 1 0 0 0 F(1,0,0) 5 1 0 1 1 F(1,0,1) 6 1 1 0 0 F(1,1,0) 7 1 1 1 1 F(1,1,1) Giả sử với ví dụ trên: F(1,1) = 1 ; F(0,0) = 1 ; F(0,1) = F(1,0) = 0 . Thì: f(A,B) = A. B + A . . B Thí dụ: Cho hàm 3 biến có bảng thật như hình trên thì: Z = f A , , )= A . . + A . . + A . . + A . . + A . . ( BC BC BC BC BC BC Từ các phân tích trên ta thấy khi biểu diễn hàm logic dạng tuyển chính quy: - Chỉ quan tâm đến các tổ hợp biến tại đó hàm thành phần nhận trị "1". - Số số hạng bằng số lần hàm thành phần nhận trị "1". 92
- Trong biểu thức logic các biến nhận trị "1" giữ nguyên, biến nhận trị"0" ta lấy phủ định. b. Dạng hội chính quy : Định lý Shannon: Mọi hàm logic được triển khai theo một trong các biến dưới dạng tích của hai tổng logic như sau: F(A,B,...,Z) = [ A + F(1,B,...,Z)].[A + F(0,B,...,Z)]. Thí dụ: Hàm 2 biến F(A,B). F(A,B) = [ A + F(1,B)].[A + F(0,B)] (1). F(1,B) = [ B + F(1,1)].[B + F(1,0)] F(0,B) = [ B + F(0,1)].[B + F(0,0)] Thay các giá trị này vào (1) ta được F( , )= [ A + B + F( ,).A + B + F( ,).A + B + F( , ).A + B + F( , ) 11 ] [ 01 ] [ 10 ] [ 00 ] AB (2) Nếu giá trị của hàm thành phần = 0 → Thừa số bằng tổng các biến. Nếu giá trị của hàm thành phần = 1 → Thừa số bị loại bỏ. Với bảng thật trên thì: Z = f( , , )= [ + B + C ][A + B + C ][A + B + C ]. A BC A . . Từ các phân tích trên khi biểu diễn hàm logic dạng hội chính quy: - Chỉ quan tâm đến các tổ hợp biến tại đó hàm thành phần nhận trị "0". - Số thừa số bằng số lần hàm thành phần nhận trị "0" . - Trong biểu thức logic các biến nhận trị "0" giữ nguyên, các biến nhận trị "1" ta lấy phủ định. c. Biểu diễn tuyển chính quy, hội chính quy dưới dạng số: - Tuyển chính quy dạng số. Từ thí dụ trước tuyển chính quy dạng số được cho: Z = F(A, B, C) = Σ (1,2,3,5,7) (tại các giá trị tổ hợp 1, 2, 3, 5, 7 của biến vào hàm nhận trị "1") 93
STTABC Z = F(A,B,C)1001 1 F(0,0,1)2010 1 F(0,1,0)3011 1 F(0,1,1)5101 1 F(1,0,1)7111 1 F(1,1,1) Z = F(A,B,C) =..C+.B.+.B.C+ A..C + A.B.C - Hội chính quy dạng số: Cũng từ thí dụ trên hội chính quy dạng số được cho như sau: Z = F(A,B,C) = ∏ (0,4,6). (tại các tổ hợp biến 0, 4, 6 hàm logic nhận trị "0" ) STTABC Z = F(A,B,C)0000 0 F(0,0,0)4100 0 F(1,0,0)6110 0 F(1,1,0) Z = (A+B+C).( +B+C).( ++C) d. Biểu diễn bằng bìa các nô. - Cấu tạo: - Gồm 1 đồ hình các ô vuông, hàm có n biến bảng có 2n ô (1 biến - 2 ô, 2 biến - 4 ô, 3 biến - 8 ô ... ). - Thứ tự của các ô do giá trị tổ hợp biến quy định -Hai ô được gọi là kề nhau, hoặc đối xứng chỉ khác nhau 1 giá trị của biến. - Giá trị của hàm tương ứng với tổ hợp biến được ghi ngay trong ô đó. - Các ô tại đó giá trị của hàm không xác định được đánh bằng dấu "X". 2.3.3 Tối thiểu hoá hàm Boole a. Phương pháp đại số Biến đổi biểu thức logic dựa vào các tính chất của đại số Boole. 94
Thí dụ : A.B + A .B = B ; A+A.B = A ; A + A .B = A + B. Ta chứng minh các đẳng thức trên, theo tính chất đối ngẫu: A.B + A .B = B ⇔ (A + B).( A + B) = B. ⇔ A.(A + B) = A. A + A.B = A A + A .B = A + B ⇔ A.( A + B) = A.B. Quy tắc 1: Nhóm các số hạng có thừa số chung. Thí dụ: A.B.C + A.B. C = A.B(C + C ) = A.B. Quy tắc 2: Đưa số hạng đã có vào biểu thức logic. A.B.C + A .B.C + A. B .C + A.B. C = = A.B.C + A .B.C + A. B .C + A.B.C + A.B. C + A.B.C = B.C.(A + A ) +A.C.(B + B ) + A.B.(C + C ) = B.C + A.C + A.B Quy tắc 3: Có thể loại các số hạng thừa. A.B + B .C + A.C = A.B + B .C + A.C (B + B ). = A.B + B .C + A.B.C + A. B .C = A.B + B .C (loại A.C) b. Phương pháp bìa các nô Nguyên tắc tối giản hàm logic trên bìa các nô - Thực hiện nhóm các ô tại đó hàm nhận trị "1" hoặc "0" kề nhau hoặc đối xứng, số ô trong một nhóm dán phải là số luỹ thừa của 2 (khi viết hàm dạng tuyển ta nhóm các ô có giá trị "1", dạng hội nhóm các ô có giá trị "0"). - Trong một nhóm dán các biến có trị thay đổi ta loại, các biến có trị không đổi giữ nguyên, điều này có nghĩa là số ô trong nhóm dán càng nhiều thì số biến bị loại càng tăng (2 ô - loại 1 biến, 4 ô - loại 2 biến ... 2m ô - loại m biến). - Biểu thức logic có số số hạng hay thừa số chính bằng số nhóm dán. Khi viết hàm logic dưới dạng tuyển các biến còn lại nhận trị "1" ta giữ nguyên, nhận trị "0" ta lấy phủ định, khi viết hàm logic dưới dạng hội thì ngược lại. - Một ô có thể tham gia vào nhiều nhóm dán. 95
- Các ô tại đó giá trị hàm không xác định ta coi tại ô đó hàm có thể lấy giá trị "1" hoặc "0" tuỳ từng trường hợp cụ thể. * Chú ý: Phương pháp tối giản hàm logic trên bìa các nô chỉ thích hợp với hàm có số biến ≤ 6. Trường hợp hàm có số biến lớn hơn 6, bảng các nô rất phức tạp. C 0 1 AB BC 00 0 1 A 0 0001111001 3 2 1 01 3 2 11 6 4 5 7 5 4 4 cột - 2 hàng (hàm 3 biến) 10 6 7 2 cột - 4 hàng (hàm 3 biến) CD 00 01 11 10 AB 00 Hàm 4 biến 3 2 1 0 (4 hàng - 4 cột -16 ô) 01 4 6 5 7 11 12 13 15 14 10 12 8 9 11 10 DEF ABC 3 2 0 1 4 6 7 5 9 11 14 15 13 12 8 10 26 24 25 28 30 31 29 27 000001011010110111101100000001011010110111101100 17 19 22 23 21 20 16 18 51 50 48 49 52 54 55 53 63 60 56 57 59 58 62 61 43 42 40 41 44 46 47 45 33 35 38 39 37 36 32 34 Hàm 6 biến (8 hàng - 8 cột - 64 ô) Thí dụ: Cho hàm logic 4 biến F(A,B,C,D) = ∑(0,1,2,4,6,8,9,10) và không xác định tại N = 5, 11,13,15. (Thí dụ này tương đương với việc cho hàm logic 4 biến F(A,B,C,D) = ∏ (3,7,12,14) và không xác định tại N = 5,11,13,15) Từ bài ra ta có bảng các nô như sau: 96
F CD AB 00011110001101011X01110XX0 1011X1 + Biểu diễn dạng tuyển (3 nhóm dán) - Nhóm 1: Các ô 0, 2, 8, 10 → kết quả: B. D - Nhóm 2: Các ô 0, 2, 4, 6 → kết quả: A . D - Nhóm 3: Các ô 1, 5, 9, 13 → kết quả: C . D Hàm biểu diễn dưới dạng tuyển: F(A,B,C,D) = B. + A . + C . D D D + Biểu diễn hàm logic dưới dạng hội (2 nhóm) - Nhóm 1: Gồm các ô 3, 7, 11, 15 → kết quả: C + D - Nhóm 2: Gồm các ô 12, 13, 14, 15 → kết quả: A + B + Hàm biểu diễn dưới dạng hội: F(A,B,C,D) = ( C + D ).( A + B ) c. Phương pháp Quine – Mc Cluskey Phương pháp Quine-Mc.Cluskey cũng dựa trên tính kề của các tổ hợp biến để đơn giản số biến trong các số hạng của biểu thức dạng tổng (minterm). Trong quá trình đơn giản này có thể xuất hiện các số hạng giống nhau mà ta có thể bỏ bớt được. Phương pháp được thực hiện qua 2 giai đọan: Giai đoạn 1: Dựa trên tính kề của các tổ hợp biến để đơn giản số biến trong các số hạng của biểu thức dạng tổng (minterm). Giai đoạn 2: Kiểm tra và thực hiện việc tối giản . Thí dụ dưới đây minh họa cho việc thực hiện phương pháp để rút gọn một hàm logic. Thí dụ 1: Rút gọn hàm f(A,B,C,D) = ∑(1,2,4,5,6,10,12,13,14) ♣ Giai đọan 1 - Các minterm được nhóm lại theo số số 1 có trong tổ hợp và ghi lại trong bảng theo thứ tự số 1 tăng dần: 97