Computer-implemented method for correcting transmission errors using linear programming
AssigneesCalifornia Institute of Technology, The Regents of the University of California
InventorsEmmanuel Candes, Terence Tao
Life of this patent
Estimating the term…
Abstract
A computer-implemented method for correcting transmission errors. According to the method, a transmitted vector corrupted by error can be recovered solving a linear program. The method has applications in the transmission of Internet media, Internet telephony, and speech transmission. In addition, error correction is embedded as a key building block in numerous algorithms, and data-structures, where corruption is possible; corruption of digital data stored on a hard-drive, CD, DVD or similar media is a good example. In short, progress in error correction has potential to impact several storage and communication systems.
Claims7
A computer-implemented method for correcting transmission errors, comprising the steps of:
- transmitting a vector encoded through an encoding device using a linear code, said vector becoming corrupted by error upon transmission;
- and
- decoding the corrupted vector through a decoding device and correcting the corrupted vector so as to recover the vector, said corrupted vector being corrected by solving a linear program in form of a convex optimization problem
- min
- x
- ∈
- R
- n
-
-
- y
- -
- Ax
-
- l
- 1
- ,
- wherein y is the corrupted vector, A is a coding matrix expressing the linear code, and l1 is a norm such that
-
- x
-
- l
- 1
- :=
- ∑
- i
-
-
- x
- i
-
- .
A method for transmitting packets over a communication network comprising:
- encoding the packets through an encoding device using a coding matrix;
- transmitting the encoded packets, wherein during transmission the packets become corrupted;
- and
- decoding through a decoding device and correcting the transmitted corrupted packets by solving a linear program
- min
- x
- ∈
- R
- n
-
-
-
- y
- -
- Ax
-
-
- l
- 1
- ,
- wherein A is the coding matrix, y is a vector expressing the transmitted encoded packets and l1 represents a norm such that
-
- x
-
- l
- 1
- :=
- ∑
- i
-
-
- x
- i
-
- .
Dependencies are inferred from the claim text.