Redundancia

Redundancia az információelméletben az információ- vagy üzenetátvitelre használt csatornán maximálisan egyszerre átvihető 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.

A redundancia (lat.) nyelvtudományi fogalma; a közlésben az egyértelmű megértéshez elegendő minimumon felüli, ezért fölösleges többlet. Terjengős kifejezések alkalmazása egyszerűbb szavak helyett, pl. javasol - javaslatot tesz. Előfordul, hogy van jelentésbeli vagy stilisztikai funkciója, pl. az ellentét kifejezője egyszersmind archaizáló.

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 (például á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}}$ mennyisé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 egy file hossza mennyire csökkenthető. (Ha úgy fejezzük ki, mint a tömörített filehossz és az eredeti filehossz 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 Kolmogorov-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ételeztük, hogy az adatok a priori valószínűségi eloszlása ismert, és előre kódoltak az adatok.

Példák

Tételezzük fel, hogy magyar nyelvű szöveget szeretnénk egy 8 bites bináris csatornán továbbítani, azaz a csatorna bitjeinek száma 8. A magyar ábécé 40 vagy 44 betűt tartalmaz. Ha még a szavak elválasztására szolgáló szóköz karaktert is figyelembe vesszük, akkor tehát 41 vagy 45 karakterről van szó. Ha még hozzávesszük a 10 számot, és az írásjeleket, akkor sincsen több, mint 63 át vivendő karakterre szükségünk. A 63 karaktert 6 biten lehet kódolni, így az üzenet bitjeinek száma legyen 6. Ebben az esetben a redundancia 2, azaz minden üzenet esetében 2 felesleges vagy kihasználatlan bitet kell átvinnünk a kommunikációs csatornán.

Ez a 2 bites redundancia esetünkben most veszteségként jelentkezik.

Külső hivatkozás

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