Bìa Karnaugh

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm


Một ví dụ về bìa Karnaugh

Bìa Karnaugh, hay sơ đồ Các-nô, biểu đồ Veitch, là một công cụ để thuận tiện trong việc điều chỉnh các biểu thức đại số Boole. Bìa Karnaugh độc đáo ở chỗ giữa các ô chỉ có sự thay đổi của một biến mà thôi; hay nói cách khác, các hàng và cột được sắp xếp theo nguyên lý mã Gray.

Lịch sử và thuật ngữ[sửa | sửa mã nguồn]

Bìa Karaugh được Edward W. Veitch sáng tạo vào năm 1952 và được Maurice Karnaugh, một kĩ sư viễn thông làm việc tại Bell Labs, phát triển thêm vào năm 1953.

Cách dùng trong luận lý Boole[sửa | sửa mã nguồn]

Thông thường, để thu gọn biểu thức của một hàm Boole cần mất rất nhiều phép toán, nhưng một người có thể sử dụng một bìa Karnaugh để làm điều đó.

Những vấn đề có thể giải quyết

  • Bìa Karnaugh tận dụng khả năng so trùng mẫu cực tốt của não người để quyết định số hạng nào nên được kết hợp với nhau để tạo ra biểu thức đơn giản nhất.
  • Bìa Karnaugh cho phép nhận biết và loại trừ các tranh đoạt điều khiển (race hazard) tiềm ẩn một cách nhanh chóng, những thứ mà chỉ có các phương trình Boole không thể thực hiện được.
  • Bìa Karnaugh là một phương tiện tuyệt vời để đơn giản hóa phương trình có tối đa sáu biến số, nhưng với nhiều biến hơn nó sẽ trở nên khó cho não bộ chúng ta nhận ra được những mẫu hình ảnh khác nhau.
  • Đối với những bài toán liên quan đến nhiều hơn sáu biến, người ta thường giải quyết bằng cách dùng biểu thức Boole hơn là dùng bìa Karnaugh.

Bìa Karnaugh cũng hữu ích khi dạy về hàm Boole và rút gọn.

Tính chất[sửa | sửa mã nguồn]

Chuyển các minterm sang bìa Karnaugh
4 sơ đồ Venn với các số (0-15) và các tên (A-D) nối với nhau trên sơ đồ minterm

Bìa Karnaugh có thể có số biến bất kỳ, nhưng nó hoạt động tốt nhất khi chỉ có ít - khoảng giữa 2 và 6. Mỗi biến có hai khả năng xảy ra với mỗi một khả năng của các biến khác trong hệ thống. Bìa Karnaugh được tổ chức sao cho tất cả các khả năng của hệ thống được sắp xếp theo dạng lưới và giữa hai ô kề nhau chỉ có một biến là thay đổi giá trị. Điều này cho phép giảm tranh đoạt.

Khi sử dụng bìa Karnaugh để tạo ra hàm rút gọn tối ưu, một người sẽ "phủ" các số 1 trên bìa bằng một hình chữ nhật "bao phủ", trong đó có chứa một số ô bằng với lũy thừa 2 (ví dụ, 4 ô dọc theo một hàng, 4 ô trong 1 hình vuông, 8 ô trong một hình chữ nhật, v.v.). Khi người đó đã phủ các số 1, một số hạng của tổng các tích được tạo ra bằng cách tìm các biến không thay đổi trong toàn bộ vùng bao phủ, và số 1 nghĩa là chính biến đó và 0 là phủ định của biến. Làm lại điều này cho tất cả các bao phủ sẽ cho ra một hàm tương đương.

Người ta cũng có thể sử dụng số 0 (zero) để tạo ra một hàm rút gọn tối đa. Quy trình hoàn toàn y hệt như với số 1 trừ số hạng được tạo ra là một số hạng trong tích các tổng - và 1 có nghĩa là phủ định của biến trong khi 0 nghĩa là không phủ định.

Mỗi hình vuông trong bìa Karnaugh tương ứng với một minterm (và maxterm). Hình bên phải cho thấy vị trí của mỗi minterm trong bìa.

