New Upper Bounds on the Separating Redundancy of Linear Block Codes

For linear block codes correcting both errors and erasures, efficient decoding can be established by using separating parity-check matrices. For a given maximum number of correctable erasures, such matrices yield parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. Typically, these parity-check matrices have redundant rows. To reduce decoding complexity, parity-check matrices with small number of rows are preferred. The minimum number of rows in a parity-check matrix separating all erasure sets of size at most l is called the lth separating redundancy. In this paper, new upper bounds on the separating redundancy are presented.