Systems and methods for broadcasting information additive codes

• US 7,243,285 B2
• Filed: 07/10/2003
• Issued: 07/10/2007
• Est. Priority Date: 09/23/1998
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Shokrollahi, M. Amin, Foisy, Christian, Vo, Joseph A.
• Primary Examiner(s): Baker; Stephen M.
• Application Number:
  US10/618,455
• Publication Number:
  US 20040101274A1
• Time in Patent Office: 1,461 Days
• Field of Search: 714/752, 714/776
• US Class Current: 714/752
• 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 2001/0093 Point-to-multipoint
• CPC Class Codes: H04N 21/23617 by inserting additional data into a data carousel, e.g. inserting software modules into a DVB carousel arrangements for broadcast or for distribution of identical information repeatedly in broadcast distribution systems H04H20/16
• CPC Class Codes: H04N 21/4349 by extracting from data carousels, e.g. extraction of software modules from a DVB carousel

Abstract

A broadcasting system for communicating data to multiple receivers using information additive code includes one or more information additive code transmitters and one or more information additive code receivers. Each of the information additive code transmitters includes an encoder configured to receive source data and to produce information additive code therefrom. Each of the information additive code receivers includes a decoder configured to receive the information additive code and to reconstruct therefrom substantially a copy of the source data.

Claims

1. A broadcast system, comprising:

one or more information additive code transmitters configured to broadcast output symbols generated from information additive codes to a plurality of information additive code receivers, each information additive code transmitter comprising an encoder configured to receive source data and to produce the output symbols therefrom, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data; and

the plurality of information additive code receivers configured to receive the output symbols broadcast by the one or more information additive code transmitters, each information additive code receiver comprising a decoder configured to substantially reconstruct a copy of the source data from the received output symbols;

wherein the output symbols transmitted to the plurality of information additive code receivers at any particular time is independent of the output symbols previously received by each of the plurality of information additive code receivers, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data has been received at each of the plurality of information additive code receivers, the plurality of information additive code receivers reconstruct the source data independent of when, and from which of the one or more information additive code transmitters the output symbols were received.

2. The broadcast system of claim 1, wherein the encoder comprises a single-stage encoder, and wherein the decoder comprises a single-stage decoder.

3. The broadcast system of claim 1, wherein the encoder comprises a multistage encoder, and wherein the decoder comprises a multistage decoder.

4. The broadcast system of claim 1, wherein the information additive code transmitter further comprises a protocol converter coupled to the encoder, and wherein the information additive code receiver comprises a protocol converter coupled to the decoder.

5. The broadcast system of claim 1, wherein at least one of the plurality of information additive code receivers further comprises means for receiving data via a secondary channel.

6. The broadcast system of claim 1, wherein the coded transmission is communicated via a satellite link.

7. The broadcast system of claim 1, wherein the coded transmission is communicated via a terrestrial wireless link.

8. The broadcast system of claim 1, wherein the coded transmission is communicated via an electrical or optical cable.

9. The broadcast system of claim 1, wherein the one or more information additive code transmitters further comprise a transmit module coupled to the encoder, the transmit module operable to modulate the output symbols onto a carrier signal, the carrier signal modulated with the output symbols comprising a coded transmission.

10. The broadcast system of claim 9, wherein the plurality of information additive code receivers further comprise a receive module coupled to the decoder, the receive module operable to demodulate the coded transmission, thereby extracting the output symbols, the receive module supplying the extracted output symbols to the decoder.

11. The broadcast system of claim 1, wherein the encoder further comprises:

a cache unit having an input coupled to receive segments of source data and an output coupled to the encoder, the cache unit configured to store segments of source data and to output segments of source data to the encoder upon receipt of a command; and

a control unit coupled to the cache unit and to the encoder, the control unit configured to output the command signal to the cache unit.

12. The broadcast system of claim 11, wherein the cache unit further comprises:

an upload unit having an input coupled to receive segments of source data, a command port coupled to the control unit, and an output; and

two or more segment buffers having an input coupled to the upload unit and an output coupled to the encoder.

13. The broadcast system of claim 12, wherein the encoder comprises two or more encoders each having an input coupled to the output of the two or more segment buffers.

