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

Journal of Xi'an University of Post and Telecommunications

Application of fast fourier transform in sum-product decoding of non-binary LDPC codes

Huijuan Zheng

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

The application of fast Fourier transform(FFT) in sum-product decoding of non-binary LDPC(low-density parity-check) codes greatly reduces the decoding complexity.However,the inherent principle of this application has not been well explained.Based on the probability mass function calculation of the sum of two independent random variables,a simple and straightforward understanding of the application of FFT in iterative decoding of non-binary LDPC codes is provided in this paper.

Related papers

An improved low-complexity sum-product decoding algorithm for low-density parity-check codes

Michaelraj Kingston Roberts, Ramesh Jayabalan

In this paper, an improved low-complexity sum-product decoding algorithm is presented for low-density parity-check (LDPC) codes. In the proposed algorithm, reduction in computational complexity is achieved by utilizing fast Fourier transform (FFT) with time shift in the check node process. The improvement in the decoding performance is achieved by utilizing an optimized integer constant in the variable node process. Simulation results show that the proposed algorithm achieves an overall coding gain improvement ranging from 0.04 to 0.46 dB. Moreover, when compared with the sum-product algorithm (SPA), the proposed decoding algorithm can achieve a reduction of 42%–67% of the total number of arithmetic operations required for the decoding process.

Frontiers of Information Technology & Electronic Engineering•Jun 1, 2015•12 citations

FFT based sum product decoding algorithm of LDPC coder for GF(q)

Jigisha N. Patel, Neeta Chapatwala, Mrugesh Patel

Low Density Parity Check (LDPC) codes have excellent error correcting performance. LDPC codes are one of the block coding techniques and it performs near Shannon limit and recommended for many practical applications. Non-binary LDPC codes extension of binary LDPC in error correcting property especially for short and moderate block length. In many digital communication systems these codes have strong competitors of turbo codes for error control. Low Density Parity Check as it name is suggests that in a parity check matrix (H) consists of very small number of non-zero elements comparing with zero elements. The strength of the LDPC code defines Parity Check Matrix (PCM). LDPC code contains two types of decoding algorithms hard and soft decision algorithm. By comparing with other traditional decoding algorithm FFT based sum product algorithm reduced computation complexity with better decoding performance. In this paper, LDPC codes for FFT based sum product decoding algorithm performances are analysed for various order of Galois Field GF(q) using AWGN channel. Decoding performance measured in terms of symbol error rate which improve with increasing order of Galois field.

International Conference on Emerging Technology Trends in Electronics, Communication and Networking (ET2ECN)•Dec 1, 2014•3 citations

Fourier domain decoding algorithm of non-binary LDPC codes for parallel implementation

Kenta Kasai, K. Sakaniwa

For decoding non-binary low-density parity-check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worse, check nodes usually have higher degree than variable nodes. As a result, most of the time for decoding is used for check node computations, which leads to a bottleneck effect. In this paper, we propose a Log-SP algorithm in the Fourier domain. With this algorithm, the role of variable nodes and check nodes are switched. The intensive computations are spread over lower-degree variable nodes, which can be efficiently calculated in parallel. Furthermore, we develop a fast calculation method for the estimated bits and syndromes in the Fourier domain.

IEEE International Conference on Acoustics Speech and Signal Processing•May 1, 2011•4 citations

Fourier Domain Decoding Algorithm of Non-binary LDPC Codes for Parallel Implementation

Kenta Kasai, Kohichi Sakaniwa

For decoding non-binary low-density parity-check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worth, check nodes usually have higher degree than variable nodes. As a result, most of the time for decoding is used for check node computations, which leads to a bottleneck effect. In this paper, we propose a Log-SP algorithm in the Fourier domain. With this algorithm, the role of variable nodes and check nodes are switched. The intensive computations are spread over lower-degree variable nodes, which can be efficiently calculated in parallel. Furthermore, we develop a fast calculation method for the estimated bits and syndromes in the Fourier domain.

arXiv:1008.4370•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2010•4 citations

Fast Fourier Transform simplified soft-distance decoding algorithm for decoding non-binary LDPC codes

Leonardo J. Arnone, Carlos Arturo Gayoso, C. M. Gonzalez +3 more

