Systematic encoding and decoding of chain reaction codes

• US 20040075593A1
• Filed: 10/01/2003
• Published: 04/22/2004
• Est. Priority Date: 10/05/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Shokrollahi, M. Amin
• Granted Patent: US 6,909,383 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• 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: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04L 1/00 Arrangements for detecting or preventing errors in the information received correcting synchronisation H04L7/00

Abstract

A method of encoding data into a chain reaction code includes generating a set of input symbols from input data. Subsequently, one or more non-systematic output symbols is generated from the set of input symbols, each of the one or more non-systematic output symbols being selected from an alphabet of non-systematic output symbols, and each non-systematic output symbol generated as a function of one or more of the input symbols. As a result of this encoding process, any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered, and (b) one or more of the non-systematic output symbols.

Claims

1. A method of encoding data into a chain reaction code having systematic output symbols and non-systematic output symbols, the method comprising:

generating, from the data, a set of input symbols, the input symbols comprising systematic output symbols; and

generating, from the set of input symbols, one or more non-systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols,

wherein any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered and (b) one or more of the non-systematic output symbols.

2. The method of claim 1, wherein generating one or more non-systematic output symbols comprises:

generating a plurality of intermediate input symbols from the set of input symbols; and

encoding the plurality of intermediate input symbols into one or more non-systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.

3. The method of claim 2, wherein generating the plurality of intermediate input symbols comprises:

computing systematic keys for the plurality of input symbols; and

generating, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.

4. The method of claim 3, wherein computing systematic keys for the plurality of input symbols comprises constructing a matrix having K columns and J rows, wherein K corresponds to the number of input symbols, the method further comprising:

(i) initializing J to 0;

(ii) computing a key D(J) as a function of J;

(iii) computing row entries of the J^th row as a function of the key D(J); and

(iv) determining if the rows in the matrix are linearly independent,

wherein if the matrix rows are not linearly independent J is incremented to J+1 and (ii)-(iii) are repeated, and wherein if the matrix rows are linearly independent the systematic keys are computed as a function of the linearly independent rows.

5. The method of claim 4, wherein (ii) computing a key D(J) comprising using a random number generator to compute key D(J) as a function of J.

6. The method of claim 4, wherein the row entries comprise a value of 0 or 1.

7. The method of claim 3, wherein computing systematic keys for the plurality of input symbols comprises:

(i) computing L unique keys D(0)-D(L-1), wherein L is a predefined number;

(ii) constructing a modified decoding matrix having K columns and L rows, wherein K corresponds to the number of input symbols, and wherein for any value of j between 0 and L-1 the row entries along the j^th row are computed as a function of the key D(j); and

(iii) solving the set of linear equations described by the modified decoding matrix, wherein the systematic keys are computed as a function of the solutions of the linear equations.

8. The method of claim 1, further comprising transmitting the systematic output symbols and the non-systematic output symbols over a communication channel.

9. The method of claim 8, further comprising:

receiving one or more systematic output symbols comprising a first subset of the set of input symbols;

receiving one or more non-systematic output symbols, wherein each non-systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and

recovering a remaining subset of the set of input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from;

(i) a predetermined number of non-systematic output symbols;

or

(ii) a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols.

10. The method of claim 9, wherein recovering a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises:

decoding a combination of the one or more received non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols; and

encoding the plurality of intermediate input symbols into a plurality of input symbols comprising a remaining subset of input symbols, the remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols.

11. The method of claim 10, wherein decoding the one or more non-systematic output symbols and the one or more systematic output symbols into a plurality of intermediate input symbols comprises:

computing systematic keys corresponding to the received systematic output symbols;

computing non-systematic keys corresponding to the received non-systematic output symbols; and

generating, from the systematic keys, the non-systematic keys, the received non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.

12. The method of claim 10, wherein encoding the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises:

computing systematic keys for the systematic output symbols not received; and

generating, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.

13. A method of decoding a chain reaction code having systematic output symbols and non-systematic output symbols into a set of input symbols, the input symbols comprising data which is sought, the method comprising:

