Kod o zmiennej długości - Variable-length code

W teorii kodowania kod o zmiennej długości to kod, który odwzorowuje symbole źródłowe na zmienną liczbę bitów.

Kody o zmiennej długości mogą umożliwiać kompresję i dekompresję źródeł z zerowym błędem ( bezstratna kompresja danych ) i nadal odczytywanie symbol po symbolu. Przy odpowiedniej strategii kodowania niezależne i identycznie rozmieszczone źródło może być skompresowane niemal dowolnie blisko swojej entropii . Jest to w przeciwieństwie do metod kodowania o stałej długości, dla których kompresja danych jest możliwa tylko dla dużych bloków danych, a każda kompresja przekraczająca logarytm całkowitej liczby możliwości wiąże się ze skończonym (choć być może arbitralnie małym) prawdopodobieństwem niepowodzenia.

Kilka przykładów znanych ze zmienną długość strategii kodowania jest kodowanie Huffmana , Lempel-Ziv , kodowanie arytmetyczne lub kontekst adaptacyjnego kodowania o zmiennej długości .

Kody i ich rozszerzenia

Rozszerzeniem kodu jest odwzorowanie sekwencji źródłowych o skończonej długości na ciągi bitów o skończonej długości, które jest uzyskiwane przez łączenie dla każdego symbolu sekwencji źródłowej odpowiedniego słowa kodowego wytworzonego przez kod oryginalny.

Używając terminów z teorii języka formalnego , dokładna definicja matematyczna jest następująca: Niech i będzie dwoma skończonymi zbiorami, zwanymi odpowiednio alfabetem źródłowym i docelowym . Kod jest całkowita funkcja mapowania każdego symbolu z do sekwencji symboli ponad i przedłużenie do homomorfizmu z INTO , co naturalnie odwzorowuje każdą sekwencję symboli źródłowych do docelowych sekwencji symboli, określa się jako jej przedłużenie . ${\displaystyle S}$${\displaystyle T}$ ${\ Displaystyle C: S \ do T ^ {*}}$${\displaystyle S}$${\displaystyle T}$${\displaystyle C}$${\ Displaystyle S ^ {*}}$${\ Displaystyle T ^ {*}}$

Klasy kodów o zmiennej długości

Kody o zmiennej długości mogą być ściśle zagnieżdżone w kolejności malejącej ogólności jako kody nieosobliwe, kody jednoznacznie dekodowalne i kody przedrostkowe. Kody prefiksów są zawsze jednoznacznie dekodowalne, a te z kolei zawsze nie są pojedyncze:

Niepojedyncze kody

Kod nie jest pojedynczy, jeśli każdy symbol źródłowy jest mapowany na inny niepusty ciąg bitów, tj. mapowanie z symboli źródłowych na ciągi bitów jest injective .

• Na przykład mapowanie nie jest pojedyncze, ponieważ zarówno „a” jak i „b” są mapowane na ten sam ciąg bitów „0” ; każde rozszerzenie tego mapowania wygeneruje kodowanie stratne (bezstratne). Takie pojedyncze kodowanie może być nadal przydatne, gdy pewna utrata informacji jest akceptowalna (na przykład, gdy taki kod jest używany w kompresji audio lub wideo, gdzie kodowanie stratne staje się równoważne kwantyzacji źródłowej ).${\ Displaystyle M_ {1} = \ {\, a \ mapsto 0, b \ mapsto 0, c \ mapsto 1 \, \}}$
• Jednak odwzorowanie nie jest pojedyncze ; jego rozszerzenie wygeneruje bezstratne kodowanie, które przyda się do ogólnej transmisji danych (ale ta funkcja nie zawsze jest wymagana). Należy zauważyć, że nie jest konieczne, aby kod w liczbie pojedynczej był bardziej zwarty niż kod źródłowy (a w wielu aplikacjach większy kod jest przydatny, na przykład jako sposób wykrywania i/lub odzyskiwania po błędach kodowania lub transmisji, lub aplikacje zabezpieczające do ochrony źródła przed niewykrywalną manipulacją).${\ Displaystyle M_ {2} = \ {\, a \ mapsto 1, b \ mapsto 011, c \ mapsto 01110, d \ mapsto 1110, e \ mapsto 10011, f \ mapsto 0 \}}$

Wyjątkowo dekodowalne kody

Kod jest jednoznacznie dekodowany, jeśli jego rozszerzenie nie jest pojedyncze (patrz wyżej). To, czy dany kod jest jednoznacznie dekodowany, można określić za pomocą algorytmu Sardinasa-Pattersona .

