SC List-Flip Decoding of Polar Codes by Shifted Pruning: A General Approach

Abstract

In the successive cancellation (SC) list decoding, the tree pruning operation retains the L best paths with respect to a metric at every decoding step. However, the correct path might be among the L worst paths due to the imposed penalties. In this case, the correct path is pruned and the decoding process fails. shifted pruning (SP) scheme can recover the correct path by additional decoding attempts when decoding fails, in which the pruning window is shifted by κ≤L paths over certain bit positions. A special case of the shifted pruning scheme where κ=L is known as SCL-flip decoding, which was independently proposed in 2019. In this work, a new metric that performs better in particular for medium and long codes is proposed, and nested shift-pruning schemes are suggested for improving the average complexity.

Keywords

• polar codes
• successive cancellation
• list decoding
• tree pruning
• shifted pruning
• segmented decoding