INFORMATIKA I. (struktura počítačů) pro obor Aplikovaná fyzika

INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ Moderní technologie ve studiu aplikované fyziky CZ.1.07/2.2.00/07.0018

INFORMATIKA I. (struktura počítačů) pro obor Aplikovaná fyzika

Luděk Bartoněk 2011

1 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


OBSAH Úvod ........................................................................................................................................... 5 1. TEORETICKÉ PROSTŘEDKY ........................................................................................ 5 1.1. Množiny ....................................................................................................................... 6

2.

1.2.

Výroky, pravdivostní hodnoty, logické funkce ........................................................... 8

1.3.

Úplný soubor logických funkcí ................................................................................. 11

1.4.

Logické algebry ......................................................................................................... 12

1.5.

Boolova algebra ......................................................................................................... 12

1.6.

Modely logických funkcí ........................................................................................... 14

1.7.

Mapa logické funkce ................................................................................................. 15

1.8.

Normální formy Boolovy algebry ............................................................................. 15

1.9.

Využití map pro minimalizaci normální formy Boolovy algebry ............................. 16

LOGICKÉ ČLENY A OBVODY .................................................................................... 18 2.1. Dvouhodnotový signál ............................................................................................... 18 2.2.

Třídění logických obvodů .......................................................................................... 21

2.3.

Kombinační logické obvody...................................................................................... 21

2.3.1.

Součtový logický člen ........................................................................................ 23

2.3.2.

Součinový logický člen ...................................................................................... 23

2.3.3.

Invertor ............................................................................................................... 23

2.3.4.

Univerzální logické členy................................................................................... 24

2.3.5.

Fyzikální realizace logických členů ................................................................... 26

2.3.6.

Diodově-tranzistorové obvody ........................................................................... 26

2.3.7

Obvody TTL se Schottkyho diodou ................................................................... 31

2.3.8

Emitorově vázané obvody .................................................................................. 32

2.3.9

Injekční integrované logické obvody ................................................................. 33

2.3.10 Logické členy s tranzistory MOS ....................................................................... 35 2.3.11 Prahové logické členy ........................................................................................ 36 2.4

Typické kombinační obvody sčítačky ....................................................................... 37

2.4.1

Sčítačka modulo 2 .............................................................................................. 37

2.4.2

Koincidenční obvod ........................................................................................... 38

2.4.3

Dekodér .............................................................................................................. 40

2.5

Sekvenční obvody...................................................................................................... 41 2

Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


3.

2.5.1

Jednostupňový KO ............................................................................................. 41

2.5.2

Dvoufázový režim činnosti obvodu řízeného hodinovými impulzy .................. 42

PAMĚŤOVÉ OBVODY .................................................................................................. 43 3.1 Typy polovodičových pamětí .................................................................................... 43 3.2

4.

5.

3.2.1

Paměti EPROM .................................................................................................. 45

3.2.2

Paměti EEPROM................................................................................................ 46

3.2.3

Paměti SRAM .................................................................................................... 47

3.2.4

Paměti DRAM .................................................................................................... 48

3.3

Vytváření paměťových sestav ................................................................................... 49

3.4

Aplikace paměťových obvodů v hardwarových automatech .................................... 51

3.5

Kontrola a oprava chyb obsahu paměti ..................................................................... 53

PROGRAMOVATELNÝ AUTOMAT ........................................................................... 55 4.1 Činnost automatu ....................................................................................................... 56 4.2

Programové řízení automatu ...................................................................................... 59

4.3

Přerušení .................................................................................................................... 61

ZOBRAZENÍ INFORMACE V PAMĚTI POČÍTAČE .................................................. 61 5.1 Aktivní a pasivní informace ...................................................................................... 61 5.2

6.

Stručný přehled základních unipolárních technologií ............................................... 44

Zobrazení numerické informace v paměti ................................................................. 62

5.2.1

Číselné soustavy, vzájemné převody čísel mezi číselnými soustavami ............. 63

5.2.2

Zobrazení dvojkového čísla v počítači, rozsah čísel, přesnost zobrazení .......... 66

5.2.3

Přímý kód (Signed magnitude) .......................................................................... 66

5.2.4

Inverzní kód (One’s complement)...................................................................... 67

5.2.5

Doplňkový kód (Two’s complement) ................................................................ 67

5.2.6

m1 Kód transformované nuly (Excess 2 code) ...................................................... 68

5.3

Zobrazení znakové informace, kódy ASCII a EBCDIC ........................................... 69

5.4

Zobrazení instrukcí v paměti ..................................................................................... 72

5.4.1

Kód instrukce ..................................................................................................... 73

5.4.2

Adresy instrukce ................................................................................................. 73

5.4.3

Typy a struktura adresy ...................................................................................... 73

ARITMETIKA VE DVOJKOVÝCH KÓDECH ............................................................. 75 6.1 Zobrazení v pevné řádové čárce, typ integer ............................................................. 77 6.2

Zobrazení v pohyblivé řádové čárce, typ real............................................................ 79 3



6.3 7.

Zobrazeni logických hodnot, typ Boolean ................................................................. 80

ZÁKLADNÍ ARITMETICKÉ OPERACE ...................................................................... 81 7.1 Sčítání v polyadických soustavách ............................................................................ 81 7.2

Odčítání v polyadických soustavách ......................................................................... 82

7.3

Násobení v polyadických soustavách ........................................................................ 83

7.3.1 7.4

Desítkové násobení ............................................................................................ 83

Dělení v polyadických soustavách ............................................................................ 85

LITERATURA ......................................................................................................................... 86



Úvod Studium na vysoké škole se neobejde bez využívání výpočetní techniky. Soudobá výpočetní technika z pohledu běžného uživatele jsou dnes především 32-bitové (64-bit) osobní mikropočítače, kompatibilní nebo blízké standardu PC. Tato skupina je v našich podmínkách většinou zaměřena výlučně uživatelsky. Díky téměř nepřebernému množství dostupných programových „balíků" mohou být tyto mikropočítače efektivně využívány při nejrůznějších pracích, především kancelářského, konstrukčního, technického i výpočetního charakteru. Jakmile je jednou určitý program zvládnut, může být pro jeho využívání vyškolena většinou i osoba jinak věci neznalá, která pak může podávat i profesionální výkony. Existuje také oblast aplikací obdobné techniky v laboratořích a v průmyslu, kterou představují různé varianty mikropočítačů, především pro jejich příznivější ekonomické ukazatele a také zlepšující se dostupnost. Zde lze uvažovat zejména jednočipové mikropočítače, paměti CMOS s většími kapacitami, programová logická pole atd. Každý, kdo se seznamuje s číslicovou a mikroprocesorovou technikou soustavně, si musí uvědomit, že je to dlouhodobá, trvalá záležitost. Musí si vytvořit svůj vlastní styl práce, číst a shánět informace, třídit je a získávat přehled o reálné situaci. K základům také patří alespoň orientační zvládnutí některého vyššího programovacího jazyka (např. Basic, Pascal, C), které tvoří dobrý základ pro práci se strojově orientovanými jazyky. Úvod do celé problematiky byl volen za předpokladu minimální předběžné přípravy. Byla zde snaha vytvořit pokud možno systematický pohled na kombinační a sekvenční logiku, který je nezbytný pro vysvětlení uvedené problematiky. Následuje stručný přehled číslicových a paměťových obvodů a základy hardwarových a programovatelných automatů, čímž se vytváří předpoklad pro výklad principů, techniky a programování mikroprocesorových systémů a mikropočítačů ve vyšších ročnících aplikované fyziky. Na předložený studijní materiál se navazuje ve vyšších ročnících studia aplikované fyziky výkladem konkrétních aplikací počítačů a programování mikroprocesorů (řízení experimentu v reálném čase atd.) z pohledu dosažené přesnosti měření při znalosti definičního rozsahu hodnot zobrazených v paměti počítače. Materiál není konstrukčního typu, ale měl by přispět k fyzikálnímu pochopení počítačového systému pro jeho optimální implementaci do případných počítačových aplikací.

1. TEORETICKÉ PROSTŘEDKY Tato kapitola svým obsahem částečně překrývá s náplní skript1 [Mašláň]. Proto je zde uveden pouze výklad částí, které jsou nezbytné k ucelenému výkladu uvedené látky. Equation Section (Next)

1

Mašláň, Žák: Logické obvody, UP Olomouc 1994



1.1.

Množiny

Všechny množinové operace můžeme znázornit graficky v rovině v tzv. Vennových diagramech, někdy též nazývaných Eulerovy kruhy (obr. 1.1, 1.2). Základní čtverec, obdélník či ovál obsahuje všechny podmnožiny, s nimiž se pracuje a budeme ho označovat množinou I. Podmnožiny musí vesměs splňovat podmínku částečného překrytí. Při úpravách výrazů s množinami se využívá následující množina základních pravidel a zákonů (pro používání závorek platí běžná konvence): a) Pravidla pro částečné uspořádání: Zákon reflexivní (zvratu) Zákon symetrie (souměrnosti) je-li

X  Y pro všechna X X  Y , Y  X , pak X  Y X  Y , Y  Z , pak X  Z

Zákon transitivní (přechodný) je-li b) Pravidla pro operaci sjednocení a průnik:

(1.1) (1.2) (1.3)

Zákon idempotentní (opakování)

XX X

X X X

(1.4)

Zákon komutativní (zaměňování)

X Y  Y  X

X Y  Y  X

(1.5)

a) b)

pro jednu podmnožinu množiny I

c) e) pro dvě podmnožiny množiny I

f) g)

Obr. 1.1. Vennovy diagramy

a) E  F

c) J  K

b) G  H

d) J  I  J

Obr. 1.2. Příklady znázornění množinových operací a) sjednocení množin, b) průnik množin, c) rozdíl množin, d) doplněk, výsledná podmnožina je vybarvena Zákon asociativní (sdružování)

X  Y  Z    X  Y   Z

(1.6)

X  Y  Z    X  Y   Z 6 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


X  Y  Z    X  Y    X  Z 

Zákon distributivní (rozdělování)

(1.7)

c) Pravidlo ekvivalence (totožnosti); pro X  Y platí

X Y  Y

X Y  X

d) Pravidla pro množiny I a 0 pro X  I , Y  I , Z  I ,

(1.8)

, 0  I platí 0  X  I pro všechna X

(1.9)

Zákon o agresivnosti 0 a I Zákon o neutrálnosti 0 a I

IX I

0 X  0

(1.10)

0 X  X

I X 0

(1.11)

XX I

X X 0

(1.12)

e) Pravidla pro doplněk Zákony doplňku (o vyloučeném třetím)

Zákony De Morganovy (duality)

 X Y   X Y

 X Y   X Y

(1.13)

X   X

(1.14)

Zákon involuce (zanikání, dvojí negace)

Z uvedených pravidel vyplývají další pravidla, která používáme při úpravách výrazů s množinovými operacemi: f) Zobecněný distributivní zákon

 X1  X 2   X n   Y1  Y2   Ym     X 1  Y1    X 1  Y2     X 1  Ym    X 2  Y1  

  X n  YmS 

(1.15)

g) Sjednocení a průnik vyhovují zákonům absorpce (pohlcení)

XX X X   X Y   X

X X X

X  X Y   X

(1.16) (1.17)

h) Platí zákony absorpce negace 7 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


X   X Y   X Y

X   X Y   X Y

(1.18)

X   X Y   X Y

X   X Y   X Y (1.19)

i) Zobecněný zákon De Morganův (Shannonův teorém)

 X  Y    Z W    X  Y    Z W  1.2.

(1.20)

Výroky, pravdivostní hodnoty, logické funkce

Představme si, že daná množina N má n prvků. Pak se z n prvků dá vytvořit celkem

k  2n

(1.21) různých podmnožin (včetně podmnožiny 0 a podmnožiny obsahující všechny prvky n  N ). Uvědomíme-li si, že každý prvek n  N má tu vlastnost, že je v podmnožinách buď přítomen, nebo nepřítomen, pak se pro práci s výše uvedenými podmnožinami množiny N dají využít vlastnosti výrokové nebo jiné dvouhodnotové logické algebry. Logická algebra je algebra vhodná k popisu vztahů mezi logickými proměnnými. Výrok je tvrzeni x, o němž můžeme jednoznačně prohlásit, zda je pravdivé nebo nepravdivé. Říkáme také, že ke každému výroku x je přiřazena pravdivostní hodnota. Pravdivost značíme zpravidla l a nepravdivost 0. Ve dvouhodnotových logických algebrách odpovídá prvek množiny výroku nebo vstupní logické proměnné a počet podmnožin, které lze z n prvků vytvořit je počet všech možných kombinací hodnot těchto prvků. Celkový počet různých složených dvouhodnotových logických funkcí pro uvedenou k kombinaci vstupních logických proměnných je (1.22) L  2k  22 Výroky (logické proměnné) označíme písmeny. Z jednoduchých výroků pomocí logických spojek můžeme tvořit složené výroky. Pravdivostní hodnota složeného výroku je dána pravdivostními hodnotami jednoduchých výroků, s nichž se tento složený výraz skládá a pravidly – logickým operacemi, které jsou přiřazeny každé spojce. Logická operace je operace, v níž operandy i výsledek jsou logické proměnné nebo jejich množiny. Operace je vytvoření údaje (tzv. výsledku) z jednoho nebo více údajů (operandů) na základě pravidel, která určují výsledek pro libovolnou přípustnou kombinaci operandů. Operátor je symbol, označující operaci, umístěný mezi symboly, před symboly, za symboly nebo nad symboly operandů. Jednočlenná operace je operace s jedním operandem, dvojčlenná operace je operace se dvěma operandy. Výrazy takto sestavené ze symbolů proměnných, operátorů a závorek, nazýváme obvykle výrokové formule. Když dosadíme za každou proměnnou do výrokové formule výrok z množiny výroků, jejichž pravdivostní hodnoty jsou dány, dospějeme k výroku, jehož pravdivostní hodnotu umíme určit. Přitom pravdivostní hodnota tohoto výroku závisí zřejmě při dané výrokové formuli pouze na pravdivostních hodnotách dosazených výroků a nikoliv na jejich n



konkrétní podobě. S výhodou se tato úloha řeší v tabulkách (viz tab. 1.1), kde v záhlaví jsou předepsány výrokové formule jednoduchých i složených výroků, s nichž je cílový výrok sestaven a v tabulce jsou uvedeny všechny možné kombinace pravdivostních hodnot těchto výroků tak, že pravdivost výroku je zaznamenaná symbolem l a nepravdivost symbolem 0. Řešme uvedenou metodou výrokovou formuli (1.23).

 x  y  x  y

(1.23)

x

y

x y

x y

 x  y  x  y

0 0 l l

0 1 0 1

0 l l l

0 0 0 1

1 0 0 1

Tab. 1.1. Tabulka pro ověření vztahu (1.23) Obdobně můžeme řešit otázku shodnosti výrokových formulí. Máme například zjistit, zda výrokové formule uvedené ve vztahu (1.24) popisují tutéž skutečnost: x y  x  y

(1.24)

x

y

x y

x y

x

y

xy

xyxy

0 0 l

0 1 0

0 l l

1 0 0

1 l 0

1 0 1

1 0 0

l l l

l

1

l

0

0

0

0

l

Tab. 1.2. Pravdivostní tabulka vztahu (1.24) Vidíme, že pro uvedené výrokové formule jsme dospěli k cílové výrokové formuli, kterou nazýváme tautologicky pravdivou čili tautologií, tedy výchozí výrokové formule popisují tutéž skutečnost. Kdybychom nedospěli k tautologii, může pak v místě nepravdivosti dodefinovat potřebný výrok, a tedy můžeme tímto způsobem vyřešit úlohu "jak zajistíme, aby jistá výroková formule po případné úpravě modelovala předepsanou skutečnost". Lze si ověřit, že tytéž úlohy lze úspěšně řešit i Vennovým diagramem nebo úpravami výrazů podle základních pravidel pro úpravy množinových výrazů. Pro potřeby analýzy a syntézy logických sítí je výhodnější pracovat s pojmy logická proměnná a logická funkce než s pojmy výrok a výroková 9 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


formule. V této oblasti aplikací mají zvláštní a základní význam logické funkce jedné a dvou proměnných. Logická funkce jedné proměnné je přehledně uvedena v tab. 1.3. Při prostudování tabulek zjistíme plnou platnost výrazů (1.21) a (1.22). Nulová funkce f0(x) a jednotková funkce f3(x) jsou konstanty, které jsou nezávislé na vstupní proměnné, vlastní funkce jedné proměnné jsou funkce opakování f1(x) a negace f2(x). proměnná

x

funkční formule

název funkce

0

x 0

f0(x) = 0

nulová

0 l l

l 0 l

f1(x) = x f2(x) = x f3(x) = l

opakovaní (aserce) negace jednotková

Tab. 1.3. Tabulka logických funkcí jedné proměnné Pro doplnění uveďme, že z hlediska logických sítí nás zajímají pouze extenzionální výrokotvorné funktory, které lze přiřadit k logickým funkcím. V logice se však používají i intenzionální výrokovorné funktory, u nichž hodnota složeného výroku závisí nejen na pravdivostních hodnotách výchozích výroků, ale i na jejich obsahu (např. „ x protože y―, „věřím, že x― apod.). Jejich praktické ekvivalenty i s doporučením operátorů jsou uvedeny v tab. 1.4.

Fn  x1, , xn   Y F1  x, y   x  y

funkce Fn , závorka, x1, xn , závorku uzavřít, rovná se výrazu Y x ani y x je inhibováno y ne x; x negace; x non

F3  x, y   x

F6  x, y   x  y  x y F7  x, y   x | y

F8  x, y   x  y  x. y  xy F9  x, y   x  y

x není ekvivalentní y; x modulo dvě y ne xy; x Shefferova funkce y xy; x i y; x krát y x je ekvivalentní y

F10  x, y   x  y

x (přímo) implikuje y

F11  x, y   x  y

x nebo y

Tab. 1.4. Tabulka operátorů a logických spojek 10 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


1.3.

Úplný soubor logických funkcí

Tak, jak byly vypsány všechny logické funkce jedné proměnné (tab. 1.3), můžeme vypsat funkce i více proměnných a stanovit pro ně operátory a názvy. Již při třech proměnných nám nastanou potíže, protože výraz (1.22) skutečně platí, a pro tři proměnné je 256 funkcí (tab. 1.5). Při více proměnných se dostáváme do prakticky neřešitelných potíží. Proto se hledaly cesty, jak tuto nepříjemnou skutečnost obejít. Řešení se našlo v tom, že existují jisté podmnožiny logických funkcí, jejichž vhodnými vazbami, tj. vytvořením výrokové formule s více než jedním operátorem se podařilo realizovat všechny zbývající logické funkce. Tyto podmnožiny se nazývají úplné soubory logických funkcí. Počet proměnných Počet logických funkcí

0 2

l 4

2 16

3 256

4 65536

5 4 294 967 296

Tab. 1.5. Počet logických funkcí více proměnných Je zřejmé, že nás zajímají především ty úplné soubory logických funkcí, jež neobsahují funkce, které lze zbývajícími funkcemi opsat. Budeme je nazývat minimální úplné soubory logických funkcí. Z minimálního úplného souboru logických funkcí nelze již žádnou logickou funkci vypustit, můžeme však libovolnou logickou funkci do něho přidat a dostaneme tak jiné úplné soubory logických funkcí, které ovšem již nejsou minimální. Nejčastěji se úplné soubory logických funkcí vybírají z logických funkcí jedné proměnné a dvou proměnných a zobecňují se pro více proměnných. V tomto případě jsou pouze dvě funkce, z nichž každá sama tvoří úplný soubor logických funkcí. Je to negace logického součtu, kterou pro potřeby úplných souboru budeme nazývat Peirceovou funkcí a negace logického součinu, kterou budeme ze stejných důvodů nazývat Shefferovou funkcí. Z ostatních logických funkcí jedné a dvou proměnných získáme další minimální úplné soubory logických funkcí tak, že vybereme vhodné dvojice logických funkcí. Lze odvodit [1], že všechny možné dvojice, jenž tvoří úplný soubor, jsou tyto: implikace – negace; implikace - nulová funkce; implikace – inhibice; implikace - nonekvivalence; inhibice – ekvivalence; inhibice – negace; inhibice – jednotková; logický součin – negace; logický součet – negace. Kromě uvedených minimálních úplných souborů logických funkcí lze z logických funkcí jedné a dvou proměnných vytvořit minimální úplné soubory logických funkcí, které obsahují tři funkce: logický součin - ekvivalence - nulová funkce; logický součin - nonekvivalence - jednotková funkce; logický součin - ekvivalence – nonekvivalence; logický součet - ekvivalence - nulová funkce; logický součet - nonekvivalence - jednotková funkce; logický součet - ekvivalence – nonekvivalence. Úplný soubor logických funkcí lze sestavit i z funkcí více proměnných a popřípadě i logických funkcí typu prahová logická funkce. Prahová logická funkce je definována pro více vstupních proměnných, kdy vstupní proměnné jsou váhově ohodnoceny a logická funkce nabývá hodnotu l, až aritmetický součet vah vstupů je roven nebo větší než stanovený práh. Váha je činitel, jímž se násobí číslice na daném řádovém místě, aby se získala její hodnota v čísle. Práh je pevná, stanovená fyzikální hodnota, nutné k tomu, aby závisle proměnná nabyla určité logické hodnoty. 11 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


1.4.

Logické algebry

