i kodowanie
Ćwiczenia IV
20. marca 2009 r.
Wstęp do kodów kanałowych, kresy związane z kodami nadmiarowymi
Zadanie 1
Udowodnij, że odległość Hamminga dla dowolnych ciągów kodowych v1 , v2 , v3 o długościach słowa n charakteryzuje się następującymi właściwościami:
1. 0 ¬ d(v1 , v2) ¬ n,
2. d(v1 , v1) = 0,
3. jeśli d(v1 , v2) = 0, to v1 = v2, 4. d(v1 , v2) = d(v2 , v1), 5. d(v1 , v2) ¬ d(v1 , v3) + d(v3 , v2).
Zadanie 2
Policz prawdopodobieństwo błędnego zdekodowania informacji kodowanej w binarnym kodzie z kontrolą parzystości, w którym długości poszczególnych słów kodowych wynoszą cztery sym-bole, zaś informacja jest transmitowana przez binarny bezpamięciowy kanał symetryczny charakteryzujący się BER = ε.
Zadanie 3
Binarny kod z powtarzaniem Rn polega na kodowaniu 0 ciągiem n zer i analogicznie dla 1: 0 → 00 . . . 0
1 → 11 . . . 1 .
|
{z
}
|
{z
}
n
n
Policz prawdopodobieństwo błędnego zdekodowania informacji kodowanej w kodzie R 3, jeśli informacja jest transmitowana binarnym bezpamięciowym kanałem symetrycznym charakteryzującym się BER = ε i stosujemy regułę decyzyjną największego prawdopodobieństwa.
Zadanie 4
Co najmniej ile pozycji kontrolnych ma binarny kod blokowy o minimalnej odległości Hamminga d min = 4, przeznaczony do zakodowania 8 wiadomości?
Zadanie 5
Określ maksymalną liczbę pozycji informacyjnych binarnego kodu nadmiarowego o długości n = 16, jeśli minimalna odległość Hamminga wynosi d min = 4.
Zadanie 6
Skonstruuj najkrótszy blokowy binarny kod nadmiarowy do zakodowania 32 wiadomości w słowa kodowe o wadze 3. Jaka jest minimalna odległość Hamminga?
Zadanie 7
Udowodnij, że jeśli istnieje kod binarny ( n, k) o odległości minimalnej d min = 2 k, to istnieje również kod binarny o tych samych parametrach ( n, k) i niegorszych właściwościach korekcyjnych, którego wszystkie słowa mają wagę parzystą.
Zadanie 8
Pewien bezpamięciowy kanał binarny zawsze poprawnie transmituje zero, natomiast jedyn-kę transmituje poprawnie z prawdopodobieństwem P . Zapisz macierz tego kanału oraz oblicz prawdopodobieństwo błędnego zdekodowania symbolu, jeśli 0 jest wysyłane z prawdopodobień-
stwem p. Następnie, zakładając że stosuje się kod z powtarzaniem R 3 (def. w zad. 3), znajdź
prawdopodobieństwo błędnego zdekodowania, jeśli stosuje się regułę decyzyjną największego prawdopodobieństwa.
Strona 1 z 2
i kodowanie
Ćwiczenia IV
20. marca 2009 r.
Informacja dodatkowa:
Na kartkach z zadaniami do kolejnych kolokwiów znajdą Państwo następujące dane: Kres górny Plotkina: d min ¬ n 2 k− 1 .
2 k − 1
Kres górny Eliasa: d
n
min ¬ 2 s
K
(1 − s ), gdzie: s, K ∈ Z oraz 2 n−k < P s
, i K jest najmniejszą liczbą całkowitą
K− 1
n
i=0
i
P s
n
i
spełniającą zależność: K i=0
.
2 n−k
Kres dolny Warszamowa-Gilberta: 2 n−k > P d− 2 n− 1 .
i=0
i
Strona 2 z 2