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

• US 9,264,069 B2
• Filed: 06/27/2011
• Issued: 02/16/2016
• 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, Sam
• Application Number:
  US13/170,028
• Publication Number:
  US 20110258510A1
• Time in Patent Office: 1,695 Days
• Field of Search: 714/752, 714/758, 714/784
• US Class Current: 1/1
• 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 decoding information received over a communications channel from an encoder, the method comprising:

receiving symbols from the communications channel, the received symbols including received source symbols of encoded data, first code encoding symbols generated from the source symbols according to a first FEC code, second code encoding symbols generated from the source symbols according to a second FEC code, first FEC code keys, and second FEC code keys, the first FEC code different from the second FEC code;

using the received source symbols, the first code encoding symbols, and the first FEC code keys to first recover one or more missing source symbols; and

if source symbols are still missing following the first recovery,

converting the first code encoding symbols and the first FEC code keys into converted encoding symbols and converted FEC code keys suitable for use for decoding using the second FEC code, and

using the received source symbols, the recovered source symbols, the second code encoding symbols, the converted encoding symbols, the second FEC code keys, and the converted FEC code keys to further recover one or more missing source symbols.

2. The method of claim 1, further comprising, following the first recovery and preceding the further recovery, using the received source symbols, the recovered source symbols, the second code encoding symbols, and the second FEC code keys to second recover one or more missing source symbols.

3. The method of claim 1, wherein the second FEC code is represented using a generalized matrix, and the further recovery comprises augmenting the generalized matrix with a new row for each converted encoding symbol.

4. The method of claim 1, wherein converting comprises:

for at least one first code encoding symbol, identifying source symbols of the first FEC code that are associated with the first code encoding symbol using a corresponding first FEC code key;

for each identified source symbol of the first FEC code whose value is known, eliminating the value of the identified source symbol from the first code encoding symbol;

for each identified source symbol of the first FEC code, identifying source symbols of the second FEC code that can be derived from the identified source symbol of the first FEC code, each identified source symbol of the second FEC code comprising a specific first sequence of bits taken from the identified source symbol of the first FEC code, the bits of the specific first sequence located at specific bit positions of the identified source symbol of the first FEC code;

outputting converted encoding symbols, each converted encoding symbol comprising a specific second sequence of bits taken from the first code encoding symbol, the bits of the specific second sequence located at the same specific bit positions of the first code encoding symbol; and

outputting converted FEC code keys, each converted FEC code key identifying source symbols of the second FEC code that are associated with a corresponding converted encoding symbol.

5. A hybrid decoder for decoding information received over a communications channel from an encoder, the hybrid decoder comprising:

an input for receiving symbols from the communications channel, the received symbols including received source symbols of encoded data, first code encoding symbols generated from the source symbols according to a first FEC code, second code encoding symbols generated from the source symbols according to a second FEC code, first FEC code keys, and second FEC code keys, the first FEC code different from the second FEC code;

a first FEC code decoder communicatively coupled with the input and configured to use the received source symbols, the first code encoding symbols, and the first FEC code keys to recover one or more missing source symbols;

a symbol converter communicatively coupled with the first FEC code decoder and configured to convert the first code encoding symbols and the first FEC code keys into converted encoding symbols and converted FEC code keys suitable for use by a second FEC code decoder; and

the second FEC code decoder communicatively coupled with the symbol converter and configured to use the received source symbols, the recovered source symbols, the second code encoding symbols, the converted encoding symbols, the second FEC code keys, and the converted FEC code keys to recover one or more missing source symbols.

6. The hybrid decoder of claim 5, wherein the second FEC code decoder is further configured to recover one or more missing source symbols using the received source symbols, the recovered source symbols, the second code encoding symbols, and the second FEC code keys without using the converted encoding symbols or the converted FEC code keys.

7. The hybrid decoder of claim 5, wherein the second FEC code decoder is configured to represent the second FEC code using a generalized matrix and to augment the generalized matrix with a new row for each converted encoding symbol.

8. The hybrid decoder of claim 5, wherein the symbol converter is configured to:

identify, for at least one first code encoding symbol, source symbols of the first FEC code that are associated with the first code encoding symbol using a corresponding first FEC code key;

eliminate, for each identified source symbol of the first FEC code whose value is known, the value of the identified source symbol from the first code encoding symbol;

identify, for each identified source symbol of the first FEC code, source symbols of the second FEC code that can be derived from the identified source symbol of the first FEC code, each identified source symbol of the second FEC code comprising a specific first sequence of bits taken from the identified source symbol of the first FEC code, the bits of the specific first sequence located at specific bit positions of the identified source symbol of the first FEC code;

