Kodowanie źródła (Język monet: 4/9)

Wstęp do teorii kodowania (kodowanie źródła ze zróżnicowaniem długości) wraz z przykładem kompresji bezstratnej. Ten uproszczony przykład dotyczy wysyłania pojedynczych symboli za pomocą symboli jednoargumentowych (szarpnięć drutu). Kodowanie źródła obejmuje kompresję danych aby zwiększyć wydajność przesyłania.

Rozpocznijmy od przykładu..

[wieje wiatr]

Alicja i Bob mieszkają w w domkach na drzewie, daleko od siebie, poza linią wzroku.

I muszą się porozumiewać. Poprowadzili więc drut między dwoma domami.

[szum wiatru, dudnienie, zakłócenia]

Naciągają przewód mocno i dołączają puszkę na każdym końcu.

[dudnienie, stukanie metalu]

Co ma umożliwić im przesyłanie drutem słabego głosu.

[Słychać "Hello" bardzo niewyraźnie]

[Alice]: Nie słyszę cię.

[Bob]: Słyszę cię, ale słabo

[Alice]: 1,2,3,4,5

Pojawia się jednak problem.

Szum

Ilekroć wystąpi silny wiatr, staje się niemożliwe usłyszenie sygnału w szumie.

Potrzebują więc sposobu na zwiększenie poziomu energii sygnału by oddzielić go od szumu.

To podsuwa Bobowi pomysł.

Mogą po prostu szarpać drut, co można łatwiej wykryć pośród szumu.

Prowadzi to jednak do kolejnego problemu: jak zakodować wiadomości jako szarpnięcia?

Cóż, skoro chcą grać w gry planszowe na odległość, muszą zająć się najczęściej występującymi komunikatami.

Wynikiem rzutu dwóch kości. W tym przypadku komunikaty jakie wysyłają można uznać za wybór ze skończonej liczby symboli.

W tym przypadku, jedenastu możliwych liczb, które można uznać za źródło dyskretne.

Początkowo stosują najprostrzą metodę. Wysyłają wynik jako liczbę szarpnięć.

Więc aby wysłać trzy, wysyłają trzy szarpnięcia.

Dziewięć to dziewięć szarpnięć, a dwanaście to dwanaście szarpnięć

Jednak wkrótce zauważają, że trwa to znacznie dłużej, niż musi.

Obserwują w praktyce, że maksymalna prędkość to

2 szarpnięcia na sekundę. Szybciej i będą się mylić. Więc dwa szarpnięcia na sekundę można uznać za prędkość

lub zdolność do przesyłania informacji w ten sposób. [Słychać szarpnięcia]

Okazuje się, że najczęstrzym wynikiem jest siedem, wysłanie liczby 7 zajmuje 3,5 sekundy, [słychać siedem szarpnięć]

Alice dostrzega, że można to zrobić znacznie lepiej, gdyby zmienili oni strategię kodowania.

Dostrzega ona, że szansę wysłania każdej z liczb określa następujący schemat.

Jest 1 sposób wyrzucenia 2, 2 sposoby, aby wyrzucić 3, 4 - aby wyrzucić pięć, 5 - aby wyrzucić sześć, najczęściej 6 sposobów, aby wyrzucić 7, 5 - aby wyrzucić osiem

4 sposoby aby wyrzucić 9 i tak dalej aż do 1 sposobu wyrzucenia 12. Powstaje wykres ilości sposobów wyrzucenia każdego możliwego wyniku,

A prawidłowość jest oczywista. Zmieńmy więc teraz wykres na ilość szarpnięć przyporządkowaną każdemu symbolowi.

Następnie przypisuje ona najczęstrzy wynik 7 najkrótszemu sygnałowi, jednemu szarpnięciu.
[Słychać jedno szarpnięcie]

Przechodzi do kolejnego najbardziej prawdopodobnego wyniku, a jeśli jest remis (kilku), wybiera jeden przypadkowo.

W tym przypadku, przypisuje 6 dwa szarpnięcia, następnie 8 trzy szarpnięcia, a następnie z powrotem 5 - cztery szarpnięcia, a 9 - pięć szarpnięć itd. aż aż dotrzemy do 12,

któremu przypisano 11 szarpnięć. Teraz najczęściej występująca liczba 7 może być wysłana w czasie mniejszym niż 1 sekunda, ogromna poprawa.

Ta prosta zmiana pozwala im przesłać więcej informacji w tym samym czasie.

W tym prostym przypadku, przyjęta strategia kodowania jest optymalna, ponieważ nie jest możliwe wymyślenie krótszej metody

na wysłanie wyniku rzutu dwóch kostek stosując identyczne szarpnięcia. Jednak używając drutu przez pewien czas,

Bob wpada na nowy pomysł

[Brak dźwięku]