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 ≤ 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 Communications
Department of Systems and Computer Engineering

Xiao, H. (Hua), & Banihashemi, A. (2009). Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration. IEEE Transactions on Communications, 57(6), 1550–1555. doi:10.1109/TCOMM.2009.06.070048