INFORMATION ADDITIVE CODE GENERATOR AND DECODER FOR COMMUNICATION SYSTEMS
First Claim
1. A method of transmitting data via one or more transmitter, wherein the data to be transmitted comprises an ordered set of input symbols and the data is transmitted as a sequence of output symbols, the method comprising:
- for each output symbol encoded;
a) determining a weight, W, of that output symbol;
b) determining integer parameters, X and Y, for that output symbol;
c) determining a set of associates of that output symbol from the weight W and the integer parameters X and Y according to a predetermined associator function, the set of associates being a set of W input symbols; and
d) determining an output symbol value for the output symbol according to a predetermined value function of the W input symbols in the set of associates for that output symbol;
generating a plurality of output symbols from the input symbols wherein at least one output symbol is generated from more than one input symbol and from less than all of the input symbols in the set of input symbols; and
transmitting the plurality of output symbols via the one or more transmitter, such that a recipient can receive N of the output symbols via some or all of the one or more transmitter, and can regenerate the ordered set of input symbols from the received N output symbols with a probability greater than a threshold probability.
3 Assignments
0 Petitions
Accused Products
Abstract
An encoder uses an input file of data and a key to produce an output symbol. An output symbol with key I is generated by determining a weight, W(I), for the output symbol to be generated, selecting W(I) of the input symbols associated with the output symbol according to a function of I, and generating the output symbol'"'"'s value B(I) from a predetermined value function F(I) of the selected W(I) input symbols. An encoder can be called repeatedly to generate multiple output symbols. The output symbols are generally independent of each other, and an unbounded number (subject to the resolution of I) can be generated, if needed. A decoder receives some or all of the output symbols generated. The number of output symbols needed to decode an input file is equal to, or slightly greater than, the number of input symbols comprising the file, assuming that input symbols and output symbols represent the same number of bits of data.
154 Citations
50 Claims
-
1. A method of transmitting data via one or more transmitter, wherein the data to be transmitted comprises an ordered set of input symbols and the data is transmitted as a sequence of output symbols, the method comprising:
-
for each output symbol encoded;
a) determining a weight, W, of that output symbol;
b) determining integer parameters, X and Y, for that output symbol;
c) determining a set of associates of that output symbol from the weight W and the integer parameters X and Y according to a predetermined associator function, the set of associates being a set of W input symbols; and
d) determining an output symbol value for the output symbol according to a predetermined value function of the W input symbols in the set of associates for that output symbol;
generating a plurality of output symbols from the input symbols wherein at least one output symbol is generated from more than one input symbol and from less than all of the input symbols in the set of input symbols; and
transmitting the plurality of output symbols via the one or more transmitter, such that a recipient can receive N of the output symbols via some or all of the one or more transmitter, and can regenerate the ordered set of input symbols from the received N output symbols with a probability greater than a threshold probability. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A method of transmitting data from a source to a destination over a packet communication channel, comprising:
-
a) arranging the data to be transmitted as an ordered set of input symbols, each input symbol being a member of an input alphabet and each input symbol having a position in the data;
b) generating a plurality of output symbols, each selected from an output alphabet, wherein each output symbol of the plurality of output symbols is generated using an error-correction code and a key associated with that output symbol, wherein the key determines how that output symbol was or is to be generated from the plurality of input symbols;
c) packetizing at least one of the plurality of output symbols into each of a plurality of packets, wherein each packet carries a packet key and at least some of the packets carry more than one output symbol;
d) transmitting the plurality of packets over the packet communication channel;
e) receiving at least some of the plurality of packets at the destination and extracting the packet key and output symbols carried in those packets; and
f) using the packet key for each received packet to reconstruct the set of keys associated with the output symbols carried in that packet; and
g) decoding the data from the plurality of received output symbols and their associated keys. - View Dependent Claims (26, 27, 28, 29)
-
-
30. A method of transmitting data via one or more transmitter, wherein the data to be transmitted comprises an ordered set of K input symbols and the data is transmitted as a sequence of output symbols, the method comprising:
-
a) determining a value P that is the smallest prime number greater than or equal to K;
b) if K is nonprime, at least logically padding the input file with P-K padding input symbols;
c) determining, for each output symbol encoded, values for;
1) a weight, W, of that output symbol;
2) integer parameters, X and Y, for that output symbol, wherein the integer parameter X is an integer between 1 and P−
1 inclusive and the integer parameter Y is an integer between 0 and P−
1 inclusive;
3) a set of associates of that output symbol from the weight W and the integer parameters X and Y, the set of associates being a set of W input symbols, wherein a position within the K input symbols of the first input symbol of the set of associates is determined by Y and a position within the K input symbols of each subsequent input symbol of the set is determined by adding X modulo P to the position of the previous input symbol in the set; and
4) an output symbol value for the output symbol according to a predetermined value function of the W input symbols in the set of associates for that output symbol;
d) generating a plurality of output symbols from the input symbols wherein at least one output symbol is generated from more than one input symbol and from less than all of the input symbols in the set of input symbols;
e) generating a plurality of packets, wherein each packet carries one or more output symbol; and
f) transmitting the plurality of packets over a packet network via the one or more transmitter such that a recipient can receive N of the output symbols via some or all of the one or more transmitter, and can regenerate the ordered set of K input symbols from the received N output symbols with a probability greater than a threshold probability. - View Dependent Claims (31)
-
-
32. A transmitter for transmitting data wherein the data to be transmitted comprises an ordered set of input symbols and an output of the transmitter is a sequence of output symbols, the transmitter comprising:
-
a weight generator for generating weights, W, for output symbols;
a parameter generator for generating integer parameters, X and Y, for output symbols; and
an output symbol generator that generates an output symbol according to a predetermined value function of the W input symbols in the set of associates for that output symbol, wherein the particular W input symbols used are based on a predetermined associator function that takes into account the integer parameters X and Y for the output symbol, wherein at least one weight W is greater than one and less than the number of input symbols in the set of input symbols. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39)
-
-
40. A method of receiving data from a source at a destination over a packet communication channel wherein the data is transmitted as set of output symbols derived from an ordered set of input symbols representing the data sent from the source to the destination, each input symbol being a member of an input alphabet and each input symbol having a position in the data, the method comprising:
-
a) receiving packets at the destination and extracting the packet key and output symbols carried in those packets;
b) using the packet key for each received packet to reconstruct the set of keys associated with the output symbols carried in that packet, the set of keys being one or more key and each packet carrying one or more output symbols and wherein each output symbol has an associated key;
c) determining, from an output symbol'"'"'s key, a weight W and integer parameters X and Y;
d) determining, from W, X and Y, the input symbols used to generate that output symbol, wherein the number of input symbols used to generate that output symbol is greater than one and less than the number of input symbols, for at least one output symbol;
e) from a set of two or more output symbols collected from received packets, determining if values of unrecovered input symbols can be determined from the collected output symbols and recovered input symbols; and
f) if determinable, recovering at least one input symbol from the unrecovered input symbols until sufficient input symbols are recovered. - View Dependent Claims (41, 42, 43)
-
-
44. A receiver for receiving data at a destination from a source over a packet communication channel wherein the data is transmitted as set of output symbols derived from an ordered set of input symbols representing the data sent from the source to the destination, each input symbol being a member of an input alphabet and each input symbol having a position in the data, the receiver comprising:
-
means for receiving data representing packets, wherein packets include packet keys and output symbols carried in those packets;
logic for reconstructing the set of keys associated with the output symbols carried in that packet using the packet key for each received packet, the set of keys being one or more key and each packet carrying one or more output symbols and wherein each output symbol has an associated key;
memory for storing received output symbols such that the receiver can determine a key for each stored output symbol;
memory for storing recovered input symbols that have been recovered from the received output symbols;
logic for determining, for each output symbol, from its associated key, a weight W and integer parameters X and Y;
logic for generating associations of output symbols and input symbols from the output symbols'"'"' associated values for W, X and Y, wherein an input symbol is associated with an output symbol if that output symbol was generated to have a value determined, at least in part, from the value of the input symbol, wherein at least one output symbol is associated with more than one input symbol and less than all of the input symbols;
logic for using the associations to determine which input symbols are recoverable from the received output symbols and recovered input symbols in the memory for storing recovered input symbols; and
logic for recovering those input symbols that are determined to be recoverable and storing recovered input symbols in the memory for storing recovered input symbols. - View Dependent Claims (45, 46, 47, 48)
-
-
49. A communication system for transmitting data from a source to a destination over a packet communication channel, comprising:
-
storage for input symbols that represent the data to be transmitted as an ordered set of input symbols, each input symbol being a member of an input alphabet and each input symbol having a position in the data;
a weight generator for generating weights, W, for output symbols;
a parameter generator for generating integer parameters, X and Y, for output symbols;
an output symbol generator that generates an output symbol according to a predetermined value function of the W input symbols in the set of associates for that output symbol, wherein the particular W input symbols used are based on a predetermined associator function that takes into account the integer parameters X and Y for the output symbol, wherein at least one weight W is greater than one and less than the number of input symbols in the set of input symbols. packet generating logic for generating data representing packets containing output symbols, wherein each packet carries a packet key and each packet carries one or more output symbol;
a channel for transporting the data representing the packets;
a packet receiver for receiving the packets and extracting the output symbols and packet keys from the symbols;
logic for reconstructing the set of keys associated with the output symbols carried in that packet; and
logic for decoding the data from the plurality of received output symbols and their associated keys. - View Dependent Claims (50)
-
Specification