The polynomial error probability for LDPC codes.pdf

arXiv:cond-mat/0310177v1 [cond--mech] 8 Oct 2003 The polynomial error probability for LDPC codes J. van Mourik The puting Research Group, Aston University, Birmingham B4 7ET, United Kingdom Y. Kabashima Department putational Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama 2268502, Japan (Dated: February 2, 2008) We obtain exact expressions for the asymptotic behaviour ofthe average probability of the block decoding error for ensembles of regular low density parity check error correcting codes, by employing diagrammatic techniques. Furthermore, we show how imposing simple constraints on the code ensemble (that can be practically implemented in linear time), allows one to suppress the error probability for codes with more than 2 checks per bit, to an arbitrarily low power ofN. As such we provide a practical route to a (sub-optimal)expurgatedensemble. PACS numbers: .+c, , .+q, , .+c I. INTRODUCTION Recent research in a cross-disciplinary ?eld between the information theory (IT) and statistical mechanics (SM) revealed a great similarity between the low density parity check (LDPC) error correcting codes and systems of Ising spins (microscopic s) which interact with each otherover random graphs[1, 2]. On the basis of this similarity, notions and methods developed in SM were employed to analyseLDPC codes, which essfully clari?edtypical properties of these excellent codes when the code lengthNis su?ciently large[3, 4, 5]. In general, an LDPC code is de?ned by a parity check matrixAwhich represents dependences between codeword bits and parity checks determined under certain constraints. This implies that the performance of LDPC codes, in particular, the probability of theblockdecoding errorP B(A) ?uctuates depending on each realization ofA. Therefore, the average of the decoding error probability over a given ensembleP Bis frequently used for characterising the performance of LDPC code ensembles. Detailed