Harta Karnaugh

Harta lui Karnaugh este o metodă de reprezentare exactă a sintezei rețelelor combinatorii la unul sau mai multe niveluri. O astfel de hartă constituie o reprezentare vizuală a unei funcții booleene capabile să evidențieze perechile de mintermi sau maxtermi cu o distanță de Hamming unitară (adică de termeni care diferă pentru o singură variabilă binară (sau booleană) ). Deoarece derivă dintr-o viziune mai puțin intuitivă a funcțiilor booleene în spații $\{0,1\}^{n}$ ${\ displaystyle \ {0,1 \} ^ {n}}$ $\ {0,1 \} ^ n$ cu $n$ ${\ displaystyle n}$ $n$ numărul de variabile funcționale, hărțile Karnaugh sunt aplicabile efectiv numai funcțiilor cu cel mult 5 - 6 variabile.

Istorie

Harta Karnaugh a fost inventată în 1953 de Maurice Karnaugh , inginer de telecomunicații la Bell Laboratories .

Utilizare

O hartă Karnaugh este o metodă grafică care are ca scop reducerea complexității funcțiilor booleene exprimate în forme canonice. Este construit pornind de la tabelul de adevăr al unei funcții booleene, în procesul de sinteză al unei rețele combinatorii .

Hărțile Karnaugh ne permit să construim pur și simplu forma minimă a unei funcții ca o sumă de produse logice (formă disjunctivă) sau ca un produs al sumelor logice (formă conjunctivă) și, prin urmare, simplificări ale funcției booleene de multe ori mai imediate decât cele obținute cu modificări algebrice .

Exemplu

Să luăm în considerare funcția:

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

{\ displaystyle f (A, B, C, D) = \ sum (6,8,9,10,11,12,13,14)}

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

Valoarea din interior $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ ( sigma ) indică care linie va avea ieșirea 1, reprezentând astfel funcția (ON - SET) în suma produselor.

Această funcție are următorul tabel de adevăr :

#	$LA$ ${\ displaystyle A}$ $LA$	$B.$ ${\ displaystyle B}$ $B.$	$C.$ ${\ displaystyle C}$ $C.$	$D.$ ${\ displaystyle D}$ $D.$	$f(A,B,C,D)$ ${\ displaystyle f (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

Deoarece există 16 combinații ale celor 4 variabile booleene, harta Karnaugh trebuie să aibă și 16 poziții. Cel mai convenabil mod de a le aranja este într-o masă 4x4.

Harta Karnaugh corespunzătoare funcției f

Numerele binare din grilă arată valoarea de ieșire a funcției pentru toate combinațiile posibile de intrare. Vom scrie 0 în extrema stângă în partea de sus, deoarece f = 0 când A = 0, B = 0, C = 0, D = 0, adică f (0,0,0,0) = 0. În mod similar, vom scrie 1 în partea de jos spre dreapta, deoarece A = 1, B = 0, C = 1, D = 0 returnează f = 1, adică f (1,0,1,0,) = 1.

Rețineți că perechile de variabile de intrare ( A , B și C , D ) sunt ordonate cu codul Gray , astfel încât o singură variabilă se schimbă între perechile de celule adiacente ( distanța Hamming = 1).

După construirea hărții Karnaugh, 1-urile sunt grupate în dreptunghiuri cât mai mari posibil, care totuși au întotdeauna o suprafață (în pătrate ale mesei) egală cu o putere de 2 (1, 2, 4, 8, 16, 32,. ..). Grupările optime, în acest exemplu, sunt cele indicate pe hartă cu conturul verde, roșu și albastru.

Pentru fiecare grupare găsim variabilele care nu își schimbă valoarea.

Pentru prima grupare (roșu) vedem că:

Variabila A menține aceeași stare (1) în întregul grup, deci trebuie inclusă în produsul rezultat.
Variabila B nu își păstrează valoarea, trecând de la 1 ( f (1, 1,0, 0) ) la 0 ( f (1, 0, 0, 0) ) și, prin urmare, trebuie exclusă.
C nu se schimbă, păstrează aceeași stare (0), deci este inclus.
D se modifică și este exclus.

Astfel, primul produs care va face parte din expresia booleană finală este AC ' (variabila directă este luată în considerare dacă, pentru valorile din interiorul dreptunghiului, își asumă valoarea 1 și este negată dacă își asumă valoarea 0).

