A new approach to the general minimum distance decoding problem: The zero-neighbors algorithm

Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined bymin (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared withmin (2^{k},2^{n-k})forn gg 1and a wide range of code ratesR = k/n. For example, forR approx 0.5this number grows approximately as a square root of the number of codewords.