Phương pháp tối ưu luận lý bằng K-map

Nguyên lý tối ưu luận lý bằng K-map

Nguyên lý tối ưu luận lý bằng K-map dựa trên 2 tính chất sau của đại số Boolean:

1. xy + xy'  = x(y + y') = x ‧ 1 = x

2. (x + y)(x + y') = x + yy' = x + 0 = x

Nghĩa là tổng (phép toán OR) của hai tích khác nhau đúng 1 bit thì kết quả sẽ tối ưu được bit khác nhau đó, tương tự với tích (phép toán AND) của 2 tổng khác nhau đúng 1 bit thì kết quả sẽ tối ưu được bit khác nhau đó. Điều này đúng với 2 minterm/maxterm chỉ khác nhau 1 bit cũng như đúng với 2 ô liền kề trên K-map, trong đó 2 ô được xem là liền kề nếu 2 tổ hợp các biến được gán cho chúng chỉ khác nhau 1 bit (hoặc có thể xem là 2 minterm/maxterm tương ứng của chúng chỉ khác nhau 1 bit). Như vậy, 2 ô liền kề có thể được gom nhóm để tối ưu luận lý.

Tối ưu luận lý bằng K-map

Về tổng quát, nguyên tắc gom các 1-minterm hoặc 0-maxterm nhưng không được đồng thời cả hai:

1. Chỉ gom được các nhóm 2k ô 1-minterm/0-maxterm với k ≥ 0. Nếu gom 1 nhóm được 2k ô thì chúng ta sẽ tối ưu được k biến.

2. Phải đảm bảo sao cho số lần gom là ít nhất, nghĩa là một nhóm phải có nhiều ô nhất có thể. Hệ quả là số tích/tổng của biểu thức cuối cùng là ít nhất và số lượng biến hoặc phần bù của nó trong mỗi tích/tổng là ít nhất.

3. Mỗi nhóm phải có ít nhất 1 ô không thuộc các nhóm khác để tránh trường hợp dư thừa các tích/tổng mà các nhóm khác đã bao phủ hết.

Vì thế, khi tối ưu cần phải đảm bảo việc gom nhóm thỏa mãn đồng thời cả 3 quy tắc trên. Nhưng cả 3 quy tắc này là rời rạc và không có thứ tự nên rất khó để xác định là việc gom nhóm đã đúng hay chưa. Để giải quyết khó khăn này thì có thể gom nhóm theo hướng dẫn bên dưới theo độ ưu tiên giảm dần cho đến khi gom được hết tất cả các ô:

1. Ưu tiên 1: Gom các nhóm 2k ô 1-minterm/0-maxterm lớn nhất có ít nhất 1 ô không thể thuộc nhóm khác.

2. Ưu tiên 2: Bỏ qua các ô đã được gom, gom các nhóm 2k ô lớn nhất liền kề các ô đã được gom sao cho có ít nhất 1 ô không thể thuộc nhóm còn lại khác.

3. Ưu tiên 3: Bỏ qua các ô đã được gom, gom các nhóm 2k ô lớn nhất liền kề các ô đã được gom.

4. Ưu tiên 4: Gom các nhóm 2k ô lớn nhất còn lại một cách tùy ý.

Việc tối ưu bằng K-map có thể thực hiện theo 2 cách:

1. Cách 1: Tối ưu để tạo ra biểu thức SoP. Để tạo ra biểu thức SoP sau khi tối ưu thì chúng ta sẽ gom các ô liền kề có giá trị 1 với nhau. Kết quả của việc gom các ô sẽ tạo ra các tích (phép toán AND) của các biến sao cho tích này có giá trị 1. Kết quả tối ưu cuối cùng sẽ là OR của các tích đã được tối ưu. 

2. Cách 2: Tối ưu để tạo ra biểu thức PoS. Để tạo ra biểu thức PoS sau khi tối ưu thì chúng ta sẽ gom các ô liền kề có giá trị 0 với nhau. Kết quả của việc gom các ô sẽ tạo ra các tổng (phép toán OR) của các biến sao cho tổng này có giá trị 0. Kết quả tối ưu cuối cùng sẽ là AND của các tổng đã được tối ưu. 

Các bạn xem chi tiết bài giảng về K-map tại đây: https://youtu.be/Lxxg0OvpubE