🖥️ BI-SAP – Struktura a architektura počítačů

🔢 Logická funkce a Booleova algebra

Logickou funkci lze vyjádřit více různými způsoby (tabulka, algebraický výraz, mapa, krychle). Hledáme takové vyjádření, které vede k nejlepší implementaci v dané technologii – proto hovoříme o minimalizaci popisu, nikoli o minimalizaci funkce samotné.

• Literál: proměnná nebo její negace (x, x̄, a, b̄, …)
• Minterm: součin všech n literálů – popisuje jeden vrchol krychle
• Implikant: krychle (podkrychle) f, jejíž všechny vrcholy jsou jedničkové (jsou v onsetu f)
• Onset f: množina {x | f(x)=1}
• Offset f: množina {x | f(x)=0}

📋 Formy popisu logické funkce a kanonické reprezentace

Stejná funkce může být zapsána nekonečně mnoha formulemi. Kanonická reprezentace zaručuje, že dvě ekvivalentní funkce mají totožný popis.

• Pravdivostní tabulka: Kanonická – jedinečně určuje funkci. Pro n proměnných má 2ⁿ řádků.
• Úplná DNF (ÚNDF / SOP – Sum of Products): Součet všech mintermů onsetu. Kanonická, ale obecně ne minimální.
• Minimální DNF (MNDF): Minimální součet součinů – nejmenší počet co největších implikantů pokrývající všechny jedničkové vrcholy.
• Úplná KNF (ÚNKF / POS – Product of Sums): Duální tvar – součin součtů pokrývající nulové vrcholy.
• Karnaughova mapa: 2D přepis n-rozměrné krychle, sousední políčka se liší jedním bitem (Grayův kód). Umožňuje vizuální minimalizaci.
• Stavový index (σ-zápis): q = σ(3, 5, 6, 7) – výčet indexů jedničkových mintermů

🗺️ Minimalizace v Karnaughově mapě (K-mapa)

K-mapa je grafická metoda hledání minimální normální disjunktivní formy (MNDF). Cílem je najít minimální počet co největších implikantů (smyček), které pokryjí všechny jedničkové vrcholy (onset).

Terminologie dvouúrovňové minimalizace:

• Přímý implikant (PI – Prime Implicant): Implikant, z jehož popisu nelze vypustit žádný literál, aniž by pokryl i nulový vrchol. Tedy největší možná „smyčka".
• Podstatný implikant (EPI – Essential Prime Implicant): Přímý implikant, který jako jediný pokrývá aspoň jeden jedničkový vrchol. Musí být v řešení.
• Neredundantní krychle: Pokrývá aspoň jeden vrchol, který žádná jiná krychle v pokrytí nepokrývá.
• Pokrytí (cover): Množina implikantů reprezentující funkci.

Algoritmus minimalizace (MNDF):

1. Najdi všechny přímé implikanty (PI)
2. Urči podstatné implikanty (EPI) – jsou povinné
3. Pokud EPI pokrývají všechny jedničky – hotovo
4. Jinak doplň minimální počet dalších PI pro pokrytí zbývajících jedniček

Realizace z hradel NAND / NOR: MNDF (SOP) se přirozeně realizuje z hradel NAND. MNKF (POS) z hradel NOR. Jak NAND, tak NOR tvoří úplný soubor logických funkcí – libovolnou funkci lze realizovat pouze z jednoho typu hradla.

🔌 Kombinační obvody – typické prvky v počítači

Základní hradla: AND, OR, NOT, NAND, NOR, XOR. Přičemž NAND i NOR jsou funkčně úplné samy o sobě (4 tranzistory CMOS).

Důležité kombinační bloky:

