2010-12-13 12:56:00 (2010-12-13 12:57:00) Podstawy Systemów Informacyjnych – ćwiczenia Ćw. 7. Kodowanie kanałowe – podstawowe pojęcia Zagadnienia: Odległość Hamminga, minimalna odległość Hamminga, właściwości korekcyjne i detekcyjne, kod idealny, ocena jakości kodu (wykorzystanie kanału, blokowa stopa błędu, prawdopodobieństwo niewykrycia błędu), odległościowa reguła dekodowania.
Kod o odległości minimalnej d H, min cechują zdolności detekcyjne (wykrywa ciągi błędów o wadze do det) det = d H, min – 1
albo zdolności korekcyjne
(poprawia ciągi błędów o wadze do t)
dH,min −1
t =
2
Parametr t jest promieniem n-wymiarowej kuli w przestrzeni Hamminga o objętości
∑ t n
n
!
n
; gdzie =
jest symbolem Newtona (liczba kombinacji „z n po i”).
i
( n − i)! !
i
0
i
i=
Dla blokowego kodu kanałowego ( n, k) o zdolnościach korekcyjnych t zachodzi n
k
2 ∑
t
n
≤ 2
0
i
i=
Dla blokowego kodu kanałowego ( n, k) idealnego zachodzi n
k
2 ∑
t
n
= 2
0
i
i=
Blokowa stopa błędu
∞
BSB ≈ ∑ n i
n i
P
P
b (1
b ) −
−
i
i= t +
1
dla Pb << 1
n
1
+
BSB ≅
t
P
t +1 b
Prawdopodobieństwo niewykrycia błędu
n det 1+
PNB ≈
P
det+1 b
Odległościowa reguła dekodowania (reguła „najbliższy sąsiad”): y : *
*
x ← s : min d (s, y) H
s
∀
y – ciąg odebrany, x* – zdekodowany ciąg informacyjny (decyzja), s* - ciąg kodowy najbliższy odebranemu ciągowi y.
Zad. 1. Dla kodów powtórzeniowych z jedną pozycją informacyjną ( k = 1) o różnych długościach ( n = 2, 3, 4, 5) określić zdolności korekcyjne i detekcyjne poszczególnych kodów oraz sprawdzić czy są to kody idealne.
Ocenić wykorzystanie kanału (zawartość informacyjną kodów), BSB (blokową stopę błędu) oraz prawdopodobieństwo niewykrycia błędy.
2010-12-13 12:56:00 (2010-12-13 12:57:00) Zad. 2. Dla kodu o k = 2 i n = 5 zdefiniowanego poniższym układem równań generujących s
⊕
⊕
⊕
1 = x 1, s 2 = x 2, s 3 = x 1
x 2, s 3 = s 2 s 3, s 3 = s 1 s 3.
określić jego zdolności korekcyjne i detekcyjne oraz sprawdzić czy jest to kod idealny.
Zdekodować następujące ciągi: „01101”, „11111”, „01010”, „00010”.
Zad. 3. Dla kodu o k = 3 i n = 6 zdefiniowanego poniższym układem równań generujących s
⊕
⊕
⊕
1 = x 1, s 2 = x 2, s 3 = x 3, s 4 = s 1
s 2, s 5 = s 2 s 3, s 6 = s 1 s 3.
określić jego zdolności korekcyjne i detekcyjne oraz sprawdzić czy jest to kod idealny.
Zdekodować następujące ciągi: „011010”, „111111”, „010100”, „000100”.
Zad. 4. Dla kodów z zadań 2-3 określić ich zawartość informacyjną oraz oszacować blokową stopę błędu dla BER = 10-3 oraz BER = 10-6. Dodatkowo oszacować prawdopodobieństwo niewykrycia blędu.