IEEE International Symposium on Information Theory (ISIT)

A Low Complexity Decoding Algorithm for NB-LDPC Codes over Quadratic Extension Fields

V. B. Wijekoon, Emanuele Viterbo, Yi Hong

Published Jun 1, 2020• 3 citations

Abstract

NB-LDPC codes, a class of codes well-known for their exceptional error correcting performance, are not yet used widely in practice due to the high complexity of decoding algorithms. In this paper, we propose a low complexity decoder for these codes by means of a novel graph expansion. We view the finite field over which the code is constructed as the quadratic extension of one of its subfields, and then expand the Tanner graph of the code into a graph over that particular field. Decoding algorithm, which is tailored for this larger graph, presents significant complexity gains while the performance loss is minimal.

DOI: 10.1109/isit44484.2020.9174489

Related papers

Decoding of NB-LDPC codes over Subfields

V. B. Wijekoon, Emanuele Viterbo, Yi Hong

In this paper, we present a novel method to expand a graph over a finite field into a larger one over one of the original field's subfields. This allows a number of different graph expansions for any given graph. These expansions can be used in various applications, and we focus specifically on the case of decoding NB-LDPC codes. Using the novel expanded graphs, it is possible to reduce decoding complexity of NB- LDPC codes significantly with minimal performance losses.

arXiv:2005.07352IEEE Transactions on CommunicationsJan 1, 20206 citations

A Novel Graph Expansion and a Decoding Algorithm for NB-LDPC Codes

V. B. Wijekoon, Emanuele Viterbo, Yi Hong +2 more

Non-binary low-density parity-check (NB-LDPC) codes are known to offer several advantages over their binary counterparts, but the higher complexity, and the resource-hungry nature of decoding algorithms have so far restricted their practical usage. In this paper, we propose a new decoding algorithm for NB-LDPC codes over finite fields of characteristic 2, based on a novel binary expansion of the Q-ary Tanner graph. While it offers substantial complexity gains, simulation results demonstrate that the performance loss of the new algorithm, in comparison to the best known decoder, is quite small. Furthermore, due to being based on a binary graph, it is particularly attractive for hardware implementations. We also suggest a simplified version of the algorithm, which offers even higher gains in complexity.

IEEE Transactions on CommunicationsDec 23, 201914 citations

Architecture of a Low-Complexity Non-Binary LDPC Decoder

Adrian Voicila, David Declercq, François S. Verdier +2 more

In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC (NB-LDPC) codes, presented in [4]. To the knowledge of the authors this is the first implementation of an GF(q) LDPC decoder for high order fields (q ≥ 64). The originality of the proposed architecture is that it takes into account the memory problem of the NB-LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field's order. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results prove also that an implementation of a NB-LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, NB-LDPC codes provides a promising vehicle for real-life efficient coding system implementations.

International Conference on Consumer ElectronicsJan 1, 20081 citation

Low-Density Parity-Check Lattices: Construction and Decoding Analysis

Mohammad‐Reza Sadeghi, Amir H. Banihashemi, Daniel Panario

Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands

IEEE Transactions on Information TheorySep 29, 200695 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

Construction of short-block nonbinary LDPC codes based on cyclic codes

Hengzhou Xu, Baoming Bai, Min Zhu +2 more

In this paper, we focus on short-block nonbinary LDPC (NB-LDPC) codes based on cyclic codes. Based on Tanner graphs' isomorphism, we present an efficient search algorithm for finding non-isomorphic binary cyclic LDPC codes. Notice that the parity-check matrix H of the resulting code is square and not of full rank, and its row weight and column weight are the same. By replacing the ones in the same column of H with a nonzero element of finite fields GF(q), a class of NB-LDPC codes over GF(q) is obtained. Numerical results show that the constructed codes perform well over the AWGN channel and have fast decoding convergence. Therefore, the proposed NB-LDPC codes provide a promising coding scheme for low-latency and high-reliability communications.

China CommunicationsAug 1, 20175 citations