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 be -hard. The complexity of known decoding algorithms is determined by , where is the code length and is 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 for and a wide range of code rates . For example, for this number grows approximately as a square root of the number of codewords.