Číslicová technika · Boolova algebra 2, 3 A 4 PREMENNÉ

Karnaughove mapy & Quine-McCluskey

Komplexná didaktická pomôcka na výučbu optimalizácie logických obvodov: od pravdivostnej tabuľky a zápisu logickou funkciou (ÚSNF / ÚKNF), cez vizuálne zoskupovanie v Karnaughovej mape v Grayovom kóde, až po exaktnú algoritmickú minimalizáciu metódou Quine-McCluskey (hľadanie prvoimplikantov a tabuľka pokrytia).

Počet premenných:
Typické školské úlohy:

1. Pravdivostná tabuľka

Kliknite na Y: 0 → 1 → X
Úplná súčtová normálna forma (ÚSNF / Canonical SOP):
Y = ...
Číselný indexový zápis:
∑ m(...)

2. Karnaughova mapa (Grayov kód)

Minterm (1) Don't care (X)

Bunky mapy sú usporiadané v Grayovom kóde (medzi susednými stĺpcami či riadkami sa mení vždy iba 1 bit: 00 → 01 → 11 → 10). Kraje a rohy mapy logicky susedia (toroidálne prepojenie).

OPTIMÁLNE ZOSKUPENIA (SLUČKY VEĽKOSTI 2k): 0 slučiek
Minimalizovaná Boolova funkcia (SOP): Úspora: 0 %
Y = 0

Žiadne aktívne mintermy (funkcia je trvalo rovná 0).

Algoritmická minimalizácia Quine-McCluskey (Tabuľková metóda)

3. Quine-McCluskey metóda krok za krokom

Zatiaľ čo K-mapa funguje intuitívne do 4 premenných, Quine-McCluskey je exaktný algoritmus vhodný pre počítače.
1 Zoskupenie podľa počtu '1' & Hľadanie prvoimplikantov

Mintermy rozdelíme do skupín podľa váhy (počtu jednotiek). Následne porovnávame susedné skupiny s Hammingovou vzdialenosťou 1 (líšia sa v 1 bite) a nahrádzame ho pomlčkou (-). Prvky, ktoré nemožno ďalej zlúčiť, sú Prvoimplikanty (PI).

2 Tabuľka pokrytia (Výber esenciálnych prvoimplikantov)

Riadky tvoria nájdené prvoimplikanty, stĺpce pôvodné mintermy. Ak má stĺpec iba jeden krížik (×), daný prvoimplikant je esenciálny (EPI) a v rovnici je povinný.

Esenciálne prvoimplikanty (EPI):
(Žiadne)
Výsledná minimalizovaná funkcia (Quine-McCluskey):
Y = 0

Didaktické pravidlá minimalizácie Karnaughovej mapy

Veľkosť slučky = mocnina 2

Slučka môže obsahovať iba 1, 2, 4, 8 alebo 16 susedných jednotiek (2k). Nikdy nie 3, 5 či 6! Čím je slučka väčšia, tým viac premenných vypadne a tým je logický člen úspornejší.

Toroidálny tvar (Okraje a rohy)

Karnaughova mapa nie je plochá tabuľka, ale povrch valca alebo toroidu (pneumatiky). Ľavý okraj susedí s pravým a horný so spodným. Všetky 4 rohy 4-premennej mapy tvoria platnú slučku veľkosti 4!

Neurčené stavy (Don't care – X)

Stavy 'X' sú vstupné kombinácie, ktoré v praxi nemôžu nastať (napr. BCD kódy 10 až 15). V K-mape ich môžeme zahrnúť do slučky, ak nám pomôžu vytvoriť väčšiu skupinu, alebo ich ignorovať, ak nepomáhajú.