Teoria informacji i kodowanie
ETEK0025W
Podstawy teorii informacji
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji, Teleinformatyki i Akustyki
pokój 909, C-5
tel. [phone]
e-mail: [e-mail]
www: https://kursy.pwr.wroc.pl/
Slajd 2/34
Literatura z teorii informacji
1. Historia
2. Fakty na temat przesyłu informacji
3. Czym zajmuje się teoria informacji
4. Dyskretne z
ródła informacji
5. Opis kanału telekomunikacyjnego
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 3/34
Historia Teorii informacji
" Twórcą teorii informacji jest Claude E. Shannon
C. E. Shannon,  A Mathematical Theory of Communication , Bell System Technical
Journal, Vol. 27,1948
 kluczowy artykuł dla teorii informacji,
 zapoczątkował jej istnienie i rozwój
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 4/34
Kilka faktów na temat przesyłu
informacji
1. Celem każdego systemu komunikacyjnego jest odtworzenie wiadomości
wyemitowanej ze z
ródła w miejscu, gdzie znajduje się jej odbiorca.
2. Każdy kanał telekomunikacyjny jest zakłócony szumem wobec czego
wierne odtworzenie informacji nadanej ze z
ródła jest niemożliwe.
3. Odbiorca chciałby, aby wiadomość , która do niego dociera jak
najwierniej oddawała wiadomość nadaną ze z
ródła.
4. Z uwagi na ograniczenia wynikające z parametrów kanału, wierność
odtworzenia informacji może być różna.
5. Z uwagi na to, że różni użytkownicy mają różny próg akceptowalności
odtworzenia wiadomości, widomości dzieli się na klasy. Wiadomości
należące do jednej klasy mają jednakowa miarę podobieństwa do
oryginału i z punktu widzenia użytkownika są nierozróżnialne.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 5/34
Przykład klasy informacji
1. Semantyczna zrozumiałość tekstu pisanego. Do zapisu poniższego zdania
zostały użyte różne fonty. Mimo różnych kształtów liter odbiorca jest w
stanie zrozumieć przesłaną wiadomość:
" Rozumiem to co czytam!
" Rozumiem to co czytam
" Rozumiem to co czytam
2. Jeżeli jako kryterium przyjmiemy semantyczną zrozumiałość tekstu, to
wszystkie powyższe zdania należą do jednej klasy
3. Jeżeli jako kryterium przyjmiemy podobieństwo reprezentacji graficznej
do fontu Times New Roman, to zdania te należą do różnych klas.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 6/34
Inny przykład klasy informacji
1. Przyjmijmy że mamy detektor progowy rozpoznający
polaryzację sygnału, tzn., czy sygnał jest większy, czy
mniejszy od napięcia 0 V.
2. Wszystkie sygnały większe od zera bez wgledu na swój
poziom należą w takim układzie do tej samej klasy,
gdyż z punktu widzenia detektora są nierozróżnialne.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 7/34
Czym zajmuje się teoria informacji?
1. Ustala graniczne parametry systemów
telekomunikacyjnych (kodowanie z
ródłowe,
graniczna szybkość transmisji w określonych
kanałach)
2. Podaje wskazówki służące optymalizacji
zaawansowanych systemów telekomunikacyjnych
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 8/34
Model systemu telekomunikacyjnego
y
ródło Kodowanie Koder
Szyfrowanie Modulator
binarne z
ródłowe kanałowy
Zakłócenia +
Ujście Dekodowanie Deszyfro Dekoder
Demodulator
binarne z
rodłowe wanie kanałowy
Kanał telekomunikacyjny
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 9/34
Pojemność kanału-Twierdzenia Shanona
S
C =� W log2ć� +�1��
�� ��
N
W
Ł� ł�
Twierdzenia Shanona-Hartleya
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 10/34
Model systemu telekomunikacyjnego
" y
ródło informacji
 ciągłe lub dyskretne
