21.9.2014
Datové formáty Radim Farana Podklady pro výuku
Obsah Datové formáty (datové typy). Textové formáty, vlastnosti zdroje zpráv. Číselné formáty, číselné soustavy. Přesnost uložení čísel. Numerické chyby.
Datové formáty (datové typy) Jednoduché Textové (alfanumerické) Číselné celočíselné neceločíselné • s pevnou řádovou čárkou • s pohyblivou řádovou čárkou
Datum a čas
Složené Pole Záznam
1
21.9.2014
Textové kódy blokové kódy s různou délkou kódového slova a mohutností abecedy, 5 bitů – nejstarší kódy, Baudotův kód, kód CCITT, dvě znakové sady po 32 znaků, 7 bitů – American Standard Code for Information Interchange – ASCII – UNIX, 8 bitů – ACSII-2, znakové sady (1250) pro různé jazyky, 16 bitů – Unicode.
Baudotův kód binary 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111
hexa 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
LTRS E LINE FEED A SPACE S I U CAR. RET. D R J N F C K T Z L W H Y P Q O B G FIGS M X V LTRS
FIGS
FIGS (US Bell)
-- unused -3 LINE FEED SPACE ' 8 7 CAR. RET. $ 4 BELL , ! : ( 5 " ) 2 # 6 0 1 9 ? & FIGS . / ; LTRS
Baudot, Jean-Maurice-Émile BELL
Baudotův telegraf
* 11. 9. 1845 Magneux, France + 28. 3. 1903 Sceaux, France http://www.converter.cz/fyzici/baudot.htm
'
STOP
Kód CCITT CCITT 1 2 3 4 5 6 7 8 9 10 11 12 13 14
znak A _ B ? C : D vz E 3 F G H I 8 J zv K ( L ) M . N ,
kód 11000 10011 01110 10010 10000 10110 01011 00101 01100 11010 11110 01001 00111 00110
CCITT 17 18 19 20 21 22 23 24 25 26 27 28 29 30
15 16
O 9 P 0
00011 01101
31 32
znak Q 1 R 4 S ! T 5 U 7 V = W 2 X / Y 6 Z + návrat válce posun řádku číslicová změna písmenová změna mezera
kód 11101 01010 10100 00001 11100 01111 11001 10111 10101 10001 00010 01000 11011 11111 00100 00000
2
21.9.2014
ASCII, ISO 8859-1 (Latin-1)
Abeceda zdroje Z26 –Mezinárodní telegrafní abeceda: ABCDEFGHIJKLMNOPQRSTUVWXYZ, Z27 – Telegrafní abeceda s mezerou, Z41 – Česká abeceda velkých písmen: AÁBCČDĎEÉĚFGHIÍJKLMNŇOÓPQRŘSŠT ŤUÚŮVWXYÝZŽ, Z42 – Česká abeceda s mezerou, Z128 – Abeceda kódu ASCII znaků (7 bitů), Z256 – Abeceda kódu ASCII-2 (8 bitů).
Vlastnosti zdroje Pravděpodobnosti výskytu jednotlivých znaků české abecedy Z42 A Á B C Č
0,054 0,021 0,014 0,019 0,008
F G H I Í
0,002 0,002 0,020 0,034 0,025
Ň O Ó P Q
0,015 0,068 0,000 0,027 0,000
Ť U Ú Ů V
0,007 0,030 0,003 0,002 0,039
Ž –
0,009 0,163
Pravděpodobnost výskytu znaků české abecedy Z 26
0,14
Pravděpodobnost
0,12 0,1 0,08 0,06 0,04 0,02 0 A B C D E F G H I
J K L M N O P Q R S T U V W X Y Z
3
21.9.2014
Slovník spisovné češtiny
Frekvence znaků v češtině
slova v běžném textu
kartotéka příjmení
A B
A
A B C D Ď G
E
C
Č
F
J
Ch J
L
I
D F
H
H
Ch
Ch
G
K
M I
L
kartotéky, soubory znaků, analýza jazyka zdroje zpráv.
Č
D Ď E F G
G H
K
B C
Č
EF I
A
C
D
H Ch
kartotéka místních jmen
B Č
N
M
O
N
I J
J K
K
L O P
L
P
Q R Ř
M
M
N
N
O
O
S
P
Q
Š
R Ř
T
S Š
U
P
Q R Ř
R
S
S
Ř
T V
Š
U
Š
W X Y
T V
T
Z
U
U
W X Y
V
Z
V
W X Y Z Ž
Ž
Ž
poloviny
třetiny
Z Ž
čtvrtiny
pětiny
Určení jazyka zdroje Index koincidence I(C)= P(i)2 Využití v kryptoanalýze
Jazyk
I (C )
angličtina
0,066895
dánština
0,070731
finština
0,073796
francouzština
0,074604
holandština
0,079805
němčina
0,076667
italština
0,073294
ruština
0,056074
španělština
0,076613
slovenština
0,060270
čeština
0,063600
Textové formáty Znak, Char, Character (1 B) String – posloupnost Byte (do 255 B) s pevnou délkou s proměnlivou délkou
Memo (až 64 kB – adresa 16 bitů). délka
znak
znak
znak
0
1
2
3
…
znak n
4
21.9.2014
Číselné formáty Celočíselné Bit (logický datový typ) Byte (1 B, rozsah 0 – 255) Integer (2 B) Long Integer (4 B)
Racionální, podíl dvou celých čísel Neceločíselné s pevnou řádovou čárkou s pohyblivou řádovou čárkou
Číselné soustavy Binární (dvojková) Oktalová (osmičková, 1 znak = 3 b) Šestnáctková (hexadecimální, 4 b) Dekadická (desítková) 18,625 postupné dělení postupné násobení 18 : 2 = 9, Zb. 0 9 : 2 = 4, Zb. 1 4 : 2 = 2, Zb. 0 2 : 2 = 1, Zb. 0 1 : 2 = 0, Zb. 1
0,625 . 2 = 1,250 0,250 . 2 = 0,500
10010,101
0,500 . 2 = 1,000
Číselné kódy Přímý kód
39
znaménko absolutní hodnota
Inverzní kód
- 39
39
- 39
záporné + 2n - 1
Doplňkový kód záporné + 2n
39
- 39
5
21.9.2014
Realizace sčítání
znaménko 39= 0 0 1 0 0 1 1 1
Včetně znaménkových bitů.
-39=
1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0
přenos
Problém přetečení rozsahu zobrazitelných čísel (přeplnění) – zdvojení znamének znaménko 39= 0 0 0 1 0 0 1 1 1 -39= 1 1 1 0 1 1 0 0 1
znaménko 127= 0 0 1 1 1 1 1 1 1 1= 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
hodnota znaménka nestejná hodnota znaménka přenos stejná ukazuje na správný výsledek přenos ukazuje na přetečení rozsahu
Čísla s pevnou řádovou čárkou Omezená velikost celé části. Omezená přesnost (počet desetinných míst). zn. 22 21 20 2-1 2-2 2-3 2-4 2,625 poloha řádové čárky
2,6
Čísla s pohyblivou řádovou čárkou Tvar m.2e, kde je m – mantisa | m | < 1 e – celočíselný exponent Normování mantisy 0,5 m < 1 zn. 2
-1
2
-2
2
-3
2
-4
zn. 2
1
2
0
+2
2,625 = 0,65625 . 2
0
1
0
1
mantisa
0
0
1
0
= 2,5
exponent
Skrytý bit (výsledek normování) Uložení hodnoty 0, exponent + 2n-1
6
21.9.2014
Zaokrouhlovací chyby při výpočtech na počítači neplatí základní matematické zákony (distributivní a asociativní zákon): (a + b) + c a + (b + c) A = 0,1234567 B = 2381,325 A+B= 2381,448
Kahanův trik pro B > A B = 2381,325 -(A+B) = 2381,448 B -(A+B) = - 0,123 A = 0,1234567 (B-(A+B))+A = 0,0004567
má kumulativní charakter
Kumulace chyb
Průběh odchylky při načítání hodnoty 0,1 binárně s přesností 24 binárních míst 30 25
odchylka
20 15 10 5 0 0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
krok
změna gradientu ovlivněna zejména změnou exponentu uložení průběžného součtu
Důsledky kumulace chyb Ekvivalentní algoritmy I = 0 DX = 0,1 X = 0 While Not I=1000 { tělo} X = X + DX I = I + 1 End While Algoritmus proběhne 1000x Pro X = 0; 0,1; 0,2; …; 99,9
DX = 0,1 X = 0 While Not X=100 { tělo} X = X + DX End While
Algoritmus bude probíhat až do přeplnění X
7
21.9.2014
Číselné kódy x0 x0
x x př 1 x
Přímý kód
Inverzní kód
x 1
x x0 xinv n 2 2 x x0
x 1
Doplňkový kód x xdop 2 x
x0 1 x 1 x0
Přesnost uložení čísel Počítačové epsilon - nejmenší číslo, zobrazitelné v daném číselném kódu, pro které platí 1,0 + > 1,0 Norma uložení IEEE 754 (formát single) 1
8
zn
exponent + 127
23 mantisa
Typické datové formáty Single 4 B – 7 desetinných míst Double 8 B – 15 desetinných míst Extended 10 B – 19 desetinných míst
Datum a čas Datum celá část čísla, počet dnů od referenčního datumu (1. 1. 1900).
Čas desetinná část čísla, 1 den = 24 hodin => 1 hodina = 1/24
Výpočty s datumy Problém testování rovnosti datumu a času
8
21.9.2014
Složené datové typy Pole (posloupnost prvků stejného datového typu). identifikace pořadím prvku, u vícerozměrného pomocí mapovacích funkcí …
Adresa 1
2
3
4
n
Záznam (množina prvků různých datových typů). identifikace názvem prvku
9
