Information additive code generator and decoder for communication systems

• US 9,246,633 B2
• Filed: 04/23/2007
• Issued: 01/26/2016
• Est. Priority Date: 09/23/1998
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G.
• Primary Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US11/738,866
• Publication Number:
  US 20080034273A1
• Time in Patent Office: 3,200 Days
• Field of Search: 341/50, 341/55, 341/60, 714/15, 395/200.3, 375/296, 375/55, 375/60, 375/280
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture

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.

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.

2. The method of claim 1, wherein the number of possible output symbols for a given ordered set of input symbols is independent of the number of input symbols in the ordered set of input symbols.

3. The method of claim 1, wherein the integer parameters X and Y are determined according to a pseudorandom number generator for at least one of the one or more transmitter.

4. The method of claim 1, wherein a key is used to generate the integer parameters X and Y.

5. The method of claim 4, wherein the one or more transmitter is a plurality of transmitters, wherein the key is generated using a pseudorandom sequence and wherein, for each transmitter of the plurality of transmitters, different pseudorandom sequences or portions of a pseudorandom sequence are used for each transmitter so that different sequences of integer parameters X and Y are used for generating each transmitter'"'"'s output symbols.

6. The method of claim 1, wherein a key is used to generate the weight W.

7. The method of claim 6, wherein the one or more transmitter is a plurality of transmitters, wherein the key is generated using a pseudorandom sequence and wherein, for each transmitter of the plurality of transmitters, different pseudorandom sequences or portions of a pseudorandom sequence are used for each transmitter so that different sequences of weights are used for generating each transmitter'"'"'s output symbols.

8. The method of claim 1, wherein a key is used to generate the weight W and the integer parameters X and Y.

9. The method of claim 8, wherein the one or more transmitter is a plurality of transmitters, wherein the key is generated using a pseudorandom sequence and wherein, for each transmitter of the plurality of transmitters, different pseudorandom sequences or portions of a pseudorandom sequence are used for each transmitter so that substantially different keys are used for generating each transmitter'"'"'s output symbols.

10. The method of claim 1, wherein the predetermined value function is the exclusive OR (XOR) function.

11. The method of claim 1, wherein the one or more transmitter is a plurality of transmitters and wherein the weights and the integer parameters are such that, for each transmitter of the plurality of transmitters, different combinations of weight and integer parameter values are used for generating each transmitter'"'"'s output symbols.

12. The method of claim 1, wherein one or more transmitter comprises exactly one transmitter.

13. The method of claim 1, wherein the one or more transmitter comprises a plurality of transmitters.

14. The method of claim 1, wherein the position of a first associate in the set of associates for the output symbol is determined from the integer parameter Y.

15. The method of claim 14, wherein the integer parameter Y is an integer between 0 and K−

1 inclusive and the position of the first associate is determined as Y, where K is the number of input symbols in the ordered set of input symbols.

16. The method of claim 1, wherein the integer parameter X determines the position of a subsequent associate in the set of associates for the output symbol based on at least a position, i, of a previous associate and at least the integer parameter X.

17. The method of claim 16, wherein the integer parameter X is an integer between 1 and K−

1 inclusive and the position of the subsequent associate is determined as i+X modulo K, where K is the number of input symbols in the ordered set of input symbols.

18. The method of claim 16, wherein the integer parameter X is an integer between 1 and P−

1 inclusive and the position of the subsequent associate is determined as i+X modulo P, where P is a number greater than or equal to the number of input symbols in the ordered set of input symbols.

19. The method of claim 18, wherein X and P are coprime.

20. The method of claim 18, wherein P is prime.

21. The method of claim 18, wherein K is nonprime and P is the smallest prime number greater than K, the method further comprising at least logically padding the input file with P−

K padding input symbols, where K is the number of input symbols in the ordered set of input symbols.

22. The method of claim 1, wherein the weight of the output symbol is determined from a set of one or more weight generation rules.

23. The method of claim 1, wherein all input symbols and all output symbols are equal in length.

24. The method of claim 1, wherein determining a set of associates for an output symbol comprises determining a weight W and integer parameters X and Y that are determined independently of weight and integer parameters for other output symbols.

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.

26. The method of claim 25, wherein the length of an output symbol and the length of an input symbol are equal.

27. The method of claim 26, wherein the number of output symbols carried in a packet is determined based on a desired number of input symbols.

28. The method of claim 25, wherein the number of output symbols carried in a packet is determined based on a desired reception overhead.

29. The method of claim 25, wherein at least one input symbol is used in generating output symbols for more than one packet such that there exists a first packet carrying a first output symbol generated from a first set of input symbols and a second packet carrying a second output symbol generated from a second set of input symbols where the first set and second set share at least one input symbol.

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.

31. The method of claim 30, wherein generating the plurality of packets is done such that at least some of the packets carry more than one output symbol and at least one input symbol is used in generating output symbols for more than one packet such that there exists a first packet carrying a first output symbol generated from a first set of input symbols and a second packet carrying a second output symbol generated from a second set of input symbols where the first set and second set share at least one input symbol.

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.

33. The transmitter of claim 32, wherein the weight generator, parameter generator and output symbol generator are implemented using software logic.