• Mapowanie jest jednoznacznie dekodowalne (można to zademonstrować patrząc na następujący zestaw po każdym docelowym ciągu bitów w mapie, ponieważ każdy ciąg bitów jest kończony, gdy tylko zobaczymy bit 0, który nie może następować po żadnym istniejącym kodzie, aby utworzyć dłuższy ważny na mapie, ale jednoznacznie rozpoczyna nowy kod).${\displaystyle M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}}$
• Rozważ ponownie kod z poprzedniej sekcji. Kod ten nie jest jednoznacznie dekodowany, ponieważ ciąg 011101110011 może być interpretowany jako ciąg słów kodowych 01110 – 1110 – 011 , ale także jako ciąg słów kodowych 011 – 1 – 011 – 10011 . W ten sposób cdb i babe podają dwa możliwe dekodowania tego zakodowanego łańcucha . Jednak taki kod jest przydatny, gdy zbiór wszystkich możliwych symboli źródłowych jest całkowicie znany i skończony lub gdy istnieją ograniczenia (na przykład składnia formalna), które określają, czy elementy źródłowe tego rozszerzenia są dopuszczalne. Takie ograniczenia pozwalają na dekodowanie oryginalnej wiadomości przez sprawdzenie, które z możliwych symboli źródłowych odwzorowanych na ten sam symbol są ważne w ramach tych ograniczeń.${\displaystyle M_{2}}$

Kody przedrostkowe

Kod jest kodem prefiksu, jeśli żaden ciąg bitów docelowych w mapowaniu nie jest prefiksem ciągu bitów docelowych innego symbolu źródłowego w tym samym mapowaniu. Oznacza to, że symbole mogą być dekodowane natychmiast po odebraniu całego ich słowa kodowego. Inne powszechnie stosowane nazwy tej koncepcji są prefix-wolny kod , kod chwilowe lub bezkontekstowych kod .

• Przykładowe mapowanie w poprzednim akapicie nie jest kodem prefiksu, ponieważ po odczytaniu ciągu bitowego „0” nie wiemy, czy koduje on symbol źródłowy „a”, czy jest to prefiks kodowania „b” lub symbole „c”.${\displaystyle M_{3}}$
• Poniżej przedstawiono przykład kodu prefiksu.

Przykład kodowania i dekodowania:

aabakdab → 00100110111010 → |0|0|10|0|110|111|0|10| → aabakdab

Szczególnym przypadkiem kodów prefiksowych są kody blokowe . Tutaj wszystkie słowa kodowe muszą mieć tę samą długość. Te ostatnie nie są zbyt przydatne w kontekście kodowania źródłowego , ale często służą jako kody korygujące błędy w kontekście kodowania kanału .

Innym szczególnym przypadkiem kodów prefiksowych są kody o zmiennej długości , które kodują dowolnie duże liczby całkowite jako ciąg oktetów — tj. każde słowo kodowe jest wielokrotnością 8 bitów.

Zalety

Zaletą kodu o zmiennej długości jest to, że nieprawdopodobnym symbolom źródłowym można przypisać dłuższe słowa kodowe, a prawdopodobnym symbolom źródłowym można przypisać krótsze słowa kodowe, dając w ten sposób niską oczekiwaną długość słowa kodowego. Dla powyższego przykładu, jeśli prawdopodobieństwa (a, b, c, d) byłyby , oczekiwana liczba bitów użytych do reprezentowania symbolu źródłowego przy użyciu powyższego kodu byłaby: ${\ Displaystyle \ textstyle \ lewo ({\ Frac {1} {2}}, {\ Frac {1} {4}}, {\ Frac {1} {8}}, {\ Frac {1} {8} }\Prawidłowy)}$

${\displaystyle 1\razy {\frac {1}{2}}+2\razy {\frac{1}{4}}+3\razy {\frac{1}{8}}+3\razy {\ frac {1}{8}}={\frac {7}{4}}}$.

Ponieważ entropia tego źródła wynosi 1,7500 bitów na symbol, ten kod kompresuje źródło tak bardzo, jak to możliwe, aby można było odzyskać źródło z zerowym błędem.

Uwagi

Bibliografia

• Berstel, Jean; Perrin, Dominik; Reutenauer, Christophe (2010). Kody i automaty . Encyklopedia Matematyki i jej Zastosowania. 129 . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-88831-8. Zbl  1187.94001 . Wersja robocza dostępna online