ERROR-CORRECTING MULTI-STAGE CODE GENERATOR AND DECODER FOR COMMUNICATION SYSTEMS HAVING SINGLE TRANSMITTERS OR MULTIPLE TRANSMITTERS

• US 20090158114A1
• Filed: 10/15/2008
• Published: 06/18/2009
• Est. Priority Date: 10/06/2003
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Shokrollahi, M. Amin
• Granted Patent: US 8,887,020 B2
• Time in Patent Office: Days
• 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 and redundant symbols, wherein at least one output symbol is generated from more than one symbol in the combined set and less than all of the symbols in the combined set, wherein the number of possible valid output symbols for a given set of symbols in the combined set is effectively unbounded relative to the number of input symbols in the input file for any expected size of input file, wherein the input symbols are from an ordered set of input symbols, 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;

upon receiving at least a subset of the output symbols, determining at least estimates of output symbol probability distributions, wherein an output symbol probability distribution represents probabilities, given a received output symbol, that a particular output symbol was transmitted;

determining, from the estimates of output symbol probability distributions, input symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols;

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; and

upon receiving at least a subset of the output symbols, regenerating at least a subset of the symbols in the combined set from the 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, wherein the steps of regenerating use the input symbol probability distributions.