Design and Implementation of a High-Reliability Min-Max Algorithm for LDPC Decoder on FPGA

Ⅰ. Introduction

Due to the remarkable advancements in communication technology and computer performance, Low-Density Parity-Check (LDPC) codes have been adopted as standards in various digital communication systems, such as storage systems^[1-3] and IEEE 802.11n, 802.3m, 802.16a^[4-6]. Recently, in situations where some error correction capabilities of the code may be lost or when the channel is modeled as a Binary Symmetric Channel (BSC), hard-decision decoders are being prioritized over soft-decision decoders. These algorithms use only binary symbols received from the channel during the initialization phase. Based on these symbols, methods such as voting or flipping are employed^[7].

Additionally, Sum-Product algorithms and Min-sum algorithms use the log-likelihood ratio (LLR) of the received symbols during the initialization phase. As a result, research continues on balancing decoder performance with computational complexity.

When Robert Gallager first introduced parity-check codes in 1962^[8], they did not attract much attention because the code lengths were too long, and the decoder algorithms were too complex. However, due to their simple decoding advantage, LDPC codes have been adopted as decoders in digital communication standards, such as 5G communication systems. In the Min-max algorithm^[9], the complexity of the algorithm is further reduced at the cost of slightly lower coding gain. In this algorithm, 'maximum' is performed instead of 'sum.' In [10] proposed an architecture for the Min-max algorithm that retains all messages, which can result in large memory requirements if the order of the finite field is not small. Additionally, this architecture incurs very long delay times because it calculates all possible combinations of field elements in each message vector. A parallel Min-max algorithm architecture was also developed in [11]. Although this architecture achieves high speed, it requires a large area due to the high level of parallelism. Moreover, its efficiency decreases when the order of the finite field is large or the code rate is low. In [12, 13] is proposed two decoding algorithms and architectures for the Min-max algorithm, both of which significantly reduce decoding complexity.

Recent research trends focusing on LDPC codes are actively progressing in various fields. In particular, various studies are being conducted to improve the performance and practical applications of Quasi-Cyclic LDPC(QC-LDPC)^[14], binary LDPC, and Non-Binary LDPC (NB-LDPC) codes. This study aims to optimize the Min-max algorithm, one of the NB-LDPC codes, and verify its advantage of high error correction capability. Hard-decision decoding has lower complexity than soft-decision decoding, but generally offers reduced error correction performance. However, the proposed High Reliability Min-max Algorithm aims to improve decoding accuracy and efficiency by systematically reducing processing complexity using the LLR of soft-decision decoding. To reduce the high computational complexity of NB-LDPC, we simplified the structure and overcame the difficulties in hardware implementation through an intuitive architectural design. Section 2 presents the software design and simulation of this study. Section 3 describes the hardware design and implementation. Section 4 contains the conclusion.

Ⅱ. Software Design & Simulation

2.1 Min-max Algorithm

To explain the Min-max algorithm, the message vector coming from variable nodes to a check node can be represented as a tree structure composed of multiple stages. Each stage represents an element of the variable-to-check message vector, and the nodes of each stage are arranged in the order of finite field elements [TeX:] $$0,1,2, \ldots, \mathrm{q}-1$$ Fig. 1 shows the trellis structure for [TeX:] $$V_d=6 \text { and } \mathrm{q}=4 .$$ The variable-to-check message vector for a single check node [TeX:] $$u_{m, n}\left(v_{m, n}\right)$$ is simply denoted as [TeX:] $$u_j\left(v_j\right)\left(0 \leq j\lt d_c\right) .$$ using this trellis representation of the variable-to-check messages, when calculating the check-to-variable message at [TeX:] $$v_j,$$ a path that passes through one node at each stage is found. However, the j-th stage is excluded. The LLR of the path is the maximum value of the LLRs of the nodes in the path, and the finite field element is the sum of the finite field elements of the nodes. Fig. 2 shows several paths for calculating [TeX:] $$v_{d c-1}$$ using the method proposed in this paper, showing the LLR and finite field elements of each path. The optimal path for [TeX:] $$u_j(\alpha)$$ is the path with the minimum LLR among the paths where the finite field element is [TeX:] $$\alpha \text {, and } u_j(\alpha)$$ is equal to the LLR value of this optimal path.

