Informacja  podstawowe pojęcia i teoria informacji
TECHNOLOGIA INFORMACYJNA
PODSTAWOWE POJ
CIA
Òð Informacja (Å‚ac. informatio - wyobrażenie, pojÄ™cie)
to pojęcie o wielu definicjach w różnych
dziedzinach.
Òð Zasadniczo mamy dwa podstawowe punkty
widzenia na informacjÄ™:
Éð Pierwszy, który można nazwać obiektywnym
(wywodzącym się z nauk ścisłych), gdzie informacja
oznacza pewną własność fizyczną lub strukturalną
obiektów
Éð Drugi, subiektywny (kogniwistyczny), gdzie informacjÄ…
jest to, co umysł jest w stanie przetworzyć i wykorzystać
do własnych celów.
INFORMACJA SUBIEKTYWNA
Òð W tym ujÄ™ciu informacja jest indywidualnÄ… lub
grupowÄ… interpretacjÄ… otrzymanego ciÄ…gu
sygnałów i musi zawsze opisywać stan jakiejś
dziedziny.
Òð Informacja jest przetwarzana przez naszÄ… wiedzÄ™ i
w wyniku daje innÄ… informacjÄ™ lub nowÄ… wiedzÄ™. W
zależności od tzw. indywidualnego systemu
konceptualizacji, ten sam ciąg sygnałów/znaków
może być z
ródłem różnych informacji dla różnych
osób lub robotów.
INFORMACJA OBIEKTYWNA
Òð W teorii informacji Shannona, informacja jest
mierzona jako prawdopodobieństwo zajścia
zdarzenia. Zdarzenia mniej prawdopodobne dajÄ…
więcej informacji
Òð PodejÅ›cie obiektywne pomija znaczenie
(semantykÄ™), jakie niesie komunikat, a skupia siÄ™
jedynie na jego składni (syntaktyce).
Òð Jeżeli danymi nazywamy wszystko to co jest
przetwarzane, to informacja jest danymi, ale nie
każde dane sÄ… informacjÄ… (np. 5 a 5°C)
POSTAĆ PRZETWARZANEJ INFORMACJI
Òð Współczesne systemy informacyjne to >
przeważającej części systemy cyfrowe operujące
na sygnałach cyfrowych będących dyskretną
reprezentacją danych ze świata rzeczywistego -
determinantÄ… tego trendu sÄ… systemy
komputerowe w swojej naturze będące binarną
podgrupą systemów cyfrowych.
Òð Reprezentacja informacji ograniczona jest tu do
zaledwie dwóch stanów znamiennych umownie
oznaczanych wartościami 0 i 1 - pojedynczy
symbol (bit) pozwala na reprezentowanie
informacji typu Prawda Fałsz, Tak - Nie itp.
POSTAĆ ANALOGOWA A CYFROWA
Òð Przebieg napiÄ™cia jest sygnaÅ‚em ciÄ…gÅ‚ym, ponieważ
może przyjmować dowolną wartość z określonego
zakresu zmienności. Tak prosta definicja sygnału
analogowego jest w zupełności wystarczająca dla
potrzeb analizy systemów przetwarzania danych
Òð UrzÄ…dzenia transmisji danych wykorzystujÄ… sygnaÅ‚y
cyfrowe, które mogą znajdować się w jednym z
możliwych stanów znamiennych ze skończonego
zbioru stanów.
Òð Szczególnym przypadkiem sygnaÅ‚u cyfrowego jest
sygnał binarny przyjmujący tylko dwie wartości (np.
poziomy napięcia 0 i 5V)
POSTAĆ ANALOGOWA A CYFROWA
Òð Poniższy rysunek przedstawia sygnaÅ‚ cyfrowy, który
przyjmuje jeden z dwóch stanów +5 V lub 0 V, jest to
zatem przykład sygnału binarnego
Òð SygnaÅ‚ skÅ‚ada siÄ™ z binarnych elementów, nazywanych
bitami, o czasie trwania równym T sekund (elementowa
podstawa czasu). Jeżeli napięcie +5 V reprezentuje stan
binarny  1", a napięcie 0 V stan binarny  0" (dodatnia
konwencja logiczna), to sygnał cyfrowy z rysunku
odpowiada sekwencji binarnej  1011".
BUDOWA BAJTU
Òð Pojedynczy symbol binarny może odpowiadać 21=2
stanom, a zatem informacja, którą przenosi to nic
innego jak  włączony/wyłączony ,  prawda/fałsz
itp.
Òð Jeżeli chcemy przekazywać wiÄ™kszÄ… ilość
informacji użytecznej, grupujemy pojedyncze bity w
grupy zawierające osiem bitów, nazywane bajtami
Òð PrzyporzÄ…dkowanie każdemu bajtowi, a wiÄ™c
każdej sekwencji ośmiu bitów, jednego znaku
pozwala przekazywać użyteczne informacje.
PrzyporzÄ…dkowanie to jest znane pod nazwÄ…
kodowania
BUDOWA BAJTU
Òð 256 kombinacji oÅ›miu bitów w zupeÅ‚noÅ›ci wystarcza do
oznaczenia wszystkich klawiszy w klawiaturze
komputerowej
Òð Podobnie jak w notacji dziesiÄ™tnej poÅ‚ożenie
poszczególnych bitów w liczbie dwójkowej ma istotne
znaczenie: bit o numerze 0 generuje wkład 20=1 w
wartość liczby dwójkowej, bit 3 generuje wkład 23=8, itd.
BUDOWA BAJTU
Òð Dla powyższego przykÅ‚adu mamy:
Éð Pomijamy wszystkie bity o wartoÅ›ci 0 (bit
0,2,3,4,5,6)
Éð Dla pozostaÅ‚ych realizujemy sumÄ™ ich  wartoÅ›ci": bit
o numerze 1 generuje wkład 21 = 2 w wartość liczby
dwójkowej, bit 7 generuje wkład 27 =128.
Éð Suma wartoÅ›ci to 2 + 128 = 130 - czyli sekwencja
1000010 w systemie dwójkowym jest równoważna
liczbie 130 w systemie dziesiętnym
BUDOWA BAJTU
Òð W wielu zastosowaniach praktycznych
wykorzystywane są grupy 4 bitów w szczególności
w szesnastkowym systemie liczbowym
(oznaczanym hex od hexadecimal) z podstawÄ…
rozwinięcia równą 16
Òð W takim ujÄ™ciu bity 7..4 nazywa siÄ™ górnym
półbajtem, natomiast bity 3..0 dolnym półbajtem
Òð W notacji szesnastkowej sekwencjÄ™ 1000001
interpretujemy jako
1000 0010 czyli 82 hex ( = 130 dec)
Òð W systemach komputerowych o Unix'owych
 korzeniach" często wykorzystywany jest system
