Część 2 poświęcona była strunom losowym, złożonych z symboli F S, w których każde wystąpienie symbolu było niezależne od pozostałych, ale tym razem prawdopodobieńtwa wynosiły 1/6 i 5/6. Takie struny (gdy nie są zbyt krótkie) dają się skompresować średnio lepiej niż 2/3 razy niż w przypadku prawdopodobieństw 1/2:1/2. Czyli jeden symbol takiej informacji jest wart mniej niż 2/3 symbolu 0-1 struny losowej o równych prawdopodobieństwach dla 0 i 1.
Poniżej zajmiemy się łatwiejszym zadaniem. Porównamy kanał ternarny, przesyłający bezbłędnie symbole 0 1 2, z bezbłędnym binarnym, przesyłającym symbole 0 1. Takie porównanie może być ważne dla biznesu. Kanał trójkowy jest droższy, ale efektywniejszy. Co opłaca się lepiej, mieć dwa kanały trójkowe, czy trzy dwójkowe? Odpowiedź może zależeć od wielu czynników, ale między innymi od porównania poniżej.
Powiedzmy, że z ternarnego kanału otrzymujemy ciąg niezależnych symboli 0 1 2, z równymi prawdopodobieństwami 1/3. Mamy go przesłać w świat, a raczej informację, używając kanał binarny. Każdy trójkowy bit możemy zastąpić przez dwa bity dwójkowe jak następuje:
- 0 ➔ 00
- 1 ➔ 01
- 2 ➔ 10
(Gdy wyrazy kodu są jednakowej długości, to oczywiście kod się dekoduje, i to łatwo). Widzimy, że trójkowy bit jest wart nie więcej niż dwa dwójkowe (z pewnością mniej, bo nie wykorzystaliśmy 11, ale o tym później).
I na odwrót, gdy otrzymujemy informację w postaci bitów dwójkowych 0 1, a mamy ją dalej przekazać kanałem trójkowym, to każdy symbol binarny 0 1 zastępujemy tym samym 0 lub 1, ale traktowanym jako bit trójkowy. Zatem bit dwójkowy jest nie więcej wart niż jeden bit trójkowy (zobaczymy, że wyraźnie mniej).
Nie chcę urazić Meksykańczyków, ale mnie goła takila nie smakuje. Drugi i dalsze kieliszki piję już jednak z lodem i czym tak jeszcze - wódce nigdy bym tak nie ubliżył (chyba, że w gościach, to trudno, gdakam w Rzymie jak starożytni). Wszystko jedno takila pomaga mi nie przejmować się zbytnio edytorem, pije się chropowato, ale pisze się gładziej. (Dzieci, nie czytać tego. Banach powiedział, że matematyka nie jest dla dzieci.) Co do jakości mojej noty? Cóż, to się nazywa po angielsku trade-off (coś za coś). W moim subiektywnym odczuciu, moja (c)nota tylko zyskuje.
Wykorzystajmy nierówności typu
[;3^k < 2^n;]
oraz
[;3^k > 2^n;]
dla porównania kanału trójkowego z dwójkowym. Na przykład:
- [;3 < 2^2;]
- [;3^3 < 2^5;]
- [;3^5 < 2^8;]
Pierwszą nierówność już wykorzystaliśmy. Powiedziała nam, że trójkowy bit jest wart co najwyżej dwa bity dwójkowe. Następna nierówność mówi nam że co najwyżej 5/3, a ostatnia, że 8/5 lub mniej. Ogólnie nierówność [;3^k < 2^n;] mówi nam, że bit trójkowy jest wart co najwyżej [;n/k;] bitu dwójkowego. Rzeczywiście, każdą z [;3^k;] strun trójkowych, długości [;k;] możemy zastąpić przez dwójkową, o długości [;n;], przy czym różne przez różne.
Podobnie nierówności:
- [;3 > 2;]
- [;3^2 > 2^3;]
- [;3^{12} > 2^{19};]
mówią nam kolejno, że bit trójkowy jest wart co najmniej jednego dwójkowego; następna nierówność - że co najmniej półtora czyli 3/2 dwójkowego; a ostatnia, że nawet 19/12 lub więcej. Otrzymaliśmy łącznie nierówność:
(19/12)*info(bit2) < info(bit3) < (8/5)*info(bit2)
Można też porównanie prowadzić w drugą stronę, gdy bity dwójkowe tłumaczymy na trójkowe:
(5/8)*info(bit3) < info(bit2) < (12/19)*info(bit3)
Prosta teoria liczb mówi nam, że istnieją coraz większe wykładniki [;k'\ k''\ n'\ n'';] takie, że:
- [;2^{k'} < 3^{n'};]
- [;2^{k''} > 3^{n''};]
oraz oba ułamki po bokach następujących (oczywiście prawdziwych) nierówności:
[;\frac{k'}{n'} < \log_2(3) < \frac{k''}{n''};]
przybliżają [;\log_2(3);] z dowolną dokładnością. Ta obserwacja daje dobry powód, żeby uważać trójkowy bit informacji wart [;\log_2(3);] dwójkowego bitu informacji. Dalsze twierdzenia pokażą, że to jest głęboko uzasadniona opinia. (Podobnie można uważać, że jeden bit dwójkowy jest wart [;\log_3(2);] bitu trójkowego; ze szkoły wiecie, że
[;\log_3(2) = \frac{1}{\log_2(3)};]
Wszystko dzieje się harmonijnie.)
Chociaż polskie wychowanie burzy się przed tym co jako naukowiec muszę obiektywnie przyznać, wartość kolejnych kieliszków takili (czy jak tam to się spelluje), po pięciu maleje eksponencjalnie (za to smak się po trochu poprawia). Jednak kończę tę notę, jakże niechętnie, z innego powodu. Muszę wkrótce lecieć (takila itp zmiękcza "muszę", ale obowiązek, to obowiązek). Nie chcę się spieszyć z pisaniem przesadnie, przerwać coś w połowie, lub pisać na siłę, i wszystko zapaprać. Zresztą butelka wyschła. Z lodem i itp, jak wiecie, to nic nie jest. 3/4L. Przysięgam, że nie była pełna. Szkoda, że nie była pełna. Żal. Koniec takilowych zwierzeń.
No comments:
Post a Comment