Grundlagen der Informationstheorie: Kanalkapazität, AEP und Quellencodierung

Kanalkapazität und Informationstheorie

Die Fähigkeit eines Kommunikationskanals (Kanalkapazität) ist die maximale Menge an Informationen, die dieser Kanal zuverlässig übertragen kann, d. h. mit einer beliebig kleinen Fehlerwahrscheinlichkeit. Sie wird in der Regel in Bit pro Sekunde (bps) ausgedrückt.

Definitionen der Kanalkapazität

• Es gibt zwei äquivalente Konzepte der Kanalkapazität: eines für kontinuierliche Zeitkanäle und eines für diskrete Zeitkanäle.

Diskreter Kanal ohne Speicher

Ein diskreter Kanal ohne Speicher wird definiert durch:

• Das Eingabealphabet $X = \{x_1, x_2, \dots, x_n\}$, die Menge der Symbole, die durch den Kanal übertragen werden können.
• Das Ausgabealphabet $Y = \{y_1, y_2, \dots, y_m\}$, die Menge der Symbole, die am Kanalausgang empfangen werden können.

Hierbei werden die Eingangs-, Ausgangs- und die bedingte Entropie (Input- und Output-Entropie) definiert.

Kontinuierliche Kanäle und das Shannon-Hartley-Theorem

Die Kanalkapazität für kontinuierliche Kanäle ist komplexer und erfordert den Einsatz des Abtasttheorems und anderer statistischer Konzepte.

Claude Shannon zeigte 1949, dass die theoretische maximale Kapazität eines bandbegrenzten AWGN-Kanals (Additive White Gaussian Noise) durch die Shannon-Hartley-Gleichung gegeben ist:

$C = B \log_2(1 + SNR)$

Diese Gleichung zeigt, dass die Kanalkapazität durch die Bandbreite $B$ und das Signal-Rausch-Verhältnis ($SNR$) begrenzt ist.

Die maximale spektrale Effizienz hängt von der Qualität des Kanals (Geräuschpegel) ab.

Die Asymptotische Gleichverteilungseigenschaft (AEP)

Die AEP ist eine zentrale Eigenschaft in der Informationstheorie. Diese Eigenschaft besagt, dass die Wahrscheinlichkeit, eine Sequenz $x_1, x_2, x_3, \dots, x_n$ aus einer Quelle $f$ zu beobachten, nahe bei $2^{-nH}$ liegt.

Während uns das Gesetz der großen Zahlen sagt, dass für unabhängige und identisch verteilte (i.i.d.) Zufallsvariablen gilt:

Wenn $n$ gegen unendlich strebt, ermöglicht uns die AEP, die erzeugten Sequenzen zu trennen. Es gibt zwei Arten: typische und atypische Sequenzen.

Wenn $x_1, x_2, \dots, x_n$ unabhängig und identisch verteilt sind, gilt mit hoher Wahrscheinlichkeit, dass die Wahrscheinlichkeit der Sequenz $p(x_1, x_2, \dots, x_n)$ nahe $2^{-nH}$ liegt. Man kann behaupten, dass die Wahrscheinlichkeit, dass die Sequenz zur Menge der typischen Sequenzen gehört, nahezu 1 ist:

$P((x_1, x_2, \dots, x_n) \mid p(x_1, x_2, \dots, x_n) \approx 2^{-nH}) \approx 1$

Grundlagen der Quellencodierung

Ein Code kombiniert Symbole aus dem Quellalphabet $A_X = \{x_1, x_2, \dots, x_n\}$ zu Folgen eines D-ären Code-Alphabets $A_D$. Ohne Verlust der Allgemeinheit kann angenommen werden, dass $A_D = \{0, 1, \dots, D-1\}$. $A_X$ wird als Quellalphabet und $A_D$ als Code-Alphabet bezeichnet.

Blockcodes

Ein Blockcode ordnet jedem Symbol in $A_X$ eine feste Folge von Codezeichen aus dem Alphabet $A_D$ zu. Jede dieser festen Sequenzen wird als Codewort bezeichnet.

$X_i \xrightarrow{c} c(x_i)$

wobei $c$ der Blockcode ist.

Die Länge eines Codeworts $c(x_i)$ ist die Anzahl der Zeichen aus dem Alphabet $A_D$, die es umfasst. Die durchschnittliche Länge eines Codes wird definiert als:

Reguläre Codes: Ein Code-Block wird als regulär bezeichnet, wenn...

Eindeutig Dekodierbare Codes

Ein Code $c$ heißt eindeutig dekodierbar (univocamnte dekodierbar), wenn jede Folge von Codewörtern nur auf eine Weise in Quellsymbole zerlegt werden kann.

Es gibt zwei Hauptarten von eindeutig dekodierbaren Codes:

1. Codes ohne Präfix-Eigenschaft (allgemein eindeutig dekodierbar)
2. Präfix-Codes oder Instant-Codes

Ein Code heißt sofort dekodierbar (Instant-Code), wenn es möglich ist, eine Sequenz zu entschlüsseln, ohne den Inhalt der nachfolgenden Symbole abwarten zu müssen (d. h., kein Codewort ist Präfix eines anderen Codeworts).

Alle Präfix-Codes sind eindeutig dekodierbar.

Datenkodierung und Codecs

Dies beschreibt die Art der Informationsverarbeitung (Codec):

1. Leitungscode (Line Code): Wird verwendet, um Daten zusammen mit dem Taktsignal auf derselben Leitung zu senden.

2. Sprach-Codec: Dient zur Komprimierung der Kodierungsgeschwindigkeit (z. B. von 64 kbit/s) für Satelliten- und Mobilfunktelefonie.

   • DPCM-Kodierung (Differential Pulse Code Modulation) gilt auch für Videosignale.
   • LPC (Lineare Prädiktive Kodierung) ist effektiver als DPCM hinsichtlich der Reduzierung von Kosten, Verzögerung und Verarbeitungsgeschwindigkeit.
   • DPCM und LPC werden in der Satelliten- und Mobiltelefonie eingesetzt.