FILE DOWNLOAD AND STREAMING SYSTEM

• US 20090031199A1
• Filed: 08/25/2008
• Published: 01/29/2009
• Est. Priority Date: 05/07/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Watson, Mark, Shokrollahi, M. Amin
• Granted Patent: US 9,136,878 B2
• Time in Patent Office: Days
• US Class Current: 714/800
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• 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/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 1/0065 Serial concatenated codes

Abstract

A method of encoding data operates on an ordered set of input symbols and includes generating redundant symbols from the input symbols, and includes generating output symbols from a combined set of symbols including the input symbols and the redundant symbols, wherein the number of possible output symbols is much larger than the number of the combined set of symbols, wherein at least one output symbol is generated from more than one symbol in the combined set of symbols and from less than all of the symbols in the combined set of symbols. The redundant symbols are generated from an ordered set of input symbols in a deterministic process such that a first set of static symbols calculated using a first input symbol has a low common membership with a second set of static symbols calculated using a second input symbol distinct from the first input symbol.

Claims

1. A method of encoding data for transmission from a source to a destination over a communications channel, wherein the data is represented at least by a plurality, K, of source symbols, K being the number of source symbols and the source symbols being in an ordered set, the method comprising:

generating one or more repair symbols from the plurality of source symbols;

transmitting one or more symbols over the communications channel, wherein the communication channel is a channel that can introduce errors in transmissions, wherein the one or more symbols are selected from the group consisting of source symbols and repair symbols;

determining a desired degree of accuracy for the regeneration of source symbols;

determining, for each of a plurality of source symbols, an associated symbol relation that is a function of a systematic index, J(K), where J(K) is a function of K;

determining L intermediate symbol values according to a function of values of the K source symbols and the K symbol associated symbol relations associated with the K source symbols and a set of L-K pre-coding relations, wherein L is at least K;

determining a value for each repair symbol using the associated symbol relation for that repair symbol and the plurality of L intermediate symbol values;

wherein the encoding is such that the plurality of source symbols can be regenerated to the desired degree of accuracy from any predetermined number, N, of a combination of the transmitted source symbols and transmitted repair symbols.

2. The method of claim 1, further comprising precalculating and storing the systematic index J(K) in a table for each value of K.

3. The method of claim 1, wherein the systematic index J(K) for values of K between 4 and 8192 is as provided in Appendix A.

4. The method of claim 1, wherein the symbol relations impose linear constraints on sets of symbols.

5. The method of claim 4, wherein the linear constraints are exclusive- or constraints.

6. The method of claim 1, wherein each symbol has an associated ESI that identifies the symbol, wherein the systematic index J(K) and a value X, wherein X is a valid ESI, determines the symbol relation for the symbol identified by ESI X.

7. The method of claim 6, wherein the systematic index J(K) and the ESI X can be used to generate a triple (a[X],b[X],d[X]) that defines the symbol relation for the symbol identified by ESI X.

8. The method of claim 6, wherein each source symbol can be identified by an integer ESI in the range 0 to K−

1, inclusive.

9. The method of claim 6, wherein each repair symbol can be identified by an integer ESI that is at least K.

10. The method of claim 7, wherein the triple (a[X],b[X],d[X]) that defines the source symbol relation associated with the source symbol with ESI X places a linear constraint on the value C′

[X] for source symbol with ESI X and the values C[0], C[1], C[L−

1] of the L intermediate symbols, the linear constraint defined by the method comprising;

defining an array of positive integer values B[0], ..., B[J−

1], wherein J  

 

is the minimum of d[X] and L, wherein L’

is the smallest integer  

 

that is prime that is at least the value of L, and wherein the values  

 

of the array of positive integer values B[0],...,B[J−

1] are set using the  

 

method comprising;

setting the initial value of B[0] to b[X];

 

 

while B[0] is at least L, recalculating B[0] as the previous  

 

value of B[0] plus a[X] modulo L’

;

 

 

for values of j starting at 1 and going up to J−

1 in increments of one,  

 

 

 

initializing the value of B[j] to B[j−

1] plus a[X];

 

 

 

 

while B[j] is at least L, recalculating B[j] as the  

 

 

 

is at least the value previous value of B[j] plus  

 

a[X] modulo L’

.

11. The method of claim 7, further comprising:

calculating a value A as (53591 + J(K) *

     997) % 65521, wherein *  

 

is the multiplication operator and % is the modulo operator;

calculating a value B as 10267 * (J(K) +

     1) % 65521;

calculating a value Y as (B + X * A) % 65521; and

determining a value v, wherein v is in the ranges from 0 and 1048575,  

 

inclusive, where v is calculated as the output of a random generator  

 

applied to the inputs Y, 0, and 1048575.

12. The method of claim 11 further comprising:

determining d[X] based on a degree function applied to the input v.

