Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems

• US 7,971,129 B2
• Filed: 05/10/2007
• Issued: 06/28/2011
• Est. Priority Date: 05/10/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Watson, Mark, Luby, Michael G.
• Primary Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US11/747,191
• Publication Number:
  US 20070300127A1
• Time in Patent Office: 1,510 Days
• Field of Search: 714/752, 714/758, 714/784, 365/200
• US Class Current: 714/784
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0064 Concatenated codes

Abstract

A method of encoding data for transmissions from a source to a destination over a communications channel is provided. The method operates on an ordered set of source symbols and may generate zero or more redundant symbols from the source symbols, wherein data is encoded in a first step according to a simple FEC code and in a second step, data is encoded according to a second FEC code, more complex than the first FEC code. The first FEC code and/or the second FEC code might comprise coding known in the art. These steps result in two groups of encoded data in such a way that a low-complexity receiver may make use of one of the groups of encoded data while higher complexity receivers may make use of both groups of encoded data.

Claims

1. A method of encoding data for transmission from a source to a destination over a communications channel, the method comprising:

obtaining an ordered set of source symbols representing the data to be encoded using the generated output symbols and an encoding for the data;

generating FEC repair data according to a first code;

generating FEC repair data according to a second code, the second code being more complex than the first code; and

sending the source symbols, the first set of FEC repair data and the second set of FEC repair data, such that received data that includes some or all of the sent data is decodable and the original source block of data is recoverable, wherein the first and second sets of FEC repair data are constructed such that the original source block of data is recoverable with less information than would be required if using the received FEC repair data from only one of the two FEC codes and the FEC decoder for that FEC code and the received original source block data.

2. The method of claim 1, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

3. The method of claim 1, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

4. The method of claim 1, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

5. The method of claim 1, wherein an FEC decoder for the first FEC code is inherently much simpler than an FEC decoder for the second FEC code.

6. The method of claim 1, wherein the FEC decoder for the received data at the receiver has approximately the same complexity as an FEC decoder for the second FEC code.

7. The method of claim 1, wherein a second receiver that receives original source block data and FEC repair data for only the first FEC code can more often fully recover the original source block than a receiver that only receives original source block data.

8. An encoder that encodes data for transmission from a source to a destination over a communications channel, the encoder comprising:

an input for receiving an ordered set of source symbols representing the data to be encoded;

first logic for generating a first set of repair data generated from the source symbols according to a first FEC code;

second logic for generating a second set of repair data generated from the source symbols according to a second FEC code, the second FEC code being more complex than the first FEC code where complexity is a measure of computational effort required to generate repair symbols; and

an output for outputting at least the first set of repair data and the second set of repair data,

wherein the first and second sets of repair data are constructed such that the original ordered set of source symbols is recoverable with less information than would be required if using the received FEC repair data from only one of the first and second set of repair data.

9. The encoder of claim 8, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

10. The encoder of claim 8, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

11. The encoder of claim 8, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

12. A decoder for decoding information received over a communications channel, possibly with errors and/or erasures and/or lost or missing information, from an encoder, the decoder comprising:

an input for receiving symbols from the communications channel;

logic for identifying whether a received symbol represents a source symbol of the encoded data, a first type of repair symbol for recovering lost, incorrect or missing information of the encoded data or a second type of repair symbol for recovering lost, incorrect or missing information of the encoded data, wherein the first type of repair symbol is a repair symbol generated from the source symbols according to a first FEC code and the second type of repair symbol is a repair symbol generated from the source symbols according to a second FEC code, the second FEC code being more complex than the first FEC code where complexity is a measure of computational effort required to generate repair symbols; and

logic for using at least the received source symbols, at least one repair symbol of the first type and at least one repair symbol of the second type to recover the encoded data, such that the encoded data is recovered with less information than would be required if only one of the first type of repair symbol or the second type of repair symbol are used.

13. The decoder of claim 12, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

14. The decoder of claim 12, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

15. The decoder of claim 12, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

16. A method of decoding transmitted data that encodes for a set of source symbols transmitted over a communications channel, the method comprising:

receiving symbols from the communications channel;

identifying whether a received symbol represents a source symbol of the encoded data, a first type of repair symbol for recovering lost, incorrect or missing information of the encoded data or a second type of repair symbol for recovering lost, incorrect or missing information of the encoded data, wherein the first type of repair symbol is a repair symbol generated from the source symbols according to a first FEC code and the second type of repair symbol is a repair symbol generated from the source symbols according to a second FEC code, the second FEC code being more complex than the first FEC code where complexity is a measure of computational effort required to generate repair symbols; and

