IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)

The Probabilistic Finite Alphabet Iterative Decoder for Low-Density Parity-Check Codes

Khoa Le, Fakhreddine Ghaffari, David Declercq

Published Aug 1, 2018• 0 citations

Abstract

This paper proposes a new concept of applying the Non-Surjective Finite Alphabet Iterative Decoder (NS-FAID) for the Low-Density Parity-Check (LDPC) decoding. Differently from the NS-FAID which applies a fixed nonlinear function by using a fixed Look-Up-Table (LUT) on the variable node messages, the proposed method, called Probabilistic FAID (PFAID), uses more than one LUTs in a probabilistic way. By using the density evolution, we show that this method provides a significant improvement in performance compared to the NS-FAID and the traditional MS. The advantage of PFAID is shown by the fact that, a PFAID with low message quantization level can reach or even surpass the performance of the higher level quantization MS decoder. Furthermore, we show that PFAID can be efficiently implemented with no hardware overhead compared to MS or NSFAID with the same message quantization level. The hardware complexity analysis and decoding simulation performance are provided as superiority evidences of PFAID over the referenced benchmarks.

DOI: 10.1109/mwscas.2018.8623923

Related papers

The Probabilistic Finite Alphabet Iterative Decoder for Low-Density Parity-Check Codes

Fakhreddine Ghaffari, Khoa Le, David Declercq

We propose in this paper a new approach of applying the Non-Surjective Finite Alphabet Iterative Decoder (NS-FAID) for the Low-Density Parity-Check (LDPC) decoding. Differently from the NS-FAID which applies a fixed nonlinear function by using a fixed Look-Up-Table (LUT) on the variable node messages, the proposed method, called Probabilistic FAID (PFAID), uses more than one LUT in a probabilistic way. By using the density evolution, we show that this method provides a significant improvement in performance compared to the NS-FAID and the traditional MS. The advantage of PFAID is shown by the fact that, a PFAID with low message quantization level can reach or even surpass the performance of the higher level quantization MS decoder. Furthermore, we show that PFAID can be efficiently implemented with no hardware overhead compared to Min-Sum (MS) or NS-FAID with the same message quantization level. The hardware complexity analysis and decoding simulation performance are provided as superiority evidences of PFAID over the referenced benchmarks.

IEEE International New Circuits and Systems Conference (NEWCAS)Jun 1, 20191 citation

Finite Alphabet Iterative Decoders for LDPC Codes: Optimization, Architecture and Analysis

Fang Cai, Xinmiao Zhang, David Declercq +2 more

Low-density parity-check (LDPC) codes are adopted in many applications due to their Shannon-limit approaching error-correcting performance. Nevertheless, belief-propagation (BP) based decoding of these codes suffers from the error-floor problem, i.e., an abrupt change in the slope of the error-rate curve that occurs at very low error rates. Recently, a new type of decoders termed finite alphabet iterative decoders (FAIDs) were introduced. The FAIDs use simple Boolean maps for variable node processing, and can surpass the BP-based decoders in the error floor region with very short word length. We restrict the scope of this paper to regular dv=3 LDPC codes on the BSC channel. This paper develops a low-complexity implementation architecture for the FAIDs by making use of their properties. Particularly, an innovative bit-serial check node unit is designed for the FAIDs, and a small-area variable node unit is proposed by exploiting the symmetry in the Boolean maps. Moreover, an optimized data scheduling scheme is proposed to increase the hardware utilization efficiency. From synthesis results, the proposed FAID implementation needs only 52% area to reach the same throughput as one of the most efficient standard Min-Sum decoders for an example (7807, 7177) LDPC code, while achieving better error-correcting performance in the error-floor region. Compared to an offset Min-Sum decoder with longer word length, the proposed design can achieve higher throughput with 45% area, and still leads to possible performance improvement in the error-floor region.

IEEE Transactions on Circuits and Systems I Regular PapersMar 20, 201420 citations

Low-complexity finite alphabet iterative decoders for LDPC codes

Fang Cai, Xinmiao Zhang, David Declercq +3 more

Low-density parity-check (LDPC) codes are adopted in many applications due to their Shannon-limit approaching error-correcting performance. Nevertheless, belief-propagation (BP) based decoding of these codes suffers from the error-floor problem. Recently, a new type of decoders termed finite alphabet iterative decoders (FAIDs) were introduced. The FAIDs use simple Boolean maps for variable node processing. With very short word length, they can surpass the BP-based decoders in the error floor region. This paper develops a low-complexity implementation architecture for FAIDs by making use of their properties. Particularly, an innovative bit-serial check node unit is designed for FAIDs, and the symmetric Boolean maps for variable node processing lead to small silicon area. An optimized data scheduling scheme is also proposed to increase the hardware utilization efficiency. From synthesis results, the proposed FAID implementation needs only 52% area to reach the same throughput as one of the most efficient Min-sum decoders for an example (7807, 7177) LDPC code, while achieving better error-correcting performance in the error-floor region.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20133 citations

Finite Alphabet Iterative Decoders—Part I: Decoding Beyond Belief Propagation on the Binary Symmetric Channel

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

We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the binary symmetric channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist {FAIDs that surpass the floating-point BP decoder in the error floor region while requiring only three bits of precision for the representation of the messages}. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.

IEEE Transactions on CommunicationsSep 16, 201383 citations

Optimized Non-Surjective FAIDs for 5G LDPC Codes With Learnable Quantization

Yanchen Lyu, Ming Jiang, Yifan Zhang +3 more

This letter proposes a novel approach for designing non-surjective (NS) finite alphabet iterative decoders (FAIDs) for quasi-cyclic low-density parity-check (LDPC) codes, especially 5G LDPC codes. We employ recurrent quantized neural networks to optimize the look-up tables used in NS-FAIDs, the design of which is the kernel of FAIDs. During the optimization of LUTs, the quantized message alphabets and quantization thresholds are jointly designed. To cope with the untrainable problem of quantization thresholds in the existing neural-network-based linear FAIDs, we use softmax distribution to soften the implied one-hot distribution of quantization thresholds, making it trainable in the neural network. The proposed decoders offer enhanced universality compared to existing neural network-based linear FAIDs, making them directly applicable to 5G LDPC codes with support for 2-bit quantization over the additive white Gaussian noise channel. Additionally, they significantly outperform the original NS-FAID in terms of performance.

IEEE Communications LettersDec 8, 20235 citations

Finite Alphabet Iterative Decoders, Part I: Decoding Beyond Belief Propagation on BSC

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

We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the Binary Symmetric channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the Belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist 3-bit precision FAIDs that surpass the BP decoder in the error floor. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.

arXiv:1207.4800Jul 19, 20123 citations