Spatially-coupled LDPC codes: introduction, theoretical advances and practical applications
Thèmes scientifiques :
- D - Télécommunications : compression, protection, transmission
Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.
17 personnes membres du GdR ISIS, et 24 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 140 personnes.
Meeting on Spatially-Coupled Coding
Our meeting is going to provide an overview of a new coding technique (the so called spatial coupling), which is accessible to researchers and students working in the area of communication systems, information theory, coding and signal processing.
Spatially-coupled codes are being actively investigated by the coding community, thanks to their outstanding asymptotic performance over a myriad of channel models (e.g. binary erasure channel, Gaussian channel, fading channels, etc.). This code construction has been recently extended to a large number of communication problems, such as transmission over multiple-access and relay channels, the Slepian-Wolf problem, multi-user modulation schemes, etc. In general, the spatial coupled technique (along with its threshold saturation phenomenon) was conjectured to be a general approach to achieve the optimal performance of a transmission system.
Our GdR-ISIS meeting will be organized around the most recent advances in the spatial coupling technique and its applications. The meeting will include:
- a tutorial on the spatial coupling technique (given by Prof. R. Urbanke),
- a session of invited talks by confirmed researchers in the area,
- a session of talks by young researchers willing to participate and to present their recent results.
Date and place:
The meeting will be held on the 19th of November, 2014, at Campus Jussieu, Amphitheatre Durand.
- Iryna Andriyanova (firstname.lastname@example.org, ETIS/ENSEA-Université de Cergy-Pontoise-CNRS)
- Charly Poulliat (email@example.com, IRIT/ENSEEIHT)
We acknowledge the sponsorship of the ETIS Laboratory, ENSEA-Université de Cergy-Pontoise-CNRS, and of the IRIT Laboratory, ENSEEIHT.
9:20 - 9:30 Opening
9:30 - 11:30 Spatial Coupling - A Primer (R. Urbanke)
11:30 - 13:00 Lunch break
13:00 - 13:30 Spatially-Coupled Turbo-Like Codes (M. Lentmaier)
13:30 - 14:00 Analyzing Finite-Length Spatially-Coupled LDPC Codes (P. Olmos)
14:00 - 14:20 Sparse Superposition Codes for the Gaussian Channel (J. Barbier)
14:20 - 14:30 Coffee break
14:30 - 15:00 Quantum Spatially-Coupled LDPC Codes (J.-P. Tillich)
15:00 - 15:30 Nonbinary Spatially-Coupled LDPC Codes (A. Graell i Amat)
15:30 - 15:50 Codes for Continuous Phase Modulation (T. Bennadi)
15:50 - 16:00 Coffee break
16:00 - 16:30 Spatially-Coupled Codded Slotted Aloha (G. LIva)
16:30 - 17:00 Spatially-Coupled LDPC Codes for Nonergodic Channels (N. ul Hassan)
17:00 - 17:20 Finite-Alphabet Iterative Decoders Robust to Faulty Hardware (E. Dupraz)
17:20 - 17:30 Closing
Résumés des contributions
Spatial Coupling - A Primer
Designing good sparse-graph codes is the problem of finding graphical structures that interact well with the message-passing decoder. Over the past 20 years many such structures have been proposed and have been found to be useful. Prominent examples of structures that work well are turbo codes, low-density parity-check codes with properly chosen degree distributions, or multi-edge ensembles.
I will talk about a further such structure which emerges if we "couple" several of our favorite graphical models along a spatial dimension. Here, "coupling" means that we connect neighbouring graphical models and we do it in such a way that the local connectivity of the graphs stays undisturbed. Due to this spatial structure, and a well chosen boundary condition, such graphical models behave under iterative decoding as well as if one had taken one of the underlying components and decoded it in an optimal fashion. I will explain why this happens and how we can take advantage of this effect. As I will discuss, this is the same phenomenon which is responsible for crystal growth and the formation of hail.
Although most of this talk will center on how to design good error correcting codes, the principle of spatial coupling can also be used in other areas (such as compressive sensing or constraint satisfaction problems). Time permitting, I will briefly paint the broader picture.
Spatially-Coupled Turbo-Like Codes: Convolutional Codes on Graphs
Lund University, Sweden
In this work we apply the concept of spatial coupling to turbo-like codes and investigate the impact on their iterative belief propagation (BP) decoding thresholds. Parallel concatenated and serially concatenated convolutional codes as well as braided convolutional codes (BCCs) are compared by means of an exact density evolution (DE) analysis for the binary erasure channel (BEC). For all three classes of codes we demonstrate that their BP thresholds approach the maximum-a-posteriori (MAP) threshold of the uncoupled ensemble. A comparison of the different ensembles shows that parallel concatenated ensembles can be outperformed by both serially concatenated and BCC ensembles, although they have the best BP thresholds in the uncoupled case.
The considered examples of turbo-like codes demonstrate that the concept of spatial coupling opens some new degrees of freedom in the design of codes on graphs: instead of optimizing the component encoder characteristics for BP decoding it is possible to consider ensembles with good MAP decoding threshold and rely on the threshold saturation effect of spatial coupling. Powerful code ensembles with strong distance properties can then perform close to capacity with low-complexity iterative decoding.
Analyzing Finite-Length Spatially-Coupled LDPC Codes Constructed from Protographs
Universidad Carlos III de Madrid, Spain
We review recent results to analyze the finite-length performance of spatially coupled LDPC Codes over the binary erasure channel (BEC). We will show how these results can be extended to SC-LDPC codes constructed from protographs, for which we will be able to predict the finite-length performance in the waterfall region using a closed-form scaling law. The prediction is based on four main quantities that can be computed/estimated directly from the protograph base matrix. The computation/estimate of such parameters will be discussed. Finally, we will compare the finite-length scaling properties of standard constructions based on coupling regular LDPC codes with recently proposed alternatives such as spatially coupled repeat-accumulate (SC-RA) codes and Spatially Coupled accumulate-repeat-jagged-accumulate (SC-ARJA) codes.
Quantum Spatially-Coupled LDPC Codes
We show in this talk that there is a dramatic improvement of the iterative decoding performances of quantum LDPC codes when using spatially coupled constructions instead. We explain where these improvements come from in the quantum case and illustrate this approach with a construction whose iterative decoding performances allow to operate succesfully at rates very close to an analogue of the Shannon capacity in the quantum case, namely the hashing bound.
Nonbinary Spatially-Coupled LDPC Codes: Threshold Saturation and Performance
Alexandre Graell i Amat
Chalmers University of Technology, Sweden
We analyze nonbinary spatially-coupled low-density parity-check (SC-LDPC) codes built on the general linear group for transmission over the binary erasure channel. We prove threshold saturation of the belief propagation decoding to the potential threshold, by generalizing the proof technique based on potential functions recently introduced by Yedla et al. The existence of the potential function is also discussed for a vector sparse system in the general case, and some existence conditions are developed. We finally give density evolution and simulation results for several nonbinary SC-LDPC code ensembles.
Spatially-Coupled Coded Slotted Aloha
DLR (German Aerospace Center), Germany
In this talk, first the Coded Slotted Aloha (CSA) random access protocol is introduced in its original framed setting. A graph-based representation of the successive interference cancellation process underlying CSA is presented, based on which capacity outer bounds are derived. The graphical representation allows to bridge the interference cancellation analysis to extrinsic information transfer charts for low-density parity-check codes over the binary erasure channel. A spatially coupled version of the scheme is then introduced, showing how its asymptotic performance tightly approaches the capacity outer bound. Threshold saturation is numerically verified by introducing a suitable equivalent of the MAP decoding algorithm for CSA.
Designing Spatially-Coupled LDPC Codes for Nonergodic Channels
Najeeb ul Hassan
Dresden Technical University (TU Dresden), Germany
The mobile-radio channel can be modelled as a slow, flat fading together with additive noise. In many cases, the channel coherence time is much longer than one symbol duration. Thus several symbols are affected by the same fading coefficient. An example of such a channel model is the block-fading channel, where coded information is transmitted over a finite number of fading blocks to provide diversity. It is well known that the convolutional codes are suitable for transmission over block-fading channels and block codes, without a specific structure like root-check, fail to provide any performance guarantee. In this work we exploit the convolutional structure of the spatially coupled LDPC codes and provide a recursive algorithm to generate a family of codes, based on protograph, with increasing code diversity. The results are validated using density evolution and Monte Carlo simulations for the finite length codes.
Sparse Superposition Codes for the Gaussian Channel: Approximate Message Passing Decoder and Spatial Coupling
ENS, Laboratoire de Physique Statistique
We revisit a capacity achieving scheme of error correcting codes over the Gaussian channel, previously introduced by Joseph and Barron. We show that these codes can be iteratively decoded in an efficient way thanks to the approximate message passing algorithm. As in LDPC codes, the decoding by message passing is however not optimal until the capacity. We thus use the spatial coupling technique to saturate the capacity, using a similar approach as the developed for compressed sensing. Finally, we show empirically with simulations, that using structured coding matrices leads to good performances even in relatively small sizes.
Analysis and Design of Finite Alphabet Iterative Decoders Robust to Faulty Hardware
ENSEA-University of Cergy-Pontoise-CNRS, Laboratoire ETIS
In this talk, we address the problem of designing LDPC decoders robust to transient errors introduced by a faulty hardware. Under symmetric error models at a message level, we derive the noisy Density Evolution equations and propose a new interpretation of the functional Density Evolution threshold previously introduced. We show that under restricted decoder noise conditions, the functional threshold can be used to predict the convergence behavior of FAIDs under faulty hardware. In particular, we reveal the existence of robust and non-robust FAIDs and propose a framework for the design of robust decoders. We finally illustrate robust and non-robust decoders behaviors of finite length codes using Monte Carlo simulations.
Protograph-Based LDPC Convolutional Codes for Continuous Phase Modulation
ENSEEIHT, Laboratoire IRIT
The spatial coupling is an efficient technique that improves the threshold of Low Density Parity Check (LDPC) codes. In this paper, we investigate the performance of the serial concatenation of Continuous phase modulation (CPM) and LDPC convolutional codes over a memoryless additive white Gaussian noise channel. We show that coupling protographs optimized for CPM improves their performance and helps designing very good ’small’ protographs. Inspired from convolutional codes and thanks to the inner structure of CPM, we also introduce a new termination without rate loss but that still exhibits a coupling gain and it thus has a very good threshold. We will illustrate the behavior of different LDPC convolutional codes with different termination methods by giving some examples and studying their performance using multidimensional EXIT analysis.