Transmisja danych

dr hab. inż. Jerzy Kisilewicz, prof.

Katedra Systemów i Sieci Komputerowych

www.kssk.pwr.wroc.pl

C-3, pok. 107

TD1-1 / 22

Konsultacje:

•Wt. godz. 13-15

•Sr. godz. 15-17

Wymagania

1. Zdanie egzaminu testowego,
2. Zaliczenie i projektu,

1. Punkty z testu zaliczeniowego,
2. Punkty z projektu,
3. Punkty za obecności na wykładach.

Co wpływa na ocenę

1. Ocenę określa lokata na liście

uszeregowanej według sumy punktów. Progi

odcinają kolejno 10%-5, 25%-4,5, 30%-4,

25%-3,5 i 10%-3 z osób, które zaliczyły

przedmiot.

Uwagi

TD1-2 / 22

Literatura

1. Simmonds A., Wprowadzenie do transmisji

danych, Warszawa, WKŁ, 1999

2. Kula S., Systemy teletransmisyjne,

Warszawa, WKŁ, 2004

3. Rutkowski J., Theory of information and

coding,

Katowice, Wyd. Uniwersytetu

Śląskiego, 2006

4. Haykin S., Systemy telekomunikacyjne,

Warszawa, WKŁ, 2004

5. Forouzan B.A., Data communications and

networking, New York, McGraw-Hill, 2007

6. Piecha J., Transmisja danych i sieci

komputerowe, Katowice, Wyd.

Uniwersytetu Śląskiego, 2006

Literatura pomocnicza

TD1-3 / 22

Tematyka wykładów

1. Informacja i jej ilość.

2. Kanały i ich przepustowość.

3. Dyskretyzacja. Interpolacja.

4. Kodowanie wiadomości.

5. Detekcja i korekcja błędów. Podstawy

modulacji.

6. Modulacje dyskretne i widma sygnałów.

7. Łącza transmisyjne. Skrętki i światłowody

8. Łącza radiowe. Transmitancja kanału.

9. Kanał binarny i jego parametry. Styki.

10.Styki szeregowe i ich okablowanie.

11.Modemy.

12.Zwielokrotnianie kanałów.

13.Okablowanie strukturalne.

14.Sterowanie modemami.

15.Zagadnienia wybrane. Test zaliczeniowy.

TD1-4 / 22

E-Portal KSSK

TD1-5 / 22

Materiały dydaktyczne

http://www.kssk.pwr.wroc.pl/

Dla studentów

e-KSSK

Transmisja danych -
wykład

1. Zalogować się w e-Portalu KSSK (system

Moodle).

2. Zapisać się na kurs „Transmisja danych -

wykład”, hasło:

ISK3W#JK

Wykład 1

Miara informacji

1. Wstęp
2. Entropia dyskretnej zmiennej

losowej

3. Właściwości entropii
4. Ilość informacji
5. Źródła z pamięcią
6. Źródła rozszerzone

TD1-6 / 22

Wstęp

Pojęcie ilości informacji

Entropia

TD1-7 / 22

Informacja

TD1-8 /

22

Komunikat o zajściu zdarzenia niesie tym więcej informacji,
im więcej zmienia nasz stan niewiedzy.

Przykłady:

Jutro też będzie dzień.

Zero informacji – jest

pewne, że jutro będzie

dzień

Pies pogryzł chłopca.

Mało informacji –

zdarzenie

prawdopodobne

Chłopiec pogryzł psa.

Dużo informacji –

zdarzenie

nieoczekiwane

Informacja a

prawdopodobieńst

wo

p

1

log



informacji

Ilość

TD1-9 / 22

•Komunikat, że zaszło zdarzenie pewne nie niesie informacji.

•Im mniejsze prawdopodobieństwo, tym więcej informacji.

p=1 Ilość informacji = 0
p0 Ilość informacji  

Entropia dyskretnej zmiennej

losowej

TD1-10 / 22

X – dyskretna zmienna losowa
x

i

– zdarzenie, X przyjmuje wartość x

i

p

i

– prawdopodobieństwo zdarzenia x

i

i = 1, 2, ..., q (q – liczba stanów
zmiennej X)
H(X) – entropia zmiennej losowej















q

i

i

i

q

i

i

i

p

p

p

p

X

H

1

1

log

1

log

)

(

Podstawa
logarytmu

2

e

10

Jednostka
entropii

bit

nat hartle

y

Entropia - interpretacja

Entropia dyskretnej zmiennej losowej
X to:
• wartość oczekiwana ilości

informacji, którą niesie wiadomość o

tym, jaki stan przyjęła zmienna losowa

X,

• miara niewiedzy o tym, jaki stan
przyjmie zmienna losowa X.

TD1-11 / 22

Zmienna losowa
dwustanowa

q = 2
P(X

=

x

1

)

=

p, P(X

=

x

2

)

=

1

–

p

H(

X

)

=

–

p

log( p)

–

(1

–

p)log(1

–

p)

p

H

TD1-12 / 22

Właściwości entropii (1)

0  H(X

) 

log q

0

log

lim

0





p

p

p

H(X) = 0 gdy p

1

=1,

p

2

=p

3

=...=p

q

=0

zatem H(X)  0

max H(X) = log q gdy
p

1

=p

2

=...=p

q

=1/q

bo dla F(X) = H(X) + (1 – p

1

– p

2

–... – p

q

)

mamy

q

const

r

p

c

p

p

X

F

c

i

i

i

1

0

log

)

(































Dowód:

Gdy 0 < p  1 to –p

log(p)  0

TD1-13 / 22

e

c log



Właściwości entropii (2)

Niech x

i

oraz y

i

(i=1, 2, ...q) będą prawdopodobień-

stwami kolejno zmiennych losowych X oraz Y
oraz niech













q

i

i

i

q

i

i

i

y

x

Y

X

F

x

x

X

H

1

1

1

log

)

