FORWARD ERROR-CORRECTING (FEC) CODING AND STREAMING

• US 20060279437A1
• Filed: 06/09/2006
• Published: 12/14/2006
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Watson, Mark, Shokrollahi, M. Amin
• Granted Patent: US 7,676,735 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• 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: H04L 1/0042 Encoding specially adapted to other signal generation operation, e.g. in order to reduce transmit distortions, jitter, or to improve signal shape H04L1/0067 takes precedence

Abstract

In a data decoder for decoding data from received symbols received over a channel from an encoder, wherein the received data can include erasures and include source symbols and repair symbols and wherein the decoder uses in decoding a generator matrix, any square submatrix of which is invertible, such that the decoder can perform decoding operations concurrently with the arrival of the source symbols and repair symbols, a method of decoding comprising representing in decoder memory a system of equations derived, at least in part, from the generator matrix, substituting received source symbols into the system of equations as the source symbols are received before receiving all source symbols, identifying, using decoder logic, repair equations to be used for solving the system of equations as repair symbols arrive, calculating, using decoder logic, vector values for equations as source symbols arrive, and converting the system of equations into an upper triangular form as repair symbols arrive at the decoder. Novel methods can be used for interleaving and specifying encoding structure for a large class of FEC codes, scheduling the sending of packets and the like.

Claims

1. In a data decoder for decoding data from received symbols received over a channel from an encoder, wherein the received data can include erasures and include source symbols and repair symbols and wherein the decoder uses a generator matrix in decoding, any square submatrix of which is invertible, such that the decoder can perform decoding operations concurrently with the arrival of the source symbols and repair symbols, a method of decoding comprising:

representing a system of equations in a decoder memory derived, at least in part, from the generator matrix;

substituting received source symbols into the system of equations as the source symbols are received before receiving all source symbols;

identifying, using decoder logic, repair equations to be used for solving the system of equations as repair symbols arrive;

calculating, using decoder logic, vector values for equations as source symbols arrive; and

converting the system of equations into an upper triangular form as repair symbols arrive at the decoder.

2. The method of claim 1, wherein the repair symbols of a code are received at the decoder before the source symbols and decoding operations are performed in-place.

3. The method of claim 1, wherein a permutation is applied at the encoder to source symbols before a two-dimensional Reed-Solomon code is applied.

4. The method of claim 3, wherein the permutation is random or pseudorandom.

5. The method of claim 3, wherein the permutation is such that no two adjacent symbols in the original ordering appear in the same row or column of the code.

6. The method of claim 5, wherein the permutation is derived from two permutations σ

₁, σ

₂ such that the symbol s[i,j] in position (i,j) in the source block is mapped through the two permutations such that the symbol s[i,j] at position (i,j) in the permuted source block satisfies s′

[i,j]=s[(σ

₁(j)+σ

₂(i)) % k,j] where k is the number of rows or columns of the code.

7. The method of claim 1, wherein the generator matrix is a generator matrix for a code that is augmented with more than one repair symbol generated per row of the generator matrix.

8. The method of claim 1, wherein the generator matrix is a generator matrix for a code of the group regular LDGM, irregular LDGM, regular LDGM staircase, irregular LDGM staircase, regular LDGM triangle, irregular LDGM triangle, regular Copper, irregular Copper, or a fountain code.

9. The method of claim 1, wherein the generator matrix is a generator matrix for an error-correcting code.

10. The method of claim 1, wherein the generator matrix is a generator matrix for an error-correcting code and an erasure code.

11. In a data encoder for encoding data to be sent over a channel, a method of generating encoded data comprising source symbols and repair symbols, the source symbols representing the data being encoded and the repair symbols usable to recover information about missing source symbols, and wherein the source symbols represent the data to be encoded as an ordered plurality of source symbols, the method comprising:

obtaining a generator matrix for a code wherein the generator matrix represents and encoding of the repair symbols from the source symbols;

reading in at least some of the source symbols;

including the at least some of the source symbols as encoded symbols in an encoded set in an order in the encoded set corresponding to an order of the source symbols in the ordered plurality of source symbols;

reordering the source symbols according to a set of one or more reordering rules to form a reordered set of source symbols;

applying the generator matrix to the reordered set of source symbols to form a set of repair symbols; and

outputting the encoded set as the encoded data and the set of repair symbols.

12. The method of claim 11, wherein the outputting occurs only after completion of the reading, reordering and applying steps.

13. The method of claim 11, wherein outputting of the encoded set occurs prior to completion of the applying step.

14. The method of claim 11, wherein the reordering rules comprise reordering according to a pseudorandom sequence known to the data encoder and determinable at a data decoder.

15. The method of claim 11, wherein the reordered set of source symbols is a physically reordered set of symbols.

16. The method of claim 11, wherein the reordered set of source symbols is a logically reordered set of symbols such that symbols stored in a memory prior to reordering need not be moved or copied to changed memory locations.

17. The method of claim 11, wherein the reordered set of source symbols is reordered in that applying the generator matrix is done such that the source symbols are taken in an order other than their original order.