Computer-implemented method for correcting transmission errors using linear programming
View Patent ↗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.
1. 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 l 1 represents a norm such that
x
l
1
:=
∑
i
x
i
.
2. The system of claim 1 , wherein the coding matrix A is a random matrix.
3. The system of claim 1 , wherein the coding matrix A is sampled from a Gaussian ensemble.
4. The system of claim 1 , wherein the original vector comprises data relating to a field selected from Internet media, Internet telephony and speech transmission.
5. The system of claim 1 , wherein the coding matrix A used to encode said original vector is known by both the first and the second computers.
6. The system of claim 1 , wherein the coding matrix A is generated through a standard random number generator with an agreed upon seed.
7. The system of claim 1 , wherein the transmission medium is a communication network, and wherein providing the original vector y to the transmission medium comprises transmitting the original vector y into the communication network.
8. The system of claim 7 , wherein the communication network is the Internet.
9. The system of claim 8 , wherein the one or more errors is introduced by noise in the communication network.
10. The system of claim 1 , wherein the transmission medium comprises a storage device, and wherein providing the original vector y to the transmission medium comprises providing the original vector y in the storage device.
11. The system of claim 10 , wherein the storage device is one of a hard disk, a CD, or a DVD.
12. The system of claim 11 , wherein the one or more errors is introduced by at least one of: a) damage to the CD, or b) damage to the DVD.
13. The system of claim 1 , wherein the first computer is the same as the second computer, and the communication medium comprises a storage device.
14. The system of claim 13 , wherein the storage device is one of a hard disk, a CD, or a DVD.