A new approach to the general minimum distance decoding problem: The zero-neighbors algorithm
Lev B. Levitin, Carlos R. P. Hartmann · IEEE Transactions on Information Theory · 1985
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 by\min (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 with\min (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.