ósemkowy (octalny, oznaczany skrótem oct)
KODY ZNAKOWE
Òð Kody znakowe sÅ‚użą do kodowania zbioru znaków lub
symboli, na przykład znaków występujących na
klawiaturze komputerowej
Òð Efektywna komunikacja nie jest możliwa, jeżeli
wymieniające informację urządzenia nie będą
interpretować kombinacji kodowych dokładnie w ten
sam sposób
Òð  ASCII jest skrótem od American Standard Code for
Information Interchange - Standardowy Kod
Amerykański dla Wymiany Informacji.
Òð Kod ASCII zostaÅ‚ opracowany przez ANSI (ang. American
National Standards Institute -Amerykański Instytut
Normalizacji), a z upływem czasu uzyskał powszechną
akceptację na aronie międzynarodowej.
KODY ZNAKOWE
Òð Kod ASCII wykorzystuje 7-bitowe kombinacje kodowe do
reprezentacji następujących znaków:
Litery duże ABCD...Z
Litery małe abcd...z
Cyfry 0123...9
Znaki interpunkcji ,.!:;?
Znaki specjalne ESC CTRL STX ETX XON XOFF itp.
Òð Dosyć czÄ™sto kod ASCII jest traktowany jako podstawa
do kodów ośmiobitowych
Òð W komputerach IBM PC dodatkowych 128 kombinacji
bitów służy do kodowania znaków graficznych oraz
znaków narodowych
KODOWANIE y
RÓDA
OWE
Òð Zadaniem nadajnika jest przeksztaÅ‚cenie danych
z
ródłowych do postaci przystosowanej do transmisji w
kanale telekomunikacyjnym
Òð Celem operacji jest maksymalizacja szybkoÅ›ci transmisji
danych, a to nie zawsze jest równoznaczne z szybkością
transmisji informacji
Òð Jeżeli informacje generowane przez z
ródło zawierają
nadmiar, odpowiednia kompresja danych może skrócić
przekazywane wiadomości
Òð Prostym przykÅ‚adem jest transmisja pliku tekstowego
pomiędzy dwoma komputerami, gdzie modem z
ródłowy
usuwa nadmiarowe bajty danych jeszcze przed ich
transmisjÄ….
KODOWANIE y
RÓDA
OWE
Òð Załóżmy że przesÅ‚any plik zawiera ciÄ…g znaków
Òð NUMER RACHUNKU~~~~~~~SALDO,
gdzie ~ oznacza znak spacji.
Òð Nadajnik przekazuje tÄ™ sekwencjÄ™ w postaci
NUMER RACHUNKU$7SALDO,
gdzie znak $ jest znakiem usuwania spacji.
Òð Odbiornik po napotkaniu symbolu specjalnego $
wykonuje operacjÄ™ odwrotnÄ… do nadajnika
odtwarzając w ten sposób sekwencję pierwotną (w
tym przypadku dodaje 7 spacji)
KODOWANIE y
RÓDA
OWE  ALFABET MORSE A
Òð Wynaleziony w 1830 r. przez amerykaÅ„skiego
malarza-portrecistÄ™ Samuela F.B. Morse'a
Òð Pierwszy próbny przekaz odbyÅ‚ siÄ™ w 1844 r
pomiędzy miastami Washington a Baltimore
Òð W systemie tym poszczególnym symbolom
przypisane są określone sekwencje kropek i
kresek.
Òð Czas trwania kropki traktuje siÄ™ jako jednostkÄ™
czasu w strukturze sygnału. Kreska odpowiada
trzem kropkom. Odstęp pomiędzy znakami to 3
kropki, słowa oddziela się przerwą o długości 3
kresek
ALFABET MORSE A
DETEKCJA BA

