Aktuální vydání

celé číslo

06

2019

Počítačová podpora vývoje a výroby, software pro řízení údržby 

celé číslo

Inspiromat pro výuku a Tecomat: logika (nejenom) pro programátory – Díl druhý (část 4)

Sousednost políček v K-mapě je ale složitější. Za sousední jsou obecně považována políčka, která se liší v hodnotě jedné proměnné. Jako sousední lze tedy sdružit i políčka, která leží na protilehlých okrajích mapy (obr. 17). Názorně by sousednost byla viditelná, kdybychom umístili čtveřici stejných map vedle sebe (obr. 18). Nepříliš názorné je stanovení sousednosti v K-mapě pro více než čtyři proměnné. Na obr. 19 je pro ilustraci zvolena K-mapa pro čtyři proměnné ve formátu 8 × 2 políček. V tomto případě by pomohla představa třírozměrné mapy, kterou bychom vytvořili rozříznutím podle svislé osy a sklopením obou částí podle této osy, jako bychom zavírali knihu. Právě přehlednost je důvodem, proč se v praxi používají K-mapy pro maximálně čtyři operandy, výjimečně více. Pak již nelze zaručit důslednou minimalizaci – ale i jen částečná minimalizace může být prospěšná.

Řešíme-li neúplně zadanou logickou funkci, je možné zvolit několik postupů. Na obr. 20a je uveden příklad neúplně zadané funkce (je zvolena fiktivní funkce, jen pro ilustraci výkladu). Křížkem jsou označena políčka, ve kterých funkce není definována – na funkční hodnotě nezáleží nebo je odpovídající kombinace operandů nedostupná. V těchto políčkách je možné zvolit hodnotu funkce nulovou (obr. 20b) nebo jedničkovou (obr. 20c). Hodnoty funkce však lze dodefinovat tak, abychom získali nejjednodušší řešení funkce (obr. 20d).

Někdy je výhodnější řešit místo zadané funkce její negaci, protože poskytuje jednodušší řešení.

 Úloha 6

Vytvořte logický výraz neúplně zadané funkce podle variant K-mapy z obr. 20b, c, d a porovnejte jejich složitost.

 Pro některé funkce popsaný způsob nepřináší významnou úsporu. Například obrazce pokrytí K-mapy funkcí liché parity (a schodišťového vypínače) z obr. 14 připomínají šachovnici. Na obr. 21 je uveden příklad této funkce pro šest operandů – i zde má obrazec pokrytí stejný charakter. Dosud uvedenými postupy je tato funkce naprosto neminimalizovatelná, protože pro žádné jedničkové políčko mapy neexistuje sousední políčko s jedničkovou hodnotou. Přitom tuto funkci lze jednoduše popsat s použitím operátoru XOR jako výraz:

licha := a XOR b XOR c XOR d;

 Podobně lze sudou paritu popsat výrazem:

suda := NOT (a XOR b XOR c XOR d);

 nebo rovnocenně:

suda := (NOT a) XOR b XOR c XOR d;

 V případech „obtížně minimalizovatelných funkcí“ lze použít intuitivní postup využívající vizuální posouzení podobnosti obrazců pokrytí s obrazci známých funkcí – na způsob úvahy typu „toto je skoro šachovnice, až na výjimky“. Na obr. 22 je ilustrativní příklad takového postupu pro fiktivní funkci. Její obrazec pokrytí (obr. 22a) je možné vytvořit jako sjednocení dvou obrazců jednoduchých funkcí (obr. 22b, obr. 22c). Podobně lze obrazec funkce na obr. 23a vytvořit jako průnik obrazců dvou jednoduchých množin (obr. 23b, obr. 23c).

 Úloha 7

Vytvořte výraz pro funkci z obr. 22obr. 23 minimalizovaný tradičním postupem a pak s využitím operátoru XOR.

 Úloha 8

Vytvořte výraz pro funkci z obr. 11, obr. 12obr. 13 minimalizovaný tradičním postupem a pak s využitím operátoru XOR.

 Ve starších učebnicích logiky se kladl důraz na důslednou minimalizaci logických funkcí. Kromě popsaných metod zde byly popisovány poměrně složité metody minimalizace, např. metoda Quin-McCluskey. Její použití bylo poměrně pracné, zdlouhavé a málo přehledné. Mezi vývojáři byla málo používána i v době, kdy byly kladeny velké požadavky na minimální objem elektroniky logických systémů logiky (v 60. až 80. letech 20. století) – v éře integrovaných obvodů malé a střední hustoty integrace (SSI a MSI). V současnosti ji lze považovat za překonanou – snad s výjimkou případů, kdy je její algoritmus implementován programem jako součást vývojového systému.