" y
ródło dyskretne
" wysyła w takt T zegara wiadomość ze skończonego
zbioru M wiadomości elementarnych
" jest stacjonarne (własności statystyczne nie zależą
od czasu) wiadomości generowane z
prawdopodobieństwami niezmiennymi w czasie
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 11/34
Model systemu telekomunikacyjnego
" Koder z
ródłowy
 Reprezentacja wiadomości za pomocą sekwencji
"
symboli elementarnych
 Dążenie do możliwie efektywnej reprezentacji
"
wiadomości za pomocą krótkich bloków symboli
" "Koder kanałowy
 Realizuje zabezpieczenie transmitowanych symboli
"
 przed przypadkowymi błędami w trakcie transmisji
przez wprowadzanie dodatkowych symboli (informacji
nadmiarowej)
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 12/34
Model systemu telekomunikacyjnego
" Dekoder kanałowy
 Odtwarza bloki symboli z wejścia kodera kanałowego, pomimo
błędów w kanale
 Wykorzystanie redundancji (symboli dodatkowych)
" Możliwe trzy sytuacje:
 Prawidłowa rekonstrukcja bloku nadanego  FEC (Forward Error
"
Correction korekcja błędów).
 Detekcja błędów  dekoder ustalił, że wystąpiły błędy, ale nie
"
wie, gdzie one są (ED  Error Detection - detekcja błędów).
 Nieprawidłowa rekonstrukcja bloku nadanego zdarzenie powinno
"
mieć małe prawdopodobieństwo wystąpienia.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 13/34
Poprawa jakości transmisji
Korekcja błędów w przód
y
ródło Koder Kanał Dekoder Odbiorca
dyskretne kanałowy dyskretny kanałowy informacji
Automatyczne żądanie powtórzenia
y
ródło Koder Kanał Detektor Odbiorca
dyskretne kanałowy dyskretny błędów informacji
Żądanie powtórzenia
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 14/34
Pojęcie informacji
" Definicja:
Informacja jest wiedzą otrzymaną przez odbiór
"
wiadomości, która pozwala odbiorcy zrealizować lub
ulepszyć jego działanie
" "Cechy informacji:
 Charakter potencjalny  może być wykorzystana do
"
działania
 Charakter względny  dla jednego odbiorcy jest
"
wartościowa, dla innego nie
 Wiadomość pojęcie pierwotne