DÓW - PARZYSTOŚĆ
Òð Parzystość umożliwia wykrywanie pewnych bÅ‚Ä™dów, które
mogą pojawić się w wiadomości przekazywanej od
nadajnika do odbiornika. W celu skorygowania błędu
zniekształcony znak musi być przesłany jeszcze raz
Òð Pojedynczy bit parzystoÅ›ci jest wystarczajÄ…cy do detekcji
błędów w wiadomościach o długości nie przekraczającej
ok. 12 bitów
Òð Wszystkie schematy wykrywania i korekcji bÅ‚Ä™dów
opierajÄ… siÄ™ na dodawaniu do przekazywanej
wiadomości redundancji umożliwiającej po stronie
odbiorczej rozróżnienie wiadomości uszkodzonych od
poprawnych
DETEKCJA BA

DÓW - PARZYSTOŚĆ
Òð Bez uzupeÅ‚niajÄ…cej redundancji każda wiadomość musi
zostać uznana za poprawną gdyż nie ma sposobu na
rozróżnienie wiadomości uszkodzonych od poprawnych
Òð Rozważmy dla przykÅ‚adu zdanie  pits miaÅ‚ ogon , które
bez trudu odczytamy jako  pies miał ogon . Język polski
zawiera redundancję, co umożliwia wykrywanie
przekłamań oraz ich korekcję
Òð Jeżeli jednak  pits miaÅ‚ ogon" nie jest zdaniem, a tylko
ciÄ…giem przypadkowych kombinacji dowolnych czterech
liter (tzn. usunęliśmy redundancję), nie istnieje sposób
stwierdzenia, czy kombinacje są poprawne czy też nie.
DETEKCJA BA

