Twierdzenie Shannona o kodowaniu źródłowym - Shannon's source coding theorem
Teoria informacji |
---|
W teorii informacji , źródło twierdzenie Shannona kodowanie (lub bezgłośny twierdzenie kodowania ) ustala granice możliwej kompresji danych oraz znaczenie operacyjne entropii Shannona .
Twierdzenie o kodowaniu źródłowym, nazwane na cześć Claude'a Shannona , pokazuje, że (w granicy, ponieważ długość strumienia niezależnych i identycznie rozłożonych danych zmiennej losowej (iid) dąży do nieskończoności) niemożliwe jest skompresowanie danych w taki sposób, że współczynnik kodowania (średnia liczba bitów na symbol) jest mniejsza niż entropia Shannona źródła, bez praktycznie pewności, że informacje zostaną utracone. Jednak możliwe jest uzyskanie współczynnika kodowania arbitralnie bliskiego entropii Shannona, przy znikomym prawdopodobieństwie utraty.
Kodowania źródłowego twierdzenie kodów symboli umieszcza górną i dolną granicę minimalnej możliwej oczekiwanej długości słów kodowych w zależności od entropii słowa wejściowego (który jest postrzegany jako zmiennej losowej ) oraz wielkości alfabetu docelowej.
Sprawozdania
Kodowanie źródłowe to mapowanie z (sekwencji) symboli ze źródła informacji na sekwencję symboli alfabetu (zwykle bitów), tak że symbole źródłowe mogą być dokładnie odzyskane z bitów binarnych (bezstratne kodowanie źródłowe) lub odzyskane z pewnymi zniekształceniami ( stratne kodowanie źródłowe). To jest koncepcja kompresji danych .
Twierdzenie o kodowaniu źródłowym
W teorii informacji twierdzenie o kodowaniu źródłowym (Shannon 1948) nieformalnie stwierdza, że (MacKay 2003, s. 81, Cover 2006, Chapter 5):
N i.id zmiennych losowych każda entropią H ( X ) mogą być skompresowane na więcej niż N H ( X ) bitów ze znikomym ryzykiem utraty informacji, jak N → ∞ ; ale odwrotnie, jeśli są one skompresowane do mniej niż NH ( X ) bitów, jest praktycznie pewne, że informacje zostaną utracone.
Twierdzenie o kodowaniu źródłowym dla kodów symboli
Niech Σ 1 , Σ 2 oznaczają dwa skończone alfabety i niech Σ*
1i Σ*
2oznaczają zbiór wszystkich skończonych słów z tych alfabetów (odpowiednio).
Załóżmy, że X jest zmienną losową przyjmującą wartości w Σ 1 i niech f będzie jednoznacznie dekodowalnym kodem z Σ *
1do Σ*
2gdzie |Σ 2 | = . Niech S oznacza zmienną losową określoną przez długość słowa kodowego f ( X ) .
Jeśli f jest optymalne w tym sensie, że ma minimalną oczekiwaną długość słowa dla X , to (Shannon 1948):
Gdzie oznacza operator wartości oczekiwanej .
Dowód: twierdzenie o kodowaniu źródłowym
Biorąc pod uwagę, że X jest źródłem iid , jego szereg czasowy X 1 , ..., X n jest iid z entropią H ( X ) w przypadku wartości dyskretnej i entropią różniczkową w przypadku wartości ciągłej. Twierdzenie o kodowaniu źródła mówi, że dla dowolnego ε > 0 , tj. dla dowolnej szybkości H ( X ) + ε większej niż entropia źródła, n jest wystarczająco duże, a koder przyjmuje n iid powtórzeń źródła, X 1: n i odwzorowuje go na n ( H ( X )+ ε ) bitów binarnych tak, że symbole źródłowe X1 : n są możliwe do odzyskania z bitów binarnych z prawdopodobieństwem co najmniej 1- ε .
Dowód osiągalności. Napraw jakieś ε > 0 i niech
Typowy zestaw, Aε
n, definiuje się następująco:
Asymptotycznej ekwipartycji obiektu (AEP) wynika, że dla dostatecznie dużej n , prawdopodobieństwo tego, że sekwencja generowana przez źródło leży w typowym zestawieε
n, jak zdefiniowano, zbliża się do jednego. W szczególności, dla wystarczająco dużego n , może być dowolnie bliski 1, a konkretnie większy niż (patrz
AEP dla dowodu).
Z definicji typowych zbiorów wynika, że te sekwencje, które leżą w typowym zbiorze, spełniają:
Zwróć uwagę, że:
- Prawdopodobieństwo wylosowania ciągu z Aε
njest większa niż 1 − ε . - , który wynika z lewej strony (dolna granica) dla .
-
, co wynika z górnego ograniczenia for i dolnego ograniczenia całkowitego prawdopodobieństwa całego zbioru Aε
n.
Ponieważ bity wystarczą, aby wskazać dowolny ciąg w tym zestawie.
Algorytm kodowania: Koder sprawdza, czy sekwencja wejściowa mieści się w typowym zestawie; jeśli tak, wyprowadza indeks sekwencji wejściowej w typowym zestawie; jeśli nie, koder wyprowadza dowolną liczbę cyfr n ( H ( X ) + ε ) . Dopóki sekwencja wejściowa mieści się w typowym zestawie (z prawdopodobieństwem co najmniej 1 − ε ), koder nie popełnia żadnego błędu. Zatem prawdopodobieństwo błędu enkodera jest ograniczone powyżej przez ε .
Dowód Converse. Odwrotność jest udowodniona przez pokazanie, że każdy zestaw o rozmiarze mniejszym niż Aε
n(w sensie wykładnika) obejmowałoby zbiór prawdopodobieństwa oddzielony od 1 .
Dowód: twierdzenie o kodowaniu źródłowym dla kodów symboli
Dla 1 ≤ i ≤ n niech s i oznacza długość słowa każdego możliwego x i . Zdefiniuj , gdzie C jest wybrane tak , że q 1 + ... + q n = 1 . Następnie
gdzie druga linia wynika z nierówności Gibbsa, a piąta linia wynika z nierówności Krafta :
więc log C ≤ 0 .
Za drugą nierówność możemy ustalić
aby
a więc
oraz
i tak dzięki nierówności Krafta istnieje kod bez przedrostków, mający te długości słów. Zatem minimalne S spełnia
Rozszerzenie na niestacjonarne źródła niezależne
Bezstratne kodowanie źródła Fixed Rate dla niestacjonarnych niezależnych źródeł z czasem dyskretnym
Zdefiniuj typowy zestaw Aε
n NS:
Wtedy, dla danego δ > 0 , dla wystarczająco dużego n , Pr( Aε
n)> 1 - δ . Teraz kodujemy tylko sekwencje w typowym zestawie, a zwykłe metody w kodowaniu źródłowym pokazują, że liczność tego zestawu jest mniejsza niż . Zatem średnio, H n ( X ) + ε bity wystarczają do kodowania z prawdopodobieństwem większym niż 1 − δ , gdzie ε i δ można dowolnie zmniejszyć, zwiększając n .
Zobacz też
- Kodowanie kanałów
- Twierdzenie o kodowaniu zaszumionych kanałów
- Wykładnik błędu
- Asymptotyczna właściwość ekwipartycji (AEP)
- Teoria informacji o skończonej długości bloku