14. An information additive code transmitter, comprising:

an encoder configured to receive source data and to produce output symbols generated from the source data using information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data; and

a transmit module coupled to the encoder and configured to broadcast the output symbols to a plurality of information additive code receivers;

wherein the output symbols transmitted to the plurality of information additive code receivers at any particular time is independent of the output symbols previously received by each of the plurality of information additive code receivers, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data has been received, the information additive code receivers reconstruct the source data independent of when, or in what order the output symbols were received.

15. The information additive code transmitter of claim 14, wherein the encoder comprises a single stage encoder, further comprising:

an input symbol generator configured to receive the source data and to provide an ordered sequence of input symbols in response;

a key generator operable to output an encoding key for each input symbol in the ordered sequence; and

a symbol encoder coupled to the input symbol generator and the key generator, the symbol encoder operable to receive the ordered sequence of input symbols and the encoding key for each input symbol, and in response produce the output symbols.

16. The information additive code transmitter of claim 14, wherein the encoder comprises a multistage encoder, comprising:

an input symbol generator having an input for receiving the source data and an output for providing an ordered sequence of input symbols in response;

a static key generator configured to provide a sequence of static encoding keys corresponding to the sequence of input symbols;

a dynamic key generator configured to provide a sequence of dynamic encoding keys corresponding to the sequence of input symbols; and

a symbol encoder coupled to the input symbol generator, the static key generator, and the dynamic key generator, the symbol encoder comprising;

a static encoder configured to receive the ordered sequence of input symbols and the corresponding sequence of static encoding keys, the static encoder producing a sequence of redundant symbols in response; and

a dynamic encoder coupled to the static encoder and configured to receive the sequence of redundant symbols and the sequence of dynamic encoding keys, the dynamic encoder producing a sequence of output symbols in response.

17. The information additive code transmitter of claim 14, wherein the encoder comprises:

means for receiving a first segment of a live data stream, the first segment S₀ containing first segment data;

means for applying a forward error correction algorithm to the first segment data to produce a corresponding transmit block T₀;

means for dividing the T₀ block into two or more T₀ subblocks, wherein each of the two or more T₀ subblocks comprise substantially distinct FEC-encoded first segment data;

means for transmitting a first of the two or more T₀ subblocks to a receiver on a first main subchannel;

means for receiving a second segment of the live data stream, the second segment S₁ containing second segment data;

means for applying a forward error correction algorithm to the second segment data to produce a transmit block T₁;

means for dividing the T₁ block into two or more T₁ subblocks, wherein each of the two or more T₁ subblocks comprise substantially distinct FEC-encoded second segment data;

means for transmitting substantially concurrently, the second of the two or more T₀ subblocks on the first main subchannel and a first of the two or more T₁ subblocks on a second main subchannel; and

means for transmitting substantially concurrently, the first T₀ subblock on a first booster subchannel, and the first T₁ subblock on a second booster subchannel, wherein the second T₀ subblock, the first T₁ subblock, the first T₀ subblock, and the first T₁ subblock are all transmitted substantially concurrently, wherein the T₀, T₁, and T₂ subblocks comprise the output symbols.

18. The information additive code transmitter of claim 14, wherein the encoder comprises:

a cache unit having an input coupled to receive segments of source data and an output coupled to the encoder, the cache unit configured to store segments of source data and to output segments of source data to the encoder upon receipt of a command; and

a control unit coupled to the cache unit and to the encoder, the control unit configured to output the command signal to the cache unit.

19. The information additive code transmitter of claim 18, wherein the cache unit further comprises:

an upload unit having an input coupled to receive segments of source data, a command port coupled to the control unit, and an output; and

two or more segment buffers having an input coupled to the upload unit and an output coupled to the encoder.

20. The information additive code transmitter of claim 19, wherein the encoder comprises a respective two or more encoders each having an input coupled to the output of the two or more segment buffers.

21. The information additive code transmitter of claim 14, further comprising a protocol converter coupled to the encoder and configured to convert the output symbols from a first protocol to a second protocol.

22. The information additive code transmitter of claim 21, wherein the first protocol is an IP protocol and the second protocol is a satellite broadcasting system protocol.