Jakýkoli, úplný soubor logických funkcí je základem, na němž lze deduktivně (axiomaticky) zavést jistou logickou algebru. Každá z těchto algeber se zavádí jako množina A konstant, proměnných a logických funkcí, v níž jsou axiomaticky dány některé vlastnosti určitých operací s prvky množiny A, a to těch operací, které vytvářejí funkce příslušného úplného souboru logických funkcí. Ze souboru axiomů, jímž je zavedena určitá logická algebra, lze ryze formálně odvodit všechny vlastnosti této algebry [1]. Soubor axiomů musí být: bezesporný (konsistentní), tj. nelze z něho správnými postupy odvodit dvě vlastnosti vzájemně si odporující (jistý výrok a jeho negaci), úplný v tom smyslu, že přidáním jakéhokoli dalšího výroku (který nevyplývá z daného souboru axiomů) nebo jeho negace by se porušila bezespornost. Kromě uvedených podmínek je žádoucí, aby soubor axiomů obsahoval pouze a) jednoduchá tvrzení, která se již nedají rozložit na několik tvrzení jednodušších b) tvrzení vzájemně nezávislá, tj. taková, z nichž žádné nelze formálně odvodit z ostatních. Při formálním vymezení axiomů není vymezen význam prvků množiny, která tvoří příslušnou logickou algebru. Z axiomů vyplývají pouze formální vztahy mezi těmito prvky, zprostředkované zavedenými operacemi. Vyskytují-li se konkrétní prvky, pro něž platí (po zavedení vhodného kódu) daný soubor axiomů, říkáme, že jde o konkrétní interpretaci (model) daného souboru axiomů. Kód je dohodnutý systém pravidel pro jednoznačné přiřazení významu ke znakům nebo signálům. Tentýž soubor axiomů může mít mnoho konkrétních interpretací v různých oborech lidské činnosti. Vlastnosti, které byly odvozeny z formálně pojímaných axiomů, platí i v těchto jednotlivých interpretacích. V tom spočívá hlavní metodologický význam formálního pojetí axiomů. K prvkům a vztahům mezi těmito prvky u jisté formálně zavedené logické algebry lze tedy nalézt různé interpretace. Jsou to například výroková algebra nebo algebra množin (byla uvedena v kap. 1.1 pod názvem "Množiny"). Vzájemně různých formálních logických algeber může být tolik, kolik se dá sestavit úplných souborů logických funkcí. Víme však, že těchto souborů je neomezený počet, neboť ke každému souboru lze přidávat libovolný počet dalších logických funkcí, čímž dostáváme stále nové úplné soubory logických funkcí. Zatím je vybudováno jen několik logických algeber. Jsou to většinou logické algebry, které se opírají o logické funkce dvou proměnných a zobecnění jejich axiomů pro více proměnných.

1.5.

Boolova algebra

Nejvýznačnější algebrou pro teorii logických sítí i pro mnohé jiné obory je Boolova algebra (zkráceně B-algebra). Boolova algebra2 je dvouhodnotová logická algebra, která užívá logického součtu, součinu a negace jako základních operací. Boolovská proměnná je logická proměnná nabývající dvou hodnot. Boolovská funkce je logická funkce boolovské proměnné. 2

V tomto a dalších názvech se v češtině připouští termín "boolovský i Boolův". V předloženém textu budeme termín "boolovský" chápat jako obecnější, širší než "Boolův".



Boolovská operace je dvouhodnotová logická operace. Boolovský operátor (boolovská spojka) je operátor boolovské operace. Tabulka boolovských operací je tabulka udávající závislost výsledku booloveké operace na jejích operandech. Boolovu algebrou budeme nazývat každou množinu B, která obsahuje jednak dva navzájem různé význačné prvky 0 a l, jednak další prvky x, y, z a v níž jsou definovány operace součtu, součinu a negace tak, že platí tento soubor axiomů; 1. Jestliže prvky x  B a y  B , pak také  x  y   B a xy  B (vnitřní zákony komposice). 2. V množině B je význačný prvek 0  B takový, že x  0  x je splněno pro libovolný prvek x  B ; podobně je význačný prvek 1 B , u něhož je x.1  x (zákony absorbce). 3. Pro prvky x  B, y  B, je vždy splněno x  y  y  x a současně xy  yx (zákony komutativní). 4. Pro prvky x  B, y  B, z  B je vždy splněno x   yz    x  y  x  z  a současně

x  y  z   xy  xz (zákony distributivní). 5. Ke každému prvku x  B se vyskytuje současně prvek x  B , pro který platí xx  0 a současně x  x  1 (zákony vyloučeného třetího). 6. Jsou alespoň dva takové prvky x  B a y  B , že x  y . Soubor axiomů, který byl uveden, zavedl již v roce 1904 americký matematik a logik E.V. Huntington. Je to pouze jeden z mnoha možných přístupů k axiomatickému vybudování Boolovy algebry, jejíž název byl zvolen na počest význačného irského matematika a logika Georga Boolea (1815-1864) a jejíž základy lze vysledovat u starořeckého filosofa a encyklopedického vědce, zakladatele logiky a řady speciálních věd Aristotela (384-322 před n.l.). Z uvedeného souboru axiomů lze odvozovat i další pravidla Boolovy algebry [1]. Za povšimnutí stojí, že uváděné základní rovnosti Boolovy algebry jsou většinou uspořádány po dvojicích, přičemž výrazy v rovnostech na pravé straně se získají z příslušných výrazů na levé straně a naopak pouze tím, že prvek 0 se nahradí prvkem l, prvek l prvkem 0, logický součin logickým součtem a logický součet logickým součinem. Jde tedy o dvojice duálních výrazů. Principu duality lze s výhodou využít při odvozování nových pravidel Boolovy algebry. Při odvození jakékoli rovnosti Boolovy algebry získáme totiž mimoděk i rovnost mezi odpovídajícími duálními výrazy. Když se nyní zamyslíme nad všemi logickými výrazy, které byly až dosud v textu uvedeny, zjistíme, že byly boolovské a že tedy modelovaly algebraicky boolovské funkce. Lišily se od sebe pouze v algebraickém vyjádření. Boolovské funkce mohou být tedy modelovány výrazy, v nichž se mohou vyskytovat jakékoli dílčí operace. Pokud ve výrazu použijeme pouze operace definované v Boolově algebře, budeme je nadále nazývat Boolovými výrazy a logické funkce takto algebraicky popsané Boolovými funkcemi. Při zkrácení je možno užívat zápis B-výraz a B-funkce. Boolovské funkce lze porovnávat nejen z hlediska jejich rovnosti, ale i z hlediska nerovností. 13 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Předpokládejme, že

0  1,

0  0,

1 1 .

(1.25)

Nerovnost dvou boolovských funkcí f  x1, x2 , , xn  a g  x1, x2 , , xn  můžeme pak zavést takto: Jestliže je f  g a jestliže fi   gi  , kde i prochází všechny možné kombinace proměnných podle vztahu (1.25) a kde fi  , popř. g  i  značí hodnoty logické funkce pro příslušnou kombinaci proměnných, říkáme, že funkce f je menší než funkce g a píšeme symbolicky f  g . Uveďme několik základních vztahů tykajících se nerovností mezi boolovskými mi3[1]. 1. Je-li f < g a g < h, potom je též f < h. 2. Je-li f < g, potom je též f  g , f  h  g  h, fh  gh . 3. Je-li f < h a současně g < h, potom je též f  g  h, fg  h . 4. Je-li f < g a současně f < h, potom je též f  g  h, f  gh .

1.6.

Modely logických funkcí

Doposud jsme se setkali s několika modely logických funkcí. Byly to algebraický výraz, tabulka a plošný útvar Vennova diagramu. Některé vztahy a přechody jsme definovali. Dále rozšíříme tuto oblast poznatků o další možnosti. Mějme logickou funkci tří proměnných, jejíž tabulkový model je tab. 1.6. Poslední sloupec obsahuje pravdivostní hodnoty logické funkce F  x, y, z  . Prostřední pole obsahuje kombinace vstupních logických proměnných, které jsou v záhlaví zapsány v pořadí, daném předpisem normální báze  x, y, z  . Jako pomůcka jsou uvedeny váhy, které jednotlivým proměnným přiřazujeme. Pracovní oblast prostředního pole obsahuje pravdivostní hodnoty logických proměnných. Jednomu řádku (kombinaci proměnných) říkáme vstupní stav. Každý vstupní stav jme schopni zakódovat vstupním stavovým indexem s. Pokud pravdivostní tabulka obsahuje vstupní stavy podle (1.21) a všem stavům je přiřazena pravdivostní hodnota logické funkce F  x, y, z  , pak se jedná o logickou funkci určenou. V případě alespoň jednoho neurčeného stavu mluvím o logické funkci neurčené. Pokud se neurčené stavy vyskytují, značíme je X.

3

Pro úplnost můžeme uvést další algebry např. Shefferova, Peirceova, Žegalkinova, Lindmanova algebra atd.



s

x

y

z

F  x, y, z 

0 1 2 3 4 5 6 7

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 1 0 1 1 0 1 0

Tab. 1.6. Pravdivostní tabulka

1.7.

Mapa logické funkce

Velmi častým grafickým útvarem pro zápis boolovské funkce je logická mapa.

Obr. 1.3. Trojrozměrná jednotková krychle logické funkce F  x, y, z  .

1.8.

Normální formy Boolovy algebry

Z mnoha možných způsobů zápisů uveďme několik výrazů logické funkce, jejíž model (mapa) je na obr. 1.4.

Obr. 1.4. Karnaughova, Svobodova funkce F(x,y,z) 15 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Několik možných zápisů funkce G(x,y,z) zadané Karnaughovou mapou.

G  x, y, z  = xyz  xyz  xyz  xyz  =  x  y  z  x  y  z  x  y  z  x  y  z   = yz  zy  xz  =  x  z  x  y  y  z   = yz  xz  =  x  z  y  z  

(1.26) (1.27) (1.28) (1.29) (1.30) (1.31)

= atd. kde jednotlivé zápisy B-výrazů lze pojmenovat: 1.26 - úplná normální disjunktní (součtová) forma – ÚNDF 1.27 - úplná normální konjunktní (součinová) forma – ÚNKF 1.28 - zkrácená normální disjunktní forma – ZNDF 1.29 - zkrácená normální konjunktní forma - ZNKF 1.30 - minimální normální disjunktní forma – MNDF 1.31 - minimální normální konjunktivní forma - MNKF

1.9.

Využití map pro minimalizaci normální formy Boolovy algebry

Úplně zadaná logická funkce F  x, y, z  . S 0

x 0

y 0

z 0

F 0 KF

1

0

0

1

1

2

0

1

0

1

3

0

1

1

0

4

1

0

0

0

5

1

0

1

1

6

1

1

0

1

7

1

1

1

1

 x  y  z DF  x  y  z  DF  x  y  z  KF  x  y  z  KF  x  y  z  DF  x  y  z  DF  x  y  z  DF  x  y  z 

Tab. 1.7. Označení ÚNDF a ÚNKF v úplně zadané logické funkci F  x, y, z  16 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Úplná normální disjunktní forma (UNDF) funkce F  x, y, z 

 x  y  z   x  y  z    x  y  z   x  y  z    x  y  z

(1.32)

Obr. 1.5. Po optimalizaci minimalizovaná disjunktní forma (MNDF)

F  x, y , z    x  y    y  z    y  z 

(1.33)

Úplná normální konjunktní forma (UNKF) funkce F  x, y, z 

 x  y  z   x  y  z    x  y  z ,

(1.34)

Obr. 1.6. Po optimalizaci minimalizovaná normální konjunktní forma (MNKF)

 x  y  z    y  z .

(1.35)

Příklad minimalizované disjunktní formy funkce F  x, y, z  a její realizace logickými obvody. MNDF F  x, y, z    x  y    y  z    y  z  = = x. y  y .z  y.z = x. y. y.z. y.z = = x. y. y.z  y.z = x. y. y.z  yz = = x. y. y .z  yz = x. y. y .z. y.z . 17 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Obr. 1.7. Realizace minimalizované disjunktní formy funkce F  x, z, y  logickými obvody

2. LOGICKÉ ČLENY A OBVODY Equation Section (Next)

Nejužívanější definice logického obvodu je následující: Logickým obvodem nazýváme takový fyzikální determinovaný systém, u něhož každá veličina na vstupu i výstupu může v ustáleném stavu nabývat s předepsanou přesností pouze jedné ze dvou možných logických hodnot a který obsahuje takové prvky, jejichž vstupní i výstupní veličiny mohou nabývat rovněž jen jedné ze dvou možných logických hodnot.4

2.1.

Dvouhodnotový signál

Pro vyjádření dvou stavů kteréhokoliv z vstupních nebo výstupních veličin jsou zavedeny symboly 0 a 1 a můžeme také říci, že tyto symboly jsou zobrazeny dvouhodnotovým signálem, někdy též zvaným elementárním signálem. Jinak řečeno, symbolům 0 a 1, které zobrazují stavy nějaké logické proměnné, přiřazujeme signální hodnoty nebo krátce signál (např. napětí U0 a U1 a naopak). Signálem v uvedené souvislosti může být jakákoliv fyzikální veličina, proto mohou být logické obvody realizovány na libovolném fyzikálním principu. V praxi však našly uplatnění jen některé principy, a to takové, které dávají předpoklady pro vysokou rychlost zpracování informace, malý prostorový objem a malou energetickou spotřebu. Proto se využívá zejména principů elektrických a magnetických. Na obr. 2.1 je uveden přehled nejčastěji užívaných signálů zobrazujících symboly 0 a 1 v logických obvodech. 4

Obecně jsou možné i logické obvody několikahodnotové. V dalších úvahách se však omezíme pouze na dvouhodnotové obvody, které jsou v praxi nejrozšířenější.



Obr. 2.1. Signály zobrazujících symboly 0 a 1 v logických obvodech. V obvodech počítačů se logické proměnné a jim odpovídající signály mění, a přijímají se většinou jen ve vymezených časových okamžicích t (obr. 2.2). Dobu t časového intervalu nazýváme taktem (také periodou nebo dobou jednoho bitu). Elementární signál má tedy význam pouze uvnitř doby t , protože v době změny signálu nemůžeme rozhodnout, zobrazíme-li logickou hodnotu 0 či 1. V počítači se setkáváme se dvěma způsoby zobrazení stavů logických proměnných nebo, jak se často říká, se dvěma způsoby zobrazení informace: hladinovým čili statickým a dynamickým. U statického zobrazení jsou symboly 0 a 1 zobrazeny např. napěťovými hladinami, které, které vyplňují celou dobu t (okamžiky změn hladin ideálně neuvažujeme). Na obr. 2.2a je příklad statického zobrazení logické proměnné, která postupně nabývá logických hodnot 1,1,0,1.

Obr. 2.2. Způsoby zobrazení informace: a) statické (hladinové) zobrazení; b) dynamické zobrazení U dynamického zobrazení je symbol 1 zobrazen přítomností impulsu v době t , symbol 0 jeho nepřítomností, popřípadě opačnou polaritou impulsu (obr. 2.1). Proto se tomuto způsobu zobrazení říká také impulsní. Na obr. 2.2b je příklad dynamického zobrazení téže časové zá19 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


vislosti proměnné jako u hladinového způsobu. Nejčastější způsob hladinového zobrazení je zobrazení pomocí napěťových úrovní. Uvažme příklad skutečného provedení logického členu, který pracuje se dvěma úrovněmi signálu 0,5 V a 5 V. Někdy se tyto úrovně označují L (low ~ nízká) a H (high ~ vysoká). Tato písmena se často vyskytují v pravdivostních tabulkách, popisujících skutečný logický člen. Na schématu i v popisu členu Booleovou algebrou je uvedena logická proměnná, nabývajících logických hodnot 0 nebo 1. Přiřadit k sobě dvojici: schéma – skutečné provedení logického členu lze zásadně dvojím způsobem: 0  L , 1  H , které označujeme jako pozitivní logika a nebo 0  H , I  L , negativní logika. Jestliže se komerční člen charakterizuje v tabulce znaky L, H je to samo o sobě dostatečně výstižné. Jsou-li v tabulkách jen logické hodnoty 0 a 1 je nutné ještě dodat, o jakou logiku jde. Např. člen popisovaný při pozitivní logice jako logický součin, dává výstup v negativní logice jako logický součet atd. Snadno se o tom přesvědčíme, jestliže v pravdivostních tabulkách včetně jejich záhlaví zaměníme logickou hodnotu 0 za 1 a naopak. Zobrazení logických hodnot 0 a 1 kmitočtem, fází nebo magnetickou indukcí (obr. 2.1) se většinou užívá v paměťových systémech počítačů a souvisí s požadavkem větší spolehlivosti nebo trvalostí uchování informace v takových systémech i při odpojení napájecích zdrojů. Přiřazujeme-li logickým hodnotám 0 a 1 nějaké konkrétní hodnoty napětí např. U0 a UI, máme na mysli ideální hodnoty těchto napětí (tj. např. UI je přesně 5V, U0 je přesně 0,5V; žádné jiné hodnoty nejsou v ideálním případě přípustné). U reálného obvodu je však nemožné dodržet ideální hodnoty, protože každá veličina logického obvodu je závislá na mnoha dalších činitelích, jako např. na rozptylu parametrů použitých součástek, vlivu šumu, teploty, kolísání napájecího napětí, magnetického či elektrického pole atd. Proto je správnější hovořit o pásmech signálů kolem ideálních hodnot. Příklad takových pásem je na obr. 2.3.

Obr. 2.3. Pásma signálů. Každou hodnotu napětí, ležící v intervalu ULmin až ULmax považujeme za nízkou úroveň a hodnotu napětí z intervalu UHmin až UHmax pokládáme za vysokou úroveň. Vlivy, které neumožňují dodržet ideální úrovně elementárních signálů, nedovolují rovněž stanovit ideální, ostrou hranici mezi pásmy. Proto jsou intervaly nízké a vysoké úrovně oddě20 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


leny tzv. zakázaným pásmem. Vyskytne-li se v logickém obvodu hodnota napětí ze zakázaného pásma, nemůžeme rozhodnout, zda zobrazuje logickou hodnotu 0 či I.

2.2.

Třídění logických obvodů

Podle fyzikálního principu rozeznáváme logické obvody elektrické, magnetické, pneumatické, optické, mechanické, chemické atd. Podle použitých základních prvků můžeme např. elektrické dělit na reléové, diodové, tranzistorové, diodově tranzistorové atd. Podle způsobu vazby uvnitř logických členů mluvíme o logických obvodech vázaných odporově, emitorově atd. Podle hlediska technologie a složitosti mluvíme o logických obvodech malé, střední a velké integrace. Z hlediska rychlosti zpracování informace v obvodu rozlišujeme rychlé a pomalé obvody apod. V další části studijního materiálu si budeme všímat pouze logických členů elektrických, a to takových, jejichž vstupní i výstupní stavy se vyznačují napěťovými hladinami, a které proto často nazýváme hladinové a nebude-li uvedeno jinak, budou uvažovány výhradně obvody pracující v kladné logice.

2.3.

Kombinační logické obvody

Fyzikální model základní (jednoduché) logické funkce budeme nazývat základním logickým členem nebo krátce logickým členem. Každý logický člen je charakterizován vztahem mezi jeho vstupními a výstupními logickými proměnnými. Vstupní proměnné příslušejí nezávisle a výstupní závisle proměnné té logické funkce, kterou daný logický člen realizuje. Každé vstupní proměnné xi (popř. výstupní proměnné yj) je přiřazeno napětí U xi U 0 ,U1 (popř. U y j U 0 ,U1 ). Napětí Ux nazýváme vstupním, Uy výstupním napětím. Připomeňme, že mnohdy z důvodů stručnosti nerozlišujeme např. mezi xi a Uxi, a to zejména ve schématech a u časových diagramů, které můžeme považovat za jeden ze způsobů popisu chování logického členu. Spojováním základních logických členů vytváříme složené členy nebo logické obvody, jimiž realizujeme logické funkce. Každý kombinační i sekvenční logický člen charakterizujeme: 1. Logickými vlastnostmi; ty jsou dány logickými funkcemi, které člen realizuje. 2. Fyzikálními vlastnostmi; ty umožňují hodnotit kvalitu nějakého reálného logického členu pomocí jistých fyzikálních veličin, které budeme nazývat parametry logického členu. a) Základní statické parametry Počet nezávislých vstupů (vstupy větvení). Rozvětvení. Rozvětvením nazýváme číslo N, které je rovno maximálnímu počtu jednotkových zátěží, které lze připojit na výstup členu viz obr. 2.4a, kde je rozvětvení naznačeno soustavou paralelních vodičů.



Obr. 2.4. Parametry logického členu Statická, neboli převodní charakteristika se definuje jako závislost výstupního napětí plně zatíženého logického členu na jenom ze vstupních napětí. Při jejím měření musí být na ostatní vstupy logického členu připojena taková úroveň napětí, aby nebránila působení změny vstupního napětí na výstup. Převodní charakteristika logického členu obsahujícího zesilovač je na obr. 2.4d. Mezní hodnoty napěťových úrovní na výstupu členu tj. U1min, U1max, U0min, U0max. Šumová imunita neboli odolnost proti statickému rušení se definuje se jako šířka pásma dovolených změn napěťových úrovní na vstupu členu podle obr. 2.4b. S1 vyjadřuje odolnost proti statickému rušení na jednotkové úrovni a podobně S0 na nulové úrovni. Kromě těchto veličin se udávají zpravidla ještě tyto: příkon, velikost napájecího napětí a jejich tolerance, provozní teplota, popřípadě rozmezí teplot, vstupní a výstupní proudy apod. b) Základní dynamické parametry Dynamické parametry charakterizují především kmitočtové vlastnosti logického členu a definujeme je pomocí obr. 2.4c. Doba tpd0 udává zpoždění přechodu signálu na nulovou úroveň a podobné doba tpd1 udává zpoždění přechodu signálu na jednotkovou úroveň. Charakteristické zpoždění je dáno vztahem t pd 

t pd 0  t pdI 2

(2.1)

Dynamická šumová imunita se udává většinou jako maximální dovolená šířka a amplituda rušivého signálu, jehož vliv se ještě nesmí projevit na výstupním signálu. Kromě těchto parametrů se někdy ještě udávají délky hran elementárních signálů a u sekvenčních logických členů požadavky na tvar výstupních signálů apod. 3. Provozně ekonomické vlastnosti: dobu života, spolehlivost, pořizovací náklady, konstrukční a technologické řešení, provozní náklady, zabraný prostor, požadavky na napájecí napětí, odolnost v prostředí atd.



2.3.1. Součtový logický člen Součtový logický člen realizuje funkci disjunkce, proto jej nazýváme člen NEBO (anglicky OR).

Obr. 2.5. Součtový logický člen Chování součtového logického členu pro dvě vstupní proměnné x1 a x2 a výstupní proměnnou y je popsáno logickou mapou včetně symbolické značky na obr. 2.5. 2.3.2. Součinový logický člen Součinový člen realizuje logickou funkci konjunkce, která odpovídá spojení výroků pomocí spojky „ i ―, proto jej často nazýváme člen I (anglicky AND). Jeho symbolická značka s logickou mapou je na obr. 2.6.

