Sparse Superposition Codes with Binomial Dictionary are Capacity-Achieving with Maximum Likelihood Decoding

It is known that sparse superposition codes asymptotically achieve the channel capacity over the additive white Gaussian noise (AWGN) channel with both maximum likelihood decoding and computationally efficient decoding (Joseph and Barron, 2012, 2014). Their codewords are superpositions of random vectors, the list of which is called a dictionary, and the capacity-achieving property is proved provided the entries of the dictionary are drawn from a Gaussian distribution. This design is theoretically well motivated, but quantization of the dictionary is required for implementation on real devices. Takeishi et al. (2014, 2019) demonstrated that these codes can also asymptotically achieve the channel capacity with maximum likelihood decoding when the dictionary is drawn from a Bernoulli distribution. In this paper, we extend this result to the case of binomial distributions and show that, for any fixed number of trials, the channel capacity is achieved as the codelength goes to infinity. We also derive a finite-length upper bound on the decoding error probability and quantify the additional penalty term due to the discreteness of the dictionary. Numerical computations examine the trade-off between the value of the derived upper bound and the number of trials in the binomial distribution.