Jak w poprzedniej Części 1, rozpatruję kanał binarny, czyli przyjmujący i przekazujący na zewnątrz sygnały 0 1. Zakładam, że bezbłędnie co kanał otrzyma to przekaże.
Tym razem chcemy przekazać ciąg wyników rzutów kostką, przy czym obchodzi nas tylko, czy wypadło 6. Oznaczając wynik 6 przez "S" (sukces), a pozostałą możliwość (od 1 do 5) przez F, z każdym ciągiem rzutów kostką możemy związać ciąg liter S i F. Jak przekazać te informację, jak ją kodować?
Mógłby ktoś machnąć ręką na litery, by po prostu przekazywać wyniki rzutów, na przykład
2 6 1 1 4 3 4 3 5 6 3 3 ...
By tak dosłownie postąpić, to potrzebny byłby kanał przekazujący bity szóstkowe 1 2 3 4 5 6. Taki kanał jest bardziej złożony od binarnego. Byłaby w takim postępowaniu marnacja, gdyż interesują nas tylko wygrane:
F S F F F F F F F S F F ...
Więc możemy użyć kanału binarnego, wysyłając tyle samo sygnałów, ale prostszych (0 1), gdzie 0 kodowałoby F, oraz 1 kodowałoby S. Wtedy powyższy ciąg rzutów kostki byłby zakodowany w sposób zredukowany, ale adekwatny dla naszego zadania:
0 1 0 0 0 0 0 0 0 1 0 0 ...
Powiedzmy, że za każdym razem wysyłamy 12 milionów wyników rzutów kostki (może chodzi o zachowanie jakiejś siatki krystalicznej, a nie dosłownie o kostkę do Chińczyka). Czy rzeczywiście musimy wysyłać aż tyle sygnałów? W przypadku rzutów monetą podobna procedura była optymalna. Zachodzi jednak istotna różnica. W przypadku monety, szansa zarówno Orła jak i Reszki była równa 1/2. Tym razem szansa wygranej S jest 1/6, a przegranej F aż 5/6. Nie widać jak z tego skorzystać bezpośrednio, gdy mamy przecież za każdym razem możliwe dwa różne wyniki (F lub S) oraz dwa różne sygnały do dyspozycji (0 oraz 1). Postęp uzyskamy kodując nie pojedyncze znaki F i S, lecz na przykład ich trójki, choćby tak:
- FFF → 0
- FFS → 100
- FSF → 101
- SFF → 110
- FSS → 11100
- SFS → 11101
- SSF → 11110
- SSS → 11111
Dla ilustracji zapiszmy wcześniejszy ciąg FSFFFFFFFSFF..., grupując symbole po trzy:
FSF FFF FFF SFF ...
Ciąg ten nowa metoda zakoduje tak (dodaję odstępy by było lepiej widać kodowanie):
101 0 0 110 ...
czyli zamiast 12 sygnałów przesyłanych wcześniejszą metodą, obecna przesyła tylko 8. Popatrzmy teraz jak jest ogólnie, to znaczy policzmy oczekiwaną długość przesyłki. Uczyńmy to najpierw dla przesyłki XYZ ciągu trzech symboli F S. Prawdopodobieństwo ciągu XYZ (gdzie każde X Y Z oznacza albo S albo F) dane jest wzorem:
[;p(XY\!Z) := \left(\frac{1}{6}\right)^{3-f}\cdot \left(\frac{5}{6}\right)^f = \frac{5^f}{6^3};]
gdzie [;f;] jest liczbą wystąpień F w ciągu XYZ. Grupując ciągi według [;f;] równego 0 1 2 lub 3, otrzymujemy następujące wyrażenie dla długości oczekiwanej kodu ciągu długości 3:
[;1\cdot 5\cdot\frac{1}{6^3} + 3\cdot 5\cdot\frac{5}{6^3} + 3\cdot 3\cdot\frac{5^2}{6^3} + 1\cdot 1\cdot\frac{5^3}{6^3} = \frac{215}{108};]
Każdy ciąg XYZ trzech liter F S możemy zakodować przez średnio niecałe dwie cyfry 0 1. Zatem ciąg 12 milionów liter F S możemy zakodować przez średnio mniej niż 8 milionów znaków 0 1. Jest tak dlatego, że S występuje średnio 5 razy rzadziej niż F. Możemy odtąd uważać, że informacja zawarta w strunie 12 milionów znaków F S jest średnio warta mniej niż zapis ciągu 8 milionów znaków 0 1.
Lepiej oszczędność kodowania liczyć nie w przeliczeniu na 3 lub 12 milionów znaków tekstu źródłowego, lecz dla jednego znaku. Czyli współczynnik oszczędności (kompresji) naszego kodowania (dla tekstów [;A;], których długość [;|A|;] jest podzielna przez 3) wynosi:
[;\frac{\frac{215}{108}}{3} = \frac{215}{324} < 2/3;]
Współczynnik oszczędności pozwala porównywać wydajność kodowania tekstów o różnej długości - im niższy współczynnik, tym wydajniejsze kodowanie. Zrobiliśmy kolejny krok w kierunku zrozumienia informacji w sensie Shannona.
UWAGA 0 Żaden z powyższych 8 wyrazów kodu:
0 100 101 110 11100 11101 11110 11111
nie jest prefiksem (czyli odcinkiem początkowym) żadnego innego wyrazu.
UWAGA 1 Dzięki własności z Uwagi 0, nasze kodowanie jest wierne, czyli daje się jednoznacznie odkodować - gdy teksty źródłowe [;A\ B;] są różne, to ich zakodowane wersje [;K(A)\ K(B);] też są różne:
[;A\ne B \Rightarrow K(A)\ne K(B);]
W przeciwnym razie, gdy [;K(A) = K(B);], nie moglibyśmy zdecydować, czy tekstem źródłowym było [;A;] czy [;B;], lub może jeszcze co innego.
W praktyce wierność to za mało. Potrzebny jest algorytm (i to wydajny), który potrafi obliczyć [;A;], gdy dane jest [;K(A);]. Właśnie taką pożądaną, wygodną sytuację mamy, gdy żaden wyraz kodu nie jest prefiksem innego wyrazu kodu.
UWAGA 2 Występuje pewna drobna nieregularność przy naszym kodowaniu odcinkami złóżonych z trzech znaków F S. Co będzie, gdy długość tekstu żródłowego (czyli liczba występujących w nim znaków F S) nie jest podzielna przez 3? Powiedzmy, że tekst żródłowy miał 12 milionów i jeden znak. Rozwiązanie jest proste: przedłużamy tekst o znak lub dwa znaki F, tak by jego długość stała się podzielna przez 3. W przypadku 12 milionów i jednego znaku, tekst przedłużymy o strunę FF. Współczynnik oszczędności kodowania
[;\frac{|K(A)|}{|A|};]
dalej w mianowniku ma 12000001, a nie 12000003. Więc przeciętna oszczędność kodowania w przypadku przedłużonych tekstów jest nieco gorsza niż dla tekstów, których długość jest okrągłą wielokrotnością 3. Przy długich tekstach nie ma to większego znaczenia (nadwyżka współczynnika oszczędności dąży do zera, gdy długość źródłowego tekstu dąży do nieskończoności). Tak działa oddech nieskończoności. Pozwala zaniedbywać drobne komplikacje.
No comments:
Post a Comment