Karnaugh kaardiga lihtsustamine

Allikas: Teadmusbaas

Karnaugh kaart

Karnaugh’ kaart on loogikafunktsiooni tõeväärtustabeli sihipärane topoloogiline ümberpaigutus tasandil või ruumis. Tõeväärtustabeli igale reale vastab Karnaugh’ kaardi üks ruut. Kaartide topoloogia:

  • 2-muutuja kaart on mõõtmetega 2x2 (või 1x4) ruutu, vt sele 1;
  • 3-muutuja kaart on mõõtmetega 2x4 ruutu, vt sele 2;
  • 4-muutuja kaart on mõõtmetega 4x4 ruutu, vt sele 3;
  • 5-muutuja kaart on ruumiline kaart mõõtmetega 2x 4x4 ruutu (analoog oleks 2 Excel töölehte 4x4 tabelitega);
  • 6-muutuja kaart on ruumiline kaart mõõtmetega 4x 4x4 ruutu (analoog oleks 4 Excel töölehte 4x4 tabelitega).

Suuremaid kaarte ei ole olemas, ka 5 ja 6 muutujaga kaartide kasutamine on haruldane nende keerukuse tõttu.

Karnaugh’ kaardi 1. põhiomadus:

kaardi iga ruudu naaberruutude arv võrdub kaardi muutujate arvuga

Seega on 2-muutuja kaardi igal ruudul 2 naaberruutu, 3-muutuja kaardil 3 naaberruutu jne Argumentvektorite paiknemine kaardi ruutudes: igale kaardi ruudule vastab loogikafunktsiooni üks argumentvektor (n-järguline kahendvektor)

Karnaugh’ kaardi 2. põhiomadus:

suvalise kahe naaberruudu argumentvektorid on teineteise lähiskoodid*

          • lähiskoodid on kahendvektorid, mis erinevad teineteisest ainult ühes oma kahendjärgus

Karnaugh kaartide näited (paigutused) on toodud seledel allpool, vt seled 1 kuni 3

Karnaugh2.png

Sele 1. Kahe muutujaga Karnaugh kaart

Karnaugh3.png

Sele 2. Kolme muutujaga Karnaugh kaart

Karnaugh4.png

Sele 3. Nelja muutujaga Karnaugh kaart

Loogikafunktsiooni muutujad on tähistaud tähtedega A..D, funktsiooni kasutamisel vastavad muutujad oleksid x1..x4. Arvude järjekord kaardi kohal pole mitte kahendkood vaid Gray kood, vt vastavustabelit 1

Tabel 1. Kümnendarvude, kahendarvude ja Gray koodi vastavus
10-arv KahendarvGray kood
0 00000000
1 00010001
2 00100011
3 00110010
4 01000110
5 01010111
6 01100101
7 01110100
8 10001100
9 10011101
1010101111
1110111110
1211001010
1311011011
1411101001
1511111000

Karnaugh’ kaardi kontuurid on kindlate mõõtmetega ruutude grupid. Tasandilise kaardi kontuurid on ristkülikud lubatud küljepikkusega 2 astmel täisarv, kuna 2 astmel 3 on 8, siis see ei mahu füüsiliselt ühelegi kaardile ja nii jäävad üle kontuuride küljepikkused 1,2 ja 4. Mitte kunagi ei saa kontuuri külje pikkus olla 3!

Kontuuride ja intervallide seos. Kahendvektorite kindlate tunnustega hulka nimetatakse intervalliks. Karnaugh’ kaardi iga kontuur vastab kahendvektorite mingile kindlale intervallile, vt sele 4.

Karnaugh1.png

Sele 4. Kaardi kontuurid ja neile vastavad intervallid

Karnaugh’ kaardi piirkonnad.

N-muutujaga kaardil on 2N omavahel kattuvat piirkonda, mis on määratud kaardi loogikamuutujate kõikvõimalike väärtustega: x1 = 0, x1 = 1, x2 = 0, x2 = 1 … xn = 0, xn = 1, kaardi piirkonnad võib tähistada vastavalt NOT(x1), x1, NOT(x2), x2 … NOT(xn), xn (eitused järgmisel selel (sele 5) on tähistatud ülakriipsuga muutujal). Iga piirkond on täpselt „pool kaart“ suur ehk tema koosseisu kuuluvad suvalise kaardi puhul täpselt pooled kaardi kõikidest ruutudest. Selel 5 on näidatud 3-muutuja kaardi kõik 6 piirkonda (igaühe suurus on 4 ruutu) ja 4-muutuja kaardi kõik 8 piirkonda (igaüks 8 ruutu).

Karnaugh5.png

Sele 5. Karnaugh' kaardi piirkonnad muutujate järgi

Järg Loogikafunktsioonide minimeerimine

Tagasi loogikafunktsioonide esituskujud lehele

Väino Liimann