Asia-Pacific Conference on Communications (APCC)

Shuffled BP decoding for punctured LDPC codes

Sangjoon Park, Sunyoung Lee, Keum-Chan Whang

Published Oct 1, 2008• 2 citations

Abstract

In this paper, we propose a scheduling method of the shuffled BP decoding algorithm for punctured LDPC codes. The number of iteration required to recover whole punctured variable nodes in the standard BP decoding algorithm is increased with the number of punctured variable nodes. However, only one number of iteration is required in the proposed shuffled BP scheduling regardless of the puncturing algorithm and the number of punctured variable nodes. Furthermore, the proposed shuffled BP scheduling can improve the reliability of the unpunctured variable nodes at the 1st iteration, while impossible in the layered BP scheduling if there are no check nodes that only unpunctured variable nodes participate. Simulation results verify that the proposed shuffled BP scheduling has comparable performance to the layered BP scheduling in spite of its smaller number of scheduling group at rate below 0.9.

Related papers

A Group Shuffled BP decoding for punctured Low-Density Parity-Check codes

Sangjoon Park, Sunyoung Lee, Seung‐Hoon Hwang +1 more

A group shuffled belief propagation (GSBP) decoding for punctured low-density parity-check (LDPC) codes is proposed in the paper. The proposed GSBP decoding schedules the updating order of each bit node according to its recovery order in the standard BP decoding. This enables the proposed decoding to recover all punctured nodes in the first iteration with the minimum required number of groups. Calculation of the number of effective updates, which indicates the number of nonzero check-to-bit messages, shows that the proposed decoding can achieve faster decoding convergence than the layered BP (LBP) decoding for rate-compatible punctured LDPC (RCP-LDPC) codes. In the simulation results, the maximum SNR gain of the proposed decoding over the LBP decoding is about 0.9dB at the FER of 10-4.

IEICE Electronics ExpressJan 1, 20101 citation

Layered BP Decoding for Rate-Compatible Punctured LDPC Codes

Jeongseok Ha, Demijan Klinc, Jini Kwon +1 more

Rate-compatible punctured LDPC codes have shown to perform well over a wide variety of code rates, both theoretically and practically. However it has been reported that the belief propagation (BP) decoding for these codes converges slower than for unpunctured codes. Layered BP algorithm is a modified BP algorithm that accelerates the decoding convergence by means of sequential scheduling of check node updates. In this letter, we propose an efficient scheduling of check node updates for rate-compatible punctured LDPC codes that performs well. We show that the convergence speed of the proposed scheduling outperforms conventional (random) scheduling and conventional BP decoding. Performance improvements become more distinctive with the growing fraction of punctured bits

IEEE Communications LettersMay 1, 200722 citations

An efficient scheduling scheme for layered belief propagation decoding of regular LDPC codes

Hua Li, Hong Wei Ding, Linhua Zheng +3 more

Schedule plays an important role in layered belief propagation (BP) decoding of low-density parity-check (LDPC) codes. It affects the error-rate performance as well as convergence rate of the decoder. In this paper, an efficient scheduling scheme is proposed to arrange the updating order of check nodes for layered BP decoder of regular LDPC codes. This scheme selects check node one at a time based on the reliability of the variable nodes. Specifically each time the check node with maximum number of low-reliability neighbors is selected. For simplicity, we introduce the updating state instead of the real-time messages to represent variable-node reliability. Simulation results on regular LDPC codes prove that the proposed scheduling scheme can obtain efficient schedules with fast convergence and good error-rate performance.

International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)Oct 1, 20166 citations

Informed Fixed Scheduling for Faster Convergence of Shuffled Belief-Propagation Decoding

Chaudhry Adnan Aslam, Yong Liang Guan, Kui Cai +1 more

A novel informed fixed scheduling (IFS) scheme for shuffled belief-propagation (BP) decoding of binary low-density parity-check (LDPC) code is introduced to improve the BP decoding convergence. The IFS finds an appropriate order of variable nodes in accordance with the number of updated neighbors in the code graph, ensuring that the maximum number of latest message updates is utilized within a single iteration. This allows the utilization of most reliable message updates in a timely manner, leading to faster error-rate convergence. Simulation results show that the proposed IFS scheme improves the convergence speed of BP decoder by up to 20% for regular LDPC codes and 45% for irregular LDPC codes, without affecting the error-rate performance, at medium-to-high signal-to-noise ratio over binary-input additive white Gaussian noise channel.

IEEE Communications LettersOct 13, 201622 citations

A Method for Grouping Symbol Nodes of Group Shuffled BP Decoding Algorithm

Y. Sato, Gou Hosoya, Hideki Yagi +1 more

In this paper, we propose a method for enhancing performance of a sequential version of the belief-propagation (BP) decoding algorithm, the group shuffled BP decoding algorithm for low-density parity-check (LDPC) codes. An improved BP decoding algorithm, called the shuffled BP decoding algorithm, decodes each symbol node in serial at each iteration. To reduce the decoding delay of the shuffled BP decoding algorithm, the group shuffled BP decoding algorithm divides all symbol nodes into several groups. In contrast to the original group shuffled BP, which automatically generates groups according to symbol positions, in this paper we propose a method for grouping symbol nodes which generates groups according to the structure of a Tanner graph of the codes. The proposed method can accelerate the convergence of the group shuffled BP algorithm and obtain a lower error rate in a small number of iterations. We show by simulation results that the decoding performance of the proposed method is improved compared with those of the shuffled BP decoding algorithm and the group shuffled BP decoding algorithm.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesOct 1, 20081 citation

An Overlapped Shuffled-BP LDPC Decoding Algorithm

Ya’nan Fan, Yao Xiujuan

Shuffled-BP (SBP) decoding algorithm is a variable-node-based serial decoding algorithm, which converges faster than the original Belief-Propagation (BP) decoding algorithm. However, due to the semi-parallel processing, there is a decrease in terms of convergence speed and error performance. An Overlapped Shuffled-BP(OSBP) decoding algorithm is proposed to enhance further the performance of the Shuffled-BP algorithm. In this algorithm, more than one sub-decoders are used to execute simultaneously, every sub-decoder has different updating order from each other. Regarding each variable node, the most reliable messages are kept and used for the next iteration, thus a faster convergence can be provided. Both theoretical analysis and simulation results show that, compared with SBP algorithm, OSBP algorithm possesses a better error performance as well as a higher convergence speed and introduces no extra storage requirement. Moreover, the proposed algorithm is effective for both regular and irregular LDPC codes.

Jan 1, 20161 citation