How to construct an effective polar decoding scheme has attracted researchers in the field of communication. The belief propagation list (BPL) decoder has performance improvement over the traditional BP decoder but comes with much higher complexity. To solve the issue of high complexity & latency, a low-density parity-check (LDPC) like BP decoder was proposed but it suffered from performance degradation over the original BP decoder. In this letter, a BP-based sparse graph list (BP-SGL) decoder is proposed by leveraging both list decoding scheme and LDPC-like BP decoding algorithm to achieve performance improvement while maintaining low complexity & latency. The key idea of the proposed list generation method is the similarity comparison of decoding graphs. Testing results verify that selecting graphs with large structural differences helps to construct a list with good overall performance. Simulation results show that the proposed scheme is superior to LDPC-like BP, and even outperforms the original BPL and some state-of-the-art (SOTA) BP-based decoding algorithms with significant reduction in complexity & latency.
How to construct an effective polar decoding scheme has attracted researchers in the field of communication. The belief propagation list (BPL) decoder has performance improvement over the traditional BP decoder but comes with much higher complexity. To solve the issue of high complexity & latency, a low-density parity-check (LDPC) like BP decoder was proposed but it suffered from performance degradation over the original BP decoder. In this letter, a BP-based sparse graph list (BP-SGL) decoder is proposed by leveraging both list decoding scheme and LDPC-like BP decoding algorithm to achieve performance improvement while maintaining low complexity & latency. The key idea of the proposed list generation method is the similarity comparison of decoding graphs. Testing results verify that selecting graphs with large structural differences helps to construct a list with good overall performance. Simulation results show that the proposed scheme is superior to LDPC-like BP, and even outperforms the original BPL and some state-of-the-art (SOTA) BP-based decoding algorithms with significant reduction in complexity & latency.
To improve the performance of BP decoding for polar codes, researchers have developed a Belief Propagation List (BPL) decoding algorithm by executing multiple BP decoders in parallel.This algorithm outperforms traditional BP decoding based on single graph decoding, although it sacrifices some complexity and delay.Unlike this basic Polar-BPL decoding mentioned above, a low-density parity check like (LDPC-like) BPL decoding algorithm has been introduced into polar codes.This algorithm performs more efficient BP decoding iterations on sparse graphs.To further reduce the complexity and delay of LDPC-like BPL, and avoid analyzing all sparse graphs, this article proposes an improved LDPC-like BPL (ILDPC-like BPL) decoding algorithm based on selecting factor graphs.This algorithm analyzes differences in permuted factor graphs and selects these graphs with non-convergent decoding results to form a decoding list, allowing decoding to be completed with fewer graphs traversed and iterations, thereby reducing complexity and delay.On this basis, to improve the reliability of this algorithm, this article further adds a path metric (PM) mechanism, which can dynamically evaluate different sparse graphs' results in parallel decoding.The simulation results show that compared with LDPC-like BPL (random scheme), ILDPC-like BPL improves decoding performance while reducing decoding delay and complexity; Compared with basic Polar-BPL (cycle-shift scheme), this algorithm greatly reduces decoding delay and complexity while achieving similar performance.
In this paper, based on the technique of LDPC (low-density parity-check)-like sparse graphs for the Polar codes, we propose a Polar decoding method which provides the schedule diversity. The investigated decoding schedules outperforms Arikan's belief propagation (BP) algorithm performed on the original encoding factor graph. Secondly, based on both the layered BP (LBP) and the modified node-wise residual BP (NW-RBP) schedules, we are able produce several sequential decoding schedules that are executed in serial. It is shown through simulations that when compared to the successive cancellation list (SCL) decoding, the proposed scheme achieves a lower complexity level, while a gap of 0.2 dB still exists in BER performance in the high-SNR region. However, the enhanced BP-based decoding method provides a flexible decoding latency, and is able to generate soft-in/soft-out information, which makes it suitable for the schemes which perform iterative decoding and detection processes.
This paper presents a general decoder architecture for 5G LDPC and polar codes. To achieve the hardware reuse maximization, both LDPC and polar codes are decoded by belief propagation (BP) algorithm on sparse bipartite graphs. However, by counting the number of short cycles on the polar bipartite graphs, we observe that numerous short cycles cause the poor performance than conventional decoding algorithms, like successive cancellation (SC) and BP decoding. To reduce the impact of short cycles, a LDPC-like BP list (BPL) decoding algorithm is proposed for polar codes, which is applied on L different polar bipartite graphs constructed by different permuted polar factor graphs. Finally, the simulation shows that the proposed general decoder for polar codes can obtain beyond SC and BP error performance with lower decoding latency and computational complexity, and even near successive cancellation list (SCL) performance in high signal-noise ratios (SNRs).
We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.
Owing to its high parallelism, belief propagation (BP) decoding is highly amenable to high-throughput implementations and thus represents a promising solution for meeting the ultra-high peak data rate of future communication systems. However, for polar codes, the error-correcting performance of BP decoding is far inferior to that of the 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 for BPL decoding that supports various PFGs and code configurations presents a big challenge. 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 graph 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 rate of one-half, our BPL decoder with 32 PFGs has a similar error-correcting performance to SCL with a list size of 4 and achieves a throughput of 25.63 Gbps and an area efficiency of 29.46 Gbps/mm2 at SNR=4.0dB, which is 1.82× and 4.33× faster than the state-of-the-art BP flip and SCL decoders,~respectively
Due to its high parallelism, belief propagation (BP) decoding is amenable to high-throughput applications and thus represents a promising solution for the ultra-high peak data rate required by future communication systems. To bridge the performance gap compared to the widely used successive cancellation list (SCL) decoding algorithm, BP list (BPL) decoding for polar codes extends candidate codeword exploration via multiple permuted factor graphs (PFGs) to improve the error-correcting performance of BP decoding. However, it is a significant challenge to design a unified and flexible BPL hardware architecture that supports various PFGs and code configurations. In this paper, we present the first VLSI implementation of a BPL decoder for polar codes that overcomes this implementation challenge with a hardware-friendly algorithm for on-the-fly flexible permutations. First, we introduce a sequential generation (SG) algorithm to obtain a near-optimal PFG set. Additionally, we demonstrate that any permutation can be decomposed into a combination of multiple fixed routings, and design a low-complexity permutation network to generate graphs in an on-the-fly fashion. Our BPL decoder has a low decoding latency by executing decoding and permutation generation in parallel and supports arbitrary list sizes without area overhead. Experimental results based on 28nm FD-SOI technology show that for length-1024 polar codes with a code rate of one-half, our BPL decoder with 32 PFGs exhibits similar error-correcting performance to SCL with a list size of 4 and achieves an average throughput of 25.63 Gbps and an area efficiency of 29.46 Gbps/mm2, which is 1.82× and 4.33× faster than the state-of-the-art BP flip and SCL decoders, respectively