Systems and methods for broadcasting information additive codes

• US 20040101274A1
• Filed: 07/10/2003
• Published: 05/27/2004
• Est. Priority Date: 09/23/1998
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Foisy, Christian, Luby, Michael, Shokrollahi, M. Amin, Vo, Joseph A.
• Granted Patent: US 7,243,285 B2
• Time in Patent Office: Days
• US Class Current: 386/46
• 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 information additive codes to one or more information additive code receivers, each information additive code transmitter comprising an encoder configured to receive source data and to produce information additive codes therefrom; and

one or more information additive code receivers configured to receive the information additive code broadcast by at least one of the one or more information additive code transmitters, each information additive code receiver comprising a decoder configured to reconstruct substantially a copy of the source data from the received information additive codes.

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 multi-stage encoder, and wherein the decoder comprises a multi-stage 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 one or more 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 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 source 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 the output the command signal to the cache unit.

10. The broadcast system of claim 9, 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;

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

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

12. The broadcast system of claim 1, wherein the information additive code transmitter further comprises a transmit module coupled to the encoder, the transmit module operable to modulate the information additive code onto a carrier signal, the carrier signal embodying the information additive code comprising a coded transmission.

13. The broadcast system of claim 12, wherein the information additive code receiver further comprises a receive module coupled to the decoder, the receive module operable to demodulate the coded transmission, thereby extracting the information additive code, the receive module supplying the extracted information additive code to the decoder.

14. An information additive code transmitter, comprising:

an encoder configured to receive source data and to produce information additive code therefrom; and

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

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 produces output symbols comprising the information additive code.

16. The information additive code transmitter of claim 14, wherein the encoder comprises a multi-stage 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, the output symbols comprising the information additive code.

17. 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 source 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 the output the command signal to the cache unit.

18. The information additive code transmitter of claim 17, 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;

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

19. The information additive code transmitter of claim 18, 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.

20. 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 the first segment data to produce a corresponding transmit block T₀;

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

means for transmitting a first of the two or more T₀ sub-blocks to a receiver on a first main sub-channel;

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₁ blocks, wherein each of the two or more T₁ blocks comprise substantially distinct FEC-encoded second segment data;

means for transmitting substantially concurrently, the second of the two or more T₀ sub-blocks on the first main sub-channel and a first of the two or more T₁ sub-blocks on a second main sub-channel; and

means for transmitting substantially concurrently, the first T₀ sub-block on a first booster sub-channel, and the first T₁ sub-block on a second booster sub-channel, wherein the second T₀ sub-block, the first T₁ sub-block, the first T₀ sub-block, and the first T₁ sub-block are all transmitted substantially concurrently,

wherein the T₀, T₁, and T₂ sub-blocks comprise the information additive code.

21. The information additive code transmitter of claim 14, further comprising a protocol converter coupled to the encoder and configured to convert the information additive code 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 information additive code onto a carrier signal, the carrier signal embodying the information additive code 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 information additive code broadcast from one or more information additive code transmitters, wherein the received information additive code comprises a plurality of output symbols; and

a decoder coupled to the receive module and configured to decode the received output symbols into source data.

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 key regenerator, the key regenerator operable to receive the output symbols and the decoding keys, and in response produces 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 multi-stage 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 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

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, in response, producing a second set of input symbols in response; and

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 information additive code 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 information additive codes from one or more transmitters to one or more receivers, the method comprising:

encoding source data to information additive code, the information additive code comprising a plurality of output symbols;

transmitting the information additive code to one or more information additive code receivers from one or more sources;

receiving information additive code from the one or more sources; and

decoding the information additive code into substantially a copy of the source data.

39. The method of claim 38, wherein encoding source data to information additive codes 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, the respective sequence of output symbols comprising the information additive code.

40. The method of claim 38, wherein decoding the information additive codes comprises:

generating a plurality of decoding keys corresponding to the received plurality of output symbols comprising the received information additive code; and

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

41. The method of claim 38, wherein transmitting comprises transmitting the information additive code 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 information additive codes via a satellite up link, cross-link, down link or by terrestrial link.

43. The method of claim 38, further comprising converting, prior to transmission, the protocol of the information additive code to a broadcast protocol.

44. The method of claim 38, further comprising converting, prior to decoding, the protocol of the received information additive code.

45. A method for broadcasting information additive code, comprising:

encoding source data to a plurality of output symbols comprising information additive code; and

transmitting the information additive code to one or more information additive code receivers.

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 information additive codes, comprising:

receiving information additive code broadcast from one of a plurality of sources, the received information additive code comprising a plurality of output symbols; and

decoding the plurality of output symbols into source data.

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.

53. A coded transmission comprising output symbols modulated onto a carrier signal and broadcast to a plurality of receivers, the coded transmission produced through the processes of:

encoding source data into output symbols; and

modulating the output symbols onto a carrier signal, the modulated carrier signal comprising the coded transmission.

54. The coded transmission of claim 53, 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.

55. The coded transmission of claim 54, 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.

56. The coded transmission of claim 54, 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.

57. A computer program product, on a computer readable storage medium, for broadcasting information additive codes, the computer program product comprising:

instruction code to encode source data into output symbols comprising information additive code; and

instruction code to transmit the information additive code to one or more information additive code receivers.

58. The computer program product of claim 57, 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.

59. The computer program product of claim 58, 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.

60. The computer program product of claim 58, 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.

61. A computer program product, on a computer readable storage medium, for receiving broadcast information additive codes, the computer program product comprising:

instruction code to receive a plurality of output symbols comprising the information additive code, the information additive code broadcast from one or more sources; and

instruction code to decode the received output symbols into source data.

62. The computer program product of claim 61, 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.

63. The computer program product of claim 61, 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.