Permutation-based Decoding of Reed-Muller Codes in Binary Erasure Channel

In this paper, we consider the problem of decoding Reed-Muller (RM) codes in binary erasure channel. We propose a novel algorithm, which exploits several techniques, such as list recursive (successive cancellation) decoding based on Plotkin decomposition, permutations of encoding factor graph as well as the properties of erasure channels. We show that with properly selected number of random permutations, this algorithm considerably outperforms straight-forward list decoding while maintaining the same asymptotic complexity. This also means that near-MAP decoding can be achieved with lower complexity cost.