23. The information additive code transmitter of claim 21, wherein the first protocol is an IP protocol and the second protocol is a terrestrial broadcasting system protocol.

24. The information additive code transmitter of claim 14, further comprising a transmit module coupled to the encoder, the transmit module operable to modulate the output symbols onto a carrier signal, the carrier signal modulated with the output symbols comprising a coded transmission.

25. The information additive code transmitter of claim 24, wherein the carrier signal comprises a satellite uplink, cross-link, or down link signal.

26. The information additive code transmitter of claim 24, wherein the carrier signal comprises a terrestrial broadcast signal.

27. An information additive code receiver, comprising:

a receive module configured to receive output symbols generated from information additive code, wherein the output symbols are broadcast from one or more information additive code transmitters, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data, wherein the output symbols received from the one or more information additive code transmitters at any particular time is independent of the output symbols previously received; and

a decoder coupled to the receive module and configured to decode the received output symbols into source data, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data has been received, the receiver module reconstructs the source data independent of when, or from which of the one or more information additive code transmitters the output symbols were received.

28. The information additive code receiver of claim 27, wherein the decoder comprises a single stage decoder, further comprising:

a key regenerator coupled to the receive module, the key regenerator configured to receive the output symbols, and to produce respective decoding keys in response;

a symbol decoder coupled to the receive module and to the key regenerator, the key regenerator operable to receive the output symbols and the decoding keys, and in response produce the input symbols; and

an input file reassembler coupled to the symbol decoder and configured to receive and reassemble the input symbols into source data.

29. The information additive code receiver of claim 27, wherein the decoder comprises a multistage decoder, further comprising:

a dynamic key regenerator coupled to the receive module, and configured to receive the output symbols and to produce respective dynamic keys in response;

a symbol decoder, further comprising;

a) a dynamic decoder coupled to the dynamic key regenerator and the received module, the dynamic decoder configured to receive the output symbols and the dynamic keys, and to produce a first set of input symbols and redundant symbols in response; and

b) a static decoder coupled to the dynamic decoder and configured to receive the redundant symbols, the first set of input symbols, and static keys, the static decoder producing a second set of input symbols in response; and

c) an input file reassembler coupled to the symbol decoder and configured to receive and reassemble the first and second set of input symbols into source data.

30. The information additive code receiver of claim 27, wherein each of the plurality of output symbols is associated with one or more input symbols, wherein an output symbol associated with one symbol comprises an output symbol of degree, wherein an output symbol associated with two or more source symbols comprises an output symbol of degree two or more, and wherein at least one source symbol is marked as active, the information additive code receiver, further comprising:

means for selecting one of the active source symbols that is associated with an output symbol of degree two or higher; and

means for deactivating the selected source symbol that is associated with the output symbol of degree two or higher.

31. The information additive receiver of claim 30, further comprising:

means for identifying at least one output symbol which is associated with only one active source symbol;

means for recovering the active source symbol associated with the identified output symbol; and

means for determining that no output symbol remains which is associated with only one active source symbol.

32. The information additive code receiver of claim 27, further comprising a protocol converter having an input coupled to the receive module and an output coupled to the decoder, the protocol converter configured to convert the received output symbols from a first protocol to a second protocol.

33. The information additive code receiver of claim 32, wherein the first protocol is a satellite broadcasting system protocol and the second protocol is an IP protocol.

34. The information additive code receiver of claim 32, wherein the first protocol is a terrestrial broadcasting system protocol and the second protocol is an IP protocol.

35. The information additive code receiver of claim 27, wherein the received output symbols are modulated onto a carrier signal prior to transmission, the output symbol modulated carrier signal comprising a coded transmission, the receive module further comprising a demodulator operable to demodulate the coded transmission, thereby extracting the output symbols, the receive module supplying the extracted output symbols to the decoder.

36. The information additive code transmitter of claim 35, wherein the carrier signal comprises a satellite uplink, cross-link, or down link signal.

37. The information additive code transmitter of claim 35, wherein the carrier signal comprises a terrestrial broadcast signal.

38. A method for communicating output symbols from one or more transmitters to one or more receivers, the method comprising:

encoding source data into a plurality of output symbols using information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data;

transmitting the output symbols to a plurality of information additive code receivers from one or more sources;

receiving output symbols from the one or more sources, wherein the output symbols received from the one or more sources at any particular time is independent of which output symbols were previously received, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data has been received, the one or more information additive code receivers reconstruct the source data independent of when, or in what order the output symbols were received; and

decoding the output symbols substantially into a copy of the source data.

39. The method of claim 38, wherein encoding source data to output symbols comprises:

arranging the source data into an ordered sequence of input symbols; and

generating, from the ordered sequence of input symbols, a respective sequence of output symbols.

40. The method of claim 38, wherein decoding the output symbols comprises:

generating a plurality of decoding keys corresponding to the received plurality of output symbols; and

generating substantially, from the output symbols and the decoding keys, a copy of the source data.

41. The method of claim 38, wherein transmitting comprises transmitting the output symbols via a satellite up link, cross-link, down link or by a terrestrial link.

42. The method of claim 38, wherein receiving comprises receiving the output symbols via a satellite up link, cross-link, down link or by a terrestrial link.

43. The method of claim 38, further comprising converting, prior to transmission, the protocol of the output symbols to a broadcast protocol.

44. The method of claim 38, further comprising converting, prior to decoding, the protocol of the received output symbols.

45. A method for broadcasting output symbols generated from information additive code, comprising:

encoding source data into a plurality of output symbols using information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data, wherein the output symbols transmitted any particular time is independent of the output symbols previously transmitted; and

transmitting the output symbols to one or more a plurality of information additive code receivers, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data has been received, the plurality of information additive code receivers reconstruct the source data independent of when, or in what order the output symbols were received.

46. The method of claim 45, wherein encoding source data comprises:

arranging the source data into an ordered sequence of input symbols; and

generating, from the ordered sequence of input symbols, a respective sequence of output symbols.

47. The method of claim 46, wherein generating a respective sequence of output symbols comprises:

generating a sequence of encoding keys corresponding to the sequence of input symbols; and

generating, from the respective sequences of the input symbols and the encoding keys, the respective sequence of output symbols.

48. The method of claim 46, wherein generating a respective sequence of output symbols comprises:

generating a sequence of static encoding keys corresponding to the sequence of input symbols;

generating a sequence of dynamic encoding keys corresponding to the sequence of input symbols;

generating, from respective sequences of the input symbols and the static encoding keys, a respective sequence of redundant symbols; and

generating, from respective sequences of the input symbols, dynamic encoding keys, and redundant symbols, a respective sequence of output symbols.

49. A method for receiving broadcast output symbols, comprising:

receiving a plurality of output symbols broadcast from one or more of a plurality of sources, the plurality of output symbols generated from information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data wherein the plurality of output symbols received at any particular time is independent of which of the plurality of output symbols was previously received; and

wherein when an amount of non-redundant output symbols sufficient to decode the source data has been received, decoding the plurality of output symbols into source data, wherein the decoding is performed independent of when, or from which of the one or more information additive code sources the plurality of output symbols were received.

50. The method of claim 49, wherein the plurality of output symbols comprises a sequence of output symbols, and wherein decoding the output symbols comprises:

generating, from the sequence of output symbols, a respective sequence of decoding keys;

generating from the sequence of output symbols and the respective sequence of decoding keys, a respective sequence of input symbols; and

reassembling the respective sequence of input symbols into the source data.

51. The method of claim 49, wherein the plurality of output symbols comprises a sequence of output symbols, and wherein decoding the output symbols comprises:

generating, from the sequence of output symbols, a respective sequence of dynamic decoding keys;

generating a respective sequence of static decoding keys;

generating, from the respective sequences of output symbols, the dynamic decoding keys, and the static encoding keys, a respective sequence of input symbols; and

reassembling the respective sequence of input symbols into the source data.

52. A method of generating a coded transmission comprising output symbols modulated onto a carrier signal and broadcast to a plurality of receivers, the method comprising:

encoding source data into output symbols using information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data; and

modulating the output symbols onto a carrier signal, the modulated carrier signal comprising the coded transmission, wherein the output symbols modulated onto the carrier signal at any particular time are independent of which of the output symbols were previously received by the plurality of receivers, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data have been received, the receivers reconstruct the source data independent of when, or which of the output symbols, or in what order the output symbols were received.

53. The method of claim 52, wherein the process of encoding the source data into output symbols comprises:

arranging the source data into an ordered sequence of input symbols; and

generating, from the ordered sequence of input symbols, a respective sequence of output symbols.

54. The method of claim 53, wherein generating a respective sequence of output symbols comprises:

generating a sequence of encoding keys corresponding to the sequence of input symbols; and

generating, from the respective sequences of the input symbols and the encoding keys, the sequence of output symbols.

55. The method of claim 53, wherein generating a respective sequence of output symbols comprises:

generating a sequence of static encoding keys corresponding to the sequence of input symbols;

generating a sequence of dynamic encoding keys corresponding to the sequence of input symbols;

generating, from respective sequences of the input symbols and the static encoding keys, a respective sequence of redundant symbols; and

generating, from respective sequences of the input symbols, dynamic encoding keys, and redundant symbols, the sequence of output symbols.

56. A computer program product, on a computer readable storage medium, for broadcasting output symbols, the computer program product comprising:

instruction code to encode source data into output symbols using information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data; and

instruction code to transmit the output symbols to a plurality of information additive code receivers, wherein the output symbols when transmitted to the plurality of information additive code receivers is independent of which output symbols were previously received by the plurality of information additive code receivers, wherein when an amount of non-redundant output symbols sufficient to reconstruct the source data have been received, the plurality of information additive code receivers reconstruct the source data independent of when, or which non-redundant output symbols, or in what order the output symbols were received.

57. The computer program product of claim 56, wherein the instruction code to encode the source data into output symbols comprises:

instruction code to arrange the source data into an ordered sequence of input symbols; and

instruction code to generate a respective sequence of output symbols from the ordered set of input symbols.

58. The computer program product of claim 57, wherein the instruction code to generate a respective sequence of output symbols comprises:

instruction code to generate a sequence of encoding keys corresponding to the sequence of input symbols; and

instruction code to generate, from the respective sequences of the input symbols and the encoding keys, the sequence of output symbols.

59. The computer program product of claim 57, wherein the instruction code to generate a respective sequence of output symbols comprises:

instruction code to generate a sequence of static encoding keys corresponding to the sequence of input symbols;

instruction code to generate a sequence of dynamic encoding keys corresponding to the sequence of input symbols;

instruction code to generate, from respective sequences of the input symbols and the static encoding keys, a respective sequence of redundant symbols; and

instruction code to generate, from respective sequences of the input symbols, dynamic encoding keys, and redundant symbols, the sequence of output symbols.

60. A computer program product, on a computer readable storage medium, for receiving broadcast output symbols, the computer program product comprising:

instruction code to receive a plurality of output symbols generated from source data using the information additive code, wherein the information additive code is such that a number of possible output symbols can be independent of a number of input symbols derived from the source data, the output symbols broadcast from one or more sources; and

instruction code to decode the received output symbols into source data, wherein the output symbols, when received, are independent of which output symbols were previously received, wherein when an amount of non-redundant output symbols sufficient to decode the source data have been received, the instruction code to decode the received output symbols decodes the output symbols independent of when, which of the output symbols, and in what order the output symbols were received.

61. The computer program product of claim 60, wherein the received output symbols comprise a sequence of output symbols, and wherein the instruction code to decode the output symbols comprises:

instruction code to generate, from the sequence of received output symbols, a respective sequence of decoding keys;

instruction code to generate from the sequence of received output symbols and the respective sequence of decoding keys, a respective sequence of input symbols; and

instruction code to reassemble the sequence of input symbols into the source data.

62. The computer program product of claim 60, wherein the received output symbols comprise a sequence of output symbols, and wherein the instruction code to decode the output symbols comprises:

instruction code to generate, from the sequence of received output symbols, a respective sequence of dynamic decoding keys;

instruction code to generate a respective sequence of static decoding keys;

instruction code to generate, from the respective sequences of received output symbols, the dynamic decoding keys, and the static encoding keys, a respective sequence of input symbols; and

instruction code to reassemble the sequence of input symbols into the source data.