Obr. 2.6. Součinový logický člen 2.3.3. Invertor Abychom dostali takový soubor členů, který umožňuje realizovat libovolnou logickou funkci, musíme k předchozím členům vytvořit ještě jeden člen umožňující realizaci negace (funkci jediné nezávisle proměnné). Takový člen, jehož grafická značka a logická mapa je na obr. 2.7, nazýváme člen NE (anglicky NOT). Je-li na jeho vstupu jednotková úroveň signálu, pak výstupní je nulová a naopak.



Obr. 2.7. Logický člen NOT a jeho převodní charakteristiky

2.3.4. Univerzální logické členy Jak bylo již předešle uvedeno, logické členy se při realizaci nějaké logické funkce řadí většinou za sebou tak, že výstupy jedněch jsou připojeny na vstupy dalších, takže vznikají řetězce logických členů. Má-li logický člen umožnit vytvoření libovolně dlouhých řetězců, musí mít jeho převodní charakteristika takový tvar, aby ze „zkažené nulové úrovně―, která vstoupí, vznikla „méně zkažená nulová úroveň― na výstupu a obdobně u jednotkové úrovně. Tomu jevu se říká regenerace hladin a požadovaná charakteristika by měla mít tvar podle obr. 2.4d. Hladinově regenerovat může jen člen obsahující aktivní prvek (např. tranzistor). Této představě nejlépe vyhovuje logický člen, který má na svém výstupu např. invertor, jehož převodní charakteristika je uvedena na obr. 2.7 a splňuje požadavek regenerace hladin. Jde v podstatě o tutéž charakteristiku jako obr. 2.4, avšak (vzhledem k funkci negace realizované invertorem) zakreslené v opačné diagonále. Logický člen regenerující hladiny pomocí invertorů si tedy můžeme představit blokově podle obr. 2.8.

Obr. 2.8. Struktura univerzálního logického členu Na logickou část navazuje invertující část. Realizuje-li logická část např. funkci logického součinu, pak na výstupu takového členu dostáváme negaci tohoto součinu, což odpovídá 24 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Shefferově funkci, což je úplný soubor funkcí. Podobně realizuje-li logická část členu logický součet, pak na výstupu je jeho negace což odpovídá Peirceově funkci, která je také úplným souborem funkcí. Znamená to, že tato koncepce představuje Shefferův (resp. Peirceův) člen, který sám umožňuje realizovat libovolnou logickou funkci. Proto takové členy také nazýváme univerzálními logickými členy.

Obr. 2.9. a) Shefferův, b) Pierceův člen Na obr. 2.9a je grafická značka Shefferova členu, pro který se značně rozšířil název NAND (NOT-AND), nebo I-NE a jeho principiální zapojení v němž jsou pro přehlednost vynechány vstupní odporové děliče, přičemž negace se vytváří připojením tranzistorů na společný kolektorový odpor. Analogicky lze popsat i Peirceův člen jako součtový člen s negací. Odtud vyplývá i jeho název: člen NEBO-NE, NOR (NOT-OR). Grafická značka i princip zapojení je na obr. 2.9b.

Obr. 2.10. Montážní logický člen Uvažujme nyní členy pole obr. 2.10a se spojenými výstupy. Předpokládáme, že konkrétní zapojení obou součtových členů umožňuje spojit jejich výstupy bez nežádoucích následků (např. zničení tranzistorů); pak se snadno přesvědčíme, že jsme tímto spojením vytvořili vlastně nový logický člen, protože výstup dosáhne jednotkové úrovně pouze tehdy, když oba 25 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


výstupy součtových členů budou mít současně jednotkovou úroveň. V tomto případě jde o člen součinový, který si můžeme představit v podobě obr. 2.10b. Takovýto logický člen, jehož symbolická značka je na obr. 2.10c, nazýváme montážním, fiktivním nebo drátovým logickým členem. Důležité uplatnění nacházejí drátové či montážní logické členy, zejména při přenosu informace pomocí sběrnice, kde zastávají funkci tzv. multiplexoru. 2.3.5. Fyzikální realizace logických členů Podívejme se nyní blíže na skutečnou podobu nejrozšířenějších logických členů, které se vyrábějí jako integrované obvody a které podle použitých konstrukčních prvků rozdělujeme na několik skupin. Odporově vázané členy se vyvinuly z přímo vázaných členů (DCTL — directly coupled transistor logic), u nichž přímé spojení kolektorů s bází navazujícího tranzistoru bylo sice z výrobního hlediska jednoduché, avšak nepříznivě se přitom projevoval výrobní rozptyl vstupních charakteristik tranzistorů, který značně omezoval rozvětvení a zhoršoval činnost obvodu. A tak se do obvodů báze zařadily odpory a takto vzniklý obvod se začal označovat jako odporově vázaný tranzistorový člen zkratkou RTL (resistor - transistor logic). Obvody RTL se vyráběly jako monolitické integrované obvody i jako hybridní obvody. Byly vyvinuty různé modifikace obvodů RTL. Na obr. 2.11a je konkrétní zapojení obvodu RTL a na obr. 2.11b je uvedeno odpovídající logické schéma. Obvod má komplementární výstupy, což poskytuje uživateli bohatší možnosti využití obvodu. V dnešní době nejsou již obvody RTL důležitým druhem, vyskytují se jen u starších číslicových zařízení a jsou nahrazeny modernějšími obvody, zejména obvody TTL.

Obr. 2.11. Obvody RTL

2.3.6. Diodově-tranzistorové obvody Jako další můžeme uvést spojení diodových obvodů s tranzistory. Vznikly tak obvody označované zkratkou DTL (diode-transistor logic), jejichž základním představitelem je obvod 26 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


podle obr. 2.12, který také odpovídá zavedené představě univerzálního logického členu. Diody D1, D2, D3 a odpor R1 tvoří jednoduchý diodový obvod logického součinu, zbývající část obvodu představuje invertor.

Obr. 2.12. Základní obvod DTL Diody D4 a D5, tvoří vazební článek mezi součinovým obvodem a invertorem. Tyto tzv. posouvací diody umožňují realizovat obvod bez pomocného zdroje předpětí a navíc zvětšují šumovou imunitu obvodu. Jsou-li všechna vstupní napětí na úrovni 4 V, diody D1 až D4 nevedou a kdyby neprocházel proud přechodem báze-emitor, bylo by napětí v bodě B asi 2,5 V, což je víc, než je zapotřebí k otevření tranzistoru. Ten se tedy otevře, napětí v bodě B klesne asi na 0,6 V, takže napětí na výstupu členu odpovídá saturačnímu napětí a je asi 0,2 V. Je-li kterékoliv ze vstupních napětí na nulové úrovni, tj. přibližně na 0,2 V, je v bodě A asi 0,8 V. K tomu, aby přes diody D4 a D5 od bodu A procházel nějaký proud, by na těchto diodách muselo být napětí alespoň 1,2 V. Jelikož tomu tak není, proud přes tyto diody neprochází, takže v bodě B je napětí 0 V, které udrží tranzistor v uzavřeném stavu, a tedy na výstupu je napětí 4 V odpovídající jednotkové úrovni elementárního signálu. Tento člen tedy realizuje funkci NAND: y  x1 x2 x3 . Kdyby v uvažovaném případě s alespoň jedním vstupním napětím na úrovni 0,2 V byla namísto dvou posouvacích diod použita jen jedna, pak napětí 0,8 V v bodě A by způsobilo otevření této diody (prahové napětí pro otevření diody nebo přechodu báze-emitor uvažujeme 0,6 V) a pak by v bodě B bylo 0,8 — 0,6 = 0,2 V, což je sice méně než prahové napětí, potřebné pro otevření tranzistoru, ale již 0,4 V šumového napětí by mohlo tento tranzistor otevřít a narušit tak správnou činnost obvodu. Nejrozšířenějším druhem logických členů jsou zatím tranzistorově-tranzistorové obvody, uváděné obvykle zkráceně jako obvody TTL (transistor-transistor logic). Můžeme si je představit jako modifikovaný obvod DTL, u něhož je diodová část, tvořící funkci součinu, nahrazena víceemitorovým tranzistorem.



Obr. 2.13. Základní obvod TTL a jeho převodní charakteristika Na obr. 2.13a je konkrétní zapojení jednoho základního logického členu NAND se třemi vstupy, vyráběného ve formě integrovaného obvodu s označením MH 7410, jehož převodní charakteristika je na obr. 2.13b. Kdybychom zjednodušeně uvažovali pouze část obvodu s tranzistorem T1,T2 a T3 a k tranzistoru T3 připojili jednoduchý kolektorový odpor, dostali bychom obvod velmi podobný obvodu DTL: emitory tranzistoru T1 odpovídají vstupním diodám, přechody báze-kolektor tranzistoru T1 a báze-emitor tranzistoru T2 tvoří posouvací diody (D4 a D5 v obr. 2.12). Avšak snaha po zkrácení časových konstant a zvětšení výkonového zisku vedla k zapojení s tranzistorem T4. Zkrácení časové konstanty lze uskutečnit zmenšením kolektorového odporu (uvažováno vzhledem k tranzistoru T3), avšak malý kolektorový odpor by zase zvětšil potřebný příkon obvodu. Je tedy žádoucí, aby při otevřeném tranzistoru T3 (tj. při dolní úrovni na vstupu členu) byl jeho kolektorový odpor velký a při zavírání tohoto tranzistoru z požadavku co nejkratší časové konstanty zase malý. Tuto funkci kolektorového odporu tranzistoru T3 uspokojivě řeší sériové spojení diody D tranzistoru T4 a jeho kolektorového odporu, jehož velikost se ve výrobě ustálila na 100 až 130  . Uvažujme nyní, že výstupní napětí Uy je na dolní úrovni. Pak všechna vstupní napětí Ux musí být na horní úrovni a tranzistory T2 a T3 jsou v saturaci. Napětí na bázi T4 se rovná napětí kolektoru T2 a dosahuje přibližně 0,2 + 0,6 = 0,8 V. Uvažujeme-li saturační napětí na přechodu kolektor-emitor tranzistoru T3 0,2 V, pak na sériové spojení přechodu báze-emitor a diodu D zbývá tedy jen 0,6 V, což je nepostačující k otevření tranzistoru T4, a tedy při otevřeném T3 je v jeho kolektoru zapojen velký odpor. Nyní uvažujme, že kterékoliv ze vstupních napětí se změní na dolní úroveň. V tom případě se tranzistory T1 a T2 uzavřou, napětí na bázi T4 poroste a stejně tak poroste výstupní napětí Uy, dokud nedosáhne hodnoty napájecího napětí, zmenšeného o úbytky na diodě D, tranzistoru T4 a odporu Rk , tj. velikosti asi 3,5 V. Během vzrůstu výstupního napětí se také musí nabít předpokládaná zatěžovací kapacita, a to se děje proudem procházejícím přes odpor Rk, otevřený tranzistor T4 i diodu D, jejichž odpory v propustném směru jsou velmi malé. Časovou konstantu tohoto nabíjení tedy určuje v podstatě jen malý odpor Rk, a tím je dosaženo krátké spínací doby. Zdálo by se, že vzhledem k požadavku malé časové konstanty by odpor Rk mohl být ještě menší. Avšak během spínání, kdy je ještě T4 otevřen, je odpor Rk jediným kolektorovým od28 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


porem tranzistoru T3, takže při jeho dalším zmenšování by neúměrně vzrostla proudová špička ve výstupním obvodu, která již při uvedeném odporu 130Ω dosahuje asi desetinásobek ustáleného stavu proudu. Odpor Rk tedy omezuje proudové špičky, vznikající během spínání. Samotný výstupní obvod je zřejmě zdrojem proudového šumu, který může vyvolat nežádoucí jevy (odrazy, zvětšení příkonu při vysokých kmitočtech apod.). Uvedené zapojení má jistou nevýhodu: nelze tvořit tzv. montážní logický člen spojením výstupů několika členů. Snadno se přesvědčíme, že přímé propojení výstupů např. dvou uvedených členů, z nichž jeden dosahuje horní a druhý dolní úrovně výstupního napětí vede vlastně ke zkratu, který může způsobit zničení tranzistorů.

Obr. 2.14. Obvod TTL s otevřeným kolektorovým výstupem Aby bylo možné vytvářet montážní členy i u obvodů TTL, vyrábějí se logické členy podle zapojení na obr. 2.14a, které vlastně představuje zjednodušený základní obvod s otevřeným kolektorovým výstupem. Požadovaná logická funkce se realizuje tak, že se výstupy takovýchto členů připojí na společný vnější kolektorový odpor, jehož velikost se určí podle počtu připojených členů. Tak např. zapojení podle obr. 2.14b realizuje logickou funkci y  x1 x2 . x3 x4 . x5 x6 (uvažované členy s otevřeným kolektorem jsou zobrazeny zjednodušeně pouze výstupním tranzistorem T3). Odpovídající logické schéma je na obr. 2.14c. Jak je zřejmé, jde v tomto případě o součinový montážní člen. Zapojení s otevřeným kolektorem neposkytuje výhody základního zapojení podle obr. 2.13 získané použitím tranzistoru T4 a diody D ve výstupním obvodu členu. Aby byly tyto výhody zachovány a bylo možné vytvářet montážní logické členy, byl navržen tzv. třístavový logický člen NAND. Jeho principiální zapojení je na obr. 2.15a. Jak je vidět, jde o modifikaci základního zapojení obvodu TTL, ve kterém lze blokovacím spínačem uzemnit bázi tranzistoru T4 a emitor T1. Skutečná podoba blokovacího spínače je na obr. 2.15b. Tento obvod může být v jednom ze tří možných stavů: 1. Je-li Ublokovací = U1 (tj. blokovací spínač je sepnut) jsou oba tranzistory T3 i T4 uzavřeny bez zřetele na ostatní vstupy obvodu. Tento stav se nazývá stavem s vysokou impedancí výstupního obvodu.



Obr. 2.15. Principiální zapojení třístavového členu NAND 2. Je-li Ublokovací = U0 (tj. blokovací spínač je rozepnut) a všechny ostatní vstupy jsou jednotkové, je tranzistor T3 otevřen a T4 zavřen. 3. Je-li Ublokovací = (U0 (spínač je rozepnut) a kterýkoliv z ostatních vstupů je na dolní úrovni, je T, uzavřen a T4 otevřen. Předpokládejme nyní několik takových členů se spojenými výstupy. Budou-li všechny blokovací vstupy na jednotkové úrovni, bude společný výstup ve stavu s vysokou výstupní impedancí. Bude-li však mít jediný ze spojených členů blokovací signál na nulové úrovni, bude logická hodnota na společném výstupu určena logickou hodnotou danou právě tímto logickým členem, takže takovéto spojení se chová jako montážní logický člen. Zdálo se, že třístavový člen NAND najde podstatně širší uplatnění v návrhářské praxi. Zatím tomu tak není a můžeme jej chápat jako obohacení možností poskytovaných technologií TTL. Další možnost poskytují obvody TTL v podobě složeného členu podle obr. 2.16a. Jde o další modifikaci základních obvodů, která realizuje funkci y  x1 x2  x3 x4  y1 , kde

y1  x5 x6 x7 x8 je funkce, která se vytváří pomocným logickým obvodem, tzv. expandérem. Zapojení expandéru je na obr. 2.16c a jak vyplývá ze samotného názvu, slouží k rozšíření počtu vstupů. Na obr. 2.16b je odpovídající logické schéma k uvedenému zapojení s expandérem. Vzhledem k realizované funkci nazýváme takto složený člen I-NEBO-NE nebo častěji AND-OR-INVERT.



Obr. 2.16. Složený logický člen a expandér Integrovaný obvod MH 7450 obsahuje dva nezávislé členy podle obr. 2.16a a obvod MH 7460 dva nezávislé expandéry. Základní obvody TTL NAND se vyrábějí v několika modifikacích podle počtu vstupů (ten je dán počtem emitorů prvního tranzistoru). Řada MH 74 je určena pro provozní teploty 0 až 70 °C; ekvivalentní co do zapojení je řada MH 54, určená pro provozní teploty - 55 až +125 °C, a také řada MH 84 pro provozní teploty -25 až +85 °C. 2.3.7 Obvody TTL se Schottkyho diodou Snaha zvýšit spínací rychlosti u logických členů s tranzistory vedla k využití Schottkyho diod. U těchto diod tvoří téměř celý propustný proud elektrony, které procházejí z polovodiče do kovu. V Schottkyho diodě proto nevzniká nadbytečný náboj a zotavovací doba je z tohoto důvodu nulová.

Obr. 2.17. Tranzistor se Schottkyho diodou



Připojíme-li Schottkyho diodu k tranzistoru podle obr. 2.17a dostáváme tak tranzistor, kterému obvykle říkáme Schottkyho tranzistor, u něhož lze dosáhnout velmi krátkých spínacích časů. Na obr. 2.17b je příklad charakteristik pro křemíkovou a Schottkyho diodu. Jak je vidět, je na Schottkyho diodě v propustném směru mnohem menší napětí než u křemíkové diody. Proto paralelní spojení Schottkyho diody s přechodem kolektor-báze křemíkového tranzistoru zabrání nasycení (saturaci) tohoto tranzistoru a jeho spínací doby se zkrátí na doby kratší než 1 ns. Navíc dojde ke zlepšení kompenzace napětí mezi emitorem a bází. Na obr. 2.18 je zapojení jednoho ze základních logických členů (dvouvstupový NAND - SN 74 S 00 fy Texas Instruments), které souhrnně označujeme zkratkou S-TTL. Schottkyho diody jsou zde použity i ve vstupním obvodu, a slouží k omezení amplitud napětí vlivem odrazů na vedeních u všech tranzistorů kromě T4. Ten nemůže při normálních podmínkách dosáhnout saturace, proto není kombinován se Schottkyho diodou. Tranzistor T6 zlepšuje průběh převodní charakteristiky. Výstupní impedance obvodu při úrovni napětí U0 je asi 50 Ω. Charakteristické zpoždění u obvodů S-TTL bývá 2 až 4 ns, střední příkon asi 40 mW; dají se použít až do kmitočtu téměř 100 MHz.

Obr. 2.18. Logický člen S-TTL

2.3.8 Emitorově vázané obvody Jedny z nejrychlejších integrovaných logických obvodů (u nás nepříliš používané) jsou emitorově vázané obvody, označované zkratkou ECL (emitter-coupled logic) nebo též jinak proudově řízené logické obvody (CML — current-mode logic).



Obr. 2.19. Příklad členu ECL Příklad zapojení ECL obvodu je na obr. 2.19a. Obvod pracuje s referenčním napětím 4 V, které v podstatě určuje mez pro rozlišení dolní a horní úrovně elementárního signálu. Obvykle napětí 4,4 V zobrazuje logickou hodnotu 1, napětí 3,6 V logickou hodnotu 0. Tranzistory Tt,T2, T3 tvoři logickou funkci a jsou spolu s T4 připojeny na společný emitorový odpor Re jako v diferenciálním zesilovači. Jsou-li všechna vstupní napětí, odpovídající proměnným x1,x2, x3 na dolní úrovni (3,6 V), jsou tranzistory T1, T2, T3 zavřeny a T4 otevřen, takže v bodě B je asi 4,2 V, v bodě A téměř 5 V. Naopak, je-li kterýkoliv z tranzistorů T1, T2, T3 otevřen horní úrovní napětí na svém vstupu, je tranzistor T4 uzavřen, takže v bodě B je téměř 5 V, kdežto v bodě A asi 4,2 V. Považujeme-li tyto dvě hodnoty napětí za elementární logický signál, pak zřejmě v bodě A odpovídá funkci x1  x2  x3 v bodě B funkci x1  x2  x3 . Obvod v závislosti na vstupních napětích přepíná emitorový proud buď do tranzistoru T4 nebo do vstupních tranzistorů, a poskytuje výstupní funkci v komplementárním tvaru. Výstup z bodu A popř. B však vzhledem k napětím 4,2 a ~5 V nelze použít k buzení vstupů případného navazujícího členu (kde, jak jsme řekli, je třeba napětí 3,6 a 4,4 V), takže jsou v základním obvodu ještě výstupní obvody s tranzistory T5 a T6, které upraví napětí do požadovaného rozsahu. Symbolická značka celého obvodu je na obr. 2.19b. Obvody ECL umožňují rovněž jednoduchou tvorbu montážních logických členů; vyznačují se nízkou výstupní impedancí, značně velkým vstupním větvením (až 20) i rozvětvením (15). Příkon je poněkud větší - asi 40 mW na jeden člen; typické charakteristické zpoždění je 5 až 7 ns. Nevýhodou je potřeba dvou napájecích napětí. 2.3.9 Injekční integrované logické obvody Injekční integrované logické obvody (pro které se ujalo označení IIL nebo I2L) se zhruba podobají obvodům DCTL, avšak liší se ve způsobu napájení. V obvodech I2L jsou jako spínače použity tranzistory NPN s vícenásobnými kolektory, jejichž báze jsou vybaveny samostatnými proudovými zdroji podle obr. 2.20a. I když v souvislosti s výkladem o logických členech není nutno zacházet do podrobností, přece jen připomeňme, že tento proudový zdroj je tvořen laterárním tranzistorem, který je dán strukturou přechodů oblastí P (pod emitorem 33 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


tranzistoru T1), oblastí N (na substrátu) a oblastí P (pod bází tranzistoru T1). Oblast P pod emitorem T1 je tzv. injektor, který vstřikuje minoritní nosiče do oblasti báze T1, a způsobí tak sepnutí tohoto tranzistoru. Takový laterární tranzistor je uveden na obr. 2.20b.

Obr. 2.20. Principy zapojení obvodů s integrovanou injekční logikou Nyní si popišme zapojení podle 2.20c. Proud z proudového generátoru prochází do kolektoru tranzistoru T1 tehdy, když tento tranzistor bude v sepnutém stavu (tj. otevřen) a to znamená, že tranzistor T2 zůstává zavřen a naopak, je-li v rozepnutém stavu T1, prochází proud z proudového generátoru do báze tranzistoru T2 a otevře ho. Tohoto principu lze využít k realizaci logických členů.

Obr. 2.21. Příklad obvodu s integrovanou injekční logikou Tak na obr. 2.21 je obvod, který připomíná montážní logický člen a který realizuje funkci logického součtu vstupních proměnných A, B. Je-li A = 0 i B = 0 (tj. na vstupy je přivedeno napětí 0V), prochází proud od obou proudových zdrojů do vstupů, takže oba tranzistory T1 i T2 zůstávají zavřené a v místě spojených kolektorů těchto tranzistorů lze naměřit jednotkovou úroveň napětí (u I2L obvodů zpravidla 0,7 V). Ve všech ostatních případech kombinací vstupních napětí je vždy alespoň jeden z tranzistorů T1 a T2 otevřen, takže výstupní napětí je nulové. To znamená, že tato část obvodu realizuje funkci A  B . Výstupní obvod s tranzistorem T3 a odporem Rk působí jako invertor, na jehož výstupu je logický součet A + B. Smysl použití více kolektorů si můžeme ukázat u tranzistoru T2, který v uvedeném případě má dva kolektory. Na druhém kolektoru tohoto tranzistoru lze sledovat napěťové hladiny od-



povídající B . Vytvoření více kolektorů tedy poskytuje širší možnosti využití jednoho základního obvodu při realizaci nějaké požadované logické funkce. Injekční integrované logické obvody jsou založeny na využití velmi jednoduché základní bipolární struktury se dvěma tranzistory, přičemž se logická funkce vytváří pouhým propojováním těchto základních prvků. To umožňuje umístit jednoduchou technologií výroby integrovaného obvodu na plochu 1 mm2 až 3000 obvodů. Navíc je součin příkon * zpoždění (který se pokládá za jakýsi souhrnný ukazatel kvality členů) v porovnání s ostatními druhy tak malý, že obvody I2L najdou v dohledné době výlučné uplatnění při praktické realizaci logických obvodů v různých oblastech techniky, a to jako obvody s malými příkony. Obvody I2L neobsahují žádné odpory (až na jediný — výstupní), uživatel si může sám zvolit injekční úroveň a tak se absolutní úroveň šumové imunity nedá určit. Proto se určuje jen relativní šumová imunita, a to jako maximální šumový proud (injekční), který ještě neovlivní činnost obvodu při dané úrovni injekce. Nevýhodou obvodů I2L je, že pro spínací časy větší než 10 ns prudce stoupá příkon. Přesto lze úrovní injekce volit spínací rychlosti a tak omezit ztrátový příkon na minimum. 2.3.10 Logické členy s tranzistory MOS Logické členy s tranzistory MOS mají specifické vlastnosti, pro které je jejich použití v mnoha případech mimořádně výhodné. Vyznačují se tím, že člen obsahuje pouze jeden druh prvku — MOS tranzistor, který může pracovat ve funkci spínače, zatěžovacího odporu i paměťové kapacity. Technologie výroby je tedy jednodušší než u bipolárních obvodů a umožňuje realizovat na ploše 1 mm2 stovky tranzistorů, což vede k tomu, že jsou neobyčejně vhodné pro velkou integraci. Mají nepatrnou spotřebu energie (neboť jejich proudy jsou až o dva řádky nižší než u bipolárních tranzistorů), mimořádně velký vstupní odpor (asi 1014  ), avšak jejich rychlost je nižší než u bipolárních tranzistorů a klesá s kapacitní zátěží; proto někdy vznikají problémy při vytváření delších řetězců; rovněž dovolený teplotní rozsah je menší (do +85 °C). Na obr. 2.22 je příklad členu NAND s tranzistory MOS. Tranzistor T1 pracuje ve funkci společného kolektorového odporu a princip zapojení se tedy neliší od členů s bipolárními tranzistory.



Obr. 2.22. Logický člen s tranzistory MOS. 2.3.11 Prahové logické členy Prahovým logickým členem nazýváme člen, který realizuje prahovou logickou funkci nezávisle proměnných x1, x2 , xn definovanou takto n

0 je-li f  x1 , x2

, xn  

 w .x i 1

i

i

P

(2.2)

n

1 je-li  wi . xi  P i 1

kde xi 0,1, wi je váha a P je práh funkce. Funkční hodnota na výstupu prahového obvodu nezávisí obecně na počtu vstupních signálů - na výstupu se může objevit jednotková úroveň třeba již při jediném vstupním signálu s jednotkovou úrovní, jestliže tento signál má váhu převyšující práh. Vyjádření prahové funkce určuje také strukturu prahového členu, kterou si můžeme představit podle obr. 2.23a. Ve vstupu jsou obvody pro vytváření součinů wi . xi (nejde o součin logický), jejichž výstupy se sečtou (opět nikoliv logicky) v obvodu, kterému můžeme říkat sumátor. Výstupní veličina sumátoru se pak v porovnávacím obvodu porovná s hodnotou prahu a podle podmínek definovaných dříve vztahem 2.2 se na výstupu objeví jednotková nebo nulová úroveň, odpovídající hodnotě prahové funkce.

Obr. 2.23. Prahový obvod Na obr. 2.23b je schéma jednoduchého a rozšířeného prahového obvodu užívaného např. ve funkci hlídače kódu. Úlohu vstupních obvodů pro vytváření součinů zde zastávají odpory R1, R2 …, Rn, protože vstupní proudy I1, I2, …, In jsou nepřímo úměrné jejich velikostem. Spojení odporů do bodu A v souladu s 1. Kirchoffovým zákonem odpovídá součtu těchto proudů. Tranzistor je pak porovnávajícím prvkem, který je v počátečním stavu uzavřen napětím -Ub, které odpovídá prahu P. Vhodnou volbou odporů a napětí lze dosáhnout toho, že tranzistor otevře tehdy, když jsou splněny podmínky definované danou konkrétní prahovou logickou 36 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


funkcí. V uvedeném případě je výstup z kolektoru tranzistoru, a jde tedy o prahový člen s inverzním (negovaným) výstupem. V praxi se nejčastěji uvažují prahové členy, u nichž je váha konstantní (nebo rovna 1) a práh P je celistvým násobkem váhy. Grafická značka prahového členu je na obr. 2.24a. Je-li např. P = 2 a w = 1, na výstupu prahového členu se objeví jednotková úroveň pouze tehdy, když alespoň dva vstupní signály nabývají jednotkovou úroveň.

Obr. 2.24 Prahový a majoritní člen Zvláštním případem prahových funkcí pro stejné váhy jsou tzv. majoritní funkce. Zapisují se: M  x1, x2 , x3 , , xn  . Grafická značka majoritního členu je na obr. 2.24b. Na výstupu majoritního členu se objeví jednotková úroveň jen tehdy, když většina vstupů členu je připojena na jednotkovou úroveň.

2.4 Typické kombinační obvody sčítačky V této části budou uvedeny typické kombinační obvody, které se v počítačích nebo jiných číslicových zařízení vyskytují a kterým často říkáme funkční bloky. Mezi základní funkční bloky řadíme sčítačky, různé typy dekodérů čí přepínačů (realizované většinou jako kombinační obvody) a dále registry, čítače, střadače (jakožto sekvenční obvody, které popíšeme později). Funkční obvod ve většině případů považujeme za konstrukční celek, který může být použit v různých částech číslicového počítače. 2.4.1 Sčítačka modulo 2 Chování sčítačky je dané pravdivostní tabulkou na obr. 2.25, kde p představuje přenos,

z  x  y . Úplná součtová forma logické funkce popisující chování sčítačky modulo 2 je z  xy  x y .

(2.3)



Obr. 2.25. Sčítačka modulo 2 Tato forma je zároveň minimální formou, lze tedy přímo zakreslit logickou síť pro strukturu INEBO podle obr. 2.25c. Kdyby byly k dispozici pouze signály, odpovídající přímým logickým proměnným, obsahovala by logická síť ještě dva invertory pro vytvoření x a y . Metodou algebraických úprav lze dokázat, že vztah z  xy  xy lze přepsat na tvar

z  x. xy. y. xy .

(2.4)

Takto upravený vztah je již realizovatelný členy NAND podle obr. 2.25d a v porovnání se sítí I-NEBO odpovídající vztahu z  xy  xy při nedostupnosti negovaných proměnných obsahuje jen čtyři logické členy. Schematická značka sčítačky je na obr. 2.25b. 2.4.2 Koincidenční obvod Koincidenční obvod (komparátor) je kombinační logický obvod, který slouží k porovnání dvou n-místných slov. Jestliže se obě porovnávaná slova shodují ve všech svých bitech, objeví se na výstupu koincidenčního obvodu jednotková úroveň elementárního signálu, v opačném případě bude nulová.

Obr. 2.26. Paralelní koincidenční logický obvod 38 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Uvažujme dvě slova X a Y, jejichž jednotlivé řády tvoří proměnné x1, x2 ,

, xn a y1, y2 , , yn .

Zřejmě platí, že hodnota koincidenčního signálu K  I pro xi  yi  i  1,2, , n  . To umožňuje, podobně jako u n-místné dvojkové sčítačky, navrhnout koincidenční obvod pomocí rozkladu. Jestliže označíme symbolem Ki signál koincidence v i-tém řádu, pak K  K1.K2

n

Ki

K n   Ki

(2.5)

i 1

kde  je symbol logického součinu, který v tomto případě vyjadřuje, že slova jsou shodná tehdy, když jsou shodná současně ve všech svých bitech. Hodnoty signálu K1 lze odvodit z pravdivostní tabulky na obr. 2.26a. Ki  xi yi  xi yi (2.6) Tento vztah vyjadřuje logickou funkci ekvivalence jednotlivých bitů, již odpovídají dvoustupňové obvody I-NEBO v obr. 2.26b, jejichž výstupy jsou připojeny na člen logického součinu, který odpovídá vztahu n

K   Ki

(2.7)

i 1

Využijeme-li toho, že funkce ekvivalence a nonekvivalence jsou komplementární, můžeme vztah Ki  xi yi  xi yi (2.8) přepsat takto

Ki  xi yi  xi yi Porovnáme-li tento nový vztah se vztahem z  xy  xy

(2.9)

(2.10)

vidíme, že celý výraz pod negací je shodný s výrazem pro funkci modelovanou či realizovanou sčítačkou modulo 2, a tedy Ki  z (2.11) což umožňuje realizovat koincidenční obvod pomocí sčítaček modulo 2 s inverzí na výstupu. Uvažujeme-li, že jsou tyto sčítačky sestavené z členů NAND, pak celý koincidenční obvod má podobu podle obr. 2.26c nebo 2.26d. Nutno připomenout, že uvedené obvody neobsahují žádné paměťové prvky, proto signály na výstupu mají informační logickou hodnotu jen po dobu trvání vstupních signálů. 39 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


2.4.3 Dekodér Důležitými funkčními obvody počítačů jsou dekodéry, které slouží např. k převodu jednoho kódu na jiný, k dekódování obsahu registru instrukcí, nebo registru adresy apod. Dekodér je obecně kombinační logický obvod, který má n vstupů a m výstupů. Název dekodér je odvozen z toho, že takový kombinační obvod převádí kód n vstupních proměnných na kód m výstupních proměnných. Jako příklad lze uvést logický návrh dekodéru pro převod desítkových číslic z přímého dvojkového kódu BCD do Aikenova kódu s vahami 2421. Označme proměnné kódu BCD s vahami 8421 symboly x1, x2, x3, x4 a proměnné kódu 2421 symboly y1, y2, y3, y4. Chování dekodéru lze popsat pravdivostní tabulkou na obr 2.27a, v níž N je desítková číslice. Proměnné y1 až y4 můžeme považovat za logické závislé proměnné, jejichž hodnota je dána stavem nezávisle proměnných x1 až x4 podle tabulky. Na výstupy y1 až y4 se můžeme dívat jako na samostatné logické funkce, které lze realizovat např. logickým obvodem struktury INEBO. Pro každý z těchto výstupů lze známým způsobem zapsat úplnou součtovou normální formu a tu pak minimalizovat.

Obr. 2.27. Převodník kódu Proveďme minimalizaci pomocí Karnaughových map, z nichž jedna, pro výstup y1 je na obr 2.27c. S využitím neurčitých stavů dostáváme

y1  x1  x2 x3  x2 x4.

(2.12)

Podobně určíme minimální formy pro ostatní výstupy y2  x1  x2 x3  x2 x 4

,

(2.13)



y3  x1  x 2 x3  x2 x 3 x4 ,

(2.14)

y4  x4 .

(2.15)

Odpovídající struktura je pak na 2.27d. Celý převodník kódu lze schematicky kreslit podle obr. 2.27b.

2.5 Sekvenční obvody Z hlediska logických obvodů je třeba zavést nejprve sekvenční obvod asynchronní, jakož to obvod obecnější a zavedením jeho normalizované formy dospět ke speciálnějšímu obvodu synchronnímu. Zvláštní pozornost přitom věnujme pojmu paměťový člen. 2.5.1 Jednostupňový KO Ovládací proměnné obvodu obr. 2.28 tradičně značí R a S (z anglického set = nastavit na logickou hodnotu 1 a reset = nastavit opačně). Někdy se užívá samotné smyčky bez hodinových hradel. Tomuto zapojení budeme říkat asynchronní klopný obvod (paměťový člen) typu RS.

Obr. 2.28. Jednoduchý klopný obvod řízený hodinovými impulzy Obvodu včetně hodinových hradel budeme říkat taktovaný klopný obvod (paměťový člen) typu RS. Abychom ho odlišili od dokonalejšího paměťového členu, budeme o něm říkat, že je jednostupňový, schopný jen dvoufázové činnosti (někdy též vzorkovací obvod nebo obvod řízený úrovní hodinového impulsu).



Obr. 2.29. Asynchronní klopný obvod

Obr. 2.30. Jednostupňový klopný obvod z členů NAND a jeho schematická značka.

Rovněž ze součinových členů lze vytvořit klopný obvod stejného druhu s dvěma invertory viz obr. 2.29. Zde je třeba si uvědomit, že pamatovací stav smyčky je při stavu ovládacích proměnných t = 1, u = 1. Pro nulování vnitřní proměnné je třeba položit u = 0 a pro nastavení na logickou hodnotu 1 t = 0. Je patrno, že zřetelem na nastavení obvodu je ovládací, proměnné aktívní, rovná-li se hodnotě 0. V souladu s tímto se značí u  R, t  S . Hodinový systém lze vytvořit např. ze čtyř součinových členů obr. 2.30. 2.5.2 Dvoufázový režim činnosti obvodu řízeného hodinovými impulzy Spolehlivé ošetření přináší např. kombinační obvod, vložený mezi výstup a vstup členů systému. Na obr. 2.31 je člen s jediným přívodem hodinových impulzů, složený ze dvou dílů – stupňů (dvoustupňový paměťový člen, člen schopný jednofázové činnosti). Prvnímu se říká řídící stupeň (též hlavní paměť), druhému závislý stupeň (též pomocná paměť). Tím se platí za jedinou vynikající vlastnost: výstup se změní teprve tehdy, když obvod není citlivý na vstupu. Na obr 2.31b je značka pro paměťový člen RS.

Obr. 2.31. a) Dvoustupňový paměťový člen řízený hod. impulzy b) schématická značka



Zavedením dvoustupňového paměťového členu se podařilo odstranit nebezpečí, že by se rozruch, procházející od výstupu paměťového členu, vrátil ostatními obvody ke vstupu paměťového členu ještě během téhož vzorkovacího intervalu.

3. PAMĚŤOVÉ OBVODY Tak jako základním prvkem sekvenčního obvodu je klopný obvod, můžeme za stavební kámen číslicové techniky považovat paměťovou buňku. Obojí mají schopnost uchovat, zapamatovat si binární stav logické proměnné. Zatímco klopný obvod je víceméně „samostatným" prvkem, tvoří paměťová buňka jen část číslicové paměti. Teprve po doplnění podpůrnými obvody (zesilovače, adresové dekodéry atd.) vznikne konstrukční prvek, schopný uchovat určité množství logických hodnot nebo informací pro další potřebu nebo zpracování. Využití paměti je podstatou variability a modifikovatelnosti jednoduchých i složitých elektronických číslicových systémů. Funkci dílčích obvodů i celých systémů lze ovlivňovat (programovat) změnou obsahu užitých paměťových prvků. Principem funkce takto programovaných automatů i nadále zůstává přesně definovaná sekvence obvodových stavů. Není však již určena výlučně zapojením, ale v podstatné míře obsahem „programové" paměti. Podle aplikačního určení a užité technologie se paměti dělí do několika skupin. My si všimneme na oblast unipolárních polovodičových pamětí, které zcela dominují.

3.1

Typy polovodičových pamětí

Základní rozdělení typů polovodičových pamětí podle aplikace je na obr. 3.1. POLOVODIČOVÉ PAMĚTI RWM

RAM

STATICKÉ

FIFO

ROM

LIFO

PROM

EPROM

2

E PROM

DYNAMICKÉ Obr. 3.1. Symbolické dělení nejběžnějších typů pamětí

Paměti lze rozdělit do dvou hlavních skupin: paměti RWM (Read Write Memory) jsou určeny jak pro zápis, tak čtení uložených dat; paměti ROM (Read Only Memory) slouží pouze pro čtení pevně uložených dat. Užívají se jako paměti programu a konstant. 43 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Oba tyto základní typy lze pak podle dalších kritérií dělit do dalších, specializovaných oblastí. Prvním kritériem je schopnost uchování paměťového obsahu po odpojení napájecího napětí. Energeticky závislé (volatilní) paměti v tomto případě svůj obsah nenávratně ztrácejí, jsou to většinou všechny paměti typu RWM. Energeticky nezávislé (nevolatilní) paměti, tvořené většinou pamětmi typu ROM, si svůj obsah uchovávají. Paměti typu RWM se podle přístupu k datům dělíme dále na: a) Paměti RAM (Random Acces Memory - s libovolným přístupem). Data mohou být do paměti zapisována a z paměti čtena v libovolném pořadí. Každá konkrétní datová položka je vždy určena příslušnou adresou, která musí datový přístup vždy doprovázet. Prakticky většinou samostatně vyráběné paměti RWM jsou typu RAM, obr. 3.2a. b) Paměti FIFO (First In - First Out). Data mohou být z paměti čtena pouze v tom pořadí, v jakém byla do paměti zapsána. Systém FIFO nevyžaduje díky tomu externí adresování, obr. 3.2b.

Obr. 3.2. Základní typy paměti RWN; a) RAM, b) FIFO, c) LIFO Každá zapsaná položka může být zpravidla čtena pouze jednou, pak je ztracena. Tento typ pamětí je vhodný pro vytváření datových a adresových front. c) Paměti LIFO (Last In - First Out). Pořadí čtení uložených dát je přesně opačné, než v předchozím případě, obr. 3.2c. Této paměťové konstrukce se opět využívá jako vratného zásobníku ve složitějších monolitických strukturách. Jako poslední se užívá všeobecně známé dělení pamětí RAM na statické a dynamické. Obdobně se paměti ROM dělí na skutečné ROM a EPROM (Erasable Programmable Read Only Memory). Kromě toho ještě existují některé méně známé, přesto však užitečné a vyráběné paměti, z nichž pozornost zasluhují zvláště typy IRAM, NVRAM a EEPROM.

3.2

Stručný přehled základních unipolárních technologií

K dosažení velké hustoty integrace LSI5, přímo vázané s potřebou co nejmenšího příkonu, jsou obvody exponovaných bloků mikropočítačů (jako mikroprocesory, paměti různého typu nebo periferní a specializované složité obvody) v současné době realizovány některou z unipolárních technologií MOS (Metal Oxid Semiconductor). 5

Large Scale Integration



V podstatě existují tři základní technologie MOS - PMOS, NMOS a CMOS viz obr. 3.3. Jejich označení přímo vyplývá z typu kanálu tranzistoru MOS, který se tou kterou technologií vytváří.

Obr. 3.3. Princip tří základních unipolárních technologií; a) PMOS, b) NMOS, c) CMOS Technologie PMOS, obr. 3.3a, vytváří p-kanálové tranzistory difúzí p-dopantů (akceptorů obvykle bóru) do křemíkového substrátu typu n. Všechny kanály (tedy i drain a source) jsou vytvořeny současně v jedné vrstvě. Technologie NMOS, obr. 3.3b, je obdobná, k vytvoření nkanálových tranzistorů se však užívá n-dopantů (donorů — fosfor, arzén), difundovaných do substrátu typu p. CMOS, tj. komplementární technologie MOS kombinuje obojí, p i nkanálové prvky na společném křemíkovém substrátu, obr. 3c. Pro vytvoření komplementárních tranzistorů musí být do původního nejprve selektivně nadifundován opačný typ substrátu. Teprve pak je možno začít s realizací jednotlivých tranzistorových kanálů. Většina z prvních obvodů MOS a paměťových prvků byla realizována technologií PMOS. S rostoucími požadavky na rychlost a hustotu integrace se stále více uplatňovala technologie NMOS. V současné době nacházejí nejširšího uplatnění různé varianty technologie CMOS, jejíž největší předností je jednotkový příkon. Technologická zlepšení (HMOS, CHMOS) již prakticky odstranila původní nedostatek, kterým byla menší rychlost vůči NMOS. Základním požadavkem na jakýkoli paměťový prvek v tuhé (pevné) fázi je co nejmenší příkon na hradlo a co největší dosažitelná hustota integrace na jedné a co největší přístupová rychlost na druhé straně. Tomu nejvíce vyhovují technologie CMOS. 3.2.1 Paměti EPROM Erasable and Programmable Read Only Memory - energeticky nezávislá paměť (nevolatilní, obsah zachován i bez přítomnosti napájecího napětí). Programuje se elektrickými impulzy, její obsah může být vymazán ultrafialovým zářením pouze jako celek. Vyrábí se i bez mazacího „okénka". V tomto provedení může být naprogramována pouze jednou. Typická vnitřní struktura buňky EPROM je na obr. 3.4.



