Přednášející : Ing. Petr Haberzettl • • •
Zápočet : práce na doma – hlavně umět vysvětlit Ze 120 lidí udělá maximálně 25 :D Literatura : Frištacký - Logické systémy
Číselné soustavy: Nevyužíváme 10
Druhy soustav: • • • •
Binární (2) Oktanová (8) Desítková (10) Hexadecimální (16)
Máme stejný počet čar – v každé soustavě vyjádříme jinak 16(10) -> 20(8) -> 100(4) Boolova algebra – řídí počítání ve dvojkové soustavě, sestavil George Bool 19. st, zakladatel logiky.
Počítání ve dvojkové soustavě: a) sčítání 1011010 101111 10001001
b) odčítání 10110 1011 1011
0-0=0 1-0=1 1-1=0 0-1=1 (1)
1+1=10 1+0=1 0+1=1 0+0=0
c) násobení při násobení se postupuje tak, že 1. činitel vynásobím 2. činitelem zprava doleva a výsledky pak sečtu s fázovým posunem. 101101 •
101 101101 0 101101 11100001
Převody z jedné číselné soustavy do soustavy jiné Převod z a do desítkové soustavy (váhové kódy) 5492 = 5×103 + 4×102 + 9×101 + 2×100
Převod z dvojkové do desítkové soustavy 1×26 + 0×25 + 1×24 + 1×23 + 0×22 + 0×21 + 1×20 = 89
Provádíme jednotlivé součty součinů a výsledkem je číslo v desítkové soustavě.
Převod z dvojkové do osmičkové soustavy 8 = 23 ...
odzadu rozdělíme na trojice, pokud je třeba, dopíšeme na začátek nuly
0 0 1‘ 2
0 1 1‘
001
2
,0 0 1‘
2
2
100
0×2 + 0×21 + 1×20
0×2 + 1×21 + 1×20
0×2 + 0×21 + 1×20
0×2 + 0×21 + 1×20
1×22 + 0×21 + 0×20
1
3
1
1
4
(1011001)2 = (131)8
Převod z dvojkové do šestnáctkové soustavy 16 = 24 ...
0 1 0 1‘ 3
0×2 + 1×22 + 0×21 + 1×21
odzadu rozdělíme na čtveřice, pokud je třeba, dopíšeme na začátek nuly
1001 3
1×2 + 0×22 + 0×21 + 1×21
,0 0 0 0‘
1110
3
1×23 + 1×22 + 1×21 + 0×21
0×2 + 0×22 + 0×21 + 0×21
5
9
0
E
(1011001)2 = (59)16
Převod z desítkové do osmičkové soustavy 130 : 8 = 2
16 : 8 = 0
2:8= 2
0
Směr čtení je opět pozpátku, začíná se tedy nulou, která stojí na pravé straně rovnice (ta se však podle úmluv na začátek čísla nepíše) a pak se pokračuje s připisováním zbytků po dělení zprava doleva, z čehož plyne: (130)10 = (202)8
Převod z osmičkové do desítkové soustavy (202)8 = 2×80 + 0×81 + 2×82 = (130)10
Převod na římská čísla a naopak I když se s Římskými číslicemi v počítači setkáváme minimálně, je dobré se seznámit i s jejich převodem do desítkové soustavy (s převodem na Arabská čísla) a naopak. To ukazuje následující tabulka. desítkové
římské I V X L C D M
1 5 10 50 100 500 1 000
Znaky se skládají psaním od nejvyšší hodnoty k nejnižší. Menší hodnota před větší znamená odečet (Př. IV = 4). Takto se odečítá jen jediná číslice. (1975)10 = MCMLXXV
Převod z desítkové do dvojkové soustavy (postupné dělení) 130 : 2 = 0
65 : 2 = 1
32 : 2 = 0
16 : 2 = 0
8:2= 0
4:2= 0
2:2= 0
1:2= 1
Směr čtení je pozpátku, začíná se nulou, která stojí na pravé straně rovnice (ta se však podle úmluv na začátek čísla nepíše) a pak se pokračuje s připisováním zbytků po dělení zprava doleva, z čehož plyne: (130)10 = (1000010)2
0
Převádět lze též i desetinná čísla. Pro tento převod se používá metoda postupného násobení. Ta spočívá v tom, že číslo násobíme dvěmi tak dlouho, dokud není výsledek větší než jedna. Poté jedničku odřízneme a počítáme s číslem opět menším než jedna podle předchozího postupu. To opakujeme do té doby, než se nám začnou násobená čísla opakovat nebo již dále nemáme po odříznutí jedničky co s čím násobit. 0,3 × 2 = 0
0,6 × 2 = 1
1,2 0,2 × 2 = 0
(0,3)10 = (0,01001)2 ...
0,4 × 2 = 0
0,8 × 2 = 1
1,6 0,6 × 2 = 1
1,2
číslo 1001 je periodické
Převod ze šestnáctkové do desítkové soustavy (D7)16 = 13×161 + 7×160 = 208 + 7 = (215)10
Následující tabulka může sloužit jako jednoduchá pomůcka pro převod z desítkové do šestnáctkové soustavy (i naopak). Např. desítkově číslo 215 je v šestnáctkové soustavě vyjádřeno jako D7 (tam, kde se protnou řádky a sloupce je výsledek).
0_ 1_ 2_ 3_ 4_ 5_ 6_ 7_ 8_ 9_ A_ B_ C_ D_ E_ F_
0
1
2
3
4
5
6
7
8
9
0 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240
1 17 33 49 65 81 97 113 129 145 161 177 193 209 225 241
2 18 34 50 66 82 98 114 130 146 162 178 194 210 226 242
3 19 35 51 67 83 99 115 131 147 163 179 195 211 227 243
4 20 36 52 68 84 100 116 132 148 164 180 196 212 228 244
5 21 37 53 69 85 101 117 133 149 165 181 197 213 229 245
6 22 38 54 70 86 102 118 134 150 166 182 198 214 230 246
7 23 39 55 71 87 103 119 135 151 167 183 199 215 231 247
8 24 40 56 72 88 104 120 136 152 168 184 200 216 232 248
9 25 41 57 73 89 105 121 137 153 169 185 201 217 233 249
A 10 26 42 58 74 90 106 122 138 154 170 186 202 218 234 250
d) celá záporná čísla Celé kladné číslo je uloženo v RAM jako 16 bitů. Zobrazení záporných čísel: přímé a nepřímé. Přímé Když je 15 bit 0 jde o číslo kladné, když je 1 je záporné.
B 11 27 43 59 75 91 107 123 139 155 171 187 203 219 235 251
C 12 28 44 60 76 92 108 124 140 156 172 188 204 220 236 252
D 13 29 45 61 77 93 109 125 141 157 173 189 205 221 237 253
E 14 30 46 62 78 94 110 126 142 158 174 190 206 222 238 254
F 15 31 47 63 79 95 111 127 143 159 175 191 207 223 239 255
Nepřímé Nepřímé lze provádět pomocí dvou variant: Inverzní kód – nevýhodou je, že 0 může mít hodnotu +0 nebo –0, tuto eventualitu řeší kódování za pomoci doplňkového kódu. 0000000001111011 1111111110000100 Doplňkový kód Ke kódu inverznímu přičteme jedničku. 1111111110000100 1 101
HČ
BČ 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0 1 2 3 4 5 6 7 8 9 A B C D E F
bez znaménka 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Necelá čísla Lze použít dvě metody:
Uložení s pevnou řádovou čárkou Číslo se vždy převede na tvar 0,…….. 15 bit značí znaménko. 14 bit 2-1 = 0,5 13 bit 2-2 = 0,25 12 bit 2-3 = 0,125 ……. ……. …….
přímé
inverzní
doplňkový kód
0 1 2 3 4 5 6 7 -0 -1 -2 -3 -4 -5 -6 -7
0 1 2 3 4 5 6 7 -7 -6 -5 -4 -3 -2 -1 -0
0 1 2 3 4 5 6 7 -8 -7 -6 -5 -4 -3 -2 -1
Uložení s pohyblivou řadovou čárkou e
Jde o častější způsob vyjádření, kde jakékoliv číslo lze ve tvaru x=m*z . m – mantisa, z – základ soustavy, e – exponent. 2 123 = 0,23*10 3 0,123*10 U dvojkové soustavy je z = 2. Mantisa se bere ve tvaru menší než je, ale větší než 0,1. Tím se nemusí zobrazovat desetinná čárka, ta se zobrazí automaticky před největším řádem mantisy. Obsazení jednotlivých bitů 31 znaménko exponentu 30-24 exponent 23 znaménko mantisy 22 – 0 mantisa Příklad 45,750 101101,11 36,625 100100,101 82,375 1010010,011 0,750
0,625
-1
2 = 0,5 -2 2 = 0,25 -1
2 = 0,5 -3 2 = 0,125
Kombinační obvody Z matematiky znáte logické funkce - negaci, logický součet, logický součin, implikaci a ekvivalenci. Zde je jejich přehled s pravdivostními tabulkami.
Negace NOT Negace výroku A je výrok, který je pravdivý právě tehdy, když je výrok A nepravdivý (a opačně). A 0 1
NOT A 1 0
Logický součet OR (+, ∨) Výrok A AND B je pravdivý právě tehdy, když je alespoň jeden z výroků A, B pravdivý. A 0 0 1 1
B 0 1 0 1
A OR B (A + B) 0 1 1 1
Logický součin AND (. , ∧) Výrok A OR B je pravdivý právě tehdy, když jsou oba výroky A, B pravdivé. A 0 0 1 1
B 0 1 0 1
A OR B 0 0 0 1
Implikace => Výrok A=>B je NEPRAVDIVÝ právě tehdy, když A je nepravdivý a B je pravdivý. V ostatních případech je výrok A=>B pravdivý. A 0 0 1 1
B 0 1 0 1
A => B 1 1 0 1
Ekvivalence <=> Výrok A<=>B je pravdivý právě tehdy, když jsou oba výroky A, B pravdivé nebo oba nepravdivé. A 0 0 1 1
B 0 1 0 1
A <=> B 1 0 0 1
Prakticky se používají i další logické funkce: NOR, NAND a EXCLUSIVE-OR.
NOR Výrok A NOR B je pravdivý právě tehdy když je výrok A OR B nepravdivý („NOR je negace logického součtu OR“). A 0 0 1 1
B 0 1 0 1
A NOR B 1 0 0 0
NAND Výrok A NAND B je pravdivý právě tehdy když je výrok A AND B nepravdivý („NAND je negace logického součinu AND“). A 0 0 1 1
B 0 1 0 1
A NOR B 1 1 1 0
EXCLUSIVE-OR (neekvivalence) Výrok A EXCLUSIVE-OR B je pravdivý právě tehdy když je právě jeden z výroků A, B pravdivý („EXCLUSIVE-OR je negace ekvivalence“). A 0 0 1 1
B 0 1 0 1
A NOR B 0 1 1 0
Libovolnou logickou funkci je možné vyjádřit pomocí operace negace a kombinací logického součtu nebo logického součinu. Vyjádření implikace: výrok A=>B je totéž jako výrok (NOT A) OR B. Vyjádření ekvivalence: výrok A<=>B je totéž jako {(NOT A) AND (NOT B)} OR {A AND B} Vyjádření NOR: výrok A NOR B je totéž jako NOT(A OR B) Vyjádření NAND: výrok A NAND B je totéž jako NOT(A AND B) Vyjádření neekvivalence: výrok A EXCLUSIVE-OR B je totéž jako {(NOT A) AND B} OR {A AND (NOT B)} Chceme-li tedy sestrojit obvod, který by modeloval nějakou zadanou logickou funkci, musíme mít k dispozici obvody, které generují tyto základní logické funkce (NOT, AND, OR).
Elektronické obvody pro generaci uvedených funkcí nazýváme po řadě: invertor, hradlo “AND” a hradlo “OR”. Vezměme nejjednodušší možnou realizaci uvedených obvodů tzv. diodovou logiku. Používá se „pozitivní logika“ i „negativní logika“. Přiřazení logických stavů “0” a “1” napěťovým úrovním je totiž zcela libovolné a záleží na tom kterém přístroji, jakého přiřazení používá. Pakliže stav logické “0” odpovídá nižšímu napětí na výstupu logického členu nežli stav logické “1”, hovoříme o tzv. pozitivní logice. Je-li tomu naopak, tj. logické “0” odpovídá vyšší napětí nežli logické “1”, pak se jedná o negativní logiku. Přitom je třeba zdůraznit, že nezáleží na velikosti napětí, obě mohou být kladná nebo obě záporná nebo jedno kladné a druhé záporné; pakliže logická “1” odpovídá kladnějšímu napětí, jedná se o pozitivní logiku, jinak je to logika negativní. Stejným způsobem se označuje logika tzv. dynamická (na rozdíl od právě popsané statické, neboli úrovňové logiky), kdy ovšem příslušné úrovně jsou na vstupech logických členů pouze po velmi krátkou dobu, tedy ve formě napěťových impulsů. Vzhledem k tomu, že parametry reálného logického členu se různí kus od kusu (užívají se odpory s určitou tolerancí, tranzistory a diody, které mohou mít různé parametry), není možné stanovit přesnou hodnotu napětí odpovídající logické “0” resp. “1” v té které logické síti. Místo toho se logické členy konstruují tak, aby nebyly citlivé na změnu napětí vstupních parametrů pokud tyto leží v určitém intervalu napětí. Viz obr.1.
obr. 1 Například pro hradla TTL (transistor-transistor-logic) jsou příslušné intervaly následující: Uvst(0) = max. 0,8 V Uvst(1) = min. 2 V neboli pro logickou “0” je povolený interval vstupních napětí 0 - 0.8V pro logickou “1” 2 5 V. Hradlo samo má zaručovaná výstupní napětí:
Uvýst(1) = min. 2,4 V Uvýst(0) = max. 0,4 V tj. hluboce v povolené toleranci napětí vstupních. Napájecí napětí je (5± 0,25) V. Uvedené hodnoty jsou typické pro tzv. tranzistorovou logiku a byly implementovány u celé řady výrobců logických obvodů. Zdaleka to však nejsou jediné napěťové úrovně u logických obvodů používané. Hradla s tranzistory řízenými elektrickým polem mají logické úrovně okolo 0 V a 9 V a existuje i tzv. logika s vysokou šumovou imunitou HLL (high-level-logic), kde napěťová úroveň logické “1” je řádu 10 - 50 V. S takovými napěťovými logickými úrovněmi pracují řídicí systémy v provozech, kde je zvýšená úroveň elektromagnetického rušení. Na druhé straně pro speciální přístroje s nízkým napájecím napětím (náramkové hodinky) byly vyvinuty obvody, kde jsou logické úrovně mezi 0 V a 3 V i níže. Nadále se budeme zabývat pouze pozitivní logikou.
Logická hradla Hradlo OR Hradlo tohoto typu je vybaveno (na jeho výstupu je úroveň logické 1), je-li alespoň jeden z jeho vstupů vybaven. X 0 0 1 1
Y 0 1 0 1
X+Y 0 1 1 1
obr. 2 Jestliže předpokládáme ideální diody (tj. nekonečný odpor v závěrném směru a nulový v propustném směru), je funkce obvodu následující: Pro vstupní napětí Ux > u nebo Uy > u je odpovídající dioda otevřena a výstupní napětí kombinace je rovno Ux nebo Uy (předpokládáme-li, že zdroje napětí Ux a Uy i zdroj napětí u mají vnitřní odpor nulový). Je-li
např. napětí Ux na vstupu X , pak dioda Dy je uzavřená, pokud napětí na vstupu Uy není větší než Ux. Pak se naopak zavře dioda Dx, vede Dy a výstup kopíruje napětí na vstupu Y. Pokud používáme reálné diody a reálné zdroje napětí logických úrovní X a Y, musíme počítat s jejich vnitřním odporem ri, odporem diod v propustném směru a se zbytkovým napětím na diodách UD (u germaniových diod ∼ 0,2V, u křemíkových ∼ 0,7V). Zbytkové napětí na diodách má tu výhodu, že není třeba používat zdroj napětí, který nám předtím vytvářel oblast napětí pro úroveň logické 0 (logická 0 byla od 0V do u V), neboť diody se neotevřou, pokud vstupní napětí nepřekročí UD. Zahrneme-li odpor diod v propustném směru do vnitřních odporů zdrojů logických úrovní, bude při aplikaci napětí Ux = Uv napětí na výstupu rovno
Jsou-li oba vstupy na úrovni E , bude výstupní napětí
Zkuste si tyto vztahy odvodit.
Hradlo AND Hradlo tohoto typu je vybaveno (na jeho výstupu je úroveň logické 1), jsou-li všechny jeho vstupy vybaveny. X 0 0 1 1
obr. 3
Y 0 1 0 1
XY 0 0 0 1
Hradlo NOT (invertor)
obr. 4 Je ho možno vytvořit transistorovým zesilovačem, pracujícím ovšem ne v lineárním, ale ve spínacím režimu. Je zřejmé, že zapojíme-li tranzistor do obvodu podle obr. 4 a budeme-li zvětšovat proud do jeho báze, bude napětí mezi kolektorem a emitorem klesat. Od určitého proudu báze však zjistíme, že napětí UKE se prakticky nesnižuje - transistor je ve stavu nasycení. Je to stav, kdy jak emitorový přechod, tak kolektorový jsou pólovány v propustném směru, a napětí mezi kolektorem s emitorem je v podstatě dáno rozdílem napětí na přechodu báze-emitor a na přechodu báze - kolektor. Prakticky u křemíkového tranzistoru je toto tzv. saturační napětí Usat asi 0,2 V a u germaniového tranzistoru asi 0,1 V. Báze je při tom nasycena minoritními nosiči náboje a veškerý přírůstek proudu báze jde na úkor přírůstku proudu emitoru. Přestaneme-li dodávat proud do báze tranzistoru, uzavřou se obě diody (BE, BK) a přebytek minoritních nosičů v bázi je opět odsáván el. polem v oblasti kolektorového přechodu. Je zřejmé, že čím více minoritních nosičů bylo v bázi před vypnutím, tím déle bude trvat, než kolektor odsaje všechny minoritní nosiče v bázi a kolektorový proud klesne na nulu. Proto je vhodné zabezpečit, aby tranzistor v sepnutém stavu pracoval na okraji oblasti nasycení: toho lze dosáhnout např. použitím tzv. desaturačních diod , zapojených mezi bázi a kolektor. Kondenzátor CB napomáhá urychlení přechodového procesu odstranění minoritních nosičů z báze, když měníme napětí vstupu z 1 na 0. Funkce obvodu na obr. 4 je tedy následující: při aplikaci napětí o logické úrovni 1 na vstup X invertoru zvětšíme proud báze natolik, že tranzistor uvedeme do saturace. Na výstupu NOT X je tedy napětí U, které je obvykle ¼ až 1/3 povoleného rozsahu napětí pro logickou 0. Přivedeme-li na vstup zařízení napětí o logické úrovni 0, je tranzistor vypnut a na jeho
kolektoru (tedy na výstupu invertoru) je plné napájecí napětí volené tak, aby odpovídalo úrovni logické 1. Obvod tedy plní logickou funkci negace.
De Morganovy zákony: de Morganovy zákony určují vztah mezi sjednocením, průnikem a doplňkem množiny. Mějme množiny A,B a nechť označuje doplněk dané množiny.
Potom platí vztahy
De Morganovy zákony se uplatňují především v Booleově algebře.
Karnaughova mapa umožňuje: • • • •
zápis disjunkční funkce nebo pravdivostní tabulky. její minimalizaci nebo jiné logické úpravy, příkladem možných úprav je rozvoj funkce až do úrovně UDNT. inverzi funkce. určení duální funkce, vzhledem k zápisu zpravidla v konjunkčním tvaru.
Vidíme, že díky mapě můžeme realizovat prakticky všechny operace, jimiž jsme se doposud zabývali na základě Booleovy algebry. Z toho vyplývá, že mezi algebraickým vyjádřením funkce, pravdivostní tabulkou a Karnaughovou mapou musí existovat systém vzájemného přiřazení jednotlivých proměnných a logických operátorů. Je zajištěn na úrovni elementárních konjunkcí UDNT, které jsou v mapě topologicky seřazeny v definovaném pořadí podle principu sousedních mintermu. Jednotlivá políčka mapy, se ve všech směrech (nahoru, dolů, doleva a doprava) mohou a musí odlišovat od druhého pouze inverzí jedné jediné proměnné. Tím je zcela zaručen definovaný souřadnicový systém mapy. Aby byla zajištěna vzájemná kompatibilita, orientace ve všech mapách různého původu a nakonec také přehlednost vlastní práce, dodržuje se zásada umisťování mintermu se všemi proměnnými v inverzním tvary /A /B /C /D do levého horního rohu mapy. Tím je definována jednotná struktura mapy pro libovolný počet proměnných.
Pro názornost je v každém políčku vyznačeny tvary (přímý i inverzní) všech proměnných příslušného mintermu. Pro mapu o dvou proměnných platí pouze proměnné A, B. Pro mapu o třech proměnných zase proměnné A, B, C. Ve skutečnosti prostor uvnitř každého políčka slouží k vepsání logické hodnoty jeho mintermu, adresa je určena souřadnicovým systémem proměnných, vyznačených na okraji mapy. Přitom se zapisují jen proměnné v přímém tvaru, za jejich inverze se považují všechna zbylá, neoznačená políčka na stejné vnější straně mapy. Následující obrázky ukazují Karnaughovy mapy pro 2, 3 a 4 proměnné. Mapa dvou proměnných, odpovídá dvourozměrnému plošnému znázornění.
Mapa tří proměnných, odpovídá třírozměrnému (kubickému) znázornění.
Mapa čtyř proměnných, odpovídá čtyřrozměrnému prostoru.
Pokud jde o způsob hodnotového vyjádření políčka, je zvykem, že se zapisuje pouze 1. Nevyplněný minterm se považuje za 0. Minterm neúplně definované tabulky se většinou označuje jako velké písmeno X. Cílem souřadnosti mintermu pochopitelně není zavést souřadný systém mapy. Ten je nutnou podmínkou k tomu, aby pomocí mapy bylo možno realizovat logické operace. • • •
U mapy dvou proměnných lze jednou souřadnou definovat všechny mintermy v příslušném sloupci nebo řádku, protože všechny obsahují tutéž proměnnou ve shodném (přímém) nebo inverzním tvaru. U mapy tří proměnných lze obdobným způsobem, jednu proměnnou, definovat všechny (podobné) mintermy jednoho řádku a dvou sloupců. U mapy čtyř proměnných stačí pro obdobný popis jedna proměnná jak pro dva řádky, tak pro dva sloupce.
Tato skutečnost umožňuje při minimalizaci funkce v určitých případech chápat a používat taková políčka mapy, která vytvářejí sdružené řetězce mintermu (souvislé plochy sudého
počtu mintermu se shodnýma hodnotami 1) jako vyjádření DNT jejich společné funkce. Přitom se podle rozsahu řetězce vylučuje jedna, dvě či tři proměnné a tedy i patřičným způsobem se zjednodušuje celý zápis funkce.