Fig. 1.

Message trellis from variable to check: The original trellis structures

Fig. 2.

Message trellis from variable to check: The rearranged trellis structures

Additionally, to simplify the algorithm, the variable- to-check message vector rearrangement technique proposed in [15] was adopted. Assuming that the element representing the most reliable message is [TeX:] $$\hat{\alpha}_j, u_j$$ is rearranged to [TeX:] $$\hat{\alpha}_j.$$

2.2 High Reliability Min-max Algorithm

The proposed High Reliability Min-max Algorithm aims to enhance decoding accuracy and efficiency by systematically reducing the complexity of processing. The process involves several key steps:

The initialization phase begins by calculating the sum of alpha values across all codeword positions, denoted as [TeX:] $$\alpha_{\text {sum }},$$ by summing the alpha values for each position j from 0 to [TeX:] $$d_c-1 .$$

In the first stage, initial values are computed for each position j within the codeword. For any given [TeX:] $$0 \leq j \lt d_c,$$ the initial values [TeX:] $$\widetilde{u}_j(\beta)$$ are determined by checking if β is equal to the bitwise combination of the estimated alpha value at position j and another alpha value.

The second one involves identifying the minimum and second minimum LLRs for each possible value of β. The minimum LLRs, [TeX:] $$\boldsymbol{M}_{\text {first_min}},$$ are the smallest LLR values along with their corresponding positions, and the second minimum LLRs, [TeX:] $$\boldsymbol{M}_{\text {second_min}},$$ are the second smallest LLR values.

In the third, vectors [TeX:] $$m_j(\beta)$$ associated with each codeword position j are constructed. For each j, the vectors consist of LLR values [TeX:] $$m_j(\beta)$$ for each β from 1 to q. The LLR value [TeX:] $$m_j(\beta)$$ is taken from [TeX:] $$m 1(\beta)$$ j is not equal to [TeX:] $$I(\beta)$$, and from [TeX:] $$m 2(\beta)$$ if j is equal to [TeX:] $$I(\beta)$$.

The fifth is the construction of the minimum basis [TeX:] $$B_j$$ for each codeword position j. The minimum basis is derived using the sorted vector [TeX:] $$\bar{M}_j$$ and consists of the smallest p elements from [TeX:] $$\bar{M}_j$$, ensuring that each element is independent of the others.

In the sixth, the algorithm calculates the values [TeX:] $$\hat{v}_j$$, for each position j. The initial value [TeX:] $$\hat{v}_j$$ is set to 0, and for each β, the value [TeX:] $$\hat{v}_j(\beta)$$ is computed as the maximum of the LLR values of the elements in the basis Bj, combined with their corresponding field elements.

Finally, in the seventh step, the final values [TeX:] $$v_j$$ are derived for each position j. This is done by aligning the computed values [TeX:] $$\hat{v}_j(\beta)$$ with the initial alpha values. If α is equal to β combined with [TeX:] $$\alpha_\text{sum}$$ and the estimated alpha value at position j, then [TeX:] $$v_j(\alpha)$$ is set to [TeX:] $$\hat{v}_j(\beta)$$.

This structured approach effectively reduces computational complexity while maintaining high reliability in the Min-max algorithm's decoding process. By leveraging organized LLR processing and careful management of message vectors, the proposed algorithm offers a robust solution for improving decoding efficiency in error correction coding systems. The proposed algorithm is defined in Fig. 3.

Fig. 3.

High Reliability Min-max Algorithm

In conclusion, unlike the existing Min-max algorithm, which transmits messages based on the maximum LLR (Log-Likelihood Ratio) value for each path, the High Reliability Min-max algorithm considers the second minimum LLR value, allowing for a more refined path selection process.