Obr. 3.4. Schéma technologie polysilikonové struktury paměťové buňky EPROM Základní kanál se vytváří běžným způsobem. Potom se dvojúrovňovým procesem vytvářejí dvě polykrystalická křemíková hradla, na nichž je založen vlastní energeticky nezávislý paměťový princip. Horní hradlo slouží k výběru buňky v řádku paměti. Vnitřní hradlo je plovoucí (float-ing), nemá žádný vývod. Obě hradla jsou jak vůči sobě, tak vůči kanálu dokonale izolována vrstvami oxidů. Paměť EPROM se programuje vstřikováním „horkých" elektronů z kanálu, pronikajících při zvětšeném (programovacím) napětí kanálu do izolovaného, plovoucího hradla. Tím plovoucí hradlo získá náboj, určující stav příslušné buňky. Náboj plovoucího hradla je kapacitně vázán na potenciál hradla vstupního. Ten se mění při výběru buňky podle toho, je-li pasivní, nebo právě adresovaná. Součet těchto dvou potenciálů určuje stav jednotranzistorové buňky aktivovaného kanálu. Je-li plovoucí hradlo dostatečně nabito, posouvá se prahové napětí tranzistoru tak, že se buňka (bit) jeví naprogramovaná do žádoucího stavu (L). V opačném případě zůstává prahové napětí malé, buňka si zachovává původní stav (H), shodný se stavem po vymazání jejího obsahu. Ultrafialové záření při mazání paměti indukuje do plovoucího hradla dostatek energie k tomu, aby byla překročena energetická bariéra izolačního prostředí kolem něj. Elektrony, tvořící náboj hradla, se proto mohou rozptýlit do vstupního hradla a kanálu buňky. Stručně shrnuto, programování i mazání obsahu buňky EPROM se uskutečňuje nabíjením a vybíjením plovoucího hradla. Paměti EPROM musí být samozřejmě před programováním nejprve vymazány. Paměti lze mazat i programovat až po vyjmutí paměti ze zařízení. Přístupová doba běžných pamětí EPROM je asi 200 až 450 ns, kapacita jednoho paměťového obvodu je od 2 kB do 64 kB a blíží se kapacitě dynamických pamětí RAM. Hlavní výhody, možnosti opakovaného programování obsahu, se využívá s výhodou nejen na vývojových pracovištích, ale i jako náhrady trvalých pamětí PROM v menších a středních výrobních sériích. 3.2.2 Paměti EEPROM Princip mazatelných i programovatelných pamětí E2ROM je do značné míry podobný předchozímu. Podstatný rozdíl ukazuje srovnání příčného řezu paměťovou buňkou (obr. 3.5), zvláště v oblasti plovoucího hradla. Zatímco oblast kanálu je od hradla vzdálena zhruba 50 nm, v oblasti elektrody drain se tato vzdálenost zmenšuje na nepatrnou vrstvičku „tunelového 46 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


oxidu", asi 10 nm. Vzájemná vzdálenost obou hradel je již opět větší, kolem 80 nm. Podstata programování paměti E2PROM je opět založena na ovládání prahového napětí unipolárního tranzistoru změnou náboje jeho plovoucího hradla. V tomto případě je však hradlo elektrickou cestou nejen nabíjeno, ale také vybíjeno.

Obr. 3.5. Schéma technologie polysilikonové struktury paměťové buňky EEPROM Hlavní roli při tom hraje právě ona tenká vrstvička oxidu, která umožňuje na principu FowlerNordheimova fenoménu nábojovým nosičům (elektronům) pronikat touto izolační vrstvičkou při dosažení energie zakázaného pásu, která je podstatně menši než energie, potřebná k překročení energetické bariéry izolačního prostředí standardním mechanismem. Uvedený princip umožňuje, aby paměti E2ROM byly elektricky programovány i mazány přímo v zařízeních, v nichž jsou používány (In-Circuit). Je samozřejmé, že nemusí být mazán celý obsah současně, ale je možno postupovat po jednotlivých bytech. 3.2.3 Paměti SRAM Standardní paměti tohoto typu mají paměťové buňky buď ze čtyřtranzistorových (výhodné z hlediska ceny), nebo šestitranzistorových (výhodné z hlediska minimalizace příkonu) jednotek, obr. 3.6.

Obr. 3.6. Dva základní typy paměťových buněk SRAM 47 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


V obou uspořádáních vždy jedna dvojice tranzistorů zajišťuje vazbu maticové buňky na řádkový a sloupcový dekodér. Předností statických pamětí RAM je to, že jejich obsah nemusí být oživován. Přístupová doba může být velmi krátká, asi 50 až 200 ns. Poměrná složitost buňky však omezuje možnost dosáhnout velkých paměťových kapacit na čipu. Rychlé paměti SRAM se vyráběly technologiemi NMOS, popř. HMOS. Jejich nedostatkem byl poměrně velký příkon a malá paměťová kapacita. Ty paměťové bloky, které bylo třeba zálohovat, se osazovaly obvody CMOS. Jejich kapacita však byla malá, desky s pamětmi CMOS často obsahovaly několik desítek IO. V oblasti statických pamětí přinesl CMOS zvrat. Díky novým technologiím se dosahuje dříve nepředstavitelných kapacit čipu. Jejich přístupové doby se, podle specifikace, pohybují v rozsahu 120 až 200 ns, příkon v režimu standby je menší než 10  W (ve specifikaci LP) a mimořádně usnadňuje zálohování energeticky závislého (volatilního) paměťového obsahu. Paměti SRAM jsou standardním prvkem číslicové techniky a jako takové se vyrábějí v nejrůznějších provedeních, s různou kapacitou, s oddělenými nebo multiplexovanými vstupyvýstupy a s různou šířkou datového pole. Různým koncepcím pamětí SRAM odpovídají i určité odchylky v organizaci řídicích signálů. Ty jsou však vždy snadno pochopitelné. 3.2.4 Paměti DRAM V paměti DRAM (Dynamic Random Access Memory) je informace uložena pomocí elektrického náboje na kondenzátoru. Tento náboj má však tendenci se vybíjet i v době, kdy je paměť připojena ke zdroji elektrického napájení. Aby nedošlo k tomuto vybití a tím i ke ztrátě uložené informace, je nutné periodicky provádět tzv. refersh, tj. oživování paměťové buňky. Tuto funkci plní některý z obvodů čipové sady.

Obr. 3.7. Realizace jedné buňky paměti DRAM v technologii TTL Ačkoli se kapacita pamětí SRAM díky novým technologiím stále zvětšuje, zůstává v důsledku rozsáhlé konstrukce paměťové buňky SRAM stále o jednu generaci za dosažitelnou kapacitou dynamických pamětí DRAM, vyráběných stejnou technologií. Ty naopak nemohou dosáhnout přístupové rychlosti statických pamětí. Paměti DRAM byly až do současné doby jediným efektivním prostředkem k dosažení větší kapacity operační paměti. Nástup rozsáhlejších pa48 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


mětí CMOS RAM a samozřejmě i řada dalších, systémových činitelů bude i do budoucna znamenat trvalý tlak na další zvětšování paměťové kapacity čipů. Dynamická paměť RAM využívá jako paměťového média, podobně jako paměť EPROM, elektrického náboje. Ten však v tomto případě nemá trvalý charakter a musí být, pokud možno v pravidelných, minimálních časových intervalech, cyklicky obnovován. To je jak technologicky, tak obvodově náročný problém. Ve srovnání s předchozími se u pamětí DRAM setkáváme s neobvyklou realizací paměťové buňky, složitým přístupem k zápisu a čtení jejího obsahu i jeho udržování a nakonec se zcela odlišným adresováním. Paměti DRAM se vyrábějí jako jednobitové. To znamená, že pro výstavbu datové paměti 1 byte je zapotřebí 8 pouzder IO. Paměti různých kapacit jsou vyráběny se vzájemně kompatibilními vývody, liší se pouze konkrétním využitím adresového pole, které by však při klasické interpretaci, obvyklé u pamětí RAM, bylo velmi rozsáhlé. Buňka se skládá z vázané dvojice řízeného vstupního tranzistoru a paměťové kapacity. Hodnota bitu, uloženého v buňce, je prezentována přítomností nebo absencí elektrického náboje. Paměťová kapacita je selektivně zpřístupňována impulsním řízením vstupního, „přístupového" tranzistoru. Náboj může být na paměťovém „kondenzátoru" udržen vzhledem ke svodům a migraci pouze omezenou dobu. Při užívání paměti DRAM proto musí existovat mechanismus, který periodicky s určitým intervalem (řádově ms) čte obsah paměťové buňky a protože samo čtení je destruktivní proces, obnovuje podle zjištěného stavu úplným nabitím nebo vybitím paměťového kondenzátoru původní logickou úroveň buňky. Obvod, který čte, vyhodnotí a obnoví původní náboj buňky se označuje jako snímací zesilovač.

Obr. 3.8. a) Zjednodušené schematické a technologické znázornění buňky paměti DRAM, b) schematické znázornění vnitřní organizace paměťového pole

3.3 Vytváření paměťových sestav Z jednotlivých paměťových obvodů IO se k dosažení větší kapacity, případně i datové šíře, vytvářejí rozsáhlejší paměťové bloky RAM, ROM buď na společných, nebo samostatných 49 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


deskách s plošnými spoji. Přitom je vždy nutno zajistit dokonalé adresování právě jediného obvodu, který má být aktivován. Jinak by vznikaly vzájemné kolize dvou nebo několika datových vstupů/výstupů. Většina paměťových obvodů zachovává určitou standardní úpravu všech vstupních a výstupních signálů, které lze rozdělit do tří skupin, datové, adresové a řídicí. Pro vzájemnou vazbu paměťového bloku s komunikujícím systémem se využívá systému sběrnic (bus). Jsou to vždy několikabitové komunikační cesty, jejichž funkce, signálové parametry a vzájemná součinnost odpovídají určitým konvencím. Adresová sběrnice je jednosměrná, u malých systémů 16 bitová. Nejvyšší adresové bity se vyhrazují pro výběr (select) jednotlivých paměťových IO. K tomu se využívá rychlých bipolárních adresových dekodérů. Datová sběrnice musí být vždy obousměrná, tedy třístavová. Nejčastěji se setkáváme se sběrnicemi 8 bitovými (malé systémy). Řídicí sběrnice umožňuje řídit komunikaci po datové sběrnici. Jejím prostřednictvím se řídí přístupy k jednotlivým blokům paměti, jejich časování, aktivace a potřebné systémové korespondence. Pro jednoduchou ukázku využijeme vazby kombinovaného paměťového modulu RAM/EPROM na vnější prostředí (obr. 3.9).

Obr. 3.9. Příklad připojení kombinovaného programového (EPROM) a datového (RAM) paměťového bloku na systémovou sběrnici K výběru pamětí RAM i EPROM se v obou sekcích využívá samostatných adresových dekodérů. Při naznačeném uspořádání musí každý dekodér rozlišit čtyři adresové bloky. Pro celkem osm odlišných bloků stačí dekódovat tři nejvyšší, pro další adresování nevyužité adresové bity, např. A13 až A15. Takové jednoduché řešení ovšem pevně definuje spojitý adresový prostor. Každému bloku IO přísluší úsek 8 kB, který při menší paměťové kapacitě RAM nebo EPROM nemusí být využit. Obě sekce RAM i EPROM mohou podle způsobu využití 50 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


obou dekodérů buď spolu sousedit, nebo se i prolínat. U složitějších systémů, u nichž je třeba s paměťovým prostorem šetřit (nebo se musí počítat s potřebou jeho úpravy), musí být i řešení adresových dekodérů složitější. Jednotlivé obvody EPROM jsou při vyslání příslušné adresy a žádosti o čtení MEMR vybírány dekodérem D-EPROM. Podobně aktivitu dekodéru D-RAM určuje vedle příslušné adresy buď žádost o čtení ( MEMR ) nebo zápis ( MEMW ) do paměti RAM. Zbývající, podstatná část bitů adresové sběrnice slouží k vlastnímu adresování paměťové matice obvodů RAM i EPROM. Rozsáhlá třístavová datová sběrnice obou paměťových bloků RAM i EPROM je na obr. 3.9 řešena jako interní. Od systémové datové sběrnice (data bus) je oddělena bipolárním třístavovým obousměrným budičem. Řešení je výhodné jak z hlediska potřebné minimalizace zatížení výstupů obou stran sběrnice, tak také z hlediska hledání případných závad. K aktivaci obousměrného budiče sběrnice je opět třeba využít logického součtu přístupových žádostí k paměti ( MEMR + MEMW ), k řízení směru přenosu musí být využito signálu MEMR . Organizace přístupu k oběma paměťovým sekcím RAM i EPROM včetně přidělování adresových prostorů a odpovídajícího sekvenčního řízení vzájemné součinnosti všech tří částí systémové sběrnice je již záležitostí nadřazeného, například mikroprocesorového systému.

3.4 Aplikace paměťových obvodů v hardwarových automatech Zvažme, jak by se dalo využít vlastností paměťových obvodů při konstrukci běžných logických a sekvenčních automatů. Jako první příklad lze uvažovat automaty s výlučně, sekvenčním pracovním cyklem, tedy bez reakce na vstupní proměnné. Zde vystupuje možnost využít pevně naprogramovanou nevolatilní paměť (ROM, EPROM), použitou jako konverzní datový obvod (obr. 3.10).

Obr. 3.10. Kombinační logika s pamětí ROM Adresa paměti je pak tvořena kódem vstupních, obsah příslušného paměťového místa kódem výstupních proměnných. Takové metody jsou v praxi poměrně časté, např. při realizaci nestandardních datových konverzí a při mapování adresových prostorů, v nichž nacházejí výhodné použití rychlé binární paměti. Ty ovšem mají zpravidla malou paměťovou kapacitu.



Na obr. 3.11 je možné řešení generátoru několikafázového impulsního signálu s neměnným pracovním cyklem, rozfázovaným pomocí libovolného, např. binárního čítače (čítač adresující v taktu hodinového signálu paměť ROM, představuje generátor vnitřních stavů).

Obr. 3.11. Blokové schéma sekvenčního několikafázového generátoru s binárním čítačem a pamětí ROM; znázornění možnosti výběru jednotlivých stránek ROM nastavením adresových bitů a5, a6 Možnost libovolně naprogramovat obsah paměti odstraňuje potřebu generování budicích funkcí. Pak ani není třeba řešit úlohu pomoci stavového grafu. Každý vnitřní stav čítače představuje aktuální adresu paměti ROM a obsah takto adresovaného paměťového místa vždy určuje příslušnou kombinaci - kód výstupních proměnných. Z řešení vyplývá řada výhodných vlastnosti, například: - délku pracovního cyklu automatu lze definovat, popřípadě ovládat nastavením pracovního cyklu čítače - okamžité stavy výstupních proměnných i jejich vzájemné relace v jednotlivých pracovních fázích lze libovolně měnit, bez úprav zapojení, přeprogramováním obsahu paměti Celý proces je řízen v taktu hodin. Jeho každý impuls inkrementuje (zvyšuje o +1) obsah čítače a tedy i adresu paměti. Při použití obousměrného čítače, popř. čítače s přednastavením by bylo možno dosáhnout inverzní posloupnosti generovaných výstupních proměnných (dekrementováním stavu čítače), popř. nesekvenčních skoků stavů čítače a tím i sledu stavů výstupních proměnných. Zvláště druhá možnost zasluhuje pozornost, protože představuje jeden ze základních principů technické realizace programovatelných automatů. Disponuje-li užitá paměť větším počtem adresových vstupů než vyžaduje pracovní cyklus čítače, je možné vybírat z několika formátů výstupních funkcí. Zde je znázorněna možnost statického výběru čtyř programů, ovládaných pomocí vhodného nastavení dvou nejvyšších adresových vstupů paměti. Každá ze čtyř ,,stránek" pak může být naprogramována pro jinou výstupní funkci.



3.5 Kontrola a oprava chyb obsahu paměti Jedním z charakteristických rysů číslicové techniky je tvoření a používání kódů. Kódem rozumíme předpis, jak k sobě přiřadit prvky dvou množin. Prvky jedné množiny mohou být např. úkony, které je nějaké zařízení schopno vykonávat, prvky druhé množiny mohou být např. čísla. Tato čísla můžeme pak chápat jako názvy příslušných úkonů nebo dokonce jako rozkazy k provedení příslušných úkonů. Mohou v něm být zahrnuty číslice nebo značky, popř. i zkratky. Seznam všech přípustných znaků, tedy množina všech písmen, se někdy nazývá též abeceda nebo soubor symbolů. V dnešní číslicové technice se zpravidla omezujeme na dvouhodnotové proměnné, čemuž odpovídá binární abeceda, tedy abeceda, obsahující jen nulu a jedničku. Pro ruční zpracování je však vhodnější abeceda obsahující více písmen, např. abeceda tvořená množinou desítkových číslic, nebo dokonce abeceda tvořená množinou písmen. V těchto případech se při styku člověka s číslicovým zařízením písmena obecnější abecedy opět kódují dvojpísmenovou, binární abecedou, tj. vytvářejí se jejich obrazy jako sledy nul a jedniček. Nula a jednička se označuje souborně slovem bit, z anglického binary digit (dvojková číslice). Vhodná volba kódu zpravidla vede ke zjednodušení práce, což se projeví buď úsporou obvodů, nebo úsporou času. Jindy se při tvorbě kódu uplatňuje hledisko zabezpečení proti chybám.

Obr. 3.12. Čtyřrozměrná jednotková krychle Výhody těchto kódů plynou ze studia aritmetických algoritmů a příslušných obvodů. Lze říci, že dnes ztrácejí na významu, protože se upouští od použití speciálních desítkových sčítaček a místo toho se projevuje snaha použít i pro desítkové sčítání standardní dvojkové sčítačky. Obecné vlastnosti bezpečnostního kódu lze ukázat na tzv. jednotkové krychli, někdy též zvané Hammingův prostor. Považujme např. čtyři bity, vyjadřující desítkovou číslici v kódu BCD za čtyři souřadnice bodu v prostoru (čtyřrozměrném). Takovými souřadnicemi není možné určit libovolný bod v prostoru, nýbrž jen ty body, které tvoří vrcholy (čtyřrozměrné) krychle o hraně rovné jedničce 53 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


a s jedním vrcholem v počátku. Změna jedné souřadnice bodu (tedy chyba v jednom bitu) zde znamená záměnu vrcholu za vrchol sousední, ležící na opačném konci téže hrany. Čtyřrozměrná krychle je na obr. 3.12. Není třeba se namáhat představou čtyřrozměrného prostoru. Stačí nakreslit si průmět třírozměrné krychle (kreslen plně) a posuvem ve směru další souřadnice (čárkované hrany) připojit průmět další třírozměrné krychle (kreslený čerchovaně). Takto vzniklý celek nazýváme čtyřrozměrnou krychlí. Souřadnice jsou připsány k vrcholům. Nechť obecný vrchol krychle představuje jedno slovo, využité v kódu. Výskyt jedné chyby vytvoří slovo, lišící se od výchozího v jediném bitu. To bude nutně zobrazeno na sousední vrchol krychle. Má-li být možné tuto chybu indikovat, nesmí patřit nově vzniklé slovo mezi slova, využitá v kódu. Je tedy nutné dodržet podmínku, že vrcholy, sousedící s využitým vrcholem, nesmějí být využity. Uvedené odvození umožní zavést pojem minimální Hammingova vzdálenost. Je to vzdálenost dvou využitých vrcholů (uvažovaného kódu), které jsou si vzájemně nejblíže ze všech jeho dvojic, měřená v počtu hran. Kód schopný indikovat jednu chybu (k chyb), musí mít minimální Hammingovu vzdálenost alespoň dvě (k + 1). Kód schopný opravit jednu chybu (k chyb), musí mít minimální Hammingovu vzdálenost alespoň tři (2k + 1). To proto, aby vrcholu, do kterého zavedl výskyt chyb, byl stále ještě z využitých vrcholů nejbližší vrchol výchozí. Kód indikující jednu chybu6 lze vytvořit např. z kódu BCD přidáním dalšího, tzv. paritního bitu (P). Hodnota tohoto bitu se vytváří v závislosti na počtu jedniček v příslušném kódovém slovu, a to např. tak, aby celkový počet jedniček byl v takto vytvořeném kódovém slovu vždy lichý. Tehdy se hovoří o liché paritě. Obdobně je možná i parita sudá.

Obr. 3.13. Kód BCD s přidanou lichou paritou Kód BCD, doplněný lichou paritou, je na obr. 3.13. Nesouhlas parity upozorní jednoduchým způsobem na výskyt chyby.

6

Kód s minimální Hammingovou vzdáleností dvě



4. PROGRAMOVATELNÝ AUTOMAT Typické přístupy k řešení jednoduchého logického, popř. sekvenčního automatu založené na využití paměťových prvků, umožňují určitou, i když velmi omezenou funkční variabilitu obvodu změnou naprogramování obsahu pamětí. Jak uvidíme dále, obě koncepce se uplatňují i v obvodovém řešení programovatelných automatů a počítačů, i když odlišným způsobem. Samy o sobě jsou sice logické, nemohou však znamenat podstatný přínos z hlediska univerzálnosti využití. Celý systém zůstává příliš primitivní, protože musí stále respektovat současnou stavovou vazbu všech vnějších a vnitřních proměnných. Obecná koncepce programovatelných automatů je založena na zcela odlišné a lze říci přímo opačné filozofii. Pokusme se ji logicky navrhnout tak, že budeme brát do úvahy nedostatky a omezení vyplývající z možností hardwarových řešení automatů.

Obr. 4.1. Znázornění sekvenčního řetězení stavů/akcí hardwarového (a) a programovatelného (b) automatu V souladu s obr. 4.1a uvažujme sekvenční činnost hardwarového automatu, který z každého stavu tn přechází do stavu tn+1. Při přechodu mezi stavy musí vždy nastat nějaká, alespoň vnitřní akce, činnost. Pokud je významná i z hlediska vnějších obvodů, můžeme ji označit jako vnější akci. Sekvenční činnost hardwarového automatu není závislá na vstupních proměnných, provádí tedy pouze vnitřní a výstupní akce. Rozhodujícím kritériem, určujícím průběh těchto akcí, jsou tedy jednotlivé sekvence vnitřních stavů. Na obr. 4.1b je obdobným způsobem stylizována sekvenční činnost programovatelného automatu. Je obdobná, automat přechází z jednoho do druhého vnitřního stavu provedením nějaké vnitřní či vnější akce. Zásadní rozdíl je však v tom, že programovatelný automat může nezávisle na stavu, v jakém se nachází, vykonat jakoukoli akci, v případě potřeby i akci vstupní. Realizace každé akce je určena instrukcí, tvořící základní prvek programu, uloženého v programové paměti. Po skončené každé akce dostává řídicí jednotka automatu novou instrukci, určující, jakou akcí bude ve své činnosti pokračovat. Význam vnitřního stavu automatu je tímto mechanismem potlačen. I když to neplatí zcela obecně, stává se pouhým předělem mezi dvěma operacemi, akcemi.



4.1

Činnost automatu

Činnost programovatelného automatu již není limitována požadavkem trvalého sledování stavu všech vstupních proměnných. Může probíhat v sekvenčních úsecích, z nichž se každý může zabývat určitými úlohami. Při jejich provádění pak sleduje pouze ty vstupní proměnné, které jsou pro aktuální činnost významné. Navíc může tyto proměnné buď v přímé, nebo upravené formě ukládat a dále zpracovávat jak pro aktuální, tak pozdější potřebu. Program, který řídí činnost automatu, může být založen na nesrovnatelně efektnějších a logičtějších postupech a algoritmech, než jaké umožňovaly technické prostředky hardwarového automatu. Popišme nejjednodušší programovatelný automat, který by navazoval na naše dosavadní představy. Nástin možného řešení je na obr. 4.2.