DÓW - PARZYSTOŚĆ
Òð Kontrola parzystoÅ›ci polega na dodaniu do
przekazywanej wiadomości tzw. bitu parzystości w taki
sposób, że przekazywana wiadomość zawiera albo
parzystą, albo nieparzystą liczbę jedynek, w zależności
od tego, czy jest stosowana normalna czy negatywna
kontrola parzystości.
Òð Kontrola parzystoÅ›ci umożliwia detekcjÄ™ dowolnej
nieparzystej liczby błędów
Òð Kontrola parzystoÅ›ci dodaje redundancjÄ™ wystarczajÄ…cÄ…
do wykrycia przypadku przekłamania informacji nie daje
natomiast możliwości korekty wykrytego błędu w inny
sposób niż poprzez ponowne przesłanie zniekształconej
informacji
DETEKCJA BA

DÓW - CIEKAWOSTKA
Òð ProszÄ™ szybko przeczytać poniższe akapity:
Òð Zdognie z nanjwoymszi baniadmai
perzporawdzomyni na bytyrijskch uweniretasytch
nie ma zenacznia kojnolesc Itier przy zpiasie
dengao solwa.
Òð Nwajzanszyeim jest, aby prieszwa i otatsnia Iteria
była na siwom mijsecu, ptzosałoe mgoą być w
niaedziłe i w dszalym cąigu nie pwinono to
sawrztać polbemórw ze zozumierniem tksetu.
Òð Dzijee sie tak datgelo, ze nie czamyty wyszistkch
Iteir w sołwie, ale cłae sołwa od razu.
TEORIA INFORMACJI
Òð Teoria informacji dostarcza odpowiedzi na
fundamentalne pytanie inżynierii informacyjnej:
czym jest informacja?
Òð PierwszÄ… zasadÄ… jaka funkcjonuje w teorii
informacji jest fakt, iż teoria informacji nie
interesuje siÄ™ wagÄ… czy znaczeniem
przypisywanym przez nas do wiadomości (zatem
informacjÄ™  wylÄ…dowali kosmici traktujemy na
równi z  przypaliłeś grzankę )
Òð DrugÄ… istotnÄ… prawidÅ‚owoÅ›ciÄ… jest zasada iż
zaskakująca nas wiadomość niesie ze sobą duży
ładunek informacyjny, wiadomość oczekiwana
dostarcza nam niewiele informacji.
TEORIA INFORMACJI
Òð Zawartość informacyjna wiadomoÅ›ci (I) w teorii
informacji jest wielkością nieujemną, I >= 0.
Òð KorzystajÄ…c z rachunku prawdopodobieÅ„stwa
możemy przypisać wiadomości oczekiwanej duże
prawdopodobieństwo odbioru (wiadomość
prawdopodobna), natomiast wiadomości
zaskakującej małe prawdopodobieństwo
(wiadomość nieprawdopodobna)
Òð PrawdopodobieÅ„stwo (P) jest miarÄ… przypisywanÄ…
zdarzeniu, przyjmującą wartości z zakresu
1 e" P e" O, przy czym P = 0 oznacza zdarzenie
nieprawdopodobne, przy P = 1 zdarzenie jest
pewne
TEORIA INFORMACJI
Òð WystÄ…pienie zdarzenia pewnego nie powie nam
niczego nowego, a więc jeżeli P = 1, to również
I = 0. Wystąpienie zdarzenie niemożliwego niesie
nieskończoną ilość informacji, tzn. przy
P = 0 mamy także I = ".
Òð Zawartość informacyjna jest mierzona w bitach, a
związek pomiędzy zawartością informacyjną (I)
wiadomości, a prawdopodobieństwem (P) jego
nadania wyraża zależność:
1
I log2
P
TEORIA INFORMACJI
Òð Rozważmy doÅ›wiadczenie o dwóch możliwych
wynikach A oraz B, pojawiajÄ…cych siÄ™ z
jednakowym prawdopodobieństwem, odpowiednio
PA oraz PB. StÄ…d:
Òð PA + PB = 1, oraz PA = PB = 0,5.
Òð Zawartość informacyjna wiadomoÅ›ci podajÄ…cej
otrzymany wynik doświadczenia wynosi
I = Iog2(1/0,5) = 1 bit, zatem taka wiadomość
może być przekazana za pomocą jednego bitu
Òð Jeżeli prawdopodobieÅ„stwa zdarzeÅ„ nie sÄ…
jednakowe, ilość informacji zawartej w
pojedynczym znaku binarnym jest mniejsza od
jednego bitu
TEORIA INFORMACJI
Òð Åšrednia zawartość informacyjna wiadomoÅ›ci
jest znana pod nazwÄ… entropii (H).
Òð Rozważmy ponownie dwa zdarzenia A oraz B, o
niekoniecznie jednakowych
prawdopodobieństwach PA oraz PB ich
wystÄ…pienia:
1 1
H PA log2 PB log2
PA PB
Òð StÄ…d ponieważ PB = 1 - PA otrzymujemy:
1 1
H PA log2 1 PA log2
PA 1 PA
TEORIA INFORMACJI
Òð Na poniższym rysunku przedstawiono wykres
średniej zawartości informacyjnej (H)
przekazywanej w pojedynczym znaku binarnym w
funkcji prawdopodobieństwa PA, przy założeniu
bezpamięciowości z
ródła:
TEORIA INFORMACJI
Òð W przypadku n jednakowo prawdopodobnych
wiadomości prawdopodobieństwo każdej z nich
wynosi P = 1/n, a zawartość informacyjna przypisana
do każdej wiadomości jest równa
I = log2(n) bitów
Òð Jeżeli wiadomoÅ›ci nie sÄ… jednakowo prawdopodobne,
zawartość informacyjna przypisana poszczególnym
wiadomościom jest równa:
1
Ii log2
Pi
Òð Oczekiwana ilość informacji przekazywanej przez
wiadomość wynosi:
n n
1
.
H PiIi Pi log2 bitów
Pi
i 1 i 1
KODOWANIE HUFFMANA
Òð Jest jednym z możliwych zastosowaÅ„ teorii
informacji, mającym na celu powiększenie
szybkości transmisji informacji poprzez eliminację
redundancji w przekazywanej informacji.
Òð Rozpatrzmy przykÅ‚ad:
KODOWANIE HUFFMANA  TWORZENIE DRZEWA
Òð W każdym kroku procedury kodowania Huffmana
zmniejszamy ilość uwzględnianych jeszcze symboli
o jeden poprzez połączenie dwóch symboli o
najmniejszych prawdopodobieństwach.
Òð Dla danych z rysunku w pierwszym kroku należy
połączyć symbole E oraz F w symbol złożony
 E lub F o prawdopodobieństwie wystąpienia 0,2
Òð Symbole zÅ‚ożone należy ustawiać w kolejnych
kolumnach (kolejne etapy) możliwie jak najwyżej.
Òð ProcedurÄ™ tÄ™ powtarzamy tak dÅ‚ugo, aż w kolumnie
pozostaną dokładnie dwa symbole.
KODOWANIE HUFFMANA  TWPRZENIE
SA
OWNIKA NA PODSTAWIE DRZEWA
Òð W utworzonym drzewie każde dwa Å‚Ä…czone
symbole oznaczamy arbitralnie 1 lub O
(ostatnie elementy każdej kolumny).
Òð Po zakoÅ„czeniu procedury należy z otrzymanego
diagramu odczytać słowa kodowe przypisane do
poszczególnych symboli poruszając się od
 korzenia do  liści utworzonego drzewa
Òð PrzykÅ‚adowo symbolowi A zostaje
przyporządkowane słowo kodowe 01
Òð Utworzony w ten sposób sÅ‚ownik ma dodatkowÄ…
cechę: żaden z jego symboli kodowych nie jest
prefiksem któregokolwiek innego symbolu