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.
Claims14
A system comprising:
- a first computer configured as an encoding device for transmitting data via a transmission medium, the transmitting comprising:
- encoding the data using a linear code, the encoded data represented by an original vector y;
- and
- providing the original vector y to the transmission medium;
- and
- a second computer configured as a decoding device for receiving and recovering the original vector y from data received via the transmission medium, the received data comprising a corrupted vector y′ corrupted by one or more errors introduced in the transmission medium, the recovering comprising:
- correcting the corrupted vector y′ by solving the convex optimization problem
- min
- x
- ∈
- R
- n
-
-
- y
- -
- Ax
-
- l
- 1
- using a linear program wherein A is a coding matrix expressing the linear code, and l1 represents a norm such that
-
- x
-
- l
- 1
- :=
- ∑
- i
-
-
- x
- i
-
- .
Dependencies are inferred from the claim text.