Teoria informacji i kodowanie:
ćwiczenia II

Źródła markowowskie, kanały informacyjne,
przepustowość

Piotr Chołda

Katedra Telekomunikacji Akademii Górniczo-Hutniczej

Kraków, 11. marca 2011 r.

Źródła Markowa (marko[wo]wskie)

Źródło Markowa i jego entropia

Źródło Markowa

rzędu

L

to źródło, które generuje N wiadomości

x

1

, . . . , x

N

i jest

opisywane

prawdopodobieństwami Pr {s

i

} oraz

Pr {x

j

|s

i

}, gdzie s

i

jest

sekwencją wiadomości wysłaną przed

x

j

:

s

i

= x

i (1)

. . . x

i (L)

. (Warunkowa) entropia takiego źródła Markowa

jest definiowana jako:

H

L

(X ) = −

N

X

j =1

N

L

X

i =1

Pr{x

j

, s

i

} lg Pr{x

j

|s

i

}

= −

N

X

j =1

N

X

i

1

=1

· · ·

N

X

i

L

=1

Pr{x

j

, x

i

1

, . . . , x

i

L

} lg Pr{x

j

|x

i

1

, . . . , x

i

L

}

.

TIiK: ćwiczenia

2/21

Przykład użycia w systemach IT

Poszukiwanie zaszyfrowanego lub spakowanego złośliwego
oprogramowania

Analiza entropii plików dostarcza interesujących informacji z
punktu widzenia bezpieczeństwa systemów IT, na przykład:

Zaszyfrowane lub spakowane złośliwe oprogramowanie
utrudnia jego automatyczne wykrywanie (hakerzy
wykorzystują ten fakt)

Dotyczy to 80 − 90% przypadków

Normalne postępowanie: wykrywa się „ręcznie” podejrzane
oprogramowanie, które jest spakowane lub zaszyfrowane, a
potem dopiero poddaje je odpowiedniej obróbce systemu
bezpieczeństwa

TIiK: ćwiczenia

3/21

Przykład użycia w systemach IT

Poszukiwanie zaszyfrowanego lub spakowanego złośliwego
oprogramowania cd.

Silne algorytmy szyfrujące, np. Triple DES, generują mniej
przewidywalne sekwencje — zwiększają entropię

W celu wykrywania podejrzanych plików bada się entropię
sekwencji binarnych

Metoda:

analiza częstości pojawiania się bajtów (00h do FF h)

występujących w równej długości blokach, następnie użycie
wzorów na obliczanie entropii

Generalnie wyższe wartości entropii są skorelowane z
zaszyfrowaną lub spakowaną treścią

TIiK: ćwiczenia

4/21

Przykład użycia w systemach IT

Poszukiwanie zaszyfrowanego lub spakowanego złośliwego
oprogramowania cd.

W ten sposób można rozróżniać wstępnie zwykłe pliki
wykonywalne od zaszyfrowanych/spakowanych

Tabela:

Przykładowe dane otrzymane z próbki uczącej

Zbiór danych

Średnia entropia

Zwykły tekst

4,347

Pliki wykonywalne

5,099

Plik spakowany

6,801

Plik zaszyfrowany

7,175

Źródło: R. Lyda and J. Hamrock, “Using Entropy Analysis to Find Encrypted and Packed Malware,” IEEE Security
& Privacy, vol. 5, no. 2, pp. 40–45, Mar./Apr. 2007.

TIiK: ćwiczenia

5/21

Zadanie powtórzeniowe I

Porównajmy klasyczną entropię z obliczoną dla źródeł Markowa. . .

Źródło binarne generuje dwie wiadomoci: 0 i 1. Oblicz entropię
klasyczną oraz entropię Markowa źródła przy następujących
założeniach:

(a)

wiadomości są równoprawdopodobne, źródło jest
źródłem z pamięcią, przy czym:

Pr{0|1} = Pr{1|0} =

1

3

;

(b)

źródło jest źródłem z pamięcią, natomiast:

Pr{0} =

3

4

Pr{0|0} =

2

3

Pr{0|1} = 1.

TIiK: ćwiczenia

6/21

Kanały transmisyjne

Dyskretny kanał bezpamięciowy

x

1

..

.

x

M

