arXiv:cs/0612011 · Canadian Workshop on Information Theory (CWIT)

Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

Published Jun 1, 2007• 12 citations

Abstract

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

DOI: 10.1109/cwit.2007.375704

Related papers

Estimation of Bit and Frame Error Rates of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

IEEE Transactions on CommunicationsDec 1, 200752 citations

Hard-Decision Performance of LDPC Codes on Binary Symmetric Channels with Small Crossover Probabilities

Hua Xiao, Amir H. Banihashemi

Upper and lower bounds are derived on the frame error rate (FER) of low-density parity-check (LDPC) codes decoded by hard-decision iterative algorithms over binary symmetric channels (BSC). The bounds, which are tight for sufficiently small crossover probabilities of the channel, provide a good estimate of FER in this region. The derivation of the bounds is based on the enumeration of low-weight error patterns at the input of the decoder and is much less complex than the conventional Monte Carlo simulation in the crossover probability range of interest. The proposed method can be applied to any LDPC code and for any decoding algorithm

Biennial Symposium on CommunicationsJul 10, 20064 citations

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE Transactions on CommunicationsJun 1, 200935 citations

Error Rate Estimation of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels Using Cycle Enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20074 citations

Performance Analysis of Verification-Based Decoding for Packet-Based LDPC Codes over Binary Symmetric Channel

Biaokai Zhu, Defeng David Huang, Sven Erik Nordholm

In this paper, we propose a statistical model to analyze the performance of verification-based algorithm (VA) for packet-based low-density parity-check (LDPC) codes over binary symmetric channel (BSC). In contrast to the analysis of VA in the literature, we propose to take the false verification into consideration. For a given ensemble of LDPC codes and channel parameters, the proposed analysis model gives an efficient way to find the average performance of packet-based LDPC codes with verification-based decoding. Through numerical results, we find that the proposed method can provide a close estimation of frame error rate (FER) for packet-based LDPC codes with verification- based decoding over BSC for all crossover probabilities of practical interests.

International Conference on CommunicationsJun 1, 20091 citation

Hard-Decision Iterative Decoding of LDPC Codes with Bounded Error Rate

Paolo Santini, Massimo Battaglioni, Marco Baldi +1 more

Differently from bounded-distance decoders used for algebraic codes, iterative decoders used for low-density parity-check (LDPC) codes are not characterized by a deterministic decoding radius. Therefore, the error rates of LDPC-coded transmissions are usually estimated heuristically through simulations. This is adequate for many applications like wireless communications, where a frame error rate (FER) in the order of 10-6or higher is usually targeted. However, lower values of FER can barely be assessed through simulations, and this limits the use of LDPC codes in applications requiring a lower FER, like optical communications and code-based cryptography. In this paper we introduce and study a version of the classic bit flipping (BF) decoder for which we are able to devise and develop a theoretical characterization of the FER. In addition, we consider a two-iteration hard-decision decoder for LDPC codes derived from BF, and discuss its error rate performance. Our results are validated through numerical simulations.

International Conference on CommunicationsMay 1, 201913 citations