Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes

• US 9,660,763 B2
• Filed: 07/27/2016
• Issued: 05/23/2017
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Luby, Michael G., Minder, Lorenz Christoph, Shokrollahi, Mohammad Amin
• Primary Examiner(s): NGUYEN, LINH V
• Application Number:
  US15/221,476
• Publication Number:
  US 20170033892A1
• Time in Patent Office: 300 Days
• Field of Search: 341 50, 341 51, 341 60, 341 94, 714746, 714751, 714752, 714782, 714786, 375254, 375340, 375341
• 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: H03M 13/458 by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0064 Concatenated codes
• CPC Class Codes: H04L 1/0065 Serial concatenated codes
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes

Abstract

Encoding of a plurality of encoded symbols is provided wherein an encoded symbol is generated from a combination of a first symbol generated from a first set of intermediate symbols and a second symbol generated from a second set of intermediate symbols, each set having at least one different coding parameter, wherein the intermediate symbols are generated based on the set of source symbols. A method of decoding data is also provided, wherein a set of intermediate symbols is decoded from a set of received encoded symbols, the intermediate symbols organized into a first and second sets of symbols for decoding, wherein intermediate symbols in the second set are permanently inactivated for the purpose of scheduling the decoding process to recover the intermediate symbols from the encoded symbols, wherein at least some of the source symbols are recovered from the decoded set of intermediate symbols.

Claims

1. A method of electronically transmitting data via one or more transmitters capable of outputting an electronic signal, wherein the data to be transmitted is represented by an ordered set of source symbols and the data is transmitted as a sequence of encoded symbols representing at least a portion of the electronic signal, the method comprising:

obtaining, in an electronically readable form, the ordered set of source symbols;

generating a set of intermediate symbols from the ordered set of source symbols, wherein the ordered set of source symbols can be regenerated from the set of intermediate symbols;

designating a plurality of sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols, the sets comprising at least a first set and a second set each of which has as members at least one intermediate symbol, and wherein the first set is designated as symbols for a first form of decoding and the second set is designated as symbols to be inactivated for the first form of decoding and are designated as symbols for a second form of decoding; and

generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from both the first set and the second set.

2. The method of claim 1, wherein the first form of decoding requires fewer computations per intermediate symbol to decode than the second form of decoding.

3. The method of claim 2, wherein the first form of decoding is belief propagation decoding and the second form of decoding is Gaussian elimination.

4. The method of claim 1, further comprising:

generating symbols of the first set using a first degree distribution;

generating symbols of the second set using a second degree distribution different from the first degree distribution;

generating a first symbol using a chain reaction encoding process applied to the symbols of the first set;

generating a second symbol as an XOR of a fixed number of symbols chosen randomly from the symbols of the second set; and

generating each encoded symbol is a combination of the first symbol and the second symbol.

5. The method of claim 1, wherein the intermediate symbols comprise the ordered set of source symbols and a set of redundant source symbols generated from the ordered set of source symbols.

6. The method of claim 5, wherein at least some of the redundant symbols are generated using a GF(2) operations and other redundant symbols are generated using GF(256) operations.

7. The method of claim 1, wherein the intermediate symbols are generated, during encoding, from the ordered set of source symbols using a decoding process, wherein the decoding process is based on a linear set of relations between the intermediate symbols and source symbols of the ordered set of source symbols.

8. The method of claim 1, wherein a number of distinct encoded symbols that can be generated from a given ordered set of source symbols is independent of a number of source symbols in that given ordered set.

9. A method of receiving data from a source, wherein the data is received at a destination as a set of received encoded symbols derived from set of source symbols representing the data sent from the source to the destination, the method comprising:

obtaining the set of received encoded symbols;

decoding a set of intermediate symbols from the set of received encoded symbols;

allocating each intermediate symbol of the set of intermediate symbols into a set of intermediate symbols of a plurality of sets of intermediate symbols each set having as members at least one intermediate symbol, wherein a first set of intermediate symbols is not designated as a set of permanently inactive symbols and a second set of intermediate symbols is designated as a set of permanently inactive symbols;

in a first decoding stage, determining a decoding schedule that would decode a first subset of the set of source symbols from the first set of intermediate symbols if the set of permanently inactive symbols were decoded already;

in a second decoding stage, decoding the set of permanently inactive symbols into a second subset of the set of source symbols, independent of values of symbols in the first subset;

