Hartung-Gorre Verlag
Inh.: Dr.
Renate Gorre D-78465
Konstanz Fon:
+49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de
|
S
|
Series in Signal and Information Processing, Vol. 29
edited by Hans-Andrea Loeliger
Christian
Schürch
On Successive
Cancellation Decoding
of Polar Codes and
Related Codes.
1. Auflage/1st edition 2017. XVIII, 160 Seiten/pages,
€ 64,00. ISBN
978-3-86628-580-4
Polar codes with a successive cancellation decoder were historically the
first practical coding scheme that was able to reliably transmit digital data
at the highest possible data rate. This thesis gives new insights on successive
cancellation decoding of polar codes and related codes. It consists of three
parts.
The first part presents a partial order for the synthesized channels of
a polar code that is independent of the transmitting channel. This partial
order is combined with a partial order from the literature. A minimal
representation of this combined partial order is derived that enables us to
practically use the combined partial order for simplifying the construction of
polar codes.
The second part investigates successive cancellation decoding of codes based
on the Discrete Fourier Transform over finite fields. Successive cancellation
decoding in the natural symbol order is impractical for reasonable blocklength. However, based on the Cooley-Tukey Fast
Fourier Transform, we found that successive cancellation decoding in the digitreversed symbol order has significantly lower
complexity but comes along with slower polarization. However, for most codes,
even this reduced complexity is still impractical. We found that for the
reasonably high blocklength of 256, successive
cancellation decoding in the digit-reversed order is feasible. Simulations
showed that the synthesized channels polarize. Moreover, for that blocklength, we found a way to choose the frozen symbols of
the Discrete Fourier Transform code such that its performance under successive
cancellation list decoding is very well. However, the decoding complexity is
still much higher than for other coding schemes with comparable performance.
The third part introduces the fat-tree decoder, which is applicable to polar
codes and related codes and which is a generalization to the successive
cancellation decoder. The fat-tree decoder does message passing on a cycle-free
factor graph for the polar code and thus computes exact posterior
probabilities. The fat-tree decoder is able to decode the information symbols
of a polar code in any desired order. Moreover, it has the ability to take into
account any frozen symbols even from the future symbols. However, to keep the
complexity manageable, only a limited number of frozen symbols can be
considered and the symbol decoding order is not completely arbitrary. We
present two specific fat-tree decoder strategies that perform substantially
better than the successive cancellation decoder and have manageable complexity.
Moreover, these strategies approach block maximum a posteriori performance for
polar codes of many parameters. The high flexibility of the fat-tree decoder suggests
that even better tradeoffs between performance and decoding complexity exist.
Keywords: successive cancellation; polar codes; factor graphs; partial order;
code construction; Discrete Fourier Transform; Fast Fourier Transform;
cycle-free; maximum likelihood decoding; maximum a posteriori decoding
Kurzfassung in Deutsch (das Buch ist in Englisch geschrieben)
Polar Codes mit einem Successive Cancellation Dekodierer waren historischgesehen
die erste praktikable Kodierungsmethode, die digitale Daten zuverlässig mit der
höchstmöglichen Rate übertragen konnte. Diese Dissertation gibt neue Einblicke
in das Successive Cancellation Dekodieren von Polar und
verwandten Codes. Sie besteht aus drei Teilen.
Der erste Teil präsentiert
eine Halbordnung für die synthetischen Kanäle eines Polar Codes, die unabhängig
vom Übertragungskanal ist. Diese Halbordnung wird kombiniert mit einer anderen
Halbordnung aus der Literatur. Eine minimale Darstellung dieser kombinierten
Halbordnung wird hergeleitet, welche es uns ermöglicht die kombinierte
Halbordnung praktisch zu nutzen um die Konstruktion eines Polar Codes zu vereinfachen.
Der zweite Teil untersucht
das Successive Cancellation Dekodieren von Codes basierend auf der Diskreten
Fourier-Transformation über endliche Körper. Das Successive
Cancellation Dekodieren in der natürlichen Symbol
Reihenfolge ist unpraktikabel für sinnvolle Blocklängen. Basierend auf der
schnellen Fourier-Transformation nach Cooley-Tukey, zeigen wir, dass das Successive Cancellation Dekodieren in Ziffer-umgekehrter Symbol
Reihenfolge eine bedeutend tiefere Komplexität besitzt, jedoch auch eine
langsamere Polarisierung mit sich zieht. Trotzdem ist für viele Codes auch
diese reduzierte Komplexität immer noch unpraktikabel. Jedoch ist das Successive Cancellation
Dekodieren in der Zifferumgekehrten Symbol Reihenfolge praktikabel für die
vernünftig hohe Blocklänge von 256. Simulationen haben gezeigt, dass für diese
Blocklänge die synthetischen Kanäle polarisieren. Wir haben ausserdem
einen Weg gefunden um die eingefrorenen Symbole des Diskreten Fourier-Transformations Codes so zu wählen, dass dessen Blockfehlerwahrscheinlichkeit
für den Successive Cancellation
Dekodierer mit Liste sehr gut ist. Jedoch ist die Dekodierkomplexität um einiges höher als für andere Codes mit
vergleichbarer Blockfehlerwahrscheinlichkeit.
Der dritte Teil führt den
Fetter-Baum Dekodierer ein, der sowohl auf Polar wie
auch auf verwandte Codes anwendbar ist und der den Successive Cancellation
Dekodierer verallgemeinert. Der Fetter-Baum Dekodierer
rechnet auf einem kreisfreien Faktorgraphen und berechnet daher exakte A-Posteriori-Wahrscheinlichkeiten.
Der Fetter-Baum Dekodierer ist imstande die
Informationssymbole eines Polar Codes in jeder gewünschten Reihenfolge zu
dekodieren. Er ist ausserdem imstande beliebige
eingefrorene Symbole miteinzubeziehen. Damit jedoch die Komplexität immer noch
zu bewältigen ist, kann nur eine limitierte Anzahl an eingefrorenen Symbolen
miteinbezogen werden und die Dekodier Reihenfolge ist nicht beliebig. Zwei
konkrete Fetter-Baum Dekodier Strategien werden präsentiert,
die eine bedeutend tiefere Blockfehlerwahrscheinlichkeit als der Successive Cancellation Dekodierer haben und die eine praktikable Komplexität
besitzen. Beide Strategien erreichen die Blockfehlerwahrscheinlichkeit eines
Block-Maximum-A-Posteriori Dekodierers für viele Parameter. Die hohe
Flexibilität des Fetter-Baum Dekodierers legt nahe, dass Strategien mit einem
besseren Kompromiss zwischen Komplexität und tiefer
Blockfehlerwahrscheinlichkeit existieren.
Stichworte: Successive Cancellation;
Polar Codes; Faktorgraphen; Halbordnung; Code Konstruktion; Diskrete Fourier Transformation;
Schnelle Fourier Transformation; kreisfrei; Maximum-Likelihood Dekodierer; Maximum-A-Posteriori Dekodierer
Series / Reihe "Series in Signal and Information Processing" im Hartung-Gorre Verlag
Direkt bestellen bei / to order directly from