Bounds on Separating Redundancy of Linear Codes and Rates of X-Codes

An error-erasure channel is a simple noise model that introduces both errors and erasures. While the two types of errors can be corrected simultaneously with error-correcting codes, it is also known that any linear code allows for first correcting errors and then erasures in two-step decoding. In particular, a carefully designed parity-check matrix not only allows for separating erasures from errors but also makes it possible to efficiently correct erasures. The separating redundancy of a linear code is the number of parity-check equations in a smallest parity-check matrix that has the required property for this error-erasure separation. In a sense, it is a parameter of a linear code that represents the minimum overhead for efficiently separating erasures from errors. While several bounds on separating redundancy are known, there still remains a wide gap between upper and lower bounds except for a few limited cases. In this paper, using probabilistic combinatorics and design theory, we improve both upper and lower bounds on separating redundancy. We also show a relation between parity-check matrices for error-erasure separation and special matrices, called X-codes, for data compaction circuits in VLSI testing. This leads to an exponentially improved bound on the size of an optimal X-code.
Comment: Part of this work was presented at the 2017 IEEE International Symposium on Information Theory (ISIT 2017), Aachen, Germany. To appear in IEEE Transactions on Information Theory. 17 pages, 4 tables. v2: added Section V on the relation of separating parity-check matrices to X-codes, improved Theorem 3.10, added references, improved exposition, typos fixed