,

(

1

log

)

(

Zachodzi:

H(X)  F( X, Y )

oraz

H(X) = F( X, X )

TD1-14 / 22

Właściwości entropii (2) -

dowód

1

ln

















i

i

i

i

x

y

x

y

























1

2

ln

1

)

,

(

)

(

1

i

i

q

i

i

x

y

x

Y

X

F

X

H



























































i

i

q

i

i

i

i

q

i

i

i

i

q

i

i

x

y

x

x

y

x

y

x

x

Y

X

F

X

H

ln

2

ln

1

log

1

log

1

log

)

,

(

)

(

1

1

1

1

1

y=x

-1

y

x

y=ln x

ln x



x –1

TD1-15 / 22





 

0

1

1

2

ln

1

2

ln

1

2

ln

1

1

1

1











































q

i

i

q

i

i

q

i

i

i

x

y

x

y

Ilość informacji

I(A) = H(X

) – H(X

|

A)

Zdarzenie A niesie tyle informacji o zmiennej losowej X,

o ile zmienia naszą niewiedzę o tej zmiennej, czyli

o ile zmienia entropię.

Zatem

TD1-16 / 22

H(X|A) – entropia zmiennej X po zajściu zdarzenia A

Ilość informacji

H(X

) = log 6 = 1 + log 3  2,58496 bita

H(X

|

A) =

I(A) = H(X ) – H(X | A)  2,58496 – 2,35846 =

0,2265 bita

Przykład
Zdarzenie A mówi, że kostka do gry jest

fałszywa, bo 2, 3 lub

4 oczka wypadają po 2 razy częściej niż 1

oczko, 5 oczek

wypada 3 razy częściej, a 6 oczek 6 razy

częściej niż 1 oczko.
Niech zdarzenie x

i

polega na wyrzuceniu

liczby i oczek.

Prawdopodobieństwa zdarzeń wynoszą:

•dla zwykłej kostki

p(x

i

) = {

1

/

6

,

1

/

6

,

1

/

6

,

1

/

6

,

1

/

6

,

1

/

6

}

•dla kostki fałszywej p(x

i

|A) = {

1

/

16

,

2

/

16

,

2

/

16

,

2

/

16

,

3

/

16

,

6

/

16

}

TD1-17 / 22

3

log

16

9

4

1

3

6

16

log

16

6

3

16

log

16

3

2

16

log

16

2

3

1

16

log

16

1













Źródła z pamięcią

H(X

) =

H(X |x

j1

, …

x

jn

)

x

j1

, … x

jn

TD1-18 / 22

Entropia źródła Markova n-tego rzędu

p(x

i

|x

j1

, x

j2

, … x

jn

)

H(X |x

j1

, … x

jn

) = – p(x

i

|x

j1

, … x

jn

) log p(x

i

|

x

j1

, … x

jn

)





q

i 1

E

Źródła stowarzyszone

 

 

 









q

i

i

i

x

p

x

p

X

H

1

~

log

~

~

 





jn

j

j

i

x

x

x

i

x

x

x

x

p

x

p

E

jn

j

j

,...

,

|

~

2

1

,...

,

2

1



TD1-19 / 22

Źródło stowarzyszone ze źródłem Markova n-
tego rzędu
to źródło bezpamięciowe o
prawdopodobieństwach

 

 

X

H

X

H

~



Przykład

TD1-20 / 22

Oblicz entropię źródła Markova pierwszego
rzędu, które po bicie 0 generuje bit 1 z
prawdopodobieństwem p, a po bicie 1 generuje
bit 0 z prawdopodobieństwem q.
Oblicz entropię źródła stowarzyszonego.

0

p(0|0) = 1– p

1

p(1|1) = 1– q

p(1|0) = p

p(0|1) = q

 

 

q

p

p

p

q

p

q

p









1

,

0

H(X | 0) = – p log p – (1– p)log(1– p)
H(X | 1) = – q log q – (1– q)log(1– q)
H(X ) = p(0) H(X | 0) + p(1) H(X | 1)

H(X ) = – p(0) log p(0) – p(1)log p(1)

~

Dla: p = 0,5 oraz q = 0,25
H(X | 0) = 1

H(X | 1) = 0,811

p(0) = 0,333

p(1) = 0,667

H(X ) = 0,874

H(X ) = 0,918

~

Rozszerzenie źródła

TD1-21 / 22

bezpamięciowego

Ciąg n symboli źródła podstawowego X traktujemy jako
pojedynczy symbol źródła rozszerzonego X

n

σ

i

= x

i1

, x

i2

, … x

in

p(σ

i

) = p(x

i1

) p(x

i2

) … p(x

in

)

H(X

n

) = nH(X )

Entropia źródła

rozszerzonego

TD1-22 / 22

 

 

 









 

 

 

 

X

nH

X

H

X

H

X

H

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

X

H

q

in

in

in

q

i

i

i

q

i

i

i

q

in

in

in

q

i

i

q

i

i

q

in

in

i

q

i

i

q

i

i

q

in

in

q

i

i

q

i

i

i

in

i

i

q

in

in

i

i

q

i

q

i

in

i

i

q

in

in

i

i

q

i

q

i

q

i

i

i

n

n







































































































































...

log

...

log

log

log

...

...

...

log

...

log

log

...

log

log

...

...

...

log

...

...

log

1

1

2

2

2

1

1

1

1

1

1

2

2

1

1

1

1

2

1

2

2

1

1

1

1

1

2

2

1

1

1

1

2

1

1

2

1

1

2

1

1

2

1

1

2

1

1

2

1

1

1





Oznaczając p

i

= p(x

i

) mamy

1