IEEE International Symposium on Information Theory (ISIT)

Fourier domain representation of non-binary LDPC codes

Valentin Savin

Published Jul 1, 2012• 6 citations

Abstract

In this paper we propose a binary representation of non-binary codes, which consists in a q-fold covering of the non-binary graph, where q is the size of the non-binary alphabet. It is shown that this covering graph is actually the underlying graph of the Fourier-domain Belief-Propagation decoding, meaning that the exchanged messages carry information about the bit-nodes of the covering graph. Finally, a new coding scheme is proposed, in which the bits transmitted over the channel correspond to a set of bit-nodes of the Fourier domain representation. The proposed coding scheme allows using the same decoder, regardless of how many and which of the Fourier-domain bit-nodes have been transmitted. This considerably increases the flexibility of the system, without increasing its complexity.

DOI: 10.1109/isit.2012.6283975

Related papers

Binary linear-time erasure decoding for non-binary LDPC codes

Valentin Savin

In this paper, we first introduce the extended binary representation of non-binary codes, which corresponds to a covering graph of the bipartite graph associated with the non-binary code. Then we show that non-binary codewords correspond to binary codewords of the extended representation that further satisfy some simplex-constraint: that is, bits lying over the same symbol-node of the non-binary graph must form a codeword of a simplex code. Applied to the binary erasure channel (BEC), this description leads to a binary erasure decoding algorithm of non-binary LDPC codes, whose complexity depends linearly on the cardinality of the alphabet. We also give insights into the structure of stopping sets for non-binary LDPC codes, and discuss several aspects related to upper-layer FEC applications.

arXiv:0910.1922IEEE Information Theory Workshop (ITW)Jan 1, 200915 citations

Performance Analysis of High-rate Non-binary LDPC Codes Under AWGN Channels

Jie Bao

To solve the problem of high computational complexity and inconvenient for hardware implementation in original decoding algorithm for non-binary LDPC codes,two simplified decoding algorithms are introduced for nonbinary LDPC codes: the fast Fourier transform belief propagation(FFT-BP) decoding algorithm and the Log-domain belief propagation(Log-BP) decoding algorithm. The performance comparison between two different decoding algorithms for LDPC Codes over GF(q) is investigated at high code rates(1/2~1) over AWGN channel.The performance curves show that by the decreasing of code rate,both coding gains and the distances from Shannon limit increase with the two algorithms,which means that non-binary LDPC Codes are suit for applications at high rates.Meanwhile it is shown that Log-BP decoding algorithm may contribute a considerable improvement in computational complexity at the cost of sacrificing some performance, which is important for Log-BP decoding algorithm to be applied in hardware implementation.

Journal of Chongqing University. English EditionJan 1, 20070 citations

Performance Advantage of Non-binary LDPC Codes At High Code Rate under AWGN Channel

Long Ma, Lin Wang, Jianwen Zhang

Two different decoding algorithms for non-binary LDPC codes: the fast Fourier transform belief propagation (FFT-BP) decoding algorithm and the Log-domain belief propagation (Log-BP) decoding algorithm are introduced in this paper. Their performance advantage of two different decoding algorithms for LDPC Codes over GF(q) is investigated at high code rates (1/2~1) over AWGN channel. The performance curves show that with the decreasing of code rate, both coding gains and the distances from Shannon limit increase under the two algorithms, which means for non- binary LDPC Codes to be suitable for applications at high rates. Meanwhile it is shown that Log-BP decoding algorithm may contribute a considerable saving in computational complexity at the cost of sacrifice small performance, which is important for Log-BP decoding algorithm to be applied in hardware implementation.

IEEE International Conference on Communication Technology (ICCT)Nov 1, 20066 citations

Joint decoding of multiple non-binary LDPC codewords

Stephan Pfletschinger

We develop a belief-propagation (BP) decoder for the joint decoding of multiple codewords which belong to the same non-binary LDPC code. Decoding is based on soft information in form of joint channel-posterior probabilities of all codeword symbols. We extend the BP algorithm for q-ary LDPC codes such that the FFT-based check node processing is preserved and the complexity remains manageable. This joint decoding is useful in settings in which multiple codewords are transmitted in a non-orthogonal way over the same channel, including multiple-access with packet collisions, physical-layer network coding and multi-resolution broadcasting. We show in an example that joint decoding can be far superior to separate decoding.

IEEE International Conference on Communications workshopsJun 1, 20149 citations

Optimizing and decoding LDPC codes with graph-based techniques

Amir H. Djahanshahi

Low-density parity-check (LDPC) codes have been known for their outstanding error-correction capabilities. With low- complexity decoding algorithms and a near capacity performance, these codes are among the most promising forward error correction schemes. LDPC decoding algorithms are generally sub-optimal and their performance not only depends on the codes, but also on many other factors, such as the code representation. In particular, a given non- binary code can be associated with a number of different field or ring image codes. Additionally, each LDPC code can be described with many different Tanner graphs. Each of these different images and graphs can possibly lead to a different performance when used with iterative decoding algorithms. Consequently, in this dissertation we try to find better representations, i.e., graphs and images, for LDPC codes. We take the first step by analyzing LDPC codes over multiple-input single-output (MISO) channels. In an n_T by 1 MISO system with a modulation of alphabet size 2M̂, each group of n_T transmitted symbols are combined and produce one received symbol at the receiver. As a result, we consider the LDPC-coded MISO system as an LDPC code over a 2̂{M n_T}-ary alphabet. We introduce a modified Tanner graph to represent MISO-LDPC systems and merge the MISO symbol detection and binary LDPC decoding steps into a single message passing decoding algorithm. We present an efficient implementation for belief propagation decoding that significantly reduces the decoding complexity. With numerical simulations, we show that belief propagation decoding over modified graphs outperforms the conventional decoding algorithm for short length LDPC codes over unknown channels. Subsequently, we continue by studying images of non-binary LDPC codes. The high complexity of belief propagation decoding has been proven to be a detrimental factor for these codes. Thereby, we suggest employing lower complexity decoding algorithms over image codes instead. We introduce three classes of binary image codes for a given non-binary code, namely: basic, mixed, and extended binary image codes. We establish upper and lower bounds on the minimum distance of these binary image codes, and present two techniques to find binary image codes with better performance under belief propagation decoding algorithm. In particular, we present a greedy algorithm to find optimized binary image codes. We then proceed by investigation of the ring image codes. Specifically, we introduce matrix-ring-image codes for a given non-binary code. We derive a belief propagation decoding algorithm for these codes, and with numerical simulations, we demonstrate that the low-complexity belief propagation decoding of optimized image codes has a performance very close to the high complexity BP decoding of the original non-binary code. Finally, in a separate study, we investigate the performance of iterative decoders over binary erasure channels. In particular, we present a novel approach to evaluate the inherent unequal error protection properties of irregular LDPC codes over binary erasure channels. Exploiting the finite length scaling methodology, that has been used to study the average bit error rate of finite-length LDPC codes, we introduce a scaling approach to approximate the bit erasure rates in the waterfall region of variable nodes with different degrees. Comparing the bit erasure rates obtained from Monte Carlo simulation with the proposed scaling approximations, we demonstrate that the scaling approach provides a close approximation for a wide range of code lengths. In view of the complexity associated with the numerical evaluation of the scaling approximation, we also derive simpler upper and lower bounds and demonstrate through numerical simulations that these bounds are very close to the scaling approximation

Jan 1, 20101 citation

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 LettersAug 4, 201126 citations