This paper considers the algebraic construction and performance of non-binary spatially-coupled low density parity check (LDPC) codes. A replicate-and-mask approach is presented to construct finite-length algebraic quasi-cyclic (QC) spatially-coupled (SC) LDPC codes. Numerical results show the superiority of non-binary algebraic SC QC LDPC codes over the corresponding random non-binary (block and SC) LDPC codes. In this paper, it is demonstrated that the threshold saturation phenomenon, previously demonstrated for binary SC LDPC codes, also holds for non-binary SC LDPC codes over the binary-input AWGN channel with BPSK modulation.

Low-density parity-check (LDPC) convolutional codes (or spatially coupled codes) were recently shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is now called threshold saturation via spatial coupling. This new phenomenon is characterized by the belief-propagation threshold of the spatially coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled scalar recursions. Our approach is based on constructing potential functions for both the coupled and uncoupled recursions. Our results actually show that the fixed point of the coupled recursion is essentially determined by the minimum of the uncoupled potential function and we refer to this phenomenon as Maxwell saturation. A variety of examples are considered including the density-evolution equations for: irregular LDPC codes on the BEC, irregular low-density generator-matrix codes on the BEC, a class of generalized LDPC codes with BCH component codes, the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise, and the compressed sensing of random vectors with independent identically distributed components.

We consider a noisy Slepian-Wolf problem where two correlated sources are separately encoded (using codes of fixed rate) and transmitted over two independent binary memoryless symmetric channels. The capacity of each channel is characterized by a single parameter that is not known at the transmitter. System performance is evaluated by computing the set of channel parameters for which the system can successfully decode. This set is called the achievable channel parameter region (ACPR). The goal is to design systems whose ACPRs are as large as possible. The main result is the design of irregular low-density parity-check (LDPC) ensembles whose ACPRs are significantly larger than previous designs. Some previous attempts to achieve large ACPRs with LDPC codes failed because systematic codes were used. In this work, we start with systematic encoders but puncture all the systematic bits before transmission. We also show that additional gains are possible using a staggered structure which enables codes optimized for single-user channels to perform well under symmetric channel conditions. The main analysis tool is a generic density-evolution framework for the analysis of joint iterative decoding for this problem.

Recently, it has been observed that terminated low-density-parity-check (LDPC) convolutional codes (or spatially-coupled codes) appear to approach the capacity universally across the class of binary memoryless channels. This is facilitated by the “threshold saturation” effect whereby the belief-propagation (BP) threshold of the spatially-coupled ensemble is boosted to the maximum a-posteriori (MAP) threshold of the underlying constituent ensemble. In this paper, we consider spatially-coupled codes over intersymbol-interference (ISI) channels under joint iterative decoding where we empirically show that threshold saturation also occurs. This can be observed by first identifying the GEXIT curve that naturally obeys the general area theorem. From this curve, the corresponding MAP and the BP threshold estimates are then numerically obtained. Given the fact that regular LDPC codes can achieve the symmetric information rate (SIR) under MAP decoding, we conjecture that spatially-coupled codes with joint iterative decoding can universally approach the SIR of ISI channels.

A fundamental connection between the belief propagation (BP) and maximum a posteriori (MAP) decoding thresholds was derived by Méasson, Montanari, and Urbanke using the area theorem for extrinsic information transfer (EXIT) curves. This connection allows the MAP threshold, for the binary erasure channel, to be evaluated efficiently via an upper bound that can be shown to be tight in some cases. In this paper, a similar analysis is used to extend these results to several multiuser systems, namely a noisy Slepian-Wolf problem and a multiple-access channel with erasures. The simplicity of these channel models allows for rigorous analysis and enables the derivation of upper bounds on the MAP thresholds using EXIT area theorems. In some cases, one can also show these bounds are tight. One interesting application is that the MAP thresholds can be compared with the BP thresholds of spatially-coupled codes to verify threshold saturation for the corresponding systems.

Convolutional low-density parity-check (LDPC) codes (or spatially-coupled codes) have now been shown to achieve capacity on binary-input memoryless symmetric channels. The principle behind this surprising result is the threshold-saturation phenomenon, which is defined by the belief-propagation threshold of the spatially-coupled ensemble saturating to a fundamental threshold defined by the uncoupled system. Previously, the authors demonstrated that potential functions can be used to provide a simple proof of threshold saturation for coupled scalar recursions. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled vector recursions. The conditions of the theorem are verified for the density-evolution equations of: (i) joint decoding of irregular LDPC codes for a Slepian-Wolf problem with erasures, (ii) joint decoding of irregular LDPC codes on an erasure multiple-access channel, and (iii) admissible protograph codes on the BEC. This proves threshold saturation for these systems.

We consider a noisy Slepian-Wolf problem where two correlated sources are separately encoded and transmitted over two independent binary memoryless symmetric channels. Each channel capacity is assumed to be characterized by a single parameter which is not known at the transmitter. The receiver has knowledge of both the source correlation and the channel parameters. We call a system universal if it retains near-capacity performance without channel knowledge at the transmitter. Kudekar et al. recently showed that terminated low-density parity-check (LDPC) convolutional codes (a.k.a. spatially-coupled LDPC ensembles) can have belief-propagation thresholds that approach their maximum a-posteriori thresholds. This was proven for binary erasure channels and shown empirically for binary memoryless symmetric channels. They also conjectured that the principle of spatial coupling is very general and the phenomenon of threshold saturation applies to a very broad class of graphical models. In this work, we derive an area theorem for the joint decoder and empirically show that threshold saturation occurs for this problem. As a result, we demonstrate near-universal performance for this problem using the proposed spatially-coupled coding system. A similar result is also discussed briefly for the 2-user multiple-access channel.