13. The method of claim 11 further comprising:

determining a[X], wherein a[X] is in the range between 0 and L′

−

1, inclusive, wherein L′

is the smallest prime number greater than or equal to L, wherein L′

is calculated as one plus the output of the random generator applied to the inputs Y, 1 and L′

−

1.

14. The method of claim 11 further comprising:

determining b[X], wherein b[X] is in the range between 0 and L′

, inclusive, wherein b[X] is calculated as the output of the random generator applied to the input Y, 2 and L′

.

15. The method of claim 11, wherein the value of d[X] is determined based on v as follows:

if the value of v is between 0 and 10240, inclusive, then the value of d[X] is 1, if the value of v is between 10241 and 4911581, inclusive, then the value of d[X] is 2, if the value of v is between 4911582 and 712793, inclusive, then the value of d[X] is 3, if the value of v is between 712794 and 831694, inclusive, then the value of d[X] is 4, if the value of v is between 831695 and 948445, inclusive, then the value of d[X] is 10, if the value of v is between 948446 and 1032188, inclusive, then the value of d[X] is 11, if the value of v is between 1032189 and 1048575, inclusive, then the value of d[X] is 40.

16. The method of claim 11, wherein the random generator on inputs Y, i, and m is calculated as (V0[(Y+i) % 256]̂

(V1[(floor(Y/256)+i) % 256]) % m, where % is the modulo operator, ̂

is the exclusive- or operator,/is the division operator, floor calculates the largest integer that is at most the input value, and V0 and V1 are each tables of 256 integers chosen randomly or pseudo-randomly.

17. The method of claim 16, wherein the 256 values for table V0 is as described in Appendix B.1.

18. The method of claim 16, wherein the 256 values for table V1 is as described in Appendix B.2.

19. The method of claim 1, wherein the number L-K of pre-coding relations comprises a first set of S pre-coding relations and a second set of H pre-coding relations, and wherein the L intermediate symbols comprises a first set of K intermediate symbols, a second set of S intermediate symbols, and a third set of H intermediate symbols.

20. The method of claim 19, wherein each pre-coding relation in the first set of pre-coding relations is uniquely associated with an intermediate symbol in the second set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set of intermediate symbols, wherein each pre-coding relation is a linear constraint on the value of the associated intermediate symbol and the values of the intermediate symbols in the specified set.

21. The method of claim 20, wherein a linear constraint is an exclusive- or constraint.

22. The method of claim 20, wherein for each first pre-coding relation among the first set of pre-coding relations and for each second pre-coding relation among the first set of pre-coding relations, the number of intermediate symbols that are both in the specified set associated with the first pre-coding relation and in the specified set associated with the second pre-coding relation is at most 3.

23. The method of claim 20, wherein each of the intermediate symbols in the first set of intermediate symbols is in the specified set of exactly three of the pre-coding relations in the first set of pre-coding relations.

24. The method of claim 19,

wherein S is the smallest prime integer that is at least as large as 0.01*K+X, wherein X is the smallest positive integer such that X*(X−

1) is at least 2*K,

wherein H is the smallest integer such that fact[H]/(fact[H−

H′

]*fact[H′

]) is at least K+2, wherein fact is the factorial operator, wherein H′

is the smallest integer that is at least H/2.

25. The method of claim 19, wherein each pre-coding relation in the second set of pre-coding relations is uniquely associated with an intermediate symbol in the third set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set and second set of intermediate symbols, wherein the pre-coding relation is a linear constraint on the associated intermediate symbol and the intermediate symbols in the specified set.

26. The method of claim 25, wherein a linear constraint is an exclusive- or constraint.

27. The method of claim 25, wherein each of the intermediate symbols in the first set or the second set of intermediate symbols is in the specified set of approximately one-half of the pre-coding relations in the second set of pre-coding relations.

28. The method of claim 25, wherein for each first intermediate symbol in the first set or second set of intermediate symbols and for each second intermediate symbol in the first set or second set of intermediate symbols that is the next consecutive intermediate symbol following the first intermediate symbol, the symmetric difference of pre-coding relations in the second set of pre-coding relations of which the first intermediate symbol is a member of the specified set and of which the second intermediate symbol is a member of the specified set is exactly two.

57. The method of claim 1, wherein the symbols are placed into one or more packets for transmission.

59. The method of claim 6, wherein the symbols are placed into packets for transmission and wherein an ESI is included in each packet to identify the first symbol placed into the packet.

60. The method of claim 59, wherein more than one symbol is placed into at least one packet and for packets that carry more than one symbol the ESIs for the second and subsequent symbols placed in the packet are determined by the ESI for the first symbol placed in the packet.

61. The method of claim 60, wherein the ESI determined for the second symbol placed in a packet is one greater than the ESI placed in the packet that is associated with the first symbol placed in the packet.

65. The method of claim 1 wherein the K source symbols correspond to a source block, wherein the source block is divided into N′

subblocks, wherein each of the N′

subblocks is composed of K′

sub-symbols, wherein one or more source blocks can correspond to a source file, wherein each of the one or more source blocks are encoded separately from the other source blocks.

66. The method of claim 65 wherein the source file is partitioned into one or more source blocks of approximately equal size as a function of the number of source symbols per source blocks and the number of source blocks, and wherein each source block is partitioned into one or more subblocks of approximately equal size as a function of the size of a source symbol and the number of sublocks per source block.

67. The method of claim 66 wherein more than one symbol is placed into a packet that is used for transmission.

68. The method of claim 66 wherein one or more parameters used to partition the source file into one or more source blocks and used to partition the one or more source blocks into one or more subblocks are made known at the destination of the symbols.

69. The method of claim 1 wherein the K source symbols correspond to a source block, wherein the source block is defined by a transport protocol for streaming data.

70. The method of claim 69 wherein one or more parameters used to determine how the K source symbols correspond to the source block are made known at the destination of the symbols.

71. The method of claim 69 wherein more than one symbol is placed into a packet that is used for transmission.

29. A method of decoding encoded data received over a communications channel transmitted from a source to a destination, the method comprising:

receiving a predetermined number, N, of symbols, wherein the symbols comprise a combination of received source symbols and repair symbols generated from a plurality of an ordered set of K source symbols,

generating to a desired degree of accuracy one or more of the not received source symbols among the ordered set of K source symbols,

wherein each symbol has an associated symbol relation that is determined by a systematic index, J(K), where J(K) is determined by K,

wherein the value of each not received source symbol is determined by the associated symbol relation and a plurality of L intermediate symbol values, wherein L is at least K,

wherein the L intermediate symbol values are determined by the K source symbol values and by the K symbol relations associated with the K source symbols and by a set of L-K pre-coding relations,

wherein the L intermediate symbol values can be generated to a desired degree of accuracy from the N received source and repair symbols,

wherein the value of each not received source symbol is determined by the associated symbol relation and the plurality of L intermediate symbol values.

30. The method of claim 29, further comprising precalculating and storing the systematic index J(K) in a table for each relevant value of K.

31. The method of claim 29, wherein the systematic index J(K) for values of K between 4 and 8192 is as provided in Appendix A.

32. The method of claim 29, wherein the symbol relations impose linear constraints on sets of symbols.

33. The method of claim 32, wherein the linear constraints are exclusive- or constraints.

34. The method of claim 29, wherein each symbol has an associated ESI that identifies the symbol, wherein the systematic index J(K) and a value X, wherein X is a valid ESI, determines the symbol relation for the symbol identified by ESI X.

35. The method of claim 34, wherein the systematic index J(K) and the ESI X can be used to generate a triple (a[X],b[X],d[X]) that defines the symbol relation for the symbol identified by ESI X.

36. The method of claim 34, wherein each source symbol can be identified by an integer ESI in the range 0 to K−

1, inclusive.

37. The method of claim 34, wherein each repair symbol can be identified by an integer ESI that is at least K.

38. The method of claim 35, wherein the triple (a[X],b[X],d[X]) that defines the source symbol relation associated with the source symbol with ESI X places the following linear constraint on the value C′

[X] for source symbol with ESI X and the values

C[0], C[1], ..., C[L−

1] of the L intermediate symbols;

defining an array of positive integer values B[0], ..., B[J−

1], wherein  

 

J is the minimum of d[X] and L, wherein L’

is the smallest integer  

 

that is prime that is at least the value of L, and wherein the values  

 

of the array of positive integer values B[0],...,B[J−

1]  

 

are set using the method comprising;

 

 

setting the initial value of B[0] to b[X];

 

 

while B[0] is at least L, recalculating B[0] as the previous  

 

value of B[0] plus a[X] modulo L’

;

 

 

for values of j starting at 1 and going up to J−

1 in increments of one,  

 

 

 

initializing the value of B[j] to B[j−

1] plus a[X];

 

 

 

 

while B[j] is at least L, recalculating B[j] as the  

 

previous value of B[j] plus a[X] modulo L’

.

39. The method of claim 35, wherein the generation of the triple

(a[X], b[X], d[X]) from an ESI X comprises the following steps:

40. The method of claim 39 further comprising:

determining d[X] based on a degree function applied to the input v.

41. The method of claim 39 further comprising:

determining a[X], wherein a[X] is in the range between 0 and L′

−

1, inclusive, wherein L′

is the smallest prime number greater than or equal to L, wherein L′

is calculated as one plus the output of the random generator applied to the inputs Y, 1 and L′

−

1.

42. The method of claim 39 further comprising:

determining b[X], wherein b[X] is in the range between 0 and L′

, inclusive, wherein b[X] is calculated as the output of the random generator applied to the input Y, 2 and L′

.

43. The method of claim 39, wherein the value of d[X] is determined based on v as follows:

if the value of v is between 0 and 10240, inclusive, then the value of d[X] is 1, if the value of v is between 10241 and 4911581, inclusive, then the value of d[X] is 2, if the value of v is between 4911582 and 712793, inclusive, then the value of d[X] is 3, if the value of v is between 712794 and 831694, inclusive, then the value of d[X] is 4, if the value of v is between 831695 and 948445, inclusive, then the value of d[X] is 10, if the value of v is between 948446 and 1032188, inclusive, then the value of d[X] is 11, if the value of v is between 1032189 and 1048575, inclusive, then the value of d[X] is 40.

44. The method of claim 39, wherein the random generator on inputs Y, i, and m is calculated as (V0[(Y+i) % 256]̂

(V1[(floor(Y/256)+i) % 256]) % m, where % is the modulo operator, ̂

is the exclusive- or operator,/is the division operator, floor calculates the largest integer that is at most the input value, and V0 and V1 are each tables of 256 integers chosen randomly or pseudo-randomly.

45. The method of claim 44, wherein the 256 values for table V0 is as described in Appendix B.1.

46. The method of claim 44, wherein the 256 values for table V1 is as described in Appendix B.2.

47. The method of claim 29, wherein the number L-K of pre-coding relations comprises a first set of S pre-coding relations and a second set of H pre-coding relations, and wherein the L intermediate symbols comprises a first set of K intermediate symbols, a second set of S intermediate symbols, and a third set of H intermediate symbols.

48. The method of claim 47, wherein each pre-coding relation in the first set of pre-coding relations is uniquely associated with an intermediate symbol in the second set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set of intermediate symbols, wherein each pre-coding relation is a linear constraint on the value of the associated intermediate symbol and the values of the intermediate symbols in the specified set.

49. The method of claim 48, wherein a linear constraint is an exclusive- or constraint.

50. The method of claim 48, wherein for each first pre-coding relation among the first set of pre-coding relations and for each second pre-coding relation among the first set of pre-coding relations, the number of intermediate symbols that are both in the specified set associated with the first pre-coding relation and in the specified set associated with the second pre-coding relation is at most 3.

51. The method of claim 48, wherein each of the intermediate symbols in the first set of intermediate symbols is in the specified set of exactly three of the pre-coding relations in the first set of pre-coding relations.

52. The method of claim 47,

wherein S is the smallest prime integer that is at least as large as 0.01*K+X, wherein X is the smallest positive integer such that X*(X−

1) is at least 2*K,

wherein H is the smallest integer such that fact[H]/(fact[H−

H′

]*fact[H′

]) is at least K+2, wherein fact is the factorial operator, wherein H′

is the smallest integer that is at least H/2.

53. The method of claim 47, wherein each pre-coding relation in the second set of pre-coding relations is uniquely associated with an intermediate symbol in the third set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set and second set of intermediate symbols, wherein the pre-coding relation is a linear constraint on the associated intermediate symbol and the intermediate symbols in the specified set.

54. The method of claim 53, wherein a linear constraint is an exclusive- or constraint.

55. The method of claim 53, wherein each of the intermediate symbols in the first set or the second set of intermediate symbols is in the specified set of approximately one-half of the pre-coding relations in the second set of pre-coding relations.

56. The method of claim 53, wherein for each first intermediate symbol in the first set or second set of intermediate symbols and for each second intermediate symbol in the first set or second set of intermediate symbols that is the next consecutive intermediate symbol following the first intermediate symbol, the symmetric difference of pre-coding relations in the second set of pre-coding relations of which the first intermediate symbol is a member of the specified set and of which the second intermediate symbol is a member of the specified set is exactly two.

58. The method of claim 29, wherein more than one source symbol is placed into at least one packet.

62. The method of claim 34, wherein the symbols are received in one or more packets and wherein an ESI is included in each packet to identify the first symbol placed into the packet.

63. The method of claim 62, wherein more than one symbol is placed into at least one packet, wherein the ESIs for the second and subsequent symbols placed in packets with more than one symbol are determined by the ESI for the first symbol placed in the packet.

64. The method of claim 63, wherein the ESI determined for the second symbol placed in a packet is one greater than the ESI placed in the packet that is associated with the first symbol placed in the packet.

72. The method of claim 29 wherein the K source symbols correspond to a source block, wherein the source block is defined by a transport protocol for streaming data.

73. The method of claim 72 wherein one or more parameters used to determine how the K source symbols correspond to the source block are made known at the destination of the symbols.

74. The method of claim 72 wherein more than one symbol is placed into a packet that is used for transmission.