GENERATING AND COMMUNICATING SOURCE IDENTIFICATION INFORMATION TO ENABLE RELIABLE COMMUNICATIONS

• US 20090067551A1
• Filed: 09/12/2008
• Published: 03/12/2009
• Est. Priority Date: 09/12/2007
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Seed, William, Prasad, Manu, Stockhammer, Thomas, Luby, Michael G., Chen, Steve
• Granted Patent: US 9,237,101 B2
• Time in Patent Office: Days
• US Class Current: 375/340
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0072 Error control for data other than payload data, e.g. control data
• CPC Class Codes: H04L 1/1841 Resequencing
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion

Abstract

A method of generating Source Identification information from a source packet stream and reliably transmitting the Source Identification information from a source to a destination over a communications channel is provided. The method operates on a set of source packets, wherein Source Identification information for each source packet to be transmitted is derived and delivered with the Source Identification information of all or most other source packets of an associated source block. The method includes techniques to minimize the network bandwidth required to deliver Source Identification information and techniques to overcome network impairments. When combined with FEC techniques, retransmission techniques, or combinations of FEC techniques and retransmission techniques, the methods described herein allow receivers to recover lost source packets, while simultaneously ensuring that the original source packets are not modified and thereby ensuring backwards compatibility for legacy receivers.

Claims

1. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:

generating source identification data from the K source data units;

transmitting a first data stream to a receiver, wherein the first data stream comprises a set of the source data units; and

transmitting a second data stream to the receiver, wherein the second data stream comprises the source identification data.

2. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine identification labels for the K source data units used to generate the source identification data.

3. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine identification labels for any source data unit.

4. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine a position of a given source data unit with respect to an ordering of all the source data units.

5. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine a position of a given source data unit with respect to a source-determined order sequence of all of the source data units.

6. The method of claim 1 wherein the second data stream further comprises repair data for the source data units.

7. The method of claim 1 wherein the second data stream further comprises repair data for the source identification data.

8. The method of claim 1 wherein the first data stream is transmitted via DVB-T and wherein the second data stream is transmitted via DVB-H.

9. The method of claim 1 further comprising:

receiving a request from the receiver for additional data; and

transmitting a third data stream to the receiver.

10. The method of claim 9 wherein the third data stream comprises a second set source data units.

11. The method of claim 9 wherein the third data stream comprises repair data for the source data units.

12. The method of claim 1 wherein generating source identification data from the K source data units comprises:

creating an ordered set S from each of the K source data units;

i) applying a hash function, H_i, to each member of S, wherein H_i maps the members of S to one of a possible L hash outputs and wherein H_i maps at least X of the members of S to a unique hash output;

ii) creating a vector corresponding to the L hash outputs, wherein the vector indicates which of the L hash outputs experience collisions and which of the L hash outputs uniquely map to a member of S;

iii) creating a set, S_i, comprising the elements of S that do not map to a unique hash output;

iv) iterating steps i-iii until either S_i is an empty set or a maximum number of iterations have been executed, wherein for each iteration of steps i-iii S_i is used as S, wherein for each iteration H_i is a hash function that differs from the hash function used during the previous iteration of steps i-iii, wherein for each iteration the values of L and X can change; and

generating source identification data from the vectors created during each iteration of steps i-iii.

13. The method of claim 12 wherein the vector further indicates the location of each uniquely mapped member of S in S, the method further comprising:

generating a position-to-sequence mapping from the location of the uniquely mapped members of S as indicated by the vectors created during each iteration of steps i-iii.

14. A computer readable medium comprising code for performing the method of claim 1.

15. A transmitter comprising a processor and the computer readable medium of claim 14 coupled to the processor.

16. A method for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:

receiving a plurality of source data units from a first data stream;

receiving source identification data from a second data stream; and

associating the source identification data with the plurality of source data units.

17. The method of claim 16 further comprising:

determining identification labels for the received plurality of source data units.

18. The method of claim 16 further comprising:

determining identification labels for any source data units that are not a member of the received plurality of source data units.

19. The method of claim 16 further comprising:

determining a position for a source data unit in the plurality of source data units with respect to an ordering of all the source data units.

20. The method of claim 16 further comprising:

determining a position for a source data unit in the plurality of source data units with respect to a source-determined order sequence of all of the source data units.

21. The method of claim 16 further comprising:

receiving repair data for the plurality of source data units from the second data stream.

22. The method of claim 16 further comprising:

receiving repair data for the source identification data from the second data stream.

23. The method of claim 16 wherein the first data stream is received via DVB-T and wherein the second data stream is received via DVB-H.

24. The method of claim 16 further comprising:

analyzing the source identification data and the plurality of source data units to determine if any of the K source data units have not been received; and

if any of the K source data units have not been received, requesting additional data.

25. The method of claim 24 further comprising:

receiving the additional data from a third data stream.

26. The method of claim 16 wherein associating the source identification data with the plurality of source data units comprises:

creating a set, S, from each of the plurality of source data units;

i) applying a hash function, Hi, to each member of S to obtain a hashed output associated with each of member of S, wherein H_i maps each of the members of S to one of a possible L hash outputs;

ii) determining which of the hashed outputs uniquely identify the source data unit associated with the hashed output;

iii) if it is determined that a hashed output does uniquely identify a source data unit, removing the uniquely identified source data unit from S and associating a proper set of identification data from the source identification data with the uniquely identified source data unit; and

iv) if it is determined that one of the hashed output is not unique, iterating steps i-iii unit S is an empty set or until a maximum number of iterations have been executed, wherein for each iteration H_i is a hash function that differs from the hash function used during the pervious iteration of steps i-iii with a potentially different value of L.

27. The method of claim 26 wherein the H_i applied for each iteration of steps i-iv is determined from the source identification data.

28. The method of claim 26 wherein determining which of the hashed outputs uniquely identify the source data unit associated with the hashed output comprises:

comparing each hashed output to a vector from the source identification data, wherein the vector corresponds to the possible L hash outputs, and wherein the vector indicates which of the L hash outputs experience collisions and which of the L hash outputs uniquely map to a member of S.

29. The method of claim 28 wherein the source identification data includes a position-to-sequence mapping and wherein associating a proper set of identification data from the source identification data with the uniquely identified source data unit comprises associating location information from the position-to-sequence mapping to the uniquely identified source data unit.

30. The method of claim 26 further comprising:

if a source data unit is associated with a proper set of identification data from the source identification data, passing the source data unit to a decoder.

31. The method of claim 26 further comprising:

if a source data unit is not associated with a proper set of identification data from the source identification data, discarding the source data unit.

32. A computer readable medium comprising code for performing the method of claim 16.

33. A receiver comprising a processor and the computer readable medium of claim 32 coupled to the processor.