09 - Reprezentácia čísiel a základné dvojkové aritmetické operácie v počítači

• kód - vzájemně jednoznačné přiřazení mezi symboly dvou množin
•  data reprezentujeme pomocí kódů, které můžeme zhruba rozdělit do dvou skupin:
  1. kódy pro vnější přenos dat, EBCDIC, ASCII, a jeho modifikace
  2. kódy pro vnitřní reprezentaci dat, jako doplňkový kód, BCD
•  FP - čísla s pohyblivou řádovou
•  FX - čísla s pevnou řádovou čárkou
•  kódování znaků
  •  ASCII - 7 bit
    • pro výměnu dat mezi systémy
    • American Standard Code for Information Interchange
  • Latin - 2 (ISO 8859-2), 1250 Microsoft Windows, …
    • doplnění 8. bitu
    •  např česká abeceda, atd… - norma ISO/IEC 8859 (východní Evropa)
  •  UNICODE
    • 16 bitů (UTF-16)
    • později 32 bitů (UTF-32)
    •  “exotické“ abecedy
• polyadické vs. nepolyadické soustavy
  • ALU realizována v nepolyadické soustavě je mnohem rychlejší jak v doplňkovém kódu ⇒ např. při sčítání není třeba pamatovat si carry (x nefunguje dělení) ⇒ dobré pro rychlou Fourierovu transformaci nebo pro digitální filtr
  • v ALU musí být konvertor z kódu zbytkových tříd do doplňkového kódu a naopak

• rôzne kódy reprezentujú jednotlivé znaky číslami bez znamienka - tzv. ordinálnymi hodnotami znakov
• rôzne znaky musia byť reprezentované rôznymi číslami
• písmeno väčšie v abecede musí byť reprezentované väčším číslom
• číslice musia byť reprezentované ako BCD číslice na najnižších štyroch bitoch svojich ordinálnych čísel

• bit - binary digital - dvojková číslica
• rozsah zobrazenia - interval ohraničený zľava najmenším a sprava najväčším zobraziteľným číslom
• rozlíšiteľnosť zobrazenia - najmenšie (kladné) zobraziteľné číslo
• presnosť zobrazenia - počet platných dekadických číslic, ktoré je možné zobraziť v danom pamäťovom priestore (hodnota nezávislá na veľkosti zobrazovaného čísla)
• LSB - least significant bit - číslica najviac napravo (najmenej významná)
• MSB - most significant bit - číslica najvac naľavo (najvýznamnejšia)

• pre k-bitový pamäťový priestor a kladné dvojkové číslo, ktoré má n miest vľavo a m miest vpravo od rádovej čiarky (k = n + m)platí:
  • rozsah zobrazenia = <0, (2^n - 2^(-m))>
  • presnosť zobrazenia = k*log10(2)

• rozlíšiteľnosť zobrazenia = 2^(-m)
• v súčasnej dobe sa v pevnej rádovej čiarke zobrazujú len celé čísla (m = 0, k = n), potom rozsah zobrazenia je daný intervalom <0, (2^n - 1)>, rozlíšiteľnosť má hodnotu 1

• nech x označuje zobrazované číslo a nech X označuje jeho obraz (číslo ukladané do pamäte)
• informáciu o znamienku nesie najvyšší bit, preto sa nazýva znamienkový
• ostatné bity nesú informáciu o hodnote čísla, preto sa nazývajú významové
• Priamy kód:
  • X = x pre x patrí <0, 2^(n-1) - 2^(-m)>
  • X = 2^(n-1)-x pre x patrí ←(2^(n-1) - 2^(-m)), 0>
  • kladné číslo sa od rovnakého záporného čísla v priamom kóde líši len hodnotou najvyššieho bitu (0 pre kladné čísla, 1 pre záporné), existujú 2 obrazy čísla 0

• Doplnkový kód:
  • X = x pre x patrí <0, 2^(n-1) - 2^(-m)>
  • X = 2^n + x pre x patrí ←2^(n-1), -2^(-m)>
  • kladné číslo sa od rovnakého záporného čísla líši o hodnotu najvyššieho bitu i hodnotu všetkých ostatných bitov
  • jednotkový doplnok:
    • dá sa spočítať negáciou jednotlivých bitov
    • kladná aj záporná nula
    • používa sa hlavne ako medzioperácia pri počítaní dvojkového doplnku

• dvojkový doplnok:
  • prakticky sa číslo s opačným znamienkom získa inverziou všetkých bitov a aritmetickým pričítaním jednotky
  • nemá dve nuly
  • je nesymetrický - má o jednu viac záporných hodnôt ako kladných
  • predstavuje základ aritmetiky väčšiny číslicových systémov

