Iterative algorithms for achieving near-ML decoding performance in concatenated coding systems

Zhang, Dan; Meyr, Heinrich

doi:32787

Iterative algorithms for achieving near-ML decoding performance in concatenated coding systems = Iterative Algorithmen zur Annäherung an die ML-Decoder-Performance in verketteten Codier-Systemen

Zhang, Dan (Author)

2013 & 2014

Verantwortlichkeitsangabevorgelegt von Dan Zhang

ImpressumAachen : Publikationsserver der RWTH Aachen University 2013

UmfangVI, 235 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2013

Prüfungsjahr: 2013. - Publikationsjahr: 2014

Genehmigende Fakultät
Fak06

Hauptberichter/Gutachter
Meyr, Heinrich (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2013-11-05

Online
URN: urn:nbn:de:hbz:82-opus-48492
URL: https://publications.rwth-aachen.de/record/229401/files/4849.pdf

Einrichtungen

Lehrstuhl für Integrierte Systeme der Signalverarbeitung (611810)

Inhaltliche Beschreibung (Schlagwörter)
Maximum-Likelihood-Decodierung (Genormte SW) ; Optimierung (Genormte SW) ; Schätzung (Genormte SW) ; Iterativ (Genormte SW) ; Effizienz (Genormte SW) ; MIMO (Genormte SW) ; Ingenieurwissenschaften (frei) ; BICM (frei) ; maximum-likelihood-decoding (frei) ; optimization (frei) ; estimation (frei) ; iterative algorithms (frei) ; efficiency (frei)

Thematische Einordnung (Klassifikation)
DDC: 620

Kurzfassung
Im Laufe des letzten Jahrzehnts ist die Nachfrage nach zuverlässigen und hohen Datenraten für die drahtlose Kommunikation schnell gewachsen. Der Erfolg von Turbo-Codes hat zu einer Vielzahl von Anwendungen der verketteten Codierung geführt, um eine zuverlässige Übertragung mit einer Datenrate nahe der Kanalkapazität zu unterstützen. Am Empfänger ist Maximum-Likelihood (ML)-Decodierung im Sinne der Minimierung der Framefehlerrate (FER) optimal. Es ist bekannt, dass ML-Decodierung für die Klasse von verketteten Codes NP-schwer ist. Für Turbo-Codes ist die heuristische iterative Turbo-Decodierung in der Lage annähernd die Performance der ML-Decodierung zu erreichen. Die Idee dahinter, das Turbo-Prinzip, kann daher auf das gesamte Empfängerdesign in verkettet kodierten Systemen erweitert werden. In dieser Arbeit wird die theoretische Beziehung zwischen der ML-Decodierung und der iterativen Turbo-Decodierung untersucht. Die erzielten Ergebnisse werden weiter zur Erstellung eines systematischen Frameworks zur Ableitung approximativer ML-Decodieralgorithmen in praktischen verkettet kodierten Systemen verwendet. Zuerst wird das ML-Decodierungs-Problem mit einem eingeschränkten Bethe freie Energie-Minimierungsproblem verknüpft, das üblicherweise in der statistischen Physik untersucht wird. Daraufhin werden hinreichende Bedingungen für die Existenz einer deterministischen Beziehung zwischen den global minimalen Lösungen der beiden Probleme hergeleitet. Auf dieser theoretischen Basis wird das Minimierungsproblem der eingeschränkten Bethe freie Energie als eine Näherung des ML-Decodierungs-Problems interpretiert, welche eine effiziente Bestimmung der Lösung erlaubt. Eine effektive iterative Methode, die die eingeschränkte Bethe freie Energie minimiert, ist die Turbo-Decodierung. Zweitens wird die Bethe freie Energie-Näherung zur ML-Decodierung erweitert, um einen approximativen ML-Decodieralgorithmus in einem System unter Verwendung von Bit-interleaved Turbo-codierter Modulation und Mehrantennen (MIMO)-Technologie zu erhalten. Der resultierende Algorithmus besteht aus zwei verschachtelten Schleifen. Die Implementierung eines solchen doppelt iterativen Decodierungsprozesses wird adressiert. Insbesondere wird ein Schema basierend auf einer Ameisenkolonie-Optimierung (ACO) für die Festlegung der Ausführungsreihenfolge der inneren und äußeren Iterationen anhand der Kenntnisse über die Kanalstatistiken vorgestellt. Zusätzlich werden obere Schranken für die Fehlerwahrscheinlichkeit der ML-Decodierung hergeleitet. Diese dienen als Basis zur Evaluierung der Performancedifferenz zwischen dem doppelt iterativen Decodieralgorithmus und der ML-Decodierung. Schließlich wird das ML-Decodierungs-Problem mit unvollständigen Informationen über die Kanäle betrachtet. Basierend auf der Bethe freie Energie-Approximation, werden zwei approximative iterative Algorithmen zur gemeinsamen Kanalschätzung und ML-Decodierung hergeleitet. Darüber hinaus wird gezeigt, dass der Bethe freie Energie Ansatz eine Verbindung zwischen etablierten Algorithmen zur iterativen Kanalschätzung und Decodierung in der Literatur und dem ML-Decodierungs-Problem herstellt.

Over the last decade, the demand for reliable and high data rate wireless communication has been rapidly growing. The success of turbo codes has led to many applications of concatenated coding to support a reliable transmission at a data rate close to the channel capacity. At the receiver, maximum likelihood (ML) decoding is optimal in the sense of minimizing the frame error rate (FER). It is known that ML decoding is NP-hard for the class of concatenated codes. For turbo codes, the heuristically invented iterative turbo decoding algorithm is able to offer near-ML decoding performance. The idea behind it, i.e., the turbo principle, is therefore extended to cover the whole receiver design in concatenated coding systems. In this thesis, the theoretical relation between ML decoding and iterative turbo decoding is investigated. The obtained results are further applied to establish a systematic framework for deriving approximate ML decoding algorithms in practical concatenated coding systems. First, the ML decoding problem is linked to a constrained Bethe free energy minimization problem commonly studied in statistical physics. More specifically, sufficient conditions on the existence of a deterministic relation between the global optimal solutions of the two problems are derived. On this theoretical basis, the constrained Bethe free energy minimization problem is further interpreted as an approximation to the ML decoding problem that allows for computationally efficient solutions. One effective iterative method to minimize the constrained Bethe free energy is turbo decoding. Second, the Bethe free energy based approximation to the ML decoding problem is extended to obtain an approximate ML decoding algorithm in a system using bit-interleaved turbo-coded modulation and multiple antennas. The resulting algorithm consists of two nested loops. The implementation of such doubly iterative decoding process in practical multiple antenna systems is addressed. In particular, an ant colony optimization (ACO) based scheme is presented for determining the execution order of the inner and outer iterations based on the knowledge of channel statistics. Furthermore, upper bounds on the error probability of ML decoding are analytically derived, providing baselines for validating the capability of the doubly iterative decoding algorithm in achieving near-ML decoding performance. Finally, the ML decoding problem with incomplete channel information is considered. Based on the Bethe free energy approximation, two approximate iterative algorithms are derived for joint channel density estimation and ML decoding. Furthermore, the Bethe free energy approach is shown to provide a link that can connect iterative channel estimation and decoding algorithms in the literature to the ML decoding problem.

Fulltext:
PDF