We study the approximate message-passing decoder for sparse superposition coding on the additive white Gaussian noise channel and extend our preliminary work. We use heuristic statistical-physics-based tools, such as the cavity and the replica methods, for the statistical analysis of the scheme. While superposition codes asymptotically reach the Shannon capacity, we show that our iterative decoder is limited by a phase transition similar to the one that happens in low density parity check codes. We consider two solutions to this problem, that both allow to reach the Shannon capacity: 1) a power allocation strategy and 2) the use of spatial coupling, a novelty for these codes that appears to be promising. We present, in particular, simulations, suggesting that spatial coupling is more robust and allows for better reconstruction at finite code lengths. Finally, we show empirically that the use of a fast Hadamard-based operator allows for an efficient reconstruction, both in terms of computational time and memory, and the ability to deal with very large messages.
The phenomenology of these codes under AMP decoding, in particular the sharp phase transitions different between MAP and AMP decoding, has many similarities with what appears in low density parity check codes (LDPC) @cite_18 . It is actually in the context of LDPC codes that spatial coupling has been introduced @cite_32 @cite_5 in order to deal with this phase transition phenomenon that blocks the convergence of low-complexity message-passing based decoders. These similarities are not a priori trivial because LDPC codes are codes over finite fields, the sparse superposition codes work in the continuous framework. Furthermore LDPC codes are decoded by loopy belief-propagation (BP) whereas sparse superposition codes are decoded by AMP which is a Gaussian approximation of loopy BP. However, they arise due to a deep connection to compressed sensing, where these phenomena (phase transition, spatial coupling, etc) have been studied as well @cite_23 @cite_24 @cite_38 @cite_15 and we shall make use of this connection extensively.
@cite_38 @cite_18 @cite_32 @cite_24 @cite_23 @cite_5 @cite_15
2952440034 2118473837 1577660440 1909826856
Recently, it was observed that spatially-coupled LDPC code ensembles approach the Shannon capacity for a class of binary-input memoryless symmetric (BMS) channels. The fundamental reason for this was attributed to a "threshold saturation" phenomena derived by Kudekar, Richardson and Urbanke. In particular, it was shown that the belief propagation (BP) threshold of the spatially coupled codes is equal to the maximum a posteriori (MAP) decoding threshold of the underlying constituent codes. In this sense, the BP threshold is saturated to its maximum value. Moreover, it has been empirically observed that the same phenomena also occurs when transmitting over more general classes of BMS channels. In this paper, we show that the effect of spatial coupling is not restricted to the realm of channel coding. The effect of coupling also manifests itself in compressed sensing. Specifically, we show that spatially-coupled measurement matrices have an improved sparsity to sampling threshold for reconstruction algorithms based on verification decoding. For BP-based reconstruction algorithms, this phenomenon is also tested empirically via simulation. At the block lengths accessible via simulation, the effect is quite small and it seems that spatial coupling is not providing the gains one might expect. Based on the threshold analysis, however, we believe this warrants further study. Recently, it was observed that spatially-coupled LDPC code ensembles approach the Shannon capacity for a class of binary-input memoryless symmetric (BMS) channels. The fundamental reason for this was attributed to a threshold saturation phenomena derived in [1]. In particular, it was shown that the belief propagation (BP) threshold of the spatially coupled codes is equal to the maximum a posteriori (MAP) decoding threshold of the underlying constituent codes. In this sense, the BP threshold is saturated to its maximum value. Moreover, it has been empirically observed that the same phenomena also occurs when transmitting over more general classes of BMS channels. In this paper, we show that the effect of spatial coupling is not restricted to the realm of channel coding. The effect of coupling also manifests itself in compressed sensing. Specifically, we show that spatially-coupled measurement matrices have an improved sparsity to sampling threshold for reconstruction algorithms based on verification decoding. For BP-based reconstruction algorithms, this phenomenon is also tested empirically via simulation. At the block lengths accesible via simulation, the effect is rather small but, based on the threshold analysis, we believe this warrants further study. Several combinatorial properties of low-density parity-check (LDPC) codes, such as minimum distance, diameter, stopping number, girth and cycle-length distribution of the corresponding Tanner graph, are known to influence their performance under iterative decoding. Recently, a new class of combinatorial configurations, termed trapping sets, was shown to be of significant importance in determining the properties of LDPC codes in the error-floor region. Very little is known both about the existence parameters of trapping sets in structured LDPC codes and about possible techniques for reducing their negative influence on the code's performance. In this paper, we address both these problems from an algorithmic and combinatorial perspective. We first provide a numerical study of the trapping phenomena for the Margulis code, which exhibits a fairly high error-floor. Based on this analysis, conducted for two different implementations of iterative belief propagation, we propose a novel decoding process, termed averaged decoding. Averaged decoding provides for a significant reduction in the number of incorrectly decoded frames in the error-floor region of the Margulis code. Furthermore, based on the results of the algorithmic approach, we suggest a novel combinatorial characterizations of trapping sets in the class of LDPC codes based on finite geometries. Projective geometry LDPC codes are suspected to have extremely low error-floors, which is a property that we may attribute to the non-existence of certain small trapping sets in the code graph. We study the approximate message-passing decoder for sparse superposition coding on the additive white Gaussian noise channel and extend our preliminary work. We use heuristic statistical-physics-based tools, such as the cavity and the replica methods, for the statistical analysis of the scheme. While superposition codes asymptotically reach the Shannon capacity, we show that our iterative decoder is limited by a phase transition similar to the one that happens in low density parity check codes. We consider two solutions to this problem, that both allow to reach the Shannon capacity: 1) a power allocation strategy and 2) the use of spatial coupling, a novelty for these codes that appears to be promising. We present, in particular, simulations, suggesting that spatial coupling is more robust and allows for better reconstruction at finite code lengths. Finally, we show empirically that the use of a fast Hadamard-based operator allows for an efficient reconstruction, both in terms of computational time and memory, and the ability to deal with very large messages.