IEICE TRANSACTIONS on Fundamentals
A Probabilistic Algorithm for Computing the Weight Distribution of LDPC Codes
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.7 pp.1677-1689
- Publication Date
- 2009/07/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.1677
- Type of Manuscript
- PAPER
- Category
- Coding Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masanori HIROTOMO, Masami MOHRI, Masakatu MORII, "A Probabilistic Algorithm for Computing the Weight Distribution of LDPC Codes" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 7, pp. 1677-1689, July 2009, doi: 10.1587/transfun.E92.A.1677.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1677/_p
Copy
@ARTICLE{e92-a_7_1677,
author={Masanori HIROTOMO, Masami MOHRI, Masakatu MORII, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Probabilistic Algorithm for Computing the Weight Distribution of LDPC Codes},
year={2009},
volume={E92-A},
number={7},
pages={1677-1689},
abstract={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.},
keywords={},
doi={10.1587/transfun.E92.A.1677},
ISSN={1745-1337},
month={July},}
Copy
TY - JOUR
TI - A Probabilistic Algorithm for Computing the Weight Distribution of LDPC Codes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1677
EP - 1689
AU - Masanori HIROTOMO
AU - Masami MOHRI
AU - Masakatu MORII
PY - 2009
DO - 10.1587/transfun.E92.A.1677
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2009
AB - 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.
ER -
English