Một sơ đồ Venn gồm bốn tập hợp được gán nhãn A, B, C, và D — ở hình bên phải tương ứng với các minterm của bìa K 4 biến số như ở trên:

  • Chẳng hạn biến A của bìa K tương ứng với tập A trong sơ đồ Venn;
  • Chẳng hạn minterm m0 của bìa K tương ứng với vùng 0 trong sơ đồ Venn

Minterm m9 là ABCD=1001 tươn ứng với nơi chỉ có tập A & D giao nhau. Do đó, một minterm nào đó sẽ xác định một phép giao độc nhất trong tất cả bốn tập hợp.

Sơ đồ Venn có thể bao gồm số tập hợp vô hạn và vẫn phù hợp với bìa Karnaugh tương ứng. Với số tập hợp và biến tăng lên, cả sơ đồ Venn và bìa Karnaugh cũng tăng lên về độ phức tạp khi vẽ và xử lý.

Kích thước của bìa[sửa | sửa mã nguồn]

Trong một bìa Karnaugh có n biến, một số hạng Boole gồm k biến trong số đó sẽ có một hình chữ nhật tương ứng có diện tích 2^{n-k}. Bìa có kích thước thông thường là 2 biến với diện tích 2x2; 3 biến là 2x4; và 4 biến là 4x4 (xem ở dưới).

Ví dụ[sửa | sửa mã nguồn]

Xem xét hàm luận lý gồm bốn biến sau (theo nhị phân, sẽ có tối đa 16 tổ hợp):

f(A, B, C, D) = E(6, 8, 9, 10, 11, 12, 13, 14)

Các giá trị trong E liệt kê các minterm trong bìa (có nghĩa là những hàng có đầu ra là 1 trong bảng chân trị).

Bảng chân trị[sửa | sửa mã nguồn]

Sử dụng các minterm đã được định nghĩa, bảng chân trị có thể được tạo ra:

# A B C D f(A, B, C, D)
0 0 0 0 0 0
1 0 0 0 1 0
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 0
5 0 1 0 1 0
6 0 1 1 0 1
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 1
13 1 1 0 1 1
14 1 1 1 0 1
15 1 1 1 1 0

Bìa[sửa | sửa mã nguồn]

Các biến nhập vào có thể được kết hợp theo 16 cách khác nhau, do đó bìa Karnaugh của chúng ta sẽ có 16 vị trí. Cách thuận tiện nhất để sắp xếp cái này là trong lưới 4x4.

Bìa K cho thấy các minterm và ô bao phủ các minterm mong muốn

Các số nhị phân trong bìa đại diện cho các kết quả đầu ra của hàm đối với bất kỳ tổ hợp đầu vào cho trước nào. Chúng ta viết 0 ở góc trên bên trái của bìa vì f=0 khi A=0, B=0, C=0, D=0. Tương tự chúng ra đánh dấu góc phải bên dưới là 1 vì A=1, B=0, C=1, D=0 cho ra f=1. Chú ý rằng các giá trị được sắp xếp theo dạng mã Gray, do đó một cách chính xác một biến thay đổi trong hai biến đối với hai ô kế cận.

Sau khi bìa Karnaugh đã được tạo ra, bước tiếp theo của chúng ra là tìm ra các số hạng tối thiểu để dùng trong biểu thức cuối cùng. Những số hạng này được tìm bằng cách bao phủ các số 1 trong bìa. Vùng bao phủ phải là hình chữ nhật và phải có diện tích là lũy thừa của hai (tức là 1, 2, 4, 8, …). Các hình chữ nhật này phải lớn nhất có thể mà không được chứa số 0 nào. Những vùng bao phủ tốt nhất trong bìa này được đánh dấu bằng các đường màu xanh lá, màu đỏ và màu xanh biển.

Đối với mỗi vùng bao phủ này chúng ta tìm những biến có cùng trạng thái trong mỗi ô trong vùng bao phủ. Đối với nhóm đầu tiên (màu đỏ) chúng ta tìm thấy:

  • Biến A có cùng trạng thái (1) trong toàn bộ vùng, do đó nó sẽ được đưa vào số hạng tương ứng với vùng màu đỏ.
  • Biến B không ngữ nguyên được trạng thái (chuyển từ 1 sang 0), và do đó sẽ bị loại trừ.
  • C không đổi, nó lúc nào cũng là 0.
  • D thay đổi.

