Multiple error correction by means of parity checks

Abstract

An n-place binary parity check code which corrects up to and including e errors in each code letter is fully described by its n characteristics, which are r-dimensional vectors, where r is the number of redundant binits in each code letter. It is shown that the characteristics of such a code have the essential property that any subset of 2e of them are linearly independent. An upper bound on r for fixed n and e is obtained by consideration of a systematic procedure for finding the characteristics; this upper bound is always less than, or equal to, twice the lower bound of Hamming.¹