providing a first subset of the set of input symbols, the first subset of input symbols comprising one or more systematic output symbols;

providing one or more non-systematic output symbols, wherein each non-systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and

recovering a remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from;

(i) a predetermined number of non-systematic output symbols;

or

(ii) a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols.

14. The method of claim 13, wherein recovering a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises:

decoding a combination of the one or more received non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols; and

encoding the plurality of intermediate input symbols into one or more input symbols comprising a remaining subset of input symbols, the first subset and remaining subset of input symbols collectively forming the set of input symbols.

15. The method of claim 14, wherein decoding the one or more non-systematic output symbols into a plurality of intermediate input symbols comprises:

computing systematic keys corresponding to the received systematic output symbols;

computing non-systematic keys corresponding to the received non-systematic output symbols; and

generating, from the systematic keys, the non-systematic keys, the non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.

16. The method of claim 13, wherein encoding the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises:

computing systematic keys for the systematic output symbols not provided; and

generating, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.

17. The method of claim 13, further comprising receiving the systematic and non-systematic output symbols by means of a transmission sent along a communication channel.

18. A method of processing data using chain reaction codes, the method comprising:

generating, from the data, a set of input symbols, the input symbols comprising systematic output symbols;

generating, from the set of input symbols, one or more non-systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols;

receiving a first subset of the set of input symbols, the first subset of input symbols comprising one or more systematic output symbols;

receiving one or more non-systematic output symbols, wherein each non-systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and

recovering a remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from;

(i) a predetermined number of non-systematic output symbols;

or

(ii) a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols.

19. The method of claim 18, wherein generating one or more non-systematic output symbols comprises:

generating a plurality of intermediate input symbols from the set of input symbols; and

encoding the plurality of intermediate input symbols into one or more non-systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.

20. The method of claim 19, wherein generating the plurality of intermediate input symbols comprises:

computing systematic keys for the plurality of input symbols; and

generating, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.

21. The method of claim 18, wherein recovering a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises:

decoding a combination of the one or more received non-systematic output symbols and the one or more received systematic output symbols into a plurality of intermediate input symbols; and

encoding the plurality of intermediate input symbols into one or more input symbols comprising a remaining subset of input symbols, the first subset and remaining subset of input symbols collectively forming the set of input symbols.

22. The method of claim 21, wherein decoding the one or more non-systematic output symbols and the one or more received systematic output symbols into a plurality of intermediate input symbols comprises:

computing systematic keys corresponding to the received systematic output symbols;

computing non-systematic keys corresponding to the received non-systematic output symbols; and

generating, from the systematic keys, the non-systematic keys, the non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.

23. The method of claim 18, wherein encoding the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises:

computing systematic keys for the systematic output symbols not provided; and

generating, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.

24. The method of claim 18, further comprising receiving the systematic and non-systematic output symbols by means of a transmission sent along a communication channel.

25. The method of claim 18, wherein receiving a first subset of the set of input symbols comprises receiving a transmission containing a first subset of the set of input symbols, and wherein receiving one or more non-systematic output symbols comprises receiving a transmission containing the one or more non-systematic output symbols.

26. An encoder configured to encode a set of input data into a chain reaction code, the chain reaction code including systematic output symbols and non-systematic output symbols, the encoder comprising:

an input symbol generator coupled to receive the set of input data and operable to output, in response, one or more input symbols;

a systematic key generator operable to generate a systematic key corresponding to each input symbol;

a non-systematic key generator operable to generate one or more non-systematic keys; and

a systematic encoder coupled to receive the one or more input symbols, the systematic keys, and the non-systematic keys and to output, in response, one or more non-systematic keys and one or more input symbols, wherein the output input symbols comprise systematic output symbols.

27. The encoder of claim 26, wherein the systematic encoder comprises:

a chain reaction decoder coupled to receive the one or more input symbols and systematic keys corresponding to the one or more input symbols, the chain reaction decoder operable to produce, in response, one or more intermediate input symbols;

