information theory Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...

and

coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

, linear programming decoding (LP decoding) is a

decoding Decoding or decode may refer to: is the process of converting code into plain text or any format that is useful for subsequent processes. Science and technology * Decoding, the reverse of encoding * Parsing, in computer science * Digital-to-analog ...

method which uses concepts from

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

(LP) theory to solve decoding problems. This approach was first used by Jon Feldman ''et al.'' "Using linear programming to Decode Binary linear codes," J. Feldman, M.J. Wainwright and D.R. Karger, IEEE Transactions on Information Theory, 51:954–972, March 2005. They showed how the LP can be used to decode block codes. The basic idea behind LP decoding is to first represent the

maximum likelihood decoding In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, s ...

of a

linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen a ...

as an

integer linear program An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...

, and then

relax Relax may refer to: Aviation * Roland Z-120 Relax, a German ultralight aircraft design for the 120 kg class Music Albums * ''Relax'' (Blank & Jones album), 2003 * ''Relax'' (Das Racist album), 2011 Songs * "Relax" (song), a 1983 song by Fran ...

the integrality constraints on the variables into linear inequalities.

References

{{mathapplied-stub Linear programming