arXiv:1712.08538 · IEEE International Symposium on Information Theory (ISIT)

Sparse Graphs for Belief Propagation Decoding of Polar Codes

Sebastian Cammerer, Moustafa Ebada, Ahmed Elkelesh, Stephan ten Brink

Published Jun 1, 2018• 58 citations

Abstract

We describe a novel approach to interpret a polar code as a low-density parity-check (LDPC)-like code with an underlying sparse decoding graph. This sparse graph is based on the encoding factor graph of polar codes and is suitable for conventional belief propagation (BP) decoding. We discuss several pruning techniques based on the check node decoder (CND) and variable node decoder (VND) update equations, significantly reducing the size (i.e., decoding complexity) of the parity-check matrix. As a result, iterative polar decoding can then be conducted on a sparse graph, akin to the traditional well-established LDPC decoding, e.g., using a fully parallel sum-product algorithm (SPA). This facilitates the systematic analysis and design of polar codes using the well-established tools known from analyzing LDPC codes. We show that the proposed iterative polar decoder has a negligible performance loss for short-to-intermediate codelengths compared to Arikan's original BP decoder. Finally, the proposed decoder is shown to benefit from both reduced complexity and reduced memory requirements and, thus, is more suitable for hardware implementations.

DOI: 10.1109/isit.2018.8437581

Related papers

Polar Decoding on Sparse Graphs with Deep Learning

Weihong Xu, Xiaohu You, Chuan Zhang +1 more

In this paper, we present a sparse neural network decoder (SNND) of polar codes based on belief propagation (BP) and deep learning. At first, the conventional factor graph of polar BP decoding is converted to the bipartite Tanner graph similar to low-density parity-check (LDPC) codes. Then the Tanner graph is unfolded and translated into the graphical representation of deep neural network (DNN). The complex sum-product algorithm (SPA) is modified to min-sum (MS) approximation with low complexity. We dramatically reduce the number of weight by using single weight to parameterize the networks. Optimized by the training techniques of deep learning, proposed SNND achieves comparative decoding performance of SPA and obtains about 0.5 dB gain over MS decoding on (128,64) and (256,128) codes. Moreover, 60% complexity reduction is achieved and the decoding latency is significantly lower than the conventional polar BP.

arXiv:1811.09801Asilomar Conference on Signals, Systems and Computers (ACSSC)Oct 1, 201836 citations

Bipartite Belief Propagation Polar Decoding With Bit-Flipping

Zihao Gong, Yifei Shen, Houren Ji +4 more

For the scenarios with high throughput requirements, the belief propagation (BP) decoding is one of the most promising decoding strategies for polar codes. By pruning the redundant variable nodes (VNs) and check nodes (CNs) in the original factor graph, the graph is condensed to a sparse bipartite graph which is similar to the graph for low-density parity-check (LDPC) codes. In this paper, we introduce the bit-flipping scheme into the LDPC-like BP (L-BP) decoding and propose two methods to identify the error-prone VNs. By additional decoding attempts, the L-BP flip (L-BPF) decoding improves the error-rate performance with a similar average complexity for high Eb=N0values. The simulation results show that the L-BPF decoding achieves 0:25 dB gain compared with the L-BP decoding.

IEEE International Conference on Acoustics Speech and Signal ProcessingApr 9, 20204 citations

Improved LDPC-like BPL Decoding Algorithm for Polar Code

Rui Guo, Chenfei Zhang, Chen Lou

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.

KSII Transactions on Internet and Information SystemsJan 31, 20250 citations

Polar Decoding with Schedule Diversity Based on LDPC-like Sparse Graphs

Yen‐Ming Chen, Yong-Jan Yang, Bo-Lun Huang +2 more

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.

IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB)Oct 27, 20204 citations

Belief Propagation-Based Polar Decoders With Schedule Diversity

C S You, Yi‐Hsin Chen, Chen-Wei Hu +2 more

Based on pruning techniques that interpret polar codes as low-density parity-check-like (LDPC-like) codes, this paper develops novel belief propagation (BP)-based decoders utilizing the concept of schedule diversity. By analyzing the impact of hidden variable nodes (VNHs), scheduling algorithms that guarantee fast convergence speeds and superior error performance are devised for the LDPC-like sparse factor graph (SPF), incorporating both standard sequential scheduling (SSS) and informed dynamic scheduling (IDS) algorithms. To further enhance error performance, cyclic redundancy check (CRC) bits are integrated into the LDPC-like SPF, and random update sequences are introduced to reduce computational complexity while implementing schedule diversity. Inspired by belief propagation list decoding, the proposed approaches eventually update messages in the LDPC-like SPF according to various schedules, thereby producing diverse decoding outcomes. Compared to the CRC-aided successive cancellation list (CA-SCL) decoder and benchmark soft-output decoders in the literature, the proposed schemes achieve comparable or improved error performance while reducing computational complexity in the high SNR region. These results serve as preliminary findings on the BP algorithm over LDPC-like SFGs and provide useful insights for the design and practical improvement of polar decoders.

IEEE Transactions on CommunicationsDec 15, 20251 citation

Belief Propagation Decoding for Short-Length Codes Based on Sparse Tanner Graph

Zongyao Li, Yifei Shen, Yuqing Ren +3 more

In this paper, we present a novel approach to improve belief propagation (BP) decoding performance by sparsifying the Tanner graph. Our proposed method first constructs a low-weight parity-check (LWPC) matrix with increased rows based on the original parity-check matrix. Then, all 4-cycles in the LWPC matrix are eliminated by adding auxiliary variable nodes and corresponding parity-check rows, resulting in the generalized LWPC (G-LWPC) matrix. Compared to the original matrix, the sparsity is greatly improved without altering the encoding constraints. Simulation results show that BP decoding based on the G-LWPC matrix is particularly effective for short code lengths. For a (128,20) polar code with 24-bit cyclic redundancy check, our proposed G-LWPC matrix reduces the density from 17.4% to 1.3%, and with 10 iterations, BP decoding can achieve the performance of successive cancellation list decoding with a list size of 32.

IEEE Communications LettersFeb 14, 20248 citations