SigSag: Iterative detection through soft message-passing

Abstract—The multiple-access framework of ZigZag decoding (Gollakota and Katabi 2008) is a useful technique for combating interference via multiple repeated transmissions, and is known to be compatible with distributed random access protocols. How-ever, in the presence of noise this type of decoding can magnify errors, particularly when packet sizes are large. We show that ZigZag decoding can be seen as an instance of belief propagation in the high-SNR limit. Building on this observation, we present a simple soft-decoding version, called SigSag, that improves performance. We show that for two users, collisions result in a cycle-free factor graph that can be optimally decoded via belief propagation. For collisions between more than two users, we show that if a simple bit-permutation is used then the graph is locally tree-like with high probability, and hence belief propagation is near-optimal. Further, we introduce the joint channel-collision decoding which decodes the collided packets while the packets are coded by an LDPC code. Through simulations we show that our scheme performs better than coordinated collision-free time division multiple access (TDMA) and the ZigZag decoder. Furthermore, we investigate the performance of the joint channel-collision decoder in different scenarios and show that it performs better than TDMA and ZigZag decoder accompanied by sum-product decoding. EDICS: SPC-DETC, WIN-CONT. I