File download and streaming system
View Patent ↗A method of encoding data for transmission from a source to a destination over a communications channel is provided. The method operates on an ordered set of input symbols and includes generating a plurality of redundant symbols from the input symbols. The method also includes 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, and such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from any predetermined number of the output symbols. The plurality of redundant symbols is generated from an ordered set of input symbols to be transmitted 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.
1. A method of encoding data for transmission from a source to a destination over a communications channel, the method comprising:
generating a plurality of redundant symbols from an ordered set of input symbols to be transmitted 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; 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, such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from any predetermined number, N, of the output symbols.
2. The method of claim 1 , further comprising transmitting the plurality of output symbols over a 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 the desired accuracy is complete recovery of the input symbols.
6. The method of claim 1 , wherein the desired accuracy is complete recovery of the input symbols with a high probability.
7. The method of claim 1 , wherein the desired accuracy is recovery of G input symbols, wherein G is less than the number of input symbols in the ordered set of input symbols.
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 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 a 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.