Design Methods for Maximum Minimum-Distance Error-Correcting Codes
by J. E. MacDonald
In error-correcting codes for combating noisy transmission channels, a central concept is the notion of minimum distance. If a code can be constructed with minimum distance between code points of 2m+1, then any number of errors per code word which does not exceed m can be corrected, thus increasing the reliability of transmission above that to be expected with no redundancy in the code.
An upper bound on minimum distance is derived which depends on g (the number of code points or messages required) and n (the number of binary symbols per code point). This bound is complementary to a bound due to Hamming and uses an argument which is essentially due to Plotkin.
Construction methods are presented for codes which actually achieve the upper bound on minimum distance for any g and an infinite class of integers n which depend on g. Sixteen code types are described: three for g=2h-1, six for g=2h, and seven for g=2k.
PDF