Czysta nauka zajmuje się abstrahowaniem i ekstrahowaniem ze skomplikowanej rzeczywistości prostych modeli. Z czasem, gdy prosty model jest dostatecznie zbadany, a istnieje potrzeba lepszego przybliżenia rzeczywistości, tworzy się modele bardziej zaawansowane. Toczy się nieustanna walka mikrochaosu z porządkiem. Ta walka jest częścią chaosu.
Zastosowania nauki są sztuką, a ten który naukę stosuje powinien być artystą, który w zastanej, niejasnej sytuacji potrafii rozpoznać jej strukturę, potrafi oddzielić mało ważne elementy od ważnych, po czym stosuje właściwy dział teorii, powiedzmy właściwy model. Przeciętny wyrobnik "stosuje" teorię, którą powierzchownie narzuca mu sformułowanie problemu lub szef.
Tak czy inaczej, będę rozpatrywał bardzo proste, aż fikcyjne kanały komunikacyjne. Celem będzie wyczucie (zrozumienie) pojęcia informacji.
Pewien serwer na swojej frontowej stronie internetowej wyświetla każdego dnia jeden z dwóch losowo wybranych obrazów, każdy z nich ma 1000x1000 = milion kropek. Gdy kolegę poinformuję, który z dwóch RGB-obrazów dziś jest wyświetlany, to czy przekazuję mu informację wartą miliona kropek (32 milionów bitów)? Nie - przekazałem informację jednobitową, jak odpowiedź na pytanie "0 czy 1?".
Powyższa fikcyjna anegdotka daje przedsmak znaczenia słowa informacja. Informacja istnieje nie absolutnie, lecz w kontekście. Inżynierzy mawiają nawet: co jest szumem dla jednego, jest informacją dla drugiego.
Rozpatrzmy kanał, który na wejściu i wyjściu przyjmuje i przekazuje tylko dwa sygnały: 0 i 1. Niech to będzie kanał dyskretny także w czasie. Działa wiecznie, zawsze, i co jedną stutysięczną sekundy przekazuje sygnal. Gdy sami nic w tej sprawie nie czynimy, to przekazuje szum, przypadkowe 0 lub 1. Na dodatek niech to będzie kanał idealny: gdy otrzymuje 0 to przekazuje na wyjściu 0, gdy 1, to 1, bez przekłamań.
Niech eksperyment lub pomiar fizyczny daje ciąg losowy dwóch możliwości, jakby Orzeł i Reszka. Prawdopodobienstwo każdej wynosi 1/2. Wiadomo, że chcemy przekazać 10 milionów kolejnych wyników, coś jakby
OOORORRORRRRROOROOO...
Zakładamy, że wiadomo, kiedy zaczynamy nadawanie, ale musimy podać metodę na rozpoznanie końca transmisji (kanał przecież zawsze coś nadaje, nie wyłącza się). Metodę przekazu musimy ustalić zawczasu. Pytanie: jaka jest najszybsza metoda kodowania (przekazująca jak najmniej znaków, które potem trzeba i można jednoznacznie odkodować)?
Co to znaczy najszybsza, gdy dla różnych ciągów wynik może być a priori różny, w zależności od ciągu (i od ustalonej metody)? Szybkość jest odwrotnie proporcjonalna do czasu transmisji, czyli do długości mierzonej liczbą nadanych sygnałów.
Jedna z odpowiedzi może w danym przykładzie brzmieć "długością procedury nazywamy średnią liczbę przekazów sygnałów". Czyli jest to suma liczb sygnałów potrzebnych dla jednorazowego przekazania każdego możliwego ciągu [;c;], podzielona przez liczbę tych ciągów:
[;\frac{\sum_c\,L(c)}{2^{{10}^7}};]
gdzie [;L(c);] jest liczbą sygnałów (bitów 0 1), potrzebną dla przesyłki ciągu [;c;]. W kontekście ogólnym teorii, to samo można ująć jako wartość spodziewaną długości transmisji czyli tak: każdy ciąg Orłów i Reszek, długości [;10^7;], ma prawdopodobieństwo wystąpienia równe
[;p(c) := 1/2^{{10}^7};]
Wtedy wartość oczekiwana jest zdefiniowana za pomocą wzoru:
[;\sum_c\,(L(c)\cdot p(c));]
Widzimy, że w danym przypadku obie definicje dają tę samą długość, więc i szybkość, przekazu, bo prawdopodobieństwa [;p(c);] są wszystkie równe.
UWAGA 0 Na ogół, przy innych zadaniach, prawdopodobieństwa [;p(c);] są różne, zależą od [;c;]. Wtedy teoria na ogół stosuje definicję z prawdopodobieństwami, gdyż właśnie ta ma znaczenie praktyczne. Definicja ze średnią arytmetyczną i tak jest jej specjalnym przypadkiem, gdy prawdopodobieństwa są równe.
Najprostsze kodowanie w powyższym przypadku przesyłania informacji o ciągu 10 milionów Orłów i Reszek wygląda tak: z góry zapowiadamy raz na zawsze, że przesyłka będzie miała 10 milionów sygnałów - dzięki temu wiadomo kiedy transmisja skończy się, przy czym każdego Orła kodujemy jako 0, oraz każdą Reszkę jako 1. Żeby było to jasnym, gdyby chodziło o ciąg dugości 6, jak ROOORR, to przekazalibyśmy 100011. Przy wyjściu, adresat (odbiorca) sam już sobie przetłumaczy (zdekoduje) każde 0 na Orła, i każde 1 na Reszkę. Jest to najprostsza procedura. Mądrość powszechna mówi, że jest to najlepsza procedura, że szybszej już nie ma. Nawiedzeni uważają to za oczywiste. Wcale to nie jest oczywiste! Każde sensowne uściślenie tego "twierdzenia" oznacza prawdziwe twierdzenie, i wtedy mądrość powszechna jest podtrzymana, ze ścisłym omówieniem "nasza procedura jest najszybsza w danym sensie. Zauważmy, że nie mówimy o przesłaniu jednego ciągu, lecz o losowym, czyli o przesyłaniu wszystkich.
Długość transmisji liczona jako wartość oczekiwana liczby sygnałów oczywiście wynosi dokładnie 10 milionów, [;10^7;].
Mądrość ludowa o optymalnośći powyższej najprostszej procedury zostałaby podważona, gdyby nie założenie, że a propos nie wiadomo, kiedy transmisja kończy się (kanał działa wiecznie, nie milknie). W przeciwnym wypadku, gdyby kanał milknął, to nie musielibyśmy wysyłać na przykład ostatniego odcinka zer, co w połowie wypadków dałoby zysk co najmniej jednego sygnału. Wartość oczekiwana długości transmisji zmniejszyłaby się co najmniej o połowę sygnału.
Spróbujmy podważyć mądrość ludową "legalnie". Umówmy się z adresatem, że zero 0 na pierwszym miejscu oznacza koniec transmisji, oraz że cały ciąg składa się wtedy wyłącznie z Orłów (zer). Gdy pierwszym wysłanym sygnałem jest 1, to po nim wysyłamy 10 milionów sygnałów po staremu, jakby się właśnie zaczęła transmisja. Może, bądźmy skąpi, gdy mamy przekazać same Orły czyli zera, a Reszkę czyli 1 jedynie na samym końcu, to sobie ten ostatni sygnał darujmy, czyli w sumie znowu wyślemy tylko 10 milionów sygnałów, zamiast 10 milionów + jeden. Jest to prawidłowa procedura, gdyż adresat za każdym razem jest w stanie rozpoznać koniec naszej transmisji.
Policzmy oczekiwaną szybkość tej procedury. Z jednej strony wspaniale zyskaliśmy przy ciągu zerowym, a z drugiej ponieśliśmy niewielką stratę przy wszystkich pozostałych ciągach poza jednym. Jaki jest bilans? Oczekiwana długość transmisji wynosi
[;1\cdot 1\cdot p + (2^L-2)\cdot (L+1)\cdot p + 1\cdot L\cdot p;]
[;=\ (2^L\cdot L + (1 + 2^L - 2\cdot(L+1) + L)\cdot p;]
[;=\ L\ +\ 1\ -\ (L+1)\cdot p\ \ >\ \ L;]
gdzie [;L := 10^7;] jest długością ciągu Orłów i Reszek, oraz
[;p := \frac{1}{2^L} = \frac{1}{2^{{10}^7}};]
jest prawdopodobieństwem jednego ciągu, dowolnego. Widzimy, że średnia długość transmisji wzrosła prawie o jeden sygnał - niewiele, ale jednak.
Powróćmy do niepoprawnej procedury ucinania ogona zer. Poszło o drobiazg :-). Gdybyśmy mogli zaznaczyć jakoś koniec transmisji, to wszystko byłoby w porządku. Wystarczyłoby na koniec dać sygnał 2. Oznaczałoby to jednak inny, bardziej złożony (droższy) kanał, zdolny do przesyłania trójkowych bitów (0 1 2) zamiast dwójkowych (0 1).
W ramach naszego zwykłego kanału binarnego można próbować zakodować koniec transmisji jako specjalny ciąg kilku 0 i 1. Wtedy jednak płacimy karę, bo na koniec przesyłamy ten dodatkowy kod. Co gorsza, w trakcje transmisji musimy unikać przesłania kodu końca transmisji przedwcześnie, co powoduje dodatkowe wydłużanie kodu. Tymczasem zysk z ucinania ogona, gdy nie martwimy się o zaznaczenie końca transmisji, wynosi dokładnie jeden sygnał minus [;1/2^L;] (przeciętnie). Niełatwo zmieścić kod końca transmisji w ramach jednego sygnału minus [;1/2^L;], a nawet jest to niemożliwe - zresztą próbujcie, bo to może być dobre ćwiczenie.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment