Sparse Graph Codes for the 2-User Unsourced MAC
Alexander Fengler, Gianluigi Liva, Yury Polyanskiy · 2022
We study the design of low-density parity check (LDPC) codes for the 2-user binary adder channel (BAC) in the unsourced setting. That is, both users employ the same code. We show that classic design criteria for LDPC codes do not capture the special requirements needed to deal with the interference in an unsourced BAC (UBAC). Instead, we give a graph theoretic analysis that allows to calculate the expected fraction of good pivots for any LDPC ensemble with a given degree distribution pair. A good pivot is a variable node associated with a received “erasure” symbol for which revealing its value allows to recover both transmitted messages up to a vanishing small fraction of residual erasures by simple BP decoding. The analysis of the expected fraction of good pivots reveals a surprising connection between graph theory and density evolution which can be used to compute optimized degree distributions. Results over the 2-user UBAC with additive white Gaussian noise are also provided, and the implications of the presence of noise are discussed. Finally, provide a simple multi-edge type LDPC code construction that can provably achieve the 2-user UBAC limit for linear codes.