IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)

An Improved Message Passing Schedule of BP-Based Decoding Algorithm for LDPC Codes

Dong Jingru, Hang Yin, Sijia Wang

Published Dec 1, 2016• 3 citations

Publisher

Abstract

In this paper, we propose an optimized schedule called IRMP (Improved Row Message Passing) schedule, based on analysis of the existing message passing schedules. This type of schedule has changed the message updating order between variable and check nodes. In accordance with this schedule, an improved BP-Based decoding algorithm is proposed. Simulations show that, this algorithm has beaten the performance of BP-Based algorithms available in terms of error rate and number of iteration.

DOI: 10.1109/ithings-greencom-cpscom-smartdata.2016.113

Related papers

Interlaced Column-Row Message-Passing Schedule for Decoding LDPC Codes

Saleh Usman, Mohammad M. Mansour, Ali Chehab

This paper investigates efficient decoding algorithms for LDPC codes. Alternating column-row message-passing (ACRMP) and Interlaced column-row message-passing (I-CRMP) schedules for decoding of LDPC codes are proposed and investigated in this work. Existing serial scheduling schemes for LDPC decoding are based either on column message-passing (MP) or row MP, and roughly converge twice as fast as Gallager's flooding-based MP schedule at high signal-to-noise ratio (SNR). To further accelerate the convergence speed of serial decoders, hybrid column-row MP schedules that perform multiple message passes between check and variable nodes within or between iterations are proposed. Our proposed I-CRMP schedule converges in less than half the number of iterations compared to the best existing serial decoding schedules. Compared to column MP, the added complexity of this scheme is proportional only to check-node-degree times more additions at variable nodes. This increase in complexity is moderate compared to the convergence acceleration factor that the scheme achieves. Superior performance of the proposed I-CRMP scheme is confirmed by decoding randomly generated as well as IEEE 802.11n/ac LDPC codes.

GlobecomDec 1, 20165 citations

Optimized Message Passing Schedules for LDPC Decoding

Predrag Radosavljevic, Alexandre de Baynast, Joseph R. Cavallaro

The major drawback of the LDPC codes versus the turbo-codes is their comparative low convergence speed: 25-30 iterations vs. 8-10 iterations for turbo-codes. Recently, Hocevar showed by simulations that the convergence rate of the LDPC decoder can be accelerated by exploiting a `turbo-scheduling' applied on the bit-node messages (rows of the parity check matrix). In this paper, we show analytically that the convergence rate for this type of scheduling is about two times increased for most of the regular LDPC codes. Second we prove that `turbo-scheduling' applied on the rows of the parity check matrix is identical belief propagation algorithm as standard message passing algorithm. Furthermore, we propose two new message passing schedules: 1) a turbo-scheduling is applied on the check-node messages (columns of the parity check matrix); and 2) a hybrid version of both previous schedules where the turbo-effect is applied on both check-nodes and bit-nodes. Frame error rate simulations validate the effectiveness of the proposed schedules

Asilomar Conference on Signals, Systems and Computers (ACSSC)Mar 22, 200667 citations

Serial Update Scheduling Based on Weighted Average Message of Check Nodes for LDPC Codes

Xingcheng Liu

For short and middle length LDPC codes,the oscillation of LLR owing to cycles degrades the performance of BP algorithm.In order to minimize the oscillation of LLR during BP decoding process,an improved BP algorithm with serial update scheduling using weighted average message to update the message of check-to-variable node is proposed.Currently computed message of check-to-variable node and the message of old check-to-variable node are weighted and then added up to update the message of check-to-variable node.By higher weighted currently computed message of check-to-variable node than the message of old check-to-variable node,the improved algorithm effectively minimizes oscillation of LLR,at the same time,keeps normal BP message propagation and low compute complexity.Simulation results show that,for short and middle length LDPC codes,the improved algorithm achieves more noticeable error performance than CSBP algorithm at middle to high signal to noise ratio.

Acta Scientiarum Naturalium Universitatis SunyatseniJan 1, 20100 citations

Reduced Complexity and Improved Performance for Short Regular LDPC Codes Based on Select Updating Schedule

Jianquan Liu, Youyun Xu, Yueming Cai

In this paper, we present a modified BP decoding algorithm based on select updating schedule by analyzing the properties of message-passing through cycles, we also proposed a concrete scheme to obtain the select updating schedule, the simulations prove that we could improve performance and reduce complexity at the same time for short regular LDPC codes which have a small difference between the maximal and minimal single bit node girths by select updating schedule compared with the conventional BP decoding algorithm.

IEEE Vehicular Technology ConferenceApr 1, 20070 citations

Analysis of Complexity and Convergence Speed of Sequential Schedules for Decoding LDPC Codes

Sunghwan Kim, Min‐Ho Jang, Song‐Nam Hong +1 more

In this paper, a sequential message-passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes is analyzed. This decoding algorithm shows better bit error rate (BER) performance than the conventional message-passing decoding algorithm, especially for the small number of iterations. Analytical results tell us that as the number of partitioned subsets of check nodes increases, the BER performance becomes better. We also derive the recursive equations for mean values of messages at check and variable nodes by using density evolution with Gaussian approximation. Finally, the analytical results are conflrmed by the simulation results.

Jan 1, 20062 citations

Improving LDPC Decoders via Informed Dynamic Scheduling

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

Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The message-passing schedule of the BP algorithm significantly affects the performance of the LDPC decoder. The authors recently presented a novel message-passing schedule, called Informed Dynamic Scheduling (IDS), that selects the message-passing schedule according to the observed rate of change of the messages. IDS yields a lower error-rate performance than traditional message-passing schedules (such as flooding and LBP) because it solves traditional trapping-set errors. However, for short-blocklength LDPC codes, IDS algorithms present non-trapping-set errors in the error floor region. This paper presents a careful analysis of those errors and proposes mixed scheduling strategies, combining LBP with IDS, that solve these non-trapping-set errors. Also, we will show that some lower-complexity techniques, such as mixed scheduling, perform close to the best IDS strategies for larger-blocklength codes.

IEEE Information Theory Workshop (ITW)Sep 1, 200731 citations