Methods, systems, and media for forming linear combinations of data

Abstract

Methods, systems, and media for forming linear combinations of data are provided. In some embodiments, methods for forming a linear combination of data include: receiving at a device a first codeword, wherein the first codeword comprises a linear combination of at least a first data unit including data, and a second data unit including data; encoding at the device the first codeword and a third data unit including data to form a second codeword, wherein the second codeword includes a linear combination of at least the first data unit, the second data unit, and the third data unit; and transmitting from the device the second codeword.

What is claimed is: 
     
         1 . A method for forming a linear combination of data, comprising:
 receiving at a device a first codeword, wherein the first codeword comprises a linear combination of at least a first data unit, comprising data, and a second data unit, comprising data;   encoding at the device the first codeword and a third data unit comprising data to form a second codeword, wherein the second codeword comprises a linear combination of at least the first data unit, the second data unit, and the third data unit; and   transmitting from the device the second codeword.   
     
     
         2 . The method of  claim 1 , wherein the encoding comprises performing a bitwise exclusive-or (XOR) operation on the first codeword and the third data unit. 
     
     
         3 . The method of  claim 1 , wherein the encoding further comprises compressing the third data unit to reduce a size of the third data unit. 
     
     
         4 . The method of  claim 1 , wherein the receiving, the encoding and the transmitting are repeated at predetermined time intervals. 
     
     
         5 . The method of  claim 1 , wherein the device comprises a sensor, and wherein the first data unit, the second data unit, and the third data unit comprise sensor data. 
     
     
         6 . The method of  claim 5 , further comprising periodically acquiring new sensor data at the device. 
     
     
         7 . The method of  claim 1 , wherein the device comprises a computing device in a peer-to-peer (P2P) network, and wherein the first data unit, the second data unit, and the third data unit comprise at least a portion of a file. 
     
     
         8 . The method of  claim 7 , further comprising distributing the first data unit, the second data unit, and the third data unit to one or more additional computing devices in the peer-to-peer network. 
     
     
         9 . The method of  claim 1 , wherein the second codeword further comprises identification information identifying the first data unit, the second data unit, and the third data unit. 
     
     
         10 . The method of  claim 9 , further comprising:
 determining a format for storing the identification information based on a number of data units encoded by the second codeword.   
     
     
         11 . The method of  claim 9 , further comprising:
 storing the first codeword and a third codeword at the device,   wherein the first codeword and the third codeword share identification information that identifies data units encoded by the first codeword and the third codeword.   
     
     
         12 . The method of  claim 1 , further comprising:
 receiving the first codeword at a first point in time; and   decoding the first codeword to recover the first data unit.   
     
     
         13 . The method of  claim 12 , further comprising:
 receiving the second codeword at a second point in time that is subsequent to the first point in time; and   decoding the second codeword to recover the third data unit using the first data unit and the second data unit.   
     
     
         14 . A system for forming a linear combination of data, comprising:
 a device that:
 receives a first codeword, wherein the first codeword comprises a linear combination of at least a first data unit, comprising data, and a second data unit, comprising data; 
 encodes the first codeword and a third data unit to form a second codeword, wherein the second codeword comprises a linear combination of at least the first data unit, the second data unit, and the third data unit; and 
 transmits the second codeword. 
   
     
     
         15 . The system of  claim 14 , wherein in encoding, the device performs a bitwise exclusive-or (XOR) operation on the first codeword and the third data unit. 
     
     
         16 . The system of  claim 14 , wherein in encoding, device also compresses the third data unit to reduce a size of the third data unit. 
     
     
         17 . The system of  claim 14 , wherein the device receives, encodes and transmits at predetermined time intervals. 
     
     
         18 . The system of  claim 14 , wherein the device comprises a sensor, and wherein the first data unit, the second data unit, and the third data unit comprise sensor data. 
     
     
         19 . The system of  claim 18 , wherein the sensor periodically acquires new sensor data. 
     
     
         20 . The system of  claim 14 , wherein the device comprises a computing device, in a peer-to-peer (P2P) network, and wherein the first data unit, the second data unit, and the third data unit comprise at least a portion of a file. 
     
     
         21 . The system of  claim 14 , wherein the second codeword further comprises information identifying the first data unit, the second data unit, and the third data unit. 
     
     
         22 . The system of  claim 21 , wherein the device further determines a format for storing the identification information based on a number of data units encoded by the second codeword. 
     
     
         23 . The system of  claim 21 , wherein the device further stores the first codeword and a third codeword, the first codeword and the third codeword share identification information that identifies data units encoded by the first codeword and the third codeword. 
     
     
         24 . The system of  claim 14 , wherein the device also:
 receives the first codeword at a first point in time; and   decodes the first codeword to recover the first data unit.   
     
     
         25 . The system of  claim 23 , wherein the device also:
 receives the second codeword at a second point in time that is subsequent to the first point in time; and   decodes the second codeword to recover the third data unit using the first data unit and the second data unit.   
     
     
         26 . A computer-readable medium containing computer executable instructions that, when executed by a processor, cause the processor to perform a method for forming a linear combination of data, the method comprising:
 receiving at a device a first codeword, wherein the first codeword comprises a linear combination of at least a first data unit, comprising data, and a second data unit, comprising data;   encoding at the device the first codeword and a third data unit comprising data to form a second codeword, wherein the second codeword comprises a linear combination of at least the first data unit, the second data unit, and the third data unit; and   transmitting from the device the second codeword.   
     
     
         27 . The medium of  claim 26 , wherein the encoding comprises performing a bitwise exclusive-or (XOR) operation on the first codeword and the third data unit. 
     
     
         28 . The medium of  claim 26 , wherein, the encoding further comprises compressing the third data unit to reduce a size of the third data unit. 
     
     
         29 . The medium of  claim 26 , wherein the device comprises a sensor, and wherein the first data unit, the second data unit, and the third data unit comprise sensor data. 
     
     
         30 . The medium of  claim 26 , wherein the device comprises a computing device in a peer-to-peer (P2P) network, and wherein the first data unit, the second data unit, and the third data unit comprise at least a portion of a file. 
     
     
         31 . The medium of  claim 26 , wherein the second codeword further comprises identification information identifying the first data unit, the second data unit, and the third data unit. 
     
     
         32 . The medium of  claim 31 , wherein the method further comprises:
 determining a format for storing the identification information based on a number of data units encoded by the second codeword.   
     
     
         33 . The medium of  claim 31 , wherein the method further comprises:
 storing the first codeword and a third codeword at the device,   wherein the first codeword and the third codeword share identification information that identifies data units encoded by the first codeword and the third codeword.   
     
     
         34 . The medium of  claim 26 , wherein the method further comprises:
 receiving the first codeword at a first point in time, and   decoding the first codeword to recover the first data unit.   
     
     
         35 . The medium of  claim 26 , wherein the method further comprises:
 receiving the second codeword at a second point in time that is subsequent to the first point in time; and   decoding the second codeword to recover the third data unit using the first data unit and the second data unit.