05. Hărţi Karnaugh, tabele de adevăr şi expresii booleene

Acasă » Electronică digitala » 08 - Hărţi Karnaugh

Metode diferite de reprezentare a funcţiilor logice

Hărţile Karnaugh simplifică funcţiile logice mult mai rapid şi mai uşor în comparaţie cu algebra booleană. Dorim simplificarea circuitelor logice spre cel mai mic cost posibil prin eliminarea componentelor. Definim cel mai mic cost ca fiind cel mai mic număr de porţi cu cel mai mic număr de intrări pe poarta.

Mai jos am reprezentat cinci metode diferite de reprezentare a aceluiaşi lucru: o funcţie logică aleatoare cu două intrări. Metodele sunt: logica ladder, porţi logice, tabel de adevăr, hartă Karnaugh şi ecuaţie booleană. Ceea ce vrem să subliniem este că toate acestea sunt echivalente. Două intrări A şi B pot lua valori de 0 sau 1, înalt sau jos, deschis sau închis, adevărat sau fals, în funcţie de caz. Există 2² = 4 combinaţii pentru generarea unei ieşiri. Acest lucru se aplică tuturor celor cinci exemple.

Aceste patru ieşiri pot fi observate prin intermediul unei lămpi la ieşirea circuitului ce utilizează logica ladder. Aceste ieşiri pot fi înregistrate într-un tabel de adevăr sau într-o hartă Karnaugh. Priviţi harta Karnaugh ca şi un tabel de adevăr „cosmetizat”. Ieşirea ecuaţiei booleene poate fi obţinută cu ajutorul legilor algebrei booleene şi transferată tabelului de adevăr sau hărţii Karnaugh. Care din cele cinci metode echivalente de reprezentare ar trebui să o folosim? Cea mai folositoare pentru situaţia în cauză.

Ieşirile unui tabel de adevăr corespund unu-la-unu elementelor unei hărţi Karnaugh. Începând cu partea de sus a tabelului de adevăr, intrările A = 0 şi B = 0 produc ieşirea α. Observaţi că aceiaşi ieşire, α, se regăseşte pe harta Karnaugh la adresa A = 0, B = 0, în partea de sus stânga, la intersecţia coloanei B = 0 cu rândul A = 0. Celelalte ieşiri ale tabelului de adevăr, β, χ respectiv δ, corespunzătoare intrărilor AB = 01, 10 respectiv 11 au de asemenea corespondent pe harta Karnaugh:

Structura hărţilor Karnaugh

Pentru uşurinţa expunerii, prezentăm mai jos regiunile adiacente ale hărţii Karnaugh cu două variabile folosind metoda dreptunghiulară a diagramei Venn din secţiunea precedentă:

Regiunile α şi χ sunt adiacente pe harta Karnaugh. Nu putem spune acelaşi lucru despre tabelul de adevăr precedent, întrucât există o altă valoare (β) între ele. Acesta este şi motivul organizării hărţilor Karnaugh sub formă de matrice pătrată. Regiunile cu variabile booleene comune trebuie să se afla una lângă cealaltă. Această structură este şi trebuie să fie uşor de recunoscut când privim o astfel de hartă, din moment ce α şi χ au variabila B' în comun. Ştim acest lucru deoarece B este 0 (identic cu B') pentru coloana de deasupra celor două regiuni. Comparaţi acest lucru cu diagrama Venn de deasupra hărţii Karnaugh.

În aceiaşi ordine de idei, putem observa că β şi δ au ca şi variabilă comună B (B = 1). Prin urmare, α şi β au în comun variabila booleană A' (A = 0), iar χ şi δ variabila A (A = 1).

Pe scurt, am încercat să grupăm variabilele booleene pe regiuni astfel încât să reiasă elementele lor comune. Hărţile Karnaugh sunt organizate pentru a ne oferi exact această „imagine”.

Exemple de utilizare a hărţilor Karnaugh

Exemplul 1

Tabelul de adevăr de mai jos conţine două valori de 1. Harta Karnaugh trebuie să conţină şi ea tot două valori de 1:

• Luăm prima valoare de 1 din rândul al doilea al tabelului de adevăr
• Observăm adresa AB a tabelului de adevăr
• Localizăm regiunea hărţii Karnaugh ce conţine aceiaşi adresă
• Scriem un 1 în acea regiune
• Repetăm procesul pentru valoarea 1 din ultima linie a tabelului de adevăr

Să încercăm să scriem acum pentru harta Karnaugh de mai sus şi expresia booleană. Soluţia este prezentată mai jos:

• Căutam regiuni adiacente (regiunile diagonale nu sunt adiacente), întrucât acestea vor avea una sau mai multe variabile booleene în comun
• Grupăm cele două valori de 1 din coloană
• Căutăm acea sau acele variabile ce sunt comune pentru grup şi scriem acest lucru ca şi rezultat boolean (în cazul nostru acesta este B)
• Ignorăm variabilele ce nu sunt identice pentru un grup de regiuni (în cazul nostru, A variază, este atât 1 cât şi 0, prin urmare, ignorăm A)
• Ignorăm de asemenea orice variabilă ce nu este asociată cu regiunile ce conţin 1 (B' nu conţine niciun 1, prin urmare, ignorăm B')
• Rezultatul final şi prin urmare expresia booleană asociată hărţii Karnaugh precedente este B

Acest lucru poate fi observat mai uşor comparând diagramele Venn din dreapta, în mod special coloana B.

Exemplul 2

Scrieţi expresia booleană asociată hărţii Karnaugh de mai jos:

Urmând o logică asemănătoare celei de mai sus, grupăm toate valorile de 1 şi găsim variabila comună întregului grup astfel format; rezultatul este A'.

Exemplul 3

Pentru tabelul de adevăr de mai jos, găsiţi harta Karnaugh corespunzătoare şi scrieţi apoi expresia booleană folosind rezultatul obţinut. Soluţia este prezentata mai jos:

• Transferăm valorile de 1 din tabelul de adevăr în locaţiile corespunzătoare pe harta Karnaugh
• Grupăm cele două valori de 1 pe coloana de sub B = 1
• Grupăm cele două valori de 1 de pe rândul A = 1
• Scriem rezultatul produsului primului grup (B)
• Scriem rezultatul produsului celui de al doilea grup (A)
• Scriem suma produselor celor doi termeni de mai sus (A + B)

Soluţia din mijloc este cea mai simplă şi prezintă cel mai mic cost. O soluţie mai puţin dorită este cea din dreapta. După gruparea valorilor 1, facem greşeala de a forma un grup cu o singură regiune. Motivul pentru care acest lucru nu este de dorit este următorul: acest grup ce conţine o singură regiune are termenul produsului egal cu AB'; soluţia întregii hărţii este în acest caz AB' + B, iar aceasta nu reprezintă cea mai simplă soluţie.

Metoda corectă constă în gruparea acestui 1 singur cu regiunea din dreapta lui, regiune ce conţine la rândul ei o valoare de 1, chiar dacă aceasta a fost deja inclusă într-un alt grup. (coloana B). Putem refolosi regiuni pentru a forma grupuri mai mari. De fapt, este chiar indicat să facem acest lucru întrucât conduce la rezultate mai simple.

Trebuie să facem observaţia că oricare dintre soluţiile de mai sus, atât cea corectă cât şi cea „greşită” sunt de fapt corecte din punct de vedere logic. Ambele circuite vor genera aceiaşi ieşire. Pur şi simplu, circuitul corect presupune un cost mai redus de implementare fizică.

Exemplul 4

Completaţi o hartă Karnaugh folosind expresia booleană de mai jos. Scrieţi apoi expresia booleană a rezultatului:

Expresia booleană conţine trei sume de produse. Va exista câte o valoare de 1 pe harta Karnaugh pentru fiecare produs. Deşi, în general, numărul valorilor de 1 pe produs variază cu numărul variabilelor produsului în comparaţie cu mărimea hărţii Karnaugh. Termenul produsului reprezintă adresa regiunii unde vom introduce valoare de 1. Primul termen este A'B şi corespunde adresei 01 a hărţii. Introducem un 1 în această regiune. Similar, introducem şi ceilalţi doi termeni de 1.

Trecem apoi la gruparea termenilor şi simplificarea rezultatului conform exemplului precedent.

Exemplul 5

Simplificaţi circuitul logic de mai jos:

• Scriem expresia booleană pentru circuitul logic iniţial
• Transferăm expresia booleană rezultată într-o hartă Karnaugh
• Grupăm regiunile precum în exemplele precedente
• Scriem expresii booleene pentru fiecare grup, conform exemplelor precedente
• Redesenăm circuitul logic simplificat

Exemplul 6

Simplificaţi circuitul logic de mai jos:

• Scriem expresia booleană pentru circuitul logic iniţial
• Completăm harta Karnaugh
• Observăm că nu putem forma niciun grup care să conţină mai mult de două regiuni 1
• Prin urmare, simplificarea nu este posibilă, iar expresia finală este identică cu cea iniţială (SAU-exclusiv)