Pentru dreptunghiul în verde (format din patru 1s dispuse vertical) vedem că A , B mențin aceeași stare, în timp ce C și D se schimbă. Deoarece B este egal cu 0, variabila trebuie anulată înainte de a fi inclusă în produs. Deci obținem AB ' .

Cu aceeași procedură, din dreptunghiul albastru găsim BCD ' : singura variabilă care nu ar trebui inclusă în produs este A, deoarece își schimbă valoarea în interiorul dreptunghiului.

Expresia finală a funcției f se obține prin adăugarea produselor găsite anterior: AC ' + AB' + BCD ' .

Dacă doriți să găsiți funcția duală, aceasta este funcția care folosește maxtermini , pur și simplu grupați valorile 0 în loc de 1: aceasta corespunde alegerii în tabelul de adevăr a liniilor pentru care funcția de ieșire este 0 în loc de 1 În acest caz, variabilele care rămân constante în grupare și care au o valoare egală cu 1 trebuie completate (adică negate). În exemplul prezentat, funcția duală este dată de (A + C) (A + B ) (B '+ C' + D ') .

Într-o hartă Karnaugh cu n variabile, un produs boolean de k variabile corespunde unui dreptunghi format din 2 celule ^nk .

Hărțile Karnaugh sunt, de asemenea, potrivite pentru simplificarea funcțiilor care conțin condiții de indiferență ( nu vă pasă , adică valorile de intrare pentru care este irelevant ce este ieșirea): acestea sunt de obicei reprezentate în grilă cu simbolurile *, - sau cu litera greacă $\Delta$ ${\ displaystyle \ Delta}$ $\ Delta$ ( delta ) și poate fi considerat fie 1, fie 0, pentru a forma clustere mai mari. Cu toate acestea, grupările care pur și simplu nu le pasă nu sunt permise .

Notă : Grila trebuie considerată nu ca un plan , ci ca un tor , astfel încât dreptunghiurile să poată traversa marginile, atât pe verticală, cât și pe orizontală, trecând dintr-o parte în opusă. De exemplu, ABD ' ar putea fi, de asemenea, un produs valid.

Limitele hărților Karnaugh

Pentru funcții cu mai mult de 4 variabile devine dificil de utilizat hărțile Karnaugh; de fapt, pentru a încerca să fie intuitivi, acestea ar trebui să devină tridimensionale sau să recurgă la harta introdusă variabilă sau chiar să utilizeze alte hărți suplimentare suplimentare al căror număr crește exponențial pentru fiecare variabilă dincolo de a patra. Numărul acestor combinații este $2^{n-4}$ ${\ displaystyle 2 ^ {n-4}}$ $2 ^ {n-4}$ , unde este $n$ ${\ displaystyle n}$ $n$ este numărul de variabile ale funcției: de exemplu, 5 variabile au nevoie de 2 hărți, 6 variabile au nevoie de 4 hărți, în timp ce 7 variabile au nevoie de 8 hărți ( $2^{3}$ ${\ displaystyle 2 ^ {3}}$ $2 ^ {3}$ ).

Observații

Funcția obținută prin luarea adecvată a grupărilor maxime de 1 din harta Karnaugh este cea minimă, adică este cea care exprimă ieșirea cu cel mai mic număr de termeni și, prin urmare, necesită cel mai mic număr de porți logice pentru a fi realizate.
O alternativă la hărțile Karnaugh, utilă în cazurile deja enumerate, este metoda de simplificare Quine McCluskey .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre harta lui Karnaugh

linkuri externe

A.Bondavalli, Simplificarea funcțiilor logice prin intermediul hărților Karnaugh

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

#	$LA$ ${\ displaystyle A}$ $LA$	$B.$ ${\ displaystyle B}$ $B.$	$C.$ ${\ displaystyle C}$ $C.$	$D.$ ${\ displaystyle D}$ $D.$	$f(A,B,C,D)$ ${\ displaystyle f (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

#	$LA$ ${\ displaystyle A}$ $LA$	$B.$ ${\ displaystyle B}$ $B.$	$C.$ ${\ displaystyle C}$ $C.$	$D.$ ${\ displaystyle D}$ $D.$	$f(A,B,C,D)$ ${\ displaystyle f (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

#	$LA$ ${\ displaystyle A}$ $LA$	$B.$ ${\ displaystyle B}$ $B.$	$C.$ ${\ displaystyle C}$ $C.$	$D.$ ${\ displaystyle D}$ $D.$	$f(A,B,C,D)$ ${\ displaystyle f (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