Slotted ALOHA can benefit from physical-layer network coding (PNC) by decoding one or multiple linear combinations of the packets simultaneously transmitted in a timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original packets of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose the batched BP decoding algorithm that combines belief propagation (BP) and local Gaussian elimination. Compared with pure Gaussian elimination decoding, our algorithm reduces the decoding complexity from cubic to linear function of the number of users. Compared with the ordinary BP decoding algorithm for low-density generator-matrix codes, our algorithm has better performance and the same order of computational complexity. We analyze the performance of the batched BP decoding algorithm by generalizing the tree-based approach and provide an approach to optimize the system performance.

Full version of a conference paper accepted by ITW 2015