Encoding and decoding using elastic codes with flexible source block mapping

• US 9,270,299 B2
• Filed: 02/11/2011
• Issued: 02/23/2016
• Est. Priority Date: 02/11/2011
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Luby, Michael G., Pakzad, Payam, Shokrollahi, Mohammad Amin, Watson, Mark, Vicisano, Lorenzo
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US13/025,900
• Publication Number:
  US 20120210190A1
• Time in Patent Office: 1,838 Days
• Field of Search: None
• US Class Current: 1/1
• 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/0042 Encoding specially adapted to other signal generation operation, e.g. in order to reduce transmit distortions, jitter, or to improve signal shape H04L1/0067 takes precedence
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/007 Unequal error protection for format H04L1/0078; for codes per se H03M13/35
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control
• CPC Class Codes: H04L 1/0086 Unequal error protection H04L27/00 and H04L1/004 take precedence for layer 1/2 aspects, e.g. bit loading

Abstract

Data can be encoded by assigning source symbols to base blocks, assigning base blocks to source blocks and encoding each source block into encoding symbols, where at least one pair of source blocks is such they have at least one base block in common with both source blocks of the pair and at least one base block not in common with the other source block of the pair. The encoding of a source block can be independent of content of other source blocks. Decoding to recover all of a desired set of the original source symbols can be done from a set of encoding symbols from a plurality of source blocks wherein the amount of encoding symbols from the first source block is less than the amount of source data in the first source block and likewise for the second source block.

Claims

1. A method for encoding data to be transmitted from an electronic device or system to a receiver over a communications channel that could possibly introduce errors or erasures, wherein source data is represented by an ordered plurality of source symbols and the source data is recoverable from encoding symbols that are transmitted, the method comprising:

identifying a base block for each source symbol of the ordered plurality of source symbols, wherein the identified base block is one of a plurality of base blocks that, collectively, cover the source data to be encoded;

identifying, from a plurality of source blocks and for each base block, at least one source block that envelops that base block, wherein the plurality of source blocks includes at least one pair of source blocks that have a characteristic that there is at least one base block that is enveloped by both source blocks of the pair and at least one base block for each source block of the pair that is enveloped by that source block and not by the other source block of the pair;

encoding each of the plurality of source blocks according to an encoding process, resulting in encoding symbols, wherein the encoding process operates on one source block to generate encoding symbols, with the encoding symbols being independent of source symbol values of source symbols from base blocks not enveloped by the one source block, wherein the encoding is such that a portion of the source data that is represented by a union of the pair of source blocks is assured to be recoverable from a combination of a first set of encoding symbols generated from a first source block of the pair and a second set of encoding symbols generated from a second source block of the pair, wherein an amount of encoding symbols in the first set is less than an amount of source data in the first source block and an amount of encoding symbols in the second set is less than an amount of source data in the second source block; and

outputting the encoding symbols for transmission to the receiver over the communications channel.

2. The method of claim 1, wherein the encoding process is such that, when the encoding symbols and the source symbols have a same size, when the first set of encoding symbols comprises M1 encoding symbols, the first source block comprises N1 source symbols, the second set of encoding symbols comprises M2 encoding symbols, the second source block comprises N2 source symbols, and when an intersection of the first and second source blocks comprises N3 source symbols with N3 greater than zero, then recoverability of the union of the pair of source blocks is assured beyond a predetermined threshold probability if M1+M2=N1+N2−

N3 for at least some combinations of values of M1<

N1 and M2<

N2.

3. The method of claim 2, wherein the recoverability of the union of the pair of source blocks is assured beyond a predetermined threshold probability if M1+M2=N1+N2−

N3 for all combinations of values of M1 and M2 such that M1≦

N1 and M2≦

N2.

4. The method of claim 2, wherein the recoverability of the union of the pair of source blocks is certain if M1+M2=N1+N2−

N3 for all combinations of values of M1 and M2 such that M1≦