• Dekodér (1 z N): Binární kód na adresových vstupech aktivuje právě jeden z 2ⁿ výstupů. Realizace: každý výstup je minterm vstupních proměnných. Příklad: 2-vstupový dekodér → 4 výstupy y₀=x̄₁x̄₀, y₁=x̄₁x₀, y₂=x₁x̄₀, y₃=x₁x₀.
• Multiplexor (MUX): Vybírá jeden z datových vstupů na výstup podle selektoru. 4-1 MUX: y = s̄₁s̄₀d₀ + s̄₁s₀d₁ + s₁s̄₀d₂ + s₁s₀d₃. V CMOS realizace přenosovými hradly (6 tranzistorů pro 2-1 MUX).
• Demultiplexor (DEMUX): Inverzní k MUX – jeden vstup přepojuje na jeden z výstupů.
• Půlsčítačka (Half Adder): S = a XOR b; Přenos q = a · b. Bez vstupního přenosu.
• Úplná sčítačka (Full Adder): s = a ⊕ b ⊕ p; q = ab + p(a ⊕ b). Se vstupním přenosem p.
• Paralelní sčítačka (Ripple Carry Adder): Kaskáda full adderů. Přenos se šíří sériově – pomalé pro velké šířky.
• Sčítačka s předvídáním přenosu (Carry Look-Ahead): Predikuje přenosy paralelně. G=ab (generuje), P=a⊕b (šíří). q' = G' + P'·p'; Přenosy vyšších řádů se počítají přímo ze vstupů.
• Majoritní funkce M3: M3(c,b,a) = ab + ac + bc – výstup 1 když alespoň 2 ze 3 vstupů jsou 1.
• XOR: Výstup 1 pro lichý počet jedničkových vstupů. Realizace: 4× NAND = 16 tranzistorů; CMOS přenosová hradla = jen 6 tranzistorů.
• Barrel shifter: Kombinační obvod pro posuv o proměnný počet míst – kombinuje obvody pro různé posuvy a multiplexory. Rychlé, ale zabírá více plochy.

🔄 Sekvenční obvody – principy a model

Matematický model sekvenčního obvodu je konečný automat (FSM – Finite State Machine):

• X – množina vstupů
• Y – množina výstupů
• Q – množina vnitřních stavů
• Q₀ – počáteční stav (pro iniciální automat)
• δ: X × Q → Q – přechodová funkce (určuje příští stav)
• λ – výstupní funkce (Mealy nebo Moore)

V BI-SAP se omezujeme na synchronní sekvenční obvody – zpětné vazby jsou přerušovány klopnými obvody (FF) řízenými hodinovým signálem CLK.

🎭 Automaty Mealy a Moore – rozdíly a konverze

Oba typy jsou ekvivalentní v síle (každý Moore lze převést na Mealy a naopak), liší se v definičním oboru výstupní funkce λ:

Konverze Moore → Mealy: Z tabulky přechodů přiřadíme výstup hraně podle cílového stavu (výstup reaguje na vstup o takt dříve).

Konverze Mealy → Moore: Uzly s různými vstupními výstupy rozdělíme – každý uzel, do nějž vstupují hrany s různými výstupy, nahradíme tolika uzly, kolik různých výstupů do něj vstupuje. Výstup bude opožděný o takt.

🛠️ Postup návrhu synchronního sekvenčního obvodu

1. Slovní popis / specifikace – porozumění zadání, identifikace chování
2. Graf přechodů (STG) – uzly = stavy, hrany = přechody ohodnocené vstup/výstup (Mealy) nebo jen vstup (Moore)
3. Tabulka přechodů a výstupů – symbolická forma (stavy jako A, B, C…)
4. Kódování: zakódování vstupů, výstupů a vnitřních stavů do binárních hodnot
5. Zakódovaná tabulka – přechodové a výstupní funkce v binárních hodnotách
6. Minimalizace budících funkcí D-FF pomocí K-map
7. Minimalizace výstupních funkcí
8. Schéma zapojení z hradel a D-FF
9. Výpočet maximální hodinové frekvence: f_max = 1 / max(W_f-f) kde W_f-f = Clock-to-Q + zpoždění kombinační logiky + Setup time

📦 Registry a čítače

Registr: n D-FF řízených společným hodinovým signálem. Uchovává n-bitové slovo dokud není přepsáno. Varianty:

• Paralelní registr: Všechny bity se zapisují/čtou současně
• Registr s řízením zápisu (Load): Při Load=0 si registr pamatuje stav; při Load=1 načítá nová data
• Posuvný registr (Shift register): Při Shift=1 se data posouvají o jeden bit doleva nebo doprava. Umožňuje sériový přenos dat.
• Vícefunkční registr: Kombinace paralelního načítání a posuvů

Čítač: Speciální registr zahrnující funkci inkrementu (dekrementu). Typy:

• Binární čítač M2ⁿ: Čítá v binárním kódu. Modulo = 2ⁿ
• Neúplný čítač (Mn): Čítá do n < 2^k. Nevyužité stavy jsou don't care
• Grayův kód: Při každém přechodu se mění jen 1 bit – eliminuje hazardy při čtení stavu
• Čítač s povolením (Enable E): Čítá jen když E=1
• Vratný čítač: Čítá nahoru nebo dolů podle řídicího vstupu

✅ Shrnutí okruhu 1

• Kombinační obvod: výstup závisí jen na aktuálních vstupech → popis logickou funkcí → minimalizace K-mapou → realizace z hradel NAND/NOR
• Sekvenční obvod: výstup závisí na historii vstupů → model konečným automatem → synchronizace D-FF a hodinovým signálem
• Moore: výstup z uzlu (opožděný, stabilní); Mealy: výstup z hrany (okamžitý, kompaktnější)
• Minimalizace: hledáme PI → EPI → minimální pokrytí; neurčené stavy (X) využíváme pro zvětšení smyček
• Kritická cesta a maximální frekvence: f = 1/W_f-f; W_f-f = CLK-to-Q + t_log + t_setup

🏗️ Základní architektura číslicového počítače

Číslicový počítač zpracovává instrukce uložené v paměti. Základní principy byly formulovány Johnem von Neumannem kolem roku 1945.

Základní součásti procesoru (CPU):

• ALU (Aritmeticko-logická jednotka): Provádí operace s daty (sčítání, odčítání, logické operace, posuvy)
• Řadič (Control Unit): Řídí všechny jednotky – generuje řídící signály podle instrukčního kódu v IR
• Pracovní registry: Rychlá vnitřní paměť pro dočasné uchování dat a adres
• PC (Program Counter): Obsahuje adresu následující instrukce
• IR (Instruction Register): Obsahuje kód právě prováděné instrukce
• SP (Stack Pointer): Ukazatel na vrchol zásobníku
• SREG (Status Register): Registr příznaků – C (Carry), Z (Zero), N (Negative), V (Overflow), S, H, T, I

Sběrnice (BUS): Soubor vodičů a pravidel pro propojení jednotek. Složen z:

• AB (Address Bus): Přenos adres (jednosměrný)
• DB (Data Bus): Přenos dat (obousměrný)
• CB (Control Bus): Řídící a stavové signály

🔁 Instrukční cyklus (Fetch–Decode–Execute)

Základní fáze instrukčního cyklu:

1. IF (Instruction Fetch – čtení instrukce): PC → AB; paměť vystaví instrukci na DB; DB → IR; PC se inkrementuje na adresu další instrukce
2. ID (Instruction Decode – dekódování): Řadič dekóduje instrukční kód z IR, určí typ operace a operandy
3. OF (Operand Fetch – čtení operandů): Operandy se načtou z registrů nebo paměti
4. IE (Instruction Execute – vykonání): ALU provede operaci
5. WB (Write Back – zapsání výsledku): Výsledek se uloží do cílového registru nebo paměti
6. Interrupt? – přerušení: Testuje se, zda není aktivní žádost o přerušení

📜 ISA – Architektura souboru instrukcí

ISA (Instruction Set Architecture) je rozhraní mezi software a hardware. Definuje: typy instrukcí, formáty, kódování, datové typy, způsoby adresace, registry a způsob zpracování přerušení.

Základní třídy ISA (podle umístění operandů):

• Střadačově orientovaná (Accumulator): Jeden implicitní operand = střadač (ACC). Instrukce: LOAD A, ADD A, STORE A. Historicky první, jednoduchý HW, ale časté přístupy do paměti. Příklady: Intel 4004, 8080, 8051.
• Zásobníkově orientovaná (Stack): Operandy na hardwarovém zásobníku. Instrukce: PUSH, POP, ADD (bere ze zásobníku). Krátké instrukce, ale sekvenční přístup. Příklady: Burroughs B5000, Java Virtual Machine.
• GPR (General Purpose Registers): Více registrů pro obecné použití. Dnes dominuje. 2 nebo 3 adresové instrukce. Registry rychlejší než cache! Příklady: RISC (MIPS, ARM, AVR), x86.

Způsoby adresace operandů:

• Implicitní: Operand je určen operačním kódem (např. ACC)
• Bezprostřední (Immediate): Operand je konstanta přímo v instrukci (LDI r16, 5)
• Přímá (Direct): V instrukci je adresa paměti nebo číslo registru
• Nepřímá (Indirect): V instrukci je adresa adresy (pointer)
• Relativní: Adresa = obsah registru (typicky PC) + offset z instrukce
• Indexová: Adresa = báze + index (z dvou registrů) – vhodné pro matice
• Autoinkrementace/dekrementace: Registr se automaticky inkrementuje/dekrementuje při přístupu (SP u zásobníku)