Obr. 4.2. Jednoduchý sekvenční programovatelný automat Automat je pro jednoduchost koncipován tak, že umožňuje pouze sekvenční činnost. Skládá se v podstatě ze čtyř funkčních bloků: programového čítače, programové paměti, programovatelné logické jednotky, vstupního a výstupního registru. Programový čítač, řízený hodinovým signálem, adresuje programovou paměť. Program je tvořen sledem instrukcí. Instrukci si můžeme v tomto případě definovat jako binárně kódovaný obsah jednoho paměťového místa. Odlišnými instrukčními kódy lze ovládat jednak činnost logické jednotky, jednak čtení ze vstupního nebo zápis do výstupního registru vstupních a výstupních proměnných. Logickou jednotku si můžeme představit např. jako rozsáhlejší logický kombinační obvod, jehož funkce je modifikovatelná na základě aktuálního instrukčního kódu, přivedeného na řídicí vstupy jednotky. Naprogramováním paměti ROM lze v každém stavu programového čítače dosáhnout, v rámci instrukčního souboru, kterým disponuje logická jednotka, výběru libovolné logické funkce mezi vstupními a výstupními proměnnými. Činnost tohoto primitivního automatu již v zásadě není určena jeho obvodovou strukturou, ale programem, uloženým v programové paměti. Univerzální programovatelný automat ovšem musí umožňovat nejen prostou sekvenční činnost, ale i jiná, ne sekvenční řazení a provádění instrukcí. K tomu je samozřejmě zapotřebí podstatně složitějších technických i programových 56 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


prostředků. Struktura i instrukční soubor programovatelného automatu musí umožňovat programové skoky, cykly, testy, práci s podprogramy, přerušení programu a řadu jiných funkcí. Tím vzniká zcela nová situace. Pro realizaci celé rozsáhlé třídy úloh může být užito prakticky jednotné struktury programovatelného automatu s definovaným instrukčním souborem. Funkce automatu v konkrétních aplikacích je podstatnou měrou určena programem. Byť je sebe složitější, je vždy realizován omezenou, konečnou množinou instrukcí, kterou disponuje užitý procesor. V té se dá orientovat mnohem snáze a systematičtěji, než ve struktuře hardwarového automatu. Celá práce je tak podstatně „přátelštější". Dále lze využívat vyšších programových prostředků, jazyků, vývojových systémů i prostředků pro ladění programů, které výrobci jednotlivých automatů, včetně rozsáhlé literatury nabízejí. Při systematické práci s konkrétními typy procesorů, pak lze mnoho úloh řešit rutinní cestou, s využíváním postupně získávaných zkušeností. Logickým důsledkem těchto možností a předností je vznik mikroprocesoru (  P ). Je to integrovaný procesor programovatelného automatu, kterému by na obr. 4.2 odpovídala kombinace programový čítač (vzdáleně představující primitivní sekvenční ,,řadič") a logická jednotka (zhruba nahrazující ,,operační jednotku"). Podle aplikace a stupně technického vývoje samozřejmě existují různé typy programovatelných automatů. Dva základní si popišme podrobněji.

Obr. 4.3. a) Nesekvenční větvení sledů stavů i akcí hardwarového automatu, b) programový přepínač řízený na základě soustavy testů příznaků předchozích akcí Vzájemné rozdíly v řešení jejich procesorů osvětlují následující obrázky. Obr. 4.4 hardwarový automat. Je na něm znázorněno větvení sledu vnitřních stavů. Ze stavu S1 může automat na základě kódu vstupních proměnných přejít do jednoho ze stavů S2 až S4, nebo setrvat ve stavu původním. Celý tento, v hardwarovém pojetí složitý blok, v podstatě tvoří programový přepínač, znázorněný symbolicky na obr. 4.3b. Podle toho, jaký stav vstupních proměnných je vyhodnocen, vybírá se cesta, vedoucí k provedení požadované akce.



Obr. 4.4. Realizace přepínače vloženými akcemi a testy, které umožňuje jednoduchý programový řadič Na obr. 4.4 je orientačně znázorněn možný postup realizace takového přepínače programovatelným automatem, který užívá tzv. jednoduchý obvodový řadič. Tento typ  P je schopen v každém taktu hodinového signálu zpracovat jednu instrukci, která je však schopna zajistit pouze elementární operaci. Tou se myslí například nastavení přenosové cesty adresy, čtení, zápis, provedení logického testu apod. Provedení akce pak zpravidla vyžaduje sekvenci většího počtu těchto elementárních instrukcí. V takové situaci je, před zahájením programového úseku, simulujícího přepínač, nejprve nutno pomocí těchto instrukcí uskutečnit celou řadu operací, na jejichž základě mohou být zahájeny testy jednotlivých větvení. Po testu na platnost podmínky se buď vystupuje z cyklu na přípravu provedení požadované akce, nebo se přechází do dalšího testu. Není-li splněna žádná z podmínek, uzavírá se smyčka zpět na vstup celého programovaného úseku a tam probíhá tak dlouho, dokud není některá z podmínek splněna. Nedostatek obvodového řadiče pro běžné aplikace je evidentní. Je jím potřeba značného počtu instrukcí pro uskutečnění úplné akce. To značnou měrou komplikuje návrh programu, protože programátor se musí soustavně zabývat množinou nadbytečných ,,mikroinstrukcí". Zmíněné problémy radikálním způsobem potlačují běžné procesory, vybavené tzv. mikroprogramovaným řadičem. Instrukce těchto jednotek jsou tvořeny sekvencí, posloupností „mikroinstrukcí" ve smyslu předchozího odstavce. Jsou proto podstatně výkonnější a umožňují přehlednější výstavbu programu. Řešení programového úseku přepínače se pak, při využití testů příznakových indikátorů, může zjednodušit až do formy, naznačené na obr. 4.5.



Obr. 4.5. Mikroprogramovaný řadič potlačuje nutnost programovat redundantní akce Nutno si však uvědomit, že provedení komplexní instrukce zpravidla trvá podstatně déle. Přednosti programovatelných automatů mohou být zastíněny prakticky pouze ve dvou případech. Prvním jsou mimořádně jednoduché aplikace. Druhý případ se stává aktuálním v případě, když se jedná o prioritu extrémně rychlé časové odezvy. Z principu činnosti programovatelného automatu, založeného na postupném řešení úlohy, postupné realizace sledu instrukcí vyplývá, že hardwarový automat by měl být vždy rychlejší. Nebývá to však vždy pravdou, protože řada úloh je již natolik složitá, že je prostě přímou hardwarovou cestou řešit nelze.

4.2

Programové řízení automatu

Programovatelnost automatu, který může variabilně testovat vybrané proměnné; kritické podmínky a stavy, ukládat a zpracovávat různá data a datové bloky, modifikovat svoji činnost a nejrůznějším způsobem komunikovat s vnějším prostředím znamená, že jeho činnost může být mimořádně efektivní. Řadu hlavních zásad navrhl již před 150 lety Babbage. Na konci 2. světové války pak základní principy koncipoval von Neumann. Princip jeho počítače je blokově znázorněn na obr. 4.6.

Obr. 4.6. Von Neumannova koncepce číslicového počítače 59 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Celá činnost je podle příslušného programu řízena řadičem, který spolu s operační jednotkou tvoří základní prvky procesoru. Ústřední jednotkou celého procesoru pak je ALU (aritmeticko-logická jednotka). Program, který má být realizován, je uložen v operační paměti. Tam je také vyhrazen prostor pro data, která jsou systému zadávána, nebo která si vytváří sám jako výsledek čtení a zpracování vstupních dat nebo interních operací. Paměťový prostor programu a dat (ROM, RAM) může být buď spojitý, nebo oddělený (Harvardská koncepce). Činnost celého počítače je synchronizována hodinovým signálem. U klasického von Neumannova systému se program realizuje postupným zpracováváním jednotlivých instrukcí, uložených podle konvence krokového adresování ve spojitém paměťovém prostoru bezprostředně jedna za druhou. Každá instrukce se zpracovává v tzv. instrukčním cyklu. Tento typický proces lze rozdělit do několika charakteristických, vzájemně navazujících etap: a) Čtení instrukce. Každá aktualizovaná instrukce musí být nejprve přečtena z paměti a uložena do instrukčního registru IR; b) Provádění instrukce. Je dekódován operační kód instrukce a na jeho základě generována sekvence elementárních mikroinstrukcí, řídící všechny činnosti, potřebné ke korektnímu provedení instrukce. To se týká jak interních obvodů procesoru (operační jednotka), tak i vnějších bloků (paměti, obvody IO ...), se kterými procesor komunikuje prostřednictvím systémové sběrnice; c) Příprava adresy následující instrukce. Ještě v průběhu aktuálního instrukčního cyklu se již připravuje adresa instrukce následující. Von Neumannova koncepce při tom umožňuje generovat adresu bezprostředně následující, sekvenčně řetězené instrukce zcela automaticky a extrémně jednoduše, prostým inkrementováním stavu programového čítače, který dosud určoval adresu platné instrukce. Tím se podstatně zrychluje běh programu a zjednodušuje programování. U instrukcí, porušujících sekvenční sled ovšem musí být z pravidla učiněna výjimka - skokové instrukce, volání podprogramů apod. Procesor pak musí být schopen adresovat požadované paměťové místo. U volání podprogramů nebo aktivace přerušení pak ještě navíc uložit návratovou adresu do tzv. zásobníkové paměti (stack); d) Test požadavku přerušení. Při aplikaci programovatelného automatu se prakticky vždy vyskytují takové speciální požadavky nebo vstupní proměnné, které se vymykají běžným zvyklostem. Především v tom, že vyžadují bezprostřední, naléhavé ošetření s minimální přípustnou časovou prodlevou, prakticky v reálném čase. Normální režim programovatelného automatu těmto požadavkům nevyhovuje, protože je také v podstatě vůbec nerespektuje. Naopak, běžné vstupní proměnné testuje pouze tehdy, když v průběhu provádění programu potřebuje znát jejich stav. Vzniklá časová prodleva pak ovšem může být nepřijatelná. Je sice možné např. periodicky testovat stav některé proměnné. Tím se však podstatně zmenšuje výkonnost, propustnost systému, protože kvůli testu se vždy pozastavují ostatní činnosti.



4.3

Přerušení

Pro daný účel bývá většinou procesor vybaven zvláštním vstupem, umožňujícím uplatnit tzv. externí přerušení (interrupt). Požadavek přerušení může být vůči systému zcela asynchronní, náhodný. Aby bylo dosaženo co nejrychlejší reakce, testuje se vždy na konci každého instrukčního cyklu, zda tento požadavek nebyl uplatněn. Pokud ne, pokračuje program další instrukcí. Pokud ano, je nejprve dokončena instrukce běžícího programu a ukládá se obsah programového čítače do zásobníkové paměti jako návratová adresa běžícího programu. Technickými prostředky (řadič přerušení) se vyhodnotí priorita žádosti a vyvolá se tzv. vektor přerušení. Je to jedna z několika adres, na které musí být předem uložen počátek programového ošetření příslušné žádosti. Jakmile je zpracování přerušení ukončeno, lze vyvoláním návratové instrukce přejít zpět k realizaci původního přerušeného programu.

Obr. 4.7. Znázornění průběhu instrukčního cyklu Typický průběh instrukčního cyklu tak, jak byl výše popsán, předkládá vývojový diagram na obr. 4.7.

5. ZOBRAZENÍ INFORMACE V PAMĚTI POČÍTAČE Equation Chapter (Next) Section 5

5.1

Aktivní a pasivní informace

Aktivní informace určuje činnost operační jednotky počítače (strojová instrukce) a představuje pokyn k provedení určité operace počítače. Pasivní informace určuje, s čím bude operace počítače pracovat - údaj; množinu údajů nazýváme data. Na základě dvojkové kombina61 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


ce obsažené v paměťovém místě nelze určit, zda toto místo obsahuje instrukci nebo údaj. Informaci v paměťovém místě, na něž před zahájením instrukce ukazuje obsah čítače instrukci, interpretuje počítač jako instrukci. Informaci na místě, na něž při zpracování instrukce ukazuje adresová část instrukce, interpretuje počítač jako údaj. Program na úrovni strojově orientovaného jazyka sestává z instrukcí a údajů, které nemusí nezbytně vytvářet celistvé a navzájem oddělené úseky. Programátor, který vytvářející program ve strojově orientovaném jazyce musí zajistit, aby při výpočtu (tj. při postupném zpracování instrukcí) "nepřišla řada" na paměťové místo obsahující údaj. Nejčastěji se to dělá tak, že úseky dat jsou umístěny bezprostředně za nepodmíněnou skokovou instrukcí, která předává řízení na jiný úsek instrukcí. Skutečnost, že počítač neumí rozlišit instrukce a data, se využívá při speciálních programátorských obratech, v nichž se s instrukcí pracuje jako s údajem. Protože v tom případě program sám mění své instrukce, hovoříme o automodifikaci programu. V běžných programech je vhodné vyhýbat se těmto obratům, protože ztěžuji srozumitelnost programu. Při jejich použití není ze zápisu programu přímo zřejmé, co se bude ve skutečnosti při výpočtu provádět, brání formální verifikaci programu a znemožňuje konstrukci podprogramů s mnohonásobným přístupem. Tyto obraty plnily svou funkci v dobách, kdy při neexistenci nepřímých adres a indexregistrů představovaly jediný prostředek pro konstrukci průchodu polem paměťových míst v cyklu a pro výstavbu uzavřených podprogramů.

5.2

Zobrazení numerické informace v paměti

Zpracování numerické informace tvořilo historicky výsadní využití výpočetní techniky. Přesto, že aplikace z oblasti nenumerického zpracování nacházejí stále více uplatnění ve všech oblastech života, zůstává zpracování numerické informace jádrem využití počítačů všech kategorií. Zobrazení numerické informace lze rozdělit do dvou charakteristických skupin. V první skupině je základem pro zobrazení čísel hodnota 2 nebo její mocnina, a proto hovoříme o binárních zobrazeních. Ve druhé skupině je základem zobrazení hodnota 10 a binárního zobrazení se používá jen pro vyjádření hodnoty jednotlivých číslic desítkové soustavy, které vytvářejí desítkové číslo. Binární zobrazení umožňuje vysoce efektivní provádění všech aritmetických operací, vyžaduje však poměrně náročnou konverzi binárního zobrazení na znakové a zpět, jež je potřebná pro vstupní a výstupní operace počítače. Proto spadá využití binárního zobrazení především do oblasti vědecko-technických výpočtů (VTV), pro které jsou charakteristické náročné numerické operace a nerozsáhlé vstupní/výstupní operace. Dvojkové desítkové zobrazení (BCD – Binary Coded Decimal) má vlastnosti opačné. Složitější aritmetické výpočty jsou časově i prostorově neefektivní a programátorsky náročné, zatímco převod na znakové zobrazení je snadný a efektivní. To předurčuje požití tohoto zobrazení pro hromadné zpracování dat (HZD), které je charakteristické vysokým počtem vstupních/výstupních a relačních operací a jen nenáročnými a nepočetnými aritmetickými operacemi. 62 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Základem binárních zobrazení je zobrazení v pevné řádové čárce (fix-point representation). V minulosti to bylo univerzální zobrazení pro veškeré numerické hodnoty, nyní se s ním setkáváme jako s typem „integer― v jazycích Fortran, Algol, Pascal, Basic apod. Toto zobrazení je základem pro zobrazení v pohyblivé řádové čárce (floating-point representation), které známe ve výše uvedených jazycích jako typ „real― resp. „double precision―. Zvláštním případem binárního zobrazení je typ „Boolean― resp. „logical―. Středem druhé skupiny je zobrazení BCD, kterému se také říká zhuštěné desítkové zobrazení (packed decimal). V tomto zobrazení je každá desítková číslice desítkového čísla reprezentovaná binární hodnotou na čtyřech bitech a informaci o znaménku nese poslední, nejpravější čtveřice bitů. Přechodným zobrazením při převodu zhuštěného na znakové zobrazení a zpět je tzv. rozvinuté desítkové zobrazení (unpacked decimal), které se od znakového zobrazení liší pouze vyjádřením znaménka, které v rozvinutém zobrazení netvoří samostatný znak.

5.2.1 Číselné soustavy, vzájemné převody čísel mezi číselnými soustavami Nechť přirozené číslo z >1 je základem dané číselné soustavy a nechť ai (pro i   ,  ) je přirozené číslo, pro které platí 0  ai  z . Pak libovolnou kladnou číselnou hodnotu lze vyjádřit polynomem (5.1) am z m  am1z m1   a1z  a0  a1z 1  a n z  n , koeficientům ai říkáme číslice a pro číselnou hodnotu používáme zkrácený zápis

amam1

a1a0  a1

a n

,

(5.2)

kde tečka (nebo čárka) odděluje koeficienty u nezáporných mocnin základu (celá část čísla) od koeficientů u záporných mocnin základu (necelá část čísla). V paměti počítače jsou číselné hodnoty zobrazeny pomocí dvojkové soustavy, což souvisí se snadnou fyzikální realizovatelností dvoustavové veličiny a s možností využití Boolovy algebry pro realizaci různých operací nad čísly. Číslice dvojkového (binárního) čísla mají hodnotu 0 nebo 1 a nesou informaci o 1 bitu. Číslo v soustavě o základu zk, kde z i k jsou přirozená čísla, lze jednoduše převést do soustavy o základu z tak, že každý koeficient ai výchozího čísla nahradíme k-ticí koeficientů k-1bi …1bi0bi takovou, aby číslo k-1bi …1bi0bi v soustavě o základu z se rovnalo hodnotě číslice ai v soustavě o základu zk. Z toho vyplývá i obrácený převod, v němž se každá k-tice číslic v soustavě o základu z nahradí číslicí ekvivalentní hodnoty v soustavě o základu zk. Této vlastnosti se využívá pro snadný převod mezi soustavou o základu 2 a soustavami o základu 8 a 16. V případě šestnáctkové soustavy používáme pro čísla 10, 11, 12, 13, 14, 15 písmena A, B, C, D, E, F. Soustava o základu 63 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

2 000000 000001 000010 000011 000100 000101 000110 000111 001000 001001 001010 001011 001100 001101 001110 001111 010000 010001





32

100000





64

1000000

8 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21



16 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11



40



20

 100

40

Uvedené vlastnosti bohužel nelze využít pro nejdůležitější převod, a to pro převod mezi desítkovou soustavou a ostatními soustavami. Pro takový převod se používá dvou následujících univerzálních algoritmů, z nichž první převádí celou část čísla a druhý necelou část čísla. Výsledné číslo vznikne spojením obou výsledků při využití oddělovače celé a necelé části. Algoritmus pro převod celé části do soustavy o základu z: i := 0 { Řád vytvořené číslice čísla do soustavy o základu z } číslo := celé číslo bez znaménka; { číslo je typu integer } základ := z; while číslo  0 do begin číslice [i]:=číslo mod základ ; číslo :=číslo div základ; i :=i+1; end; { V poli číslice[0]až číslice [n]jsou uloženy hodnoty číslic výsledného čísla v obráceném pořadí } 64 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Algoritmus pro převod necelé části čísla do soustavy o základu z číslo := necelá část čísla ;{ číslo je typu real } základ :=z ; for i := i to požadovaný počet míst do begin součin := číslo * základ ; { součin je typu real } číslice i := trunc (součin); číslo := součin – číslice[i]; end ; { V poli číslice[i]až číslice [požadovaný počet míst] jsou vloženy hodnoty číslic necelé části výsledného čísla v přímém pořadí.} Příklad na ruční převod čísla z desítkové soustavy do soustavy o základu 2, 8 a 16. Dané číslo 473.4 rozdělíme na celou a necelou část, s každou z nich převedeme zvlášť. 473 : 8 Podíl zbytek 59 7 0

1 3 7

[0] [1] [2]

číslice

(473)10 = (731)8 0.4

*8

číslice [1] číslice [2] číslice [3]

3 1 4 6

2 6 8 4

číslo : = součin – číslice [1] (0.4)10  (0.314)8

Výsledkem je (473.4)10 = (731.314)8 Pro převod do dvojkové soustavy stačí nahradit každou osmičkovou číslici trojicí dvojkových číslic. Číslo: (731.314)8 = (111 011 001  011 001 100)2. (1 1101 1001  0110 0110 0)2 Převod z dvojkové soustavy do šestnáctkové se provede náhradou jedné šestnáctkové číslice za čtveřici dvojkových míst. Čtveřice vytváříme od řádové tečky nalevo a napravo. Chybějící číslice doplníme nulami. (0001 1101 1001



0110 0110 0000)2 = (1D9.660)16 .

(5.3)

Ruční převod do desítkové soustavy se dělá běžnými metodami pro vyčíslení hodnoty polynomu (např. Hornerovým schématem) nebo pomocí tabulek mocnin čísla 2. 65 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


5.2.2 Zobrazení dvojkového čísla v počítači, rozsah čísel, přesnost zobrazení Zobrazení dvojkového čísla v počítači závisí na velikosti nejmenší adresovatelné jednotky paměti – paměťové buňky. Standardní typy čísel bývají zobrazeny na celém prostoru jedné nebo několika paměťových buněk. Velikost paměťového prostoru pro zobrazení čísla přímo souvisí s rozsahem zobrazitelných čísel, případně i s přesností zobrazení. Rozsahem zobrazení se rozumí interval omezený zleva nejmenším a zprava největším zobrazitelným číslem. Tento interval vymezuje definiční obor čísel, se kterými může počítač pracovat. Výsledky aritmetických operací, které nespadají do definičního oboru, vedou k chybovým stavům. Přesnost zobrazení se používá u zobrazení necelých čísel a definuje se maximálním počtem číslic (např. desítkových), kterými lze zobrazované číslo vyjádřit. S ní souvisí i hodnota nejmenšího kladného nenulového čísla, které lze v počítači zobrazit, a která představuje rozlišitelnost zobrazení. Stává se, že požadujeme výstup čísla s menší přesností, než jakou poskytuje zobrazení. Například postačuje-li tisk necelého čísla s přesností na dvě desetinná místa, ačkoliv zobrazení poskytuje přesnější vyjádření. Základním typem zobrazení je zobrazení celých čísel (integer) a zobrazení desetinných čísel (real). Rozsah zobrazení celých čísel je dán počtem bitů n a je vymezen intervalem 0, 2n  1 , zobrazujeme-li jen kladná čísla, a intervalem  2n 1, 2n 1  1 zobrazujeme-li kladná i záporná čísla. Desetinná čísla jsou v paměti zobrazena dvojicí čísel – mantisou a exponentem. Typy zobrazení desetinných čísel na různých počítačích se mohou lišit hodnotou základu u exponentu, kterou bývá vždy celá mocnina čísla 2. Rozsah zobrazitelných čísel typu real je vymezen intervalem   z maxexponent , z maxexponent  , kde z je použitý základ zobrazení necelých čísel. Rozlišitelnost je řádově dána výrazem

