An upper bound on the separating redundancy of linear block codes

Abstract

Linear block codes over noisy channels causing both erasures and errors can be decoded by deleting the erased symbols and decoding the resulting vector with respect to a punctured code and then retrieving the erased symbols. This can be accomplished 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. Separating parity-check matrices typically have redundant rows. An upper bound on the minimum number of rows in separating parity-check matrices, which is called the separating redundancy, is derived which proves that the separating redundancy tends to behave linearly as a function of the code length.