Programming lesson
Polar-Codes verstehen: Ein Tutorial zu Kodierung, Dekodierung und Polarisation
Lerne die Grundlagen von Polar-Codes: Kodierung mit Successive Cancellation Decoding, Polarisation für den BEC und Konvexität der Rate-Distortion-Funktion. Mit aktuellen Beispielen aus dem Jahr 2026.
Einführung in Polar-Codes
Polar-Codes, entwickelt von Erdal Arıkan, sind eine Klasse von Fehlerkorrekturcodes, die die Kapazität symmetrischer gedächtnisloser Kanäle erreichen. Sie basieren auf dem Phänomen der Kanalpolarisation: Durch rekursives Kombinieren und Aufteilen von Kanälen entstehen synthetische Kanäle, die entweder fast rauschfrei oder fast nutzlos sind. Dieses Tutorial erklärt die grundlegenden Konzepte anhand eines Beispiels mit N=4 und einem Binary Erasure Channel (BEC).
Kodierung mit Polar-Codes
Betrachten wir einen Polar-Code der Länge N=4. Die Kodierung erfolgt über ein rekursives Netzwerk (siehe Abbildung 1). Die Eingangsbits U1, U2, U3, U4 werden linear zu den Codewortbits X1, X2, X3, X4 transformiert. In den Teilen (a) bis (c) nehmen wir an, dass U1 und U2 auf 0 eingefroren sind, während U3 und U4 die Nachrichtenbits tragen. Die Rate des Codes ist dann 2/4 = 0.5. Für die Nachricht (U3,U4) = (1,1) ergibt sich das Codewort (X1,X2,X3,X4) = (1,1,1,1).
Successive Cancellation Decoding (SCD)
Beim SCD werden die Bits nacheinander geschätzt, wobei frühere Entscheidungen als bekannt vorausgesetzt werden. Für den empfangenen Vektor (Y1,Y2,Y3,Y4) = (1,?,?,1) – wobei '?' für eine Auslöschung steht – dekodieren wir wie folgt: Zuerst schätzen wir Û1 = 0 (da eingefroren), dann Û2 = 0. Für Û3 berechnen wir die Likelihoods unter Berücksichtigung der Auslöschungen. Das Ergebnis: Die Dekodierung gelingt, und wir erhalten (U3,U4) = (1,1).
In den Teilen (d) und (e) ändern wir die eingefrorenen Bits: U2 und U3 sind jetzt 0, U1 und U4 sind Nachrichtenbits. Für den gleichen Empfangsvektor (1,?,?,0) schlägt das SCD bei der Schätzung von U1 fehl, da die Auslöschungen eine eindeutige Entscheidung verhindern. Die optimale Maximum-Likelihood-Dekodierung hingegen vergleicht alle vier möglichen Codewörter und findet, dass nur (U1,U4) = (1,1) mit dem Empfang konsistent ist – die Dekodierung gelingt.
Polarisation für den BEC
Der BEC mit Auslöschungswahrscheinlichkeit p ist ein klassischer Kanal. Die Mediokrität eines Kanals W ist definiert als M(W) = √(p(1-p)). Sie ist genau dann 0, wenn p=0 oder p=1, also der Kanal deterministisch ist. Für die polarisierten Kanäle W+ und W− (nach einem Schritt) gilt: W+ ist ein BEC mit Auslöschung p², W− ein BEC mit 2p-p². Die Mediokritäten sind M(W+)=p√(1-p²) und M(W−)=√((2p-p²)(1-2p+p²)).
Stellen wir uns einen Ameisenpfad vor: Die Ameise startet bei W und wählt mit gleicher Wahrscheinlichkeit W+ oder W−. Nach m Schritten erreicht sie einen Kanal mit einer bestimmten Auslöschungswahrscheinlichkeit. Die Verteilung Fm dieser Wahrscheinlichkeiten für n=2ᵐ Kanäle lässt sich rekursiv berechnen. Für m=1: F1 = (p², 2p-p²) jeweils mit Wahrscheinlichkeit 1/2. Für m=2: F2 = (p⁴, 2p²-p⁴, 2p²-p⁴, 4p-4p²+p⁴) mit Wahrscheinlichkeiten 1/4, 1/4, 1/4, 1/4.
Die durchschnittliche Mediokrität Mm = E[M(W)] für Fm. Für m=1 gilt M1 = ½ M(W+) + ½ M(W−). Mit der Ungleichung M(W) ≤ √(p(1-p)) und der Rekursion zeigt man, dass Mm ≤ (√(p(1-p)))²ᵐ = ρᵐ, wobei ρ = √(p(1-p)) < 1 für p∈(0,1). Daher konvergiert Mm gegen 0. Der Anteil der Kanäle mit Mediokrität > p^(ε(1-ε)) geht gegen 0. Dies beweist die Polarisation: Fast alle Kanäle werden entweder gut (Auslöschung < ε) oder schlecht (Auslöschung > 1-ε). Der Anteil guter Kanäle g(m,ε) ist mindestens 1-p, da die erwartete Auslöschung konstant p ist. Somit gilt g(ε) = lim g(m,ε) ≥ 1-p = C, der Kapazität des BEC.
Konvexität der Rate-Distortion-Funktion
Die Rate-Distortion-Theorie ist zentral für die verlustbehaftete Kompression. Für eine gegebene Quelle X und eine Verzerrungsfunktion d(x, ẑ) sucht man die minimale Rate R(D), um eine mittlere Verzerrung ≤ D zu erreichen. Ein wichtiges Ergebnis: R(D) ist konvex im Verzerrungsparameter D.
Der Beweis nutzt die Konvexität der Kullback-Leibler-Divergenz D(p||q) in (p,q) und die Darstellung I(X;Y) = D(p(x,y)||p(x)p(y)). Für feste Quellverteilung p(x) ist I(X;Y) konvex in der bedingten Verteilung p(y|x). Dies überträgt sich auf die Rate-Distortion-Funktion: R(D) = min_{p(ẑ|x): E[d]≤D} I(X;Ẑ) ist konvex, da das Minimum konvexer Funktionen über eine konvexe Menge konvex ist.
Ausblick und Anwendungen
Polar-Codes werden in der 5G-Kommunikation eingesetzt und sind ein heißes Thema in der aktuellen Forschung. Auch im Jahr 2026 bleiben sie relevant, etwa bei der Satellitenkommunikation oder in Quantencomputern. Die Konzepte der Polarisation und der Rate-Distortion sind auch für maschinelles Lernen und KI-Anwendungen nützlich, z.B. bei der Datenkompression für neuronale Netze.
Mit diesem Tutorial hast du die Grundlagen von Polar-Codes verstanden – von der Kodierung über die Dekodierung bis zur Polarisation und Konvexität. Übe mit den Aufgaben aus dem Assignment, um dein Wissen zu vertiefen!