kodowanie*

Podobnie dwóm innym ciągom wiadomości x 1 X3 i X3 Xi odpowiadałby wyraz kodowy 000. Zatem kod F₂ nie jest kodem jednoznacznie dekodowalnym.

Przykład:

W tym przykładzie porównamy cztery różne kody jednoznacznie dekodowalne utworzone dla tego samego zbioru wiadomości elementarnych:

Wiad.elem.F3 F4 F5 F6 x₀    00    0    0    0

xi    01    10    10    01

x₂    10    110    110    011

x₃    1111101110111

Kod F₃ demonstruje najprostszy sposób kodowania jednoznacznie dekodowalnego: wszystkie wyrazy kodu sąjednakowej długości

są w systemie dwójkowym kolejnymi liczbami numerującymi wiadomości

00 = 0*21 -+0*20 = 0 01 =0*21 +1*20=1 10 = 1*21 +0*20 = 2 11 = 1*21 +1*20 = 2 + 1 =3

Konwersja dwójkowo-dziesiętna:

Jeśli w wyraża się przez 4 03 a₂ oh w zapisie binarnym, to w zapisie dziesiętnym odpowiada:

W = a₄2³ + «₃2² + a₂2¹ + «i2° (3.4)

Kod F₄jest tzw. kodem z przecinkiem. Funkcję przecinka rozdzielającego jeden wyraz kodowy od drugiego pełni zero. Typowym kodem z przecinkami jest alfabet Morse'a. Jest to kod przyporządkowujący literom alfabetu łacińskiego wyrazy kodowe o różnych długościach zbudowane z dwóch elementów — kropki i kreski. Ale faktycznie jest jeszcze trzeci element — dłuższa przerwa oddzielająca kolejne wyrazy kodowe odpowiadające poszczególnym literom. To ona pełni rolę przecinka.

Kod F₅ nie jest kodem przecinkowym, ale jest jednoznacznie dekodowalnym o zmiennej długości wyrazu kodowego. Ten kod można jednoznacznie zdekodować dekodując z osobna jeden wyraz po drugim. Tego nie da się niestety zrobić z kodem F₆. Jeśli odbieramy ciąg 01 to nie możemy stwierdzić czy odpowiada wiadomości xi tak długo, jak nie odbieramy następnego symbolu. Jeśli następnym symbolem jest 0, to wiemy, że odpowiada xi, ale gdyby było 1 to musimy czekać, na kolejny symbol, żeby stwierdzić czy jest to x₂ (011) czy X3 (0111). Opóźnienie jest warunkiem poprawnego dekodowania F₆.

Kod jednoznacznie dekodowalny nazywamy dekodowalnym bez opóźnienia, ieśli nie musimy czekać na pojawienie się elementów alfabetu kodu odpowiadającym dalszym wyrazom następującym po aktualnie dekodoyyanym. Takimi kodami sąF₃, F₄, F₅ ale nie F_e.

Jaki warunek winien spełniać kod, by był dekodowalny bez opóźnienia?

Niech wiadomości Xj odpowiada wyraz kodowy:

■-*!    O, )

Przedrostkiem każdego wyrazu kodowego Sj nazywamy ciąg utworzony z elementów alfabetu postaci:

O_t,_A,u_v.₂gdzie i < j < Li

np. dla wyrazu kodowego 01100111 przedrostkami sąO, 01,011,0110, 01100, 011001,0110011 i 01100111.

Widać, że wkw, aby dany kod był dekodowalny bez opóźnienia, jest by żaden pełny wyraz kodowy nie był użyty jako przedrostek jakiegokolwiek innego wyrazu kodu.