Nadmiarowość (teoria informacji)

W teorii informacji redundancja mierzy ułamkową różnicę między entropią $H (X)$ zespołu $X$ , a jego maksymalną możliwą wartością $_ { X}|)}$ } . Nieformalnie jest to ilość zmarnowanej „przestrzeni” wykorzystywanej do przesyłania pewnych danych. Kompresja danych to sposób na zmniejszenie lub wyeliminowanie niepożądanej redundancji przy jednoczesnej korekcji błędów w przód to sposób na dodanie pożądanej redundancji w celu wykrywania i korygowania błędów podczas komunikacji przez zaszumiony kanał o ograniczonej przepustowości .

Definicja ilościowa

Opisując redundancję surowych danych, szybkość źródła informacji jest średnią entropią na symbol. Dla źródeł bez pamięci jest to po prostu entropia każdego symbolu, podczas gdy w najbardziej ogólnym przypadku procesu stochastycznego jest to

{\ Displaystyle R = \ lim _ {n \ do \ infty} {\ Frac {1} {n}} H (M_ { 1},M_{2},\kropki M_{n}),}

w granicy, gdy n dąży do nieskończoności, wspólnej entropii pierwszych n symboli podzielonych przez n . W teorii informacji często mówi się o „szybkości” lub „ entropii ” języka. Jest to właściwe, na przykład, gdy źródłem informacji jest angielska proza. Szybkość źródła bez pamięci to po prostu $, ponieważ z$ kolejnych komunikatów źródła bez pamięci ^{[ potrzebne źródło ]}

Bezwzględna stawka języka lub źródła jest po prostu

\ Displaystyle R = \ log | \ mathbb {M} |, \,}

logarytm liczności przestrzeni wiadomości lub alfabetu . (Ta formuła jest czasami nazywana funkcją Hartleya .) Jest to maksymalna możliwa szybkość przesyłania informacji za pomocą tego alfabetu. (Logarytm należy przyjąć do podstawy odpowiedniej dla używanej jednostki miary.) Szybkość bezwzględna jest równa rzeczywistej szybkości, jeśli źródło nie ma pamięci i ma równomierny rozkład .

Bezwzględna redundancja może być wtedy zdefiniowana jako

{\ Displaystyle D = Rr, \,}

różnica między stopą bezwzględną a stopą procentową.

Wielkość nazywana jest redundancją względną $,$ daje maksymalny możliwy współczynnik kompresji danych , wyrażony jako procent o jaki można zmniejszyć rozmiar pliku (Wyrażona jako stosunek oryginalnego rozmiaru pliku do rozmiaru skompresowanego pliku, ilość daje maksymalny współczynnik kompresji, jaki można osiągnąć). Uzupełnieniem koncepcji względnej redundancji jest wydajność , zdefiniowana jako ${\ displaystyle R: r}$ ${\ Displaystyle {\ Frac {r} {R}}},$ że ${\ Displaystyle {\ Frac {r} {R}} + {\ Frac {D} {R}} = 1 }$ . Źródło bez pamięci z równomiernym rozkładem ma zerową redundancję (a tym samym 100% wydajność) i nie może być skompresowane.

Inne pojęcia

Miarą redundancji między dwiema zmiennymi jest informacja wzajemna lub wariant znormalizowany. Miarą redundancji wśród wielu zmiennych jest całkowita korelacja .

$Displaystyle L (M ^ {n}) \, \!}$ odnosi się do różnicy między oczekiwaną długością skompresowanych danych wiadomości $n$ ${\ Displaystyle L (M ^ {n}) / n \, \!}$ (lub oczekiwaną szybkością transmisji danych ) i entropia ${\ Displaystyle nr \, \!}$ (lub współczynnik entropii ${\ displaystyle r \, \ !}$ ). (Tutaj zakładamy, że dane są ergodyczne i stacjonarne , np. źródło bez pamięci). Chociaż różnica szybkości może być dowolnie mała, $displaystyle n \, \!}$ $\, \!}$ $nr$ wzrosła, rzeczywista różnica nie może, chociaż teoretycznie może być ograniczona przez ${\ Displaystyle L (M ^ {n}) -nr \, \!}$ 1 w przypadku źródeł bez pamięci o skończonej entropii.

Redundancja w kontekstach teorii informacji może również odnosić się do informacji, które są zbędne między dwiema wzajemnymi informacjami. Na przykład, biorąc pod uwagę trzy zmienne , i $displaystyle X_ {1}}$ $displaystyle Y}$ $,$ , że wspólne wzajemne informacje mogą być mniejsze niż suma X krańcowych wzajemnych informacji: ${\ Displaystyle I (X_ {1}, X_ {2}; Y) < ja (X_ {1}; Y) + ja (X_ {2}; Y)}$ . $X_ {1}}$ tym przypadku przynajmniej część informacji o ujawnionych przez $displaystyle$ lub ${\ displaystyle X_ {2}}$ Jest taki sam. Takie sformułowanie redundancji jest komplementarne do pojęcia synergii, która występuje, gdy łączna wzajemna informacja jest większa niż suma marginesów, wskazując na obecność informacji ujawnianej tylko przez wspólne państwo, a nie jakikolwiek prostszy zbiór źródeł.

Zobacz też

Reza, Fazlollah M. (1994) [1961]. Wprowadzenie do teorii informacji . Nowy Jork: Dover [McGraw-Hill]. ISBN 0-486-68210-2 .
Schneier, Bruce (1996). Kryptografia stosowana: protokoły, algorytmy i kod źródłowy w C . Nowy Jork: John Wiley & Sons, Inc. ISBN 0-471-12845-7 .
Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). „Porównanie miar redundancji i istotności dla wyboru cech w klasyfikacji tkanek obrazów CT”. Postępy w eksploracji danych. Zastosowania i aspekty teoretyczne . Skoczek. s. 248–262. CiteSeerX 10.1.1.170.1528 .