X

Kanał informacyjny

y

1

..

.

y

L

Y

Dyskretny kanał bezpamięciowy

Dyskretny kanał bezpamięciowy

jest definiowany za pomocą:

zbioru

wiadomości wejściowych

: X = {x

1

, x

2

, . . . , x

M

}

zbioru

wiadomości wyjściowych

: Y = {y

1

, y

2

, . . . , y

L

}

zbioru M × L

prawdopodobieństw

: Pr{y

j

|x

i

}

TIiK: ćwiczenia

7/21

Różne kanały transmisyjne

Kanał bezszumowy (konstrukt czysto teoretyczny):
Pr{y

k

|x

k

= y

k

} = 1

Kanał binarny z wymazywaniem

Bardzo ważny — binarny kanał symetryczny (BSC):

0

1

0

1

Pr{0|0}

Pr{1|1}

Pr{0|1}

Pr{1|0}

Pr{0|1}

BSC

= Pr{1|0}

BSC

= BER

Chętnie modelujemy kanały jako bezpamięciowe, ale nie jest
to poprawne dla dużych szybkości transmisji (bł. paczkowe)

TIiK: ćwiczenia

8/21

Binarny kanał symetryczny

Trochę danych praktycznych

Tabela:

Wartości BER dla różnych technik transmisyjnych

Technika

BER

Łącza światłowodowe

≤ 10

−13

SDH

∼ 10

−12

Typowe łącze dzierżawione E1

∼ 10

−9

Standard IEEE 802

r

-2001 dla sieci LANs/MANs

≤ 10

−8

Typowe łącza ADSL

∼ 10

−7

Transmisja satelitarna

∼ 10

−6

Źródło: J. Evans and C. Filsfils, Deploying IP and MPLS QoS for Multiservice Networks.

San Francisco, CA:

Morgan Kaufmann Publishers—Elsevier, 2007.

TIiK: ćwiczenia

9/21

Zadanie powtórzeniowe II

Kolokwium z lat poprzednich. . .

Sprawdź czy kaskada binarnych kanałów symetrycznych (kanały są
połączone szeregowo: wyjście jednego z wejściem kolejnego; kanały
niekoniecznie są identyczne) też jest binarnym kanałem
symetrycznym.

TIiK: ćwiczenia

10/21

Przepustowość kanału

Interesuje nas, jak dużo informacji można przenieść przez kanał
transmisyjny (określony przez X , Y , Pr{y

j

|x

i

}).

Przepustowość kanału

Przepustowość dyskretnego kanału bezpamięciowego

jest

definiowana jako maksymalna

transinformacja

I (X ; Y ) która może

być transmitowana przez kanał na raz, przy czym

maksymalizacja

przebiega po wszystkich rozkładach prawdopodobieństwa

wiadomości wejściowych:

C = max

P

X

I (X ; Y ) = max

P

X

[H(X ) − H(X |Y )] =

max

P

X

[H(Y ) − H(Y |X )]

.

TIiK: ćwiczenia

11/21

Zadanie powtórzeniowe III

Dany jest binarny symetryczny kanał z wymazywaniem:

x

1

= 0

x

2

= 1

y

1

= x

1

y

2

= E

y

3

= x

2

Kanał charakteryzuje się następującymi prawdopodobieństwami:





1 − α − β

α

β

β

α

1 − α − β





.

Pokaż, że jego przepustowość da się opisać następującym wzorem:

C = (1 − β)[1 − lg(1 − β)] + (1 − α − β) lg(1 − α − β) + α lg α.

TIiK: ćwiczenia

12/21

Zadanie 1

Sporządź wykres stanów źródła Markowa drugiego rzędu, jeśli
źródło jest źródłem binarnym, a prawdopodobieństwa warunkowe
wynoszą:

Pr{0|00} = Pr{1|11} = 0,8

Pr{1|00} = Pr{0|11} = 0,2

Pr{0|01} = Pr{0|10} = Pr{1|01} = Pr{1|10} = 0,5.

Następnie oblicz entropię tego źródła, jeśli wiadomo że:

Pr{00} = Pr{11} =

5

14

Pr{01} = Pr{10} =

2

14

.

TIiK: ćwiczenia

13/21

Zadanie 2

