Error-Correcting Codes-A Linear Programming Approach

Abstract

Two theorems are proved that characterize the matrices used to construct systematic error-correcting codes. A lower bound on the number of required check bits is derived, and it is shown that, in certain cases, this bound for systematic codes is identical with Plotkin's bound on the size of any error-correcting code. A linear program whose solutions correspond directly to a minimum-redundancy error-correcting code is derived. This linear program can be solved by an algorithm that is essentially the simplex method modified to produce integer solutions. Explicit solutions in closed form that specify the codes directly are derived for the cases when the specified code parameters satisfy certain restrictions. Several theorems are proved about minimum redundancy codes with related parameters.