Card Carnot Carnot

1 Principiile minimizării
2 Descriere
3 Exemple
- 3.1 Exemplul 1
- 3.2 Exemplu de hartă Carnot în cinci variabile
- 3.3 Exemplu de hartă Carnot mare în opt variabile

Fig. 1 Exemplu de Carnot Maps

Harta Carnot este o modalitate grafică de a minimiza funcțiile de comutare (booleană), oferind o simplitate relativă de lucru cu expresii mari și eliminând cursele potențiale. Este o operație de lipire incompletă pe perechi și absorbție elementară. Carnoturile Carnot sunt tratate ca o tabelă a adevărului rearanjată a funcției. Carnoturile Carnot pot fi considerate ca o anumită scanare plat a unui cub Boolean n-dimensional.

Karnaugh hartă a fost inventat în 1952 de către Edward W. Veitch și îmbunătățit în 1953 de Maurice Karnaugh, un fizician de la «Bell Labs», și au fost concepute pentru a ajuta la simplificarea circuitele digitale.

În harta Carnot, variabilele booleene sunt transmise din tabelul de adevăr și sortate folosind codul gri, în care fiecare următor număr diferă de cel precedent cu doar o singură cifră.

1. Principiile minimizării

Principala metodă de minimizare a funcțiilor logice, reprezentată sub formă de SDNF sau SKNF, este operația de lipire parțială parțială și absorbție elementară. Operația de lipire pe perechi se efectuează între doi termeni (membri) care conțin aceleași variabile ale căror apariții (linii și inverse) coincid pentru toate variabilele, cu excepția uneia. În acest caz, toate variabilele cu excepția unuia pot fi scoase din paranteze, iar celelalte evenimente directe și inverse ale unei variabile din paranteze sunt lipite împreună. De exemplu:

În mod similar pentru CNF:

Posibilitatea de absorbție rezultă din egalitatea evidentă

Astfel, principala sarcină în minimizarea SDNF și SKNF este de a căuta termeni potriviți pentru lipire cu absorbție ulterioară, care pentru formele mari poate fi o provocare. Carnoturile Carnot oferă o modalitate vizuală de a găsi astfel de termeni.

După cum se știe, funcțiile booleene ale variabilelor N, reprezentate ca SDNF sau SKNF, pot avea 2 N termeni diferiți în compoziția lor. Toți acești termeni constituie o structură topologică echivalentă cu un cub N-dimensional și oricare doi termeni alături de o margine sunt potriviți pentru lipire și absorbție.

Figura arată un simplu tabel de adevăr pentru funcția de două variabile corespunzătoare acestui tabel cub 2-dimensional (pătrat) și cubul 2-dimensional cu membrii desemnare PDNF și tabelul echivalente pentru grupuri de termeni:

În cazul unei funcții a trei variabile, trebuie să ne ocupăm de un cub tridimensional. Acest lucru este mai complicat și mai puțin evident, dar posibil din punct de vedere tehnic. În figură, tabelul de adevăr pentru o funcție booleană a trei variabile și cubul corespunzător sunt prezentate ca un exemplu.

Așa cum se poate observa din figură, pentru un caz tridimensional, sunt posibile configurații termale mai complexe. De exemplu, patru termeni aparținând aceleiași fețe a cubului sunt combinate într-un singur termen cu absorbția a două variabile:

În cazul general, putem afirma că termenii 2 K aparținând aceleiași fețe K-dimensionale ale hipercubei sunt lipite împreună într-un singur termen, în timp ce variabilele K sunt absorbite.

Pentru a simplifica munca cu funcții booleene a unui număr mare de variabile, a fost propusă următoarea metodă convenabilă. Cubul, care este o structură pe termen, se desfășoară pe plan, așa cum se arată în figură. Astfel, devine posibil să reprezinte funcții booleene cu mai mult de două variabile sub forma unui tabel plat. Trebuie reamintit faptul că ordinea termenilor din tabelul codurilor (00 01 11 10) corespunde ordinii secvenței de numere binare, iar celulele din coloanele exterioare ale mesei, învecina reciproc.

În mod similar, puteți lucra cu funcții de patru, cinci sau mai multe variabile. Exemple de tabele pentru N = 4 și N = 5 sunt prezentate în figură. Pentru aceste tabele trebuie amintit faptul că sunt celulele localizate în celulele corespunzătoare coloanelor respective și celulele extreme ale șirurile superioare și inferioare vecine. Pentru tabelele 5 și mai multe variabile trebuie luate în considerare, de asemenea, că pătratele 4x4 sunt practic suprapusă în a treia dimensiune, astfel încât respectivele două celule vecine sunt pătrate 4x4 sosoednimi, iar termenii corespunzători pot fi lipite.

