Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
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.
Chargement
Chargement
Chargement
Chargement
Chargement
seeding'' perfect information on the replicas at the boundaries of the coupling chain. This extra information makes decoding easier near the boundaries, and this effect is then propagated into the coupling chain upon iterations of the decoding algorithm. Spatial coupling was also applied to various other problems that are governed by low-complexity message-passing algorithms, such as random constraint satisfaction problems, compressive sensing, and statistical physics. Each system has an associated algorithmic threshold and an optimal threshold. As with coding, once the underlying graphs are spatially coupled, the algorithms for these systems exhibit optimal performance. In this thesis, we analyze the performance of iterative low-complexity message-passing algorithms on general spatially coupled systems, and we specialize our results in coding theory applications. To do this, we express the evolution of the state of the system (along iterations of the algorithm) in a variational form, in terms of the so-called potential functional, in the continuum limit approximation. This thesis consists of two parts. In the first part, we consider the dynamic phase of the message-passing algorithm, in which iterations of the algorithm modify the state of the spatially coupled system. Assuming that the boundaries of the coupled chain are appropriately
seeded'', we find a closed-form analytical formula for the velocity with which the extra information propagates into the chain. We apply this result to coupled irregular LDPC code-ensembles with transmission over general BMS channels and to coupled general scalar systems. We perform numerical simulations for several applications and show that our formula gives values that match the empirical, observed velocity. This confirms that the continuum limit is an approximation well-suited to the derivation of the formula. In the second part of this thesis, we consider the static phase of the message-passing algorithm, when it can no longer modify the state of the system. We introduce a novel proof technique that employs displacement convexity, a mathematical tool from optimal transport, to prove that the potential functional is strictly displacement convex under an alternative structure in the space of probability measures. We hence establish the uniqueness of the state to which the spatially coupled system converges, and we characterize it. We apply this result to the (l,r)-regular Gallager ensemble with transmission over the BEC and to coupled general scalar systems.