Základy číslicové techniky 2+1 z, zk
Ing. Vít Fábera, K614 • e-mail:
[email protected] • K508, 5. patro, laboratoř, 2 2435 9555
Ing. Tomáš Musil, Ph.D., K620 • e-mail:
[email protected] • K508, 5. patro, laboratoř, 2 2435 9556 doc. Ing. Vlastimil Jáneš, CSc., K620 • e-mail:
[email protected] • K508, 5. patro, laboratoř, 2 2435 9555
Fábera, V. : Úvod do hardware počítačů, skriptum FD ČVUT, Vydavatelství ČVUT, Praha 2005 Douša, J., Jáneš, V. : Logické systémy, skriptum FEL ČVUT, Vydavatelství ČVUT,Praha 1998 Pluháček, A. a kol.: Úvod do počítačových systémů, přednášky – slidy, katedra počítačů, FEL ČVUT, Praha 1995 - 2004 Janeček, J. : Projektování mikropočítačových systémů, skriptum FEL ČVUT, Vydavatelství ČVUT, Praha 1999
Informace a materiály ke stažení na WWW: http://www.fd.cvut.cz/personal/xfabera
Podmínky zápočtu • přiměřená docházka na cvičení povolena 1 absence
• absolvování laboratorních cvičení • odevzdání semestrální práce návrh kombinačního obvodu z 1. laboratorního cvičení
Zkouška • písemný test návrh kombinačního obvodu návrh sekvenčního obvodu otázky, příklady (převody, …) doba vypracování cca 90 min.
Počítač • počítač je matematický stroj, který zpracovává programy a data • pracuje na určitém fyzikálním principu – mechanické počítače – Vinci, Pascal – elektronické počítače – období 2. světové války
• zpracovává : programy - systémové a aplikační data – původně jen numerická data • matematické úlohy – numerické řešení diferenciálních rovnic – výpočet dráhy střely pro vojenské účely apod.
– texty, obrázky, zvuk, multimediální aplikace, …
Počítač • zpracování dat, tj. – transformuje vstupní data na výstupní
vstupní data
výstupní data
Počítač
Počítač a zobrazení dat •
počítač reprezentuje data (zobrazuje) pomocí určitých fyzikálních veličin možnosti: dva základní principy zobrazení dat:
1. spojité zobrazení (analogové) – fyzikální veličina může nabývat libovolných hodnot, zpravidla z určitého intervalu
2. diskrétní zobrazení (číslicové) – fyzikální veličina může nabývat diskrétních (izolovaných, oddělených) hodnot, zpravidla z určitého rozsahu – mechanické: natočení kolečka – elektrické: napětí, proud
Příklady zobrazení dat Jaké je toto zobrazení?
Spojité neboli analogové
Příklady zobrazení dat A toto?
Diskrétní neboli číslicové
Příklady zobrazení dat • říkáme také, že u číslicového zobrazení je hodnota zobrazena určitým stavem; při změně hodnoty dochází ke skokové změně stavu – změna musí být „dostatečně rychlá“ – odolnost změnám parametrů systému Zajímavost: • elektromechanický číslicový počítač -programátor v automatické pračce - typový váleček se zářezy
• mechanický čísl. systém - hrací strojky, flašinet
Zobrazení dat v počítači • v číslicových počítačích se data zobrazují pomocí dvojkové soustavy, tj. čísel 0,1 – číslice 0,1 se také označují jako logické hodnoty (nepravda, pravda, no, yes, false, true), protože se jimi v matematické logice ohodnocuje pravdivost výroků
• matematický aparát pro práci s 0 a 1 existuje již od 19. století – 1848: anglický matematik George Bool: Booleova algebra
Zobrazení dat v počítači Proč dvojková soustava?
• mechanické systémy již v 19. stol. • první číslicový počítač byl reléový, které dokáže rozlišit 2 stavy (rozepnuto, sepnuto – 0,1) • informace o velikosti 0 nebo 1 se nazývá 1 bit –bit = binary digit (dvojková číslice) • ale 1 bit (1b) není jednotkou informace, je to shannon, který je pro dvoustavovou logiku totožný s bitem
Zobrazení dat v počítači - jednotky • 8 bitů = 1 Byte (bajt), 1B, správně česky slabika • 16 bitů = 1 Word (slovo) • 32 bitů = 1 DoubleWord (dvojslovo) Násobky slabiky: • 1 KB = 1 KiloByte - 1 KB = 1024 B • 1 MB = 1 MegaByte - 1 MB = 1024 KB Proč 1KB = 1024 B? 210 = 1024 (nejblíže hodnotě 1000)
Zobrazení dat v počítači - jednotky Poznámka: • v některé literatuře se rozumí: 1 kB (kiloByte)= 1000 B 1 KB (KiloByte) = 1024 B • nově podle IEC: 1KB = 1 KiB (KibiByte) = 1024 B Kibi = kilo binary • my budeme chápat vždy "kilo" = 1024 B
Číselné soustavy Používané v „běžném lidském životě“ • standardní polyadické soustavy – charakteristika: • základ soustavy • z cifer
– zápis čísla vyjadřuje hodnotu
Zajímavost – dělení číselných soustav • polyadické soustavy – hodnotu čísla lze vyjádřit polynomem – označují se jako poziční • hodnota číslice je dána pozicí v čísle
– standardní: • jeden celočíselný základ z
– nestandardní: • více číselných základů, např. soustava časová: 24h 60m 60s
Zajímavost – dělení číselných soustav • nepolyadické soustavy – označují se jako nepoziční • hodnota číslice není dána její pozicí v čísle, ale nějakým speciálním postupem
Příklad: • soustava římských číslic
x
VI
=1
IV
=-1
Standardní polyadické číselné soustavy • desítková soustava
• dvojková soustava
Standardní polyadické číselné soustavy • osmičková soustava
• šestnáctková soustava
Hornerovo schéma • slouží k vyhodnocení polynomu bez výpočtu mocnin
Převody mezi číselnými soustavami • převod do dvojkové soustavy – počítáme zbytky po dělení číslem 2 (%) a celočíselné podíly ( ) – převedeme 7510 do dvojkové soustavy
÷
Převody mezi číselnými soustavami • převod do dvojkové soustavy – jiná metoda: • číslo vyjádříme jakou součet mocnin dvou • ve dvojkové soustavě napíšeme jedničky do řádů, jejichž mocniny jsou v součtu zastoupeny
Převody mezi číselnými soustavami • převod do šestnáctkové soustavy – počítáme zbytky po dělení číslem 16 (%) a celočíselné podíly ( ) – převedeme 93610 do šestnáctkové soustavy
÷
Převody mezi příbuznými soustavami • dvě číselné soustavy o základech z1, z2 – z1< z2 • příbuzné soustavy: z2 = z1k • příbuzné soustavy jsou – dvojková a šestnáctková: 24 = 16 – dvojková a osmičková: 23 = 8 • převádíme přímo k-tice bitů
Převod mezi dvojkovou a šestnáctkovou soustavou 1. Doplň zleva dvojkové číslo nevýznamnými nulami tak, aby byl celkový počet cifer roven nějakému násobku čísla 4 2. Jednotlivé čtveřice dvojkových cifer přepiš na šestnáctkové cifry dle následující tabulky
Převod mezi dvojkovou a šestnáctkovou soustavou
Převod mezi dvojkovou a šestnáctkovou soustavou Převeďte číslo 11010112 z dvojkové soustavy do šestnáctkové 1. doplníme nevýznamnými nulami: 01101011 2. rozdělíme na čtveřice: 0110 1011 3. převedeme: 6 B 11010112 = 6B16
Převod mezi dvojkovou a osmičkovou soustavou 1. Doplň zleva dvojkové číslo nevýznamnými nulami tak, aby byl celkový počet cifer roven nějakému násobku čísla 3 2. Jednotlivé trojice dvojkových cifer přepiš na osmičkové cifry dle následující tabulky
Převod mezi dvojkovou a osmičkovou soustavou
Převod mezi dvojkovou a osmičkovou soustavou Převeďte číslo 11010112 z dvojkové soustavy do osmičkové 1. doplníme nevýznamnými nulami: 001101011 2. rozdělíme na trojice: 001 101 011 3. převedeme: 1 5 3 11010112 = 1538
LOGICKÉ OBVODY
Kombinační logické obvody
Logické obvody • digitální obvody – dvojková soustava – hodnoty 0,1 = logické hodnoty • log. 0, log. 1
• reprezentace pomocí napětí, např. • log. 0 - 0V - 0,4V, • log. 1 - 2,4V - 5V
– nebo • log. 0 - 0V - 0,99V, • log. 1 - 2,3V – 3,3V • 2,5V logika, 1,8V logika
Logické obvody • logické obvody – zpracovávají diskrétní log. hodnoty 0 a 1
• logické systémy – matematické modely a popisy těchto obvodů na úrovni logiky
Logické obvody Dělení logických obvodů podle • způsobu realizace – mechanické, elektrické, pneumatické,…
• použitých prvků (součástek) – reléové, elektronkové, obvody s tranzistory, integrovanými obvody
• technologie výroby – zejména u integrovaných obvodů – TTL (bipolární), CMOS, HCMOS, BiCMOS
Logické obvody Dělení logických obvodů podle chování • kombinační logické obvody – hodnoty výstupních proměnných závisejí pouze na aktuálních hodnotách vstupních proměnných
• sekvenční logické obvody – hodnoty výstupních proměnných závisejí na okamžitých hodnotách vstupních proměnných a také na historii jejich hodnot
Kombinační logické obvody
• vstupní vektor = vstupní písmeno • výstupní vektor = výstupní písmeno • matematický vztah mezi vstupem a výstupem – kombinační zobrazení
Booleova algebra Booleova algebra je asociativní, distributivní, komutativní a komplementární svaz s binárními operacemi logického součtu, logického součinu a unární operací negace, resp. inverze, s proměnnými a s konstantami 0, 1.
Booleova algebra
negace NOT
log. log. součin součet AND
OR
Booleova algebra - zákony 1. Komutativní zákon
a+b = b+a 2. Asociativní zákon
(a + b ) + c =
a + (b + c )
duální forma
a ⋅b = b⋅ a
(a ⋅ b ) ⋅ c =
a ⋅ (b ⋅ c )
3. Zákon idempotence
a+a = a 4. Zákon absorpce
a + (a ⋅ b ) = a
a⋅a = a a ⋅ (a + b ) = a
5. Zákon agresivnosti nuly a jedničky
a ⋅0 = 0
a +1 = 1
Booleova algebra - zákony 6. Zákon neutrálnosti nuly a jedničky
a+0= a
a ⋅1 = a
7. Distributivní zákon
a ⋅ (b + c ) = a ⋅ b + a ⋅ c
a + b ⋅ c = (a + b ) ⋅ (a + c )
8. Zákon sporu a vyloučeného třetího
a⋅a = 0
a + a =1
9. Zákon involuce neboli dvojí negace
a =a 10. Zákon absorpce negace
(
)
a ⋅ a + b = a ⋅b
a + a ⋅b = a + b
Booleova algebra - zákony 11. De Morganovy zákony
a + b + c +L+ z = a ⋅ b ⋅ c ⋅ L⋅ z
a ⋅ b ⋅ c ⋅K⋅ z = a + b + c + L+ z 12. Shannonův expanzní teorém - rozklad logické funkce a) verze součtová: F(x1, x2 , … , xn ) = x1 . F( 1, x2 , … , xn ) + x1 . F( 0 , x2 , … , xn ) b) verze součinová:
[
]
F(x1, x2 , … , xn ) = [x1 + F( 0 , x2 , … , xn )]⋅ x1 + F( 1, x2 , … , xn )
Každá logická funkce se dá realizovat v součtové nebo součinové formě.
Booleova algebra - zákony
DUALITA FUNKCÍ FD (x1 , x2, … , xn , 0 , 1 , + , .) = F(x1 , x2, … , xn , 1 , 0 , . , + )
Poznámka: • pořadí operací + a . je důležité: jde o záměnu, totéž platí pro logické konstanty 0 a 1
Booleovská funkce • booleovská funkce n proměnných
y = f (x1, x2,…,xn) f : {0,1} → {0,1} n
booleovských funkcí n proměnných je
2
2n
Boooleovské funkce • k odvození počtu booleovských funkcí
Booleovská funkce • pro n = 2 proměnné dostáváme:
2 = 2 = 16 22
4
funkcí – kompletní tabulka viz skripta a cvičení
Booleovské funkce • některé další důležité (booleovské) logické funkce – pravdivostní tabulka
1. Kombinační logické obvody – základní logické funkce Některé základní logické funkce (k tabulce): 1. Vylučovací nebo, XOR [eXclusive OR], součet modulo 2, nonekvivalence X⊕Y=X.Y+X.Y 2. Funkce ANI, NOR, Pierceova funkce, … X↓Y=X+Y 3. Funkce NAND, Shefferova funkce, … X ↑ Y= X.Y 4. Ekvivalence 5. Implikace
X ≈ Y = X . Y + X. Y X→Y=X+Y
1. Kombinační logické obvody – operace „nebo“ Funkce „nebo“ 1. Uveďme příklad výroku: bude-li číslo dělitelné 2 nebo 3 není to prvočíslo. Tedy : číslo X - je dělitelné 2 číslo Y - je dělitelné 3 .... pak X nebo Y = pravda , neboli 1 nebo 1 = 1 Hovoříme o tzv. „obyčejném nebo“ – zápis → X + Y 2. Uveďme jiný příklad: chlapec bude hodný nebo dostane pár facek Tedy : A - bude hodný B - dostane par facek A nebo B : 1 nebo 1 = 0 → jedná se o tzv.
„vylučovací nebo“ Zapisujeme jako : A ⊕ B - součet modulo 2
Závěr: nebo ≠ nebo
Zápis logických funkcí • • • • •
pravdivostní tabulka booleovský výraz seznam vstupních (stavových) indexů mapa jednotková krychle
Pravdivostní tabulka, log. výraz
f (c, b, a ) = ab + bc f (c, b, a ) = b(a + c)
Seznam vstupních indexů • seznam vstupních kombinací (chápané jako dvojkové číslo), kdy funkce nabývá hodnoty 1
f (c, b, a ) = ∑ (0,4,5) • seznam vstupních kombinací (chápané jako dvojkové číslo), kdy funkce nabývá hodnoty 0
f (c, b, a) = Π (1,2,3,6,7 )
Jednotková krychle sousední vstupní písmena (liší se v jediném bitu) – Hammingova vzdálenost = 1
nabývá log. 1 pro vstup 000
Jednotková krychle
Schématické značky hradel • hradlo (gate) – součástka realizující log. funkci
Výrazy • uvažujme n proměnných x1, x2, x3, …, xn • součinový term – výraz obsahující pouze operaci log. součinu n – termů je 3 -1
• minterm – součinový term obsahující všechny uvažované proměnné v přímé nebo negované formě – nabývá hodnoty log. 1 pouze pro právě jednu kombinaci vstupních písmen
Výrazy • součtový term – výraz obsahující pouze operaci log. součtu n – termů je 3 -1
• maxterm – součtový term obsahující všechny uvažované proměnné v přímé nebo negované formě – nabývá hodnoty log. 0 právě pro jednu kombinaci vstupních proměnných
Vyjádření booleovské funkce výrazem Podle tvaru výrazu • součtová forma (disjunktivní) – výraz je ve tvaru součtu součinových termů – úplná normální disjunktivní forma • výraz je ve tvaru součtu mintermů
• součinová forma (konjunktivní) – výraz je ve tvaru součinu součtových termů – úplná normální konjunktivní forma • výraz je ve tvaru součinu maxtermů
• smíšená forma
Příklad mintermy
maxtermy
c⋅b⋅ a c⋅b⋅ a c⋅b⋅ a c⋅b⋅ a c⋅b⋅ a c⋅b⋅ a c⋅b⋅ a c⋅b⋅ a
c +b+a c +b+a c +b+a c +b+a c +b+a c +b+a c +b+a c +b+a
c 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
a 0 1 0 1 0 1 0 1
f 1 0 0 0 1 1 0 0
Vytvoření úplné součtové formy • vybereme řádky, kde nabývá funkce hodnoty log. 1 a zapíšeme součet odpovídajících mintermů
f (c,b,a) = c⋅ b⋅ a +c⋅ b⋅ a +c⋅ b⋅ a
Vytvoření úplné součinové formy • vybereme řádky, kde nabývá funkce hodnoty log. 0 a zapíšeme součin odpovídajících maxtermů
f (c,b,a) = (c +b + a) ⋅ (c +b + a) ⋅ (c +b + a) ⋅ ⋅ (c +b + a) ⋅ (c +b + a)
Minimální forma • minimalizujeme úplné formy pomocí zákonů Booleovy algebry – nepohodlné
f = c⋅b⋅ a +c⋅b⋅ a +c⋅b⋅ a = c⋅b⋅ a +c⋅b⋅ a +c⋅b⋅ a +c⋅b⋅ a = zákon idempotence
( )
( )
1
1
= c +c ⋅b⋅ a +c⋅b⋅ a +a = b⋅ a +c⋅b
Minimalizace pomocí map • mapa – „grafická, resp. „tabulková“ forma – vychází z Vennových diagramů • rozdělíme určitou oblast na podoblasti a každé podoblasti přiřadíme určitý bod stavového prostoru
– Vennův diagram pro tři proměnné
Mapy • mapy pro 3 proměnné – 8 kombinací • mapa má 2 x4 políček
Mapy • mapy pro 4 proměnné – 16 kombinací • mapa má 2 x 8 políček nebo 4 x 4 políček
Grayův kód • kód, kde každá dvě po sobě jdoucí dvojková čísla jsou sousední, tj. liší se v jediném bitu • tvoříme jej „zrcadlovou metodou“ z kratšího kódu – n bitový Grayův kód vytvoříme z (n-1) bitového zrcadlením – jednobitový kód je posloupnost 0 , 1
Grayův kód
zrcadlení
jednobitový
přidám 0 a 1
dvoubitový
tříbitový
Mapy • Karnaughova mapa – vstupní proměnné jsou kódovány Grayovým kódem
• Svobodova mapa – vstupní proměnné jsou kódovány binárním kódem
Mapy Zobrazení logických funkcí do mapy :
Mapy Pravidla pro tvorbu smyček při hledání minimální součtové formy • hledáme co nejmenší počet co největších smyček obsahujících pouze 1 • každá 1 musí být v alespoň jedné smyčce, smyčky se mohou překrývat • smyčka musí obsahovat takový počet jedniček, který se rovná určité mocnině čísla 2, tj. musí obsahovat 1 nebo 2 nebo 4 nebo 8 atd. jedniček! • smyčka musí obepínat takovou množinu vstupních písmen (podoblast v mapě), která tvoří podkrychli ve stavovém prostoru vstupních písmen
Mapy Mapy pro 3 a 4 logické proměnné a sousední termy :
Mapy
Mapy
Mapy
Mapa vs. krychle • smyčka v mapě musí obepínat podkrychli v jednotkové krychli
Mapy II Karnaughova mapa pro 5 proměnných podle Grayova cykl. kódu
Kombinační logické obvody – úplné norm. formy a) Úplná normální disjunktní forma (úndf) - součtová V úplné normální formě je každá jedničková hodnota zadané logické funkce „pokrývána“ jedním termem resp. implikantem. Takový součinový term obsahuje všechny proměnné zadané logické funkce jako přímé nebo negované (minterm). Na příklad u majority ze tří (funkce je dána třemi proměnnými) jsou implikanty délky 3 – tj. xyz , x yz , x yz , x y z , atd. Prvotní popis majoritní funkce ze 3 je zapsán úplnou normální formou.
b) Úplná normální konjunktní forma (únkf) - součinová Konjunktní forma pokrývá nulové hodnoty zadané logické funkce svými součtovými termy – např. (maxtermy – obsahuje opět všechny proměnné ).
Kombinační logické obvody - mndf c) Minimální normální disjunktní forma (mndf) Minimální normální disjunktní forma (mndf) obsahuje nejmenší možný počet nejkratších implikantů(součinových termů), tj. přímých implikantů. Kriteria minimality tedy jsou: 1) má minimální délku formy (tj. počet přímých implikantů) 2) má minimální délku implikantů(tj. s min.počtem prom.) 3) eventuelně obsahuje minimální počet negací
Minializace pomocí mapy: Pokrýváním jedničkových stavů zadané logické funkce vytvoříme nejmenší počet co největších smyček! Řešení nemusí být jediné. Ukázka viz Karnaughova resp. Svobodova mapa pro 4 proměnné – řešení jsou dvě 1. F1(a,b,c,d) = 2. F2(a.b.c.d) =
ac + abc + bcd + abd
Kombinační logické obvody Příklad na tabulku pokrytí Je daná následující logická funkce 4 proměnných
Kombinační logické obvody – pokrytí • musím vybrat zelenou a tmavě-modrou smyčku: (nesporné implikanty) • pak si mohu vybrat mezi: •
růžovou a oranžovou smyčkou
•
šedou a světle modrou smyčkou
rozhoduji se podle počtu proměnných v termu a počtu negací Existují dvě nejvýhodnější řešení: F1(a, b, c, d) = a.d + a . d + c . d + a . b .c F2 (a, b, c, d) = a.d + a . d + c . d + b .c.d Obě funkce jsou pro realizaci rovnocenné – mají stejný počet termů (implikantů), termy jsou stejně dlouhé a je potřeba všechny proměnné negovat.
1. Kombinační logické obvody - realizace Ekvivalence logických členů NAND → AND - NOT
1. Kombinační obvody – realizace s členy NAND
1. Kombinační obvody – návrh KO s členy NAND Výchozí podmínky: - minimální forma logické funkce - jsou dané typy logických členů, resp. se volí pro danou technologii - je daná rychlost logického obvodu --------------------------------------------------------------------------------------------- požaduje se snadná diagnostika a oživování - bere se ohled na konstrukční řešení a další I. OBECNÁ a KLASICKÁ STRUKTURA AND – OR Uvažujme realizaci dané logické v minimálním tvaru:
F3 (a, b, c, d) = a . b + a . d + a . b . d + a . c . d + a . b . c Tuto minimální součtové funkci (mndf) můžeme zakreslit ve struktuře AND - OR
Kombinační obvody – realizace AND - OR
Kombinační obvody – realizace se členy NAND Úprava minimální logické funkce pro realizaci s členy NAND Použijeme zákona dvojí negace (involuce) a De Morganových pravidel
Z této úpravy lze již snadno nakreslit schéma se členy NAND neboť každé závorce odpovídá logický člen NAND a negace celého výrazu odpovídá pětivstupovému NAND výstupnímu
Kombinační obvody – realizace NAND
Kombinační obvody – výsledné schéma Výsledné schéma se členy NAND max. třívstupovými - bylo třeba nahradit výstupní log. člen pětivstupový
Kombinační obvody • náhrada pětivstupového hradla:
(
)( )
a ⋅ b ⋅ c ⋅ d ⋅ e = (a ⋅ b ⋅ c ) ⋅ (e ⋅ f ) = a ⋅ b ⋅ c ⋅ e ⋅ f
