On Successive Cancellation Decoding of Polar - ETH E

Diss. ETH No. 23608
On Successive
Cancellation Decoding
of Polar Codes and
Related Codes
A dissertation submitted to
ETH Zurich
for the degree of
Doctor of Sciences
presented by
Christian Schürch
MSc ETH
born on December 23, 1985
citizen of Heimiswil (Bern)
accepted on the recommendation of
Prof. Dr. Hans-Andrea Loeliger, examiner
Prof. Dr. Henry D. Pfister, co-examiner
2016
Abstract
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 sucvii
viii
Abstract
cessive 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
Polar Codes mit einem Successive Cancellation Dekodierer waren historisch gesehen 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 FourierTransformations Codes so zu wählen, dass dessen Blockfehlerwahrscheinlichkeit für den Successive Cancellation Dekodierer mit Liste sehr gut ist.
ix
x
Kurzfassung
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

Download Report