IEICE Transactions on Communications

Fast Decoding Algorithm for Low-Density Parity-Check Codes

Dan Wang

Published Nov 1, 2005• 1 citation

Abstract

A fast decoding algorithm for low-density parity-check codes is presented based on graph decomposition and two-way message passing schedule. Simulations show that the convergence speed of the proposed algorithm is about twice that of the conventional belief propagation algorithm.

DOI: 10.1093/ietcom/e88-b.11.4368

Related papers

Fast Decoding Algorithm for Low-Density Parity-Check Codes

Wang Dan, Li Ping, Hu Yu +1 more

A fast decoding algorithm for low-density parity-check codes is presented based on graph decomposition and two-way message passing schedule. Simulations show that the convergence speed of the proposed algorithm is about twice as fast as that of the conventional belief propagation algorithm.

IEEE International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless CommunicationsApr 28, 20060 citations

An efficient message-passing schedule for LDPC decoding

E. Sharon, Simon N. Litsyn, Jacob Goldberger

An efficient decoding schedule for low-density parity-check (LDPC) codes that outperforms the conventional approach, in terms of both complexity and performance, is presented. Conventionally, in each iteration, all symbol nodes and, subsequently, all the check nodes, send messages to their neighbors ("flooding schedule"). In contrast, in the proposed method, the updating of nodes is performed according to a serial schedule which propagates the information twice as fast. A density evolution (DE) algorithm for asymptotic analysis of the new schedule is derived, showing that, when working near the code's capacity, the decoder converges in approximately half the number of iterations. In addition, a concentration theorem is proved, showing that, for a randomly chosen serial schedule, code graph, and decoder input, the decoder's performance approaches its expected one as predicted by the DE algorithm, when the code length increases.

IEEE Convention of Electrical and Electronics Engineers in IsraelNov 30, 2004125 citations

A fast convergence decoding algorithm for LDPC codes

Xinmei Wang

A realization of belief propagation algorithms based on the two-way schedule and a serial concatenated decoding algorithm for LDPC codes based on the matrix decomposition are presented. The performance of this new algorithm is systematically analyzed via the density evolution theory. Analysis and simulation results show that the serial concatenated decoding algorithm demonstrates a higher convergence speed and has as good performance as the conventional belief propagation algorithm.

Journal of Xidian UniversityJan 1, 20050 citations

Low-density parity-check codes with 2-state trellis decoding

Mao‐Ching Chiu

A class of low-density parity-check (LDPC) codes with a simple 2-state trellis structure is presented. For LDPC decoding, the conventional belief propagation (BP) algorithm consists of numerous sub-decoders of single-parity check codes and exchanges information between sub-decoders in an iterative manner. If the single-parity check codes can be constructed and grouped in a proper way, the decoder can be decomposed into few identical 2-state trellis decoders. Therefore, instead of numerous sub-decoders of single-parity check codes, an iterative decoding algorithm based on few sub-decoders over 2-state trellis is proposed. The proposed decoding algorithm improves the efficiency of message passing between sub-decoders and hence provides a fast convergent rate as compared to the standard BP algorithm. Simulation results show that the proposed scheme provides a better performance and a fast convergent rate as compared to those of standard BP algorithm. The result also shows that the proposed algorithm has a similar performance as that of asynchronous replica shuffled BP algorithm and has a slightly inferior performance than that of synchronous replica shuffled BP algorithm. However, complexity analysis shows that our proposed algorithm has complexity that is lower than that of the replica shuffled BP algorithm.

IEEE Transactions on CommunicationsJan 1, 20092 citations

Fast convergence algorithm for decoding of low density parity check codes

Jin Xie, Liuguo Yin, Ning Ge +1 more

Abstract: In this paper, a fast-convergence algorithm is proposed for the decoding of low-density parity-check (LDPC) codes. By putting more weight on the message update from check node to variable node in current iteration, the proposed method speeds up the decoding significantly. Simulation results show that compared with the standard layered min-sum decoding algorithm, the proposed scheme may reduce about 1/6 iteration numbers for LDPC codes used in DVB-S2, with hardware complexity overhead less than 2%. Key–Words: LDPC code, fast convergence decoding algorithm, layered decoding, min-sum algorithm, hardware implementation 1

WSEAS TRANSACTIONS on COMMUNICATIONS archiveJul 1, 20091 citation

Informed Scheduling for Belief-Propagation Decoding of LDPC Codes

Andres I. Vila Casado, Miguel Griot, Richard D. Wesel

Abstract — Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Complexity and implementability issues are also addressed. Index Terms — Belief propagation-algorithm, messagepassing schedule, error-control codes, low-density paritycheck codes. I.

Feb 19, 20070 citations