Redundancja (teoria informacji) - Redundancy (information theory)

W Information Theory , redundancji mierzy różnicę ułamkowe pomiędzy entropii H (X) się z zespołu X i jego maksymalnej możliwej wartości . Nieformalnie jest to ilość zmarnowanej „przestrzeni” wykorzystywanej do przesyłania określonych danych. Kompresja danych to sposób na zmniejszenie lub wyeliminowanie niepożądanej nadmiarowości, podczas gdy sumy kontrolne są sposobem na dodanie pożądanej nadmiarowości w celu wykrywania błędów podczas komunikacji przez zaszumiony kanał o ograniczonej przepustowości . ${\ Displaystyle \ log (| {\ mathcal {A}} _ {X} |)}$

Definicja ilościowa

W opisie redundancji surowych danych szybkość źródła informacji jest średnią entropią na symbol. Dla źródeł bez pamięci jest to jedynie entropia każdego symbolu, podczas gdy w najogólniejszym 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 idzie do nieskończoności, łącznej entropii pierwszych n symboli podzielonej 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 proza ​​angielska. Wskaźnik źródła bez pamięci jest po prostu , ponieważ z definicji nie ma współzależności kolejnych komunikatów źródła bez pamięci. ${\ Displaystyle H (M)}$

Bezwzględny wskaźnik języka lub źródła jest po prostu

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

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

Absolutnym redundancji może być zdefiniowany jako

${\displaystyle D=Rr,\,}$

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

Wielkość ta nazywana jest nadmiarowością względną i określa maksymalny możliwy współczynnik kompresji danych , wyrażony jako procent, o który można zmniejszyć rozmiar pliku. (Wyrażone jako stosunek pierwotnego rozmiaru pliku do rozmiaru skompresowanego pliku ilość daje maksymalny współczynnik kompresji, które można osiągnąć.) Komplementarne do pojęcia względne redundancji wydajność określona jako tak, że . Źródło bez pamięci o równomiernym rozkładzie ma zerową nadmiarowość (a tym samym 100% wydajność) i nie może być skompresowane. ${\ Displaystyle {\ Frac {D} {R}}}$${\displaystyle R:r}$${\displaystyle {\frac {r}{R}},}$${\ Displaystyle {\ Frac {R} {R}} + {\ Frac {D} {R}} = 1}$

Inne pojęcia

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

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

Redundancja w kontekstach informacyjno-teoretycznych może również odnosić się do informacji, które są redundantne między dwiema wzajemnymi informacjami. Na przykład przy danych trzech zmiennych , , i , wiadomo, że łączna informacja wzajemna może być mniejsza niż suma marginalnych informacji wzajemnych: . W takim przypadku przynajmniej część informacji o ujawnionych przez lub jest taka sama. To sformułowanie redundancji jest komplementarne do pojęcia synergii, która występuje wtedy, gdy wspólna wzajemna informacja jest większa niż suma marginalnych, wskazujących na obecność informacji ujawnianych tylko przez wspólne państwo, a nie na prostszy zbiór źródeł. ${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\ Displaystyle Y}$${\displaystyle I(X_{1},X_{2};Y)<I(X_{1};Y)+I(X_{2};Y)}$${\ Displaystyle Y}$${\displaystyle X_{1}}$${\displaystyle X_{2}}$

Zobacz też

• Minimalne kodowanie nadmiarowe
  • Kodowanie Huffmana
• Kompresja danych
• Funkcja Hartley
• Negentropia
• Twierdzenie o kodowaniu źródłowym
• Nadkompletność

Bibliografia

• Reza, Fazlollah M. (1994) [1961]. Wprowadzenie do teorii informacji . Nowy Jork: Dover [McGraw-Hill]. Numer ISBN 0-486-68210-2.
• Schneiera, Bruce'a (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 środków redundancji i trafności doboru 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 .