Benutzer:SnowIsWhite/Quellenkodierungssatz
Zur Navigation springen
Zur Suche springen
Der Quellenkodierungssatz ist ein zentraler Satz der Informationstheorie, der 1948 von dem amerikanischen Mathematiker Claude Elwood Shannon formuliert wurde. Er beschreibt den Zusammenhang zwischen der Entropie und der optimalen Codewortlänge einer Zufallsvariable.
Aussage
[Bearbeiten | Quelltext bearbeiten]Sei eine Zufallsvariable mit höchstens abzählbarem Wertebereich , und ein binärer Präfixcode, d.h. ordnet jedem Ereignis aus eine endliche --Folge zu. Bezeichnet die Länge dieser Folge so gilt:
,
die Entropie ist also eine untere Schranke für die durchschnittliche Codewortlänge. Desweiteren gibt es einen Präfixcode , sodass
.
Beweis
[Bearbeiten | Quelltext bearbeiten]Der Beweis ist eine Anwendung der Kraft-Ungleichung. Es gilt:
Quellen
[Bearbeiten | Quelltext bearbeiten]- Thomas M. Cover, Joy A. Thomas. Elements of information theory New York: Wiley, 1991. ISBN 0471062596
- Shannon, C.E.: A Mathematical Theory of Communication. In: Bell System Technical Journal. Band 27, 1948, S. 379–423, 623-656.