International Conference on Electronics and Information Engineering

A fixed bits LDPC decoder

Fen Xu, Liang Zhou, Hong Wen, Chen Huang, Qian Zhao

Published Aug 1, 2010• 0 citations

Abstract

With iterative decoding, most LDPC codes have a weakness known as error floor. In this work, we propose a fixed bits LDPC decoding scheme to improve the ability of LDPC transmission. The method is universal as it can be applied to any code/channel model/decoding algorithm and it improves performance greatly, without losing the code regularity, without changing the decoding algorithm. Simulation results show that the error floor performance also can be significantly improved with this decoding scheme.

DOI: 10.1109/iceie.2010.5559810

Related papers

Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

Dung Viet Nguyen

Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

Jan 1, 20121 citation

An improved two-stage iterative decoding of LDPC codes for Lowering error floors

Shuo-chen Wang, Atabaev Doniyor, Heejong Suh

In iterative decoding of LDPC codes ,from the phenomenon of error floors of LDPC code is mostly caused by an undesirable structure ,know as trapping set. In this paper, we propose a improved two-stage iterative decoding to break trapping sets. This algorithm is not need to observe all the error, only need to break which trapping set effect the effectiveness. Simulation results show that the error floor performance can be significantly improved with this decoding scheme.

대한전자공학회 학술대회Jun 1, 20140 citations

An efficient post processing scheme to lower the error floor of LDPC decoders

Wenjie Li, Jun Ting Lin, Zhongfeng Wang

Low-Density Parity-Check (LDPC) codes have extensive applications in numerous communication systems. However, iterative LDPC decoders may suffer from error floor. In this paper, a low complexity post processing scheme (PPS) is proposed to significantly improve the error correction performance of a Min-Sum based LDPC decoder in the error floor region. Instead of using trapping set elimination algorithms, the proposed PPS introduces perturbations so that a decoder can escape from undesired local maximums. After decoding failure, for these unreliable code bits, the proposed PPS generates carefully modified soft messages, which are employed in the following decoding iterations. Numerical results demonstrate that the presented PPS significantly lowers the error floor for simulated LDPC codes.

IEEE International Conference on Communication Technology (ICCT)Oct 1, 20174 citations

A Two-Stage Iterative Decoding of LDPC Codes for Lowering Error Floors

Jingyu Kang, Li Guo Zhang, Zhi Jun Ding +1 more

In iterative decoding of LDPC codes, trapping sets often lead to high error floors. In this work, we propose a two-stage iterative decoding to break trapping sets. Simulation results show that the error floor performance can be significantly improved with this decoding scheme.

GlobecomJan 1, 200816 citations

Lowering Error Floors of Systematic LDPC Codes Using Data Shortening

Sung-Rae Kim, Dong‐Joon Shin

In this paper, data shortening methods for lowering error floors of systematic LDPC codes are proposed. Rather than attempting to analyze trapping (or stopping) sets of a given LDPC code rigorously, we search information bits associated with dominant trapping (or stopping) sets of systematic LDPC codes through simulation under various channels. Then, proper information bits forming dominant trapping (or stopping) sets are selected and known values are assigned to them before encoding to weaken the effect of dominant trapping (or stopping) sets. To decode codewords, fixed known values are assigned to the selected information bits, which gives rise to the disconnection of some edges in dominant trapping (or stopping) sets. Through simulation, it is shown that the proposed schemes result in remarkably better performance, especially at the error floor region, than the base LDPC codes under various channels with negligible loss of code rate.

IEEE Communications LettersNov 19, 20136 citations

Techniques for the decoding of low density parity check codes: efficient simulation, algorithm improvement and implementation

Babak Daneshrad, Enver Çavuş

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.

Jan 1, 20072 citations