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

• US 9,876,607 B2
• Filed: 12/02/2015
• Issued: 01/23/2018
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Luby, Michael G., Shokrollahi, Mohammad Amin, Minder, Lorenz Christoph
• Primary Examiner(s): Nguyen, Linh
• Application Number:
  US14/956,778
• Publication Number:
  US 20160087755A1
• Time in Patent Office: 783 Days
• Field of Search: 341 50, 341 51, 341 65, 341 67, 341106, 341107, 714746, 714751, 714752, 714777, 714786, 714792, 714794, 714795
• 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:

determining sets of intermediate symbols from a group of intermediate symbols, the group of intermediate symbols generated from the ordered set of source symbols, wherein the source symbols can be derived from the group of intermediate symbols, such that each intermediate symbol of the group of intermediate symbols is determined as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; 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 a plurality of the sets of intermediate symbols.

2. The method of claim 1, wherein the first set of intermediate symbols are determined as symbols for belief propagation decoding and the second set of intermediate symbols are determined as symbols to be inactivated for belief propagation decoding.

3. The method of claim 1, wherein each encoded symbol is generated from a combination of a first symbol generated from one or more of the first set of intermediate symbols and a second symbol generated from one or more of the second set of intermediate symbols.

4. The method of claim 3, wherein the distinct encoding parameters comprise at least distinct degree distributions, such that each encoded symbol is generated from a combination of a first symbol generated from one or more of the first set of intermediate symbols having a first degree distribution and a second symbol generated from one or more of the second set of intermediate symbols having a second degree distribution different from the first degree distribution.

5. The method of claim 3, wherein the first symbol is generated using a chain reaction encoding process applied to the first set of intermediate symbols.

6. The method of claim 3, wherein the second symbol is an XOR of a fixed number of symbols chosen randomly from the second set of intermediate symbols.

7. The method of claim 3, wherein the second symbol is an XOR of a first number of symbols chosen randomly from the second set of intermediate symbols, and wherein the first number depends on a second number equal to a number of the symbols chosen from the first set to generate the first symbol.

8. The method of claim 3, wherein the combination is the XOR of the first symbol and the second symbol.

9. 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.

10. The method of claim 9, 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.

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

12. The method of claim 11, wherein at least some of the linear relations are relations over GF[2] and other linear relations are relations over GF[256].

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

14. The method of claim 1, wherein an average number of symbol operations performed to generate an encoded symbol is bounded by a constant independent of the number of source symbols in that ordered set.

15. The method of claim 1, wherein the first set of symbols is more than an order of magnitude larger than the second set of symbols.

16. A method for decoding data a set of received encoded symbols, the set of received encoded symbols derived from an ordered set of source symbols, the method comprising:

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

associating each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is determined as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols; and

recovering at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process.

17. The method of claim 16, wherein the decoding process comprises at least a first decoding phase, wherein a set of reduced encoded symbols are generated that depend on a second set of permanently inactive symbols and a third set of dynamically inactive symbols that is a subset of the first set of symbols, and a second decoding phase, wherein the set of reduced encoded symbols is used to decode the second set of permanently inactive symbols and the third set of dynamically inactive symbols, and a third decoding phase, wherein the decoded second set of permanently inactive symbols and the third set of dynamically inactive symbols and the set of received encoded symbols is used to decode at least some of the remaining intermediate symbols that are in the first set of symbols.

18. The method of claim 17, wherein the first decoding phase uses belief propagation decoding combined with inactivation decoding, and/or the second decoding phase uses Gaussian elimination.

19. The method of claim 17, wherein the third decoding phase uses back substitution or a back sweep followed by a forward sweep.

20. The method of claim 17, wherein the decoding process operates on the third set of dynamically inactive symbols considering that the number of symbols in third set of dynamically inactive symbols is less than 10% of the number of source symbols and/or less than 10% of the number of symbols in the second set of permanently inactive symbols.

21. The method of claim 16, wherein the received encoded symbols are operated on as LDPC code generated symbols or Reed-Solomon code generated symbols.

22. The method of claim 16, wherein each received encoded symbol of the set of received encoded symbols is operated on as being a combination of a first symbol generated from one or more of the first set of symbols and a second symbol generated from one or more of the second set of symbols.

23. The method of claim 22, wherein each received encoded symbol is operated on as the combination being an XOR of the first symbol and the second symbol.

24. The method of claim 22, wherein each received encoded symbol is operated on as the second symbol being an XOR of a fixed number of symbols that was chosen randomly from the second set.

25. The method of claim 22, wherein each received encoded symbol is operated on as the second symbol being an XOR of a first number of symbols that was chosen randomly from the second set, wherein the first number of symbols depends on the second number of symbols that was chosen from the first set to generate the first symbol.

26. The method of claim 22, wherein the decoding process operates as if the first symbol was chosen based on a chain reaction code from the first set of symbols.

27. The method of claim 16, wherein the decoding process operates as if the size of the second set of permanently inactive symbols is proportional to the square root of the number of source symbols.

28. The method of claim 16, wherein the decoding process operates as if the intermediate symbols comprise the ordered set of source symbols and a set of redundant symbols generated from the ordered set of source symbols.

29. The method of claim 28, wherein the decoding process operates 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.

30. The method of claim 16, wherein the decoding process operates as if the intermediate symbols comprise the ordered set of source symbols.

31. The method of claim 16, wherein the decoding process operates as if the intermediate symbols are symbols that were generated from the source symbols using a decoding process based on a linear set of relations between the intermediate symbols and the source symbols.

32. The method of claim 31, wherein the decoding process operates as if at least some of the linear relations are relations over GF[2] and other linear relations are relations over GF[256].

33. The method of claim 16, wherein the decoding process operates as if the number of different possible encoded symbols that can be received is independent of the number of source symbols in the ordered set.

34. The method of claim 16, wherein an average number of symbol operations performed to decode the set of source symbols from the set of received encoded symbols is bounded by a constant times the number of source symbols, wherein the constant is independent of the number of source symbols.

35. The method of claim 16, wherein the decoding process operates as if the number of symbols in the first set of symbols is more than an order of magnitude larger than the number of symbols in the second set of permanently inactive symbols.

36. The method of claim 16, wherein the decoding process operates such that recovery of all of the set of K source symbols from a set of N=K+A encoded symbols, for some K, N and A, has a probability of success of at least 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.

37. An apparatus for encoding 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;

determine sets of intermediate symbols from a group of intermediate symbols, the group of intermediate symbols generated from the ordered set of source symbols, wherein the source symbols can be derived from the group of intermediate symbols, such that each intermediate symbol of the group of intermediate symbols is determined as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; and

generate 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 a plurality of the sets of intermediate symbols.

38. The apparatus of claim 37, wherein the memory and processor are further configured such that the first set of intermediate symbols are determined as symbols for belief propagation decoding and the second set of intermediate symbols are determined as symbols to be inactivated for belief propagation decoding.

39. The apparatus of claim 37, wherein the memory and processor are further configured such that each encoded symbol is generated from a combination of a first symbol generated from one or more of the first set of intermediate symbols and a second symbol generated from one or more of the second set of intermediate symbols.

40. The apparatus of claim 39, wherein the memory and processor are further configured such that the distinct encoding parameters comprise at least distinct degree distributions, such that each encoded symbol is generated from a combination of a first symbol generated from one or more of the first set of intermediate symbols having a first degree distribution and a second symbol generated from one or more of the second set of intermediate symbols having a second degree distribution different from the first degree distribution.

41. The apparatus of claim 39, wherein the memory and processor are further configured such that the first symbol is generated using a chain reaction encoding process applied to the first set of intermediate symbols.

42. The apparatus of claim 39, wherein the memory and processor are further configured such that the second symbol is an XOR of a fixed number of symbols chosen randomly from the second set of intermediate symbols.

43. The apparatus of claim 39, wherein the memory and processor are further configured such that the second symbol is an XOR of a first number of symbols chosen randomly from the second set of intermediate symbols, and the first number depends on a second number equal to a number of the symbols chosen from the first set to generate the first symbol.

44. The apparatus of claim 39, wherein the memory and processor are further configured such that the combination is the XOR of the first symbol and the second symbol.

45. The apparatus of claim 39, wherein the memory and processor are further configured 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.

46. The apparatus of claim 45, wherein the memory and processor are further configured such that at least some of the redundant symbols are generated using a GF[2] operations and other redundant symbols are generated using GF[256] operations.

47. The apparatus of claim 37, wherein the memory and processor are further configured such that the intermediate symbols are generated, during encoding, from the source symbols using a decoding process, and the decoding process is based on a linear set of relations between the intermediate symbols and the source symbols.

48. The apparatus of claim 47, wherein the memory and processor are further configured such that at least some of the linear relations are relations over GF[2] and other linear relations are relations over GF[256].

49. The apparatus of claim 37, wherein the memory and processor are further configured such that the number of distinct encoded symbols that can be generated from a given ordered set of source symbols is independent of the number of source symbols in that ordered set.

50. The apparatus of claim 37, wherein the memory and processor are further configured such that an average number of symbol operations performed to generate an encoded symbol is bounded by a constant independent of the number of source symbols in that ordered set.

51. The apparatus of claim 37, wherein the memory and processor are further configured such that the first set of symbols is more than an order of magnitude larger than the second set of symbols.

52. An apparatus for decoding data 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;

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

associate each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is determined as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols; and

recover at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process.

53. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process comprises at least a first decoding phase, and a set of reduced encoded symbols are generated that depend on a second set of permanently inactive symbols and a third set of dynamically inactive symbols that is a subset of the first set of symbols, and a second decoding phase, and the set of reduced encoded symbols is used to decode the second set of permanently inactive symbols and the third set of dynamically inactive symbols, and a third decoding phase, and the decoded second set of permanently inactive symbols and the third set of dynamically inactive symbols and the set of received encoded symbols is used to decode at least some of the remaining intermediate symbols that are in the first set of symbols.

54. The apparatus of claim 53, wherein the memory and processor are further configured such that the first decoding phase uses belief propagation decoding combined with inactivation decoding, and/or the second decoding phase uses Gaussian elimination.

55. The apparatus of claim 53, wherein the memory and processor are further configured such that the third decoding phase uses back substitution or a back sweep followed by a forward sweep.

56. The apparatus of claim 53, wherein the memory and processor are further configured such that the decoding process operates on the third set of dynamically inactive symbols considering that the number of symbols in third set of dynamically inactive symbols is less than 10% of the number of source symbols and/or less than 10% of the number of symbols in the second set of permanently inactive symbols.

57. The apparatus of claim 52, wherein the memory and processor are further configured such that the received encoded symbols are operated on as LDPC code generated symbols or Reed-Solomon code generated symbols.

58. The apparatus of claim 52, wherein the memory and processor are further configured such that each received encoded symbol of the set of received encoded symbols is operated on as being a combination of a first symbol generated from one or more of the first set of symbols and a second symbol generated from one or more of the second set of symbols.

59. The apparatus of claim 58, wherein the memory and processor are further configured such that each received encoded symbol is operated on as the combination being an XOR of the first symbol and the second symbol.

60. The apparatus of claim 58, wherein the memory and processor are further configured such that each received encoded symbol is operated on as the second symbol being an XOR of a fixed number of symbols that was chosen randomly from the second set.

61. The apparatus of claim 58, wherein the memory and processor are further configured such that each received encoded symbol is operated on as the second symbol being an XOR of a first number of symbols that was chosen randomly from the second set, and the first number of symbols depends on the second number of symbols that was chosen from the first set to generate the first symbol.

62. The apparatus of claim 58, wherein the memory and processor are further configured such that the decoding process operates as if the first symbol was chosen based on a chain reaction code from the first set of symbols.

63. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates as if the size of the second set of permanently inactive symbols is proportional to the square root of the number of source symbols.

64. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates as if the intermediate symbols comprise the ordered set of source symbols and a set of redundant symbols generated from the ordered set of source symbols.