The High Reliability algorithm systematically reduces computational complexity by utilizing a minimum basis and reorganizing the message vectors based on β values, offering a more efficient processing flow compared to the existing algorithm. Additionally, the High Reliability approach improves decoding accuracy by calculating the minimum basis at each codeword position to select the optimal path, whereas the existing Min-max algorithm does not include such additional basis calculations.

In fig. 4 compares repetition codes under soft-decision and hard-decision decoding. It demonstrates that soft-decision decoding achieves a lower error probability. In comparison to the (4191, 3602) binary LDPC code, the (837, 726) Min-Max code offers notable advantages due to its shorter length. The reduced length of the (837, 726) Min-Max code implies greater transmission efficiency, as the same level of error correction performance can be achieved with fewer resources. This translates to reduced bandwidth usage and lower power consumption, which are critical factors in many communication systems. Furthermore, the shorter code length also leads to lower decoding complexity, reducing the demand on both hardware and software resources. This reduction in complexity is especially advantageous for real-time communication systems, where rapid and efficient decoding is essential. Overall, the (837, 726) Min-Max code, with its shorter length and lower complexity, provides a more efficient solution while maintaining error correction performance comparable to the longer LDPC codes. In Fig. 5, the proposed High Reliability Min-Max Algorithm, implemented using the soft-decision method described in [14], demonstrates performance similar to the (4191, 3602) binary LDPC code. This comparison highlights the superior performance of the proposed approach in terms of error correction, as it maximizes error correction capability by addressing the limitations of hard-decision decoding methods. Thus, the proposed algorithm achieves high reliability while maintaining efficient processing, further proving its effectiveness in enhancing overall decoding performance.

Fig. 4.

Performance of repetition code using hard-and soft-decision decoding[ 16]

Fig. 5.

FER of the (837, 726) Min-Max code and the (4191, 3602) binary LDPC code over the AWGN channel

Ⅲ. Hardware Design and Verification

The proposed design first sorts a limited number of v-to-c messages with the highest reliability, then derives the c-to-v messages from the sorting results using a path construction procedure without storing other intermediate messages. This algorithm consists of a total of 8 stages, where the output of each stage is used as the input for the next stage. We describe the input and output values for each stage and detail the operations according to the given algorithm. The ultimate goal is to recover the alpha value. In the step-by-step explanation, the initialization phase calculates [TeX:] $$\alpha_\text{sum}$$ by performing an XOR operation on [TeX:] $$\hat{\alpha} \text{ and } \alpha.$$ This value is used as an input in subsequent stages. In the first stage, [TeX:] $$u_j(\beta)$$ is obtained by performing an XOR operation on [TeX:] $$\hat{\alpha} \text{ and } \alpha,$$ and in the second stage, the minimum and second minimum values among several [TeX:] $$u_j(\beta)$$ values are selected to obtain [TeX:] $$\boldsymbol{M}_{\text {first_min}} \text { and } \boldsymbol{M}_{\text {second_min}} \text {. }$$ In the third stage, [TeX:] $$m_j(\beta)$$ is calculated using [TeX:] $$\boldsymbol{M}_{\text {first_min}} \text { or } \boldsymbol{M}_{\text {second_min}} \text {. }$$ In the fourth stage, [TeX:] $$m_j(\beta)$$ values are sorted to obtain data_out, and in the fifth stage, the data_out values are set as the final message and alpha_out.

In the sixth stage, max_value and xor_result is calculated using data_in and alpha_in, and these values are used to obtain [TeX:] $$\alpha_\text{sum}$$. Finally, in the seventh stage, v_out is calculated using max_value, xor_result, and [TeX:] $$\alpha_\text{sum}$$. Through this process, the original alpha value can be recovered.

Fig. 6.

Hardware Architecture of Proposed Algorithm

Fig. 7.

Timing Diagram of the Proposed Architecture

Fig. 8.

Simulation Result using EDA Tool