🎛️ Řadič procesoru

Řadič je sekvenční obvod (FSM), který řídí všechny jednotky počítače podle instrukčního kódu v IR a stavových signálů z ALU a periferií. Generuje řídící signály pro ALU, registry, paměť a V/V.

Dvě základní realizace:

• Obvodový řadič (Hardwired): Klasický sekvenční obvod navržený přímo z hradel a klopných obvodů. Typicky v kódu 1 z n (každý stav = jeden FF). Rychlý, ale obtížně modifikovatelný. Používán v RISC.
• Mikroprogramový řadič: Kombinační část nahrazena řídící pamětí (ROM). Každá položka paměti = mikroinstrukce (sada řídících signálů pro daný takt). Soubor mikroinstrukcí = mikroprogram. Soubor mikroprogramů = firmware. Flexibilní (lze přeprogramovat), ale pomalejší. Používán v CISC.

Přerušení (Interrupt):

• Vnější (od periferií): maskovatelné (lze zakázat příznakem I v SREG instrukcí CLI/SEI) nebo nemaskovatelné (NMI)
• Vnitřní (chyby, instrukce INT n)
• Postup: (1) Uloží SREG a PC na zásobník; (2) Zakáže přerušení; (3) Skočí na adresu obsluhy (vektor přerušení); (4) Provede obsluhu; (5) Obnoví PC a SREG, návrat

💾 Typy pamětí a základní pojmy

Paměti se dělí podle různých kritérií:

• Podle způsobu výběru: Adresovatelné (RAM – Random Access Memory), asociativní (CAM – Content Addressable Memory – klíčem je část dat), sériové (LIFO zásobník, FIFO fronta)
• Podle možnosti změny:
  • ROM (Read Only Memory) – obsah určen při výrobě
  • PROM – jednorázově programovatelná
  • EPROM, EEPROM, Flash – mazatelné a přepisovatelné
  • SRAM (Static RAM) – bistabilní KO, rychlá, dražší, malá kapacita (cache)
  • DRAM (Dynamic RAM) – kondenzátor, nutné obnovovanie, levnější, větší kapacita (hlavní paměť)
• Volatile vs. non-volatile: SRAM, DRAM – energeticky závislé (data zmizí po vypnutí). ROM, Flash – energeticky nezávislé.

Základní pojmy adresovatelné paměti:

• Paměťová buňka: Základní prvek – uchovává 1 bit
• Paměťové místo: Skupina buněk čtených/zapisovaných najednou (šířka slova)
• Adresa: Číselné označení paměťového místa
• Kapacita: Počet paměťových míst
• Řídící signály: OE (Output Enable), WE (Write Enable), CS (Chip Select)
• Big-endian vs. Little-endian: Pořadí slabik víceslabikového čísla v paměti – big-endian: nejdůležitější byte na nejnižší adrese; little-endian: nejméně důležitý byte na nejnižší adrese (Intel x86)

📐 Paměťová hierarchie a princip lokality

Motivace: Latence DRAM (~16 ns) je 50–100× větší než cyklus procesoru (~0.33 ns). Přístupy do paměti jsou bottleneck.

Princip lokality (základ fungování hierarchie):

• Časová (temporal) lokalita: K nedávno použitým datům bude s velkou pravděpodobností brzy přistupováno znovu (cykly, funkce). → Ukládáme nedávno použitá data do rychlé cache.
• Prostorová (spatial) lokalita: S velkou pravděpodobností se bude přistupovat k datům v okolí těch, se kterými se právě pracuje (pole, sekvenční instrukce). → Přenášíme data po blocích (cache lines).

Analogie s knihovnou: Registry = knihy na stole; Cache = domácí polička; Hlavní paměť = městská knihovna; Záložní paměť = meziknihovní výpůjčka.

🌐 Virtualizace paměti a stránkování

Virtualizace umožňuje, aby programy pracovaly s logickým adresovým prostorem větším, než je fyzická hlavní paměť. Ve skutečnosti jsou data uložena na disku a do RAM se přenáší jen to, co je právě potřeba.

Stránkování:

• Logický prostor dělen na stránky (pages) pevné velikosti (4 KB–8 KB)
• Fyzický prostor dělen na stránkové rámce (page frames) stejné velikosti
• Tabulka stránek mapuje logické stránky na fyzické rámce. Je uložena v hlavní paměti.
• Položka tabulky stránek obsahuje: číslo rámce, příznak přítomnosti, Dirty bit (byla stránka modifikována?), přístupová práva
• TLB (Translation Lookaside Buffer): Rychlá asociativní cache pro překlad virtuálních adres na fyzické – urychluje stránkování
• Page fault: Stránka není v RAM → přerušení → OS načte stránku z disku (miss penalty obrovský!)

⚡ Skrytá paměť (Cache)

Princip čtení: Přístup se zahájí současně do cache i do HP. Pokud je položka v cache nalezena (cache hit), čtení z HP se přeruší.

• Cache Hit: Data nalezena v cache
• Cache Miss: Data v cache nejsou – nutno načíst z HP (miss penalty)
• Hit rate: Podíl přístupů s nalezením v cache. Typicky >95%.
• Miss rate: 1 – Hit rate
• Miss penalty: Čas pro načtení bloku z HP do cache při výpadku

Organizace cache – stupeň asociativity:

• Plně asociativní: Blok lze uložit na libovolné místo v cache. Adresář prohledáván parallelně (CAM). Nejflexibilnější, ale nejnákladnější na HW.
• Přímo mapovaná (stupeň 1): Každý blok HP může být jen na jednom místě v cache (určeno bitovým polem adresy). Levné, ale konflikty.
• N-cestně asociativní: Každý blok může být na N místech. Kompromis. Typická cache: 4-cestná nebo 8-cestná.

Struktura adresy při přístupu do cache:

• TAG: Horní bity adresy – uloženy v adresáři, slouží k ověření shody
• Index (adresní výběr): Určuje řádek (sadu) v cache
• Offset: Vybírá konkrétní byte v bloku (cache line)

Strategie zápisu:

• Write-through (průběžný zápis): Nová hodnota se zapíše zároveň do cache i do HP. Jednodušší konzistence, ale více zápisů do HP.
• Write-back (odložený zápis): Zapíše se jen do cache; do HP až při vyhazování bloku (pokud Dirty bit = 1). Méně zápisů do HP, ale složitější konzistence.

Strategie výměny (eviction policy):

• LRU (Least Recently Used): Vyhazuje nejdéle nepoužívaný blok. Nejúčinnější, ale vyžaduje udržování pořadí.
• Náhodný výběr (Random): Jednodušší HW, podobný výkon jako LRU
• FIFO: Vyhazuje nejdéle v cache přítomný blok

Organizace paměťového subsystému: Varianty přístupu HP→cache: (1) Jednoduché – zachování šířky slova, velká latence. (2) Paměť se širokým slovem – přenos N slov najednou, snižuje latenci. (3) Prokládaná paměť (interleaved) – nezávislé moduly, zřetězené přístupy.

✅ Shrnutí okruhu 2

• Von Neumann: společná paměť pro instrukce a data; Harvard: oddělené paměti – rychlejší přístup
• Instrukční cyklus: IF → ID → OF → IE → WB → přerušení? – opakuje se stále dokola
• ISA třídy: střadačová (1 registr), zásobníková (LIFO HW), GPR (mnoho registrů) – dnes dominuje GPR
• RISC: jednoduché instrukce, 1 takt, pipelining, obvodový řadič; CISC: složité instrukce, mikroprogramový řadič
• Paměťová hierarchie: registry → L1 → L2 → L3 → DRAM → disk; čím blíže CPU, tím rychlejší a dražší
• Lokalita: temporal (znovu použití) + spatial (blízkost) → základ efektivity cache
• Cache: hit/miss, hit rate, miss penalty; associativita: přímo mapovaná, N-cestná, plně asociativní
• Stránkování: logická → fyzická adresa přes tabulku stránek; TLB urychluje překlad

🔢 Poziční číselné soustavy a řádová mřížka

Důležité soustavy: dvojková (z=2), šestnáctková (z=16 = 2⁴ → 1 hex cifra = 4 bity).

Převody:

• Desetinná → dvojková (celá část): Opakované dělení 2, zbytky odpisu od konce
• Desetinná → dvojková (zlomková část): Opakované násobení 2, celé části odpisu od začátku
• Dvojková ↔ Šestnáctková: Přímá záměna po skupinách 4 bitů (od řádové čárky)

