REPREZENTACE DAT. Principy počítačů I. Literatura. Literály. Typy dat. Literály. Čísla Instrukce. Znaky. Logické hodnoty

SWI065 2002/2003 LS

RNDr. David Obdržálek

SWI065 2002/2003 LS

1


Literatura

Principy počítačů I

• D.Goldberg: What Every Computer Scientist Should Know About Floating-Point Arithmetic • IA-32 Intel Architecture Software Developer’s Manual (Vol.1 – Basic Architecture)

REPREZENTACE DAT „There are only 10 types of people in the world: those who understand binary, and those who don't.“

SWI065 2002/2003 LS


SWI065 2002/2003 LS

Typy dat

Literály • • • •

• Literály • Čísla • Instrukce

SWI065 2002/2003 LS


logické hodnoty znaky grafické symboly nečíselná data

SWI065 2002/2003 LS

Logické hodnoty • možno reprezentovat jediným bitem x x x x 0 x x x


x x x x 1 x x x

– problémy s adresováním

• reprezentace celou datovou jednotkou 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

? ? ? ? ? ? ? ?


Znaky • EBCDIC • ASCII • UNICODE

– problémy s velikostí

1

SWI065 2002/2003 LS


SWI065 2002/2003 LS


EBCDIC

ASCII

• 256 závazných znaků • 0x00 .. 0x3F ... speciální (řídící) znaky • 0x40 .. 0xFF ... tisknutelné znaky

b3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

• Mnoho volných pozic • Abeceda není v jednom bloku

b2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

b1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

b0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

b6 0 b5 0 b4 0 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI

0 0 1 DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US

0 1 0 space ! " # $ % & ' ( ) * + , . /

0 1 1 0 1 2 3 4 5 6 7 8 9 : ; < = > ?

1 0 0 @ A B C D E F G H I J K L M N O

1 0 1 P Q R S T U V W X Y Z [ \ ] ↑ _

