File download and streaming system

• US 9,236,887 B2
• Filed: 02/29/2012
• Issued: 01/12/2016
• Est. Priority Date: 05/07/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Shokrollahi, M. Amin, Watson, Mark
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US13/408,944
• Publication Number:
  US 20130067295A1
• Time in Patent Office: 1,413 Days
• Field of Search: 714/746, 714/799, 714/810
• US Class Current: 1/1
• 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 for transmission is representable by an ordered set of input symbols, the method comprising:

generating a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol in the plurality of redundant symbols is calculated using one or more of the ordered set of input symbols; and

generating a plurality of 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 symbols in 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,

wherein the generating of the plurality of redundant symbols is done using a deterministic process that ensures low common membership among redundant symbols,

wherein common membership between two redundant symbols is the set of input symbols that both redundant symbols depend upon and wherein low common membership between two redundant symbols is present when the number of input symbols that both redundant symbols depend upon is less than a threshold as given by said process and

wherein for each input symbol there is a predetermined number of redundant symbols that depend upon said input symbol.

2. The method of claim 1, further comprising transmitting the plurality of output symbols over said communications channel.

3. The method of claim 1, further comprising storing the plurality of output symbols on a storage media.

4. The method of claim 1, wherein the plurality of redundant symbols is generated according to a LDPC code.

5. The method of claim 1, wherein output symbols are such that the ordered set of input symbols can be regenerated from any predetermined number, N, of the output symbols, where N is slightly larger than the number of input symbols.

6. The method of claim 1, wherein the output symbols are such that there is a high probability that the ordered set of input symbols can be regenerated from N of the output symbols where N is at least as large as the number of input symbols.

7. The method of claim 1, wherein the output symbols are such that G of the ordered set of input symbols can be regenerated from K of the output symbols where K is the number of input symbols and G is less than K.

8. The method of claim 1, wherein at most G input symbols can be regenerated from any number of output symbols, wherein G is less than the number of input symbols in the ordered set of input symbols.

9. The method of claim 1, wherein generating a plurality of redundant symbols includes, for each redundant symbol:

determining t distinct input symbols according to a weight distribution; and

computing each redundant symbol as the XOR of the t distinct input symbols.

10. The method of claim 1, further comprising transmitting the plurality of output symbols over said communications channel, wherein the step of generating the plurality of output symbols is performed substantially concurrently with the step of transmitting the plurality of output symbols.

11. The method of claim 1, wherein the plurality of redundant symbols comprises static symbols, Hamming symbols and padding symbols, wherein the sum of the number of symbols is selected to be a prime number.

12. The method of claim 1, wherein the predefined threshold is six, such that for any two distinct redundant symbols, the sets of input symbols that each of those two distinct redundant symbols depend on have at most six input symbols in common.

13. The method of claim 1, wherein generating the plurality of redundant symbols using one or more of the ordered set of input symbols comprises:

initializing an array C[K], . . . , C[K+S−

1] so that each array element is a known value, wherein K is the number of input symbols and S is the number of redundant symbols to be generated and C[0], . . . , C[K−

1] corresponds to the K input symbols;

performing the following steps, with a counter i=0, wherein a and b are intermediate variables, “

%”

represents a modulo operation, floor( ) is a function representing a highest integer value that is less than the function'"'"'s argument, and “

^”

represents a bitwise XOR operation;

(1) a=1+(floor(i/S) % (S−

1))

(2) b=1% S

(3) C[K+b]=C[K+b]^C[i]

(4) b=(b+a) % S

(5) C[K+b]=C[K+b]^C[i]

(6) b=(b+a) % S

(7) C[K+b]=C[K+b]^C[i]

repeating those steps, for each value of counter i from 1 to K−

1; and

outputting at least the resulting array C[K], . . . , C[K+S−

1] as the plurality of S redundant symbols.

14. The method of claim 13, wherein S is the smallest prime integer such that S≧

ceil(0.01·

K)+X, where X is the smallest positive integer such that X·

(X−

1)=2·

K.

15. The method of claim 1, wherein for each input symbol the predetermined number of redundant symbols that depend upon said input symbol is three.

16. A system for encoding data for transmission from a source to a destination over a communications channel, wherein the data for transmission is representable by an ordered set of input symbols, the system comprising:

a static encoder configured to generate a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol in the plurality of redundant symbols is calculated using one or more of the ordered set of input symbols; and

a dynamic encoder communicatively coupled to the static encoder and configured to generate a plurality of 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 symbols in 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,

wherein the static encoder is configured to generate the plurality of redundant symbols using a deterministic process that ensures low common membership among redundant symbols,

wherein common membership between two redundant symbols is the set of input symbols that both redundant symbols depend upon and wherein low common membership between two redundant symbols is present when the number of input symbols that both redundant symbols depend upon is less than a threshold as given by said process and

