Diagramă Karnaugh
De la Wikipedia, enciclopedia liberă
Diagramele Karnaugh au fost inventate în 1950 de Maurice Karnaugh, un inginer în telecomunicaţii de la Laboratoarele Bell pentru a facilita minimizarea expresiilor algebrice booleene.
În mod normal, sunt nevoie de calcule complicate, folosind formule şi iteraţii, dar în schimb, Diagramele Karnaugh sunt mult mai simplu şi mai rapid de utilizat pentru că folosesc capabilităţile creierului uman de recunoaştere a formelor pentru a decide care termeni să fie combinaţi pentru a găsi expresiile cele mai simple.
O diagramă Karnaugh poate fi un ajutor excelent pentru simplificarea expresiilor de până la şase variabile, dar cu mai multe variabile, devine mai greu pentru creierul nostru să vadă modelele, astfel că de obicei, pentru mai mult de patru variabile, se foloseşte algoritmul Quine-McCluskey.
Diagrama Karnaugh se construieşte cu ajutorul codului Gray, codul în care doi termeni succesivi diferă printr-un singur bit, astfel că doi mintermeni vecini sunt cei între care există o diferenţă de un bit, putându-se astfel extinde diagramele Karnaugh pentru oricât de multe variabile.
Simplificare în cadrul diagramele Karnaugh se bazează pe gruparea mintermenilor, folosind principiul x+x’ = 1. Astfel că dacă un mintermen are un vecin alt mintermen de aceeaşi dimensiune, aceştia se pot “unifica”, rezultând un mintermen cu mai puţine variabile în componenţă.
[modifică] Exemplu
Fie următoarea funcţie, cu patru variabilă dată cu parametri mintermeni: f(A, B, C, D) = E(4, 8, 9, 10, 11, 12, 14, 15)
Tabela de adevăr a acestei funcţii este:
A B C D f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1
Având 4 variabile de intrare, ele pot fi combinate în 16 feluri diferite, astfel că diagrama Karnaugh trebuie să aibă 16 poziţii. Cel mai convenabil mod este să fie aranjate într-un tabel 4x4.
Cifrele binare în diagramă reprezintă ieşirea funcţiei pentru o anumită combinaţie de valori de intrare. În colţul din stânga-sus avem 0 pentru f = 0 atunci când A = 0, B = 0, C = 1, D = 0.
După ce am construit diagrama Karnaugh, trebuie să aflăm expresiile minimale care vor fi utilizate în expresia finală. Acest lucru va fi făcut prin încadrarea de valori de '1', astfel încât figura reprezentată de acestea să aibă formă dreptunghiulară, să conţină 2n elemente, unde n este un număr natural (1, 2, 4, 8, 16, etc), şi să fie maximală.
Inversul funcţiei poate fi obţinut în acelaşi mod prin încercuirea zerourilor în loc de 1. În exemplul de mai sus, se poate obţine expresia:
A' B' + A' C + B C' D
