Faculté informatique et communications IC, Section des systèmes de communication (Laboratoire de théorie des communications LTHC)

Conservation laws for coding

Measson, Cyril ; Urbanke, Rüdiger (Dir.) ; Montanari, Andrea (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3485.

Ajouter à la liste personnelle
    Summary
    This work deals with coding systems based on sparse graph codes. The key issue we address is the relationship between iterative (in particular belief propagation) and maximum a posteriori decoding. We show that between the two there is a fundamental connection, which is reminiscent of the Maxwell construction in thermodynamics. The main objects we consider are EXIT-like functions. EXIT functions were originally introduced as handy tools for the design of iterative coding systems. It gradually became clear that EXIT functions possess several fundamental properties. Many of these properties, however, apply only to the erasure case. This motivates us to introduce GEXIT functions that coincide with EXIT functions over the erasure channel. In many aspects, GEXIT functions over general memoryless output-symmetric channels play the same role as EXIT functions do over the erasure channel. In particular, GEXIT functions are characterized by the general area theorem. As a first consequence, we demonstrate that in order for the rate of an ensemble of codes to approach the capacity under belief propagation decoding, the GEXIT functions of the component codes have to be matched perfectly. This statement was previously known as the matching condition for the erasure case. We then use these GEXIT functions to show that in the limit of large blocklengths a fundamental connection appears between belief propagation and maximum a posteriori decoding. A decoding algorithm, which we call Maxwell decoder, provides an operational interpretation of this relationship for the erasure case. Both the algorithm and the analysis of the decoder are the translation of the Maxwell construction from statistical mechanics to the context of probabilistic decoding. We take the first steps to extend this construction to general memoryless output-symmetric channels. More exactly, a general upper bound on the maximum a posteriori threshold for sparse graph codes is given. It is conjectured that the fundamental connection between belief propagation and maximum a posteriori decoding carries over to the general case.
    Zusammenfassung
    Diese Arbeit behandelt Codierungssysteme, die auf graphischen Codes basieren. Der Schwerpunkt liegt auf der Beziehung zwischen der optimalen (Maximum a Posteriori) und der iterativen (Belief Propagation) Decodierung. Wir zeigen, dafl die Verbindung dieser zwei Codierungsarten durch eine Konstruktion gegeben ist, die identisch mit der Maxwell-Konstruktion in der Thermodynamik ist. Unser Hauptaugenmerk liegt auf einem Funktionstyp, der EXIT-Funktionen sehr ähnelt. EXIT-Funktionen wurden ursprünglich als handliches Mittel zum Design von iterativen Codierungssystemen eingeführt. Es stellte sich heraus, dafl EXIT-Funktionen einige wichtige grundlegende Eigenschaften haben. Einige dieser Eigenschaften lassen sich aber einzig auf den Löschkanal anwenden. Dies führte zu der Idee, GEXIT-Funktionen einzuführen, die im Fall des Löschkanals den EXIT-Funktionen entsprechen. Die GEXIT-Funktionen haben in vielen Fällen die gleichen Eigenschaften in Bezug auf allgemeine symmetrische Kanäle ohne Gedächtnis wie EXIT-Funktionen für Löschkanäle. Im Besonderen erfüllen die GEXIT-Funktionen das allgemeine Flächenerhaltungsgesetz. Als eine erste Anwendung dieses Theorems zeigen wir, dafl eine perfekte Übereinstimmung der GEXIT-Funktionen der Komponenten des Codes notwendig ist, um durch Belief Propagation die Rate der Kanalkapazität anzunähern. Diese Bedingung war bis jetzt nur für den Löschkanal bekannt. Als weiteres Ergebnis zeigen wir, dafl GEXIT-Funktionen für unendlich lange Blocklängen eine fundamentale Beziehung zwischen Belief Propagation und Maximum a Posteriori Decodierung aufzeigen. Ein Decodierungsalgorithmus, den wir Maxwell-Decodierer nennen, erlaubt eine operationelle Interpretierung für den Löschkanal. Sowohl der Algorithmus als auch die Analyse des Decodierers entstehen aus der U¨ bertragung der Maxwell-Konstruktion von der statistischen Physik auf das Gebiet der wahrscheinlichkeitsbasierten Decodierung. Wir zeigen erste Schritte, um diese Konstruktion für allgemeine symmetrische Kanäle ohne Gedächtnis zu generalisieren. Genauer gesagt entwickeln wir eine allgemeine obere Schranke für den Maximum a Posteriori Schwellenwert von graphischen Codes. Des weiteren folgern wir, dafl die grundlegende Beziehung zwischen Belief Propagation und Maximum a Posteriori Decodierung auf den allgemeinen Fall übertragen werden kann.
    Résumé
    Ce travail se consacre aux systèmes de codage de type Turbo codes. L'accent est mis sur la relation entre le décodage à maximum de vraisemblance et le décodage itératif dit à propagation de croyances. On montre que les deux types de décodage sont liés par une construction identique à la construction de Maxwell en thermodynamique. L'objet principal de notre étude est une fonction similaire à la fonction d'entropie de sortie qui est aussi appelée fonction EXIT. Il est vite apparu que les fonctions EXIT possèdent plusieurs propriétés extrêmement fortes. Malheureusement, la plupart d'entre elles ne s'appliquent qu'au canal à effacement. En introduisant les fonctions GEXIT, nous généralisons les propriétés fondamentales des fonctions EXIT. Plus exactement, les fonctions GEXIT et EXIT sont confondues sur le canal à effacement où elles partagent des propriétés communes. Elles diffèrent, en général, sur un canal symétrique et sans mémoire, où la fonction GEXIT conserve les mêmes propriétés. Les fonctions GEXIT satisfont notamment le théorème général des aires. Une première application de ce théorème est de généraliser la condition d'ajustement des courbes pour les codes constituants d'un code composite. Cette condition était, jusqu'à présent, connue uniquement dans le cadre du canal à effacement. Une deuxième application, principale et fondamentale, est le fait que les courbes GEXIT contiennent, par essence, le lien entre décodage à maximum de vraisemblance et décodage itératif. Ce lien apparaît lorsque les longueurs de mots utilisées tendent vers l'infini. Dans le cadre du canal à effacement nous introduisons le décodeur de Maxwell. Cet algorithme et son analyse sont la traduction exacte de la construction de Maxwell, mais cette fois dans le domaine du décodage probabilistique. Nous formulons la conjecture que cette construction de Maxwell se généralise à tout canal symétrique sans mémoire. Nous apportons plusieurs éléments de réponse qui valident cette hypothèse. En particulier, nous donnons une borne supérieure fine sur le seuil de décodage à maximum de vraisemblance d'un ensemble de codes de type Turbo codes.