Kanalcodierung und Fehlerwahrscheinlichkeit: Tutorial zu EE276 Homework #5

Einführung in die Kanalcodierung

In der modernen Nachrichtentechnik ist die zuverlässige Übertragung von Informationen über gestörte Kanäle eine zentrale Herausforderung. Ob beim Streamen eines Viral-Videos auf TikTok, bei der Datenübertragung zwischen KI-Servern oder beim Hochladen von Hausaufgaben auf Moodle – stets müssen Fehler korrigiert werden. Dieses Tutorial behandelt die wichtigsten Konzepte aus der Übung EE276 Homework #5, darunter die Minimierung der Fehlerwahrscheinlichkeit, Gauß-Kanäle und Joint Typicality. Es richtet sich an Studierende der Informationstheorie und alle, die ihr Verständnis vertiefen möchten.

1. Minimierung der Kanalfehlerwahrscheinlichkeit

Betrachten wir ein Kommunikationssystem mit einer Nachricht J, die gleichverteilt aus {1,2,…,M} gewählt wird. Ein Encoder weist jeder Nachricht einen Codewort Xn(j) aus einem Codebuch cn zu. Dieses wird über einen gedächtnislosen Kanal mit Übergangswahrscheinlichkeit PY|X gesendet. Der Empfänger erhält Yn und schätzt die Nachricht durch einen Decoder Ĵ(Yn), der auch einen Fehler melden kann. Die Fehlerwahrscheinlichkeit ist Pe = P(Ĵ ≠ J).

Für ein festes Codebuch wird Pe minimiert durch die Maximum-a-Posteriori (MAP)-Decodierung:

Ĵ(yn) = argmax1≤j≤M P(J = j | Yn = yn)

Dies ist intuitiv: Man wählt die Nachricht, die nach Beobachtung des Empfangs am wahrscheinlichsten ist. Ein Beispiel aus dem Schulalltag: Ein Lehrer gibt eine Multiple-Choice-Klausur (M=4). Ein Schüler errät die Antworten. Der MAP-Decoder entspricht dem Schüler, der seine Antworten basierend auf dem Gehörten (Empfang) und seiner Vorkenntnis (A-priori-Wahrscheinlichkeit) wählt.

Beweisskizze

Für ein gegebenes yn ist die bedingte Wahrscheinlichkeit eines Fehlers P(Ĵ ≠ j | Yn = yn) = 1 - P(J = j | Yn = yn) für eine Entscheidung j. Um diese zu minimieren, wählt man das j mit maximaler A-posteriori-Wahrscheinlichkeit. Da dies für jedes yn gilt, wird die gesamte Fehlerwahrscheinlichkeit minimiert.

2. Der Zwei-Blick-Gauß-Kanal

Stellen Sie sich vor, Sie schauen sich ein YouTube-Video an – einmal auf dem Handy und einmal auf dem Tablet. Beide Geräte empfangen das gleiche Signal, aber mit unterschiedlichem Rauschen. Genau das modelliert der Zwei-Blick-Gauß-Kanal:

Y1 = X + Z1, Y2 = X + Z2

mit (Z1, Z2) ∼ N(0, K) und Kovarianzmatrix K = σ2 [[1, ρ], [ρ, 1]]. Die Sendeleistung ist auf P beschränkt. Die Kanalkapazität C hängt von der Korrelation ρ ab:

ρ = 1: Die beiden Rauschkomponenten sind identisch. Dann haben wir effektiv nur einen Kanal, und die Kapazität ist C = ½ log(1 + P/σ2).
ρ = 0: Unkorreliertes Rauschen. Die Kapazität verdoppelt sich: C = log(1 + P/σ2).
ρ = -1: Die Rauschkomponenten sind entgegengesetzt gleich. Durch Mittelung der beiden Ausgänge kann man das Rauschen eliminieren, was zu einer unendlichen Kapazität führt (theoretisch).

Dieses Prinzip findet sich in der MIMO-Technik (Multiple Input Multiple Output) wieder, die in 5G-Netzen und WLAN-Standards wie WiFi 6 verwendet wird. Durch mehrere Antennen werden mehrere „Blicke“ auf das Signal ermöglicht, was die Datenrate erhöht.

3. Ausgangsleistungsbeschränkung