N1 and M2≦

N2.

5. The method of claim 2, wherein the recoverability of the union of the pair of source blocks is assured with a probability higher than a predetermined threshold probability if M1+M2 is larger than N1+N2−

N3 by less than a predetermined percentage but smaller than N1+N2 for at least some combinations of values of M1 and M2.

6. The method of claim 1, wherein at least one encoding symbol generated from a source block is equal to a source symbol from a portion of the source data that is represented by that source block.

7. The method of claim 1, wherein the encoding process is such that a portion of the source data that is represented by the first source block of the pair is assured to be recoverable from a third set of encoding symbols generated from the first source block, wherein an amount of encoding symbols in the third set is no greater than the amount of source data in the first source block.

8. The method of claim 1, wherein the encoding process is such that a portion of the source data that is represented by the first source block of the pair is assured to be recoverable with a probability higher than a predetermined threshold probability from a third set of encoding symbols generated from the first source block, wherein an amount of encoding symbols in the third set is only slightly greater than the amount of source data in the first source block.

9. The method of claim 1, wherein a number of distinct encoding symbols that can be generated from each source block is independent of a size of the source block.

10. The method of claim 1, wherein a number of distinct encoding symbols that can be generated from each source block depends on a size of the source block.

11. The method of claim 1, wherein identifying base blocks for source symbols is performed prior to a start to encoding.

12. The method of claim 1, wherein identifying source blocks for base blocks is performed prior to a start to encoding.

13. The method of claim 1, wherein at least one encoding symbol is generated before a base block is identified for each source symbol or before the enveloped base blocks are determined for each of the source blocks or before all of the source data is generated or made available.

14. The method of claim 1, further comprising:

receiving receiver feedback representing results at a decoder that is receiving or has received encoding symbols; and

adjusting one or more of membership of source symbols in base blocks, membership of base blocks in enveloping source blocks, number of source symbols per base block, number of symbols in a source block, and/or number of encoding symbols generated from a source block, wherein the adjusting is done based on, at least in part, the receiver feedback.

15. The method of claim 14, wherein adjusting includes determining new base blocks or changing membership of source symbols in previously determined base blocks.

16. The method of claim 14, wherein adjusting includes determining new source blocks or changing envelopment of base blocks for previously determined source blocks.

17. The method of claim 1, further comprising:

receiving data priority preference signals representing varying data priority preferences over the source data; and

adjusting one or more of membership of source symbols in base blocks, membership of base blocks in enveloping source blocks, number of source symbols per base block, number of symbols in a source block, and/or number of encoding symbols generated from a source block, wherein the adjusting is done based on, at least in part, the data priority preference signals.

18. The method of claim 1, wherein a number of source symbols in the base blocks enveloped by each source block is independent, as between two or more of the source blocks.

19. The method of claim 1, wherein source symbols identified to a base block are not consecutive within the ordered plurality of source symbols.

20. The method of claim 1, wherein source symbols identified to a base block are consecutive within the ordered plurality of source symbols.

21. The method of claim 20, wherein source symbols identified to the base blocks enveloped by a source block are consecutive within the ordered plurality of source symbols.

22. The method of claim 1, wherein a number of encoding symbols that can be generated for a source block is independent of a number of encoding symbols that can be generated for other source blocks.

23. The method of claim 1, wherein a number of encoding symbols generated for a given source block is independent of a number of source symbols in base blocks enveloped by the given source block.

24. The method of claim 1, wherein encoding further comprises:

determining, for each encoding symbol, a set of coefficients selected from a finite field; and

generating the encoding symbol as a combination of source symbols of one or more base blocks enveloped by a single source block, wherein the combination is defined, in part, by the set of coefficients.

25. The method of claim 1, wherein a number of symbol operations to generate an encoding symbol from a source block is linearly proportional to a number of source symbols in a portion of the source data that is represented by the source block.

