A Probabilistic Algorithm for Computing the Weight Distribution of LDPC Codes

Masanori HIROTOMO  Masami MOHRI  Masakatu MORII  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A    No.7    pp.1677-1689
Publication Date: 2009/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1677
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
Keyword: 
LDPC codes,  weight distribution,  probabilistic method,  minimum distance,  

Full Text: PDF(431.1KB)>>
Buy this Article


Summary: 
Low-density parity-check (LDPC) codes are linear block codes defined by sparse parity-check matrices. The codes exhibit excellent performance under iterative decoding, and the weight distribution is used to analyze lower error probability of their decoding performance. In this paper, we propose a probabilistic method for computing the weight distribution of LDPC codes. The proposed method efficiently finds low-weight codewords in a given LDPC code by using Stern's algorithm, and stochastically computes the low part of the weight distribution from the frequency of the found codewords. It is based on a relation between the number of codewords with a given weight and the rate of generating the codewords in Stern's algorithm. In the numerical results for LDPC codes of length 504, 1008 and 4896, we could compute the weight distribution by the proposed method with greater accuracy than by conventional methods.