Low-Density Parity-Check (LDPC) codes are used for channel coding in the 5G NR standard, where efficient decoding is essential for meeting the low-latency demands of modern wireless communication. As data traffic continues to grow, the computational cost of LDPC decoding becomes an increasingly important factor in system performance. In this thesis we investigate how the decoding time of LDPC decoding algorithms can be reduced through code optimization, without affecting decoding accuracy. Starting from an existing MATLAB codebase provided by Tieto, four algorithms were optimized: the Sum-Product Algorithm (SPA), the Min-Sum Algorithm (MSA), and their layered variants (LSPA and LMSA). Optimizations were applied in stages: code restructuring to eliminate redundant computations, vectorization to replace sequential loops with array operations, and early termination to allow the decoder to stop once a valid codeword is found. Each stage was evaluated against the original baseline by comparing decoding time and Block Error Rate (BLER) performance across a range of signal-to-noise conditions. The results show decoding time reductions of approximately 80 % for the SPA and 70 % for the MSA through code optimization alone. For the layered variants, the combined effect of optimization and vectorization reduced decoding time by approximately 85 % for the LSPA and 89 % for the LMSA. With early termination enabled, reductions of up to 96 % and 99 % were achieved for the LSPA and LMSA respectively. BLER performance remained consistent across all versions.
Low-Density Parity-Check (LDPC) codes are used for channel coding in the 5G NR standard, where efficient decoding is essential for meeting the low-latency demands of modern wireless communication. As data traffic continues to grow, the computational cost of LDPC decoding becomes an increasingly important factor in system performance. In this thesis we investigate how the decoding time of LDPC decoding algorithms can be reduced through code optimization, without affecting decoding accuracy. Starting from an existing MATLAB codebase provided by Tieto, four algorithms were optimized: the Sum-Product Algorithm (SPA), the Min-Sum Algorithm (MSA), and their layered variants (LSPA and LMSA). Optimizations were applied in stages: code restructuring to eliminate redundant computations, vectorization to replace sequential loops with array operations, and early termination to allow the decoder to stop once a valid codeword is found. Each stage was evaluated against the original baseline by comparing decoding time and Block Error Rate (BLER) performance across a range of signal-to-noise conditions. The results show decoding time reductions of approximately 80 % for the SPA and 70 % for the MSA through code optimization alone. For the layered variants, the combined effect of optimization and vectorization reduced decoding time by approximately 85 % for the LSPA and 89 % for the LMSA. With early termination enabled, reductions of up to 96 % and 99 % were achieved for the LSPA and LMSA respectively. BLER performance remained consistent across all versions.
This thesis investigates the acceleration of Low-Density Parity-Check (LDPC) decoding for 5G New Radio (5G NR) communication systems using NVIDIA Graphics Processing Units (GPUs) and the NVIDIA Sionna simulation framework. LDPC codes are widely used in modern wireless communication systems, including 5G NR, because of their strong error-correction capabilities. However, the decoding process is computationally intensive since it relies on iterative algorithms that require multiple rounds of calculations before a final decoding decision can be made. As communication systems continue to demand higher data rates and lower latency, improving the efficiency of LDPC decoding has become increasingly important. A complete LDPC-based communication system was implemented using Sionna. The system included Cyclic Redundancy Check (CRC) encoding, LDPC encoding, modulation, transmission through an Additive White Gaussian Noise (AWGN) channel, demodulation, LDPC decoding, and CRC decoding. Three LDPC decoding algorithms were evaluated: Sum-Product Algorithm (SPA), Min-Sum Algorithm (MSA), and Offset Min-Sum Algorithm (OMSA). The study focused on measuring decoding performance on NVIDIA GPUs and investigating optimization techniques that could reduce LDPC decoding execution time while maintaining reliable decoding performance. Two optimization techniques were implemented and evaluated: CRC-based early termination and Accelerated Linear Algebra (XLA) graph compilation. Early termination allowed the LDPC decoder to stop before reaching the maximum number of decoding iterations. XLA was used to improve the efficiency of the computations executed during LDPC decoding. The performance of the optimized implementations was compared with a baseline implementation across different signal-to-noise ratio (SNR) values. The results showed that both optimization techniques reduced decoding execution time, while maintaining reliable Block Error Rate (BLER) performance compared to the baseline scheme.
Over the last ten years, there has been an incremental growth of mobile network data traffic. The evolution leading to the development of 5G stands as a testament to the increased demands for high speed networks. Channel coding plays a pivotal role in 5G networks, making it possible to recover messages from errors introduced when sent through the network. Channel decoding is however a time consuming task for a receiver, and making optimization to this process could therefore have a significant impact on receiver processing time. Low-Density Parity-Check (LDPC) codes are one of the channel coding schemes used in the 5G standard. These codes could benefit from parallel processing, making Graphics Processing Units (GPUs) with their parallel computation abilities a possible platform for effective LDPC decoding. In this thesis, our goal is to evaluate a GPU as a platform for 5G LDPC decoding. The LDPC codes adhering to the 5G standard belong to the Quasi-Cyclic LDPC (QC-LDPC) subclass. Optimizations targeting this subclass, as well as other optimization techniques, are implemented in our thesis project to promote fast execution times. A GPU-based decoder is evaluated against a Central Processing Unit (CPU)-based decoder, written with Compute Unified Device Architecture (CUDA) and C++ respectively. The functionally equivalent decoders implement the layered offset Min-Sum Algorithm (MSA) with early termination to decode messages. Execution time for the decoders were measured while varying message size, Signal-to-Noise Ratio (SNR) and maximum iterations. Additionaly, we evaluated the decoders with and without including early termination, and also evaluated the GPU-decoder when it was integrated into a MATLAB 5G channel simulator used by Tietoevry. The results from the experiments showed that the GPU-based decoder experienced up to 4.3 times faster execution than the CPU-based decoder for message sizes ranging from 3000-12000 bits. The GPU-based decoder however experienced a higher baseline execution time, making the CPU-based decoder faster for smaller message sizes. It was also concluded that the benefit of including early termination in the decoder generally outweighs the cost of additional processing time.
Two methods are proposed to reduce the complexity of the belief propagation (BP) decoding for low-density parity-check (LDPC) codes, with the focus on the layered decoding for quasi-cyclic LDPC (QC-LDPC) codes. The two methods can be separately incorporated into the layered decoding procedures and combined seamlessly to provide the two-fold complexity reduction. In the first method, the message updates regarding a subset of variable nodes are omitted. To construct the subset, the most reliable bit-level channels, derived fromM-ary input channels, are identified. Then, we select the variable nodes with initial log-likelihood ratios (LLRs) exceeding a threshold among the ones assigned to the most reliable bit-level channels to form the subset. The threshold is designed and adjusted based on characteristics of the most reliable bit-level channels. Our numerical results demonstrate that the first method significantly reduces the complexity with negligibly impacting the error-correcting performance. In the second method, each layer of base graphs of QC-LDPC codes uses either sum-product algorithm (SPA) or min-sum algorithm (MSA) to update LLRs. A degree-based algorithm is presented to determine the layers employing either SPA or MSA. We compare with two intuitive methods: 1) applying SPA to randomly selected layers and MSA to the remaining layers, and 2) applying SPA to the core layers of 5G NR LDPC codes and MSA to the remaining layers. According to the numerical results, the degree-based algorithm maximally reduces the complexity while maintaining the same performance. To evaluate the joint method, the first method is applied on top of the second method. Further complexity reduction is achieved without degrading the performance of the second method.
In this work, iterative decoders for Low-Density Parity-Check (LDPC) codes are analyzed and optimized for low computational complexity. LDPC block codes are now widely used in industry standards such as Wi-Fi or 5G New Radio (NR). Hence, there is a strong need for decoder concepts suitable for hardware designs. In addition, terminated LDPC convolutional codes are promising candidates for next-generation communication systems. The main theme of this work is to investigate low-overhead strategies for reducing the computational complexity of iterative decoders. Two aspects are considered for fast decoding of the LDPC block codes in 5G NR. Firstly, an efficient but simple-to determine update schedule for the iterative decoding process, i.e., the sequence of updates on different parts of a codeword, is proposed. Secondly, Early Termination (ET), i.e., an option to stop decoding before a maximal number of iterations is exhausted, is improved in two ways: On the one hand, a partial evaluation of the code’s Parity-Check (PC) equations speeds up the detection of valid codewords. On the other hand, a novel criterion detects when the decoding process is unlikely to converge and stops the decoding before a lot of resources are wasted on futile iterations. The combination of all techniques results in a decoder with significant reduction of the computational complexity compared to a decoder without these methods. Still, only few additional residual decoding errors are produced. This work also contains an analysis of various aspects of a Windowed Decoder (WD), which is a specialized decoder design for LDPC convolutional codes. A WD can be configured in even more ways than a decoder for block codes. The analysis in this work assumes a normalization of the computational complexity to a certain maximal value. With this setup, it is shown that a larger size of the decoding window may be preferable over a smaller size to minimize the computational complexity. Furthermore, various window update strategies (determining in which way the code symbol reliabilities are updated in each window) and variations of ET are compared to identify a well-suited WD configuration. Lastly, strategies with Dynamic Scheduling (DS) are considered to further reduce the computational complexity. A novel fixed approach derived from several DS strategies performs well without actual dynamic knowledge of the decoder state. All in all, the optimized WD configuration halves the computational complexity of a block decoder while maintaining an acceptable loss in the decoding performance measured by the number of residual decoding errors. A comparison of systems with Hybrid Automatic Repeat reQuest (HARQ) expands the scope of this work into the domain of error control by retransmissions. The analyzed systems make use of the decoder output, e.g., the final code-symbol reliabilities, to assemble dynamic retransmissions that are as short as possible and contain specifically selected code symbols. These systems stand in contrast to contemporary implementations of HARQ that only use imprecise feedback messages. Still, some compatibility with existing systems is achieved by assuming a limited feedback channel, which requires clever compression of the feedback information. A novel HARQ system is proposed, which evaluates the code’s PC equations to avoid the computational overhead of soft-value processing. The throughput with the proposed system is found to be improved compared to a reference system that evaluates code-symbol reliabilities. Finally, approximations of the accurate message-update rules of the Sum–Product Algorithm (SPA) are analyzed. With fixed-point arithmetic, Look-Up Tables (LUTs) are a promising approach to approximate functions that are costly to compute. It is shown that an optimized LUT with just nine entries can be used in a fixed-point decoder such that the decoding performance is close to that of a floating-point decoder with accurate message updates.
Channel coding technique is a fundamental building block in any modern communication system to realize reliable, fast, and secure data transmission. At the same time, it is a challenging and crucial task, as the data transmission happens in a channel where noise, fading, and other impairments are present. The Low-Density Parity-Check (LDPC) codes give substantial results close to the Shannon limit when the complexity and processing delay time are unlimited. In this paper, the performance of the LDPC decoding with four algorithms was investigated. The investigated four algorithms were Belief Propagation (BP), Layered Belief Propagation (LBP), Normalized min-sum (NMS), and Offset min-sum (OMS). These algorithms were examined for code rates ranging from 1/3 to 9/10 and message block lengths (64, 512, 1024, and 5120) bits. The simulation results revealed the flexibility of these decoders in supporting these code rates and block lengths, which enables their usage in a wide range of applications and scenarios for fifth-generation (5G) wireless communication. In addition, the effect of the maximum number of decoding iterations on the error correction performance was investigated, and a gain of 5.6 dB can be obtained by using 32 decoding iterations at BER=2*10-3 instead of one decoding iteration. The results showed that the decoders performed better for longer message blocks than for short message blocks, and less power was required for transmitting longer messages. Finally, the comparison results of their performance in terms of bit error rate (BER) under the same conditions showed a gain of 0.8 dB using LBP at BER= 10-5 compared with the NMS decoding algorithm.
5G technology new radios (5G NR) require high-speed decoders that operate on highly irregular low-density parity-check (LDPC) codes.LDPC decoders have gained significant attention due to their excellent error correction performance.This study evaluates on different algorithms and scheduling techniques used for LDPC decoders.The analysis highlights that Min-Sum-based approaches can reduce the computational complexity compared to the basic sum-product algorithm, while the normalized and extended Min-Sum algorithms provide a better trade-off owing to their accurate value assumptions.Furthermore, different scheduling methods are implied for MS to improve speed and reduce latency.This study provides a comparative analysis of the algorithms and architectures that yield high throughputs without compromising performance efficiency.The LNMS algorithm with a data-level rescheduling technique resolves data dependency issues.This resolves the complexity of CN and VN and improves the throughput, making it suitable for 5G NR applications.The decoded throughput achieved with this scheduling is 7.0 Gbps.This throughput is achieved by maintaining the standard parameters and worst case parameters, such as four/eight iterations, BG1, and a code rate of 0.8/0.5.The evaluated architectures are implemented on Field Programmable Gate Array (FPGA) devices.This study aids in selecting the optimal architecture and scheduling techniques for LDPC decoders by considering various performance standards to deploy wireless networks in 5G and beyond.