Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Message passing algorithm with MAP decoding on zigzag cycles for non-binary LDPC codes

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

Published Jul 1, 2013• 1 citation
Publisher

Abstract

In this paper, we propose a decoding algorithm which lowers decoding erasure rates in the error floor regions for non-binary low-density parity-check codes transmitted over the binary erasure channels. This decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding erasures in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. A simulation result shows that the decoding erasure rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.

DOI
10.1109/isit.2013.6620741

Related papers

Message Passing Decoder with Decoding on Zigzag Cycles for Non-binary LDPC Codes

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

In this paper, we propose a message passing decoding algorithm which lowers decoding error rates in the error floor regions for non-binary low-density parity-check (LDPC) codes transmitted over the binary erasure channel (BEC) and the memoryless binary-input output-symmetric (MBIOS) channels. In the case for the BEC, this decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding errors in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. Moreover, we extend this decoding algorithm to the MBIOS channels. Simulation results demonstrate that the decoding error rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•2 citations

Analysis of Error Floors of Non-binary LDPC Codes over BEC

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

In this paper, we investigate the error floors of the non-binary low-density parity-check codes transmitted over the binary erasure channels under belief propagation decoding. We propose a method to improve the decoding erasure rates in the error floors by optimizing labels in zigzag cycles in the Tanner graphs of codes. Furthermore, we give lower bounds on the bit and the symbol erasure rates in the error floors. The simulation results show that the presented lower bounds are tight for the codes designed by the proposed method.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•3 citations

Analysis of Error Floors of Non-binary LDPC Codes over MBIOS Channel

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

In this paper, we investigate the error floors of non-binary low-density parity-check (LDPC) codes transmitted over the memoryless binary-input output-symmetric (MBIOS) channels. We provide a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the belief propagation decoder. We consider an expurgated ensemble of non-binary LDPC codes by using the above necessary and sufficient condition, and hence exhibit lower error floors. Finally, we show lower bounds of the error floors for the expurgated LDPC code ensembles over the MBIOS channels.

arXiv:1106.2109•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2011•2 citations

Finite alphabet iterative decoders for LDPC codes surpassing floating-point iterative decoders

Shiva Kumar Planjery, David Declercq, Ludovic Danjean +1 more

Introduced is a new type of message-passing (MP) decoders for low-density parity-check (LDPC) codes over the binary symmetric channel. Unlike traditional belief propagation (BP) based MP algorithms which propagate probabilities or log-likelihoods, the new MP decoders propagate messages requiring only a finite number of bits for their representation in such a way that good performance in the error floor region is ensured. Additionally, these messages are not quantised probabilities or log-likelihoods. As examples, MP decoders are provided that require only three bits for message representation, but surpass the floating-point BP (which requires a large number of bits for representation) in the error-floor region.

Electronics Letters•Aug 4, 2011•27 citations

Analysis of Error Floors of Non-Binary LDPC Codes over MBIOS Channel

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

In this paper, we investigate the error floors of non-binary low-density parity-check (LDPC) codes transmitted over the memoryless binary-input output-symmetric (MBIOS) channels. We clarify a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the BP decoder. We expurgate non-binary LDPC code ensemble to analyze and to lower the error floor by using the above condition. Finally, we show upper and lower bounds of the error floors of the expurgated LDPC code ensemble over the MBIOS channel.

International Conference on Communications•Jun 1, 2011•8 citations

A differential binary message-passing LDPC decoder

Nastaran Mobini, A.H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

IEEE Transactions on Communications•Sep 1, 2009•32 citations
In this paper, we propose a decoding algorithm which lowers decoding erasure rates in the error floor regions for non-binary low-density parity-check codes transmitted over the binary erasure channels. This decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding erasures in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. A simulation result shows that the decoding erasure rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.
In this paper, we propose a message passing decoding algorithm which lowers decoding error rates in the error floor regions for non-binary low-density parity-check (LDPC) codes transmitted over the binary erasure channel (BEC) and the memoryless binary-input output-symmetric (MBIOS) channels. In the case for the BEC, this decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding errors in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. Moreover, we extend this decoding algorithm to the MBIOS channels. Simulation results demonstrate that the decoding error rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.
In this paper, we investigate the error floors of the non-binary low-density parity-check codes transmitted over the binary erasure channels under belief propagation decoding. We propose a method to improve the decoding erasure rates in the error floors by optimizing labels in zigzag cycles in the Tanner graphs of codes. Furthermore, we give lower bounds on the bit and the symbol erasure rates in the error floors. The simulation results show that the presented lower bounds are tight for the codes designed by the proposed method.
In this paper, we investigate the error floors of non-binary low-density parity-check (LDPC) codes transmitted over the memoryless binary-input output-symmetric (MBIOS) channels. We provide a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the belief propagation decoder. We consider an expurgated ensemble of non-binary LDPC codes by using the above necessary and sufficient condition, and hence exhibit lower error floors. Finally, we show lower bounds of the error floors for the expurgated LDPC code ensembles over the MBIOS channels.
Introduced is a new type of message-passing (MP) decoders for low-density parity-check (LDPC) codes over the binary symmetric channel. Unlike traditional belief propagation (BP) based MP algorithms which propagate probabilities or log-likelihoods, the new MP decoders propagate messages requiring only a finite number of bits for their representation in such a way that good performance in the error floor region is ensured. Additionally, these messages are not quantised probabilities or log-likelihoods. As examples, MP decoders are provided that require only three bits for message representation, but surpass the floating-point BP (which requires a large number of bits for representation) in the error-floor region.
In this paper, we investigate the error floors of non-binary low-density parity-check (LDPC) codes transmitted over the memoryless binary-input output-symmetric (MBIOS) channels. We clarify a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the BP decoder. We expurgate non-binary LDPC code ensemble to analyze and to lower the error floor by using the above condition. Finally, we show upper and lower bounds of the error floors of the expurgated LDPC code ensemble over the MBIOS channel.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.