• Kód transformovanej nuly:
  • X = 2^(n-1) + x pre x patrí ←2^(n-1), 2^(n-1)-2^(-m)>
  • kladné číslo sa od rovnakého záporného v kóde transformovanej nuly líši o hodnotu najvyššieho bitu i hodnotu všetkých ostatných bitov
  • v tomto kóde sa číslo prakticky získa z čísla v doplnkovom kóde zmenou hodnoty najvyššieho bitu

1. chyba měření:
   • vzniká při pořizování čísla vlivem chyby metody měření
2. chyba stupnice (scaling):
   • číselná soustava nemůže na konečném počtu míst vyjádřit přesně všechny hodnoty
     
3. chyba zanedbáním (truncation = odseknutí) a zaokrouhlením (rounding)
   • používá se statistické zaokrouhlování ⇒ zaokrouhluje se k sudému číslu
     

• každá desiatková číslica je zobrazená samostatne štyrmi bitmi dvojkovej sústavy:
• 586.248 = 0101 1000 0110.0010 0100 1000
• je-li binární součet větší než 9, je třeba provést korekci ⇒ přičíst k výsledku číslo 6 (zjištěno na základě analýzy kódu)

• je neváhový kód, který kóduje informaci nadbytečným množstvím bitů, je tedy redundantní
• redundantní ⇒ detekuje jednobitové chyby
• při sčítání máme uloženy všechny kombinace v paměti - look up tabulka (rychlé, ale velká paměť, která není dostatečně využitá)

• umožňuje optimálně vyřešit problém, jakým způsobem zakódovat znaky abecedy tak, aby častěji se vyskytující znaky byly zakódovány pomocí kratší binární sekvence
• Huffmanovo kódování patří mezi kódy s proměnnou délkou (VLC - Variable Length Coding)
• například formát jpeg, pkzip
• dá se představit na Morseově abecedě ⇒ musí být jednoznačný

• průměrná délka značky - udělám průměr všech značek
• střední dynamická délka značky - při sčítání délek každou délku vynásobím počtem výskytů
• teoretická optimální délka značky - vzorec s logaritmama (nebudou snad chtít) ⇒ pamatuji si akorát, jak jsme to počítali na písemce a byla to dost otrava
• redundance kódu - (dynamická-teoretická)/dynamická = nadbytečnost

• X = (-1)^SM.B^E
  1. znamienko - S
  2. exponent - E - celé číslo, vyjadruje rád (počet číslic o ktoré sa posunie desatinná čiarka mantisy)
  3. mantisa - M - reálne číslo, vyjadruje hodnotu
  4.  základ - B - budeme brát 2

• základné aritmetické operácie (v obmedzenom pamäťovom priestore, k = n = 4), sledujeme prenosy/výpožičky z/do (C) a do/z (P) najvyššieho bitu:

• dochádza k prenosom do vyššieho rádu
• sledujeme prenos z a do najvyššieho bitu
• keď sa výsledok nedá zobraziť v danom pamäťovom priestore, indikujeme to pretečením

sčítačky

• dochádza k výpožičkám z vyššieho rádu
• sledujeme prenos z a do najvyššieho rádu
• keď prenos z najvyššieho rádu != prenos do najvyššieho rádu, znamená to chybu a výsledok sa nedá zobraziť

• 2 výsledky - celočíselný podiel a zvyšok po delení
• výsledok je vždy zobraziteľný
• robí sa s kladnými operandmi, keď je jeden záporný tak sa výsledok nakoniec prevedie

• môžeme násobiť absolútne hodnoty čísel a nakoniec doplniť znamienko, alebo násobiť priamo čísla so znamienkom
• násobenie môže byť sekvenčné (postupne) alebo kombinačné (v jednom kroku):
  • sekvenčné násobičky
  • kombinačné násobičky
• podľa typu operandu:
  • v pevnej rádovej čiarke
  • v plávajúcej rádovej čiarke

• majme 2 čísla: N-bitový násobiteľ a M-bitový násobenec
• súčin bude:
• 

• pri sekvenčnom násobení čísel A x B sa do prvej polovice spojených registrov PB pripraví násobiteľ B, do hornej polovice nuly, násobiteľ do registra A.
• postup:
  1. najnižším bitom registra PB sa vynásobí násobenec A a pričíta sa k hornej časti registra PB, kde sa udržuje priebežný súčet dielčích súčinov.
  2. obsah registra PB sa posunie o jeden bit vpravo
  3. kroky 1, 2 vykonáme celkovo n-krát
• výhoda - nízky počet hradiel
• nevýhoda - nízka rýchlosť, n taktov na násobenie