Microsoft PowerPoint - 04-reprezentacja informacji.pptx

Reprezentacja podstawowych

informacji w systemach

informatycznych dla medycyny

Wykład nr 4 z kursu IT dla

Inżynierii Biomedycznej

prowadzonego przez

Prof. Ryszarda Tadeusiewicza

Komputery nie są urządzeniami, które
istnieją „same dla siebie”.

Ich użyteczność wynika z tego, że z pomocą technologii informacyjnych
można:

• rejestrować,

• ewidencjonować,

• opisywać,

• badać,

• analizować,

• sterować

• i przewidywać...

różne fakty dotyczące rzeczywistego świata.

Aby to było możliwe – fakty te trzeba właściwie

odwzorowywać

w rejestrach

i pamięciach systemów komputerowych. Przywołuje to problem

Reprezentacja informacji w systemach
komputerowych

Wszelkie informacje przetwarzane,
przechowywane oraz przesyłane
w systemach komputerowych mają postać
binarną

Jeśli są to dane liczbowe, to są ona zapisane w
systemie dwójkowym, czyli w systemie
pozycyjnym o podstawie 2

Jeśli są to dane inne niż wartości liczbowe, to są
one

kodowane za pomocą symboli binarnych.

Sygnały (dźwięki, obrazy, rejestracje EKG itd. są
umieszczane w komputerze jako tablice liczb.

Pozycyjne systemy liczenia (1)

Każda liczba całkowita N ≥

≥

≥ 2 może być

podstawą systemu liczenia (mówimy
wówczas o systemie o podstawie N).

System dziesiętny (system o podstawie

System dziesiętny (system o podstawie
równej 10) jest przykładem pozycyjnego
systemu liczenia

System binarny jest także przykładem

pozycyjnego

systemu liczenia

Pozycyjne systemy liczenia (2)

Do zapisu liczb wykorzystywane są cyfry:

w systemie dwójkowym: 0, 1;

w systemie dziesiętnym: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

w systemie ósemkowym: 0, 1, 2, 3, 4, 5, 6, 7;

w systemie szesnastkowym: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

w systemie szesnastkowym: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
A, B, C, D, E, F;

w systemie o podstawie N: 0, 1, ..., N - 1

Cechą charakterystyczną systemów pozycyjnych jest
to, że wartość cyfry uzależniona jest od jej pozycji.

Obliczanie wartości liczby (1)

system dziesiętny (system o podstawie 10)

353

(10)

= 3 * 100 + 5 * 10 + 3 * 1 = 3 * 10

5 * 10

+ 3 * 10

5 * 10 + 3 * 10

2,4

(10)

= 2 * 1 + 4 * 0,1 = 2 * 10

+ 4 * 10

-1

∑

⋅

Obliczanie wartości liczby (2)

System dwójkowy (system o podstawie 2)

Analizowana liczba 101,11

(2)

∑

⋅

Obliczanie wartości liczby (3)

Uogólnienie:

System o podstawie N

∑

⋅

System szesnastkowy

dzielimy liczbę binarną na grupy po 4 cyfry -
w lewo i prawo rozpoczynając od pozycji
separatora dziesiętnego;

wartość każdej wydzielonej grupy zapisujemy

wartość każdej wydzielonej grupy zapisujemy
za pomocą jednej cyfry szesnastkowej.

Przykład:

1111100000

(2)

= ?

(16)

0011 | 1110 | 0000 = 3E0
1111100000

(2)

= 3E0

(16)

Przyczyny stosowania systemu
szesnastkowego

znacznie większa zwięzłość zapisu w
porównaniu z zapisem binarnym (4 cyfry
binarne = 1 cyfra szesnastkowa)

prosta konwersja pomiędzy systemem

prosta konwersja pomiędzy systemem
binarnym i szesnastkowym

liczba bitów w jednej komórce jest zwykle
wielokrotnością liczby 4, co znacznie ułatwia
przedstawienie jej zawartości w systemie
szesnastkowym.

Reprezentacja liczb całkowitych (1)

liczby całkowite bez znaku

na kolejnych bitach przechowywane są
poszczególne cyfry binarne

Np. liczba 41

(10)

w komórce ośmiobitowej

(10)

przechowywana jest w następujący sposób:

Reprezentacja liczb całkowitych (2)

prosta reprezentacja liczb całkowitych ze
znakiem (reprezentacja typu znak-moduł,
reprezentacja bezpośrednia)

Kodowanie informacji o znaku:

plus

minus

Np. liczba -41 w komórce ośmiobitowej
przechowywana jest w następujący sposób:

Reprezentacja liczb całkowitych (3)

Wady reprezentacji znak-moduł:

możliwe są dwa sposoby reprezentacji zera:

10000000

00000000

występują problemy przy realizacji obliczeń na
liczbach ujemnych (np. -2 + 3)

10000010

(-2)

00000011

(+3)

10000101

(-5)

Reprezentacja liczb całkowitych (4)

kod uzupełnieniowy

Kod uzupełnieniowy służy do reprezentacji
liczb całkowitych:

liczby całkowite nieujemne przyjmują

postać:

bit znaku, moduł liczby

Reprezentacja liczb całkowitych (6)

Pojęcie „uzupełnienia do dwóch”

Uzupełnieniem do dwóch dodatniej liczby binarnej b zapisanej

na N bitach jest wartość u wyrażona wzorem:

u = 2

– b.

Należy zauważyć, że 2

jest wartością większą o jeden od

największej liczby zapisanej na N bitach – czyli liczby

składającej się z N jedynek.

Przykład:

Niech N = 4.
Poszukujemy uzupełnienia do dwóch liczby b = 0011

(2)

= 3

(10)

= 2

= 16

(10)

= 10000

(2)

– b = 16

(10)

– 3

(10)

= 13

(10)

= 1101

(2)

Uzupełnieniem do dwóch liczby 0011

(2)

jest 1101

(2)

Reprezentacja liczb całkowitych (8)

Zamiana pomiędzy reprezentacją w kodzie
prostym i uzupełnieniowym

zapis liczby dodatniej w kodzie prostym i
uzupełnieniowym jest identyczny;

konwersja liczby ujemnej z zapisu w kodzie
prostym na kod uzupełnieniowy (lub z kodu
uzupełnieniowego na prosty):

dokonaj negacji wszystkich bitów z wyjątkiem bitu
znaku,

do otrzymanej wartości dodaj (binarnie) jedynkę.

Reprezentacja liczb całkowitych (9)

Przykład:

Przedstaw sposób reprezentacji w kodzie
uzupełnieniowym w komórce 8-bitowej liczby
-41

(10)

-41

(10)

10101001

(2)

kod prosty

11010110

(2)

negacja wartości (bez bitu znaku)

00000001

(2)

jedynka

11010111

(2)

suma (wart. w kodzie uzupeł.)

Reprezentacja liczb całkowitych (10)

Zamiana wartości z kodu uzupełnieniowego na
system dziesiętny

Kolejnym pozycjom przypisywane są
współczynniki będące kolejnymi potęgami liczby 2,
przy czym współczynnik odpowiadający pozycji

przy czym współczynnik odpowiadający pozycji
wysuniętej najbardziej w lewo (bit znaku)
uwzględniany jest ze znakiem minus

Przy konwersji na system dziesiętny sumowane
są współczynniki znajdujące się na pozycjach
jedynek w rozpatrywanej liczbie binarnej.

Reprezentacja liczb całkowitych (13)

Kod uzupełnieniowy:

trudny do stosowany dla człowieka,

ułatwia wykonywanie działań na liczbach
całkowitych ze znakiem - w trakcie obliczeń bit

znaku jest traktowany w taki sam sposób jak
pozostałe bity.

Reprezentacja liczb całkowitych (14)

Przykład

-2 + 3
-2

10000010

(kod prosty)

11111101

(negacja, bez bitu znaku)

00000001

(jedynka)

11111110

(kod uzupełnieniowy)

11111110

(kod uzupełnieniowy)

00000011

(kod prosty)

00000011

(kod uzupełnieniowy)

-2 + 3

11111110

(-2, kod uzupełnieniowy)

00000011

(+3, kod uzupełnieniowy)

1 00000001

(wynik, kod uzupeł., bit przeniesienia jest ignorowany)

00000001

(wynik, kod prosty)

Reprezentacja liczb całkowitych (15)

Cechy maszynowej reprezentacji liczb całkowitych:

w systemach komputerowych mogą być reprezentowane

wartości całkowite z pewnego zakresu - uzależnionego od:

liczby bitów przeznaczonych na przechowywanie jednej

wartości numerycznej,

przyjętego sposobu reprezentacji.

wartości całkowite mieszczące się w dopuszczalnym

zakresie przechowywane są w sposób dokładny

wyniki obliczeń realizowanych na liczbach całkowitych są

dokładne (pod warunkiem, że mieszczą się na przyjętej

liczbie bitów)

podstawowym problemem mogącym pojawić się w trakcie

obliczeń na liczbach całkowitych jest błąd nadmiaru -

powstaje wtedy, gdy wynik nie mieści się na przyjętej liczbie

bitów

ilość
bitów

nazwa

zakres

char

−128 — +127 (ze znakiem)
0 — +255 (bez znaku)

short int

−32 768 — +32 767 (ze znakiem)

short int

0 — +65 535 (bez znaku)

int, long int

−2 147 483 648 — +2 147 483 647 (ze znakiem)
0 — +4 294 967 295 (bez znaku)

long long int

−9 223 372 036 854 775 808 — +9 223 372 036 854 775 807
(ze znakiem)
0 — +18 446 744 073 709 551 615 (bez znaku)

Reprezentacja liczb rzeczywistych (1)

Do reprezentacji wartości rzeczywistych
stosuje się:

reprezentację stałopozycyjną
(stałoprzecinkową),

reprezentację zmiennopozycyjną
(zmiennoprzecinkową, półlogarytmiczną).

Reprezentacja liczb rzeczywistych (2)

Reprezentacja stałopozycyjna:

do przechowania jednej wartości rzeczywistej
wykorzystuje się N bitów,

bit najbardziej wysunięty w lewo przechowuje

informację o znaku liczby (0 - dodatnia, 1 -
ujemna)

liczba bitów służących do przechowania
części całkowitej i części ułamkowej jest stała
(stała jest pozycja separatora dziesiętnego -
stąd określenie stałopozycyjny).

Reprezentacja liczb rzeczywistych (4)

Cechy reprezentacji stałopozycyjnej:

w systemie komputerowym mogą być przechowywane wartości

rzeczywiste z pewnego zakresu,

komputerowa reprezentacja liczb rzeczywistych ma charakter
dyskretny (a nie ciągły),

0.00000000(2) = 0

(10)

0.00000000(2) = 0

(10)

0.00000001(2) = 1*2

-8

= 1/256 = 0,00390625

0.00000010(2) = 1 * 2

-7

= 1/128 = 0,0078125

0.00000011(2) = 1 * 2

-7

+ 1 * 2

-8

= 0,01171875

......

więc np. liczba 0,005

(10)

= 0,0000000101...

(2)

Liczby rzeczywiste

nie są

przechowywane w sposób dokładny!!!

Reprezentacja liczb rzeczywistych (5)

Cechy reprezentacji stałopozycyjnej:

pamięć przeznaczona do przechowywania wartości

rzeczywistej nie jest wykorzystywana w sposób

optymalny

np. wartość 0,0000011111 przechowywana jest

np. wartość 0,0000011111

(2)

przechowywana jest

jako:

00000000000000000000000

00000111

Pominięte zostały dwie ostatnie cyfry, a część

przeznaczona na przechowywanie części

całkowitej nie jest wykorzystana!

Reprezentacja liczb rzeczywistych (7)

Reprezentacja zmiennopozycyjna

(zmiennoprzecinkowa, półlogarytmiczna)

Każda liczba rzeczywista X może być

przedstawiona w postaci:

X = mantysa * 2

cecha

X = mantysa * 2

cecha

gdzie:
mantysa jest wartością rzeczywistą (dodatnią lub

ujemną),

cecha jest wartością całkowitą (dodatnią lub ujemną).

Stosując reprezentację zmiennopozycyjną w

systemie komputerowym przechowywana jest

mantysa oraz cecha liczby.

Liczby rzeczywistej mogą być w pojedynczej (float)

i w podwójnej (double) dokładności (wg. norm IEEE 754)

Załóżmy, że m to liczba cyfr przeznaczonych na mantysę, natomiast n+1 to liczba
cyfr przeznaczonych na wykładnik (n cyfr dla wartości i 1 dla znaku wykładnika).

Uznaje się również, że jedna dodatkowa pozycja (najstarsza) zarezerwowana

jest dla zapisu znaku całej liczby. Wówczas wartości maksymalne i minimalne dla
M i E określone są następująco:

Wykładnik E:

min

= − B

+ 1

max

= B

− 1

Mantysa M:

min

= 1

max

= B − B

− (m − 1)

Stąd najmniejsza i największa liczba dodatnia
możliwa do zapisania w takiej reprezentacji to:

Jeśli komputer wygeneruje w trakcie obliczeń liczbę o wartości bezwzględnej

|x| < x

min

to uważa się, że jest to wartość błędna (underflow),

zwykle zamieniana na 0

Jeśli komputer wygeneruje w trakcie obliczeń liczbę o wartości bezwzględnej

|x| > x

max

to uważa się, że jest to wartość błędna (overflow) co

zwykle przerywa obliczenia!

Reprezentacja liczb rzeczywistych (9)

Przykładowa liczba: 7(10) = 111(2)

111 = 111 * 2

= 11,1 * 2

= 1,11 * 2

= 0,111 * 2

zawsze wybiera się taki sposób reprezentacji, w
którym mantysa (w zapisie binarnym) zaczyna się od
0,1…. Dzięki temu nie ma potrzeby zapamiętywania

0,1…. Dzięki temu nie ma potrzeby zapamiętywania
znaków „0,”. Prezentacja spełniająca ten warunek
określana jest jako znormalizowana.

Ostatecznie, liczba rzeczywista 7 przechowywana
jest w postaci:

0111000000000011

Reprezentacja liczb rzeczywistych (10)

Cechy prezentacji zmiennopozycyjnej:

zbiór reprezentowanych wartości jest:

ograniczony,

dyskretny,

liczby rzeczywiste nie są przechowywane w

sposób dokładny - szczególnie niebezpieczne

jest kumulowanie się błędów w trakcie

obliczeń,

reprezentacja zmiennopozycyjna pozwala

zwykle na lepsze wykorzystanie pamięci niż

reprezentacja stałopozycyjna.

Reprezentacja liczb rzeczywistych (11)

Wybór pomiędzy reprezentacją stało-
i zmiennopozycyjną

Reprezentacja zmiennopozycyjna:

możliwość reprezentowania wartości z większego
zakresu.

zakresu.

Reprezentacja stałopozycyjna:

wartości reprezentowane są z taką samą
dokładnością (co jest istotne np. w obliczeniach
finansowych).

Reprezentacja znaków

W systemie komputerowym każdy tekst
przechowywany jest w postaci binarnej

Jest to możliwe, ponieważ każdy znak (litera,
cyfra, znak przestankowy itp.) jest zamieniany

cyfra, znak przestankowy itp.) jest zamieniany
w kod znaku (będący liczbą całkowitą).

Liczbami binarnymi są także informacje
sterujące, określające format tekstu (na
przykład wielkość i kolor czcionki, rozmiar
strony, wielkość marginesu itp.)

Kod ASCII

ASCII - American Standard Code for
Information Interchange.

w wersji podstawowej - 7 bitowy (128 znaków)

w wersji rozszerzonej - 8 bitowy (256 znaków)

Kod ASCII – problem polskich
znaków

Znaki specyficzne dla języka polskiego

(ąćęłńóśżźĄĆĘŁŃÓŚŻŹ) przypisane mają kody

większe od 128 utrudnia to proces sortowanie,

wyszukiwania i porządkowania danych!!!

Istnieją różne sposoby kodowania polskich znaków
utrudnia to wymianę dokumentów tekstowych

pomiędzy różnymi systemami.

utrudnia to wymianę dokumentów tekstowych

pomiędzy różnymi systemami.

Podstawowe sposoby kodowania polskich znaków:

MS Windows CP 1250 (Windows Latin-2, Windows-

1250) - sposób kodowania wprowadzony przez firmę

Microsoft wraz z systemem Windows 3.11 PL

ISO Latin-2 (ISO-8859-2, Polska Norma PN-93 T-

42118) - sposób kodowania określony przez ISO,

stosowany powszechnie w Internecie.

Unicode (Unikod)

Unikod (ang. Unicode lub UCS - Universal Character
Set) – sposób kodowania znaków uwzględniający
większości wykorzystywanych znaków w różnych
językach na całym świecie.

Znaki uwzględnione w Unikodzie podzielone zostały

Znaki uwzględnione w Unikodzie podzielone zostały
na:

podstawowy zestaw znaków (określany jako Basic
Multilingual Plane - BMP lub Plane 0) – dla tych
znaków stosowane są kody 16 bitowe;

dodatkowy zestaw znaków – stosowane są kody 32
bitowe.

Reprezentacja unikodów

UTF - Unicode Transformation Format – metody

przechowywania unikodów w pamięci komputera:

UTF-8 – kody znaków wchodzących w skład

podstawowego zestawu ASCII zapisywane są jako

wartości jednobajtowe; pozostałe kody zapisywane są

na dwóch, trzech, czterech, pięciu lub sześciu bajtach

(znaki o kodach zapisywanych na trzech i większej

liczbie bajtów spotykane są we współczesnych

językach bardzo rzadko);

UTF-16 – kody znaków zapisywane są na dwóch,

trzech lub czterech bajtach (najczęściej

wykorzystywane są znaki o kodach dwubajtowych);

UTF-32 – kody znaków zapisywane są na 4 bajtach.

Unicode jest międzynarodowym standardem zbioru
znaków, który może być wykorzystany do pisania
dokumentów w niemalże każdym istniejącym języku.

Wersja 4.0.1 z czerwca 2004 roku zawiera

96 447

znaków z prawie wszystkich języków na świecie.

Unicode z łatwością mieści cały alfabet łaciński, ale
również pismo pochodzenia greckiego, włączając

również pismo pochodzenia greckiego, włączając
starożytne i współczesne odmiany oraz cyrylicę używaną
np. w Serbii.

Prawdopodobnie jedna osoba na milion obywateli świata
obecnie mówi językiem, który nie może być sensownie
przedstawiony w Unicode.

Charakterystyka reprezentacji
bitmapowej

bardzo duże zapotrzebowanie na pamięć,

trudne przekształcenie obrazu (skalowanie,
obrót),

przydatna przy reprezentacji zdjęć (ale nie

przydatna przy reprezentacji zdjęć (ale nie
medycznych!).

Kompresja jako zmiana sposobu
reprezentacji informacji

Kompresja - przekształcenie sposobu
reprezentacji informacji mające na celu
zmniejszenie zapotrzebowania na pamięć
(wewnętrzną, zewnętrzną) przeznaczoną do
jej przechowywania.

jej przechowywania.

Dekompresja - odtworzenie pierwotnego
sposobu reprezentacji informacji.

Rodzaje kompresji

Operacje kompresji i dekompresji najczęściej
dotyczą plików.

Rodzaje kompresji:

bezstratna – plik po dekompresji jest

bezstratna – plik po dekompresji jest
dokładnie taki sam jak plik poddany kompresji
(kompresja tekstów, programów),

stratna – plik po dekompresji jest zbliżony do
pliku poddanego kompresji (kompresja
dźwięku, grafiki, filmów).

Kodowanie Huffmana jako przykład
algorytmu kompresji bezstratnej

metoda kompresji bezstratnej (przydatna do

kompresji tekstów, programów),

metoda ta wykorzystuje różnice

w częstościach występowania

poszczególnych znaków w tekście (krótsze

kody przypisywane są znakom częściej się

pojawiającym, zaś dłuższe znakom rzadko

występującym),

metoda ta wykorzystywana jest

w popularnych programach pakujących

(np. pkzip, arj, rar).

Przykładowe zastosowanie algorytmu
Huffmana (1)

Załóżmy, że:

w tekście występują tylko cztery znaki: A, B, C, D,

długość tekstu wynosi 1000 znaków

Przed kompresją:

do zakodowania jednego znaku potrzebne są 2 bity:

A – 00
B – 01
C – 10
D – 11

do zakodowania tekstu o długości 1000 znaków
potrzebny jest obszar pamięci o wielkości 2000 bitów.

Przykładowe zastosowanie algorytmu
Huffmana (4)

Proces kompresji:

w kolejnych krokach pobiera się dwa

najrzadziej

występujące elementy, łączy w jeden

i umieszcza na odpowiedniej pozycji listy

krok 1 – połączenie elementów D i B

(D, B) (20%)
C

(35%)

(45%)

Przykładowe zastosowanie algorytmu
Huffmana (5)

Proces kompresji:

krok 2 – połączenie (D, B) i C

(45%)

((D, B), C)

(55%)

krok 3 – połączenie A i ((D, B), C)

(A, ((D, B), C)) (100%)

Przykładowe zastosowanie algorytmu
Huffmana (6)

Proces kompresji:

Uzyskany element (A, ((D, B), C)) przedstawia
się w postaci drzewa

się w postaci drzewa

Kody znaków

A – 0
B – 101
C – 11
D – 100

Przykładowe zastosowanie algorytmu
Huffmana (7)

Długość tekstu w postaci skompresowanej

A: 1 * 0.45 * 1000 =  450 bitów
B: 3 * 0.15 * 1000 =  450 bitów
C: 2 * 0.35 * 1000 =  700 bitów

C: 2 * 0.35 * 1000 = 700 bitów
D: 3 * 0.05 * 1000 = 150 bitów
SUMA:

1750 bitów