Do đó số hạng đầu tiên của biểu thức Boole sẽ là A\overline{C}.

Đối với vùng bao phủ màu xanh lá chúng ta nhìn thấy AB giữ nguyên trạng thái, còn D thay đổi, c that đổi. B là 0 và phải được phủ định trước khi ghi vào số hạng. Do đó số hạng thứ hai sẽ là A\overline{B}.

Tương tự, hình chữ nhật màu xanh biển cho ra số hạng BC\overline{D}. Cuối cùng biểu thức thu được là: A\overline{C} + A\overline{B} + BC\overline{D}.

Nối qua cạnh[sửa | sửa mã nguồn]

Mạng lưới được nối qua cạnh, có nghĩa là các hình chữ nhật có thể bao xung quanh các cạnh, do đó A\overline{D} là một số hạng đúng, mặc dù không phải là một phần của tập hợp tối thiểu-nó bao phủ các minterm 8, 10, 12 & 14.

Có lẽ số hạng bao phủ xung quanh khó thấy nhất là \overline{B}\,\overline{D} bao phủ bốn góc-nó sẽ phủ các minterm 0, 2, 8, 10.

Nghịch đảo[sửa | sửa mã nguồn]

Nghịch đảo của hàm được giải theo cách tương tự, bằng cách nhóm các số 0.

Ba số hạng bao phủ phần đảo nằm trong ô màu xám với các khung có màu khác nhau:

  • nâu—\overline{A}\,\overline{B}
  • vàng—\overline{A}\,\overline{C}
  • xanh biển—BCD

Nó sẽ cho ra đảo:

\overline{F} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD

Bằng cách sử dụng Định luật De Morgan, tích các tổng có thể xác định được:

\overline{\overline{F}} = \overline{ \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD }
F = \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)

Tùy định[sửa | sửa mã nguồn]

Minterm 15 bỏ qua và thay thế bằng một tùy định, nó sẽ bỏ hoàn toàn số hạng xanh lá cây nhưng làm chặt chẽ thêm số hạng đảo màu xanh nước biển

Bìa Karnaugh cũng cho phép sự tối thiểu hóa dễ dàng các hàm mà bản chân trị có cả các điều kiện "tùy định" (tức là tập các đầu vào mà người thiết kế không quan tâm đến giá trị đầu ra là gì) vì các điều kiện "tùy định" có thể được bao hàm trong một khung để khiến cho nó lớn hơn mà không nhất thiết phải quan tâm đó là số nào. Chúng thường được vẽ trên bìa bằng dấu gạch/X thay vì số. Giá trị của nó có thể là "0", "1", hoặc gạch ngang/X tùy vào người đó đang dùng "0" hay "1" để rút gọn bìa K hơn nữa. Nếu "tùy định" không giúp ích gì trong việc rút gọn bìa K, thì hãy sử dụng gạch ngang/X.

Ví dụ phía bên phải là ví dụ y hệt ở trên nhưng minterm 15 bị bỏ đi và thay thế bằng tùy định. Điều này cho phép số hạng đỏ mở rộng xuống phía dưới và, do đó, bỏ hoàn toàn số hạng xanh lá.

Nó sẽ cho ra phương trình rút gọn mới:

F = A + BC\overline{D}.

Chú ý rằng số hạng đầu tiên chỉ là A chứ không phải A\overline{C}. Trong trường hợp này, giá trị tùy định đã bỏ đi một số hạng (xanh lá); rút gọn số hạng khác (đỏ); và bỏ được tranh đoạt điều khiển (màu vàng như sẽ thấy trong phần dưới).

Tương tự, vì trường hợp nghịch đảo không còn phải bao phủ minterm 15, minterm 7 có thể bị bao phủ bằng \left(A + \overline{D}\right) thay vì \left(\overline{B} + \overline{C} + \overline{D}\right) với kết quả tương tự.

Tranh đoạt điều khiển[sửa | sửa mã nguồn]

Bìa K ở trên có số hạng A\overline{D} được thêm vào để tránh tranh đoạt điều khiển

