On the complexity of minimum distance decoding of long linear codes

We suggest a decoding algorithm of q-ary linear codes, which we call supercode decoding. It ensures the error probability that approaches the error probability of minimum distance decoding as the length of the code grows. For n -> inf the algorithm has the maximum likelihood performance. The asymptotic complexity of supercode decoding is exponentially smaller than the complexity of all other methods known. The algorithm develops the ideas of covering-set decoding [12], [25] and split syndrome decoding [15].