Aritmetické operace ve dvojkové soustavě:

• Sčítání: Bit po bitu od nejnižšího řádu, přenos do vyššího řádu
• Odčítání: A - B = A + (-B). Odčítání je přičtení opačného čísla modulo M → musí vyjít přenos pro správný výsledek
• Násobení: Postupné posuvy a sčítání (jako v desítkové soustavě)

±️ Kódy pro zobrazení čísel se znaménkem

Standardní polyadické soustavy zobrazují jen nezáporná čísla. Pro záporná čísla existují tři hlavní kódy:

💥 Přeplnění (Overflow) a jeho detekce

Kdy nastane přeplnění v doplňkovém kódu?

• Součet dvou kladných čísel dá záporný výsledek
• Součet dvou záporných čísel dá kladný výsledek
• Při sčítání čísel různých znamének přeplnění nikdy nenastane

Detekce přeplnění:

• Podle přenosů do/z MSB: overflow = p ⊕ q, kde p = přenos do MSB-bloku, q = přenos z MSB-bloku
• Podle znamének: overflow = a̅b̅s + abs̄ (kde a, b jsou MSB sčítanců, s je MSB výsledku)
• Jinými slovy: Pokud vstupní bity znaménka jsou oba 0 a výsledný znaménkový bit je 1 → overflow; nebo oba 1 a výsledek 0 → overflow

➕ Paralelní sčítačka/odčítačka – realizace

Úplná sčítačka (Full Adder, FA):

• Vstupy: a, b (sčítance), p (vstupní přenos)
• Výstupy: s = a ⊕ b ⊕ p (součet), q = ab + p(a⊕b) (výstupní přenos)
• Lze sestavit ze dvou půlsčítaček: s = (a⊕b)⊕p; q = a·b + p·(a⊕b)
• Realizace: NOT-AND-OR nebo NAND-NAND-NAND

Ripple Carry Adder (sčítačka s šíreným přenosem): Kaskáda FA – přenos se šíří postupně od nejnižšího po nejvyšší řád. Jednoduchá, ale pomalá (zpoždění roste lineárně s počtem bitů).

Carry Look-Ahead Adder (CLA, sčítačka s předvídáním přenosu):

