Teoria Sygnałów i Informacji (TSI)
Laboratorium
Preskrypt
na prawach rękopisu
Gustaw Mazurek
Anatolij PÅ‚atonow
Zakład Teorii Obwodów i Sygnałów
Instytut Systemów Elektronicznych
Wydział Elektroniki i Technik Informacyjnych
Politechnika Warszawska
Warszawa, 22 maja 2014
Spis treści
5 Charakterystyki informacyjne binarnego kanału transmisyjnego 3
5.1 Podstawy teoretyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5.1.1 Charakterystyki probabilistyczne . . . . . . . . . . . . . . . . . . . . 4
5.1.2 Charakterystyki informacyjne . . . . . . . . . . . . . . . . . . . . . 5
5.2 Zadanie do wykonania w domu . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.3 Pomiar entropii z
ródła sygnałów (entropii a priori) . . . . . . . . . . . . . . 7
5.3.1 Obliczanie estymat prawdopodobieÅ„stwa P¾(x1) = p . . . . . . . . . 7
5.3.2 Obliczenie entropii z
ródła . . . . . . . . . . . . . . . . . . . . . . . 9
5.4 Analiza charakterystyk kanału transmisyjnego . . . . . . . . . . . . . . . . . 9
5.4.1 Generowanie sygnału w z
ródle informacji . . . . . . . . . . . . . . . 9
5.4.2 Zakłócanie sygnału w kanale transmisyjnym . . . . . . . . . . . . . 10
5.4.3 Oszacowanie przepustowości kanału i sprawności transmisji . . . . . 11
5.5 Kodowanie z
ródłowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.5.1 Właściwości zakodowanego ciągu bitów . . . . . . . . . . . . . . . . 13
5.5.2 Porównanie właściwości kodów dla różnych długości bloku . . . . . 13
5.6 Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2
Ćwiczenie 5
Charakterystyki informacyjne binarnego
kanału transmisyjnego
Celem ćwiczenia jest zapoznanie się z obliczeniami rozkładów prawdopodobieństwa metodą
macierzową i możliwościami symulowania kanałów transmisyjnych w środowisku Matlab.
Główną wagę ćwiczenia położono na systemy z przesyłaniem sygnałów binarnych.
W celu przyspieszenia wykonywania laboratorium zaleca siÄ™ zaznaczanie i kopiowanie
fragmentów kodu bezpośrednio z niniejszej instrukcji w formacie PDF do schowka Windows
(ctrl-C), a następnie wklejanie ich do okna komend środowiska Matlab (ctrl-V) lub do edytora
tekstowego.
Dłuższe fragmenty kodu, bądz
gotowe funkcje Matlabowskie, dołączono do tego doku-
mentu PDF jako pliki osadzone (załączniki tekstowe), wyróżnione piktogramem pinezki na
marginesie. Załączniki te należy zapisać na dysku (po kliknięciu prawym przyciskiem na  pi-
nezce ) w katalogu roboczym środowiska Matlab. Nazwę tego katalogu można uzyskać za
pomocÄ… komendypwd.
Podczas laboratorium należy wypełniać formatkę sprawozdania, odpowiadając krótko i kon-
kretnie na postawione pytania. Należy zgłaszać prowadzącemu każde wykonane zadanie i moż-
liwie szybko zgłaszać ew. trudności w jego wykonaniu.
Przed laboratorium należy wykonać w domu (samodzielnie!) zadanie 5.2. Należy tak-
że przynieść wydrukowaną formatkę sprawozdania (jedną dla dwuosobowego zespołu),
dostępną w formacie PDF razem z innymi materiałami dydaktycznymi na stronie interneto-
wej przedmiotu.
5.1 Podstawy teoretyczne
Na rys. 5.1 pokazano schemat blokowy elementarnego Å‚Ä…cza transmisyjnego.
Rysunek 5.1: Schemat elementarnego Å‚Ä…cza transmisyjnego
3
5.1.1 Charakterystyki probabilistyczne
y
ródÅ‚o informacji generuje sygnaÅ‚y xi ze zbioru &!¾ = {x1, . . . , xM}. SygnaÅ‚y sÄ… generowane
niezależnie od siebie (z
ródło bez pamięci) i z prawdopodobieństwami a priori:
[P¾(xi)]M,1 = [P¾(x1), . . . , P¾(xM)]T . (5.1)
Wygenerowane sygnały są przesyłane przez kanał stacjonarny bez pamięci, tzn. o właści-
wościach niezmiennych w czasie i niezależnych od historii przesyłanych sygnałów. Na skutek
oddziaływania szumu ł możliwa jest zarówno poprawna, jak i błędna transmisja. Prawdopo-
dobieństwa tych zdarzeń są określone tzw. macierzą przejścia kanału transmisyjnego:
îÅ‚ Å‚Å‚
P·|¾(y1|x1)] . . . P·|¾(y1|xM)]
ðÅ‚ ûÅ‚
[P·|¾(yk|xi)] = . . . . . . , (5.2)
P·|¾(yM|x1)] . . . P·|¾(yM|xM)]
gdzie yk to sygnaÅ‚y odbierane: yk " &!· = {y1, . . . , yM}1. W przypadku bezbÅ‚Ä™dnego odbioru
mamy k = i, zaś przy błędnym odbiorze lub nie podjętej decyzji: k = i.
8
Znając rozkłady (5.1), (5.2) możemy obliczyć rozkład sygnałów yk na wyjściu kanału:
M
P·(yk) = P·|¾(yk|xi)P¾(xi), (5.3)
i=1
lub w formie macierzowej:
[P·(yk)] = [P·|¾(yk|xi)][P¾(xi)]. (5.4)
Rozkład łączny można obliczyć ze wzoru:
P¾,·(xi, yk) = P·|¾(yk|xi)P¾(xi) = P¾|·(xi|yk)P·(yk), (5.5)
lub w formie macierzowej:
[P·,¾(yk, xi)] = [P·|¾(yk|xi)]diag[P¾(xi)] = [P¾,·(xi, yk)]T . (5.6)
Rozkład a posteriori opisuje zmiany rozkładu a priori po odbiorze któregoś z sygnałów
yk. Rozkład ten może być wyznaczony na podstawie (5.1), (5.2) za pomocą formuły Bayesa :
P·|¾(yk|xi)P¾(xi) P·|¾(yk|xi)P¾(xi)
P¾|·(xi|yk) = = , (5.7)
M
P·(yk)
P·|¾(yk|xi)P¾(xi)
i=1
lub w postaci macierzowej:
[P¾|·(xi|yk)] = [P¾,·(xi, yk)]diag[P·(yk)]-1 =
îÅ‚ Å‚Å‚
P·(y1)-1 . . . 0
ïÅ‚ śł
(5.8)
0 P·(y2)-1 . . .
śł
= [P·,¾(yk, xi)]T ïÅ‚ .
ðÅ‚ ûÅ‚
. . . . . . . . .
0 . . . P·(yM)-1
1
Dla rozpatrywanego kanaÅ‚u licznoÅ›ci zbiorów realizacji &!¾, &!· sÄ… równe (M = N). W dalszej analizie
będziemy posługiwać się wyłącznie stałą M.
4
5.1.2 Charakterystyki informacyjne
Miarą informacji wysyłanej ze z
ródła jest tzw. entropia a priori (lub entropia z
ródła):
M M
1
H(¾) = - P¾(xi) log2 P¾(xi) = P¾(xi) log2 . (5.9)
P¾(xi)
i=1 i=1
Analogicznie oblicza siÄ™ entropiÄ™ zmiennej losowej · na wyjÅ›ciu kanaÅ‚u (licznoÅ›ci zbiorów
realizacji obu zmiennych losowych ¾, · sÄ… równe: M = N):
M M
1
H(·) = - P·(yk) log2 P·(yk) = P·(yk) log2 . (5.10)
P·(yk)
k=1 k=1
Entropia warunkowa a posteriori dana jest wzorem:
M M
H(¾|·) = - P¾,·(xi, yk) log2 P¾|·(xi|yk), (5.11)
i=1 k=1
gdzie P¾,·(xi, yk) jest rozkÅ‚adem Å‚Ä…cznym.
Przez analogię do entropii warunkowej a posteriori określonej zależnością (5.11) definiuje
siÄ™ drugÄ… entropiÄ™ warunkowÄ…:
M M
H(·|¾) = - P¾,·(xi, yk) log2 P·|¾(yk|xi). (5.12)
i=1 k=1
Miarą oczekiwanej ilości informacji przesyłanej przez kanał z zadanego z
ródła (czyli miarą
ilości informacji na wyjściu kanału) jest tzw. transinformacja, czyli średnia wzajemna ilość
informacji pomiÄ™dzy sygnaÅ‚ami wysyÅ‚anymi (¾) i odbieranymi (·):
I(¾, ·) = H(¾) - H(¾|·) = H(·) - H(·|¾) =
M M
P¾|·(xi|yk)
= P¾,·(xi, yk) log2 =
P¾(xi)
(5.13)
i=1 k=1
M M
P·|¾(yk|xi)
= P¾,·(xi, yk) log2 .
P·(yk)
i=1 k=1
Transinformacja jest funkcją zarówno probabilistycznej charakterystyki kanału, jak i cha-
rakterystyki z
ródła informacji. Zatem dla określenia właściwości kanału przesyłowego ko-
nieczne jest wprowadzenie innej miary, tzw. przepustowości kanału, nie zależącej od rozkładu
a priori.
Przepustowość kanału C określamy jako maksymalną (po zbiorze wszystkich możliwych
rozkładów a priori) możliwą ilość informacji przesyłaną przez kanał w pojedynczych sygna-
Å‚ach:
C = max I(¾, ·) = max [H(·) - H(·|¾)]. (5.14)
{P¾(xi)} {P¾(xi)}
Dla kanału binarnego symetrycznego bez pamięci opisanego macierzą przejścia:
d 1 - d
[P·|¾(yk|xi)] = , (5.15)
1 - d d
5
gdzie parametr d określa prawdopodobieństwo poprawnej transmisji pojedynczego sygnału,
zależnoÅ›ci ulegajÄ… znacznemu uproszczeniu (H(·|¾) = -d log2 d - (1 - d) log2(1 - d),
niezależnie od przyjÄ™tego rozkÅ‚adu P¾(xi)). Ilość informacji na wyjÅ›ciu takiego kanaÅ‚u można
obliczyć ze wzoru:
I(¾, ·) = H(·) + d log2 d + (1 - d) log2(1 - d). (5.16)
PodstawiajÄ…c dalej H(·) = Hmax = 1 otrzymujemy wzór na przepustowość symetrycznego
kanału binarnego:
C = 1 + d log2 d + (1 - d) log2(1 - d). (5.17)
Wygodną miarą jakości transmisji przez kanał jest współczynnik sprawności transmisji in-
formacji (lub inaczej: wykorzystania kanału transmisyjnego). Współczynnik ten charakteryzu-
je stopień wykorzystania kanału o przepustowości C przy transmisji sygnałów generowanych
przez z
ródÅ‚o o zadanym rozkÅ‚adzie P¾(xi) i jest on obliczany wedÅ‚ug wzoru:
I(¾, ·)
k = . (5.18)
C
5.2 Zadanie do wykonania w domu
A
ącze binarne bez pamięci jest opisane macierzą rozkładu łącznego:
0, 63 0, 07
Wariant A: [P¾,·(xi, yk)] = ,
0, 03 0, 27
(5.19)
0, 6 0, 15
Wariant B: [P¾,·(xi, yk)] = .
0, 05 0, 2
Studenci o parzystych numerach indeksów przyjmują wariant A, zaś pozostali  B (w nagłów-
ku pracy domowej należy podać swój numer indeksu).
1. Na podstawie rozkładu (5.19) wyznaczyć:
(a) RozkÅ‚ad a priori: [P¾(xi)].
(b) RozkÅ‚ad sygnaÅ‚u na wyjÅ›ciu kanaÅ‚u: [P·(yk)].
(c) Macierz przejÅ›cia kanaÅ‚u: [P·|¾(yk|xi)].
(d) RozkÅ‚ad a posteriori: [P¾|·(xi|yk)].
(e) OkreÅ›lić typ kanaÅ‚u opisywany macierzÄ… [P·|¾(yk|xi)].
2. Obliczyć charakterystyki informacyjne z
ródła i kanału:
(a) Entropie a priori i a posteriori.
(b) Przepustowość kanału C.
(c) WzajemnÄ… ilość informacji (transinformacjÄ™) I(¾; ·).
(d) Współczynnik k wykorzystania kanału transmisyjnego.
(e) Bitową stopę błędów (BER, ang. Bit Error Rate) określaną jako prawdopodobień-
stwo błędnej transmisji pojedynczego bitu.
3. Opisać zmiany charakterystyk (a d) przy zmianach prawdopodobieństwa generacji sy-
1
gnaÅ‚u P¾(x1) w przedziale 0 . . . .
2
6
5.3 Pomiar entropii z
ródła sygnałów (entropii a priori)
Na początku realizacji ćwiczenia należy uruchomić komputer, wybrać system operacyjny Win-
dows 7, zalogować się na konto Student i uruchomić środowisko Matlab za pomocą odpowied-
niej ikony na pulpicie.
Zdefiniujemy nowe zmienne opisujÄ…ce dany system transmisyjny. Zgodnie z numerem sta-
nowiska S = 1 . . . 16 należy wybrać odpowiednie wartości parametrów:
" p  prawdopodobieÅ„stwo P¾(x1) wysÅ‚ania sygnaÅ‚u x1 = 0 ze z
ródła informacji:
p=0.6+0.02*S
" d  prawdopodobieństwo przesłania sygnału bez błędu:
d=0.95-0.022*S
Na podstawie tych parametrów definiujemy podstawowe rozkłady prawdopodobieństwa:
" P¾(xi)  wektor kolumnowy prawdopodobieÅ„stwa a priori (charakterystyka probabili-
styczna z
ródła):
Pksi=[p 1-p]'
" P·|¾(yk|xi)  macierz przejÅ›cia kanaÅ‚u (charakterystyka probabilistyczna kanaÅ‚u):
Peta_ksi=[d 1-d; 1-d d]
Tak zdefiniowane macierze należy wpisać w odpowiednie miejsca w sprawozdaniu.
Przyjęty zestaw parametrów łącza transmisyjnego:
1. Wektor rozkÅ‚adu a priori: [P¾(xi)] = . . .
2. Macierz przejÅ›cia kanaÅ‚u: [P·|¾(yk|xi)] = . . .
5.3.1 Obliczanie estymat prawdopodobieÅ„stwa P¾(x1) = p
Eksperyment polegał będzie na analizie wielu realizacji pseudolosowego sygnału binarnego,
przy czym każda realizacja składa się ze stałej, zadanej liczby bitów.
Definiujemy liczbÄ™ K realizacji badanych podczas eksperymentu:
K=100
oraz długość każdej realizacji (liczbę bitów Nb)  początkowo równą 100:
N_b=100
przygotowujemy także tablicę do przechowywania wyników:
p_est_tab=zeros(1,K);
Algorytm obliczania wartości (estymat) prawdopodobieństw sygnałów polega na zliczaniu
zer (lub jedynek) w wygenerowanej realizacji i dzieleniu tej liczby przez długość realizacji.
Wynik dla każdej realizacji zapamiętywany jest w tablicyp_est_tab. Zadania te wykonuje
następujący program:
7
for r=1:K
Db=sign(rand(Nb,1)-p) /2 +0.5; % Generowanie sygnału bin.
N0=length(find(Db<0.5)); % Zliczanie zer
p_est=N0/Nb; % Estymacja prawdopodob. wystÄ…pienia zera
p_est_tab(r)=p_est; % Zapamiętanie wyniku w tablicy
end
Poniższy program rysuje histogramy estymat prawdopodobieństwa p, ilustrujące rozpro-
szenie ich wartości w poszczególnych realizacjach:
figure
hist(p_est_tab,20); grid on;
axis([p-0.2 p+0.2 0 20]);
xlabel ('Estymata p');
ylabel ('Liczba realizacji');
title (['Histogram estymaty p, dł. real.=' num2str(Nb)]);
Uzyskany wykres można zapisać do pliku graficznego na dysku komputera:
print -dpng nazwa_pliku.png
Skończona długość realizacji powoduje losowe rozproszenie estymat, w związku z czym
dla każdej realizacji estymata przyjmuje nieco inną wartość. Dla otrzymania dokładnych wy-
ników obliczenia są uśredniane po wszystkich K realizacjach. Wynikiem uśredniania będzie
estymata p bliska realnej wartoÅ›ci prawdopodobieÅ„stwa P¾(x1):
mean(p_est_tab) % średnia po wszystkich realizacjach
Bazując na wynikach zapamiętanych w tablicyp_est_tabwyznaczamy jeszcze odchylenie
standardowe (Ã), bÄ™dÄ…ce miarÄ… rozrzutu estymat wokół wartoÅ›ci Å›redniej:
std(p_est_tab) % odchylenie standardowe
Uzyskane wartości wpisujemy w odpowiednie miejsce w tabeli 5.1.
Powtarzamy eksperyment dla dłuższych realizacji (Nb = 1000, 4000, 10000). Za każdym
razem wpisujemy wartości średnie oraz odchylenia standardowe uzyskane z badania K =
100 realizacji do odpowiednich miejsc w tabeli 5.1. Uzyskane histogramy należy przedstawić
prowadzącemu ćwiczenie oraz zgrubnie przerysować do sprawozdania.
Porównujemy wyniki numeryczne oraz histogramy uzyskane dla różnych długości reali-
zacji i wyciągamy wnioski, odpowiadając na postawione niżej pytania.
Tabela 5.1: Porównanie wyników estymacji dla różnych długości realizacji Nb
Nb = 100 Nb = 1000 Nb = 4000 Nb = 10000
Wartość średnia (p)
Odchylenie standardowe (Ã)
1. Jak zmienia się histogram dla różnych długości realizacji Nb?
8
2. Jak zależy rozrzut à uzyskiwanych estymat od dÅ‚ugoÅ›ci realizacji?
3. Wskazać wartość Nb, dla której wyznaczone odchylenie standardowe nie przekroczyło
1% wartości p: ......
4. Jak zmienią się histogramy oraz wartości à w przypadku estymacji prawdopodobień-
stwa P¾(x2) wygenerowania drugiego sygnaÅ‚u (x2)?
5. Porównać otrzymane wyniki z wartoÅ›ciami teoretycznymi: P¾(x1) = . . . . . ., P¾(x2) =
. . . . . .
5.3.2 Obliczenie entropii z
ródła
Korzystając z wyników poprzedniego punktu, obliczamy wartości entropii z
ródła (a priori)
wedÅ‚ug wzoru (5.9), zastÄ™pujÄ…c w nim wartoÅ›ci dokÅ‚adne (P¾(xi)) przez estymaty prawdopo-
dobieństw sygnałów (p, 1-p) otrzymane przy różnych długościach realizacji (Nb = 100, 1000,
4000, 10000).
Uzyskane wartości $
(¾) wpisujemy do sprawozdania. Obliczamy i wpisujemy również
teoretyczną wartość entropii:
H(¾) = -p log2(p) - (1 - p) log2(1 - p). (5.20)
Porównujemy wyniki z wartością teoretyczną i odpowiadamy na pytania:
Tabela 5.2: Porównanie estymacji H(¾) dla różnych dÅ‚ugoÅ›ci realizacji Nb
Nb = 100 Nb = 1000 Nb = 4000 Nb = 10000
Estymowana wartość $
(¾)
Różnica w % względem wartości
teoretycznej H(¾) = . . . . . .
1. Jak wpływa długość Nb realizacji na dokładność estymacji entropii i dlaczego?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Opisać, jak będzie zmieniała się teoretyczna wartość entropii i histogramy jej estymat
1
przy zmianach P¾(x1) od 0 do ?
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Analiza charakterystyk kanału transmisyjnego
5.4.1 Generowanie sygnału w z
ródle informacji
Definiujemy nową długość generowanego ciągu informacji (liczbę bitów Nb) i generujemy
pseudolosowy strumień danych binarnych Db o zadanej długości:
9
Nb=12E4;
Db=sign(rand(Nb,1)-p) /2 +0.5;
Podobnie jak w poprzedniej części ćwiczenia, zliczamy zera występujące w wygenerowa-
nym wektorze danych:
N0=length(find(Db<0.5))
oraz estymujemy prawdopodobieństwa p0, p1 wystąpienia zer i jedynek:
p0_est=N0/Nb
p1_est=1-p0_est
Następnie estymujemy entropię z
ródła, tj. ilość wysyłanej informacji:
Hksi=-p0_est*log2(p0_est)-p1_est*log2(p1_est)
Uzyskaną wartość wpisujemy do sprawozdania.
5.4.2 Zakłócanie sygnału w kanale transmisyjnym
Jako z
ródło zakłóceń ł (patrz rys. 5.1) wykorzystany będzie szum pseudolosowy o rozkładzie
Gaussa, generowany komendąrandn()w środowisko Matlab. Odchylenie standardowe szu-
mu à należy dobrać tak, aby uzyskać prawdopodobieÅ„stwo bÅ‚Ä™du (BER) równe 1 - d. Dla
sygnaÅ‚u binarnego &!¾ = {x1 = 0, x2 = 1} zakłócanego szumem Gaussa o wariancji Ã2:
1 1 1
BER = 1 - Åš = 1 - erf " = 1 - d, (5.21)
2Ã 2
2Ã 2
gdzie funkcja Ś(x) jest dystrybuantą standardowego rozkładu normalnego:
x
1 -t2 1 x
Åš(x) = " exp dt = 1 + erf " , (5.22)
2 2
2Ä„ -"
2
zaś erf(x) jest tzw. funkcją błędu Gaussa:
x
2
erf(x) = " exp(-t2)dt. (5.23)
Ä„
0
Funkcja błęduerf()oraz funkcja do niej odwrotnaerfinv()są zaimplementowane
w środowisku Matlab, dzięki czemu obliczenie właściwej wartości à dla zadanego prawdo-
podobieństwa poprawnej transmisji d sprowadza się do jednej linijki kodu:
sigma=1/(2*sqrt(2)*erfinv(1-2*(1-d)))
Modelujemy działanie zakłóceń ł w kanale transmisyjnym, dodając do sygnału informa-
cyjnego odpowiednio przeskalowane próbki szumu. W tym momencie sygnał przestaje być
dyskretny i staje się ciągły w amplitudzie:
u=Db+sigma*randn(Nb,1);
Po stronie odbiorczej zawsze występuje blok decyzyjny, którego zadaniem jest detekcja
sygnałów, czyli wybranie, który dwóch z sygnałów (x1, x2) odpowiada odebranemu zakłóco-
nemu, ciągłemu w amplitudzie sygnałowi u. W ćwiczeniu stosujemy regułę decyzyjną pole-
gającą na wybraniu takiego sygnału xj, dla którego prawdopodobieństwo warunkowe P (xj|u)
10
jest większe niż pozostałe prawdopodobieństwa: P (xi|u) < P (xj|u). Jest to tzw. zasada
i8=j
Maksimum Wiarygodności (MW).
W zastosowaniu do naszego zadania, po niezłożonych obliczeniach, zasada ta prowadzi
1
do prostej reguły decyzyjnej: jeżeli odebrano sygnał u < , to stwierdzamy, że wysłany był
2
sygnał x1 = 0, a w przeciwnym wypadku  sygnał x2 = 1. W środowisku Matlab taką operację
progowania można zrealizować, wykorzystując funkcję sign:
Dz=sign(u-0.5)/2+0.5;
Zliczamy zera występujące w zakłóconym wektorze danych Dz:
N0=length(find(Dz<0.5))
oraz estymujemy prawdopodobieństwa p0, p1 wystąpienia zer i jedynek:
p0z=N0/Nb
p1z=1-p0z
NastÄ™pnie estymujemy entropiÄ™ H(·) zakłóconego sygnaÅ‚u (Dz) na wyjÅ›ciu kanaÅ‚u:
Heta=-p0z*log2(p0z)-p1z*log2(p1z)
Wpisujemy uzyskany wynik do sprawozdania i porównujemy z entropią z
ródÅ‚a H(¾).
Na skutek zakłóceń w kanale transmisyjnym część bitów została przekłamana. Zliczamy
ilość błędnie odebranych bitów (tzn. odległość Hamminga pomiędzy wektorami Dz, Db):
Nerr=length(find (Dz~=Db));
Możemy teraz obliczyć prawdopodobieństwo przekłamania pojedynczego bitu:
BER=Nerr/Nb
Uzyskaną wartość wpisujemy w odpowiednie miejsce sprawozdania i porównujemy z warto-
ścią teoretyczną (1 - d).
1. Estymata entropii H(·) sygnaÅ‚u na wyjÅ›ciu kanaÅ‚u: Heta=. . .
2. Porównanie z estymowaną entropią sygnału na wejściu kanału: Hksi=. . .
3. Jak należy interpretować różnicę? Czy na wyjściu jest więcej informacji?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Zmierzona bitowa stopa błędów: BER=. . .
5. Porównanie z zadanym prawdopodobieństwem błędu: (1 - d) = . . .
6. Przyczyny rozbieżności: . . . . . . . . . . . . . . .
5.4.3 Oszacowanie przepustowości kanału i sprawności transmisji
Otrzymane w poprzednim punkcie estymaty prawdopodobieństwa generacji zer (p0z) i jedy-
nek (p1z) oraz błędnej transmisji (BER) dla kanału binarnego pozwalają oszacować podsta-
wowe informacyjne charakterystyki kanału i sprawność transmisji. Tak, według wzoru (5.12),
wartość warunkowej entropii dla kanału binarnego symetrycznego będzie równa:
H(·|¾) = -d log2 d - (1 - d) log2(1 - d) (5.24)
11
i zgodnie z (5.17) określa ona przepustowość kanału:
C = 1 - H(·|¾) = 1 + d log2 d + (1 - d) log2(1 - d). (5.25)
Zmierzone wartości entropii i przepustowości otrzymujemy podstawiając do tych wzorów
w miejsce d obliczoną poprzednio estymatęBER.
Obliczenia transinformacji I(¾, ·) i sprawnoÅ›ci transmisji k prowadzimy na podstawie
wzorów:
I(¾, ·) = H(·) - H(·|¾) = H(·) + d log2 d + (1 - d) log2(1 - d), (5.26)
I(¾, ·)
k = , (5.27)
C
zastÄ™pujÄ…c w nich wartoÅ›ci teoretyczne H(·), d przez poprzednio wyznaczone wartoÅ›ciHeta,
BER. Wpisujemy wyniki obliczeń do sprawozdania i odpowiadamy na postawione niżej pyta-
nia.
Tabela 5.3: Porównanie estymowanych miar jakości kanału z wartościami teoretycznymi
H(·|¾) C I(¾, ·) k
Zmierzona wartość
Wartość teoretyczna
Różnica (w %)
1. Porównać wyniki teoretyczne i doświadczalne oraz opisać przyczyny różnic.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Jak będą zmieniały się obliczone wielkości przy zmianach poziomu szumu (sigma)
od zera do dużych wartości?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Kodowanie z
ródłowe
Rozpatrzmy bardziej złożony schemat systemu transmisyjnego, pokazany na rys. 5.2
Rysunek 5.2: Schemat systemu transmisyjnego z kodowaniem
Sygnał Db wygenerowany w poprzedniej części ćwiczenia dzielony będzie na bloki Xi o
stałej długości g bitów. Na początek przyjmiemy najmniejszą nietrywialną długość bloku:
12
g=2
Ciąg g-bitowych bloków podlega następnie kodowaniu Huffmana. Cały proces kodowania wy-
konywany jest w załączonym skrypcie Matlaba kodhuf.m:
kodhuf
Skrypt ten wykonuje grupowanie bitów w g-bitowe bloki, następnie zlicza ilości wystąpień
bloku każdego typu Xi w strumieniu danych Db i na tej podstawie konstruuje drzewo kodo-
we i słowa kodowe Di, wykorzystując do tego gotową2 funkcję huffman.m (dostępną jako
załącznik w pliku PDF).
Na koniec tworzony jest nowy strumień danych zakodowanych Dkod, w którym zamiast
bloków Xi podstawiane są odpowiadające im słowa kodowe Di o różnej długości, wynikającej
z konstrukcji drzewa kodowego Huffmana.
Skrypt kodhuf.m oblicza i wyświetla parametry zakodowanego sygnału, takie jak:
" średnia długość słowa kodowego: L,
" długość ciągu danych po zakodowaniu: Nk,
" współczynnik kompresji: ½ = Nk/Nb,
" czas potrzebny na operacjÄ™ kodowania3.
Parametry te, jak również sprawność kodu º = gH(¾)/L, należy wpisać w odpowiednie
miejsca tabeli 5.4 w sprawozdaniu, przy czym entropia H(¾) liczona jest wedÅ‚ug wzoru (5.20).
5.5.1 Właściwości zakodowanego ciągu bitów
Estymujemy prawdopodobieństwa p0, p1 wystąpienia symboli 0, 1 w zakodowanym ciągu da-
nychDkod:
N0=length(find(Dkod<0.5));
p0=N0/Lkod
p1=1-p0
Pksi=[p0 p1]'
oraz entropię zakodowanego sygnału:
Hkod=-p0*log2(p0)-p1*log2(p1)
Parametry te wpisujemy do tabeli 5.4 w sprawozdaniu.
5.5.2 Porównanie właściwości kodów dla różnych długości bloku
Powtarzamy cały proces kodowania (za pomocą skryptukodhuf) dla coraz większych dłu-
gości bloku: g = 3, 4, 5, 6. . Otrzymane wyniki wpisujemy w kolejne kolumny tabeli 5.4. Po
wypełnieniu tabeli należy wyciągnąć wnioski z badań i odpowiedzieć na pytania:
1. Jakie wartości przyjmuje entropia zakodowanego sygnału i z czego to wynika?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
R. C. Gonzalez, R. E. Woods, S. L. Eddins, Digital Image Processing Using MATLAB, Prentice-Hall, 2004.
3
Dokładniej rzecz biorąc, podawany jest tylko czas konstrukcji drzewa kodowego funkcją huffman.m.
13
Tabela 5.4: Porównanie kodów z różnymi długościami bloku g
g = 2 g = 3 g = 4 g = 5 g = 6
Liczba możliwych słów kodowych (= 2g)
Średnia długość słowa kodowego L
Sprawność kodu º = gH(¾)/L
(H(¾) wg. wzoru (5.20))
Prawdopodobieństwa wyst. symboli 0/1
w zakodowanym ciÄ…guDkod
Entropia Hkod zakodowanego ciÄ…gu
Współczynnik kompresji ½
Czas potrzebny na kodowanie
2. Jak wpÅ‚ywa dÅ‚ugość bloku g na współczynnik kompresji ½ ?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Jaki jest koszt zwiększania długości bloku g ?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Czy istnieje optymalna wartość g, biorąc pod uwagę czas potrzebny na kodowanie oraz
uzyskiwany współczynnik kompresji? Czy warto stosować bardzo długie bloki danych?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. Co się stanie w systemie, jeśli tak zakodowany sygnał zostanie przesłany przez kanał
transmisyjny wprowadzający błędy (z parametrym d < 1) ?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Literatura
1. S. Haykin, Systemy telekomunikacyjne, t.1-2, WKA
, Warszawa, 2004.
2. K. Wesołowski, Podstawy cyfrowych systemów telekomunikacyjnych, Rozdział 1, WKA
,
Warszawa, 2003.
3. S. Dymowski, Elementy teorii informacji, WPW, Warszawa, 1968.
14