Posted by: atri | September 18, 2007

Project 9: LP Decoding

Linear Programming (or LP) decoders have been analyzed to obtain polynomial time decoding algorithms that achieve the capacity of some well known stochastic channels. These decoders proceed by casting the decoding problem as a linear program. LP decoder have the nice property called maximum-likelihood certificate property, which implies that when a codeword is output by the algorithm it is guaranteed to be the one closest to the received word.

A good starting point is the paper titled LP Decoding Achieves Capacity (SODA05) by Feldman and Stein. For more papers see the publications page of Jon Feldman.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: