Advances in Electrical and Electronic Engineering

Hardware Implementation Analysis of Min-Sum Decoders

Rajagopal Anantharaman, Karibasappa Kwadiki, Vasundara Patel Kerehalli Shankar Rao

Published Jun 22, 2019• 5 citations

Abstract

The objective of this work is to propose a modified Min-Sum decoding Low Density Parity Check (LDPC) algorithm and perform the hardware implementation analysis of Min-Sum, optimized Min-Sum and modified Min-Sum decoders. The Min-Sum algorithm mainly uses the process of finding the minimum and addition. Hence the number of multiplications is drastically reduced which helps in reducing the complexity of implementation. Adding an optimisation factor to the decoder increases the accuracy and reduces the number of iterations required to compute the decoded message. Hence the process of optimisation reduces the overall decoding time required. Modified Min-Sum algorithm is proposed to further improve the performance by decreasing the number of stages in the decoding process which reduces the complexity in Field Programmable Gate Array (FPGA) implementation.

DOI: 10.15598/aeee.v17i2.3042

Related papers

Reduced-Complexity Min-Sum Algorithm for Decoding LDPC Codes With Low Error-Floor

F. Angarita, Javier Valls, Vicenç Almenar +1 more

This paper proposes a low-complexity min-sum algorithm for decoding low-density parity-check codes. It is an improved version of the single-minimum algorithm where the two-minimum calculation is replaced by one minimum calculation and a second minimum emulation. In the proposed one, variable correction factors that depend on the iteration number are introduced and the second minimum emulation is simplified, reducing by this way the decoder complexity. This proposal improves the performance of the single-minimum algorithm, approaching to the normalized min-sum performance in the water-fall region. Also, the error-floor region is analyzed for the code of the IEEE 802.3an standard showing that the trapping sets are decoded due to a slow down of the convergence of the algorithm. An error-floor free operation below BER=10-15is shown for this code by means of a field-programmable gate array (FPGA)-based hardware emulator. A layered decoder is implemented in a 90-nm CMOS technology achieving 12.8 Gbps with an area of 3.84 mm2.

IEEE Transactions on Circuits and Systems I Regular PapersFeb 18, 201472 citations

Improved LDPC decoding algorithms based on min-sum algorithm

Y.V. A. C. Kumara, Chandika Bandara Wavegedara

Low-Density Parity check (LDPC) codes offer high-performance error correction near the Shannon limit which employs large code lengths and some iterations in the decoding process. The conventional decoding algorithm of LDPC is the Log Likelihood Ratio based Belief Propagation (LLR BP) which is also known as the `Sum-Product algorithm' which gives the best decoding performance and requires the most computational complexity and implementations with increased hardware complexity. Another simpler variant of this algorithm is used which is known as `min-sum algorithm' which reduces computational complexity as well as hardware complexity but with reduced accuracy. This paper analyzes the reason min-sum algorithm is more prone to errors when compared to the sum-product algorithm, and puts forward two improved algorithms which improve the performance of the min-sum algorithm with comparable algorithmic complexity.

Moratuwa Engineering Research Conference (MERCon)Apr 1, 20168 citations

Design and implementation of decoders for error correction in high-speed communication systems.

Joan Marc Català Pérez

This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.

Jul 7, 20170 citations

Enhancing Data Communication Performance: A Comprehensive Review and Evaluation of LDPC Decoder Architectures

Maryam Imad Subhi, Qusay Al-Doori, Omar Alani

Error Correction Codes (ECCs) stand as a linchpin in ensuring data accuracy in wireless communication.As the landscape of modern communication standards continues to expand, there is a mounting inclination towards efficient ECC technologies, such as Low-Density Parity-Check codes (LDPCs).Distinguished by their near-capacity performance and low computational complexity, LDPCs are increasingly utilized in the successful encoding and decoding of data.This study undertakes an exploration of recent advancements in LDPC research, encompassing the analysis of decoding algorithms, architectures, applications, simulations, real-world implementations, and complexities across various hardware platforms.The central research problem addressed within this work is the identification of the most efficacious LDPC decoder implementation, with an emphasis placed on Field-Programmable Gate Array (FPGA) technology.From the outcomes of this study, the Min-Sum algorithm emerged as the favored choice for LDPC decoding, particularly within FPGA implementations.The selection of this algorithm is attributable to its simplicity and implementation feasibility, thus directly addressing the posed research problem.The inherent simplicity of the Min-Sum algorithm's structure renders it a practical choice for real-world applications.Further, its proficiency in error correction and compatibility with FPGA hardware underscore its potential for augmenting the reliability of data transmission in communication systems.The findings of this study advocate for the Min-Sum algorithm as a valuable asset in LDPC decoding, notably within FPGA implementations.This positions it as a promising candidate for optimizing data communication systems.The selection of FPGA as the implementation platform reaffirms its practicality and relevance in contemporary communication technology, thus offering a comprehensive solution to the identified research problem.

Ingénierie des systèmes d informationOct 31, 20234 citations

A modified Min-Sum algorithm for low-density parity-check codes

Wei Han, Jianguo Huang, WU Fang-fei

A modified Min-Sum algorithm for low-density parity check codes is proposed in this paper. The inaccurate check node messages of the Min-Sum algorithm compared to the belief propagation (BP) algorithm are compensated by modified variable node messages, which is different from the normalized Min-Sum algorithm. The modified factor is obtained before decoding program and only one extra multiplication is needed in one cycle. So the increased complexity is fairly low. The simulation results show that the bit error rate (BER) and average number of iteration of the modified Min-Sum algorithm are very close to the BP algorithm, the modified algorithm can improve the BER performance compared to the Min-Sum algorithm while added complexity slightly.

Wireless Communications, Networking and Information SecurityJun 1, 20109 citations

Efficient Implementation of a Threshold Modified Min-Sum Algorithm for LDPC Decoders

Yanfang Liu, Wei Tang, David G. M. Mitchell

In this brief, we present a hardware efficient implementation of a threshold modified min-sum algorithm (MSA) to improve the performance of a low density parity-check (LDPC) decoder. The proposed architecture introduces a novel lookup table based threshold attenuation technique, called threshold attenuated MSA (TAMSA). The proposed TAMSA implementation is shown to improve bit error rate (BER) performance compared to the conventional AMSA and MSA. Furthermore, a layered version of the TAMSA implementation is investigated to reduce hardware cost. Utilizing circuit optimization techniques, including a parallel computing structure, the proposed layered TAMSA field-programmable gate array (FPGA) implementation results show that the modified architecture requires no extra circuit power or circuit area compared to conventional AMSA, and only 0.07% extra leaf cells compared to conventional MSA.

IEEE Transactions on Circuits & Systems II Express BriefsJun 11, 202018 citations