In modern data communication system Error Detection and Correction has great practical importance to maintain the data integrity across the noisy channel. To deal with this challenge, the theory of Error detection and correction need to get one's precise attention. To retrieve the original data, an efficient process is required. A class of error correcting codes which performs iterative decoding inside a graph is considered which can provide a good approximation. In this context Low Density Parity Check (LDPC) code comes with an excellent error correction performance. In this paper architecture and algorithms for Error Detection and Correction method based on LDPC code is proposed. Also, a simulator for the proposed algorithms is designed and tested successfully.
In modern data communication system Error Detection and Correction has great practical importance to maintain the data integrity across the noisy channel. To deal with this challenge, the theory of Error detection and correction need to get one's precise attention. To retrieve the original data, an efficient process is required. A class of error correcting codes which performs iterative decoding inside a graph is considered which can provide a good approximation. In this context Low Density Parity Check (LDPC) code comes with an excellent error correction performance. In this paper architecture and algorithms for Error Detection and Correction method based on LDPC code is proposed. Also, a simulator for the proposed algorithms is designed and tested successfully.
Encoding/decoding plays an important role in the reliability and success of modern data communication, as this becomes an integral part of our daily lives. However, by its inherent nature, the data communication systems are most vulnerable to errors. In communication, the errors mainly occur across the channels and its effect is very severe at times. Depending on the type of error, the code word transmitted across the channel can be partially or totally changed. So, the information transmitted can be lost permanently due to error. The concept of error correction is to introduce redundant data in the information during the transfer of data. The receiver can check the redundant data in the received message and can determine the consistency of the sent message. It can also check the redundant data to detect the transmitted errors in the message and can correct the errors if any. In this context, the principle of loopy Belief Propagation has been used by the Low-Density Parity Check (LDPC) codes. This code comes with an excellent error correction performance. The goal of this paper is to set up a framework to describe the LDPC code constraints, compute probabilities in trellises and finally generate transfer vectors for Loopy Belief Propagation model.
Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.
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.
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
Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.