Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters

• US 8,887,020 B2
• Filed: 10/15/2008
• Issued: 11/11/2014
• Est. Priority Date: 10/06/2003
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Shokrollahi, M. Amin
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US12/252,331
• Publication Number:
  US 20090158114A1
• Time in Patent Office: 2,218 Days
• Field of Search: 714800-801, 714/762, 714/788, 714/752, 714/777, 714/786, 714/792, 714794-795, 375/262, 375/265, 375/341, 711/200
• US Class Current: 714/752
• 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

Abstract

A communications system includes an encoder that produces a plurality of redundant symbols. For a given key, an output symbol is generated from a combined set of symbols including the input symbols and the redundant symbols. The output symbols are generally independent of each other, and an effectively unbounded number of output symbols (subject to the resolution of the key used) can be generated, if needed. The output symbols are information additive such that a received output symbol is likely to provide additional information for decoding even when many symbols are already received. The output symbols are such that a collection of received output symbols can provide probabilistic information to support error correction. A decoder calculates check symbols from the output symbols received, wherein each check symbol is associated with one or more input symbols and redundant symbols For each received output symbol, the decoder updates a running total of estimated information content and, in one or more rounds, generates a probability distribution for each input symbol over all or some of the possible values of input symbols. This process may be repeated until, for all of the input symbols, one of the many possible values is much more probable than others, or the process may be repeated a predetermined number of rounds, or other criteria is met. The updating can take into account already decoded symbols, additional output symbols and the check symbols.

Claims

1. A method of receiving data transmitted from a source over a communications channel, wherein the data is transmitted as a plurality of output symbols and is generated from at least one symbol in a combined set of input symbols of an input file and redundant symbols, wherein the number of possible valid output symbols for a given set of symbols in the combined set is independent of the number of input symbols in the input file, and wherein the redundant symbols are generated from the input symbols, the method comprising:

receiving output symbols from the communications channel, wherein the communications channel might have introduced errors and/or erasures; and

regenerating at least a subset of the symbols in the combined set from the received output symbols, the subset of the symbols in the combined set including a plurality of regenerated input symbols and a plurality of regenerated redundant symbols, the regenerating using input symbol probability distributions determined from estimates of output symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols, and wherein the estimates of output symbol probability distributions are determined from probabilities, given a received output symbol, that a particular output symbol was transmitted.

2. The method of claim 1, further comprising:

determining, for received output symbols, an information quantity associated with the received output symbol;

accumulating a total information quantity associated with a plurality of received output symbols; and

triggering regenerating when the accumulated total information quantity meets predefined criteria relative to an information content quantity of the ordered set of input symbols.

3. The method of claim 2, wherein the predefined criteria includes a criterion that the accumulated total information is equal to the information content quantity of the ordered set of input symbols plus a small additional amount of information, wherein the small additional amount of information is a percentage of the information content quantity of the input symbols.

4. The method of claim 1, further comprising:

quantizing output symbol probability distributions according to a coarse quantization in a first decoding phase; and

quantizing output symbol probability distributions according to a fine quantization in a second decoding phase, wherein the coarse quantization has fewer quantization levels than the fine quantization.

5. The method of claim 1, wherein output symbol probability distributions comprise probability values each taking on one of two values, with one of the values representing a high probability and the other representing a low probability.

6. The method of claim 1, further comprising reading the output symbol probability distributions as representing probability per bit of an output symbol indicating a probability that the bit was a one or a zero at transmission.

7. The method of claim 1, further comprising reading the input symbol probability distribution stored as a data structure not including entries for possible transmitted bits or symbols when the corresponding estimated probability is zero.

8. The method of claim 1, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file.

9. The method of claim 1, wherein the redundant symbols include a first plurality of redundant symbols and a second plurality of redundant symbols, wherein the regenerating at least some of the unregenerated input symbols includes:

regenerating, from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols, at least one of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols; and

