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:

kódy pro vnější přenos dat, EBCDIC, ASCII, a jeho modifikace

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

Zobrazenie znakov

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

Zobrazenie čísel v dvojkovej sústave v počítači

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)

Zobrazenie čísel v pevnej rádovej čiarke

Používání kódů, jak je na obrázku, je třeba znát na státnice!

Reprezentace čísla 7

Zobrazenie kladných čísel (čísel bez znamienka)

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

Zobrazenie čísel so znamienkom

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

Chyby zobrazení čísla FX

chyba měření:

vzniká při pořizování čísla vlivem chyby metody měření

chyba stupnice (scaling):

číselná soustava nemůže na konečném počtu míst vyjádřit přesně všechny hodnoty
Chyba stupnice

chyba zanedbáním (truncation = odseknutí) a zaokrouhlením (rounding)

používá se statistické zaokrouhlování ⇒ zaokrouhluje se k sudému číslu
Chyba zaokrouhlováním

Zobrazenie BCD čísel

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)

Kódování 2 z 5

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á)

Vzpomeňte si, jak bylo v IPZ u SATA a DVI uveden kód 8b/10b ⇒ také byla méně bitová čísla kódována na více bitů.

Huffmanův kód

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ý

Huffmanův kód

Parametry kódu

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

Zobrazenie čísel v pohyblivej rádovej čiarke

X = (-1)SM.BE

znamienko - S

exponent - E - celé číslo, vyjadruje rád (počet číslic o ktoré sa posunie desatinná čiarka mantisy)

mantisa - M - reálne číslo, vyjadruje hodnotu

základ - B - budeme brát 2

E: 5 bitů, M: 8 bitů, S: 1 bit, B = 2 1710 = 100012 = 10001 * 25 FP - 17 6553610 = 216 = 0,1 * 217 FP - 65536 Toto číslo by se na 14 bitů u FX nikdy nevešlo. Problém je s malými čísly ⇒ použije se lichý nebo sudý posuv. Zavede se BIAS (posunutí) FP - BIAS Čísla jdou zapsat více způsoby: FP - unikátnost Musíme nějak zobrazit nulu ⇒ IEEE 754 standard

IEEE 754

Aritmetické operácie:

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:

Sčítanie:

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

Odčítanie

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ť

Delenie

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

Reštaurácia nezáporného zbytku

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

Delenie SRT

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

Násobenie

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

Princíp násobenia (bez znamienka)

majme 2 čísla: N-bitový násobiteľ a M-bitový násobenec

súčin bude:

Sekvenčná násobička

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:

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.

obsah registra PB sa posunie o jeden bit vpravo

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

Kombinačná násobička

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

Násobenie čísel so znamienkom v doplnkovom kóde

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:

u dielčích súčinov sa objavia ľavostranné jednotky

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

Princíp Boothovho prekódovania

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.

Boothovo prekódovanie s radixom 2

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ů.

Boothovo prekódovanie s radixom 4

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"

Boothovo prekódovanie - všeobecný počet bitov

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

Násobička s uchovaním prenosov

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:

Príklad na násobenie s uchovaním prenosu

Nejdříve jsou sečteny částečné součiny A, B a C, výsledek je v S1 a C1.

Potom jsou sečteny částečné součiny D, E a F, výsledek je v S2 a C2.

Následuje součet S1, C1 a S2, výsledek je v S3 a C3.

Nakonec jsou sečteny S3, C3 a C2, výsledek je v S4 a C4.

Sčítačkou s postupným přenosem jsou nakonec sečteny S4 a C4.

Kromě posledního sčítaní jsou všechna ostatní sčítání s uchováním přenosu.

Wallaceov strom

Zrychlené sčítání částečných součinů

6×6 bitov:

8×8 bitov:

Zdroj

Čerpal som zo slidov k IAS: https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/IAS-IT/lectures/10ias_1.pdf a zo slidov k INP: https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/INP-IT/lectures/inp2010_08mult.pdf https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/INP-IT/lectures/inp2010_09div.pdf

Potvrzení