Kolokwium z lat poprzednich. . .

Mamy do dyspozycji niekoniecznie identyczne binarne kanały
symetryczne charakteryzujące się prawdopodobieństwami błędu:

1

2

≤ p

i

< 1.

W jaki sposób można z nich (niekoniecznie wszystkich) uzyskać
binarny kanał symetryczny charakteryzujący się:

0 < BER ≤

1

2

?

TIiK: ćwiczenia

14/21

Zadanie 3

Kolokwium z lat poprzednich. . .

Informacja złożona z N symboli binarnych jest transmitowana przez
binarny kanał symetryczny o prawdopodobieństwie przekłamania p.
Jaka jest wartość oczekiwana liczby bitów przesłanych poprawnie w
tej informacji? Jaka jest przepustowość tego kanału?

TIiK: ćwiczenia

15/21

Zadanie 4

Kolokwium z lat poprzednich. . .

Kanał binarny charakteryzuje się następującymi
prawdopodobieństwami przejść:

p(y

1

|x

1

) = 1

p(y

1

|x

2

) = p(y

2

|x

2

) =

1

2

Znajdź przepustowość tego kanału.

TIiK: ćwiczenia

16/21

Zadanie 5

Kolokwium z lat poprzednich. . .

Oblicz, ile wynosi informacja wzajemna I (X ; Y ) między wejściem i
wyjściem kanału o dwóch wejściach x

1

, x

2

∈ X i trzech wyjściach

y

1

, y

2

, y

3

∈ Y :

x

1

= 0

x

2

= 1

y

1

= 0

y

3

= E

y

2

= 1

1
4

1
2

1
4

jeśli

Pr {x

1

} = Pr {x

2

} =

1

2

.

TIiK: ćwiczenia

17/21

Zadanie 6

Kolokwium z lat poprzednich. . .

Oblicz przepustowość „kanału pięciokątnego”. Przy strzałkach
mamy dane prawdopodobieństwa przejść p(y

j

|x

i

) =

1
2

:

p(y

1

|x

2

) = p(y

1

|x

5

) = p(y

2

|x

1

) = p(y

2

|x

3

) = p(y

3

|x

2

) =

p(y

3

|x

4

) = p(y

4

|x

3

) = p(y

4

|x

5

) = p(y

5

|x

4

) = p(y

5

|x

1

) =

1
2

(kanał

jest symetryczny).

1
2
3
4
5

1
2
3
4
5

TIiK: ćwiczenia

18/21

Zadanie 7

Kolokwium z lat poprzednich. . .

Binarny kanał asymetryczny jest reprezentowany za pomocą
macierzy:

1 − a

a

b

1 − b

,

gdzie na wejściu i wyjściu mamy symbole ze zbioru {0, 1} oraz
a 6= b. Odbiornik otrzymuje na swoim wejściu symbole 0 i 1 tak
samo często. Znajdź rozkład prawdopodobieństwa na wejściu do
tego kanału (czyli na wyjściu z nadajnika) i pokaż, że entropia na
wyjściu kanału jest większa niż na jego wejściu.

TIiK: ćwiczenia

19/21

Zadanie 8

Kolokwium z lat poprzednich. . .

1

2

3

4

Uproszczoną klawiaturę numeryczną pokazano na ry-
sunku obok. Ma ona cztery klawisze (w dwóch rzę-
dach po dwa klawisze). Użytkownik, który chce nacis-
nąć klawisz x , naciśnie z prawdopodobieństwem α inny
klawisz w tym samym rzędzie lub z prawdopodobieńst-
wem α inny klawisz w tej samej kolumnie. A więc z
prawdopodobieństwem 1 − 2α naciśnie właściwy klawisz x . Taką
klawiaturę można opisywać jako kanał transmisyjny, gdzie na wejś-
ciu mamy intencję użytkownika, a na wyjściu faktycznie naciśnięty
klawisz. Zapisz macierz tego kanału i oblicz jego przepustowość.

TIiK: ćwiczenia

20/21

Pytania? Dziękuję za

uwagę! Za tydzień

kodowanie źródłowe

,

kody

Huffmana

i

kodowanie

arytmetyczne

— wykłady

2 i 3

TIiK: ćwiczenia

21/21