regenerating at least one unregenerated input symbol from redundant symbols of the second plurality of redundant symbols and the plurality of decoded input symbols if the step of regenerating from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols does not regenerate the input symbols to a desired degree of accuracy.

10. The method of claim 9, further comprising:

regenerating some of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols using an LDPC decoder; and

regenerating some input symbols from redundant symbols of the second plurality of redundant symbols using a Hamming decoder.

11. The method of claim 1, further comprising tracking, for error correction, probability estimates for more than one possibility for a given input symbol and then selecting the highest probability estimate.

12. The method of claim 1, wherein probability distributions comprise probability estimates that are based, at least in part, on strength or intensity of communications signals representing the received output symbols.

13. The method of claim 1, wherein probability distributions comprise probability estimates that are based on a function of distance between a received signal and possible values for the received signal.

14. The method of claim 1, further comprising calculating an estimate of an amount of information in a received output symbol as a binary entropy of a probability distribution of the received output symbol over possible transmitted output symbols.

15. Computer-readable program code embedded in non-transitory computer storage medium for processing data received over a communications channel, the data having been transmitted as a plurality of output symbols generated from a combined set of input symbols of an input file and redundant symbols, wherein the number of possible valid output symbols for a given set of symbols in the combined set is independent of the number of input symbols in the input file, and wherein the redundant symbols are generated from the input symbols, the program code comprising:

program code for receiving output symbols, possibly including errors and/or erasures; and

program code for regenerating at least a subset of the symbols in the combined set from the received output symbols taking into account the possibility of errors and/or erasures, the subset of the symbols in the combined set including a plurality of regenerated input symbols and a plurality of regenerated redundant symbols, the program code for regenerating also including program code for (i) determining input symbol probability distributions from estimates of output symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols, and (ii) determining the estimates of output symbol probability distributions from probabilities, given a received output symbol, that a particular output symbol was transmitted.

16. The computer-readable program code of claim 15, further comprising:

program code for determining, for received output symbols, an information quantity associated with the received output symbol;

program code for accumulating a total information quantity associated with a plurality of received output symbols; and

program code for triggering one or more of the steps of regenerating when the accumulated total information quantity meets predefined criteria relative to an information content quantity of the ordered set of input symbols.

17. The computer-readable program code of claim 16, wherein the predefined criteria includes a criterion that the accumulated total information is equal to the information content quantity of the ordered set of input symbols plus a small additional amount of information, wherein the small additional amount of information is a percentage of the information content quantity of the ordered set of input symbols.

18. The computer-readable program code of claim 15, further comprising:

program code for coarse quantization for quantizing output symbol probability distributions coarsely in a first decoding phase; and

program code for fine quantization for quantizing output symbol probability distributions in a second decoding phase, wherein the coarse quantization has fewer quantization levels than the fine quantization.

19. The computer-readable program code of claim 15, wherein output symbol probability distributions comprise probability values each taking on one of two values, with one of the values representing a high probability and the other representing a low probability.

20. The computer-readable program code of claim 15, further comprising program code to read the output symbol probability distributions as representing probability per bit of an output symbol indicating a probability that the bit was a one or a zero at transmission.

21. The computer-readable program code of claim 15, further comprising program code to read the input symbol probability distribution stored as a data structure not including entries for possible transmitted bits or symbols when the corresponding estimated probability is zero.

22. The computer-readable program code of claim 15, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file.

23. The computer-readable program code of claim 15, wherein the redundant symbols include a first plurality of redundant symbols and a second plurality of redundant symbols, wherein the program code for regenerating at least some of the unregenerated input symbols includes:

program code for regenerating, from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols, at least one of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols; and

program code for regenerating at least one unregenerated input symbol from redundant symbols of the second plurality of redundant symbols and the plurality of decoded input symbols if regenerating from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols does not regenerate the input symbols to a desired degree of accuracy.

24. The computer-readable program code of claim 23, further comprising:

program code for regenerating some of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols using an LDPC decoder; and

program code for regenerating some input symbols from redundant symbols of the second plurality of redundant symbols using a Hamming decoder.

25. The computer-readable program code of claim 15, further comprising program code for tracking, for error correction, probability estimates for more than one possibility for a given input symbol and then selecting the highest probability estimate.

26. The computer-readable program code of claim 15, wherein probability distributions comprise probability estimates that are based, at least in part, on strength or intensity of communications signals representing the received output symbols.

27. The computer-readable program code of claim 15, wherein probability distributions comprise probability estimates that are based on a function of distance between a received signal and possible values for the received signal.

28. The computer-readable program code of claim 15, further comprising calculation program code for calculating an estimate of an amount of information in a received output symbol as a binary entropy of a probability distribution of the received output symbol over possible transmitted output symbols.

29. A decoder for decoding input symbols from a plurality of received output symbols, the plurality of received output symbols having been transmitted over a communications channel that might have introduced errors and/or erasures, and the output symbols having been generated from at least one symbol in a combined set of input symbols of an input file and redundant symbols, wherein the number of possible valid output symbols for a given set of symbols in the combined set is independent of the number of input symbols in the input file, and wherein the redundant symbols are generated from the input symbols, the decoder comprising:

a receive module for receiving output symbols from the communications channel and for storing output symbols as data units; and

a decoding unit for regenerating at least a subset of the symbols in the combined set from the received output symbols, the subset of the symbols in the combined set including a plurality of regenerated input symbols and a plurality of regenerated redundant symbols, the regenerating using input symbol probability distributions determined from estimates of output symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols, and wherein the estimates of output symbol probability distributions are determined from probabilities, given a received output symbol, that a particular output symbol was transmitted.

30. The decoder of claim 29, further comprising:

a dynamic decoder module;

storage for regenerated input symbols and regenerated redundant symbols; and

a static decoder module.

31. The decoder of claim 29, further comprising storage for output symbol probability distributions.

32. The decoder of claim 29, further comprising storage for the input symbol probability distribution, stored as a data structure not including entries for possible transmitted bits or symbols when the corresponding estimated probability is zero.

33. The decoder of claim 29, further comprising a key generator, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file.

34. The decoder of claim 29, wherein the decoding unit further comprises storage for a total information quantity associated with a plurality of received output symbols and is configured to trigger a regenerating process when the total information quantity meets a predefined criteria relative to an information content quantity of the input symbols.

35. The decoder of claim 34, wherein the predefined criteria includes a criterion that the total information quantity is equal to the information content quantity of the input symbols plus a small additional amount of information, wherein the small additional amount of information is a percentage of the information content quantity of the input symbols.

36. The decoder of claim 29 wherein the decoding unit is configured to perform at least two levels of quantization.

37. The decoder of claim 29, wherein output symbol probability distributions comprise probability values each taking on one of two values, with one of the values representing a high probability and the other representing a low probability.

38. The decoder of claim 29, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file.

39. The decoder of claim 29, wherein the redundant symbols include a first plurality of redundant symbols and a second plurality of redundant symbols, and the decoding unit is configured to regenerate, from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols, at least one of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols, and regenerate at least one unregenerated input symbol from redundant symbols of the second plurality of redundant symbols and the plurality of decoded input symbols if regenerating from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols does not regenerate the input symbols to a desired degree of accuracy.

40. The decoder of claim 39, further comprising:

an LDPC decoder that regenerates some of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols; and

a Hamming decoder that regenerates some input symbols from redundant symbols of the second plurality of redundant symbols.

41. The decoder of claim 29, wherein probability distributions comprise probability estimates that are based, at least in part, on strength or intensity of communications signals representing the received output symbols.

42. The decoder of claim 29, wherein probability distributions comprise probability estimates that are based on a function of distance between a received signal and possible values for the received signal.