High-Throughput Flexible Belief Propagation List Decoder for Polar Codes

Due to its high parallelism, belief propagation (BP) decoding can be implemented with high throughput and is a promising solution to meet the ultra-high peak date rate requirement of future communication systems. However, for polar codes, the error-correcting performance of BP decoding is far inferior to that of widely used CRC-aided successive cancellation list (SCL) decoding algorithm. To close the performance gap to SCL, BP list (BPL) decoding expands the exploration of candidate codewords through multiple permuted factor graphs (PFGs). From an implementation perspective, designing a unified and flexible hardware architecture of BPL decoding that supports different PFGs and various code configurations is challenging. In this paper, we propose the first hardware implementation of a BPL decoder for polar codes and overcome the implementation challenge by applying a hardware-friendly algorithm that generates flexible permutations on the fly. First, we derive the permutation selection gain and provide a sequential generation (SG) algorithm to obtain a near-optimal PFG set. We further prove that any permutation can be decomposed into a combination of multiple fixed routings, and we design a low-complexity permutation network to satisfy the decoding schedule. Our BPL decoder not only has a low decoding latency by executing the decoding and permutation generation in parallel, but also supports an arbitrary list size without any area overhead. Experimental results show that, for length-${1024}$ polar codes with a code of one-half, our BPL decoder with a list size ${\mathbb{L}=32}$ has a similar error-correcting performance to SCL with ${\mathbb{L}=4}$ and achieves a throughput of ${25.63}$ Gbps and an area efficiency of ${29.46}$ Gbps/mm${^2}$ at SNR ${=4.0}$ dB, which is $1.99\times$ and $7.08\times$ faster than the state-of-the-art BP flip and SCL decoders, respectively.