in a third decoding stage, decoding the first set of intermediate symbols into the first subset using the decoding schedule and the second subset; and

recovering the data from the first set and the set of permanently inactive symbols.

10. The method of claim 9, wherein the allocating is done according to a mapping of permanently inactive symbols and the mapping is known to the source and available for the allocating.

11. The method of claim 10, wherein some intermediate symbols are allocated to a third set of intermediate symbols, a set of dynamically inactive symbols, comprising intermediate symbols mapped at the source to the first set of intermediate symbols but operated upon as being in the set of permanently inactive symbols and used in the second decoding stage along with the set of permanently inactive symbols for decoding at least the second subset.

12. The method of claim 9, wherein the first decoding stage uses belief propagation decoding, the second decoding stage uses Gaussian elimination, and the third decoding stage uses back substitution or a back sweep followed by a forward sweep.

13. The method of claim 9, wherein each received encoded symbol of the set of received encoded symbols is operated on as being an XOR of a first symbol generated from one or more source symbol of the first subset and a second symbol generated from one or more source symbol of the second subset.

14. The method of claim 13, wherein each received encoded symbol is operated on as the second symbol being an XOR of a fixed number of symbols chosen randomly from the second subset.

15. The method of claim 13, wherein each received encoded symbol is operated on as the second symbol being an XOR of a first number of source symbols chosen randomly from the second subset, wherein the first number of source symbols depends on a second number of source symbols chosen from the first subset to generate the first symbol.

16. The method of claim 9, wherein the three decoding stages operate as if the intermediate symbols comprise the set of source symbols and a set of redundant symbols generated from the set of source symbols.

17. The method of claim 16, wherein the three decoding stages operate as if at least some of the redundant symbols were generated using GF(2) operations and other redundant symbols were generated using GF(256) operations.

18. The method of claim 9, wherein the three decoding stages operate as if the intermediate symbols comprise the set of source symbols.

19. The method of claim 9, wherein the three decoding stages operate as if a number of different possible encoded symbols that can be received were independent of the number of source symbols in the set of source symbols.

20. The method of claim 9, wherein the three decoding stages operate such that, when the set of source symbols comprises K source symbols, a probability of success of recovery of all of the K source symbols from a set of N=K+A encoded symbols, for some K, N and A, has a lower bound of 1−

(0.01)^(A+1) for A=0, 1 or 2, with the lower bound being independent of the number of source symbols in the set of source symbols.

21. An apparatus for electronically transmitting data to be transmitted via one or more transmitters capable of outputting a signal, the apparatus comprising

memory;

and

a processor;

the memory and processor configured to perform operations comprising;

(a) obtaining an ordered set of source symbols;

(b) generating a set of intermediate symbols from the ordered set of source symbols, wherein the ordered set of source symbols can be regenerated from the set of intermediate symbols;

(c) designating a plurality of sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols, the sets comprising at least a first set and a second set each of which has as members at least one intermediate symbol, and wherein the first set is designated as symbols for a first form of decoding and the second set is designated as symbols to be inactivated for the first form of decoding and are designated as symbols for a second form of decoding; and

(d) generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from both the first set and the second set.

22. The apparatus of claim 21, wherein the memory and processor are configured to perform operations such that the first form of decoding requires fewer computations per intermediate symbol to decode than the second form of decoding.

23. The apparatus of claim 22, wherein the memory and processor are configured to perform operations such that the first form of decoding is belief propagation decoding and the second form of decoding is Gaussian elimination.

24. The apparatus of claim 21, wherein the memory and processor are configured to perform operations further comprising:

generating symbols of the first set using a first degree distribution;

generating symbols of the second set using a second degree distribution different from the first degree distribution;

generating a first symbol using a chain reaction encoding process applied to the symbols of the first set;

generating a second symbol as an XOR of a fixed number of symbols chosen randomly from the symbols of the second set; and

generating each encoded symbol is a combination of the first symbol and the second symbol.

25. The apparatus of claim 21, wherein the memory and processor are configured to perform operations such that the intermediate symbols comprise the ordered set of source symbols and a set of redundant source symbols generated from the ordered set of source symbols.

26. The apparatus of claim 25, wherein the memory and processor are configured to perform operations comprising generating at least some of the redundant symbols using a GF(2) operations and other redundant symbols using GF(256) operations.

