Lechner, G. (2007). Efficient decoding techniques for LDPC codes [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-17493
E389 - Institut für Nachrichtentechnik und Hochfrequenztechnik
-
Date (published):
2007
-
Number of Pages:
87
-
Keywords:
Kanalcodierung; LDPC; iterative Decodierung
de
channel coding; LDPC; iterative decoding
en
Abstract:
Effiziente Decodieralgorithmen für LDPC Codes gewinnen mehr und mehr an Bedeutung, da diese Gruppe von Codes mittlerweile in vielen Standards vertreten ist. Trotz ihrer beeindruckenden theoretischen Leistungsfähigkeit, treten bei der praktischen Implementierung von LDPC Decodern Probleme wie numerische Instabilität, begrenzte Speichergröße, usw. auf. Diese Arbeit beschäftigt sich mit Methoden, welche die Decodier-Komplexität reduzieren und gleichzeitig den Verlust gering halten. Um dies zu erreichen, untersuchen wir drei Punkte: die Vereinfachung der Komponenten eines LDPC Decoders, die Verwendung von harten Entscheidungen innerhalb des Decoders und die Kombination des LDPC Decoders mit anderen Aufgaben einer iterativen Empfängerstruktur.<br />Für die Vereinfachung der Komponenten analysieren wir den min-sum Algorithmus und entwickeln ein theoretisches Gerüst mit welchem bekannte heuristische Methoden zur Verbesserung dieser Approximation erklärt werden. Weiters adaptieren wir den Algorithmus für irreguläre LDPC Codes und erreichen eine Verbesserung nahe zum optimalen Algorithmus.<br />Die Einschränkung der internen Werte auf harte Entscheidungen führt zu einer Reduktionen der Speichererfordernisse und erlaubt die Implementierung von Decodern mit hohem Datendurchsatz, wie sie zum Beispiel in optischen Systemen verwendet werden. Wir verwenden extrinsic information transfer charts, um diese Gruppe von Decodern zu analysieren, wobei sich als Spezialfall der Algorithmus von Gallager ergibt. Wir verallgemeinern diesen Algorithmus für den Fall, daß der Kanal mehr Information als eine harte Entscheidung zur Verfügung stellt und verwenden die Analyse, um Schranken für diese Gruppe von Decodern herzuleiten. Weiters zeigen wir, wie Codes für diese Algorithmen optimiert werden können.<br />Zuletzt präsentieren wir die Optimierung eines LDPC Codes für den Fall, daß der Decoder im Kontext einer Empfängerstruktur betrachtet wird, wobei der Empfänger weitere Aufgaben wie Demapping oder Multi-User Detektion übernimmt. Wir zeigen, wie der LDPC Code effizient optimiert werden kann, wobei die Verteilungen der Symbol und Prüfknoten gemeinsam optimiert werden. Diese Optimierung des Codes erfordert nur die Kenntnis der Transfer Funktion der beteiligten Empfänger-Teile, welche entweder analytisch oder durch Simulation gewonnen werden kann. Nach einer allgemeinen Herleitung der Code Optimierung, wenden wir diese auf iteratives Demapping und iterative Multi-User Detektion an.<br />
de
Efficient decoding techniques for LDPC codes are in demand, since these codes are included in many standards nowadays. Although the theoretical performance of LDPC codes is impressive, their practical implementation leads to problems like numerical inaccuracy, limited memory resources, etc. We investigate methods that are suited to reduce the decoding complexity while still keeping the loss in performance small. We aim to reduce the complexity using three approaches:<br />simplification of the component decoders, restricting the message passing algorithm to binary variables and combining the LDPC decoder with other receiver tasks like demapping or multi-user detection.<br />For the simplification of the component decoders, we analyze the min-sum algorithm and derive a theoretical framework which is used to explain previous heuristic approaches to improve the performance of this algorithm. Using this framework, we are able to modify the algorithm in order to achieve good performance for regular as well as irregular LDPC codes.<br />Restricting all internal messages of an LDPC decoder to binary variables, leads to a significant reduction of memory requirements and allows the implementation of high-throughput decoders which are used for example in optical communication systems. We analyze binary message passing decoders using a general framework which is based on extrinsic information transfer charts. As special cases, we rederive Gallagers bit-flipping algorithm. Our derivation allows to generalize these algorithms for the case where soft-information from the channel is available, while still using binary variables for all internal messages.<br />The analysis is used to derive bounds and to optimize LDPC codes for binary message passing decoders.<br />Finally, we consider the optimization of an LDPC code where the decoder is not considered on its own, but in the context of a receiver structure which performs additional tasks like demapping or multi-user detection.<br />We show how the code optimization can be performed efficiently by optimizing the degree distributions of variable and check nodes jointly.<br />Our code optimization requires only knowledge of the extrinsic information transfer function of the receiver front-end, which can be obtained either analytically or via simulations. After a general derivation of the code optimization, we apply the optimization tools to iterative demapping and iterative multi-user detection.