Redundancia

A Wikipédiából, a szabad lexikonból.

Redundancia az információelméletben az információ vagy üzenet átvitelnél használt bitek számának és az aktuális információ vagy üzenet bitjei számának a különbsége. Az adattömörítés egy lehetséges mód a nem kívánt redundancia csökkentésére, a különféle ellenőrző összegek pedig hibajavítás céljából növelik a redundanciát, ha az átvitel egy zajos csatornán folyik, ahol a zaj csökkenti az átviteli kapacitást.

[szerkesztés] Mennyiségi meghatározása

Az információelmélet szerint egy információ forrás rátája (a legáltalánosabb esetben)

r=\mathbb E H(M_t|M_{t-1},M_{t-2},M_{t-3}, \cdots),

ami az üzenet várt, vagy átlagos, feltételes üzenetenkénti entrópiáját ( időegységre eső) adja az előző üzenetek vonatkozásában. Ismert az információelméletből, hogy egy nyelvnek is létezik "rátája" vagy "entrópiája". Egy emlékezet nélküli forrás rátája egyszerűen H(M), ami a definíció alapján azt jelenti, hogy nincsen kapcsolat az egymást követő üzenetek között egy emlékezet nélküli forrás esetén.

Egy nyelv vagy forrás abszolút rátája egyszerűen

R = \log |M| ,\,

az üzenet tér (pl. ábécé) számosságának logaritmusa. Ez az üzenet maximális valószínűségi rátája, ha az adott ábécét használva küldjük el. Az abszolút ráta akkor, és csakis akkor egyezik meg a rátával, ha a forrás emlékezet nélküli és egyenletes eloszlású.

A redundancia tehát meghatározható, mint

D = R - r ,\,

azaz a abszolút ráta és a ráta közötti különbség.

A \frac D R menyiséget tekinthetjük, mint relatív redundanciát, és megadja a lehetséges legnagyobb adattömörítési arányt, ha százalékosan fejezik ki, ami azt mutatja meg, hogy a egy file hossza mennyire csökkenthető. (Ha úgy fejezzük ki, mint a tömörített file hossz és az eredeti file hossz aránya, akkor az R:r mennyiség az elérhető legnagyobb tömörítési arányt adja meg.) Egy emlékezet nélküli, egyenletes eloszlású forrás redundanciája nulla, és nem tömöríthető.

Meg kell jegyezni, hogy a Kolomogorov komplexitás alapján meghatározott maximális tömörítési valószínűség eltér az előzőek szerint számított maximális tömörítési valószínűségtől, mivel itt azt feltételezztük, hogy az adatok a priori valószínűségi eloszlása ismert, és előre kódoltak az adatok.

[szerkesztés] Lásd részletesebben

  • B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc. 1996. ISBN 0471117090