• G = ab (Generate – přenos se generuje bez ohledu na vstupní přenos)
• P = a ⊕ b (Propagate – přenos se šíří z nižšího řádu)
• q' = G' + P'·p'; q'' = G'' + P''·(G' + P'·p'); … Přenosy se počítají paralelně ze vstupů
• Rychlejší (log zpoždění), ale více logiky

Sčítačka-odčítačka v doplňkovém kódu: Odčítání = přičtení opačného čísla. D(-B) = D(B) + 1. Implementace: XOR brána na každém bitu B řízená signálem „Odčítej" + přiveď na vstupní přenos „Odčítej" (horká jednička). Tentýž HW pro ADD i SUB!

V procesoru (příkazy ADD, ADC, SUB, SBB):

• ADD: m=0, p*=0 (vstupní přenos 0)
• ADC (Add with Carry): m=0, p*=Carry (vstupní přenos = příznak C)
• SUB: m=1, p*=1 (negace B + vstupní přenos 1)
• SBB (Sub with Borrow): m=1, p*=Carry

↔️ Aritmetické posuvy a jejich realizace

Posuv doleva o k míst = násobení 2^k. Posuv doprava o k míst = dělení 2^k.

Overflow při posuvu vlevo v doplňkovém kódu: Pokud vypadávají bity různé od MSB (mění se znaménko) → přeplnění.

Ztráta přesnosti při posuvu vpravo: Pokud vypadají nenulové bity → ztráta přesnosti (ZP).

Kombinace posuvů v HW: Dva řídící bity (arit, cykl) určují typ posuvu. Kombinovány multiplexory.

🔧 Dekodér, multiplexor a čítač – role v počítači

Tyto kombinační a sekvenční bloky jsou základními stavebními kameny procesoru a ALU:

• Dekodér: Adresový dekodér v paměti vybírá konkrétní paměťové místo. Dekódování instrukčního kódu (opcode) v řadiči → výběr operace.
• Multiplexor: Výběr vstupů ALU (operandy z různých registrů nebo paměti), výběr operace sčítačky/odčítačky, barrel shifter (výběr posuvné funkce), výběr dat na sběrnici (jen jeden zdroj smí vysílat).
• Čítač (jako speciální SSO): PC (Program Counter) je čítač – inkrementuje se při každém IF cyklu. Čítač taktů v časovacích obvodech. Stavový automat řadiče.

🌊 Pohyblivá řádová čárka (Floating-Point)

Proč pohyblivá řádová čárka? Čísla s pevnou řádovou čárkou mají omezený rozsah: pro 32 bitů max. celé číslo < 5·10⁹, min. zlomek > 2·10^-9. FP umožňuje reprezentovat čísla od ~10^-38 do ~10³⁸.

Struktura FP čísla:

• Mantisa (m): Informace o hodnotě čísla
• Exponent (e): Poloha řádové čárky
• Obě části používají kódy pro čísla se znaménkem

Normalizovaný tvar: Mantisa posunuta co nejvíce doleva (nejvyšší řád je 1 pro z=2). Umožňuje maximální přesnost mantisy a jednoznačnost reprezentace.

Skrytá jednička: V normalizovaném binárním FP (z=2) je MSB mantisy vždy 1 → lze ji vynechat ze zápisu a ušetřit 1 bit přesnosti. Výjimka: speciální hodnota 0 (subnormální čísla).

Příklad: Číslo −58₁₀ = −111010₂ = −1.11010 × 2⁵

• Znaménko: 1
• Exponent: 5 + 127 = 132 = 10000100₂
• Mantisa (frakce bez skryté 1): 11010 000...0
• Výsledek: 1 10000100 11010000000000000000000 = C2680000₁₆

Uložení v paměti (Endianness): Little-endian (Intel): nejméně důležitý byte na nejnižší adrese. Big-endian (Motorola): nejdůležitější byte na nejnižší adrese.

Aritmetika FP:

• Sčítání/odčítání: Srovnat exponenty (posunout mantisu menšího), pak sečíst/odečíst mantisy, normalizovat
• Násobení: Sečíst exponenty, vynásobit mantisy, normalizovat
• Dělení: Odečíst exponenty, vydělit mantisy, normalizovat
• Po každé operaci nutno normalizovat výsledek!

🔟 BCD kódy a zaokrouhlení

BCD (Binary Coded Decimal): Každá desítková číslice zakódována do 4 bitů. Kód 8421 je nejběžnější. Umožňuje přesné zobrazení desetinných čísel bez chyby zaokrouhlení pro desítkové výpočty (bankovnictví, kalkulačky).

Korekce BCD sčítačky: Pokud součet > 9 nebo vznikl binární přenos (výsledek > 15), přičteme +6 (korekce −10 = −16 + 6 v binárním kódu). Přenosová podmínka: q₁₀ = q + y₈(y₄ + y₂).

Zaokrouhlení při zkrácení řádové mřížky:

• Oříznutí (dolů): Jednoduché odstranění přebývajících bitů
• Zaokrouhlení nahoru: Přičtení 1 na místo za posledním uchovaným bitem, pak oříznutí
• Round to nearest even: Preferuje sudou poslední cifru pro odstranění systematické chyby

✅ Shrnutí okruhu 3

• Přímý kód: znaménko + absolutní hodnota, dvě nuly, složitá aritmetika
• Doplňkový kód: D(X) = X pro X≥0, M+X pro X<0. Jediná nula, sčítání = jen sečti obrazy a ignoruj přenos. Dominantní v CPU.
• Aditivní kód: A(X) = X + K. Používán pro exponent v FP (IEEE 754: K=127 pro 32b).
• Overflow ≠ Carry! Overflow = výsledek mimo rozsah signed. Detekce: p⊕q nebo z kombinace znamének operandů a výsledku.
• Sčítačka: FA kaskáda (Ripple) nebo CLA (paralelní předvídání přenosů). Odčítání = negace B + 1 (hot one) + sečtení.
• Aritmetický posuv vpravo: doplňuje MSB (sign extension). Vlevo: doplňuje 0, detekce overflow.
• IEEE 754: 1b znaménko + 8b exponent (bias 127) + 23b mantisa (skrytá 1). Speciální hodnoty: 0, ∞, NaN, subnormální.
• FP aritmetika: srovnej exponenty → proveď operaci → normalizuj výsledek.