In class today, we defined the notion of efficient algorithms to be polynomial time algorithms. The most obvious algorithmic questions related to codes are that of encoding and decoding. We have already seen that for *linear* codes, encoding is always efficient. However, is it true that efficient decoding is always possible? Or is it the case that like most natural optimization problems, this is an NP-hard problem?

In class today, we saw that for the Hamming code, the obvious brute force implementation of the Maximum Likelihood Decoding (MLD) function takes exponential time. However, can one do an efficient implementation of the MLD function? Further, maybe it does not work for the Hamming code but maybe it can done for other codes. Unfortunately, MLD turns out to be a very slippery customer: there are **no** non-trivial codes known for which efficient implementation of MLD is known. There has been a series of results along this line for about 25 years now. One of the more recent result due to Guruswami and Vardy is their paper titled __Maximum-Likelihood Decoding of Reed-Solomon codes is NP-Hard__ (SODA05).

Another parameter of the code that is not immediately obvious from the definition of a linear code is the distance of the code. The situation here is not as hopeless as MLD– for certain linear codes it is easy to figure our their distance (for most of the linear codes that we will study in the course, this will be the case). However, there do exist linear codes for which it is NP-hard to determine its distance (in fact it is hard even to approximate it). See for example, the paper by Dumer, Micciancio and Sudan titled __Hardness of Approximating the Minimum Distance of a Linear Code__ (FOCS99).

### Like this:

Like Loading...

*Related*

[…] is a link to an earlier post that talk about the complexity issues for MLD (and other coding […]

By:

Lecture 23: Shannon vs. Hamming « Error Correcting Codes: Combinatorics, Algorithms and Applicationson March 22, 2011at 10:06 pm