V současné době není minimalizace logických funkcí tak důležitá jako v minulosti. Tehdy složitost logických výrazů rozhodovala o objemu elektroniky realizující logické funkce, a tudíž mnohdy i o realizovatelnosti a komerčním úspěchu výrobku. Současné technologie mikroelektroniky dovolují realizovat i rozsáhlé logické systémy v malém prostoru. Délka programu také není kritickým problémem. Současné programovatelné systémy disponují dostatečným výpočetním výkonem a paměťovou kapacitou. Programem lze řešit i velmi složité úlohy při zajištění dostatečně krátké doby odezvy.

Požadavek na minimalizaci sice není striktní, ale přesto je účelné minimalizaci řešit – alespoň částečně a příležitostně. Optimalizované logické výrazy jsou totiž kratší a přehlednější, názorněji lze interpretovat jejich funkci. To přispívá k pochopení řešené funkce a k minimalizaci chyb. Důsledkem je zkrácení doby vývoje a doby uvádění zařízení do chodu, jednodušší je i servis. S tím souvisí i přehlednost a názorná dokumentovatelnost, která dovoluje, aby se v řešení mohl orientovat nejenom sám autor (i ten po čase zapomíná detaily svého řešení), ale především jeho spolupracovníci a pokračovatelé při dodatečných úpravách, řešení nových požadavků a inovacích. Důležité je i řešení diagnostiky – nejenom samotného logického systému, ale především řízeného objektu. Vše lze finančně vyčíslit.

 Prahové funkce

Prahové funkce jsou charakterizovány hodnotou prahu – což je celé kladné číslo nejvýše rovné počtu operátorů. Výsledek je jedničkový, jestliže je počet jedničkových operandů větší nebo roven hodnotě prahu. Budeme je zapisovat jako Pnk a číst „alespoň k z n“, kde k je hodnota prahu a n je počet operandů funkce. Tomuto požadavku vyhovují i mnohé funkce, které zde byly popsány dříve. Například logický součet OR je pravdivý, je-li pravdivý alespoň jeden z operandů – je tedy prahovou funkcí typu P21, P31, P41, obecně Pn1. Majoritní (většinové, hlasovací) funkce jsou definovány pro lichý počet operandů a jsou pravdivé, jestliže je pravdivá většina operandů. Majorita M3 je prahovou funkcí P32. Další majoritní funkcí je tedy M5 = P53. Logický součin AND je jedničkový, jsou-li všechny jeho operandy jedničkové – lze jej tedy zapsat jako P22, P33, P44, obecně Pnn. Jedničkovou funkci (konstantu 1) je možné definovat jako Pn0, nulovou funkci (konstantu 0) jako Pn(n+1). Mapy některých prahových funkcí byly uvedeny již dříve, na obr. 24 jsou souhrnně uvedeny všechny prahové funkce pro čtyři proměnné. Prahové funkce lze popsat optimalizovaným logickým výrazem, který obsahuje součinové členy v délce rovné prahu funkce, v nichž jsou zastoupeny všechny kombinace operandů v přímém (nikoliv negovaném) tvaru. Pro prahové funkce platí obdoba De Morganových pravidel. Například pro M3 platí:

 NOT M3(a, b, c) = M3(NOT a, NOT b, NOT c)

 Úloha 9

Dokažte tuto rovnost algebraickými úpravami logických výrazů podle pravidel Booleovy algebry a potom z K-mapy.

Z uvedených K-map lze snadno zjistit, že

NOT P41(a, b, c, d) = P44(NOT a, NOT b, NOT c, NOT d),

NOT P42(a, b, c, d) = P43(NOT a, NOT b, NOT c, NOT d).

Obecně platí

NOT Pn1(a, b, c…) = Pnn(NOT a, NOT b, NOT c…),

NOT Pn2(a, b, c…) = Pnn–1(NOT a, NOT b, NOT c…),

NOT Pn3(a, b, c…) = Pnn–2(NOT a, NOT b, NOT c…) atd.

 Prahové funkce jsou pro svou názornost nejen užitečným předmětem zadání cvičných příkladů v učebnicích logiky, ale uplatňují se i v praxi – zejména při řešení bezpečných řídicích systémů s redundancí (zálohováním), ale i při vyhodnocování souboru redundantních senzorů. Je možné se s nimi setkat v budovách při vyhodnocení signálu snímačů pohybu (PIR), požárních hlásičů, snímačů zaplavení a dalších snímačů zabezpečovací techniky. Jejich redundancí lze zvýšit spolehlivost (např. při výpadku některého ze senzorů) nebo zabránit falešným poplachům.

Dosud byly uvažovány prahové funkce, jejichž všechny vstupy byly rovnocenné (měly stejnou váhu). Někdy je ale účelné zvětšit význam některého vstupu oproti ostatním – přiřadit mu větší váhu. V tom případě lze použít zobecněnou prahovou funkci podle obr. 25. Na obr. 25a je zobrazena schematická značka. Každému ze vstupů lze přiřadit váhový koeficient w1, w2, w3wn (obvykle je to celé kladné číslo, ale může být i necelé), kterými se aritmeticky vynásobí pravdivostní hodnoty vstupů. Jednotlivé součiny se potom aritmeticky sečtou a porovnají s hodnotou prahu. Je-li součet větší nebo roven hodnotě prahu, bude výstup jedničkový, jinak bude nulový. Rovnocenně lze operaci porovnání s prahem řešit tak, že hodnotu prahu od součtu odečteme – přičteme se záporným znaménkem. Potom rozhodujeme, zda je součet větší nebo roven nule, nebo nikoliv. Řešení je možné upravit tak, že práh budeme považovat za další vstup připojený ke konstantní hodnotě –1 a násobený váhovým koeficientem w0. Na obr. 25 b je funkce rozdělena na sčítací a rozhodovací blok. Zde (jak je obvyklé) je rozhodovací funkce nespojitá ve tvaru reléové charakteristiky. Můžeme se ale „dopustit zobecnění“, kdy rozhodovací funkce bude spojitá – ve tvaru lomené křivky, složené z přímkových úseků (obr. 25c), nebo hladké křivky, např. sigmoidy na obr. 25d. Výstupem nyní bude spojitá proměnná s hodnotou v uzavřeném intervalu od nuly do jedné – odpovídá fuzzy logice. Vytvořili jsme tak zjednodušený model nervové buňky – neuronu. Takové nebo různě modifikované umělé neurony se v praxi propojují v různých topologických strukturách a vytvářejí se tak umělé neuronové sítě (ANN, Artificial Neuronal Net). Jsou jednou z úspěšných cest k umělé inteligenci (AI, Artificial Inteligence). To už je ale zase „jiná pohádka“.

 Symetrické funkce

Je zřejmé, že pravdivost prahových funkcí nezáleží na pořadí jejich operandů. Výstup se nezmění, jestliže je na vstupu libovolně prohodíme – označují se proto jako symetrické. Třída symetrických funkcí je ale širší. Obecně jsou symetrické funkce charakterizovány množinou čísel – celých nezáporných. Symetrická funkce je pravdivá, jestliže je počet jedničkových operandů roven některému číslu z definiční množiny. Například funkci majority M3 odpovídá množina {2, 3} a její negaci (minoritě ze tří) doplňková množina {0, 1}. Pro čtyři proměnné odpovídá logickému součtu OR = P41 množina {1, 2, 3, 4} a jeho negaci NOR {0} logickému součinu AND = P44 množina {4} a jeho negaci NAND {0, 1, 2, 3}, prahové funkci P42 {2, 3, 4}, P43 {3, 4}, jedničkové funkci {0, 1, 2, 3, 4}, výlučnému součtu {1}, ekvivalenci EQ {0, 4}, liché paritě PO {1, 3} a sudé PE {0, 2, 4}. Je patrné, že negaci symetrické funkce odpovídá doplňková množina. Takto lze snadno ověřit platnost pravidel Booleovy algebry, např. De Morganových.

Významné jsou elementární symetrické funkce. Jejich definiční množina obsahuje jen jediné číslo, např. funkci právě jedna ze čtyř (výlučný součet) odpovídá množina {1}. Budeme ji zapisovat jako S41, resp. obecně Snk, kde k je stupeň symetrické funkce a n je počet jejích operandů. Podobně lze definovat a označovat další elementární symetrické funkce, např. logický součin AND = S44 je definován množinou {4}. S použitím elementárních symetrických funkcí lze vytvářet další symetrické funkce, které jsou jejich logickým součtem OR. Například pro logický součet čtyř proměnných platí OR = S41 OR S42 OR S43 OR S44, pro funkci sudé parity PE = S42 OR S44 apod. Na obr. 26 jsou uvedeny K-mapy všech elementárních symetrických funkcí pro čtyři proměnné.