34. The transmitter of claim 32, wherein the weight generator and parameter generator are configured to be able to generate valid output symbols for a given ordered set of input symbols wherein the number of distinct valid output symbols is independent of the number of input symbols in the ordered set of input symbols.

35. The transmitter of claim 32, wherein one or both of the weight generator and parameter generator include one or both of an input from a pseudorandom number generator and an input for a key.

36. The transmitter of claim 35, wherein the transmitter transmits output symbols over a plurality of communication channels, wherein the key is generated using a pseudorandom sequence and wherein, for each communication channel of the plurality of communication channels, different pseudorandom sequences or portions of a pseudorandom sequence are used for each communication channel so that different sequences of weights or integer parameters are used for generating each communication channel'"'"'s output symbols.

37. The transmitter of claim 32, wherein the predetermined value function is the exclusive OR (XOR) function.

38. The transmitter of claim 32, wherein all input symbols and all output symbols are equal in length.

39. The transmitter of claim 32, wherein the weight generator and parameter generator are configured to be able to generate weights and integer parameters for a given output symbol independently of weight and integer parameters for other output symbols.

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.

41. The method of claim 40, wherein the length of an output symbol and the length of an input symbol are equal.

42. The method of claim 40, wherein recovering at least one input symbol from the unrecovered input symbols until sufficient input symbols are recovered is performed until all of the input symbols are recovered.

43. The method of claim 40, wherein the number of possible keys is independent of the number of input symbols.

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.

45. The receiver of claim 44, wherein the length of an output symbol and the length of an input symbol are equal.

46. The receiver of claim 44, wherein the number of possible keys is independent of the number of input symbols.

47. The receiver of claim 44, wherein the logic for recovering input symbols comprises:

a) logic for determining whether an output symbol in the memory for storing received output symbols is an output symbol for which all but one of its associate input symbols have been recovered; and

b) logic for recovering, in such cases, the one remaining unrecovered associate input symbol, using values of the output symbol and the recovered associate input symbols.

48. The receiver of claim 47, wherein the output symbol value is the XOR of its associated input symbols, and wherein the value of the one remaining unrecovered associate input symbol value is determined as the XOR of the values of the output symbol and the recovered associate input symbols.

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.

50. The communication system of claim 49, wherein packet generating logic is such that at least some of the packets carry more than one output symbol and at least one input symbol is used in generating output symbols for more than one packet such that there exists a first packet carrying a first output symbol generated from a first set of input symbols and a second packet carrying a second output symbol generated from a second set of input symbols where the first set and second set share at least one input symbol.

51. A method of transmitting data via a plurality of transmitters, 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 of the plurality of transmitters, determining a sequence of keys to be used at the transmitter for symbol generation, wherein at least two transmitters use key sequences distinct from each other;

for each output symbol encoded;

a) determining a key, I, for that output symbol, wherein the number of possible keys is independent of the number of input symbols in the ordered set of input symbols, and wherein the determined key is in the sequence of keys for the transmitter that is to send the encoded output symbol;

b) determining a weight, W(I), of that output symbol, wherein W(I) is greater than one for at least one value of I and is less than the number of input symbols in the ordered set of input symbols for at least one value of I;

c) determining a set of associates, AL(I) of that output symbol from the weight W(I), the set of associates being a set of W(I) input symbols; and

d) determining an output symbol value, B(I), for the output symbol according to a predetermined value function, F(I), of the W(I) input symbols in the set of associates AL(I) for that output symbol;

generating a plurality of encoded output symbols from the ordered set of input symbols at the plurality of transmitters, wherein at least two transmitters generate encoded output symbols independent of which output symbols the other has generated; and

transmitting the plurality of output symbols via the plurality of transmitters, such that a recipient can receive output symbols via some or all of the plurality of transmitters, and can regenerate the ordered set of input symbols from the received set of output symbols.

52. The method of claim 51, wherein the keys are generated using a pseudorandom sequence and wherein, for each transmitter of the plurality of transmitters, different pseudorandom sequences or portions of a pseudorandom sequence are used for each transmitter so that different sequences of weights and sets of associates are used for generating each transmitter'"'"'s output symbols.

53. The method of claim 51, wherein the predetermined value function is the exclusive OR (XOR) function.

54. The method of claim 51, wherein the weight of each output symbol is determined from a set of one or more weight generation rules.

55. The method of claim 51, wherein all input symbols and all output symbols are equal in length.

56. A method of transmitting data from a source to a destination over a packet communication channel using a plurality of transmitters, the method 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, wherein each of the transmitters generates at least some output symbols without reference to which output symbols were sent by another transmitter;

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 using the plurality of transmitters;

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.

57. The method of claim 56, wherein at least one input symbol is used in generating output symbols for more than one packet such that there exists a first packet carrying a first output symbol generated from a first set of input symbols and a second packet carrying a second output symbol generated from a second set of input symbols where the first set and second set share at least one input symbol.

58. A method of receiving data from a plurality of transmitters 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, wherein the number of different valid packet keys is independent of the number of symbols in the ordered set of input symbols;

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, wherein at least one input symbol is recovered using output symbols received from more than one of the plurality of transmitters.