IEEE Communications Surveys & Tutorials

A Survey on High-Throughput Non-Binary LDPC Decoders: ASIC, FPGA, and GPU Architectures

Oscar Ferraz, Srinivasan Subramaniyan, Chinthala Ramesh, João Andrade, Joseph R. Cavallaro, Soumitra K. Nandy, Vitor M. M. da Silva, Xinmiao Zhang, Madhura Purnaprajna, Gabriel Falcão

Published Nov 8, 2021• 74 citations

Publisher

Abstract

Non-binary low-density parity-check (NB-LDPC) codes show higher error-correcting performance than binary low-density parity-check (LDPC) codes when the codeword length is moderate and/or the channel has bursts of errors. The need for high-speed decoders for future digital communications led to the investigation of optimized NB-LDPC decoding algorithms and efficient implementations that target high throughput and low energy consumption levels. We carried out a comprehensive survey of existing NB-LDPC decoding hardware that targets the optimization of these parameters. Even though existing NB-LDPC decoders are optimized with respect to computational complexity and memory requirements, they still lag behind their binary counterparts in terms of throughput, power and area optimization. This study contributes to an overall understanding of the state-of-the-art on application-specific integrated-circuit (ASIC), field-programmable gate array (FPGA) and graphics processing units (GPU) based systems, and highlights the current challenges that still have to be overcome on the path to more efficient NB-LDPC decoder architectures.

DOI: 10.1109/comst.2021.3126127

Related papers

High-Performance and Energy-Efficient Decoder Design for Non-Binary LDPC Codes

Yuta Toriyama

Binary Low-Density Parity-Check (LDPC) codes are a type of error correction code known to exhibit excellent error-correcting capabilities, and have increasingly been applied as the forward error correction solution in a multitude of systems and standards, such as wireless communications, wireline communications, and data storage systems. In the pursuit of codes with even higher coding gain, non-binary LDPC (NB-LDPC) codes defined over a Galois field of order q have risen as a strong replacement candidate. For codes defined with similar rate and length, NB-LDPC codes exhibit a significant coding gain improvement relative to that of their binary counterparts.Unfortunately, NB-LDPC codes are currently limited from practical application by the immense complexity of their decoding algorithms, because the improved error-rate performance of higher field orders comes at the cost of increasing decoding algorithm complexity. Currently available ASIC implementation solutions for NB-LDPC code decoders are simultaneously low in throughput and power-hungry, leading to a low energy efficiency.We propose several techniques at the algorithm level as well as hardware architecture level in an attempt to bring NB-LDPC codes closer to practical deployment. On the algorithm side, we propose several algorithmic modifications and analyze the corresponding hardware cost alleviation as well as impact on coding gain. We also study the quantization scheme for NB-LDPC decoders, again in the context of both the hardware and coding gain impacts, and we propose a technique that enables a good tradeoff in this space. On the hardware side, we develop a FPGA-based NB-LDPC decoder platform for architecture prototyping as well as hardware acceleration of code evaluation via error rate simulations. We also discuss the architectural techniques and innovations corresponding to our proposed algorithm for optimization of the implementation. Finally, a proof-of-concept ASIC chip is realized that integrates many of the proposed techniques. We are able to achieve a 3.7x improvement in the information throughput and 23.8x improvement in the energy efficiency over prior state-of-the-art, without sacrificing the strong error correcting capabilities of the NB-LDPC code.

Jan 1, 20160 citations

Complexity evaluation of non-binary Galois field LDPC code decoders

Timo Lehnigk-Emden, Norbert Wehn

Forward error correction is an essential part of digital communication systems. Non-binary low-density parity-check (NB-LDPC) codes have an excellent communications performance for short block lengths. The higher the field size is, the better the communications performance is. Non-binary LDPC codes can outperform all other state-of-the-art code classes. However, the algorithmic decoding complexity grows with the field size. For an intended, future use of these codes in real systems, an efficient hardware implementation is mandatory. Hardware architectures for binary LDPC codes are well investigated, but efficient implementation of non-binary LDPC decoders is still an open field. To the best of our knowledge, this paper studies for the first time the hardware implementation costs for non-binary LDPC decoders with Galois field sizes of 4, 16 and 256 on FPGA and a 65nm ASIC technology.

International Symposium on Turbo Codes and Iterative Information ProcessingSep 1, 201025 citations

Linear-time encoding and decoding of low-density parity-check codes

Mikael Simberg

Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.

Jan 20, 20150 citations

Decoder FPGA Implementation

Wojciech Sułek

The non-binary Low Density Parity Check (LDPC) codes over Galois Fields GF(q = 2 p ) have evolved from the binary LDPC codes that are today an industry standard for channel coding. The performance of short block length codes is significantly higher for non-binary LDPC, at the cost of increased decoding complexity. The efficient decoder hardware implementation is still a challenging task. Most of the recently proposed hardware realizations are ASIC-oriented as they employ multiplierless computation units. This article concerns a different decoder design approach that is specifically intended for an FPGA implementation. The reformulated mixed-domain FFT-BP decoding algorithm is applied that does not exclude the multiplication units. This allows mapping a part of the algorithm to the multiplier cores embedded in an FPGA. In this article we concentrate on the important issue of the proper selection of the numeric precision employed. We present the partially parallel extension of the mixed-domain decoder that operates for the structured codes. Then we carefully analyze the finite precision effects on the decoding performance. By simulation and synthesis results we show that it is advantageous to segment the decoder dataflow into 3 parts with different precision. The provided results also facilitate the precision selection for maximum performance or for some performance- complexity tradeoff. Index Terms—Error correcting codes, LDPC codes, Non- binary codes, Iterative decoder, Hardware decoder

Jan 1, 20150 citations

Decoder Design for Non-Binary LDPC Codes

Fei Liu, Haitao Li

Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate. In this paper, we give the different initial step for different modulation and present a hardware implementation of the extended min-sum (EMS) decoding algorithm for non-binary LDPC codes. Moreover, an FPGA simulation over GF(16) is given to demonstrate the efficiency of the presented techniques.

International Conference on Wireless Communications, Networking and Mobile ComputingSep 1, 20111 citation

A survey on decoding schedules of LDPC convolutional codes and associated hardware architectures

Hayfa Ben Thameur, Bertrand Le Gal, Nadia Khouja +2 more

Low-density parity-check convolutional codes (LDPC-CC) have interesting error correction features. They have a great potential to become a key error-correcting codes for enhancing reliability of modern digital communication systems, optical systems and storage devices. On the implementation side, however, the design of low-cost low-power and high-throughput LDPC-CC decoders remains challenging. This survey paper provides an overview of the state-of-the-art of different algorithmic optimizations proposed to ease and improve the LDPC-CC decoder implementations. To this end, a summary of the available decoding scheduling approaches is provided. Besides, a complexity analysis, performance comparison and an architectural analysis of LDPC-CC decoders based on different scheduling techniques is detailed.

IEEE Symposium on Computers and Communications (ISCC)Jul 1, 20178 citations