Redundancia

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés]

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 , 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 (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

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

A 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 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é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[szerkesztés]

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 átviendő 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[szerkesztés]

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