Bìa Karnaugh hữu ích trong việc tìm ra và loại bỏ tranh đoạt điều khiển. Bị dễ dàng nhìn ra bằng cách dùng bìa Karnaugh, vì một tranh đoạt điều khiển có thể tồn tại khi di chuyển giữa một cặp liền kề, nhưng rời rạc, những vùng được khoanh trên bìa.

  • Ở ví dụ trên, một tranh đoạt điều khiển tiềm ẩn tồn tại khi C là 1 và D là 0, A là 1, và B thay đổi từ 1 sang 0 (di chuyển từ trạng thái xanh nước biển sang trạng thái xanh lá cây). Trong trường hợp này, ngõ ra được định nghĩa là 1 không đổi, nhưng vì sự chuyển đổi này không được một số hạng cụ thể nào bao phủ trong phương trình, khả năng xảy ra một lỗi (đột ngột chuyển qua 0 trong thời gian ngắn) tồn tại.
  • Một lỗi khó nhìn ra hơn là khi D là 0 và A và B cùng là 1, với C thay đổi từ 1 sang 0 (di chuyển từ trạng thái xanh sang trạng thái đỏ). Trong trường hợp này lỗi bao xung quanh từ đỉnh đến cuối bìa.

Dù những lỗi này có xảy ra hay không phụ thuộc vào bản chất vật lý khi hiện thực, và việc chúng ta có cần quan tâm về chúng hay không tùy thuộc vào ứng dụng.

Trong trường hợp này, một số hạng cộng thêm A\overline{D} sẽ loại bỏ tranh đoạt điều khiển tiềm ẩn, nối giữa trạng thái ngõ ra xanh lá cây và xanh nước biển hoặc trạng thái ngõ ra xanh nước biển và đỏ: nó là vùng màu vàng.

Số hạng là dư thừa nói theo luận lý tĩnh của hệ thống, nhưng sự dư thừa như vậy, hay theo cách nói đồng thuận, thường là cần thiết để đảm bảo hiệu suất động không có tranh đoạt.

Tương tự, một số hạng cộng thêm \left(A + \overline{D}\right) phải được thêm vào trường hợp nghịch đảo để loại bỏ một khả năng tranh đoạt điều khiển khác.

Bìa có 2 biến[sửa | sửa mã nguồn]

Dưới là tất cả những trường hợp có thể của bìa Karnaugh 2x2 có 2 biến. Liệt kê theo từng bìa là các minterm đóng vai trò là hàm của phương trình rút gọn E() không có tranh đoạt điều khiển (xem phần trước).

Các vấn đề với bìa Karnaugh[sửa | sửa mã nguồn]

Bìa Karnaugh nói chung trở nên ngày càng lộn xộn hơn và khó nhìn khi thêm vào càng nhiều biến. Một nguyên tắc chung đó là bìa Karnaugh sẽ làm việc tốt với tối đa bốn biến, và không nên được dùng với số biến nhiều hơn sáu. Đối với những biểu thức có số lượng biến lớn, có thể dùng giải thuật Quine-McCluskey. Nói chung ngày nay quy trình rút gọn được thực hiện bằng máy tính, trong đó Trình rút gọn luận lý heuristic Espresso đã trở thành chương trình rút gọn tiêu chuẩn.

Phần mềm[sửa | sửa mã nguồn]

Có nhiều phần mềm để giải bài toán bìa K. Một phần mềm tự do như vậy dành cho Linux và Windows là GKMap.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  • Karnaugh, Maurice (tháng 11 năm 1953). “The Map Method for Synthesis of Combinational Logic Circuits”. Transactions of American Institute of Electrical Engineers part I 72 (9): 593–599. 
  • Katz, Randy (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company. tr. 70–85. doi:10.1016/0026-2692(95)90052-7. ISBN 0-8053-2703-7. 
  • William W. Wickes 1968, Logic Design with Integrated Circuits, John Wiley & Sons, Inc., NY. No ISBN. Library of Congress Catalog Number: 68-21185. Wickes describes the Veitch diagram as "a refinement of the Venn diagram in that circles are replaced by squares and arranged in a form of matrix. The Veitch diagram labels the squares with the minterms. Karnaugh assigned 1s and 0s to the squares and their labels and deduced the numbering scheme in common use (cf pp. 36–49).

Liên kết ngoài[sửa | sửa mã nguồn]

Ứng dụng[sửa | sửa mã nguồn]