Redundance (informační teorie) - Redundancy (information theory)

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červen 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v Informační teorie, nadbytek měří zlomkový rozdíl mezi entropie H (X) souboru Xa jeho maximální možná hodnota ${ displaystyle log (| { mathcal {A}} _ {X} |)}$.^[1][2] Neformálně jde o množství promarněného „prostoru“ použitého k přenosu určitých dat. Komprese dat je způsob, jak snížit nebo eliminovat nechtěnou nadbytečnost kontrolní součty jsou způsob přidání požadované redundance pro účely detekce chyb při hlasité komunikaci kanál omezené kapacita.

Kvantitativní definice

Při popisu redundance nezpracovaných dat hodnotit zdroje informací je průměr entropie na symbol. Pro zdroje bez paměti je to pouze entropie každého symbolu, zatímco v nejobecnějším případě a stochastický proces, to je

${ displaystyle r = lim _ {n to infty} { frac {1} {n}} H (M_ {1}, M_ {2}, dots M_ {n}),}$

v limitu, as n jde do nekonečna, z společná entropie první n symboly děleno n. V informační teorii je běžné hovořit o „míře“ nebo „entropie „jazyka. To je vhodné, například když je zdrojem informací anglická próza. Rychlost zdroje bez paměti je jednoduše ${ displaystyle H (M)}$, protože podle definice neexistuje vzájemná závislost následných zpráv zdroje bez paměti.^{[Citace je zapotřebí ]}

The absolutní sazba jazyka nebo zdroje je jednoduše

${ displaystyle R = log | mathbb {M} |, ,}$

the logaritmus z mohutnost prostoru pro zprávy nebo abecedy. (Tento vzorec se někdy nazývá Hartleyova funkce.) Toto je maximální možná rychlost informací, které lze s touto abecedou přenášet. (Logaritmus by měl být přenesen na základnu odpovídající použitým měrným jednotkám.) Absolutní rychlost se rovná skutečné rychlosti, pokud je zdroj bez paměti a má rovnoměrné rozdělení.

The absolutní redundance pak lze definovat jako

${ displaystyle D = R-r, ,}$

rozdíl mezi absolutní sazbou a sazbou.

Množství ${ displaystyle { frac {D} {R}}}$ se nazývá relativní nadbytečnost a dává maximum možné kompresní poměr dat, vyjádřeno jako procento, o které lze zmenšit velikost souboru. (Když je vyjádřeno jako poměr původní velikosti souboru k velikosti komprimovaného souboru, množství ${ displaystyle R: r}$ udává maximální kompresní poměr, kterého lze dosáhnout.) Doplněk k konceptu relativní redundance je účinnost, definováno jako ${ displaystyle { frac {r} {R}},}$ aby ${ displaystyle { frac {r} {R}} + { frac {D} {R}} = 1}$. Zdroj bez paměti s rovnoměrnou distribucí má nulovou redundanci (a tedy 100% účinnost) a nelze jej komprimovat.

Jiné pojmy

Míra nadbytek mezi dvěma proměnnými je vzájemné informace nebo normalizovaná varianta. Míra redundance mezi mnoha proměnnými je dána vztahem celková korelace.

Redundance komprimovaných dat se týká rozdílu mezi očekávaný délka komprimovaných dat ${ displaystyle n}$ zprávy ${ displaystyle L (M ^ {n}) , !}$ (nebo očekávaná rychlost přenosu dat ${ displaystyle L (M ^ {n}) / n , !}$) a entropie ${ displaystyle nr , !}$ (nebo míra entropie ${ displaystyle r , !}$). (Zde předpokládáme, že data jsou ergodický a stacionární např. bez paměti.) Přestože je rychlostní rozdíl ${ displaystyle L (M ^ {n}) / n-r , !}$ může být libovolně malý jako ${ displaystyle n , !}$ skutečný rozdíl ${ displaystyle L (M ^ {n}) - nr , !}$, nemůže, i když v případě zdrojů bez paměti s konečnou entropií může být teoreticky horní mez 1.

Viz také

• Minimální kódování redundance
  • Huffmanovo kódování
• Komprese dat
• Hartleyova funkce
• Negentropy
• Věta o zdrojovém kódování
• Nadměrnost

Reference

• Reza, Fazlollah M. (1994) [1961]. Úvod do teorie informace. New York: Dover [McGraw-Hill]. ISBN  0-486-68210-2.
• Schneier, Bruce (1996). Aplikovaná kryptografie: protokoly, algoritmy a zdrojový kód v jazyce C.. New York: John Wiley & Sons, Inc. ISBN  0-471-12845-7.
• Auffarth, B; Lopez-Sanchez, M .; Cerquides, J. (2010). "Srovnání míry redundance a relevance pro výběr prvků v tkáňové klasifikaci CT snímků". Pokroky v dolování dat. Aplikace a teoretické aspekty. Springer. 248–262. CiteSeerX  10.1.1.170.1528.