LT STAIRCASE FEC CODE

• US 20140215292A1
• Filed: 01/28/2014
• Published: 07/31/2014
• Est. Priority Date: 01/29/2013
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Luby, Michael George
• Granted Patent: US 9,294,227 B2
• Time in Patent Office: Days
• US Class Current: 714/776
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• 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/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

Systems and methods for encoding data for transmission over a communications channel using an improved LT staircase FEC code are provided. Embodiments may include mapping source symbols to repair symbols, wherein a number of edges of the mapping associated with a source symbol is determined randomly according to a first distribution. The repair symbols may be ordered, and at least a first repair symbol may be encoded based on the source symbols that map to the first repair symbol and/or another repair symbol that immediately precedes the first repair symbol in the ordering of the repair symbols.

Claims

1. A method of encoding data for transmission over a communications channel, comprising:

mapping a first plurality of symbols to a second plurality of symbols according to a first distribution algorithm, wherein a number of edges of the mapping associated with a symbol in the first plurality of symbols is determined randomly according to the first distribution algorithm;

ordering the second plurality of symbols; and

encoding a first symbol in the second plurality of symbols based on at least one of;

one or more values of one or more symbols in the first plurality of symbols that map to the first symbol; and

an encoded value of a second symbol in the second plurality of symbols, wherein the second symbol immediately precedes the first symbol in the ordering of the second plurality of symbols.

2. The method of claim 1, wherein mapping the first plurality of symbols to the second plurality of symbols according to the first distribution algorithm comprises:

mapping each symbol in a first portion of the first plurality of symbols to a first number of symbols in the second plurality of symbols; and

mapping each symbol in a second portion of the first plurality of symbols to a second number of symbols in the second plurality of symbols.

3. The method of claim 1, wherein the encoded value of the second symbol is based on at least one of:

one or more values of one or more symbols in the first plurality of symbols that map to the second symbol; and

an encoded value of a third symbol in the second plurality of symbols, wherein the third symbol immediately precedes the second symbol in the ordering of the second plurality of symbols.

4. The method of claim 1, further comprising determining an intermediate value for the first symbol, wherein the intermediate value is equal to one of:

a value of a symbol in the first plurality of symbols that maps to the first symbol when only one symbol in the first plurality of symbols maps to the first symbol; and

a value equal to the exclusive disjunction of the one or more values of the one or more symbols in the first plurality of symbols that map to the first symbol.

5. The method of claim 4, wherein encoding the first symbol comprises setting the value of the first symbol to the value of the exclusive disjunction of the determined intermediate value and the encoded value of the second symbol.

6. The method of claim 1, wherein mapping the first plurality of symbols to the second plurality of symbols according to the first distribution algorithm results in at least one of:

approximately ½

of the symbols in the first plurality of symbols having two edges; and

approximately ⅙

of the symbols in the first plurality of symbols having three edges.

7. The method of claim 1, wherein a number of edges of the mapping associated with a symbol in the second plurality of symbols is determined randomly according to a second distribution algorithm.

8. The method of claim 7, wherein using the first distribution and the second distribution to form the mapping from the first plurality of symbols to the second plurality of symbols comprises:

determining a number E of edges;

determining a number K of symbols in the first plurality of symbols;

determining a number N of symbols in the second plurality of symbols;

assigning each symbol of the first plurality of symbols a degree value, wherein the sum of the degree values over all symbols in the first plurality of symbols is equal to E, and wherein the degree value for each symbol in the first plurality of symbol is determined by the first distribution;

assigning each symbol of the second plurality of symbols a degree value, wherein the sum of the degree values over all symbols in the second plurality of symbols is equal to E, and wherein the degree value for each symbol in the second plurality of symbols is determined by the second distribution;

mapping each of the E edges randomly to a unique symbol of the first plurality of symbols, wherein the number of edges mapped to each symbol is equal to the degree value assigned to that symbol; and

mapping each of the E edges randomly to a unique symbol of the second plurality of symbols, wherein the number of edges mapped to each symbol is equal to the degree value assigned to that symbol.

9. The method of claim 1, further comprising transmitting one or more symbols comprising one of:

the first plurality of symbols;

the second plurality of symbols; and

a combination of symbols in the first plurality of symbols and symbols in the second plurality of symbols.

10. The method of claim 9, wherein the order in which one or more symbols are transmitted from at least the second plurality of symbols is random.

11. A method of decoding data transmitted over a communications channel, comprising:

receiving one or more transmitted symbols, wherein a first symbol from a first plurality of symbols is received, a second symbol from the first plurality of symbols that immediately precedes the first symbol in an ordering of the first plurality of symbols is not received, and a third symbol from the first plurality of symbols that immediately precedes the second symbol in the ordering of the first plurality of symbols is received; and

decoding the received one or more transmitted symbols to recover one or more symbols in a second plurality of symbols based, at least in part, on the values of the first received symbol and the third received symbol, wherein the second plurality of symbols are mapped to the first plurality of symbols according to a first distribution algorithm.

12. The method of claim 11, wherein a number of edges of the mapping associated with a symbol in the second plurality of symbols is determined randomly according to the first distribution algorithm.

13. The method of claim 11, wherein at least one of the symbols from the second plurality of symbols that is mapped to the second symbol that is not received is recovered based, at least in part, on the values of the first received symbol and the third received symbol.

14. The method of claim 11, wherein decoding comprises determining an exclusive disjunction value of the values of the symbols from the second plurality of symbols that mapped to the first received symbol and the values of the symbols from the second plurality of symbols that mapped to the second symbol that is not received.

15. The method of claim 14, wherein determining the exclusive disjunction value comprises calculating the exclusive disjunction value of the value of the first received symbol and the value of the third received symbol.

16. A computer program product for decoding data transmitted over a communications channel, the computer program product comprising:

a non-transitory computer-readable medium having program code recorded thereon, the program code including;

program code to receive one or more transmitted symbols, wherein a first symbol from a first plurality of symbols is received, a second symbol from the first plurality of symbols that immediately precedes the first symbol in an ordering of the first plurality of symbols is not received, and a third symbol from the first plurality of symbols that immediately precedes the second symbol in the ordering of the first plurality of symbols is received; and

program code to decode the received one or more transmitted symbols to recover one or more symbols in a second plurality of symbols based, at least in part, on the values of the first received symbol and the third received symbol, wherein the second plurality of symbols are mapped to the first plurality of symbols according to a first distribution algorithm.

17. The computer program product of claim 16, wherein a number of edges of the mapping associated with a symbol in the second plurality of symbols is determined randomly according to the first distribution algorithm.

18. The compute program product of claim 16, wherein at least one of the symbols from the second plurality of symbols that is mapped to the second symbol that is not received is recovered based, at least in part, on the values of the first received symbol and the third received symbol.

19. The compute program product of claim 16, wherein the program code to decode comprises program code to determine an exclusive disjunction value of the values of the symbols from the second plurality of symbols that mapped to the first received symbol and the values of the symbols from the second plurality of symbols that mapped to the second symbol that is not received.

20. The compute program product of claim 16, wherein the program code to determine the exclusive disjunction value comprises program code to calculate the exclusive disjunction value of the value of the first received symbol and the value of the third received symbol.