Systematic encoding and decoding of chain reaction codes

• US RE43,741 E1
• Filed: 11/17/2011
• Issued: 10/16/2012
• Est. Priority Date: 10/05/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Shokrollahi, M. Amin, Luby, Michael G.
• Primary Examiner(s): Lauture, Joseph
• Application Number:
  US13/374,565
• Time in Patent Office: 334 Days
• Field of Search: 341/50, 341/51, 341/55, 341/60, 714/15, 714/801, 714/6, 714/752
• 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;

computing systematic keys for the set of input symbols;

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

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, 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;

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 decoding matrix having K columns and L rows, wherein K corresponds to the number of input symbols, and wherein each row corresponds to a function of the key D(j), wherein j is equal to a value between 0 and L−

1;

(iii) initializing a set S to contain no symbols;

(iv) applying chain reaction decoding to the decoding matrix to identify an output node to be added to set S;

(v) adding the output node to set S;

(vi) updating the decoding matrix to remove the output node;

(v) comparing size of set S to K;

(vi) if the size of set S is less than K, repeating steps (iv)-(v); and

(vii) if the size of set S is equal to K, sorting the elements in set S from smallest to largest and using the sorted set S to create the systematic keys.

2. The method of claim 1 wherein computing L unique keys is done using a random number generator.

3. The method of claim 1 wherein computing L unique keys is done using a fixed-list of reusable keys.

4. A computer-readable medium comprising code for performing the method of claim 1.

5. An encoder with a processor and the computer-readable medium of claim 4.

6. 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;

computing systematic keys for the set of input symbols;

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

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, 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;

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) determining whether it is possible if K symbols can be decoded using the L keys;

wherein K corresponds to the number of input symbols;

(iii) if it is determined that K symbols cannot be decoded using the L keys, aborting the current attempt to compute systematic keys for the plurality of input symbols;

(iv) initializing a systematic set, a non-systematic set, and an unvisited set, wherein the systematic set is initialized to be empty, wherein the non-systematic set is initialized to be empty, and wherein the unvisited set is initialized to contain keys D(0)-D(L−

1);

(v) removing a key, C, from the unvisited set;

(vi) determining whether it is possible that K symbols can be decoded using the union of the unvisited set and the systematic set;

(vi) if it is possible to decode K symbols in step (vi), adding key C to the non-systematic set;

(vii) if it is not possible to decode K symbols in step (vi), adding key C to the systematic set;

(viii) repeating steps (v)-(vii) until the systematic set contains at least K symbols; and

(ix) using the systematic set as the systematic keys.

7. The method of claim 6 wherein the current attempt to compute systematic keys is followed by another attempt to compute the systematic keys by restarting the method at step (i).

8. The method of claim 6 wherein computing L unique keys is done using a random number generator.

9. The method of claim 6 wherein computing L unique keys is done using a fixed-list of reusable keys.

10. A computer-readable medium comprising code for performing the method of claim 6.

11. An encoder with a processor and the computer-readable medium of claim 10.

12. 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;

computing systematic keys for the set of input symbols;

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

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, 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 wore of the non-systematic output symbols;

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 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;

wherein computing L unique keys is done using a random number generator.

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;

wherein recovering a remaining subset of the input symbols comprises;

(i) creating a matrix B, wherein the number of rows in B corresponds to the number of provided non-systematic output symbols and wherein the number of columns in B corresponds to the number of input symbols;

(ii) creating a matrix C, wherein the number of rows in C corresponds to the number of systematic keys and wherein the number of columns in C corresponds to the number of input symbols.

(iii) creating a matrix A as the inverse of matrix C;

(iv) creating a matrix H from the product of B and A;

(v) creating a set E, wherein E is the set of indices of the non-provided systematic symbols;

(vi) creating a set R, wherein R is the set of indices of the provided systematic symbols;

(vii) dividing matrix H into sub-matrices He and Hr, wherein He corresponds to the indices of the systematic symbols not provided and wherein Hr corresponds to the indices of the systematic symbols provided;

(ix) creating vector y from the product of Hr with a vector formed by the provided systematic symbols;

(x) creating vector b from the provided non-systematic output symbols and vector y;

(xi) solving the system of equations for x, wherein the system of equations is He*x=y+b; and

(xii) using x to recover input symbols.

14. The method of claim 13 wherein step (iii) creates the inverse matrix using Gaussian elimination.

15. The method of claim 13 wherein step (iii) creates the inverse matrix using chain reaction decoding.

16. The method of claim 13 wherein step (xi) solves the system of equations using Gaussian elimination.

17. The method of claim 13 wherein step (xi) solves the system of equations using chain reaction decoding.

18. The method of claim 13 wherein step (xi) solves the system of equations using inactivation decoding.

19. A computer-readable medium comprising code for performing the method of claim 13.

20. A decoder with a processor and the computer-readable medium of claim 19.