Diagramă Karnaugh

Diagramele Karnaugh, numite și hărți Karnaugh^[1], 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, pentru minimizarea acestor expresii este nevoie de calcule complicate, folosind formule și iterații, pe când 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.

Diagramele Karnaugh pot fi construite pentru oricât de multe variabile. Totuși, o diagramă Karnaugh poate fi de folos pentru simplificarea expresiilor de până la șase variabile; 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.

Reducerea expresiilor

Diagrama Karnaugh pentru 2, 3 și 4 variabile

Diagrama Karnaugh se construiește punând valorile unor variabile pe linii și al celorlalte variabile pe coloane. Distribuția valorilor trebuie să respecte codului Gray, astfel că între două căsuțe vecine există o diferență de un bit. Valoarea asociată unei căsuțe este valoarea funcției pentru combinația respectivă de valori de intrare. Valorile posibile sunt 1, 0 sau X (nu contează). Diagramele pentru 2, 3 și 4 variabile sunt reprezentate în figura alăturată.

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 valorilor de 1, astfel încât figura reprezentată de acestea să aibă următoarele proprietăți:

are formă dreptunghiulară
conține 2ⁿ elemente, unde n este un număr natural (1, 2, 4, 8, 16 etc. elemente)
este maximală, adică nu poate fi inclusă într-o altă figură cu aceste proprietăți, dar cu n mai mare. Dacă un mintermen are un vecin un alt mintermen de aceeași dimensiune, aceștia se pot uni, rezultând un mintermen cu mai puține variabile în componență.
conține elemente X doar dacă zona rezultată este mai mare decât cea care putea fi obținută fără elementul respectiv (adică dacă se obține o reducere a termenului algebric echivalent).

Grupurile generate sunt convertite într-o expresie booleană prin:

determinarea valorilor posibile ale variabilelor în grupul respectiv. Dacă figura se află pe o coloană unde A=1, se ia în considerare valoarea A. Dacă figura se află pe o coloană unde A=0, se ia în considerare valoarea ${\overline {A}}$
se elimină variabilele care sunt prezente atât cu valoarea posibilă 1, cât și cea 0.

Fiecare grup generează astfel un produs, iar valoarea expresiei booleene este suma acestor produse.

Funcția inversă se poate obține grupând valorile de 0, în locul celor de 1.

Exemplu

Enunț

Fie o funcție f(A, B, C, D), cu următoarea tabelă de adevăr:

#	$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

Funcția dată cu parametrii mintermeni (adică valorile pentru care rezultatul funcției este 1 în tabela de adevăr) este:

$f(A,B,C,D)=\sum _{}m(6,8,9,10,11,12,13,14)=({\overline {A}}BC{\overline {D}})+(A{\overline {B}}{\overline {C}}{\overline {D}})+(A{\overline {B}}{\overline {C}}D)+(A{\overline {B}}C{\overline {D}})+(A{\overline {B}}CD)+$
$+(AB{\overline {C}}{\overline {D}})+(AB{\overline {C}}D)+(ABC{\overline {D}})$

Se dorește reducerea acestei expresii până la cea mai mică expresie algebrică echivalentă.

Rezolvare

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, după cum este ilustrat în figura de mai jos.

Valorile din diagramă reprezintă ieșirea funcției pentru combinația de valori de intrare corespunzătoare valorilor de pe linie și coloană. În colțul din stânga-sus avem 0 pentru f(0, 0, 0, 0) = 0, iar în dreapta sus f(1, 0, 0, 0) = 1.

Grupurile definite sunt marcate prin culori. Zona maro este obținută prin suprapunerea grupurilor roșu și verde. Aplicând regulile descrise mai sus, expresiile algebrice corespunzătoare grupurilor sunt:

Grup	Variabile	Expresie
roșu	$A,B,{\overline {B}},{\overline {C}},D,{\overline {D}}$	$A{\overline {C}}$
verde	$A,{\overline {B}},C,{\overline {C}},D,{\overline {D}}$	$A{\overline {B}}$
albastru	$A,{\overline {A}},B,C,{\overline {D}}$	$BC{\overline {D}}$

Rezultă deci: $f(A,B,C,D)=A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}$

Funcția inversă (obtinută prin grupare de zerouri - zonele gri): ${\overline {f}}(A,B,C,D)={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD$

Note

^ Kuphaldt, Tony R (martie 2000). Lessons In Electric Circuits [Introducere în circuite electrice și electronice]. IV. Parametru necunoscut |other= ignorat (posibil, |others=?) (ajutor)

Vezi și

Hărți Karnaugh la circuiteelectrice.ro

[1] Kuphaldt, Tony R (martie 2000). Lessons In Electric Circuits [Introducere în circuite electrice și electronice]. IV. Parametru necunoscut |other= ignorat (posibil, |others=?) (ajutor)

[1]

#	$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

#	$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

#	$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