Ein weiteres Szenario ist ein AWGN-Kanal mit einer Beschränkung der erwarteten Ausgangsleistung: E[Y2] ≤ P. Hier ist Y = X + Z mit Z ∼ N(0, σ2) und unabhängig von X. Die Kapazität ergibt sich aus der Maximierung der gegenseitigen Information I(X;Y) unter der Nebenbedingung E[Y2] ≤ P. Da E[Y2] = E[X2] + σ2, ist die Bedingung äquivalent zu E[X2] ≤ P - σ2. Für P > σ2 ist die Kapazität C = ½ log(1 + (P - σ2)/σ2) = ½ log(P/σ2). Falls P ≤ σ2, ist keine positive Leistung für das Signal übrig, und C = 0.

Dieses Modell ist relevant, wenn ein Verstärker eine maximale Ausgangsleistung nicht überschreiten darf – etwa bei der Bluetooth-Kommunikation in Kopfhörern, um die SAR-Grenzwerte einzuhalten.

4. Gegenseitige Information bei Gaußschen Zufallsvariablen

Angenommen, (X, Y, Z) sind gemeinsam gaußsch und bilden eine Markov-Kette X → Y → Z. Die Korrelationskoeffizienten seien ρXY = ρ1 und ρYZ = ρ2. Die gegenseitige Information I(X;Z) lässt sich dann berechnen zu:

I(X;Z) = -½ log(1 - ρ12 ρ22)

Dies folgt aus der Tatsache, dass ρXZ = ρ1 ρ2 aufgrund der Markov-Kette. Ein Beispiel aus der KI-Forschung: In einem neuronalen Netz repräsentiert X die Eingabe, Y die versteckte Schicht und Z die Ausgabe. Die gegenseitige Information zwischen Eingabe und Ausgabe wird durch die Korrelationen bestimmt.

5. Flaschenhals-Kanal

Ein Flaschenhals-Kanal liegt vor, wenn das Signal X über eine Zwischenstufe V mit k möglichen Werten an den Empfänger gelangt: X → V → Y. Die Übergangswahrscheinlichkeiten sind beliebig. Es lässt sich zeigen, dass die Kanalkapazität C ≤ log k ist. Dies ist eine Anwendung des Datenverarbeitungsungleichung: Die Kapazität kann nicht größer sein als die Kapazität des Zwischenkanals.

Stellen Sie sich vor, Sie streamen ein Spiel in 4K (X), aber Ihr Internetanschluss (V) erlaubt nur 1080p (k=2). Dann ist die maximal mögliche Datenrate begrenzt. In der Praxis nutzen adaptive Streaming-Dienste wie Netflix diese Erkenntnis, um die Videoqualität an die verfügbare Bandbreite anzupassen.

6. Joint Typicality

Das Konzept der Joint Typicality ist fundamental für die Beweise in der Informationstheorie. Gegeben seien i.i.d. Zufallsvariablen (Xi, Yi, Zi) ∼ p(x,y,z). Eine Sequenz (xn, yn, zn) heißt jointly typical, wenn die empirischen Entropien nahe an den theoretischen liegen. Wenn (xn, yn, zn) aus unabhängigen Marginalverteilungen p(xn)p(yn)p(zn) gezogen wird, dann ist die Wahrscheinlichkeit, dass sie jointly typical sind, ungefähr:

P(jointly typical) ≈ 2-n(I(X;Y)+I(X;Z)+I(Y;Z)-I(X;Y;Z))

wobei I(X;Y;Z) die multivariate gegenseitige Information ist. Dieses Ergebnis wird in der Netzwerkcodierung und bei der Analyse von verteilten KI-Systemen verwendet, um die Effizienz der Datenkompression zu bestimmen.

Fazit

Die Aufgaben aus EE276 Homework #5 decken zentrale Konzepte der Informationstheorie ab. Von der MAP-Decodierung über Gauß-Kanäle bis zur Joint Typicality – jedes Thema hat praktische Relevanz in der heutigen Kommunikationstechnik. Ob beim 5G-Ausbau, bei KI-gestützten Anwendungen oder im Schulalltag (z.B. bei der Datenübertragung in Lernplattformen): Die Prinzipien der Kanalcodierung helfen, Fehler zu minimieren und Kapazitäten optimal zu nutzen. Vertiefen Sie Ihr Wissen durch eigene Berechnungen und Simulationen – und denken Sie daran: Der MAP-Decoder ist Ihr bester Freund, wenn es um minimale Fehlerwahrscheinlichkeit geht!