Redundancia

A Wikipédiából, a szabad enciklopédiábó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.

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 | forrásszöveg szerkesztése]

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 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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