A Caltech Library Service

On the stopping distance and the stopping redundancy of codes

Schwartz, Moshe and Vardy, Alexander (2006) On the stopping distance and the stopping redundancy of codes. IEEE Transactions on Information Theory, 52 (3). pp. 922-932. ISSN 0018-9448.

See Usage Policy.


Use this Persistent URL to link to this item:


It is now well known that the performance of a linear code /spl 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 /spl Copf/. Several recent papers refer to this parameter as the stopping distance s of /spl Copf/. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for /spl Copf/ depends on the corresponding choice of a parity-check matrix. It is easy to see that s /spl les/ d, where d is the minimum Hamming distance of /spl Copf/, and we show that it is always possible to choose a parity-check matrix for /spl Copf/ (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of /spl Copf/, defined as the minimum number of rows in a parity- check matrix H for /spl 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 codes.

Item Type:Article
Related URLs:
URLURL TypeDescription
Schwartz, Moshe0000-0002-1449-0026
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received March 17, 2005; revised December 9, 2005. [Posted online: 2006-03-06] This work was supported in part by the National Science Foundation and in part by the David and Lucile Packard Foundation. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Adelaide, Australia, September 2005. We are grateful to Ilya Dumer, Tuvi Etzion, Jonathan Feldman, and Paul Siegel for helpful and stimulating discussions.
Subject Keywords:Erasure channels, Golay codes, iterative decoding, linear codes, maximum distance separable (MDS) codes, Reed–Muller codes, stopping sets
Issue or Number:3
Record Number:CaltechAUTHORS:SCHWieeetit06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6330
Deposited By: Archive Administrator
Deposited On:01 Dec 2006
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page