z

 maxexponent

 . Přesnost zobrazení je dána počtem bitů mantisy.

Např. zobrazení „double precision― se od zobrazení „real― liší větším (přibližně dvojnásobným) počtem bitů mantisy. Na n-bitovém prostoru lze vytvořit 2n různých kombinací jedniček a nul. Interpretujeme-li tyto kombinace jako kladná dvojková čísla, pak lze zobrazit čísla v rozsahu 0, 2n  1 . Otázkou je jak využit těchto možností pro zobrazení jak kladných tak záporných čísel. 5.2.3 Přímý kód (Signed magnitude) Přímý kód je nejběžnější způsob zobrazení záporných čísel předpočítačové éry. Zvláštní dvouhodnotová předpona, nazývaná znaménko, udává polaritu zbývající části zobrazení, která měla tvar absolutní hodnoty. Zavedeme-li konvenci, že 0 na místě předpony odpovídá znaménku „  ― a 1 odpovídá znaménku „  ―, dostaneme situaci znázorněnou na obr. 5.1 pomocí číselné osy.



Obr. 5.1. Graf přímého kódu. Z obr. 5.1 je vidět, že kladná čísla, která mají první (znaménkový) bit nulový, mají definiční obor vzoru i obrazu stejný  0,2n1  1 a rostou ve smyslu symbolického klínu, zleva doprava.

Vzorový definiční obor záporných čísel  2n1,0  je zobrazen do obrazového definičního oboru

2

n1

,2n  1 , a to obráceným způsobem, tzn. že v doméně obrazu roste hodnota čísel zprava

doleva. Přímý kód má dvě nulové hodnoty - „ kladnou― a „zápornou― nulu, které se liší znaménkovým bitem. Ostatní bity jsou nulové. 5.2.4 Inverzní kód (One’s complement) Inverzní kód je založen na myšlence, že 2n různých kombinací lze mezi kladná a záporná čísla zobrazit tak, že každému kladnému číslu bude odpovídat jeho záporná hodnota v doméně obrazu ve tvaru „negativu―, inverze. Situaci znázorňuje obr. 5.2.

Obr. 5.2. Graf inverzního kódu Na tomto obrázku je vidět, že od přímého kódu se inverzní kód liší tím, že vzorová doména záporných čísel se do obrazové domény zobrazuje přímo, tzn. že v obou doménách roste hodnota čísel zleva doprava. Inverzní kód má také dvě nulové hodnoty, které jsou vzájemně inverzní. „Kladná― nula sestává z n nul, zatímco „záporná― nula sestává z n jedniček. Pojem inverze se označuje operace, která invertuje každý z bitů čísla. Výsledkem je hodnota záporná k původní hodnotě.

5.2.5 Doplňkový kód (Two’s complement) 67 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Doplňkový kód je založen na myšlence, že k dané hodnotě se vytvoří odpovídající záporná hodnota v obrazové doméně ve formě doplňku do hodnoty z m ( kde z je základ soustavy a m je maximální počet číslic). Obraz záporného čísla k danému číslu nutno přičítat, abychom dostali hodnotu z m . Např. pro z  10 , m  1 , tedy u jednomístného desítkového čísla, lze interval (0, 9) rozdělit v doplňkovém kódu tak, že interval (0, 4) představuje obrazový i vzorový obor kladných čísel a obrazový interval (5, 9) odpovídá vzorovému intervalu (-5, -1), tzn. že obrazem čísla -5 je číslo 5, obrazem čísla -4 je číslo 6 atd. Situaci dvojkového doplňkového kódu znázorňuje obr. 5.3.

Obr. 5.3. Graf dvojkového doplňkového kódu A rozdíl od obou předcházejících kódů má dvojkový doplňkový kód jen jednu nulu. Zbývající lichý počet nenulových čísel se dělí tak, že záporných čísel je o jedno číslo více. Je to nejzápornější číslo a v definičním oboru neexistuje jeho absolutní hodnota. Srovnáme-li obrazovou doménu záporných čísel v doplňkovém a inverzním kódu (domény kladných čísel jsou v obou kódech identické), pak zjistíme, že obraz ve tvaru n jedniček odpovídá hodnotě 1 v doplňkovém kódu a nule (záporné) v inverzním kódu. Z toho vyplývá významný důsledek pro tvorbu doplňku (který podobně jako inverze v inverzním kódu, slouží k vytvoření záporně vzaté hodnoty). Doplněk k danému číslu (jeho záporně vzatá hodnota), který by se musel vytvářet na základě odečítání od hodnoty 2n , lze vytvořit pomocí inverze, ke které se přičte jednička k nejnižšímu bitu m1 5.2.6 Kód transformované nuly (Excess 2 code)

Kód transformované nuly vychází z myšlenky lineárního posunu počátku číselné osy v doméně obrazu viz obr. 5.4.



Obr. 5.4. Graf kódu transformované nuly. U všech předcházejících kódu se doména vzoru i obrazu pro kladná čísla se shodovaly. V případě kódu transformované nuly platí u všech čísel transformační vztah Hodnota obrazu = Hodnota vzoru  2n-1 . Pro obecný kód transformované nuly (se symetrickou nulou) platí Hodnota obrazu = Hodnota vzoru  z m / 2 , kde z je základ soustavy a m je počet číslic. Vzorový interval je potom   z m / 2, z m / 2  1 .

5.3 Zobrazení znakové informace, kódy ASCII a EBCDIC Člověk je zvyklý číst a opticky zpracovávat informaci, která je zobrazena jako řetězec znaků používané abecedy. Zobrazení číselné informace má nejčastěji tvar řetězce číslic s možnou předponou znaménka a s možným oddělovačem celé a desetinné části čísla. Slova mluveného jazyka zobrazujeme řetězcem písmen dané abecedy, abstraktním pojmům přiřazujeme symbolické identifikátory ve tvaru řetězců zvolených znaků abecedy při zachováni stanovených pravidel. Některé z těchto objektů nohou mít v paměti počítače jiné, tzv. vnitřní zobrazení, které je výhodnější pro efektivní zpracování informace počítačem. Pro styk počítače s člověkem je však základním zobrazením informace znakové zobrazení, v němž je každému znaku slova, čísla atd. jednoznačně přiřazena celočíselná hodnota - kód. Daný znakový kód úzce souvisí s konstrukcí vstupních a výstupních zařízení. Vstupní zařízení nebo zařízení pro pořizování vstupních dat transformují znakovou informaci (např. stisknuti klávesy označené znakem) na kód znaku a naopak výstupní zařízení (tiskárna, obraz. display) transformují obdržený znakový kód na znak zobrazitelný na výstupním médiu. Pro efektivní zpracováni informace se požadují některé zvláštní vlastnosti znakových údajů, z nichž nejčastějšími jsou: a) Lexikální uspořádání kódů abecedy, které požaduje, aby znaku, jehož pořadí v abecedě je nižší než pořadí jiného znaku, odpovídala i nižší hodnota znakového kódu. Tato vlastnost významně zvyšuje efektivnost abecedního třídění a vyhledávání. b) Uspořádání kódů desítkových číslic takové, aby zbytek po dělení tohoto kódu vhodným celým číslem (nejčastěji 16) byl roven hodnotě zobrazované číslice. Tato vlastnost má význam pro efektivní transformaci znakového tvaru číselných hodnot do jejich vnitřní reprezen69 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


tace. Např. čtyři nižší bity osmibitového kódu číslic jak v kódu ASCII tak v EBCDIC reprezentuji dvojkovou hodnotu, která je rovna hodnotě kódované číslice. Textová informace se zobrazuje pomocí posloupnosti znaků, které se říká textový řetězec. Nejčastějšími operacemi nad řetězci znaků jsou slučování (konkatenace) dvou, nebo více řetězců do jednoho řetězce, rozdělení jednoho řetězce na dva, nebo více řetězců a lexikální relace dvou řetězců, která určuje, zda jsou dva řetězce ekvivalentní, nebo zda je jeden řetězec menší, než druhý‚ (tzn. že při abecedním řazení by byl menší řetězec zařazen před druhý). Soubor znaků pro vstup a výstup informace do nebo z počítače zpravidla zahrnuje 26 písmen latinské abecedy, 10 arabských číslic, určitý počet speciálních znaků a znaky interpunkční. I když není úplná standardizace povolených znaků bez ohledu na typ počítače prakticky možná, existují standardizované soubory – kódy, které se používají pro různé typy počítačů. K nejrozsáhlejším patří kód ISO definovaný mezinárodní organizací pro standardizaci (International Standards Organization) a jeho americká varianta kód ASCII (American Standard Code for Information Interchange), případně kód EBCDIC (Extended Binary Coded Decimal Interchange Code). Kód ASCII obsahuje 128 znaků. Protože 128 = 27, je každý znak tohoto kódu reprezentován jednoduchou kombinací 7 bitů (dvojkových číslic). Zobrazení množiny znaků na množinu sedmic bitů se nazývá sedmibitový kód. Pro znaky kódu ASCII je toto zobrazení uvedeno v tab. 5.1. Poznamenejme, že slovo kód má tedy dva významy: Soubor znaků, jež jsou prvky určité standardizované množiny znaků a reprezentace (kódování) znaků prostřednictvím n-tic bitů. Znaky kódu ASCII lze rozdělit do dvou skupin – na tisknutelné znaky a řídící znaky. První skupina zahrnuje velká a malá písmena, číslice a speciální znaky jako závorky, interpunkční znaménka, operátory apod. (V případě absence malých písmen mluvíme o omezeném ASCII kódu.). Základní funkcí řídících znaků je poskytnout řídící informaci zařízením, které jsou určena ke zprostředkování přenosu dat. např. znaky lf (line feed = nový řádek) řídí posuv papíru v tiskárně a tisk od počátku řádku a cr (carriage return = návrat vozíku) atd. S reprezentací znaků dvojkovými čísly úzce souvisí dvě převodní funkce. V jazyce Pascal to jsou funkce ord(z) a chr(i), které popisují zobrazení množiny znaků na množinu přirozených čísel a naopak. Pro kód ASCII jsou definovány takto: Ord(z) je tzv. ordinální (pořadové) číslo v uspořádané množině znaků. Podle tab. 5.1 můžeme ordinální číslo znaku z vypočítat ze vztahu ord ( z )  16* x  y

(5.4)

kde x a y jsou souřadnice znaku z v tab. 5.1. Chr(i) je znak, jehož ordinální číslo je i.


INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ Moderní technologie ve studiu aplikované fyziky CZ.1.07/2.2.00/07.0018 0

1

0

nul

dle

1

soh

dc1

2

stx

3

2

3

4

5

6

7

0

@

P

!

1

A

Q

a

q

dc2

―

2

B

R

b

r

etx

dc3

#

3

C

S

c

s

4

eot

dc4

$

4

D

T

d

t

5

enq

Nak

%

5

E

U

e

u

6

ack

Syn

&

6

F

V

f

v

7

bel

Etb

‚

7

G

W

g

w

8

bs

Can

(

8

H

X

h

x

9

ht

Em

)

9

I

Y

i

y

10

lf

Sub

*

:

J

Z

j

z

11

vt

esc

+

;

K

[

k

{

12

ff

fs

‚

<

L

\

l

|

13

cr

qs

-

=

M

]

m

}

14

so

rs

.

>

A

^

n

15

si

us

/

?

O

_

o

p

del

Tab. 5.1. Tabulka znaků kódu ASCII (American Standard Code for Information Interchange) Protože původní funkce chr je inverzní vzhledem k původní funkci ord a naopak, platí:

chr ord  z    z a ord  chr i    i

(5.5)

Uspořádání na množině znaků je definováno funkcí ord takto: Nechť z1 a z2 jsou znaky. Relace z1 < z2 platí právě tehdy, když ord (z1) < ord (z2). Příklad znaky A, B: ord (A) = 16*4+1 = 65; ord (B) = 16*4+2 = 66; B > A Kódu EBCDIC (Extended Binary Coded Decimal Interchange Code) se používá zejména u velkých sálových počítačů. Každý ze znaků kódu je reprezentován 8 bity a je proto možné zobrazit v tomto kódu 256 znaků. Tabulka kódu EBCDIC je uvedena v tab. 5,2. Kód EBCDIC nepřiřazuje každé 8-bitové kombinaci určitý znak (existují kombinace, jenž žádný znak nevyjadřují). Pro kód jsou významné tyto vlastnosti: Vyjádříme-li jednotlivé dvojkové reprezentace znaků čísly 0-255, potom interval čísel vyjadřujících číslice je souvislý, čísla zobrazující řídící znaky < čísla zobrazující znaménka a malá písmena < čísla zobrazující velká písmena < čísla zobrazující číslice.


INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ Moderní technologie ve studiu aplikované fyziky CZ.1.07/2.2.00/07.0018 Pravá číslice Levá

0

1

2

3

4

6

mezera

7

0

8

&

9

!

$

>

?

5

6

7

8

9

.

<

(

+

I

-

/

*

)

;

:

#

@

‚

=

„

d

e

F

g

h

i

j

k

v

w

10 11 12 13

b

c

14 15

o

p

16

q

r

s

t

U

17 18

[

A m

A

x

y

Z

\

{

}

F

G

]

19 20

H

I

21

K

L

M

A

B

C

D

E

N

O

P

Q

R

S

T

U

V

6

7

8

9

22 23

W

X

Y

Z

24

0

1

2

3

4

5

Tab. 5.2. EBCDIC (Extended Binary Coded Decimal Interchange Code)-tisknutelné znaky. Kódy 00-63 reprezentují netisknutelné řídící znaky Př: Písmeno „A― = 19 / 3; 10011 / 011; 128+0+0+16+8+0+2+1 = 155. U zařízení výpočetní techniky se používá dále i odvozených kódů. Např. kód KOI-8 čs (Kód dlja obměna i obrabotki informacii) je odvozen z kódu ASCII a je doplněn o další znaky (např. písmena s háčky a čárkami aj.), kód DKOI (Dvojičnyj kód dlja obměny i obrabotki informaci) je obdobným odvozením kódu EBCDIC.

5.4 Zobrazení instrukcí v paměti Program v paměti počítače sestává z posloupnosti instrukcí. Instrukce je pokyn k provedení jisté operace. Typ operací a tudíž i instrukcí závisí na konstrukci počítače, a proto se mohou soubory instrukcí odlišných typů počítačů značně lišit. Rozdílný bývá i způsob zobrazení 72 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


instrukcí v paměti. Programovacím jazykům, které odrážejí specifické vlastnosti konkrétního počítače proto říkané strojově orientované jazyky. Paměťový prostor, který zaujímá zobrazení instrukce se co do velikosti nuže lišit jak podle typu počítače, tak podle typu instrukce. Slovně orientované počítače mívají všechny instrukce zobrazeny na n bitech svého slova a nají tedy instrukce o pevné délce. Paměťová jednotka bytové orientovaných počítačů 1B nestačí pro zobrazení jedné instrukce a proto instrukce těchto počítačů bývají zobrazeny na 2, 4 nebo 6 bytech paměti. Tyto počítače mají instrukce o různých délkách, a proto hovoříme o instrukcích s proměnnou délkou. Nejvýznamnějšími složkami zobrazení instrukce je kód instrukce (kód operace) a adresa. 5.4.1 Kód instrukce Kódem instrukce se rozumí přirozené číslo z intervalu (0, 2m - l), které je jednoznačně přiřazeno každé operaci daného počítače. Kód, který je zobrazen na m bitech umožňuje rozlišit 2m různých operací. 5.4.2 Adresy instrukce Podle počtu operandů nazýváme operace s jedním operandem monadickými a se dvěma operandy dyadickými. Operand strojové instrukce může být umístěn v paměti počítače nebo v registru. Určení registru s operandem může být implicitní (registr je určen přímo kódem instrukce) nebo explicitní (jeden z několika registrů je určen pořadovým číslem - adresou registru). Operand v paměti je určen adresou paměťové buňky (je-li na ní uložen celý) nebo adresou první paměťové buňky v posloupnosti buněk (bytů, slov) - je-li zobrazen na více po sobě jdoucích buňkách. Podle toho zda instrukce nemá žádný operand v paměti, či má jeden nebo dva operandy v paměti, hovoříme o bezadresové, jednoadresové či dvouadresové instrukci. Každý operand v paměti vyžaduje samostatný přístup do paměti a každému přístupu do paměti odpovídá vybavovací doba paměti. Bereme-li v úvahu operandy zobrazené na stejně velkém prostoru v paměti, pak počtu operandů v paměti je přímo úměrná doba potřebná pro provedení instrukce (execution time). 5.4.3 Typy a struktura adresy Adrese, která je součástí zobrazení instrukce, se říká vnitřní adresa instrukce. Vnitřní adresa může být jednoduchá nebo složená. Jednoduchá adresa je reprezentována přirozeným číslem zobrazeným na vyhrazeném prostoru zobrazeni instrukce a odpovídá adrese operandu v paměti. Složená adresa sestává se z několika komponent. Nejčastějšími komponentami jsou: jednoduchá adresa, obsah indexregistru a obsah bázového registru. Výsledné hodnotě adresy, která je 73 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


adresou operandu v paměti a která se získá součtem použitých komponent, se říká efektivní adresa. Řád adresy je délka zřetězené posloupnosti adres, na něž se postupně odkazuje, aby se získal operand. Adresa nultého řádu se obvykle nazývá přímý operand (immediate operand) a znamená to, že sama hodnota adresy je hodnotou operandu. Pro získání operandu byl zapotřebí nulový počet adres - posloupnost adres byla prázdná. Adresa prvého řádu je hodnota adresy panelového místa, na němž je uložen operand. Pro získání operandu je zapotřebí jedné adresy. Adresa, která odkazuje na operand se říká také přímá adresa (direct address). Adresa operandu však může být sama uložena na určitém paměťovém místě. Adrese, která odkazuje na místo v paměti, na němž je uložena adresa (a ne operand) se říká nepřímá adresa (indirect address). Adresa druhého řádu je nepřímá adresa, která odkazuje na místo v paměti, na němž je uložena přímá adresa. (K získání operandu je zapotřebí dvou adres a tudíž i dvou přístupů do paměti.) Adresa n-tého řádu (n > l) vytváří zřetězenou strukturu n -1 nepřímých adres a jedné adresy přímé, která je ve zřetězeném lineárním seznamu poslední. Pro získání operandu je zapotřebí n adres a n přístupů do paměti. Přímá adresa bývá od nepřímé odlišena dvoustavovým příznakem, který bývá realizován jedním bitem, který je součástí adresy. Pro práci s adresou a jejím obsahem zavedeme zápis = obsah adresy.

Obr. 5.5. Zobrazení instrukce



6. ARITMETIKA VE DVOJKOVÝCH KÓDECH Základní aritmetickou operací je součet. Součin lze realizovat opakovanými součty. Je-li součet definován pro kladné i záporné sčítance, lze rozdíl realizovat přičtením záporné vzatého menšitele. Pomocí opakovaného rozdílu lze vytvořit podíl a sdružený zbytek (modulo) po celočíselném dělení. (Celočíselný podíl a operace modulo vznikají vždy současně.) Správný výsledek aritmetické operace musí spadat do definičního oboru zobrazovaných čísel. Jestliže je výsledek větší než pravá hranice definičního oboru zobrazitelných čísel, dochází k tzv. přetečení (overflow). Opak přetečení, kdy je výsledek menší než levá hranice definičního oboru se říká podtečení (underflow). (Při obou typech přetečení má součet v inverzním i doplňkovém kódu obrácenou polaritu.) Součet C : A  B dvou čísel v doplňkovém kódu, kde výsledek C je definován bity Cn1 C0 a sčítance A a B bity An1 A0 , Bn1 B0 , probíhá podle algoritmu: přenos := 0; for i := 0 to n-1 do begin C[i] := (A[i] + B[i] + přenos ) mod 2 ; přenos := (A[i] + B[i] + přenos ) div 2 ; if i = n-2 then přenos do zn. bitu := přenos; end; Přetečení := přenos do zn. bitu  přenos; {Přetečení je typu Boolean} Slovy lze algoritmus v doplňkovém kódu shrnout takto: Při součtu odpovídajících si bitů může vzniknout přenos, který se uplatní při součtu nejblíže vyšší dvojice bitů. Vznikne-li při součtu dvou čísel přenos ze znaménkového bitu (přenos ze součtu nejvyšší dvojice bitů) – ignoruje se. Nonekvivalence přenosu do a ze znaménkového bitu definuje stav přetečení součtu. Při součtu v inverzním kódu je v určitém případě nutné provést korekci výsledku pomoci tzv. kruhového přenosu. Inverzní kód má dvě nuly, zápornou a kladnou, přičemž kladná nula je l větší než záporná. Jestliže je jeden ze sčítanců záporný a výsledek Je kladný, nebo jsou-li oba sčítance záporné, je výsledek o l menší. Protože právě v těchto případech vzniká přenos ze znaménkového bitu, je signálem k provedení korekce výsledku přičtením jedničky. Tomuto přenosu se pro jeho aplikaci na nejnižší bit výsledku říká kruhový. Situaci ilustruje přiklad, kdy k záporné nule na 16-ti bitovém slově se přičítá jednička: (- 0) +1

=1

1 111 111 111 111 111 0 000 000 000 000 001 1 0 000 000 000 000 000 +1 0 000 000 000 000 001 75



Pak tedy k algoritmu součtu v doplňkovém kódu stačí přidat if not přetečení then begin i := 0 ; while přenos  0 do begin C[i] := (C [i] + přenos) mód 2 ; přenos := (C[i] + přenos) div 2 ; i:= i + l ; end ; end ; Přiklad: Zobrazme čísla 7 a 3 na 16-ti bitovém slově a proveďme operace 3+7, 7-3, 3-7 a -3-7 v inverzním i doplňkovém kódu. ČÍSLO 3 -3

