IEEE Vehicular Technology Conference

On the Threshold of Right Regular LDPC Codes for the Erasure Channel

Enrico Paolini, Marco Chiani

Published Dec 10, 2005• 3 citations

Abstract

We provide an analytical expression for the threshold for right regular low-density parity-check (LDPC) codes for the erasure channel (EC), under message passing decoding. We first develop an expression for the threshold for regular LDPC codes, alternative to that already available in the literature; then we generalize it for the class of right regular codes. Thus, we show that the problem of computing the threshold can be reduced to the search for the fixed points of a function depending only on the variable nodes degree distribution, /spl lambda/(x), and on the uniform weight, d/sub c/, of check nodes. Finally, we show the application of our analysis to a class of capacity-approaching right regular LDPC codes.

DOI: 10.1109/vetecs.2005.1543375

Related papers

Exact thresholds for low-density parity-check codes over the binary erasure channel

Jianjun Mu, Xiaopeng Jiao, Xinmei Wang

A simple method for determining the threshold of irregular LDPC codes over the binary erasure channel (BEC) under message-passing decoding is proposed. An exact formula for calculating the threshold of irregular LDPC codes over the BEC is proved. This generalizes the known result on the threshold of regular LDPC codes to irregular LDPC codes. Moreover, our new method can avoid the computation of the inverse of the degree distribution function for irregular LDPC codes. Numerical results demonstrate the correctness of our proposed method.

Progress in Natural Science Materials InternationalApr 29, 20091 citation

Analytic Expressions of Decoding Thresholds for LDPC Codes Over BEC

Meilin He, Haiquan Wang, Zhirui Hu +1 more

Analytic expressions of decoding thresholds both for regular and irregular low-density parity-check (LDPC) codes over the binary erasure channel (BEC) are given, and low-complexity methods for determining the thresholds are proposed based on the analytic expressions. Specifically, firstly, a fixed-point equation, which represents a constraint relationship between the threshold and erasure probability of transmitted bits, is established. Secondly, by introducing an auxiliary equation, the threshold can be solved as an analytically function of solutions of a polynomial equation. Moreover, this method is extended to the Additive White Gaussian Noise (AWGN) channel. Numerical results show that, our proposed method is more accurate, and the complexity is much lower than that of conventional density evolution (DE). Moreover, our method does not require to compute the inverse of degree distribution function for irregular LDPC codes.

IEEE Communications LettersDec 11, 20200 citations

Analysis of threshold of regular and irregular LDPC codes using Gaussian approximation

Chia‐Lu Ho

We present the formulas for searching for the thresholds of regular and irregular low-density parity-check (LDPC) codes under message-passing (MP) algorithm. A Gaussian approximation is applied to studying the evolution of the means of the messages of the variable nodes and the check nodes. Accurate numerical integration methods by using transformations are shown for evaluating the expected values of the message of the check nodes. Tables are built first and interpolations are used for further evaluations. Two curves are used to locate the threshold. We utilize an iterative decoding tunnel between these two curves and study the decoding performance by evaluating conditions of the derivatives of these two curves. Using this method the performance of both regular and irregular LDPC codes can be studied in a unified manner without using simulation.

Wireless Telecommunications SymposiumMay 1, 20092 citations

Bounds on Achievable Rates of LDPC Codes Used Over the Binary Erasure Channel

Ohad Barak, David Burshtein, Meir Feder

We derive upper bounds on the maximum achievable rate of low-density parity-check (LDPC) codes used over the binary erasure channel (BEC) under Gallager's decoding algorithm, given their right-degree distribution. We demonstrate the bounds on the ensemble of right-regular LDPC codes and compare them with an explicit left-degree distribution constructed from the given right degree.

IEEE Transactions on Information TheorySep 28, 200420 citations

Noise Thresholds for Discrete LDPC Decoding Mappings

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.

GlobecomJan 1, 200851 citations

Capacity-Approaching Low-Density Parity-Check Codes

Pierre J. Garrigues

The class of low-density parity-check (LDPC) codes was introduced by Gallager in his thesis in 1961 [2]. Until the invention of turbo codes, they were largely neglected, but received a lot of interest lately, due to the possibility of designing LDPC codes within 0:0045 dB of the Shannon limit. We review in this project techniques used to analyze the performance of LDPC codes under a message-passing decoding algorithm, namely belief propagation (BP) [4][5]. This analysis gives us the tools to design good LDPC codes. We will flrst take the simpler example of transmission over the class of binary erasure channels (BEC). We will then see how it is possible to extend the results for the BEC to the much more general class of symmetric channels.

Jan 1, 20050 citations