"
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 15/34
Teoria informacji
" Dla dyskretnego z
ródła informacji miarą ilości informacji w
wiadomości jest przeciętna liczba bitów niezbędna do
zakodowania wszystkich informacji.
" Formalną miarą ilości informacji w wiadomości jest entropia
tej wiadomości. Mierzy ona nieokreśloność lub
nieprzewidywalność informacji. Im większa entropia, tym
większa jest ilość informacji zawarta w wiadomości. Zerowa
entropia oznacza, że wiadomość nie niesie żadnej informacji.
" Przykład: Wiadomość o treści  Ford T, którego kupiliśmy
wczoraj jest czarny nie niesie informacji o kolorze,
ponieważ Ford T był produkowany tylko w kolorze czarnym.
Przesłana informacja jest z góry zdeterminowana.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 16/34
Entropia
n
Entropia jest dana
H(�X )�=� -� p(�Xi)���log2 p(�Xi )�
��
zależnością:
i=�1
gdzie: X1,...., Xn będą wariantami treści wiadomości
występującymi z prawdopodobieństwami: p(X1),....,
p(Xn) oraz:
n
p(�Xi )�=�1
��
i=�1
Uwzględniając wszystkie wiadomości X, mamy:
ć� ��
1
H(X ) =� -� p(�X )�log2 p(�X )�=� p(�X )�log2��
�� ��
�� ��
p(�X )���
X X
Ł� ł�
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 17/34
Optymalne zakodowanie informacji
Entropia osiąga maksymalna wartość, gdy wszystkie
informacje są jednakowo prawdopodobne.
1
H(�X )�=� max, gdy p(�Xi)�=� , i =�1,....,n
n
Naturalne z
ródła informacji, nie osiągają maksymalnej
.
entropii ze względu na nierównomierne
prawdopodobieństwo występowania zdarzeń.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 18/34
Entropia dla z
ródła sygnałów jednakowo
prawdopodobnych
Dla M symboli jednakowo prawdopodobnych entropia
z
ródła informacji wynosi
M
1
H(X ) =� log2(�M )�=� log2(�M )�bit / symbol
��
M
i=�1
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 19
Przykład dla z
ródła binarnego
1
Mamy binarne z
ródło
informacji
0.8
generujące dwa
0.6
zdarzenia x1, x2 ,
H(p)
takie że:
0.4
P(x1)=p, P(x2)=1-p
0.2
0
0 0.2 0.4 0.6 0.8 1
p
ć� �� ć� ��
1 1
H(�x)�=� p log2�� �� +�(�1-� p)�log2��
�� �� ��1-� p ��
��
p
Ł� ł� Ł� ł�
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 20/34
Przykłady wyznaczania enropii
" Wyznaczanie entropii z
ródła informacji na temat płci
" Wyznaczanie entropii dla z
ródeł o różnym
prawdopodobieństwie symboli
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 21/34
Entropia warunkowa
Entropia warunkowa wieloznaczność jest dana zależnością:
HY (�X )� =� -� p(�X ,Y )��� log2 pY (�X )�
��
X ,Y
n
Niech Y jest wiadomością ze zbioru
p(�Yi )�=�1
��
Y1,...., Yn oraz spełnione jest równanie:
i=�1
p(�X,Y)�=� pY (�X )�p(�y)�
Prawdopodobieństwo łączne
pY (�X )�
Prawdopodobieństwo warunkowe
ć� ��
1
�� ��
HY (�X )�=� -� p(�Y)� pY (�X )�log2��
�� ��
pY (�X )���
Y X
Ł� ł�
G�
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 22/34
Po co stosować koder z
ródłowy
" Koder z
ródłowy stosujemy, aby zminimalizować ilość
przesyłanych bitów w kanale telekomunikacyjnym
" Przesyłanie informacji o płci kodem ASCI wymaga
przesłania:
" 7bajtów -kobieta
" 9bajtów-meżczyzna
" W postaci binarnej tylko 1 bitu
"  0 -kobieta
"  1 -meżczyzna
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 23/34
Optymalne zakodowanie informacji
Entropia osiąga maksymalna wartość, gdy wszystkie
informacje są jednakowo prawdopodobne.
1
H(�X )�=� max, gdy p(�Xi)�=� , i =�1, 2, 3....n
n
Naturalne z
ródła informacji, nie osiągają
maksymalnej entropii ze względu na nierównomierne
prawdopodobieństwo występowania zdarzeń. Np. litera a
występuje w tekście częściej niż litera x.
Strona 23/33
Ó�
Robert Borowiec
Ó�
Robert Borowiec
� Robert Borowiec
Slajd 24/34
Nadmiarowość informacji
" Każde naturalne z
ródło informacji (tekst, obraz,
zapis dz
więku) charakteryzuje się
nadmiarowością (redundancją). .
" Dla każdego z
ródła można określić parametry:
 wskaz
nik bezwzględny języka R
 wskaz
nik względy języka r
 redundancja D=R-r
