IEEE Transactions on Information Theory · 2006 · 185 citations · 17 references
EngineeringComputer ScienceElectrical EngineeringAlgorithmsInformation TheoryTheory Of ComputationChannel CapacityChannel CodingCoding TheoryErasure CodingError Control CodingError-correcting CodesBinary CodesBounds On CodesChannelsHamming DistanceIterative DecodingLinear CodesParity Check CodesParity-check Matrices
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, 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 codes
17
Sphere Packings, Lattices and Groups.
H. S. M. Coxeter, J. H. Conway, N. J. A. Sloane · American Mathematical Monthly · 1989 · 3.5K citations
Lower bounds for constant weight codes
R. L. Graham, N. J. A. Sloane · IEEE Transactions on Information Theory · 1980 · 272 citations