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)
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
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
azaz a abszolút ráta és a ráta közötti különbség.
A
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





Based on work by