65. The apparatus of claim 64, wherein the memory and processor are further configured such that the decoding process operates 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.

66. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates as if the intermediate symbols comprise the ordered set of source symbols.

67. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates as if the intermediate symbols are symbols that were generated from the source symbols using a decoding process based on a linear set of relations between the intermediate symbols and the source symbols.

68. The apparatus of claim 67, wherein the memory and processor are further configured such that the decoding process operates as if at least some of the linear relations are relations over GF[2] and other linear relations are relations over GF[256].

69. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates as if the number of different possible encoded symbols that can be received is independent of the number of source symbols in the ordered set.

70. The apparatus of claim 52, wherein the memory and processor are further configured such that an average number of symbol operations performed to decode the set of source symbols from the set of received encoded symbols is bounded by a constant times the number of source symbols, and the constant is independent of the number of source symbols.

71. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates as if the number of symbols in the first set of symbols is more than an order of magnitude larger than the number of symbols in the second set of permanently inactive symbols.

72. The apparatus of claim 52, wherein the memory and processor are further configured such that the decoding process operates such that recovery of all of the set of K source symbols from a set of N=K+A encoded symbols, for some K, N and A, has a probability of success of at least 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.

73. 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:

determining sets of the intermediate symbols from a group of intermediate symbols, the group of intermediate symbols generated from the ordered set of source symbols, wherein the source symbols can be derived from the group of intermediate symbols, such that each intermediate symbol of the group of intermediate symbols is determined as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; 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 a plurality of the sets of intermediate symbols.

74. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the first set of intermediate symbols are determined as symbols for belief propagation decoding and the second set of intermediate symbols are determined as symbols to be inactivated for belief propagation decoding.

75. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that each encoded symbol is generated from a combination of a first symbol generated from one or more of the first set of intermediate symbols and a second symbol generated from one or more of the second set of intermediate symbols.

76. The non-transitory processor-readable storage medium of claim 75, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the distinct encoding parameters comprise at least distinct degree distributions, such that each encoded symbol is generated from a combination of a first symbol generated from one or more of the first set of intermediate symbols having a first degree distribution and a second symbol generated from one or more of the second set of intermediate symbols having a second degree distribution different from the first degree distribution.

77. The non-transitory processor-readable storage medium of claim 75, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the first symbol is generated using a chain reaction encoding process applied to the first set of intermediate symbols.

78. The non-transitory processor-readable storage medium of claim 75, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the second symbol is an XOR of a fixed number of symbols chosen randomly from the second set of intermediate symbols.

79. The non-transitory processor-readable storage medium of claim 75, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the second symbol is an XOR of a first number of symbols chosen randomly from the second set of intermediate symbols, and the first number depends on a second number equal to a number of the symbols chosen from the first set to generate the first symbol.

80. The non-transitory processor-readable storage medium of claim 75, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the combination is the XOR of the first symbol and the second symbol.

81. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor 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.

82. The non-transitory processor-readable storage medium of claim 81, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that at least some of the redundant symbols are generated using a GF[2] operations and other redundant symbols are generated using GF[256] operations.

83. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the intermediate symbols are generated, during encoding, from the source symbols using a decoding process, and the decoding process is based on a linear set of relations between the intermediate symbols and the source symbols.

84. The non-transitory processor-readable storage medium of claim 83, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that at least some of the linear relations are relations over GF[2] and other linear relations are relations over GF[256].

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

86. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that an average number of symbol operations performed to generate an encoded symbol is bounded by a constant independent of the number of source symbols in that ordered set.

87. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the first set of symbols is more than an order of magnitude larger than the second set of symbols.

88. The non-transitory processor-readable storage medium of claim 73, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the group of intermediate symbols comprise the ordered set of source symbols.

89. 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 decoding data a set of received encoded symbols, the set of received encoded symbols derived from an ordered set of source symbols, the operations comprising:

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

associating each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is determined as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols; and

recovering at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process.

90. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process comprises at least a first decoding phase, and a set of reduced encoded symbols are generated that depend on a second set of permanently inactive symbols and a third set of dynamically inactive symbols that is a subset of the first set of symbols, and a second decoding phase, and the set of reduced encoded symbols is used to decode the second set of permanently inactive symbols and the third set of dynamically inactive symbols, and a third decoding phase, and the decoded second set of permanently inactive symbols and the third set of dynamically inactive symbols and the set of received encoded symbols is used to decode at least some of the remaining intermediate symbols that are in the first set of symbols.

91. The non-transitory processor-readable storage medium of claim 90, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the first decoding phase uses belief propagation decoding combined with inactivation decoding, and/or the second decoding phase uses Gaussian elimination.

92. The non-transitory processor-readable storage medium of claim 90, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the third decoding phase uses back substitution or a back sweep followed by a forward sweep.

93. The non-transitory processor-readable storage medium of claim 90, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates on the third set of dynamically inactive symbols considering that the number of symbols in third set of dynamically inactive symbols is less than 10% of the number of source symbols and/or less than 10% of the number of symbols in the second set of permanently inactive symbols.

94. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the received encoded symbols are operated on as LDPC code generated symbols or Reed-Solomon code generated symbols.

95. The non-transitory processor-readable storage medium of claim 89, wherein the stored 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 a combination of a first symbol generated from one or more of the first set of symbols and a second symbol generated from one or more of the second set of symbols.

96. The non-transitory processor-readable storage medium of claim 95, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that each received encoded symbol is operated on as the combination being an XOR of the first symbol and the second symbol.

97. The non-transitory processor-readable storage medium of claim 95, wherein the stored 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 fixed number of symbols that was chosen randomly from the second set.

98. The non-transitory processor-readable storage medium of claim 95, wherein the stored 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 symbols that was chosen randomly from the second set, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the first number of symbols depends on the second number of symbols that was chosen from the first set to generate the first symbol.

99. The non-transitory processor-readable storage medium of claim 95, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the first symbol was chosen based on a chain reaction code from the first set of symbols.

100. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the size of the second set of permanently inactive symbols is proportional to the square root of the number of source symbols.

101. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the intermediate symbols comprise the ordered set of source symbols and a set of redundant symbols generated from the ordered set of source symbols.

102. The non-transitory processor-readable storage medium of claim 95, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates 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.

103. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the intermediate symbols comprise the ordered set of source symbols.

104. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the intermediate symbols are symbols that were generated from the source symbols using a decoding process based on a linear set of relations between the intermediate symbols and the source symbols.

105. The non-transitory processor-readable storage medium of claim 104, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if at least some of the linear relations are relations over GF[2] and other linear relations are relations over GF[256].

106. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the number of different possible encoded symbols that can be received is independent of the number of source symbols in the ordered set.

107. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that an average number of symbol operations performed to decode the set of source symbols from the set of received encoded symbols is bounded by a constant times the number of source symbols, and the constant is independent of the number of source symbols.

108. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates as if the number of symbols in the first set of symbols is more than an order of magnitude larger than the number of symbols in the second set of permanently inactive symbols.

109. The non-transitory processor-readable storage medium of claim 89, wherein the stored processor-executable instructions are configured to cause the processor to perform operations such that the decoding process operates such that recovery of all of the set of K source symbols from a set of N=K+A encoded symbols, for some K, N and A, has a probability of success of at least 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.

110. 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 recovering a block of data from a received plurality of encoded symbols generated from the block, wherein a block includes a grouping of one or more sub-blocks, wherein each encoded symbol includes a plurality of sub-symbols generated from at least one sub-block using a common set of operations, the operations comprising:

determining a value, WS, representing a maximum size for a sub-block based on a memory constraint;

determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL;

determining which blocks of the integer number of blocks organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by a first parameter set by a sender representing available space within packets, a second parameter representing a symbol size used within each packet, the parameters being such that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file;

decoding blocks from received encoded symbols, wherein sub-blocks are decoded from sub-symbols and the sub-blocks form blocks, wherein the sub-symbol size of each sub-block is at most SS*AL and the size of each sub-block is at most WS; and

outputting the decoded blocks.