Non-Binary Low-Density Parity-Check (NB-LDPC) codes have been shown to outperform equivalent LDPC codes defined over the binary field, especially when they are designed in high order Galois fields GF(q). This however leads to an increased decoding complexity.

Argentine School of Micro-Nanoelectronics, Technology and Applications•Jul 1, 2014•2 citations

A Construction of Algebraic Geometric LDPC Codes*

Dongliang Xiao, Huizhen Li, Ke Wen +1 more

This paper presents an original method for constructing high performance non-binary LDPC codes based on algebraic geometric codes’ parity check matrix. Codes constructed based on this method perform very well over the AWGN channel. With iterative decoding using a Fast Fourier Transform (FFT) based q-ary sum-product algorithm (QSPA), AG-LDPC codes achieve significantly large coding gains over the PEG non-binary LDPC and binary LDPC. Simulation results also show that the AG-LDPC significantly lower the decoding error floor, and the undetected error rate.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 7, 2024•0 citations
The application of fast Fourier transform(FFT) in sum-product decoding of non-binary LDPC(low-density parity-check) codes greatly reduces the decoding complexity.However,the inherent principle of this application has not been well explained.Based on the probability mass function calculation of the sum of two independent random variables,a simple and straightforward understanding of the application of FFT in iterative decoding of non-binary LDPC codes is provided in this paper.
In this paper, an improved low-complexity sum-product decoding algorithm is presented for low-density parity-check (LDPC) codes. In the proposed algorithm, reduction in computational complexity is achieved by utilizing fast Fourier transform (FFT) with time shift in the check node process. The improvement in the decoding performance is achieved by utilizing an optimized integer constant in the variable node process. Simulation results show that the proposed algorithm achieves an overall coding gain improvement ranging from 0.04 to 0.46 dB. Moreover, when compared with the sum-product algorithm (SPA), the proposed decoding algorithm can achieve a reduction of 42%–67% of the total number of arithmetic operations required for the decoding process.
Low Density Parity Check (LDPC) codes have excellent error correcting performance. LDPC codes are one of the block coding techniques and it performs near Shannon limit and recommended for many practical applications. Non-binary LDPC codes extension of binary LDPC in error correcting property especially for short and moderate block length. In many digital communication systems these codes have strong competitors of turbo codes for error control. Low Density Parity Check as it name is suggests that in a parity check matrix (H) consists of very small number of non-zero elements comparing with zero elements. The strength of the LDPC code defines Parity Check Matrix (PCM). LDPC code contains two types of decoding algorithms hard and soft decision algorithm. By comparing with other traditional decoding algorithm FFT based sum product algorithm reduced computation complexity with better decoding performance. In this paper, LDPC codes for FFT based sum product decoding algorithm performances are analysed for various order of Galois Field GF(q) using AWGN channel. Decoding performance measured in terms of symbol error rate which improve with increasing order of Galois field.
For decoding non-binary low-density parity-check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worse, check nodes usually have higher degree than variable nodes. As a result, most of the time for decoding is used for check node computations, which leads to a bottleneck effect. In this paper, we propose a Log-SP algorithm in the Fourier domain. With this algorithm, the role of variable nodes and check nodes are switched. The intensive computations are spread over lower-degree variable nodes, which can be efficiently calculated in parallel. Furthermore, we develop a fast calculation method for the estimated bits and syndromes in the Fourier domain.
For decoding non-binary low-density parity-check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worth, check nodes usually have higher degree than variable nodes. As a result, most of the time for decoding is used for check node computations, which leads to a bottleneck effect. In this paper, we propose a Log-SP algorithm in the Fourier domain. With this algorithm, the role of variable nodes and check nodes are switched. The intensive computations are spread over lower-degree variable nodes, which can be efficiently calculated in parallel. Furthermore, we develop a fast calculation method for the estimated bits and syndromes in the Fourier domain.
This paper presents an original method for constructing high performance non-binary LDPC codes based on algebraic geometric codes’ parity check matrix. Codes constructed based on this method perform very well over the AWGN channel. With iterative decoding using a Fast Fourier Transform (FFT) based q-ary sum-product algorithm (QSPA), AG-LDPC codes achieve significantly large coding gains over the PEG non-binary LDPC and binary LDPC. Simulation results also show that the AG-LDPC significantly lower the decoding error floor, and the undetected error rate.