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

• zavedieme skratky:
  • D - delenec
  • d - deliteľ
  • Q - podiel
  • - i-ty bit podielu
  • - i-ty zbytok

• v praxi sa posúva dielčí zbytok vľavo a deliteľ je v pevnej polohe
• keď je deliteľ väčší ako
  • potom
  • inak

• v praxi sa porovnávanie založené na komparátoroch nepoužíva
• odčítanie sa prevedie skúšobne, teda keď je menšie ako:
  • potom
  • inak
• ak je výsledok skúšobného odčítania nie je správny, treba pričítať d - reštaurácia nezáporného zvyšku
• postup bez reštaurácie:
  • v každom kroku prevádzame len jednu operáciu:
  • keď je , použijeme:
  • keď je , použijeme:
  • v každom kroku teda len pričítame alebo odćítame, nemusíme robiť zbytočne 2 operácie

• algoritmus pre delenie znamienkových čísel
• vykonávané operácie sa pre každý krok určujú podľa najvyšších bitov priebežného zbytku
• pre demonštráciu - odhad podľa 3 bitov, ale pre niektoré hodnoty D a d postup zlyháva

• v praxi sa odhaduje podľa viacerých bitov - napr. Pentium - podľa 7 bitov priebežného zbytku a 5 bitov deliteľa
• obvodová realizácia - sekvenčná delička, odhad podľa 3 bitov priebežného zbytku:
  • ak má delenec aj deliteľ k ľavostranných núl, posunú sa obsahy registrov PA aj B o k bitov vľavo
  • ak je , potom - posun registra PA o 1 bit vľavo
  • ak je , potom , odčítanie PA - B, posun registra PA o 1 bit vľavo
  • ak je , potom , pričítanie PA + B, posun registra PA o 1 bit vľavo
  • ak je koncový zbytok menší ako nula, pričítame P + B a odčítame Q - 1

• 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

• jednotlivé dielčie súčiny sa tvoria radom hradiel a sčítajú sa na 4-bitových sčítačkách s postupným prenosom
• celkový opčet hradiel pre násobičku n*n bitov je O(n^2)
• celkový počet jednobitových sčítačiek je (n-1)*n
• oneskorenie sčítačky je dané najdlhšou cestou v kombinačnej sieti - ak je prenosové oneskorenie hradla T a sčítačky 2T, má najdhlšia cesta oneskorenie 16T - s rastúcou dĺžkou operandov sa zväčšuje

• výsledok je na M + N bitoch
• dôslední práca so znamienkom:
  • výsledok násobenia dvoch čísel na n bitoch bude na 2n bitoch - aj vstupné operandy musia byť zakódované na 2n bitoch
  • princíp šírenia hodnoty znamienkového bitu doľava - 2 problémy:
    1. u dielčích súčinov sa objavia ľavostranné jednotky
    2. objavia sa ďalšie dielčie súčiny
  • počet čiastočných súčinov s šírenie znamienkového bitu sa dá redukovať pomocou Boothovho algoritmu
  • počet úrovní nutných na sčítanie čiastočných súčinov sa dá redukovať pomocou Wallaceovho stromu

• Překódováním násobitele potenciálně velmi usnadníme násobení, protože zredukujeme počet částečných součinů a zbavíme se levostranných jedniček.

• Základem Boothova algoritmu je překódování násobitele do soustavy relativních číslic. Máme-li násobit číslem 31, tedy 00011111, dostaneme stejný výsledek, vynásobíme-li číslem (32 - 1), což zapíšeme v soustavě relativních číslic, která používá číslice 0, +1, -1, jako:
• 0 0 0 1 1 1 1 1
• 0 0 1 0 0 0 0-1
• Tento princip aplikujeme na dvojkové číslo opakovaně pro všechny skupiny jedniček, přičemž za skupinu jedniček považujeme i jedinou jedničku.
• 0 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1
• 1 0-1 0 0 1-1 1 0-1 1 0 0 0-1 1 0 0 0-1
• Odtud můžeme sestavit překódovaci tabulku. Kromě překódovaného bitu se řídíme ještě hodnotou sousedního bitu vpravo. Dostáváme tak základní Boothovo překódování, zvané též překódování s radixem 2.

• vznikají nulové částečné součiny, které usnadňují výsledný součet
• zůstává však nutnost šíření znaménka u záporných dílčích součinů.

• Dalším požadavkem pro urychlení násobení je snížení počtu dílčích součinů
• překódování „2 bity najednou“

1 1   0 1   0 1   1 0   0 1 původní číslo rozdělené do dvojic
2 1   2 1   2 1   2 1   2 1 váhy
0-1   1-1   1 0   -1 0  1-1 Boothovo překódování po jednom bitu
-1     1     2     -2    1  překódování "2 bity najednou"

• Obecný postup je takový: V každé skupině zopakujeme nejvyšší bit, a přičteme k nejnižšímu bitu nejvyšší bit ze skupiny vpravo. Výsledné číslo pak považujeme za relativní číslici v doplňkovém kódu.

Radix 4:
00  00  11  01  11  10  01  00  10  10   původní číslo
000 000 111 001 111 110 001 000 110 110  rozšíření znam. bitu
 0   1   0   1   1   0   0   1   1   0   přičtení bitu zprava
--------------------------------------------------------------------------
000 001 111 010 000 110 001 001 111 110  doplňkový. kód rel. číslice
0   +1  -1   2   0  -2  +1   1  -1  -2   překódování s radixem 4

• Urychlení sečtení částečných součinů
• Sčítá se bez uvážení přenosů (tj. rychle).
• Avšak přenosy se uchovávají v registru a přičítají (pomocí úplných sčítaček) k průběžnému součtu a dalšímu operandu v následujícím kroku (opět bez přenosu).
• Přičtení posledního operandu se provede pomocí sčítačky s postupným přenosem.
• Ze tří řad sčítacího stromu jsme odstranili sčítačky s postupným přenosem.
• Sčítačky v jedné řadě se označují jako sčítačka s uchováním přenosu (SUP, angl. CSA - Carry-Save Adder).
• V každém stupni se sčítačka v nejvyšším řádu redukovala na hradlo.
• Museli jsme však nakonec jednu řadu sčítaček s postupným přenosem (SPP) přidat.
• Základem n-bitové násobičky s uchováním přenosu je n-bitová SUP:

1. Nejdříve jsou sečteny částečné součiny A, B a C, výsledek je v S1 a C1.
2. Potom jsou sečteny částečné součiny D, E a F, výsledek je v S2 a C2.
3. Následuje součet S1, C1 a S2, výsledek je v S3 a C3.
4. Nakonec jsou sečteny S3, C3 a C2, výsledek je v S4 a C4.
5. Sčítačkou s postupným přenosem jsou nakonec sečteny S4 a C4.
6. Kromě posledního sčítaní jsou všechna ostatní sčítání s uchováním přenosu.

• Zrychlené sčítání částečných součinů
• 6×6 bitov:

• 8×8 bitov: