A BP decoding algorithm for polar codes based on task graph reconstruction

Polar codes have become prevalent in the fifth-generation mobile communication technology (5G) owing to their capacity characteristics and straightforward compilation. The belief propagation (BP) decoding algorithm, which demonstrates parallel execution and a high throughput rate, is a commonly employed polar code decoding algorithm. This paper proposes a BP decoding algorithm based on task graph reconstruction (TGR) to reduce the algorithm's decoding complexity and delay. Using graph equivalence relations, the decoding algorithm is structurally optimized in two steps. Firstly, the redundancy elimination algorithm is used to remove the redundant calculations in the BP decoding algorithm and simplify the algorithm's operation structure. Subsequently, the branch transformation algorithm is used to optimize the operation order and reduce the critical path delay. The suggested BP algorithm has a better overall performance, particularly in application scenarios with sensitive delay and harsh channel conditions, than the three BP decoding algorithms that aim for structural optimization. It can reduce the critical path delay by at least 2.3%, reduce the computational complexity by at least 4.2%, and virtually eliminate the loss of error correction performance.