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

Patent metadata

Field	Value
Publication number	US-9419749-B2
Application number	US-85916110-A
Country	US
Kind code	B2
Filing date	Aug 18, 2010
Priority date	Aug 19, 2009
Publication date	Aug 16, 2016
Grant date	Aug 16, 2016

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.

First claim

What is claimed is:

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 source symbols can be regenerated from the set of intermediate symbols;
designating sets of the intermediate symbols such that each intermediate symbol is designated 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 designated as symbols for belief propagation decoding and the second set of intermediate symbols are designated 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 of receiving data from a source, wherein the data is received at a destination over a packet communication channel, and wherein the data representable by a set of encoded symbols derived from an ordered 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;
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 designated 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

Assignees

• Luby Michael G
• Shokrollahi Mohammad Amin
• Minder Lorenz Christoph
• Qualcomm Inc

Inventors

• Luby Michael G
• Shokrollahi Mohammad Amin
• Minder Lorenz Christoph

Classifications

• H04L1/0041 Primary

  Arrangements at the transmitter end · CPC title

• H04L1/0065

  Serial concatenated codes · CPC title

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

• H03M13/458

  by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result · CPC title

• H04L1/0066

  Parallel concatenated codes · CPC title