Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the additive white Gaussian noise (AWGN) channel at rates approaching the channel capacity. The codebook is defined in terms of a Gaussian design matrix, and codewords are sparse linear combinations of columns of the matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes, whose decoding complexity scales linearly with the size of the design matrix. The performance of the decoder is rigorously analyzed and it is shown to asymptotically achieve the AWGN capacity with an appropriate power allocation. Simulation results are provided to demonstrate the performance of the decoder at finite blocklengths. We introduce a power allocation scheme to improve the empirical performance, and demonstrate how the decoding complexity can be significantly reduced by using Hadamard design matrices.
The adaptive successive decoder of Joseph-Barron @cite_7 and the iterative soft-decision decoder of Cho-Barron @cite_21 @cite_4 both have probability of error that decays as @math for any fixed rate @math , but the latter has better empirical performance. Theorem shows that the probability of error for the AMP decoder goes to zero for all @math , but does not give a rate of decay; hence we cannot theoretically compare its performance with the Cho-Barron decoder in @cite_4 . We can, however, compare the two decoders qualitatively.
@cite_21 @cite_4 @cite_7
2092639489 1485005937 2100540720 2039957496
Recently sparse superposition codes with iterative term selection have been developed which are mathematically proven to be fast and reliable at any rate below the capacity for the additive white Gaussian noise channel with power control. We improve the performance using a soft decision decoder with Bayes optimal statistics at each iteration, followed by thresholding only at the final step. This presentation includes formulation of the statistics, proof of their distributions, numerical simulations of the performance improvement, and useful identities relating a squared error risk to a posterior probability of error. In this paper, we consider the problem of min- imizing the multicast decoding delay of generalized instantly decodable network coding (G-IDNC) over persistent forward and feedback erasure channels with feedback intermittence. In such an environment, the sender does not always receive acknowledgement from the receivers after each transmission. Moreover, both the forward and feedback channels are subject to persistent erasures, which can be modelled by a two state (good and bad states) Markov chain known as Gilbert-Elliott channel (GEC). Due to such feedback imperfections, the sender is unable to determine subsequent instantly decodable packets combination for all receivers. Given this harsh channel and feedback model, we first derive expressions for the probability distributions of decoding delay increments and then employ these expressions in formulating the minimum decoding problem in such environment as a maximum weight clique problem in the G-IDNC graph. We also show that the problem formulations in simpler channel and feedback models are special cases of our generalized formulation. Since this problem is NP-hard, we design a greedy algorithm to solve it and compare it to blind approaches proposed in literature. Through extensive simulations, our adaptive algorithm is shown to outperform the blind approaches in all situations and to achieve significant improvement in the decoding delay, especially when the channel is highly persistent. Index Terms—Multicast Channels, Persistent Erasure Chan- nels, G-IDNC, Decoding Delay, Lossy Intermittent Feedback, Maximum Weight Clique Problem. The fixed slope lossy algorithm derived from the kth-order adaptive arithmetic codeword length function is extended to finite-state decoders or trellis-structured decoders. When this algorithm is used to encode a stationary, ergodic source with a continuous alphabet, the Lagrangian performance converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of auxiliary random variables and reproduction levels, where spl lambda >0 and - spl lambda are designated to be the slope of the rate distortion function R(D) of the source at some D; the quantity is close to R(D)+ spl lambda D when the order k used in the arithmetic coding or the number of states in the decoders is large enough, An alternating minimization algorithm for computing the quantity is presented; this algorithm is based on a training sequence and in turn gives rise to a design algorithm for variable-rate trellis source codes. The resulting variable-rate trellis source codes are very efficient in low-rate regions. With k=8, the mean-squared error encoding performance at the rate 1 2 bits sample for memoryless Gaussian sources is comparable to that afforded by trellis-coded quantizers; with k=8 and the number of states in the decoder=32, the mean-squared error encoding performance at the rate 1 2 bits sample for memoryless Laplacian sources is about 1 dB better than that afforded by the trellis-coded quantizers with 256 states, with k=8 and the number of states in the decoder=256, the mean-squared error encoding performance at the rates of a fraction of 1 bit sample for highly dependent Gauss-Markov sources with correlation coefficient 0.9 is within about 0.6 dB of the distortion rate function. For the additive white Gaussian noise channel with average codeword power constraint, sparse superposition codes are developed. These codes are based on the statistical high-dimensional regression framework. In a previous paper, we investigated decoding using the optimal maximum-likelihood decoding scheme. Here, a fast decoding algorithm, called the adaptive successive decoder, is developed. For any rate R less than the capacity C, communication is shown to be reliable with nearly exponentially small error probability. Specifically, for blocklength n, it is shown that the error probability is exponentially small in n logn.