New upper bounds on the separating redundancy of linear block codes

Abstract

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, in the paper ‘Separating Erasures for Errors for Decoding’, [1], Abdel-Ghaffar and Weber introduced parity-check matrices yielding 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. This allows for the separation of erasures from errors to facilitate decoding. 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 [1], upper and lower bounds on the separating redundancy were presented. In this paper, we give improvements on the upper bounds from [1].