26. A method for decoding data received at an electronic device or system and delivered from a transmitter over a communications channel that could possibly include errors or erasures, to recover source data that was represented by a set of source symbols, the method comprising:

identifying a base block for each source symbol, wherein the identified base block is one of a plurality of base blocks that, collectively, cover the source data;

identifying, from a plurality of source blocks and for each base block, at least one source block that envelops that base block, wherein the plurality of source blocks includes at least one pair of source blocks that have a characteristic that there is at least one base block that is enveloped by both source blocks of the pair and at least one base block for each source block of the pair that is enveloped by that source block and not by the other source block of the pair; and

receiving a plurality of received symbols;

for each received symbol, identifying a source block for which that received symbol is an encoding symbol for;

decoding a set of source symbols from the plurality of received symbols, wherein a portion of the source data that is represented by a union of the pair of source blocks is assured to be recoverable from a combination of a first set of received symbols corresponding to encoding symbols that were generated from a first source block of the pair and a second set of received symbols corresponding to encoding symbols that were generated from a second source block of the pair, wherein an amount of received symbols in the first set is less than an amount of source data in the first source block and an amount of received symbols in the second set is less than an amount of source data in the second source block; and

outputting the decoded source symbols in a computer-readable form.

27. The method of claim 26, wherein if N1 is a number of source symbols in source data of the first source block, if N2 is a number of source symbols in source data of the second source block, if N3 is a number of source symbols in an intersection of the first and second source blocks with N3 greater than zero, if the encoding symbols and the source symbols have a same size, if R1 is a number of received symbols in the first set of received symbols, if R2 is a number of received symbols in the second set of received symbols, then decoding the union of the pair of source blocks from the first set of R1 received symbols and from the second set of R2 received symbols is assured beyond a predetermined threshold probability if R1+R232 N1+N2 −

N3, for at least one value of R1 and R2 such that R1<

N1 and R2<

N2.

28. The method of claim 27, wherein decoding the union of the pair of source blocks is assured beyond a predetermined threshold probability if R1+R2=N1+N2−

N3 for all values of R1≦

N1 and R2≦

N2.

29. The method of claim 27, wherein decoding the union of the pair of source blocks is certain if R1+R2=N1+N2−

N3 for all values of R1≦

N1 and R2≦

N2.

30. The method of claim 26, wherein a portion of the source data that is represented by the first source block of the pair is recoverable from a third set of encoding symbols generated from the first source block, wherein an amount of encoding symbols in the third set is no greater than the amount of source data in the first source block.

31. The method of claim 26, wherein a number of distinct encoding symbols that can be generated from each source block is independent of a size of the source block.

32. The method of claim 26, wherein at least one of identifying base blocks for source symbols and identifying source blocks for base blocks is performed prior to a start to decoding.

33. The method of claim 26, wherein at least some source symbols are decoded before a base block is identified for each source symbol and/or before the enveloped base blocks are determined for each of the source blocks.

34. The method of claim 26, further comprising:

determining receiver feedback representing results at a decoder based on what received symbols have been received and/or what portion of the source data is desired at a receiver and/or data priority preference; and

outputting the receiver feedback such that it is usable for altering an encoding process.

35. The method of claim 26, wherein a number of source symbols in the base blocks enveloped by each source block is independent, as between two or more of the source blocks.

36. The method of claim 26, wherein source symbols identified to a base block are consecutive within an ordered plurality of source symbols that is the set of source symbols.

37. The method of claim 26, wherein source symbols identified to the base blocks enveloped by a source block are consecutive within an ordered plurality of source symbols that is the set of source symbols.

38. The method of claim 26, wherein decoding further comprises:

determining, for each received symbol, a set of coefficients selected from a finite field; and

decoding at least one source symbol from more than one received symbol or previously decoded source symbols using the set of coefficients for the more than one received symbol.

39. The method of claim 26, wherein a number of symbol operations to recover a union of one or more source blocks is linearly proportional to a number of source symbols in a portion of the source data that is represented by the union of one or more source blocks.

