Benutzer:SnowIsWhite/Quellenkodierungssatz

aus Wikipedia, der freien Enzyklopädie
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.

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

.

Der Beweis ist eine Anwendung der Kraft-Ungleichung. Es gilt:

  • 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.