The FPGA design process for the Min-Max algorithm began as presented in Fig. 9. Using the Very High-Speed Integrated Circuit Hardware Description Language (VHDL), an LDPC decoder based on the high-reliability Min-Max algorithm was implemented, and a Finite State Machine (FSM) was designed to precisely control the decoding process. Through Register Transfer Level (RTL) simulation, it was confirmed that the input value “1101010101” was correctly decoded to the output “110101.” The simulation results were consistent with the expected hardware behavior, and the output signal was verified using an oscilloscope. Fig. 10 illustrates how the designed circuit was placed on the Cyclone 10GX 10CX085YF672E5G chip. After downloading the program to the FPGA, the actual hardware operation was confirmed through the test process presented in Fig. 11. The design operated at 119.37 MHz and utilized 348 LUTs and 255 flip-flops to achieve optimal hardware performance. The test results matched the simulation, and the output signals were accurately verified using the oscilloscope. From a hardware perspective, the proposed design applied parallel processing and a pipeline structure to reduce hardware complexity and maximize performance. XOR operations and optimized lookup tables (LUTs) were used to accelerate the key computational steps of the Min-Max algorithm. Additionally, multiple arithmetic logic units (ALUs) were arranged in parallel to efficiently handle high-complexity operations such as comparison and sorting. These optimizations, combined with the inherent parallel processing capabilities of the FPGA, significantly improved throughput while minimizing resource usage.

Fig. 9.

FPGA Design Flow for Min-max Algorithm

Fig. 10.

Chip Layout of FPGA

Fig. 11.

Test Process for the Programmed FPGA

Additionally, in the software implementation, as shown in Fig. 12, a 6-bit output was generated from a 10-bit input using the C programming language. The software verification results were consistent with the FPGA hardware implementation, confirming that the proposed algorithm was accurately implemented in both software and hardware.

Fig. 12.

Actual Test Result using C language

Moreover, the bit error rate (BER) calculation function was implemented using the calculate_ber function, which compares the input bits with the decoded bits and calculates the proportion of incorrectly decoded bits. This function compares the decoded bits with the final output to compute the error rate. In the current execution, the BER was computed to be 0.000010 according to the 5G standard, as shown in the console output.

Additionally, the throughput calculation function was implemented using the calculate_throughput function, which measures the program's execution time and calculates the number of bits processed per second. Based on the input frequency of 200 MHz, the program recorded a throughput of 119.37 MHz.

Fig. 13 illustrates that in terms of resource usage, this paper significantly reduces the consumption of FFs and LUTs, maximizing resource efficiency, whereas in [17] utilizes more resources to achieve higher performance. In terms of performance, the earlier design achieves a throughput of 165.787 MHz by employing more resources, while this paper minimizes resource usage while still maintaining an adequate performance of 119.37 MHz Furthermore, in terms of design objectives, the earlier approach prioritizes performance, accepting higher resource consumption, whereas this paper emphasizes resource-saving while still delivering efficient performance. Thus, in [17] is suitable for environments where performance maximization is critical, even if it requires significant resource consumption, while the design proposed in this paper offers an optimal solution for environments where hardware constraints necessitate resource efficiency while maintaining adequate performance.

Fig. 13.

Comparative Analysis of Different LDPC Decoder Designs

Ⅳ. Conclusions

Hard-decision decoding generally has lower complexity than soft-decision decoding, but it typically offers reduced error correction performance. However, the proposed High Reliability Min-Max Algorithm seeks to enhance decoding accuracy and efficiency by leveraging Log-Likelihood Ratio (LLR) to systematically reduce processing complexity. In this paper, we present a decoder based on this algorithm, which is a type of NB-LDPC. By utilizing the strengths of NB-LDPC's low computational complexity, we have developed an efficient algorithm. The proposed Min-Max Algorithm demonstrated excellent error correction performance in simulations. In future work, we aim to further validate the performance through Application-Specific Integrated Circuit (ASIC) implementation and compare it with other existing methods.