Details
| Autor: | Marcos B.S. Tavares |
| Titel: | On Low-Density Parity-Check Convolutional Codes: Constructions, Analysis and VLSI Implementation |
| Typ: | Dissertation |
| Fachgebiet: | Informationstechnik |
| Reihe: | Mobile Nachrichtenübertragung, Nr.: 48 |
| Auflage: | 1 |
| Sprache: | Englisch |
| Erscheinungsdatum: | August 2010 |
| Lieferstatus: | Lieferbar |
| Umfang: | 236 Seiten |
| Bindung: | Soft |
| Preis: | 49,00 EUR |
| ISBN: | 9783938860380 |
| Umschlag: | (vorn) |
| Inhaltsverzeichnis: | (pdf) |
Abstrakt in Englisch
This dissertation concerns the study and further development of low-density parity-check (LDPC) convolutional codes. In contrast to LDPC block codes, LDPC convolutional codes are not limited to a single block length, and the same encoder and decoder apparatuses can be used for processing varying block lengths.
We follow the philosophy of probabilistic coding. Therefore, our main objective is to find codes that optimize the performance/complexity tradeoff. In this sense, because the same encoders/decoders can be used for processing different block lengths (which may imply a constant complexity for different performances), the LDPC convolutional codes have the potential of achieving good performance/complexity tradeoffs.
One of the main inventions presented in this dissertation are the tail-biting versions of LDPC convolutional codes. The tail-biting LDPC convolutional codes represent an elegant solution to the rate-loss problem of terminated code sequences while still keeping the same underlying bipartite graph structures and, thus, the same performance/complexity properties as their mother convolutional codes. We show with the help of several computer simulations that the tail-biting LDPC convolutional codes are serious competitors to conventional LDPC block codes.
Two different construction approaches for LDPC convolutional codes and their tailbiting versions are proposed. The first construction approach is of algebraic nature and produces time-invariant codes. The second construction approach uses performance-optimized graph templates called protographs as base for the generation of larger graphs. Along with these two construction procedures, we also provide bounds to the performance of codes with quasi-cyclic symmetries. Moreover, we study the bipartite graph configurations that lead to the error-floor phenomenon and propose techniques for avoiding these harmful graph configurations during the code construction. By means of computer simulations, we compare the performance of the codes obtained from the procedures discussed above against codes from constructions presented in the literature, where we can observe the superiority of our constructions in terms of the performance/complexity tradeoff. In order to assess the performance of code ensembles - rather than the performance of a single code - we propose a framework for the asymptotic analysis of free/mininum distances and trapping set properties of protograph-based ensembles of LDPC convolutional codes and their tail-biting versions. Using numerical analysis, we show the dual nature of tailbiting LDPC convolutional codes, which can behave as block or as convolutional codes depending on the length of the tail-biting code sequences being considered. Moreover, in the situations where the tail-biting LDPC convolutional codes behave as block codes, we show that the performance can be improved while the encoding/decoding complexity remains constant.
Especially for low coding rates - where the complexity of belief propagation decoding becomes high - we present a new protograph-based code construction method based on the braided concatenation of component convolutional codes. The codes originating from this construction, which we call braided protograph convolutional codes, can be decoded using the belief propagation algorithm or a trellis based decoding algorithm, depending on how the underlying protographs are lifted. Hence, the decoding algorithm for the braided protograph convolutional codes can be chosen such that the decoding complexity is minimized. Computer simulations show the superiority (in the moderate to high SNR region) of the tail-biting braided protograph convolutional codes when compared against turbo codes with the same length, and with component encoders with the same number of states. Moreover, the interleaving structure of the braided protograph convolutional codes and their tail-biting versions enables the development of efficient, high-speed decoding architectures. Furthermore, an asymptotic analysis of the convergence properties of the braided protograph convolutional codes confirms their clear superiority to the turbo codes. Coding for the multiple-access channel is also addressed in this dissertation. For this purpose, we introduce a new scheme called braided code division multiple access (BCDMA), which is based on orthogonal frequency division multiplexing (OFDM) and braided convolutional codes. The BCDMA scheme represents a paradigm shift in the design of modems for multiple-access applications. In this case, the tasks of error-correction coding, interleaving for channel diversity exploitation, modulation and multiple access - which are generally processed by separate elements of a modem - are now concentrated in one single entity. Moreover, the comparison of the BCDMA scheme against conventional bit-interleaved coded modulation (BICM) schemes based on turbo and LDPC block codes shows that the BCDMA scheme is an attractive option in terms of the performance/complexity tradeoff. In order to be able to evaluate the performance/complexty tradeoff in its fundamentals, we study VLSI decoding architectures for LDPC convolutional codes and their tail-biting versions. For this purpose, we propose an algebraic framework that captures the structured parallelism inherent to the bipartite graphs underlying the LDPC convolutional codes and their tail-biting versions. From this algebraic framework, we derive an architectural template that can be used as base to form even more powerful decoders. In this case, a new dimension of scalability is obtained, which is not possible for LDPC block codes. As case studies, we consider the implementation of programmable, high-speed decoding processors. Synthesis results and a chip implementation show that it is possible to achieve throughputs in the range of Gbit/s/Iteration, still with relatively small area and low power consumption.
Abstrakt in Deutsch
Diese Dissertation beschreibt die Untersuchung und die Weiterentwicklung von Low-Density Parity-Check (LDPC) Faltungscodes. Im Unterschied zur LDPC-Blockcodes sind LDPCFaltungscodes nicht auf eine bestimmte Blocklänge beschränkt, und die gleichen Encoderund Decoder-Vorrichtungen können benutzt werden, um variable Blocklängen zu verarbeiten. Wir verfolgen das Konzept der probabilistischen Kodierung. Unsere Hauptaufgabe ist die Suche nach Codes, die den Kompromiss zwischen Leistungsfähigkeit und Komplexität optimieren. Da die gleichen Encoder und Decoder für die Verarbeitung von verschiedenen Blocklängen genutzt werden können (und dies konstante Komplexität für variable Leistungsfähigkeit bedeutet), besitzen LDPC-Faltungscodes das Potenzial, gute Kompromisse zwischen Leistungsfähigkeit und Komplexität zu erzielen.
Eine der Haupterfindungen, die in dieser Dissertation vorgestellt wird, sind die Tail- Biting Versionen der LDPC-Faltungscodes. Die Tail-Biting LDPC-Faltungscodes stellen eine elegante Lösung des Rate-Loss Problems von terminierten Codesequenzen dar. Sie besitzen die grundlegende zweiteilige Graphenstrukturen zusätzlich zum Kompromiss zwischen Leistungsfähigkeit und Komplexität ihrer Mutter-Faltungscodes. Wir zeigen mit der Hilfe von verschiedenen Computersimulationen, dass die Tail-Biting LDPC-Faltungscodes ernstzunehmende Konkurrenten von herkömmlichen LDPC-Blockcodes sind.
Zwei verschiedene Konstruktionsansätze für LDPC-Faltungscodes und ihre Tail-Biting Versionen werden vorgeschlagen. Der erste Konstruktionsansatz ist von algebraischen Natur und erzeugt zeitinvariante Codes. Der zweite Konstruktionsansatz nutzt optimierte Graphenvorlagen (bekannt als Protographen) als Basis für die Eurzeugung von großeren Graphen. Neben diesen zwei Konstruktionsprozeduren werden auch Grenzen der Leistungsfähigkeit von Codes mit quasi-zyklischen Symmetrien aufgezeigt. Darüber hinaus untersuchen wir die Graphenkonfigurationen, die zum Error-Floor Phänomen führen, und wir schlagen Techniken zur Vermeidung dieser schlädlichen Graphenkonfigurationen während der Codekonstruktion vor. Anhand von Computersimulationen vergleichen wir die Leistungsfähigkeit der Codes, die mit den oben erwähnten Prozeduren erzeugt wurden, mit Codes von Konstruktionen, die in der Literatur präsentiert werden, wobei wir die Überlegenheit unserer Codes bezüglich des Kompromisses zwischen Leistungsfähigkeit und Komplexität nachweisen können.
Mit der Absicht die Leistungsfähigkeit von Codeensembles - anstatt der Leistungsfähigkeit von einem einzelnen Code - zu bewerten, schlagen wir vor, ein Rahmenwerk für die asymptotische Analyse der Frei- und Minimaldistanz und auch der Trapping-Set Eigenschaften von protograph-basierten Ensembles von LDPC-Faltungscodes und ihrer Tail-Biting Versionen zu untersuchen. Anhand von numerischer Analyse wird die duale Natur von Tail-Biting LDPC-Faltungscodes festgestellt, die sich abhängig von ihren Längen entweder als Blockcodes oder als Faltungscodes verhalten. Ferner wird es gezeigt, dass sich die Leistungsfähigkeit in Situationen, in denen Tail-Biting LDPC-Faltungscodes als Blockcodes arbeiten, ohne Änderung der Encodierungs-/Decodierungskomplexität verbessern lässt.
Besonders für niedrige Codierungsraten - wenn die Komplexität der Belief-Propagation Decodierung steigt - präsentieren wir eine neuartige protograph-basierte Codekonstruktionsmethode, die sich auf der umflochtenen Verkettung von Komponentenfaltungscodes basiert. Die Codes, die bei dieser Konstruktionsmethode entstehen, bezeichnen wir als Braided Protograph Faltungscodes. Die Braided Protograph Faltungscodes können abhängig von der Weise, auf der die grundlegenden Protographen zusammengefügt werden, mittels der Belief-Propagation oder Trellis-basierten Algorithmen decodiert werden. Infolgedessen kann der Decodierungsalgorithmus für Braided Protograph Faltungscodes so gewählt werden, dass die Decodierungskomplexität minimiert wird. Computersimulationen zeigen die Überlegenheit (in der moderaten bis hohen SNR-Region) der Tail-Biting Braided Protograph Faltungscodes, wenn diese mit Turbo-Codes der gleichen Blocklänge und der gleichen Anzahl von Zuständen des Komponentencodes verglichen werden. Darüber hinaus ermöglicht die Interleaving-Struktur von Braided Protograph Faltungscodes und von ihren Tail-Biting Versionen die Entwicklung von effizienten Hochgeschwindigkeitsdecoder- Architekturen. Zudem bestätigt die asymptotische Analyse der Konvergenzeigenschaften der Braided Protograph Faltungscodes ihre eindeutige Überlegenheit gegenüber Turbo- Codes.
Codierung für den Vielfachzugriffskanal wird zusätzlich in dieser Dissertation betrachtet. Für diesen Zweck wird ein neuartiges Schema entwickelt, das wir Braided Code Division Multiple Access (BCDMA) nennen und Orthogonal Frequency Division Multiplexing (OFDM) und Braided Faltungscodes als Grundlagen besitzt. Das BCDMA-Schema stellt einen Paradigmenwechsel für den Entwurf von Modems für Vielfachzugriffsanwendungen dar. In diesem Fall werden die Aufgaben der Kodierung für Fehlerkorrektur, Interleaving für die Ausnutzung der Kanaldiversität, Modulation und Vielfachzugriff, die normalerweise von verschiedenen Elementen eines Modems übernommen werden, in einer einzigen Einheit vereinigt. Darüber hinaus zeigt ein Vergleich zwischen dem BCDMA-Schema und herkömmlichen Turbo-Code-basierten Bit-Interleaved Coded Modulation (BICM) Schemata die Atraktivität des BCDMA-Schemas im Hinblick auf den Kompromiss zwischen Leistungsfähigkeit und Komplexität.
Mit dem Ziel den Kompromiss zwischen Leistungsfähigkeit und Komplexität in seinen Grundlagen zu evaluieren haben wir die VLSI-Decoderarchitekturen für LDPC-Faltungscodes und ihre Tail-Biting Versionen untersucht. Für diesen Zweck schlagen wir ein algebraisches Rahmenwerk vor, das den Parallelismus inhärent zu den grundlegenden zweiteiligen Graphen der LDPC-Faltungscodes und ihrer Tail-Biting Versionen erfasst. Anhand dieses algebraischen Rahmenwerks wird eine architektonische Vorlage hergeleitet, die benutzt werden kann, um noch leistungsfähigere Decoder zu bauen. In diesem Fall ist eine neue Dimension der Skalierbarkeit erreicht, die mit LDPC-Blockcodes nicht möglich ist. Als Fallbeispiele betrachten wir die Implementierung von programmierbaren Hochgeschwindigkeitsdecoderprozessoren. Ergebnisse der Synthese und der Chip-Implementierung zeigen, dass Datendurchsätze in der Größenordnung von Gbit/s/Iteration mit relativ kleiner Fläche und niedrigem Leistungsverbrauch erreichbar sind.