Podcast na Jak navrhnout logický obvod z pravdivostní tabulky

Kapitoly

Zbytečně složité?

Od tabulky k výrazu

Kouzlo minimalizace

Příklad se zámkem

Běžné chyby a na co si dát pozor

Booleova algebra

Kouzlo Karnaughovy mapy

Od mapy k výsledku

Srovnání v praxi

Hraní s hradly

Závěrečné shrnutí

Přepis

Adéla: Hele, Vojtěchu, představ si, že máš rovnici: Z se rovná (A s pruhem krát B krát C) plus (A krát B s pruhem krát C s pruhem) plus… a tak dál, celkem pět složitých členů. Co bys řekl, kdybych ti tvrdila, že tohle popisuje jednoduchý kombinační zámek?

Vojtěch: Řekl bych, že máš sice pravdu... ale že je to taky ten nejsložitější a nejméně efektivní způsob, jak ten zámek popsat. Většina lidí si myslí, že návrh obvodů je o vytváření takových složitých rovnic. Ve skutečnosti je to přesně naopak — je to o tom, jak z takového monstra udělat něco elegantního a jednoduchého.

Adéla: Aha! Takže ta složitost je jenom výchozí bod, ne cíl? Tohle je Studyfi Podcast.

Vojtěch: Přesně tak. Tyhle obvody jsou všude — v mobilech, počítačích, v pračce… a nikdo nechce, aby byly zbytečně drahé, pomalé a aby moc „žraly“. A proto je musíme umět navrhovat a hlavně zjednodušovat.

Adéla: Dobře, tak kde ten proces začíná? Předpokládám, že ne u té šílené rovnice.

Vojtěch: Správně. Začíná to u takzvané pravdivostní tabulky. To je vlastně jenom seznam všech možných kombinací vstupů a toho, co chceme, aby obvod udělal na výstupu. Pro každý případ si prostě řekneme: teď má být výstup 1, teď zase 0.

Adéla: Takže je to jako takový jízdní řád pro ten obvod? Vstup A, B, C je takový, takže výstup Z bude makový.

Vojtěch: Perfektní přirovnání! A z tohohle „jízdního řádu“ pak můžeme vytvořit ten logický výraz. Existují dva hlavní způsoby. První je disjunktivní normální forma, zkráceně DNF. Tam se soustředíme na řádky, kde má být výstup 1. Pro každý takový řádek vytvoříme malý součin.

Adéla: To zní jako ta rovnice ze začátku. Spousta věcí, co se sčítají dohromady.

Vojtěch: Přesně tak. Součet součinů. A pak je tu opak, konjunktivní normální forma, CNF. Tam se naopak díváme na řádky, kde je na výstupu 0, a vytváříme součin součtů.

Adéla: A který z nich si mám vybrat?

Vojtěch: Vybíráš si ten, který bude na začátku jednodušší. Pokud máš v tabulce málo jedniček, použiješ DNF. Pokud máš málo nul, sáhneš po CNF. Cílem je ušetřit si práci hned na startu.

Adéla: Dobře, takže mám výraz. Ale tys na začátku říkal, že ten dlouhý, co jsem četla, je špatný. Proč?

Vojtěch: Protože je zbytečně složitý! A teď přichází to kouzlo — minimalizace. To je proces, kdy ten dlouhý a ošklivý výraz zjednodušíme na nejmenší možnou formu, která ale dělá pořád to samé.

Adéla: A proč je to tak důležité? Jestli to funguje, tak to funguje, ne?

Vojtěch: To sice jo, ale představ si to takhle: každý člen v té rovnici, každá operace „krát“ nebo „plus“, je v reálném světě součástka — logické hradlo. Čím víc členů, tím víc součástek. A víc součástek znamená, že obvod je dražší na výrobu, pomalejší a spotřebuje víc energie.

Adéla: Jasně, takže minimalizace šetří peníze, čas i baterku v mobilu.

Vojtěch: Přesně tak! A jedním z nejmocnějších nástrojů pro ruční minimalizaci je Karnaughova mapa. To je taková speciální tabulka, do které si přepíšeš výstupy z pravdivostní tabulky a pak v ní hledáš skupiny jedniček.

Adéla: Pojďme si to ukázat na příkladu. Co ten náš kombinační zámek? Tři tlačítka A, B, C. Otevře se (výstup Z=1), když je stisknuté jen A, anebo když jsou stisknutá B a C zároveň.

Vojtěch: Skvělý příklad. Když si pro tohle sestavíme pravdivostní tabulku, zjistíme, že výstup Z=1 máme v pěti řádcích. Kdybychom z toho udělali DNF výraz bez zjednodušení, dostaneme přesně tu hrůzu, co jsi říkala na začátku.

Adéla: Z = (A̅·B·C) + (A·B̅·C̅) + (A·B̅·C) + (A·B·C̅) + (A·B·C). Brr.

Vojtěch: Přesně. Ale teď vezmeme ty jedničky, zakreslíme je do Karnaughovy mapy a začneme hledat co největší skupiny. V tomto případě najdeme jednu velkou skupinu čtyř jedniček, která odpovídá situaci, kdy A=1. A z téhle celé skupiny nám po zjednodušení zbyde jen... A.

Adéla: Počkej, z čtyřikrát tří proměnných zbyde jen jedna? To je docela úspora.

Vojtěch: Přesně! A pak nám zbývá ještě jedna jednička, kterou spojíme se sousední a vytvoříme druhou skupinku. Ta se nám zjednoduší na výraz B·C. Takže celý ten ošklivý výraz se nám smrsknul na Z = A + (B·C).

Adéla: Takže „otevři, když je A rovno jedné, NEBO když je B a C rovno jedné“. To dává naprostý smysl! A obvod je pak mnohem jednodušší — jen jedno hradlo AND a jedno hradlo OR.

Adéla: Kde studenti nejčastěji chybují, když se snaží takhle kouzlit s Karnaughovou mapou?

Vojtěch: Nejčastější chybou je špatné tvoření skupin. Lidi spojují buňky, které spolu nesousedí, nebo zapomínají, že mapa je vlastně spojená přes okraje — jako bys z ní sroloval válec.

Adéla: Takže levý a pravý sloupec spolu sousedí?

Vojtěch: Přesně tak! A horní s dolním taky. Další chybou je, že se spokojí s malými skupinkami, i když by mohli vytvořit větší. Cílem je vždy pokrýt všechny jedničky co nejmenším počtem co největších skupin. Je to taková malá strategická hra.

Adéla: A co ty stavy „don't care“?

Vojtěch: To je takový žolík. Jsou to kombinace vstupů, u kterých je nám jedno, co bude na výstupu, protože třeba nikdy nemůžou nastat. A tyhle stavy, značené jako X, můžeme libovolně zařadit do skupiny, pokud nám to pomůže ji zvětšit. Ale nemusíme je pokrývat, pokud nechceme. Kdo je ignoruje, připravuje se o tu nejlepší možnou minimalizaci.

Adéla: Super. Takže až si to budou chtít naši posluchači vyzkoušet v simulátoru, měli by si postavit oba obvody? Ten složitý i ten jednoduchý?

Vojtěch: Určitě! Postavte si obvod pro Z = A + (B·C). Připojte vstupy A, B, C na přepínače a výstup Z na LEDku. A pak si zkuste ověřit, že se LEDka rozsvítí přesně v těch případech, které jsme si řekli. Uvidíte, že ta jednoduchá rovnice dělá přesně to, co ta složitá, ale s mnohem menším úsilím.

Adéla: Takže máme ty dlouhé, skoro nekonečné výrazy z minula. To přece nemůže být konec, že? Musí existovat nějaký způsob, jak to celé zjednodušit a zefektivnit.

Vojtěch: Přesně tak, Adélo. A tomu se právě říká minimalizace logických funkcí. Cílem je najít nejjednodušší možný obvod, který dělá úplně to samé. Je to jako uklidit si v pokoji, ale pro elektroniku.

Adéla: Tak jdeme na ten úklid! Kde začneme?

Vojtěch: První metoda je v podstatě matematická. Jmenuje se minimalizace pomocí Booleovy algebry. Používáme sadu pravidel a identit, abychom ten výraz algebraicky zkrátili.

Adéla: Takže zpátky do lavic a upravovat rovnice? Co jsou to za pravidla?

Vojtěch: Jsou to takové logické zkratky. Třeba že proměnná A plus 0 je pořád A. Nebo že A plus její vlastní negace je vždy 1. A samozřejmě slavné De Morganovy zákony.

Adéla: To zní... docela pracně. Zvlášť jestli je ten výraz dlouhý.

Vojtěch: Přesně. Pro jednoduché funkce je to fajn, ale u složitějších je to snadné přehlédnout nějaké zjednodušení nebo udělat chybu. Je to taková ruční práce, která se může protáhnout.

Adéla: Existuje tedy nějaký chytřejší, vizuálnější způsob? Něco, kde tu chybu neudělám tak snadno?

Vojtěch: A jaký! Jmenuje se Karnaughova mapa, zkráceně K-mapa. Je to geniální grafická metoda, která je super efektivní pro funkce se dvěma až pěti proměnnými.

