Protection of data from erasures using subsymbol based codes
First Claim
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 such that each input subsymbol can be identified by 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 of one input symbol, each input subsymbol being identified by different indices within that one input symbol;
generating a plurality of output symbols from the generated plurality of output subsymbols, 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 decode received output symbols to regenerate 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 Assignments
0 Petitions
Accused Products
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.).
65 Citations
16 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 such that each input subsymbol can be identified by 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 of one input symbol, each input subsymbol being identified by different indices within that one input symbol; generating a plurality of output symbols from the generated plurality of output subsymbols, 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 decode received output symbols to regenerate 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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:
-
obtaining a base matrix of t rows and s columns, wherein the base matrix entries are members of a finite field GF(2m) 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; dividing each of the s input symbols into m subsymbols of the same size, wherein m is greater than one; operating on the s*m input subsymbols using the expansion binary matrix to form 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. - View Dependent Claims (16)
-
Specification