output converted encoding symbols, each converted encoding symbol comprising a specific second sequence of bits taken from the first code encoding symbol, the bits of the specific second sequence located at the same specific bit positions of the first code encoding symbol; and

output converted FEC code keys, each converted FEC code key identifying source symbols of the second FEC code that are associated with a corresponding converted encoding symbol.

9. 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, the received symbols including received source symbols of the encoded data, first code encoding symbols generated from the source symbols according to a first FEC code, second code encoding symbols generated from the source symbols according to a second FEC code, first FEC code keys, and second FEC code keys, the first FEC code different from the second FEC code;

means for recovering one or more missing source symbols using the received source symbols, the first code encoding symbols, and the first FEC code keys; and

if source symbols are still missing following the first recovery,

means for converting the first code encoding symbols and the first FEC code keys into converted encoding symbols and converted FEC code keys suitable for use by means for recovering missing source symbols using the second FEC code, and

means for further recovering one or more missing source symbols using the received source symbols, the recovered source symbols, the second code encoding symbols, the converted encoding symbols, the second FEC code keys, and the converted FEC code keys.

10. The system of claim 9, wherein the means for further recovering further comprise means for recovering one or more missing source symbols using the received source symbols, the recovered source symbols, the second code encoding symbols, and the second FEC code keys without using the converted encoding symbols or the converted FEC code keys.

11. The system of claim 9, wherein the second FEC code is represented using a generalized matrix, which is augmented with a new row for each converted encoding symbol.

12. The system of claim 9, wherein the means for converting are configured to:

identify, for at least one first code encoding symbol, source symbols of the first FEC code that are associated with the first code encoding symbol using a corresponding first FEC code key;

eliminate, for each identified source symbol of the first FEC code whose value is known, the value of the identified source symbol from the first code encoding symbol;

identify, for each identified source symbol of the first FEC code, source symbols of the second FEC code that can be derived from the identified source symbol of the first FEC code, each identified source symbol of the second FEC code comprising a specific first sequence of bits taken from the identified source symbol of the first FEC code, the bits of the specific first sequence located at specific bit positions of the identified source symbol of the first FEC code;

output converted encoding symbols, each converted encoding symbol comprising a specific second sequence of bits taken from the first code encoding symbol, the bits of the specific second sequence located at the same specific bit positions of the first code encoding symbol; and

output converted FEC code keys, each converted FEC code key identifying source symbols of the second FEC code that are associated with a corresponding converted encoding symbol.

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

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

obtain symbols received from the communications channel, the received symbols including received source symbols of encoded data, first code encoding symbols generated from the source symbols according to a first FEC code, second code encoding symbols generated from the source symbols according to a second FEC code, first FEC code keys, and second FEC code keys, the first FEC code different from the second FEC code;

use the received source symbols, the first code encoding symbols, and the first FEC code keys to first recover one or more missing source symbols; and

if source symbols are still missing following the first recovery,

convert the first code encoding symbols and the first FEC code keys into converted encoding symbols and converted FEC code keys suitable for use for decoding using the second FEC code, and

use the received source symbols, the recovered source symbols, the second code encoding symbols, the converted encoding symbols, the second FEC code keys, and the converted FEC code keys to further recover one or more missing source symbols.

14. The computer program product of claim 13, wherein the processor-readable medium is further configured to cause the processor to, following the first recovery and preceding the further recovery, use the received source symbols, the recovered source symbols, the second code encoding symbols, and the second FEC code keys to second recover one or more missing source symbols.

15. The computer program product of claim 13, wherein the processor-readable medium is configured to cause the processor to represent the second FEC code using a generalized matrix and to augment the generalized matrix with a new row for each converted encoding symbol.

16. The computer program product of claim 13, wherein the processor-readable medium is configured to cause the processor to:

identify, for at least one first code encoding symbol, source symbols of the first FEC code that are associated with the first code encoding symbol using a corresponding first FEC code key;

eliminate, for each identified source symbol of the first FEC code whose value is known, the value of the identified source symbol from the first code encoding symbol;

identify, for each identified source symbol of the first FEC code, source symbols of the second FEC code that can be derived from the identified source symbol of the first FEC code, each identified source symbol of the second FEC code comprising a specific first sequence of bits taken from the identified source symbol of the first FEC code, the bits of the specific first sequence located at specific bit positions of the identified source symbol of the first FEC code;

provide converted encoding symbols, each converted encoding symbol comprising a specific second sequence of bits taken from the first code encoding symbol, the bits of the specific second sequence located at the same specific bit positions of the first code encoding symbol; and

provide converted FEC code keys, each converted FEC code key identifying source symbols of the second FEC code that are associated with a corresponding converted encoding symbol.