Information-optimal decoding and demodulation on sparse graphs

Abstract

In der vorliegenden Dissertation beschäftigen wir uns mit informations-optimaler Kodierung, angewandt zur Quantisierung gaußscher Zufallsvariablen sowie zur Konzeptionierung diskreter, informations-optimaler Dekodierverfahren. Darüber hinaus schlagen wir ein neuartiges Verfahren für die vorwärtsfehlerkorrigierte Datenübertragung über additive Rauschkanäle vor, welches zeitgleiche Demodulierung und Dekodierung mit linearer Komplexität ermöglicht. Nach einem kurzen Überblick über die relevante Literatur beginnen wir mit einer Diskussion über die informations-optimale Quantisierung gaußscher Zufallsvektoren. “Informations-optimal” bedeutet in diesem Zusammenhang, das Quantisierungsverfahren so zu gestalten, dass die Transinformation zwischen der quantisierten, sowie einer zweiten, mit dem Quantisierereingang korrelierten Zufallsvariable, maximal wird. Für diesen Fall betrachten wir den sogenannten Informations-Raten-Abgleich, d.h. die maximal mögliche Transinformation unter der Vorgabe einer höchstzulässigen Kompressionsrate. Wir leiten eine fundamentale Verbindung zwischen informations-optimaler und linear gefilterter, MSE1 -optimaler Quantisierung her, die eng mit den Konzepten der Wiener-Filterung im Zusammenhang steht. Anschließend nutzen wir diese Verbindung, um aus bewährten, MSE-optimalen Quantisierungsverfahren informations-optimale Verfahren abzuleiten. Im Weiteren benutzen wir das Prinzip der Informations-Optimalität zur Konstruktion dis- kreter, LUT2-basierter LDPC3-Dekoder mit geringer Bitbreite. Wir leiten einen Zusammenhang zwischen LUT-Dekodierung und dem belief propagation- Dekodierverfahren her, welchen wir für das Design hybrider Dekodierverfahren mit geringer Komplexität und hoher Fehlertoleranz heranziehen. Besondere Aufmerksamkeit schenken wir dabei der LUT-Dekodierung irregulärer LDPC-Codes, für die wir gemeinsam optimierte LUT-Designs ableiten und ein Ver- fahren zur Optimierung der irregulären Codegraphenstruktur unter der Berücksichtigung von LUTs vorschlagen. Die so erzeugten Decoder liefern niedrigere Fehlerraten als konventionelle min-sum-Decoder mit Gleitkommapräzision bei einer LUT-Auflösung von nur 3 Bit bei regulären und 4 Bit bei irregulären Codes. Letztlich führen wir SMLDPC4-Codes neu ein. Dabei handelt es sich um eine neuartige Klasse von Vorwärtsfehlerkorrektur-Codes mit hoher Rate für Rauschkanalübertragungen. SMLDPC-Codes ergeben sich durch eine Kombination aus LDPC-Codes und Superpositions Modulation (SM) und erlauben zeitgleiche Datendemodulierung und –dekodierung mithilfe spärlich besetzter Graphen. Indem verschiedene Gewichte für die SM herangezogen werden, decken SMLDPC-Codes ein weites Spektrum unterschiedlichster Modulationsarten ab – darunter die weitverbreitete Quadraturamplitudenmodulation (QAM). Wir liefern einen mathematisch exakten Beweis, dass SMLDPC-Codes das gleiche Konzentrations– und Grenzwertverhalten wie konventionelle LPDC-Codes aufweisen, d.h. dass für den Grenzfall unendlich langer Codes alle zufällig erzeugten Codes aus dem gleichen Ensemble dasselbe Fehlerkorrekturverhalten aufweisen, und sich dieses durch den Mittelwert zyklenfreier Codegraphen beschreiben lässt. Darüber hinaus zeigen wir, wie sich dieser Mittelwert für belief propagation-Decodierung exakt berechnen lässt. Daraus ergibt sich ein Verfahren zur Codeoptimierung, bei dem wir nicht einzelne Codes, sondern die Verteilung des gesamten Code-Ensembles optimieren. Das Konzentrationstheorem besagt dann, dass sich ein zufällig aus einem Ensemble ausgewählter Code ebenso verhält wie der Ensemble-Mittelwert.

In this thesis, we consider information-optimal quantization of Gaussian random variables and derive discrete information-optimal decoders for low-density parity-check (LDPC) codes. Moreover, a novel joint decoding and demodulation approach for transmission over continuous input additive white noise channels is proposed. After a brief revision of related concepts, we begin by discussing information-optimal quantization of Gaussian random vectors. Here, information-optimal means that the quantization preserves information on a second variable that is correlated with the quantizer input. We study the rate information tradeoff for this setting which characterizes the highest amount of information that can be retained for any given quantization rate. Furthermore, we establish a fundamental connection between information-optimal quantization and linearly preprocessed mean-square error (MSE)-optimal rate distortion quantization based on concepts related to Wiener filtering. We then use this connection to obtain information-optimal quantizer designs from well-known MSE-optimal designs. Next, we use the principle of information-optimality to design low-resolution discrete message passing LDPC decoders based on look-up tables (LUTs). We show that there is a con- nection between LUT decoding and belief propagation and use this to derive low-complexity hybrid decoding approaches. Special attention is paid to LUT decoding for irregular LDPC codes, for which we derive jointly optimal LUT designs and propose a strategy to optimize the degree distributions of irregular codes for LUT decoding. The so obtained decoders outper- form conventional min-sum decoders at floating point precision at LUT resolutions as low as 3 bit for regular and 4 bit for irregular codes. Subsequently, we introduce superposition modulated low-density parity-check (SMLDPC) codes — a new class of codes for high-rate transmission over continuous input channels. SM- LDPC codes are obtained by a concatenation of LDPC coding and superposition modulation (SM) and allow for parallel decoding and demodulation on a joint sparse graph without the need of deinterleaving or an explicit demodulation step. By using different edge coefficients for SM, a wide variety of modulation schemes can be adopted by SMLDPC codes, including the well-known regular QAM constellations. We show that SMLDPC codes exhibit the same concentration and thresholding phenomenon as LDPC codes, where the thresholds can be computed exactly for belief propagation decoding. This gives rise to a code optimization approach based on ensembles, i.e., we propose to optimize the distributions that characterize the codes rather than the codes themselves. A particular code is then obtained by drawing a random sample from the ensemble and the concentration theorem states that for long block lengths, any code obtained that way will perform as predicted by the ensemble threshold.