Twierdzenie Shannona o kodowaniu źródłowym - Shannon's source coding theorem

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 Σ*
1
i Σ*
2
oznaczają 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 Σ*
1
do Σ*
2
gdzie 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ε
    n
    jest 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 ≤ in 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ż

Bibliografia