  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.
