On the stopping distance and the stopping redundancy of codes

摘要

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.