27. The apparatus of claim 21, wherein the memory and processor are configured to perform operations comprising generating the intermediate symbols, during encoding, from the ordered set of source symbols using a decoding process, wherein the decoding process is based on a linear set of relations between the intermediate symbols and source symbols of the ordered set of source symbols.

28. The apparatus of claim 21, wherein the memory and processor are configured to perform operations such that a number of distinct encoded symbols that can be generated from a given ordered set of source symbols is independent of a number of source symbols in that given ordered set.

29. An apparatus for decoding data from a set of received encoded symbols, the set of received encoded symbols derived from an ordered set of source symbols, the apparatus comprising:

memory; and

a processor;

the memory and processor configured to perform operations comprising;

(a) obtaining the set of received encoded symbols;

(b) decoding a set of intermediate symbols from the set of received encoded symbols;

(c) allocating each intermediate symbol of the set of intermediate symbols into a set of intermediate symbols of a plurality of sets of intermediate symbols each set having as members at least one intermediate symbol, wherein a first set of intermediate symbols is not designated as a set of permanently inactive symbols and a second set of intermediate symbols is designated as a set of permanently inactive symbols;

(d) in a first decoding stage, determining a decoding schedule that would decode a first subset of the set of source symbols from the first set of intermediate symbols if the set of permanently inactive symbols were decoded already;

(e) in a second decoding stage, decoding the set of permanently inactive symbols into a second subset of the set of source symbols, independent of values of symbols in the first subset;

(f) in a third decoding stage, decoding the first set of intermediate symbols into the first subset using the decoding schedule and the second subset; and

(g) recovering the data from the first set and the set of permanently inactive symbols.

30. The apparatus of claim 29, wherein the memory and processor are configured to perform operations such that the allocating is done according to a mapping of permanently inactive symbols and the mapping is known to the source and available for the allocating.

31. The apparatus of claim 30, wherein the memory and processor are configured to perform operations comprising allocating some intermediate symbols to a third set of intermediate symbols, a set of dynamically inactive symbols, comprising intermediate symbols mapped at the source to the first set of intermediate symbols but operated upon as being in the set of permanently inactive symbols and used in the second decoding stage along with the set of permanently inactive symbols for decoding at least the second subset.

32. The apparatus of claim 29, wherein the memory and processor are configured to perform operations such that the first decoding stage uses belief propagation decoding, the second decoding stage uses Gaussian elimination, and the third decoding stage uses back substitution or a back sweep followed by a forward sweep.

33. The apparatus of claim 29, wherein the memory and processor are configured to perform operations comprising operating on each received encoded symbol of the set of received encoded symbols on as being an XOR of a first symbol generated from one or more source symbol of the first subset and a second symbol generated from one or more source symbol of the second subset.

34. The apparatus of claim 33, wherein the memory and processor are configured to perform operations comprising operating on each received encoded symbol as the second symbol being an XOR of a first number of source symbols chosen randomly from the second subset, wherein the first number of source symbols depends on a second number of source symbols chosen from the first subset to generate the first symbol.

35. The apparatus of claim 29, wherein the memory and processor are configured to perform operations such that a number of different possible encoded symbols that can be received were independent of the number of source symbols in the set of source symbols.

36. The apparatus of claim 29, wherein the memory and processor are configured to perform operations such that, when the set of source symbols comprises K source symbols, a probability of success of recovery of all of the K source symbols from a set of N=K+A encoded symbols, for some K, N and A, has a lower bound of 1−

(0.01)^(A+1) for A=0, 1 or 2, with the lower bound being independent of the number of source symbols in the set of source symbols.

37. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor of a computing device to perform operations for encoding data to be transmitted via one or more transmitters capable of outputting a signal, the operations comprising:

obtaining an ordered set of source symbols;

generating a set of intermediate symbols from the ordered set of source symbols, wherein the ordered set of source symbols can be regenerated from the set of intermediate symbols;

designating a plurality of sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols, the sets comprising at least a first set and a second set each of which has as members at least one intermediate symbol, and wherein the first set is designated as symbols for a first form of decoding and the second set is designated as symbols to be inactivated for the first form of decoding and are designated as symbols for a second form of decoding; and

generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from both the first set and the second set.

38. The non-transitory processor-readable storage medium of claim 37, wherein the processor-executable instructions are configured to cause the processor to perform operations such that the first form of decoding requires fewer computations per intermediate symbol to decode than the second form of decoding.

