Zeitvariante Kanäle und typische Sequenzen: Tutorial zur Kanalcodierung

Einführung in zeitvariante Kanäle und typische Sequenzen

In der digitalen Kommunikation stehen wir oft vor der Herausforderung, dass sich Kanäle im Laufe der Zeit verändern – sei es durch Mobilfunkbewegungen, WLAN-Interferenzen oder adaptive Übertragungssysteme. In diesem Tutorial beleuchten wir die Theorie zeitvarianter diskreter gedächtnisloser Kanäle (DMC) und die Berechnung typischer Sequenzen, wie sie in der Kanalcodierung verwendet werden. Die Konzepte sind nicht nur für traditionelle Nachrichtentechnik relevant, sondern auch für moderne KI-Anwendungen, bei denen Daten über verrauschte Verbindungen übertragen werden – etwa beim Training verteilter neuronaler Netze oder bei Echtzeit-KI-Assistenten.

Zeitvariante gedächtnislose Kanäle

Ein zeitvarianter DMC wird durch eine Familie von Übergangswahrscheinlichkeiten p_i(y_i|x_i) beschrieben, die sich mit jedem Symbol ändern können. Im gegebenen Szenario ist jeder Unterkanal ein BSC (Binary Symmetric Channel) mit Kreuzungswahrscheinlichkeit δ_i. Die gemeinsame Verteilung über einen Block der Länge n ist:

p(y|x) = ∏_{i=1}^n p_i(y_i|x_i)

Die entscheidende Größe ist die wechselseitige Information I(X;Y) zwischen Eingabe X und Ausgabe Y. Für einen zeitvarianten Kanal gilt:

Maximierung von I(X;Y) über die Eingabeverteilung PX ergibt die Kanalkapazität. Der Beweis nutzt eine Kette von Ungleichungen ähnlich dem Umkehrbeweis der Kanalcodierung.

Konkret zeigt man, dass für jede Verteilung PX gilt: I(X;Y) ≤ ∑_{i=1}^n C_i, wobei C_i die Kapazität des i-ten BSC ist. Die Gleichheit wird erreicht, wenn die Eingaben unabhängig und gleichverteilt sind – ein Ergebnis, das auch für adaptive Systeme in 5G-Netzen relevant ist.

Typische Sequenzen und der BSC

Betrachten wir einen BSC mit Kreuzungswahrscheinlichkeit 0,1. Die Eingabe sei gleichverteilt (Bernoulli(1/2)). Die gemeinsame Verteilung lautet:

p(x,y): (0,0)=0,45; (0,1)=0,05; (1,0)=0,05; (1,1)=0,45

Daraus berechnen wir:

H(X) = H(Y) = 1 Bit
H(X,Y) = 0,45*log(1/0,45) + 0,05*log(1/0,05) + 0,05*log(1/0,05) + 0,45*log(1/0,45) ≈ 1,469 Bits
I(X;Y) = H(X) + H(Y) - H(X,Y) ≈ 0,531 Bits

Für n=25 und ε=0,2 besteht die typische Menge aus Sequenzen, deren empirische Entropie nahe der wahren Entropie liegt. Die Tabelle zeigt Wahrscheinlichkeiten und Anzahlen von Sequenzen mit k Einsen. Die Größe der typischen Menge ergibt sich aus der Summe der Anzahlen für k von 0 bis 12: etwa 16.777.216 Sequenzen (also 2^24).

Gemeinsam typische Sequenzen und Fehlerwahrscheinlichkeit

Ein Paar (x^n, y^n) ist gemeinsam typisch, wenn x^n typisch ist und die Differenz z^n = y^n - x^n (mod 2) typisch für die Rauschverteilung ist. Für eine feste empfangene Sequenz y^n = 0^n ist die Anzahl der gemeinsam typischen x^n gleich der Anzahl der typischen z^n. Die Wahrscheinlichkeit, dass ein zufällig gewähltes Codewort gemeinsam typisch mit y^n ist, beträgt etwa 2^{-n I(X;Y)}.

Bei einem Code mit 512 Codewörtern (n=25) ist die Wahrscheinlichkeit, dass mindestens ein anderes Codewort gemeinsam typisch ist, durch die Union Bound beschränkt: 511 * 2^{-n I(X;Y)} ≈ 511 * 2^{-13,275} ≈ 0,025. Die genaue Fehlerwahrscheinlichkeit liegt nahe an diesem Wert, da die Ereignisse nahezu unabhängig sind.

BSC mit Rückkopplung

Ein interessanter Spezialfall ist der BSC mit Rückkopplung, bei dem die gesendete Sequenz durch die vorherigen Empfänge bestimmt wird: X_1 = Bern(1/2), X_2 = Y_1, X_3 = Y_2, … Dann gilt lim_{n→∞} I(X^n;Y^n)/n = 0, da die Ausgabe deterministisch von der Eingabe abhängt – die Kapazität ist 0. Dies zeigt, dass Rückkopplung die Kapazität eines gedächtnislosen Kanals nicht erhöht (im Gegensatz zu Kanälen mit Gedächtnis).

Fano-Ungleichung und Fehlerschranken

Die Fano-Ungleichung liefert eine untere Schranke für die Fehlerwahrscheinlichkeit in Abhängigkeit von der Entropie. Für eine diskrete Zufallsvariable X mit m Ausprägungen und dem besten Raterater X̂ = 1 gilt Pe = 1 - p_1. Die Maximierung von H(X) unter der Nebenbedingung 1 - p_1 = Pe ergibt:

H(X) ≤ H(Pe) + Pe log(m-1)

Diese Ungleichung ist fundamental für die Kanalcodierung: Sie zeigt, dass bei gegebener Entropie die Fehlerwahrscheinlichkeit nicht unter einen bestimmten Wert fallen kann.

Fazit und Ausblick

Die Konzepte zeitvarianter Kanäle, typischer Sequenzen und der Fano-Ungleichung sind essenziell für das Verständnis moderner Kommunikationssysteme. Sie finden Anwendung in der Fehlerkorrektur bei Satellitenkommunikation, in KI-gestützten Übertragungsprotokollen und in der Quantenkommunikation. Mit den hier vorgestellten Methoden können Sie die Leistungsfähigkeit von Codierverfahren analysieren und optimieren.