2. Descrierea

Hărțile Carnot pot fi compuse pentru orice număr de variabile, totuși este convenabil să lucrați cu numărul de variabile nu mai mari de cinci. De fapt, harta Carnot este o tabelă de adevăr compusă în formă 2-dimensională. Prin folosirea codului Gray în el, rândul de sus este adiacent rândului de jos, iar coloana din dreapta este adiacentă cu cea din stânga, deci Întreaga Carnot Map este pliată într-o figură torus (bagel). La intersecția rândului și coloanei, se introduce valoarea corespunzătoare din tabelul de adevăr. Odată ce harta este plină, puteți continua să minimizați.

Dacă este necesar să obținem un DNF minim, atunci în Hartă luăm în considerare numai acele celule care conțin unități, dacă este nevoie de CNF, atunci considerăm acele celule care conțin zerouri. Minimizarea se face în conformitate cu următoarele reguli (pe exemplul DNP):

combina celule adiacente conținând unități din regiune, astfel încât o regiune cuprinde 2 n (n este un număr întreg = 0, ...) celule (amintiți-vă de faptul că rândurile extreme și coloanele sunt adiacente unul la celălalt), în regiune nu ar trebui să fie celule conținând zerouri;
zona ar trebui să fie localizată simetric față de axa (axele sunt localizate la fiecare patru celule);
zonele adiacente, situate simetric față de axa (axele), pot fi combinate într-una;
zona ar trebui să fie cât mai mare posibil, iar numărul de regiuni să fie cât mai mic posibil;
zonele se pot suprapune;
există mai multe opțiuni de acoperire posibile.

În continuare, să ia prima regiune și a vedea ce variabile nu se schimbă în acest domeniu, scrie conjugarea acestor variabile, neschimbat dacă variabila este nul, ștanțat pe ea inversiune. Luăm următoarele aspecte, facem același lucru ca și pentru primul și așa mai departe pentru toate regiunile. Conjuncția regiunilor este unită prin disjuncție.
De exemplu (pentru Hărți pentru 2 variabile):

CNF pentru aceleași lucruri, ia în considerare numai celulele cu zerouri, nu schimbă variabile în aceeași zonă se combină într-o disjuncție (inversiune ștanțat pe variabila unică), iar zonele disjuncție se combină în conjuncție. În acest sens, minimizarea este considerată completă. Deci, pentru harta Carnot în Figura 1, expresia în format DNF va arata ca:
În formatul CNF:

În mod similar, de la DNF la CNF și invers, se poate folosi Legea lui de Morgan.

3. Exemple

3.1. Exemplul 1

Baiatul Kolya are o mamă, un tată, un bunic și o bunică. Kolya va merge pe jos pe stradă, dacă îi vor permite cel puțin două rude.
Pentru scurtcircuit, hai să remarcăm rudele lui Kolya prin literele:
mama - x1
tată - x2
bunicul - x3
bunica - x4
Să fim de acord să denotăm acordul rudelor de către unitate, nu acordul prin zero. Posibilitatea de a merge pe jos este marcată de litera f, Kolya merge pentru o plimbare - f = 1, Kolya nu merge pentru plimbări - f = 0.
Să compilam tabelul de adevăr:

Redestim tabelul de adevăr într-o formă bidimensională:

Transpuneți rândurile și coloanele în ea conform codului Gray. Au primit Harta Carnotului:

Avem o astfel de tabelă de adevăr:

Harta Carnot va arăta astfel (pentru o percepție vizuală mai bună pe hartă, nu se înregistrează zerouri):

Greșit (pe baza exemplului DNP):

- Zona S1 - acoperită corect;
- Zona S2 - încalcă clauza 1;
- Zona S3 - încalcă clauza 2;
-Zonele S4 și S6 - nu îndeplinesc clauza 3, aceasta nu este o eroare - expresia va fi mai mare decât dacă S4 și S6 ar fi o zonă;
- Zona S5 - încalcă clauza 1 cu numărul de celule și prin inadmisibilitatea de a găsi zerouri în zonă.

Corect, dar nu optim:

Această hartă Carnot este minim non-optimă, deoarece este posibilă combinarea unităților membre S3 și S5.

Minimizând acest card, obținem următoarele DNF:

Vom compila CNF minim: