Protection of data from erasures using subsymbol based codes

• US 20050219070A1
• Filed: 12/01/2004
• Published: 10/06/2005
• Est. Priority Date: 12/01/2003
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Shokrollahi, M. Amin
• Granted Patent: US 7,412,641 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• CPC Class Codes: G06F 11/3672 Test management
• CPC Class Codes: H03M 13/132 Algebraic geometric codes, e.g. Goppa codes

Abstract

An encoder uses output symbol subsymbols to effect or control a tradeoff of computational effort and overhead efficiency to, for example, greatly reduce computational effort for the cost of a small amount of overhead efficiency. An encoder reads an ordered plurality of input symbols, comprising an input file or input stream, and produces output subsymbol. The ordered plurality of input symbols are each selected from an input alphabet, and the generated output subsymbols comprise selections among an output subsymbol alphabet. An output subsymbol is generated using a function evaluator applied to subsymbols of the input symbols. The encoder may be called one or more times, each time producing an output subsymbol. Output subsymbols can then be assembled into output symbols and transmitted to their destination. The functions used to generate the output subsymbols from the input subsymbols can be XOR'"'"'s of some of the input subsymbols and these functions are obtained from a linear code defined over an extension field of GF(2) by transforming each entry in a generator or parity-check matrix of this code into an appropriate binary matrix using a regular representation of the extension field over GF(2). In a decoder, output subsymbols received by the recipient are obtained from output symbols transmitted from one sender that generated those output symbols based on an encoding of an input sequence (file, stream, etc.).

Claims

1. A method of transmitting data from a source to a destination over a communication channel wherein the data to be transmitted is arranged into an ordered set of input symbols, the method further comprising:

designating input subsymbols of the data, wherein an input subsymbol is a portion or all of an input symbol and at least one input symbol is divided into two or more subsymbols and each input subsymbol is identifiable with an index unique within its input symbol;

generating a plurality of output subsymbols from the input subsymbols, wherein an output subsymbol is generated from one or more input subsymbol using a value function and a set of associates, the set of associates identifying the input subsymbols to which the value function is applied, wherein at least one output subsymbol is a function of a plurality of input subsymbols each having distinct indices within their input symbols;

generating a plurality of output symbols from the generated plurality of outputs of symbols, wherein the plurality of output symbols is such that, for at least one possible set of received output symbols of equal size to the encoded input symbols, additional received output symbols are required to completely decoding of received output symbols to regenerated the encoded input symbols; and

transmitting the plurality of output symbols over the communication channel, such that a recipient can regenerate the ordered set of input symbols from some or all of the plurality of output symbols.

2. The method of claim 1, wherein the number of possible output symbols for a given set of input symbols is effectively unlimited with respect to the number of output symbols needed to regenerate the set of input symbols

3. The method of claim 1, wherein at least one output subsymbol is generated from more than one input subsymbol and from less than all of the input subsymbols in the set of input subsymbols and from less than all of the subsymbols in at least one input symbol.

4. The method of claim 1, wherein each of the input symbols are divided into a common number of subsymbols and the common number is greater than one.

5. The method of claim 1, wherein the value function is the same for all output subsymbols.

6. The method of claim 1, wherein the value function is different for at least two output subsymbols.

7. The method of claim 1, wherein the set of associates are determined using a chain reaction coding process.

8. The method of claim 1, wherein the value function is a linear function of the set of associates.

9. The method of claim 8, wherein the linear function is derived using an interleaved transformation process.

10. The method of claim 1, wherein the value functions varies over output subsymbols, is a linear function of the set of associates derived using an interleaved transformation process wherein a plurality of value functions is obtained using the interleaved transformation process applied to a generator matrix of a code defined over a finite field of degree at least two over its prime field.

11. The method of claim 10, wherein the code is an Algebraic-Geometric code defined over a curve of genus larger than zero.

12. The method of claim 10, wherein the code is a random code.

13. The method of claim 10 in which the code is a chain reaction code over a finite field which is an extension of degree at least two over its prime field.

14. The method of claim 13, wherein the chain reaction code is a random code.

15. A method of encoding data comprising s input symbols, where s is an integer greater than one, into t symbols, where t is an integer greater than one, the method comprising:

dividing each of the s input symbols into m subsymbols of the same size;

obtaining a base matrix of t rows and s columns, wherein the base matrix entries are members of a finite field GF(2^m) and the base matrix forms other than a Reed-Solomon base matrix;

generating an expansion binary matrix from the base matrix by substituting for each entry of the base matrix a regular representation of a finite field as a GF(2)-module, thereby generating a binary matrix of t*m rows and s*m columns;

operating the expansion binary matrix on the s*m input subsymbols to from t*m output subsymbols, and

grouping groups of m output subsymbols into output symbols, thus forming t output symbols that, together with the s input symbols is usable as error-correction for the s input symbols.

16. The method of claim 15, wherein the base matrix represents an algebraic-geometric code based on a curve of genus greater than zero.