using at least the received source symbols, at least one repair symbol of the first type and at least one repair symbol of the second type to recover the encoded data, such that the encoded data is recovered with less information than would be required if only one of the first type of repair symbol or the second type of repair symbol are used.

17. The method of claim 16, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

18. The method of claim 16, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

19. The method of claim 16, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

20. A system for encoding data for transmission from a source to a destination over a communications channel, the system comprising:

means for generating from an ordered set of source symbols FEC repair data according to a first code, the ordered set of source symbols representing the data to be encoded;

means for generating from the ordered set of source symbols FEC repair data according to a second code, the second code being more complex than the first code; and

means for sending the source symbols, the first set of FEC repair data and the second set of FEC repair data, such that received data that includes some or all of the sent data is decodable and the original source block of data is recoverable, wherein the first and second sets of FEC repair data are constructed such that the original source block of data is recoverable with less information than would be required if using the received FEC repair data from only one of the two FEC codes and the FEC decoder for that FEC code and the received original source block data.

21. The system of claim 20, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

22. The system of claim 20, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

23. The system of claim 20, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

24. A system for decoding transmitted data that encodes for a set of source symbols transmitted over a communications channel, the system comprising:

means for receiving symbols from the communications channel;

means for identifying whether a received symbol represents a source symbol of the encoded data, a first type of repair symbol for recovering lost, incorrect or missing information of the encoded data or a second type of repair symbol for recovering lost, incorrect or missing information of the encoded data, wherein the first type of repair symbol is a repair symbol generated from the source symbols according to a first FEC code and the second type of repair symbol is a repair symbol generated from the source symbols according to a second FEC code, the second FEC code being more complex than the first FEC code where complexity is a measure of computational effort required to generate repair symbols; and

means for using at least the received source symbols, at least one repair symbol of the first type and at least one repair symbol of the second type to recover the encoded data, such that the encoded data is recovered with less information than would be required if only one of the first type of repair symbol or the second type of repair symbol are used.

25. The system of claim 24, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

26. The system of claim 24, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

27. The system of claim 24, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

28. A computer program product for encoding data for transmission from a source to a destination over a communications channel, the product comprising:

a processor-readable medium storing processor-readable instructions configured to cause a processor to;

obtain an ordered set of source symbols representing the data to be encoded using the generated output symbols and an encoding for the data;

generate FEC repair data according to a first code;

generate FEC repair data according to a second code, the second code being more complex than the first code; and

provide for sending the source symbols, the first set of FEC repair data and the second set of FEC repair data, such that received data that includes some or all of the sent data is decodable and the original source block of data is recoverable, wherein the first and second sets of FEC repair data are constructed such that the original source block of data is recoverable with less information than would be required if using the received FEC repair data from only one of the two FEC codes and the FEC decoder for that FEC code and the received original source block data.

29. The computer program product of claim 28, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

30. The computer program product of claim 28, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

31. The computer program product of claim 28, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.

32. A computer program product for decoding transmitted data that encodes for a set of source symbols transmitted over a communications channel, the product comprising:

a processor-readable medium storing processor-readable instructions configured to cause a processor to;

obtain symbols received from the communications channel;

identify whether a received symbol represents a source symbol of the encoded data, a first type of repair symbol for recovering lost, incorrect or missing information of the encoded data or a second type of repair symbol for recovering lost, incorrect or missing information of the encoded data, wherein the first type of repair symbol is a repair symbol generated from the source symbols according to a first FEC code and the second type of repair symbol is a repair symbol generated from the source symbols according to a second FEC code, the second FEC code being more complex than the first FEC code where complexity is a measure of computational effort required to generate repair symbols; and

use at least the received source symbols, at least one repair symbol of the first type and at least one repair symbol of the second type to recover the encoded data, such that the encoded data is recovered with less information than would be required if only one of the first type of repair symbol or the second type of repair symbol are used.

33. The computer program product of claim 32, wherein the first FEC code is a simple parity code and the second FEC code is a chain reaction code.

34. The computer program product of claim 32, wherein the first FEC code is a simple parity code and the second FEC code is a Reed-Solomon code.

35. The computer program product of claim 32, wherein the first FEC code is a Reed-Solomon code and the second FEC code is a LDPC, LDGM or chain reaction code.