39. The non-transitory processor-readable storage medium of claim 38, wherein the processor-executable instructions are configured to cause the processor to perform operations such that the first form of decoding is belief propagation decoding and the second form of decoding is Gaussian elimination.

40. The non-transitory processor-readable storage medium of claim 37, wherein the processor-executable instructions are configured to cause the processor to perform operations comprising:

generating symbols of the first set using a first degree distribution;

generating symbols of the second set using a second degree distribution different from the first degree distribution;

generating a first symbol using a chain reaction encoding process applied to the symbols of the first set;

generating a second symbol as an XOR of a fixed number of symbols chosen randomly from the symbols of the second set; and

generating each encoded symbol is a combination of the first symbol and the second symbol.

41. The non-transitory processor-readable storage medium of claim 37, wherein the processor-executable instructions are configured to cause the processor to perform operations such that a number of distinct encoded symbols that can be generated from a given ordered set of source symbols is independent of a number of source symbols in that given ordered set.

42. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor of a computing device to perform operations for decoding a set of received encoded symbols, the set of received encoded symbols derived from an ordered set of source symbols, the operations comprising:

obtaining the set of received encoded symbols;

decoding a set of intermediate symbols from the set of received encoded symbols;

allocating each intermediate symbol of the set of intermediate symbols into a set of intermediate symbols of a plurality of sets of intermediate symbols each set having as members at least one intermediate symbol, wherein a first set of intermediate symbols is not designated as a set of permanently inactive symbols and a second set of intermediate symbols is designated as a set of permanently inactive symbols;

in a first decoding stage, determining a decoding schedule that would decode a first subset of the set of source symbols from the first set of intermediate symbols if the set of permanently inactive symbols were decoded already;

in a second decoding stage, decoding the set of permanently inactive symbols into a second subset of the set of source symbols, independent of values of symbols in the first subset;

in a third decoding stage, decoding the first set of intermediate symbols into the first subset using the decoding schedule and the second subset; and

recovering the ordered set of source symbols from the first set and the set of permanently inactive symbols.

43. The non-transitory processor-readable storage medium of claim 42, wherein the processor-executable instructions are configured to cause the processor to perform operations such that the allocating is done according to a mapping of permanently inactive symbols and the mapping is known to the source and available for the allocating.

44. The non-transitory processor-readable storage medium of claim 43, wherein the processor-executable instructions are configured to cause the processor to perform operations comprising allocating some intermediate symbols to a third set of intermediate symbols, a set of dynamically inactive symbols, comprising intermediate symbols mapped at the source to the first set of intermediate symbols but operated upon as being in the set of permanently inactive symbols and used in the second decoding stage along with the set of permanently inactive symbols for decoding at least the second subset.

45. The non-transitory processor-readable storage medium of claim 42, wherein the processor-executable instructions are configured to cause the processor to perform operations such that the first decoding stage uses belief propagation decoding, the second decoding stage uses Gaussian elimination, and the third decoding stage uses back substitution or a back sweep followed by a forward sweep.

46. The non-transitory processor-readable storage medium of claim 42, wherein the processor-executable instructions are configured to cause the processor to perform operations such that each received encoded symbol of the set of received encoded symbols is operated on as being an XOR of a first symbol generated from one or more source symbol of the first subset and a second symbol generated from one or more source symbol of the second subset.

47. The non-transitory processor-readable storage medium of claim 46, wherein the processor-executable instructions are configured to cause the processor to perform operations such that each received encoded symbol is operated on as the second symbol being an XOR of a first number of source symbols chosen randomly from the second subset, wherein the first number of source symbols depends on a second number of source symbols chosen from the first subset to generate the first symbol.

48. The non-transitory processor-readable storage medium of claim 42, wherein the processor-executable instructions are configured to cause the processor to perform operations as if a number of different possible encoded symbols that can be received were independent of the number of source symbols in the set of source symbols.

49. The non-transitory processor-readable storage medium of claim 42, wherein the processor-executable instructions are configured to cause the processor to perform operations such that when the set of source symbols comprises K source symbols, a probability of success of recovery of all of the K source symbols from a set of N=K+A encoded symbols, for some K, N and A, has a lower bound of 1−

(0.01)^(A+1) for A=0, 1 or 2, with the lower bound being independent of the number of source symbols in the set of source symbols.