K řešení symetrických funkcí lze použít netradiční, ale výhodný postup. Spočívá v počítání operandů s jedničkovou hodnotou. Výsledkem součtu je celé kladné číslo, které je vhodné uložit v některém z formátů celých čísel. Hodnota prahové funkce je pak výsledkem porovnání tohoto součtu s hodnotou prahu: je-li součet větší nebo roven prahu, je hodnota jedničková (a opačně negace funkce má hodnotu jedna, je-li součet menší než práh). Pro řešení elementárních symetrických funkcí je použita podmínka rovnosti součtu a prahu. Pro řešení obecných symetrických funkcí je pak postupně porovnávána shoda součtu s hodnotami čísel z definiční množiny a výsledky dílčích porovnání jsou logicky sečteny (OR). Pro speciální případy lze testovat jednotlivé bity celočíselného vyjádření součtu. Například nejnižší bit čísla (bit 0) je shodný s funkcí liché parity (PO), jeho negace je funkcí sudé parity PE. Jednička bitu na sousední pozici (bit 1) znamená, že součet je větší nebo roven 2. Pro tři operandy je tedy shodný s funkcí majority M3. Obdobně lze postupovat při řešení dalších speciálních funkcí. Postup je výhodný pro řešení většiny „netriviálních“ logických funkcí. Je ale zřejmé, že pro funkce AND, OR by tento postup byl obdobou „střílení kanonem na vrabce“.

Podobným postupem lze řešit i zobecněné prahové funkce tak, že se sčítají pravdivostní hodnoty operandů násobené odpovídajícím váhovým koeficientem.

 Úloha 10

Vytvořte program, který sečte pravdivostní hodnoty pěti operandů a popsaným postupem řeší funkci majority z pěti M5 = P53, popř. další prahové a symetrické funkce. Stejné funkce řešte tradičním postupem s logickými výrazy. Porovnejte složitost a názornost řešení.

 Úloha 11

Postup z předchozí úlohy zobecněte pro zvolený počet operandů (např. pět nebo pro počet volitelný jako vstupní parametr), navrhněte a vytvořte univerzální uživatelský funkční blok, který spočte pravdivostní hodnoty operandů a předá hodnotu součtu jako celé číslo. 

Ing. Ladislav Šmejkal, CSc., Teco a. s. a externí redaktor časopisu Automa

Obr. 17. Sousednost políček na protilehlých okrajích K-mapy

Obr. 18. Zviditelnění sousednosti políček čtveřicí shodných K-map

Obr. 19. V K-mapě pro čtyři proměnné není sousednost políček vždy „přímo viditelná“

 Obr. 20. Neúplně zadaná logická funkce (a; vlevo nahoře) s možnostmi jejího řešení: důsledným doplněním neurčitých funkčních hodnot nulami (b; vpravo nahoře), jedničkami (c; vlevo dole) a s ohledem na získání minimálního výrazu (d; vpravo dole)

Obr. 21. K-mapa funkce liché parity pro šest proměnných

Obr. 22. Příklad řešení formou sjednocení dvou dílčích obrazců pokrytí

Obr. 23. Příklad řešení formou průniku dvou dílčích obrazců pokrytí

Obr. 24. K-mapy všech prahových funkcí pro čtyři proměnné

Obr. 25. Znázornění zobecněného prahového obvodu: (a) schematická značka, (b) oddělený součtový blok a rozhodovací blok, (c), (d) rozhodovací funkce pro neostré (fuzzy) rozlišení

Obr. 26. K-mapy elementárních symetrických funkcí čtyř proměnných


Rekordní „integráč“

V minulém pokračování bylo konstatováno, že obor mikroelektroniky se stále rozvíjí, což se projevuje neustále narůstající hustotou integrace, která dovoluje na vymezeném prostoru realizovat stále více logických členů. Dokazuje to aktuální informace, zveřejněná nedávno (v listopadu 2018) na webu (Seznam). Společnost AMD ukázala nový čip z edice Epyc (obr. 27), který obsahuje 64 procesorových jader, což je nejvýkonnější procesor na světě. Dosud nejlepší procesory pro stolní počítače se zpravidla chlubí 16 až 24 jádry. Rekordních 64 jader se podařilo do jednoho čipu vtěsnat především díky novému, 7 nm výrobnímu procesu. Jeden procesor se tedy skládá z osmi čipů, z nichž každý má osm nativních jader a šestnáct vláken.