Strona 24/33
Ó�
Robert Borowiec
Ó�
Robert Borowiec
� Robert Borowiec
Slajd 25/34
Wskaz
nik bezwzględny języka R
Wskaz
nik bezwzględny języka określa maksymalną
liczbę bitów niezbędną do przedstawienia
informacji, która mogłaby być zakodowana w
dowolnym znaku, przy założeniu, że wszystkie
możliwe sekwencje znaków są jednakowo
prawdopodobne. Definiowany jest on zależnością:
,
R =� log2 L
gdzie: L-ilość liter w alfabecie
Strona 25/33
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 26/34
Wskaz
nik względny języka r
Wskaz
nik względny języka określa przeciętną liczbę
bitów na jeden znak informacji. Definiowany jest
zależnością.
H(�X )�
,
r =�
N
gdzie: N-ilość zdarzeń.
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 27/34
Redundancja języka D=R-r
Przykłady: Płeć
Jeżeli zapisujemy płeć słowami: mężczyzna,
kobieta, to:
R =� log2 35 =� 5.13
H(�X )� 1
r(m) =� =� =� 0.11(�1)�
N 9
D =� R -� r =� 5.13-� 0.11(�1)�=� 5.02 bita / znak
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 28/34
Redundancja języka D=R-r
Przykłady: Płeć
Jeżeli zapisujemy płeć binarnie: mężczyzna=1,
kobieta=0, to:
R =� log2 2 =�1
H(�X )� 1
r(m) =� =� =� 1
N 1
D =� R -� r =�1-�1=� 0 bita / znak
Brak redundancji!!!
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 29/34
Optymalne kodowanie informacji
" Optymalną ilość bitów do zakodowania
zdarzenia o prawdopodobieństwie p
wyraża zależność
ć� ��
1
log2�� ��bitów
�� ��
p
Ł� ł�
" Zależność nie mówi nic o sposobie jej
zakodowania, a tylko o ilości bitów
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 30/34
Kod Huffmana
" Optymalne zakodowanie zdarzeń na bitach można
uzyskać za pomocą kodu Huffmana.
" Mamy zdarzenia A, B, C, D, E, F, G o
prawdopodobieństwach:
" P(A)=0.5 , to log2(1/0.5)=1
" P(B)=0.25 , to log2(1/0.25)=2
" P(C)=0.125 , to log2(1/0.125)=3
" P(D)=0.061 , to log2(1/0.063) @� 4
" P(E)=0.032 , to log2(1/0.031)@�5
" P(F)=0.032 , to log2(1/0.0016) @� 5
H(X)=0.5*1+0.25*2+0.125*3+0.061*4+0.032*5+0.032*5=1.939
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 31/34
Kod Huffmana
Posortuj zdarzenia od najmniejszej prawdopodobnego do
najbardziej prawdopodobnego
F E D C B A
0.32 0.32 0.61 0.125 0.25 0.5
Połącz zdarzenia najmniej prawdopodobne i ponownie posortuj
D FE C B A
0.61 0.64 0.125 0.25 0.5
F E
0.32 0.32
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 32/34
Kod Huffmana
ABCDEF
1
Powtarzaj operację
0 1
łączenia najmniej
BCDEF
A
prawdopodobnych
0.5
0.5
zdarzeń i sortowanie ich
0 1
układu, aż do uzyskania
CDEF B
drzewa. Następnie
0.25 0.25
lewym gałęziom
0 1
przypisz  0 , a prawym
DEF C
0.125 0.125
 1 , lub odwrotnie.
0 1
Odczytujemy wartości
D EF
ścieżek od węzła
0.061 0.064
głównego do
0 1
poszczególnych
F E
zdarzeń
0.032 0.032
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 33/34
Optymalne przyporządkowanie
Zdarzenie Sekwencja binarna
A 1
B 01
C 001
D 0000
E 00011
F 00010
Ciąg zdarzeń: AAAAAAAAAAAAAAAABBBBBBBBCCCCDDEF
Ciąg binarny: 11111111111111110101010101010101001001001001000000000001100010
Ciąg po podziale na duobity: 11 11 11 11 11 11 11 11 01 01 01 01 01 01 01 01 00 10 01 00
10 01 00 00 00 00 00 01 10 00 10
Ó�
Robert Borowiec
Ó�
Robert Borowiec
Slajd 34/34
KONIEC
Dziękuję za uwagę
Ó�
Robert Borowiec
Ó�
Robert Borowiec