On the stopping distance and the stopping redundancy of codes
Authors:
- M. SchwartzMSM. Schwartz
- A. VardyAVA. Vardy
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 975-979
Abstract
It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s = d. We thus introduce a new parameter, termed the stopping redundancy of Copf, defined as the minimum number of rows in a parity-check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely s(H) = d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codesKeywords
This publication has 5 references indexed in Scilit:
- Stopping Set Distribution of LDPC Code EnsemblesIEEE Transactions on Information Theory, 2005
- On the effect of parity-check weights in iterative decoding2004
- Stopping sets in codes from designs2003
- Minimal tail-biting trellises: the Golay code and moreIEEE Transactions on Information Theory, 1999
- Orbit and coset analysis of the Golay and related codesIEEE Transactions on Information Theory, 1990