Encoding and decoding using elastic codes with flexible source block mapping

Patent metadata

Field	Value
Publication number	US-9270299-B2
Application number	US-201113025900-A
Country	US
Kind code	B2
Filing date	Feb 11, 2011
Priority date	Feb 11, 2011
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

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.

First claim

The invention claimed is:

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 M 1 encoding symbols, the first source block comprises N 1 source symbols, the second set of encoding symbols comprises M 2 encoding symbols, the second source block comprises N 2 source symbols, and when an intersection of the first and second source blocks comprises N 3 source symbols with N 3 greater than zero, then recoverability of the union of the pair of source blocks is assured beyond a predetermined threshold probability if M 1 +M 2 =N 1 +N 2 −N 3 for at least some combinations of values of M 1 <N 1 and M 2 <N 2 .

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 M 1 +M 2 =N 1 +N 2 −N 3 for all combinations of values of M 1 and M 2 such that M 1 ≦N 1 and M 2 ≦N 2 .

4. The method of claim 2 , wherein the recoverability of the union of the pair of source blocks is certain if M 1 +M 2 =N 1 +N 2 −N 3 for all combinations of values of M 1 and M 2 such that M 1 ≦N 1 and M 2 ≦N 2 .

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 M 1 +M 2 is larger than N 1 +N 2 −N 3 by less than a predetermined percentage but smaller than N 1 +N 2 for at least some combinations of values of M 1 and M 2 .

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 sou

Assignees

• Luby Michael G
• Pakzad Payam
• Shokrollahi Mohammad Amin
• Watson Mark
• Qualcomm Inc

Inventors

• Luby Michael G
• Pakzad Payam
• Shokrollahi Mohammad Amin
• Watson Mark
• Vicisano Lorenzo

Classifications

• H03M13/3761 Primary

  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 title

• H04L1/007

  Unequal error protection (for format H04L1/0078; for codes per se H03M13/35) · CPC title

• H04L1/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 title

• H04L1/0083

  Formatting with frames or packets; Protocol or part of protocol for error control · CPC title

• H04L1/0086

  Unequal error protection (H04L27/00 and H04L1/004 take precedence for layer 1/2 aspects, e.g. bit loading) · CPC title