INVERZNÍ KÓD 0 000 000 000 000 011 1 111 111 111 111 100

DOPLŇKOVÝ KÓD totéž jak inv. kód 1 111 111 111 111 101

7 -7 Očekávané hodnoty 4 -4 10 -10 výpočet 3+7 3 +7 = 10

0 000 000 000 000 111 1 111 111 111 111 000

totéž jak inv. kód 1 111 111 111 111 001

0 000 000 000 000 100 1 111 111 111 111 011 0 000 000 000 001 010 1 111 111 111 110 101

totéž jak inv. kód 1 111 111 111 111 100 totéž jak inv. kód 1 111 111 111 110 110

0 000 000 000 000 011 0 000 000 000 000 111 0 000 000 000 001 010

totéž jak inv. kód

výpočet 7-3 = 7+(-3) 7 0 000 000 000 000 111 +(-3) 1 111 111 111 111 100 1 0 000 000 000 000 011 +1 0 000 000 000 000 100 (410) výpočet 3-7 = 3+(-7) 3 0 000 000 000 000 011 +(-7) 1 111 111 111 111 000 1 111 111 111 111 011 (- 410)

0 000 000 000 000 111 1 111 111 111 111 101 1 0 000 000 000 000 100 (410)

0 000 000 000 000 011 1 111 111 111 111 011 1 111 111 111 111 100 (-410)



výpočet -3-7 = (-3)+(-7) (-3) 1 111 111 111 111 100 +(-7) 1 111 111 111 111 000 1 1 111 111 111 110 100 +1 1 111 111 111 110 101 (-1010)

1 111 111 111 111 101 1 111 111 111 111 001 1 1 111 111 111 110 110 (-1010)

Při násobení dvou celých čísel zobrazených v paměti je nutné si uvědomit, že součin bude vyžadovat prostor dvakrát větší než jeden činitel. Výsledný součin může snadno překročit meze definovaného oboru zobrazení. V počítači se dvojnásobný prostor pro součin zajišťuje nejčastěji spojením dvou registrů typu střadač. Protože následnou operací (např. dělením) se často "přetečený" součin jako mezivýsledek - vrátí do definovaného oboru zobrazení, nesignalizuje přetečení součinu vždy nepodmíněný chybový stav. Ve dvojnásobném prostoru je pak znaménkovým bitem nejlevější bit levého registru. Operace dělení se většinou definuje komplementárně k násobení, a proto se předpokládá, že dělenec je uložen ve dvojnásobném prostoru. Programátor pak musí podle polarity dělence o jednonásobné délce, který je uložen v pravém registru, nastavit správně levý registr na samé nuly (+) nebo samé jedničky (-). Všimněme si, že "nevýznamné" nuly zleva u kladných čísel nají obdobu v "nevýznamných" jedničkách zleva u záporných čísel v doplňkovém i inverzním dvojkovém kódu.

6.1

Zobrazení v pevné řádové čárce, typ integer

Až doposud jsme předpokládali, že v paměti počítače se zobrazují jen celá čísla. Řada aplikací vyžaduje také zobrazení necelých čísel, čísel v absolutní hodnotě menších než l nebo čísel větších, než je celočíselný rozsah daného zobrazení. Pro tyto případy se zavádí pojem pevné řádové čárky a měřítka. Pevnou čárkou se rozumí takové zobrazení, které pracuje s necelými čísly v dané číselné soustavě s daným počtem číslic a se stanovenou pozicí řádové čárky (tečky) - nejčastěji za první číslicí (ve dvojkových kódech za znaménkovým bitem). Interval zobrazovaných čísel pak bývá vymezen nerovností 1  x  1 . Měřítko je myšlený exponent u základu dané soustavy; základem s tímto exponentem je třeba násobit číslo v doméně obrazu, aby se získala hodnota vzoru. Snaha zobrazovat číslo s co nejmenším možným měřítkem vede k normalizovanému (normovanému) tvaru zobrazeného čísla a je vedena cílem zachovat co největší přesnost (počet platných míst) zobrazovaného čísla. Příklad: Číslo (5.5)10 = (101.l )2 lze zobrazit na 16-ti bitovém slově v pevné řádové čárce těmito způsoby: 0.101 100 000 000 000 s měřítkem e = 3 nebo 0.000 000 101 100 000 s měřítkem e = 9 77 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Pozn.: Trojúhelníčkem je označena pozice myšlené řádové čárky. Exponent je pak rozdílem pozice strojové řádové čárky a myšlené řádové čárky. Zvolíme-li pro toto číslo měřítko e = 16, ztrácí se při zobrazeni dvě nižší platná místa zobrazovaného čísla. 0.000 000 000 000 010 110 s měřítkem e = 16. Číslo s měřítkem e = 3 bylo normalizované. Podobně se pracuje s čísly menšími v absolutní hodnotě než l. Číslo (0.15625)10 = (0.00101)2 lze zobrazit např. takto: 0 0 0.101 010 000 000 000

s měřítkem

e = -2,

nebo 0.001 010 000 000 000 s měřítkem e = 0, nebo 0.000 000 000 000 101 s měřítkem

e = 10.

Číslo s měřítkem e = -2 je normalizované. Pro aritmetické operace s čísly v pevné řádové čárce platí tato pravidla: a) Sečíst se mohou jen dvě čísla se stejným měřítkem. Toto měřítko pak má i součet. U sčítanců s nestejnými měřítky se upravuje sčítanec s menším měřítkem zvětšením měřítka a příslušným posuven zobrazení doprava. (Posuv doprava je ekvivalentní operaci děleni základem soustavy.) b) Měřítko součinu je součtem měřítek obou činitelů. c) Měřítko podílu je rozdílem měřítka dělence a dělitele. Použití měřítek v pevné řádové čárce bylo historicky jediným způsobem pro vyjádření necelých čísel. Této techniky se používá i v současné době všude tam, kde pro práci s necelými čísly nelze aplikovat technickou ani programovou verzi zobrazení v pohyblivé řádové čárce. Typickými příklady jsou některé technické aplikace mikroprocesorů nebo aritmetické operace s BCD čísly na bytově orientovaných počítačích. Z pohledu zobrazení v pevné řádové čárce jsou čísla typu integer zobrazena s měřítkem e  n  1, kde n je počet bitů zobrazovacího prostoru. Příklady využití měřítka. C=|a|+|b| | a | = + (1.5)10 = (1.10)2 ~ 0.011 @2 ~ - 1.5 = 1.100 @2 | b | = + (2.5)10 = (10.1)2 ~ 0.101 @2 ~ - 2.5 = 1.010 @2



Výpočet v inverzním kódu + 1.5 + 2.5 +4 + 1.5 - 2.5 - 1

0.011 0.101 1.000 0.011 1.010 1.101

- 1.5 + 2.5 +1

1.100 0.101 1 0.001 +1 0.010 1.100 1.010 1 0.110 +1 0.111

- 1.5 - 2.5

-4

@2 @2 @2 ~ 100.00)2 (410) @2 @2 @2 ~ 110.1)2 (- 110) @2 @2 @2 @2 ~ (01.0)2 @2 @2 @2

(110)

@2 ~ (011.1) ~ (- 410)

Výpočet v doplňkovém kódu | a | = + (1.5)10 = (1.10)2 ~ 0.011 @2 ~ - 1.5 = 1.101 @2 | b | = + (2.5)10 = (10.1)2 ~ 0.101 @2 ~ - 2.5 = 1.011 @2 + 1.5 + 2.5

jako INV.

+ 1.5 - 2.5 - 1

0.011 @2 1.011 @2 1.110 @2

- 1.5 - 2.5

1.101 @2 1.011 @2 1 1.000 @2

Ignoruje se +4

6.2

1.000 @2

~ (- 110)

~ (+ 410)

Zobrazení v pohyblivé řádové čárce, typ real

Při práci s necelými čísly zobrazenými v pevné řádové čárce musel programátor sám manipulovat se zobrazeným číslem na základě znalosti měřítka, které samo nebylo předmětem 79 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


zpracování počítačem. Veškeré opravy čísla a změny měřítek určoval programátor v době tvorby progresu. Zobrazení v pohyblivé řádové čárce využívá všech principů uvedených pro práci s pevnou řádovou čárkou. Exponent se však stává součásti zobrazení a veškeré manipulace jsou zautomatizovány. Zobrazení čísla v pohyblivé řádové čárce je tvořeno uspořádanou dvojici - mantisou a exponentem. Základ soustavy může být pro různé počítače různý a pro dané zobrazení je implicitní. Nejčastějšími základy jsou 2. 8 a 16. Ve všech případech je mantisa zobrazena dvojkově, podle hodnoty základu však změna exponentu o jedničku znamená posun mantisy o l, 3 resp. 4 bity pro základ 2, 8 resp. 16. Číslo typu real, je definováno jako číslo v pohyblivé řádové čárce s normalizovanou mantisou. Mantisa má tvar čísla v pevné řádové čárce s měřítkem e = 0, exponent je číslo typu integer. Kladná normalizovaná mantisa má na jednom, třech či čtyřech bitech (pro základy 2, 8, 16) za strojovou řádovou čárkou nenulovou hodnotu. Většina současných počítačů určených pro vědecko-technické aplikace mají ve svém instrukčním repertoáru samostatnou skupinu aritmetických instrukcí pro práci s čísly typu reál. Počítače, které nemají takové instrukce, bývají vybaveny programovým vybavením, jež řeší tyto operace programově - skokem do odpovídajícího podprogramu. Uživatel se většinou nemusí zabývat otázkou. Jakým způsobem jsou zpracovávána čísla typu real. Výpočet pomocí "programové" pohyblivé řádové čárky je však výrazně pomalejší než výpočet pomocí "zabudované" či "strojové" pohyblivé řádové čárky. Každý programátor si však, zejména ve vyšším programovacím jazyku, musí uvědomit, že čísel typu reál používáme jen tam, kde je to nezbytně nutné, že aritmetika s typy reál je vždy pomalejší než celočíselná aritmetika, a to i v případě strojové pohyblivé čárky a že použití čísel typu reál s sebou vždy nese nebezpečí zaokrouhlovací (rounding) nebo osekávací (truncation) chyby, především při použití multiplikativních operaci. Řada numerických metod vyžaduje při programování důkladnou znalost konkrétního zobrazení typu reál a mnohé pracující programy složitějších numerických metod nemusí být vždy přenosné na jiný počítač v důsledku odchylek v zobrazení typu reál. Typickou neobratností nezkušených programátorů je použití relace rovnosti dvou hodnot typu reál. Rozdělíme-li např. interval (a, b) na n ekvidistantních části k, jejichž velikost je určena výrazem k:= (b-a)/a, není záruka, že n-násobné přičtení kroku k k dolní hranici bude rovno hodnotě b. Čísla typu double precision mají shodnou strukturu s čísly typu reál. Prodloužením mantisy na přibližně dvojnásobek se zvětší přesnost zobrazení necelého čísla, za cenu prodloužení doby potřebné pro provedení aritmetické operace. Důležitými operacemi pro zobrazení v pevné a pohyblivé řádové čárce je vzájemný převod obou zobrazení.

6.3

Zobrazeni logických hodnot, typ Boolean

Logické hodnoty potřebují pro své zobrazení jediný bit, jehož nulová resp. jedničková hodnota zobrazuje Booleovské hodnoty false a true. Typ Boolean nebo Logical používaný ve vyšších programovacích jazycích však bývá zobrazen na prostoru celé samostatně adresovatelné paměťové jednotky. Její nejsnadněji testovatelný bit bývá nositelem logické hodnoty. 80 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Rozsáhlé používání Booleovských hodnot může proto vést k neefektivnímu využití operační paměti.

7. ZÁKLADNÍ ARITMETICKÉ OPERACE Equation Chapter (Next) Section 7

7.1

Sčítání v polyadických soustavách

Běžně známé je sečítání ve dvojkové soustavě. Zde jen zdůrazněme, že číslice součtu vzniká sečtením stejnolehlých číslic obou sčítanců, přičemž vliv nižších řádů se respektuje přenosem (při dvou sčítancích jsou obvykle jen dvě možnosti: přenos 0 nebo přenos 1). Vliv vyšších řádů neexistuje. Tato vlastnost připomíná vlastnost konečného automatu: nepředpovídá. Skutečně, jestliže se ve dvou příkladech sčítání opakuje situace v nižších řádech, opakuje se i příslušná část výsledku. Druhá vlastnost automatového zobrazení: zachování délky, bývá vlastně též zajištěna. Sice platí, že součet může být o jeden řád delší než sčítanci (než delší ze sčítanců). Ovšem pevně vymezený formát nutí k zachování tohoto pravidla.7 V souladu s těmito pravidly lze hovořit o konečném automatu, realizujícím sčítání. Sériová sčítačka představuje pak realizaci tohoto automatu. Má dva vnitřní stavy respektující přenos, vstupní abeceda respektuje všechny možnosti, jak se může vyskytnout dvojice vstupujících číslic v obecném řádu, výstupní abeceda respektuje všechny možné číslice (z nichž je tvořen součet). Pro desítkovou sčítačku by tedy vstupní abeceda obsahovala celkem 102 písmen, kdežto vstupní jen deset. Sériová sčítačka obecně vypadá podle obr. 7.1.

Obr. 7.1. Blokové schéma sériové sčítačky v polyadické soustavě o základu z Je to sekvenční obvod se dvěma vnitřními stavy, jehož kombinační část K je schopna z číslic sčítanců (a přenosu) stanovit číslici součtu. Využívá se opakovaně pro číslice jednotlivých řádů, počínaje nejnižším, přechod k dalšímu řádu je uskutečněn přechodem k dalšímu taktu. Přenos do vyššího řádu se uplatní jako vstupující v témž bloku K, ovšem o tak později. V paralelní sčítačce je tolik kombinačních částí K, kolik je řádů sčítaných čísel. Pracují všechny současně. Zpráva o přenosu se nepřenáší do následujícího taktu, nýbrž do sousedního obvodu K, a to pokud možno bez zpoždění. Paralelní sčítačka je na obr. 7.2. Tlusté šipky zna-

7

Jde pak vlastně o sečítání při modulu rovném jedničce ve ztraceném řádu



čí vedení pro přesun jedné číslice při základu z. Na obr. 7.2b je vyznačena paralelní sčítačka blokově.

Obr. 7.2. Blokové schéma paralelní sčítačky pro polyadickou soustavu při základu z Tlusté šipky zde představují vedení pro přenos čísel (složených z mnoha číslic).

7.2

Odčítání v polyadických soustavách

Postup sčítačky je možno obměnit tak, aby mohla i odečítat. Vzhledem k tomu, že sčítačka respektuje stejnou délku vstupních i výstupních čísel, nedává na výstupu součet, nýbrž je to součet modulo M, kde M je číslo, o které je změněn výsledek v případě přeplnění. Např. desítková sčítačka pracující na dva řády dává při součtu 45+98 výsledek 43 místo správného 143. Modul M = 100. Příklad můžeme chápat jako součet 45 + (M-2) = 43. Říkáme, že (M-2) je obrazem záporného čísla (-2). Jde o zobrazení v doplňkovém kódu. Odečítání se pak převádí na přičítání obrazů čísel s opačným znaménkem. Má-li být sčítačka též užita k odčítání, je třeba, aby na jeden z jejich vstupů byl zařazen blok, který je schopen „obrátit znaménko―, tj. přicházející číslo nahradit jeho doplňkem schematicky podle obr. 7.3, ovšem jen v případě odečítání.

Obr. 7.3. Blokové schéma odečítání Blok A by měl vytvořit doplněk do M, kde M je obecně při soustavě o základu z rovno zn, kde n je počet řádů zpracovávaných ve sčítačce.8 Doplněk se tvoří tak, že v každém řádu se na8

Pro jednoduchost zde uvažujme řádovou čárku na pravém okraji čísel, tedy sčítání čísel celých.



hradí číslice svým doplňkem do čísla z-1 a k takto vzniklému číslu se přičte jednička v nejnižším řádu.

7.3

Násobení v polyadických soustavách

Násobení ve dvojkové soustavě, pokud nevyužívá prostředků ke zrychlení, je jednodušší než násobení v desítkové soustavě. Důležitým prostředkem ke zrychlování operace násobení je blok, realizující v podstatě „malou násobilku― zvaný násobící tabulka. Charakterizujeme jej jako obvod, kterým prochází číslo (násobenec) a při svém průchodu se změní na svůj k-násobek. Číslo k je malé číslo a lze je nastavit speciálním vstupem do uvažovaného bloku. Například naznačme provedení násobící tabulky pro dvojková čísla k = 0,1,2,3,4. Nechť je číslo k kódováno třemi bity k2 k1 k0. Použijeme-li paralelní dvojkovou sčítačku, do níž zavedeme číslo vhodně posunuté (násobené mocninou dvou) a popř. sečteme takto upravená čísla mezi sebou (jen v případě k = 3). Obvod je na obr. 7.4a. Místo hradel ve vstupních přívodech jsou jen u příslušných přívodů připsány ovládací proměnné, které umožní jejich průchodnost. Přehled o činnosti obvodu podává tabulka na obr.7.4b

Obr. 7.4. a) Násobící tabulka vytvořená z paralelní sčítačky; b) Zpracovávaná čísla a ve sčítačce v závislosti na požadovaném násobku k

7.3.1 Desítkové násobení Extrémně pomalý algoritmus. Kdybychom uměli jen sečítat a neznali další zákonitosti polyadických soustav, násobili bychom pomocí postupného přičítání. Na obr. 7.5a je příklad 102 x 912, kde první číslo je násobenec a druhé násobitel. Algoritmus s hustou násobící tabulkou. Algoritmus je uveden na příkladu 102 x 912 v obr. 7.5b. Využívá se okolnosti, že vyjádření čísla je váhové. Násobení devíti sty se zajistí vynásobením devíti a posunem o dva řády. 83 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


Obr. 7.5. a) Pomalý algoritmus násobení, b) algoritmus s hustou násobící tabulkou Součet většího počtu položek se provádí postupně, a to tak, že se vždy další položka přičítá k součtu všech dosavadních, který musí být uschován v registru. Jde tedy o střádání. Postup takového střádání je v příkladech naznačen vlevo. K realizaci prvního algoritmu v aritmetických obvodech by stačil prostý střadač. Pro druhý algoritmus potřebujeme mít možnost posuvů během střádání. Jako výhodné se ukázalo posouvat obsah registru střadače (vzhledem ke sčítačce). Tím se stane, že číslice některých řádů střadače „vyjdou ze záběru― se sčítačkou. Pokud jsou to číslice nižších řádů, nevadí to, protože se součtu nezúčastní teď ani v budoucnosti. Říká se jim také hotové číslice součinu. Na obr. 7.6 je naznačena varianta s posuvy střadače. Zde stačí zdvojnásobit šířku registru Z. Okolnost, že pravá polovina registru Z není v záběru se sčítačkou, je symbolicky naznačena rozštěpením výstupního vedení tak, že jeho část obchází sčítačku.

Obr. 7.6. Uspořádání sčítačky a registrů pro násobení. Varianta s posuvy částečného výsledku doprava. Nižší řády registru Z nejsou ve styku se sčítačkou. Pro ukázku si uveďme nejjednodušší algoritmus násobení (19*13 = 247) ve dvojkové soustavě. Svou rychlostí patří ke středě rychlým algoritmům.



Obr. 7.7. a) Dvojkové násobení, b) uspořádání aritmetické jednotky pro dvojkové násobení Obvody pro vypočtení příkladu jsou na obr. 7.7. Řádky v závorce představují výstup ze sčítačky. Ten se v témž taktu změní posuvem p (během přesunu do registru Z), takže nejbližší stav registru Z je vždy na následujícím řádku. Posuv během přesunu je ve schématu naznačen existencí vstupního vedení, odchýleného doprava.

Obr. 7.8. Pohyb číslic při dvojkovém násobení v aritmetické jednotce Řádky v závorce představují výstup ze sčítačky. Ten se v témž taktu změní posuvem (během přesunu do registru Z), takže nejbližší stav registru Z je vždy na následujícím řádku. Posuv během přesunu je ve schématu naznačen existencí vstupního vedení, odchýleného doprava.

7.4

Dělení v polyadických soustavách

Extrémně pomalý algoritmus by mohl být realizován obdobně jako v případě násobení, ale s postupným odečítáním. Dále by mohl být algoritmus s násobící tabulkou atd. Pro ukázku 85 Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.


nejjednoduššího algoritmu dělení ve dvojkové soustavě s restaurací nezáporného zbytku, je uveden příklad viz obr. 7.9.

Obr. 7.9. Algoritmus dělení ve dvojkové soustavě s restaurací nezáporného zbytku Znakem ξ je označen přechod do oblasti záporných zbytků a návrat (restaurace nezáporného zbytku).

LITERATURA [1] Klír. J., Seidl.: Syntéza logických obvodů. SNTL Praha, 1966. [2] Sekanina, L.: Návrh číslicových obvodů. FIT VUT Brno, 2002. [3] Eysselt, M.: Vybrané úlohy z logických systémů. VÚT Brno, 1993. [4] Blatný, J., Hlavička, J., Jindra,V.: Počítačové systémy. VA Brno, 1992.



Doc. Ing. Luděk Bartoněk, Ph.D. Informatika I. Struktura počítačů Výkonný redaktor: Prof. RNDr. Tomáš Opatrný, Dr. Odborný redaktor: Doc. RNDr. Roman Kubínek, CSc. Odpovědná redaktorka: Mgr. Jana Kreiselová Technický redaktor: Doc. Ing. Luděk Bartoněk, Ph.D. Určeno pro studenty, odbornou veřejnost a další zájemce. Vydala Univerzita Palackého v Olomouci Křížkovského 8, 771 47 Olomouc www.upol.cz/vup e-mail: [email protected] Olomouc 2012 1. vydání Oponent: Doc. Ing. Jiří Salinger, CSc. Tato publikace neprošla redakční jazykovou úpravou. © Luděk Bartoněk, 2012 Ediční rada — Skripta Online publikace ISBN 978-80-244-2973-1 http://fyzika.upol.cz/cs/predmety-kef-slo/informatika-1


INFORMATIKA I. (struktura počítačů) pro obor Aplikovaná fyzika

Recommend Documents