a chain reaction encoder coupled to receive the one or more intermediate input symbols and the one or more non-systematic keys, the chain reaction decoder operable to produce, in response, one or more non-systematic output symbols.

28. The encoder of claim 27, further comprising a transmit module coupled to receive the one or more input symbols and the one or more non-systematic output symbols, the transmit module operable to transmit the input symbols and the non-systematic output symbols, wherein the transmitted input symbols comprise systematic output symbols.

29. An decoder configured to decode a set of chain reaction codes, the chain reaction code including one or more non-systematic output symbols and one or more systematic output symbols, the decoder comprising:

a non-systematic key generator configured to generate a set of non-systematic keys for each acquired non-systematic output symbols;

a systematic key generator configured to regenerate one or more systematic keys;

a systematic decoder coupled to receive the one or more systematic output symbols, the one or more systematic output symbols, the systematic keys, and the non-systematic keys, and to output, in response, one or more input symbols.

30. The decoder of claim 29, wherein the systematic key regenerator is configured to regenerate a first set of systematic keys and a second set of systematic keys, wherein each of the first set of systematic keys corresponds to an acquired systematic output symbol, and wherein each of the second set of systematic keys corresponds to a missing systematic output symbol.

31. The decoder of claim 30, wherein the systematic encoder comprises:

a chain reaction decoder coupled to receive the received systematic output symbols, the set of non-systematic keys, and the first and second set of systematic keys, the chain reaction decoder producing, in response, a corresponding set of intermediate input symbols; and

a chain reaction encoder coupled to receive the intermediate input symbols and the second set of systematic keys, the chain reaction encoder producing, in response, a copy of the missing systematic output symbols,

wherein the received systematic output symbols in combination with the copy of the non-received systematic output symbols comprises the complete set of transmitted input symbols comprising the set of original data.

32. A computer program product, stored on a computer readable medium, for encoding data into a chain reaction code, the chain reaction code including systematic output symbols and non-systematic output symbols, the computer program product comprising:

instruction code to generate, from the data, a set of input symbols, the input symbols comprising systematic output symbols; and

instruction code to generate, from the set of input symbols, one or more non-systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols,

wherein any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered and (b) one or more of the non-systematic output symbols.

33. The computer program product of claim 32, wherein instruction code to generate one or more non-systematic output symbols comprises:

instruction code to generate a plurality of intermediate input symbols from the set of input symbols; and

instruction code to encode the plurality of intermediate input symbols into one or more non-systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.

34. The computer program product of claim method of claim 33, wherein the instruction code to generate the plurality of intermediate input symbols comprises:

instruction code to compute systematic keys for the plurality of input symbols; and

instruction code to generate, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.

35. A computer program product, stored on a computer readable storage medium, for decoding a chain reaction code into a set of input symbols, the chain reaction code including systematic output symbols and non-systematic output symbols, the input symbols comprising data which is sought, the computer program product comprising:

instruction code to provide a first subset of the set of input symbols, the first subset of input symbols comprising one or more systematic output symbols;

instruction code to provide one or more non-systematic output symbols, wherein each non-systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and

instruction to recover a remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from;

(i) a predetermined number of non-systematic output symbols;

or

(ii) a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols.

36. The computer program product of claim 35, wherein the instruction code to recover a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises:

instruction code to decode a combination of the one or more received non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols; and

instruction code to encode the plurality of intermediate input symbols into one or more input symbols comprising a remaining subset of input symbols, the first subset and remaining subset of input symbols collectively forming the set of input symbols.

37. The computer program product of claim 36, wherein the instruction code to decode the one or more non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols comprises:

instruction code to compute systematic keys corresponding to the received systematic output symbols;

instruction code to compute non-systematic keys corresponding to the received non-systematic output symbols; and

instruction code to generate, from the systematic keys, the non-systematic keys, the non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.

38. The computer program product of claim 36, wherein instruction code to encode the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises:

instruction code to compute systematic keys for the systematic output symbols not provided; and

instruction code to generate, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.