In a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Low–Density Parity–Check (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programming–based exact and heuristic decoding algorithms for its solution. In particular, we consider relax–and–fix heuristics that decode information in small windows. Computational results indicate that our approaches identify near–optimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.
In a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Low–Density Parity–Check (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programming–based exact and heuristic decoding algorithms for its solution. In particular, we consider relax–and–fix heuristics that decode information in small windows. Computational results indicate that our approaches identify near–optimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.
Low-density parity check (LDPC) codes, are a family of error-correcting codes, their performances close to the Shannon limit make them very attractive solutions for digital communication systems. There are several algorithms for decoding LDPC codes that show great diversity in terms of performance related to error correction. Also, very recently, many research papers involved the genetic algorithm (GA) in coding theory, in particular, in the decoding linear block codes case, which has heavily contributed to reducing the bit error rate (BER). In this paper, an efficient method based on the GA is proposed and it is used to improve the power of correction in terms of BER and the frame error rate (FER) of LDPC codes. Subsequently, the proposed algorithm can independently decide the most suitable moment to stop the decoding process, moreover, it does not require channel information (CSI) making it adaptable for all types of channels with different noise or intensity. The simulations show that the proposed algorithm is more efficient in terms of BER compared to other LDPC code decoders.
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.
The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.
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.
Digital communication has become part of most applications we use today.It could be for internet access using WLAN/WiMAX technology or satellite based Digital Video Broadcasting (DVB) or even mobile applications.It may be possible to achieve very high communication bandwidth for these applications.But the problem is with the reliability of information received over the communication channel that is often subjected to noise.The obvious solution to this problem is incorporating error correction techniques in the communication system to correct the errors introduced during transit.One of the best performing error correction codes are Low-Density Parity-Check (LDPC) codes discovered by Gallager in 1962, but these codes only gained popularity over the last decade or so.LDPC codes can achieve excellent bit error rate (BER) performance and are very suitable for next-generation communication systems.Studies have shown that large LDPC codes can achieve BER performance very close to the Shannon Limit.Hence these codes are of paramount interest among the research community.However, practical implementation of high performance LDPC decoders with large code lengths is a challenge faced by designers today due to the huge complexity and hardware resources required.This research aims to reduce the complexity of LDPC decoding algorithms and explore resource efficient architectures for hardware implementation.LDPC decoders are primarily based on iterative algorithms and typically consist of large number of computational nodes, with complex interconnections among the nodes.A fully-parallel implementation of LDPC decoder with large code length can provide high throughput, but is costly in terms of hardware resources required.Even today's high-end FPGAs
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area.
This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.