1 1 0 ` a b c d e f g h i j k l m n o

1 1 1 p q r s t u v w x y z { | } ~ DEL

'G' ≈ 01000111

SWI065 2002/2003 LS


SWI065 2002/2003 LS

ASCII • • • • • •

UNICODE

KOI8-čs PC standard EAST8 Latin x (Latin 2) Windows codepage (1250) ISO/IEC 8859 (8859-2)

SWI065 2002/2003 LS

UNICODE • podpora národních abeced – Latin – Greek – Cyrillic – Hebrew – Hiragana, Katakana – ... a množství dalších


• • • • • •


součást normy ISO/IEC 10646-1 (1993) znak reprezentován vícebytovou sekvencí diakritika možnost uživatelských symbolů problém se staršími programy pozor na konkrétní implementaci

SWI065 2002/2003 LS


Grafické symboly • reprezentace spolu se znaky • jazyky pro popis grafických symbolů

• návrhy rozšíření

2

SWI065 2002/2003 LS


SWI065 2002/2003 LS


Číselné soustavy

Číselné soustavy

• Polyadické – Číslo A =

• Nepolyadické i = n −1

∑a z

i=− m

i i

– římské číslice

reprezentujeme

• 1648 ≈ MDCXLVIII 2003 ≈ MMIII • pro počítání nevhodné

uspořádanou (m+n)ticí koeficientů ai – Soustava může mít jeden nebo více základů (radix mumber system) – V soustavě s jedním základem z jsou hodnoty zi určeny jako zi=zi – m=0 ... celá čísla, m>0 ... zlomková část

SWI065 2002/2003 LS


– soustava zbytkových tříd (residue number system) • definována k-tice různých základů – prvočísel • číslo vyjádřeno k-ticí zbytků po dělení příslušným základem • Příklad: základy 2,3,11: číslo „devět“ zapsáno jako 109 • jednoznačné pouze pro čísla menší než součin základů

SWI065 2002/2003 LS


Převodní algoritmus

Přepis celého čísla do soustavy s jiným základem • Zápis čísla A v soustavě o základu z: A = an-1zn-1 + an-2zn-2 + … + a1z1 + a0z0 = (an-1zn-2 + an-2zn-3 + … a1)z + a0 = a0 + z (a1 + z (a2 + …+ z(an-2 + zan-1)…)) • V soustavě o základu z’ bude A zapsáno: A = b0 + z’(b1 + z’(b2 + …+ z’(bn-2 + z’bn-1)…)) • A = z’ ⎣ A/z’⎦ + A mod z’

9 ≈ IX, VIIII

1

číslo v soustavě z

V soustavě o základu z dělit základem nové soustavy (z’) Výsledek dělení

NE

Výsledek je nula?

Zbytek = bn

ANO

Konec

SWI065 2002/2003 LS


Příklady 15110 do binární soustavy: 151 : 2 = 75 1 75 : 2 = 37 1 37 : 2 = 18 1 18 : 2 = 9 0 9:2= 4 1 4:2= 2 0 2:2= 1 0 1:2= 0 1

1349 do sedmičkové soust.: 134 : 7 = 17 0 17 : 7 = 2 2 2:7= 0 2 1349 = 2207

SWI065 2002/2003 LS


Převod do desítkové soustavy • Koeficienty zápisu čísla o základu z vynásobíme příslušnou mocninou z a sečteme: A ≈ an-1an-2 … a1a0 A = an-1zn-1 + an-2zn-2 + … + a1z1 + a0z0 • Hornerovo schéma: A = (…(an-1z + an-2)z + …)z + a0

15110 = 100101112

3

SWI065 2002/2003 LS


Převod čísla se zlomkovou částí • Hledáme koeficienty pro

zi,

SWI065 2002/2003 LS


Převodní algoritmus zlomkové části

1

zlomková část čísla v soustavě z

-m ≤ i ≤ n-1

V soustavě o základu z násobit základem nové soustavy (z’)

• Celá část: popsána výše • Zlomková část: podobně, ale základem nové soustavy násobíme.

zlomková část

NE

desetinná část je nula?

celá část = bn

ANO

Konec

SWI065 2002/2003 LS


SWI065 2002/2003 LS

Příklad

Příklad 0,67810 převést do dvojkové soustavy: 0,678* 2 =1,356 1 0,356* 2 =0,712 0 0,712* 2 =1,424 1 0,424* 2 =0,848 0 0,848* 2 =1,696 1 0,696* 2 =1,392 1 0,392* 2 =0,784 0 0,784* 2 =1,568 1 0,67810 ≈ 0,101011012

0,110 převést do dvojkové soustavy: 0,1 * 2 = 0,2 0 0,2 * 2 = 0,4 0 0,4 * 2 = 0,8 0 0,8 * 2 = 1,6 1 0,6 * 2 = 1,2 1 0,2 * 2 = 0,4 0 0,110 ≈ 0,0001100110011…2

Postup nemusí být konečný!

SWI065 2002/2003 LS


Čísla • • • •

přirozená čísla celá čísla racionální reálná


SWI065 2002/2003 LS


Zobrazení přirozených čísel I • převodem do binární soustavy a přímým uložením 1910 ≈

0 0 0 1 0 0 1 1

22910 ≈ 1 1 1 0 0 1 0 1

4

SWI065 2002/2003 LS


SWI065 2002/2003 LS

Zobrazení přirozených čísel II

– „horní“ 4 bity nevyužity nebo využity jinak

Příklad: 193010 ≈ 0001 1001 0011 0000 Problémy → →

– číslo převedeno do binární podoby – doplněno znaménkovým bitem – Problém: dvě reprezentace nuly, složitější operace

• s posunutím – k číslu se přičte konstanta reprezentující nulu – posunuté číslo se převede do binární podoby – přirozená čísla se zobrazí přímo, záporná jako „pseudopozitivní“ číslo


Dvojkový doplněk Mějme číslo A. Jeho doplněk A’ = A + M = -|A| + M kde M je modul. Pro dvojkovou soustavu je M=2n kde n je počet cifer zápisu čísla.

SWI065 2002/2003 LS

A = -1 A’ = (-1) + 2n

pro n=4: ≈ 11112

-10 +19 ----+9 ?

10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 10 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 -10 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 -10 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 19 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1

+9 !

1. zneguj bity 2. přičti 1

SWI065 2002/2003 LS


Konverze délek • znaménkové rozšíření

-18 -18


Aritmetika ve dvojkovém doplňku

Ve dvojkové soustavě:

+18 +18

1

• dvojkový doplněk

speciální instrukce packed BCD

SWI065 2002/2003 LS

Zobrazení celých čísel • se znaménkem

• BCD – Binary Coded Decimal Každá cifra desítkového zápisu čísla reprezentována pomocí 4 bitů

– aritmetika – neúsporné


0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0

9 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

SWI065 2002/2003 LS

Příklady zobrazení

číslo se znaménkem s posunutím +7 +6 +5 +4 +3 +2 +1 +0 -0 -1 -2 -3 -4 -5 -6 -7 -8

0111 0110 0101 0100 0011 0010 0001 0000 1000 1001 1010 1011 1100 1101 1110 1111 ---

1111 1110 1101 1100 1011 1010 1001 1000 1000 0111 0110 0101 0100 0011 0010 0001 0000


dvojkový doplněk 0111 0110 0101 0100 0011 0010 0001 0000 0000 1111 1110 1101 1100 1011 1010 1001 1000

5

SWI065 2002/2003 LS


Ukládání vícebytových sekvencí

SWI065 2002/2003 LS

1

• Big-endian


Zobrazení reálných čísel • Čísla s pevnou řádovou čárkou

– IBM 370, PDP-10, Motorola, různé RISC, IA-64

• Little-endian – PDP-11, VAX, Intel, IA-64 (nižší adresa=nižší význam) • (Midle-endian – ani little, ani big. „Used of perverse byte orders such as 3-4-1-2 or 2-1-4-3, ocassionally found in the packed-decimal formats of minicomputer manufacturers who shall remain nameless.“)

– Zobrazení celých čísel je speciální případ, kdy řádová čárka je zcela vpravo – Posunutím řádové čárky směrem vlevo měníme rozsah zobrazovaných čísel a přesnost zobrazení 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1

• NUXI problem

SWI065 2002/2003 LS


SWI065 2002/2003 LS

Zobrazení reálných čísel • Z jiných reprezentací se nejvíce ujala reprezentace s plovoucí řádovou čárkou („floating point“): • Je dán základ β a přesnost p • Příklad: 0,9 pro β=10, p=3 ... 9.00 × 10-1 0,1 pro β=2, p=24 ... (nelze přesně) 1.10011001100110011001101 × 2-4

SWI065 2002/2003 LS


Floating – point • Zápis nemusí být jednoznačný: 1.00 × 10-1 0.01 × 101 • Je-li d0 ≠ 0, reprezentace je nazývána normalizovanou • Pro d0 = 0 je reprezentace nazývána denormalizovanou


Floating – point • Zápis ve tvaru ±d0.d1d2 ... dp-1 × β e ( 0 ≤ di < β ) reprezentuje číslo ±(d0 + d1 β -1 + ... + dp-1 β 1-p) β e

SWI065 2002/2003 LS


Používaná zobrazení Znaménko exponentu

Řádová čárka exponentu

± ±

Exponent

Znaménko mantisy

Znaménko mantisy

Mantisa Řádová čárka exponentu i mantisy

± (sExponent posunem) Znaménko mantisy

Řádová čárka mantisy

Mantisa

1. ±

Exponent

Mantisa (vždy normalizována) Řádová čárka exponentu i mantisy

6

SWI065 2002/2003 LS


SWI065 2002/2003 LS


IEEE Standard 754

IEEE Standard 754

• single precision: β=2, p=24, |e| = 8 bitů • double precision: β=2, p=53, |e| = 11 bitů

• přesný zápis v bitovém formátu ± Exponent

• quadruple precision: β=2, p=113, |e| = 15 bitů

31 30

Extended formats: • single extended: β=2, p≥32, |e| ≥ 11 bitů • double extended: β=2, p≥64, |e| ≥ 15 bitů

79 78

±

Mantisa

23 22

0

Exponent

Mantisa 64 63

0

Correct use of this format is a nontrivial challenge to programmers

SWI065 2002/2003 LS


SWI065 2002/2003 LS

IEEE Standard 754

SWI065 2002/2003 LS

IEEE Standard 754


IEEE Standard 854 • • • •


povoluje β=2 a β=10 neurčuje konkrétní zápis nevyžaduje konkrétní hodnoty p pro single a double precision zavádí omezující podmínky možných hodnot p.

SWI065 2002/2003 LS


Možnosti zápisu dle IEEE 754 exponent

mantisa

význam

emin-1

m=0

±0

emin-1

m≠0

0.m × 2emin

< emin, emax>

m

1.m × 2e

emax+1

m=0

±∞

000…000

111…111

emax+1

m≠0

1xxx…xxx

NaN

emax+1

m≠0

0xxx…xxx

SNaN

1

7

SWI065 2002/2003 LS


1

NaN

POZOR na chování konkrétního procesoru a kompilátoru!!! operace + × / REM √

vznik NaN ∞ + (-∞) 0×∞ 0/0, ∞/∞ x REM 0, ∞ REM y √x pro x<0

SWI065 2002/2003 LS


SWI065 2002/2003 LS


Operace s floating-point čísly exp1

A=M1 × z Sčítání o odečítání

• Pro exp1=exp2 je A+B = (M1 + M2) × zexp1 • Pro exp1≠exp2 je nutno: • A nebo B denormalizovat • provést výpočet • normalizovat výsledek

• Pozor: • sčítání a odečítání nejsou asociativní • přetečení či podtečení (při denormalizaci i při výpočtu)

SWI065 2002/2003 LS

Operace s floating-point čísly A=M1 × zexp1


Vznik chyb

B=M2 × zexp2

Násobení a dělení

exp2

B=M2 × z

• Při výpočtu zexp1+exp2

• A.B = (M1 . M2) × • A/B = (M1 / M2) × zexp1-exp2

• Pozor: operace v binární soustavě se zápornými čísly mohou vést k časově náročným postupům. Řešení – Boothovo kódování.

– overflow – přetečení – underflow – podtečení – divide by zero – dělení nulou – invalid – neplatná operace – inexact – nepřesný výsledek

• místo hodnot 0,1 jsou použity relativní hodnoty +1,0,-1 • Příklad: násobení 63: 00111111 → 0100000-1

SWI065 2002/2003 LS


Vznik chyb • Při konverzi – scaling error – zavedením stupnice – truncation error – zanedbáním části čísla – rounding error – zaokrouhlením – (při pořizování)

SWI065 2002/2003 LS


Problémy IEEE 754/854 ((2×10-30 + 1030) − 1030) − 10-30 ≡ 10-30

na počítači pracujícím podle IEEE = -10-30

8

REPREZENTACE DAT. Principy počítačů I. Literatura. Literály. Typy dat. Literály. Čísla Instrukce. Znaky. Logické hodnoty

Recommend Documents