40. An encoder of an electronic device or system that encodes data for transmission to a receiver over a communications channel that could possibly introduce errors or erasures, comprising:

an input for receiving source data that is represented by an ordered plurality of source symbols and the source data is recoverable from encoding symbols that are transmitted;

storage for at least a portion of a plurality of base blocks, wherein each base block comprises a representation of one or more source symbols of the ordered plurality of source symbols;

a logical map, stored in a machine-readable form or generatable according to logic instructions, mapping each of a plurality of source blocks to one or more base blocks, wherein the plurality of source blocks includes at least one pair of source blocks that have a characteristic that there is at least one base block that is enveloped by both source blocks of the pair and at least one base block for each source block of the pair that is enveloped by that source block and not by the other source block of the pair;

storage for encoded blocks;

one or more encoders that each encode source symbols of a source block to form a plurality of encoding symbols, with a given encoding symbol being independent of source symbol values from source blocks other than the source block it encodes source symbols of, such that a portion of the source data that is represented by a union of the pair of source blocks is assured to be recoverable from a combination of a first set of encoding symbols generated from a first source block of the pair and a second set of encoding symbols generated from a second source block of the pair, wherein an amount of encoding symbols in the first set is less than an amount of source data in the first source block and an amount of encoding symbols in the second set is less than an amount of source data in the second source block; and

an output for outputting the encoding symbols for transmission to the receiver over the communications channel.

41. The encoder of claim 40, wherein a number of encoding symbols in the first set plus a number of encoding symbols in the second set is no greater than a number of source symbols in the portion of the source data that is represented by the union of the pair of source blocks, if the encoding symbols and the source symbols have a same size.

42. The encoder of claim 40, wherein a portion of the source data that is represented by the first source block of the pair is recoverable from a third set of encoding symbols generated from the first source block, wherein an amount of encoding symbols in the third set is no greater than the amount of source data in the first source block.

43. The encoder of claim 40, wherein a number of distinct encoding symbols that can be generated from each source block is independent of a size of the source block.

44. The encoder of claim 40, further comprising:

an input for receiving receiver feedback representing results at a decoder that is receiving or has received encoding symbols; and

logic for adjusting one or more of membership of source symbols in base blocks, membership of base blocks in enveloping source blocks, number of source symbols per base block, number of symbols in a source block, and/or number of encoding symbols generated from a source block, wherein the adjusting is done based on, at least in part, the receiver feedback.

45. The encoder of claim 40, further comprising:

an input for receiving data priority preference signals representing varying data priority preferences over the source data; and

logic for adjusting one or more of membership of source symbols in base blocks, membership of base blocks in enveloping source blocks, number of source symbols per base block, number of symbols in a source block, and/or number of encoding symbols generated from a source block, wherein the adjusting is done based on, at least in part, the data priority preference signals.

46. The encoder of claim 40, wherein a number of source symbols in the base blocks enveloped by each source block is independent, as between two or more of the source blocks.

47. The encoder of claim 40, wherein source symbols identified to a base block are consecutive within the ordered plurality of source symbols.

48. The encoder of claim 40, wherein source symbols identified to the base blocks enveloped by a source block are consecutive within the ordered plurality of source symbols.

49. The encoder of claim 40, wherein a number of distinct encoding symbols that can be generated for a source block is independent of a number of encoding symbols that can be generated for other source blocks.

50. The encoder of claim 40, wherein a number of distinct encoding symbols generated for a given source block is independent of a number of source symbols in base blocks enveloped by the given source block.

51. The encoder of claim 40, further comprising:

storage for a set of coefficients selected from a finite field for each of a plurality of the encoding symbols, wherein the one or more encoders further comprise

logic for generating the encoding symbol as a combination of source symbols of one or more base blocks enveloped by a single source block, wherein the combination is defined, in part, by the set of coefficients.