Belief Propagation Decoder With Multiple Bit-Flipping Sets and Stopping Criteria for Polar Codes

Abstract

Compared with successive cancellation list (SCL) decoders, belief propagation (BP)-based decoders suffer performance loss in middle-and high-signal-to-noise ratio (SNR) regions. By analyzing the behavior of the incorrect decoding results of the bit-flipping BP decoder with a critical set of order ω (BFBP-CSω), we found that undetected errors mainly contribute to the error floor. Based on this observation, we proposed a belief propagation decoder with multiple bit-flipping sets (BFSs) and stopping criteria (BP-MF-MC) in this work. We use multiple stopping criteria to identify undetected errors and a small BFS to find an additional estimated codeword given by the bit-flipping BP (BFBP) function. For uncorrected errors, we use multiple BFSs to find estimated codewords with the BFBP function. Furthermore, we propose a method to dynamically generate a BFS based on the submatrix check. This method can remove unnecessary bit-flipping positions and increase the order of the critical set. Then, the best codeword is selected from all estimated codewords according to the maximum likelihood principle. Numerical results show that BP-MF-MC performs similarly to the cyclic redundancy check-aided SCL (CA-SCL) decoder with list size 16 and is slightly worse than CA-SCL with list size 32.

Keywords

• Polar codes
• belief propagation
• bit-flipping
• multiple stopping criteria