wherein for each input symbol there is a predetermined number of redundant symbols that depend upon said input symbol.

17. The system of claim 16, further comprising a transmit module communicatively coupled to the dynamic encoder and configured to transmit the plurality of output symbols over said communications channel.

18. The system of claim 16, wherein the static encoder is configured to generate the plurality of redundant symbols using one or more of the ordered set of input symbols including:

initializing an array C[K], . . . , C[K+S−

1] so that each array element is a known value, wherein K is the number of input symbols and S is the number of redundant symbols to be generated and C[0], . . . , C[K−

1] corresponds to the K input symbols;

performing the following steps, with a counter i=0, wherein a and b are intermediate variables, “

%”

represents a modulo operation, floor( ) is a function representing a highest integer value that is less than the function'"'"'s argument, and “

^”

represents a bitwise XOR operation;

(1) a=1+(floor(i/S) % (S−

1))

(2) b=1% S

(3) C[K+b]=C[K+b]^C[i]

(4) b=(b+a) % S

(5) C[K+b]=C[K+b]^C[i]

(6) b=(b+a) % S

(7) C[K+b]=C[K+b]^C[i]

repeating those steps, for each value of counter i from 1 to K−

1; and

outputting at least the resulting array C[K], . . . , C[K+S−

1] as the plurality of S redundant symbols.

19. The system of claim 18, wherein S is the smallest prime integer such that S≧

ceil(0.01·

K)+X, where X is the smallest positive integer such that X·

(X−

1)=2·

K.

20. A non-transitory computer-readable medium for use with electronics capable of executing instructions read from the computer-readable medium in order to implement encoding data for transmission from a source to a destination over a communications channel, wherein the data for transmission is representable by an ordered set of input symbols, the computer-readable medium having stored thereon:

program code for generating a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol in the plurality of redundant symbols is calculated using one or more of the ordered set of input symbols; and

program code for generating a plurality of 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 symbols in 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,

wherein the program code for generating the plurality of redundant symbols uses a deterministic process that ensures low common membership among redundant symbols,

wherein common membership between two redundant symbols is the set of input symbols that both redundant symbols depend upon and wherein low common membership between two redundant symbols is present when the number of input symbols that both redundant symbols depend upon is less than a threshold as given by said process and

wherein for each input symbol there is a predetermined number of redundant symbols that depend upon said input symbol.

21. A system for encoding data for transmission from a source to a destination over a communications channel, wherein the data for transmission is representable by an ordered set of input symbols, the system comprising:

means for generating a plurality of redundant symbols from the ordered set of input symbols, wherein each redundant symbol in the plurality of redundant symbols is calculated using one or more of the ordered set of input symbols; and

means for generating a plurality of 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 symbols in 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,

wherein the means for generating the plurality of redundant symbols includes means for using a deterministic process that ensures low common membership among redundant symbols,

wherein common membership between two redundant symbols is the set of input symbols that both redundant symbols depend upon and wherein low common membership between two redundant symbols is present when the number of input symbols that both redundant symbols depend upon is less than a threshold as given by said process and

wherein for each input symbol there is a predetermined number of redundant symbols that depend upon said input symbol.

22. A system for decoding encoded data received over a communications channel transmitted from a source to a destination, the system comprising:

a receive module configured to receive a predetermined number, N, of symbols, wherein the received symbols comprise a combination of received source symbols and received repair symbols generated from a plurality of an ordered set of K source symbols; and

a decoder communicatively coupled to the receive module and configured to generate to a desired degree of accuracy one or more unreceived source symbols of the ordered set of K source symbols,

wherein each received 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 unreceived 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, and

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

23. The system of claim 22, wherein each source symbol has an associated encoding symbol identifier (“

ESI”

) that identifies the source symbol, wherein the systematic index J(K) and a value X, wherein X is a valid ESI, determines the symbol relation for the source symbol identified by ESI X.

24. The system of claim 22, 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.

25. The system of claim 22, wherein the K source symbols correspond to a source block, wherein the source block is defined by a transport protocol for streaming data.

26. A non-transitory computer-readable medium for use with electronics capable of executing instructions read from the computer-readable medium in order to implement decoding encoded data received over a communications channel transmitted from a source to a destination, the computer-readable medium having stored thereon:

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

program code for generating to a desired degree of accuracy one or more unreceived source symbols of the ordered set of K source symbols,

wherein each received 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 unreceived 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, and

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

27. A system for decoding encoded data received over a communications channel transmitted from a source to a destination, the system comprising:

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

means for generating to a desired degree of accuracy one or more unreceived source symbols of the ordered set of K source symbols,

wherein each received 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 unreceived 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, and

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