Adéla: Mapa? Jako mapa pokladu k nalezení nejjednoduššího výrazu?

Vojtěch: Vlastně jo! Představ si to jako speciální mřížku. Každá buňka v té mřížce odpovídá jednomu řádku v pravdivostní tabulce. A teď to hlavní – buňky jsou uspořádané tak, že sousedi se liší jen v jedné jediné proměnné.

Adéla: Dobře, takže máme mřížku. Co s ní dál?

Vojtěch: Jednoduše. Podle pravdivostní tabulky vyplníš do buněk jedničky a nuly. A pak začne ta zábava. Hledáš sousední jedničky a snažíš se je spojit do co největších skupin. Velikost skupiny musí být mocnina dvou – takže dvě, čtyři, osm jedniček.

Adéla: A ty skupiny se můžou i překrývat?

Vojtěch: Přesně tak! A co víc, mapa se chová, jako by byla nakreslená na povrchu donutu. Takže levý okraj sousedí s pravým a horní se spodním. Můžeš tak spojit jedničky přes okraje.

Adéla: Dobře, mám zakroužkované skupinky jedniček. Co teď? Jak z toho dostanu ten zjednodušený výraz?

Vojtěch: Pro každou skupinu se podíváš, které proměnné se v ní nemění. Ty, které mění svou hodnotu z nuly na jedničku nebo naopak, jednoduše vyškrtneš. Zůstanou ti jen ty stabilní, a ty tvoří jeden zjednodušený člen.

Adéla: Aha! Takže čím větší skupina, tím víc proměnných vypadne a tím jednodušší bude výsledek.

Vojtěch: Přesně! Mám tu jeden skvělý příklad. Představ si funkci tří proměnných, která má v K-mapě sloupec čtyř jedniček. Po zakroužkování celé téhle velké skupiny zjistíme, že se změnily dvě proměnné a jen jedna, třeba C, zůstala konstantní. Výsledná funkce je F rovná se C.

Adéla: Počkej... takže celý ten složitý výraz, který by mohl mít třeba čtyři dlouhé členy, se smrskne jen na jedno písmenko? To je neuvěřitelné!

Vojtěch: Je, že? To je síla K-map. Umožní nám vidět ta zjednodušení, která bychom v algebře mohli snadno přehlédnout. Ale samozřejmě, má to své limity.

Adéla: Jasně, říkal jsi tak do pěti proměnných. Co když jich máme víc? Třeba deset? To už asi na papír nenakreslíme, co?

Adéla: Takže máme ten krásně zjednodušený výraz z minula. Ale jak si ověříme, že to opravdu funguje stejně jako ten původní, složitý?

Vojtěch: Výborná otázka, která nás vede k té nejzábavnější části — k simulaci. Doporučuju zkusit sestavit obvod pro oba výrazy. Ten náš minimalizovaný i ten původní, dlouhý.

Adéla: Pro ten se všemi těmi závorkami a čárkami nahoře? To bude asi... hodně propojování a zmatku.

Vojtěch: Přesně! A právě v tom je to kouzlo. Okamžitě uvidíte, že oba obvody se chovají stejně, ale ten náš je mnohem elegantnější a efektivnější.

Adéla: Dobře, to dává smysl. A co dál si můžeme v simulátoru vyzkoušet, když s tím začínáme?

Vojtěch: Prostě si hrajte. Berte si jednotlivá hradla — AND, OR, NOT — a sledujte, co dělají. Je to jako takové digitální LEGO. Spojujte je, přidávejte negace na vstupy a pozorujte, jak se mění výstup.

Adéla: Digitální LEGO, to je skvělé přirovnání! A když už se budeme cítit odvážnější?

Vojtěch: Pak je tu ta nejlepší zkouška. Vymyslete si vlastní jednoduchou funkci. Třeba „kontrolka svítí, když je stisknutý lichý počet tlačítek“. A zkuste si ji navrhnout od začátku až do konce.

Adéla: Takže klíčové je, že simulátor je takové bezpečné hřiště, kde si všechno můžeme osahat a pochopit bez rizika. To je perfektní shrnutí nejen tohoto tématu, ale vlastně celého našeho povídání.

Vojtěch: Přesně tak. Doufám, že jsme vám ukázali, že logické obvody nejsou žádná černá magie, ale spíš zábavná skládačka. Děkuji za pozvání a za skvělé otázky.

Adéla: I já děkuji, Vojtěchu. A vám, milí posluchači, děkujeme za pozornost u dalšího dílu Studyfi Podcastu. Mějte se hezky a u slyšenou příště!