Systematic encoding and decoding of chain reaction codes
First Claim
1. A method of encoding data, wherein the data to be encoded is represented as a set of K input symbols stored in a non-transitory form in an electronically-readable medium, K being an integer greater than one, wherein each of the K input symbols has a value that is from an input symbol alphabet, and wherein the encoded data is representable as a plurality of output symbols, each of which has a value that is from an output symbol alphabet, the method comprising:
- obtaining at least some of the K input symbols in an electronically-readable form, such that each of the K input symbols has an associated position within the K input symbols;
generating, from the plurality of input symbols, a plurality of intermediate symbols, each intermediate symbol having an associated position within the plurality of intermediate symbols, wherein the generation of the plurality of intermediate symbols from the plurality of input symbols is performed according to a rateless decoding process, wherein a rateless decoding process is rateless in that it is an inverse of a rateless encoding process that can generate a number of output symbols where the number is independent of the number of input symbols; and
generating output symbols of the plurality of output symbols, using the rateless encoding process and having the plurality of intermediate symbols as an input, wherein the rateless encoding process and the rateless decoding process have the property that the plurality of output symbols is, in part, systematic, so that K of the plurality of output symbols are equal to the K input symbols, and further wherein additional output symbols beyond K systematic output symbols are generated using the same rateless encoding process as would generate the K systematic output symbols.
2 Assignments
0 Petitions
Accused Products
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.
460 Citations
46 Claims
-
1. A method of encoding data, wherein the data to be encoded is represented as a set of K input symbols stored in a non-transitory form in an electronically-readable medium, K being an integer greater than one, wherein each of the K input symbols has a value that is from an input symbol alphabet, and wherein the encoded data is representable as a plurality of output symbols, each of which has a value that is from an output symbol alphabet, the method comprising:
-
obtaining at least some of the K input symbols in an electronically-readable form, such that each of the K input symbols has an associated position within the K input symbols; generating, from the plurality of input symbols, a plurality of intermediate symbols, each intermediate symbol having an associated position within the plurality of intermediate symbols, wherein the generation of the plurality of intermediate symbols from the plurality of input symbols is performed according to a rateless decoding process, wherein a rateless decoding process is rateless in that it is an inverse of a rateless encoding process that can generate a number of output symbols where the number is independent of the number of input symbols; and generating output symbols of the plurality of output symbols, using the rateless encoding process and having the plurality of intermediate symbols as an input, wherein the rateless encoding process and the rateless decoding process have the property that the plurality of output symbols is, in part, systematic, so that K of the plurality of output symbols are equal to the K input symbols, and further wherein additional output symbols beyond K systematic output symbols are generated using the same rateless encoding process as would generate the K systematic output symbols. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An encoder, having an input to electronically receive data to be encoded and an output to output encoded data that can represent the received data as the encoded data is conveyed over a communications channel, wherein the encoded data is representable as a plurality of output symbols, each of which has a value that is from an output symbol alphabet, the encoder comprising:
-
an input for receiving K input symbols in an electronically-readable form, the K input symbols representing the data to be encoded, K being an integer greater than one, wherein each of the K input symbols has a value that is from an input symbol alphabet; storage for at least some of the K input symbols, such that values of stored input symbols can be read by a module of the encoder and wherein each of the stored input symbols has an associated position within the K input symbols; a key generator for generating K systematic key values; a decoder module for generating a plurality of L intermediate symbols from the K input symbols according to the K systematic key values; a rateless encoder module for generating non-systematic output symbols that form part of the encoded data, generated from intermediate symbols and non-systematic key values, wherein the rateless encoder is such that, given the plurality of L intermediate symbols based on the K systematic key values and the K input symbols, the rateless encoder'"'"'s output would match the K input symbols, wherein the rateless encoding process is rateless in that it can generate an output symbol for each of a plurality of keys and the number of keys available is independent of K; and an output for outputting K systematic output symbols and outputting additional output symbols that are non-systematic output symbols. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
16. A computer program product that comprises a non-transitory tangible media storing computer-executable code for execution upon a computer system including a processor, the computer program product comprising:
-
program code for encoding data, wherein the data to be encoded is represented as a set of K input symbols stored in a non-transitory form in an electronically-readable medium, K being an integer greater than one, wherein each of the K input symbols has a value that is from an input symbol alphabet, and wherein the encoded data is representable as a plurality of output symbols, each of which has a value that is from an output symbol alphabet; program code for reading at least some of the K input symbols, such that each of the K input symbols has an associated position within the K input symbols; program code for generating, from the plurality of input symbols, a plurality of intermediate symbols, each intermediate symbol having an associated position within the plurality of intermediate symbols, including rateless decoder code, wherein rateless decoding is rateless in that it is an inverse of a rateless encoding process that can generate a number of output symbols where the number is independent of the number of input symbols; and program code for generating output symbols of the plurality of output symbols, using the rateless encoding process and having the plurality of intermediate symbols as an input, wherein the rateless encoding process and rateless decoding have the property that the plurality of output symbols is, in part, systematic, so that K of the plurality of output symbols are equal to the K input symbols, and further wherein additional output symbols beyond K systematic output symbols are generated using the same rateless encoding process as would generate the K systematic output symbols. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23)
-
-
24. A method of decoding data received from an electronically-readable medium in a non-transitory form, wherein the received data to be decoded is received as a set of output symbols comprising all or some of a plurality of output symbols generated using a rateless encoding process and encoding for K input symbols, wherein K is an integer greater than one and a rateless encoding process is rateless in that the number of output symbols the process can generate is independent of K, wherein each of the K input symbols is representable by a value that is from an input symbol alphabet, and wherein each of the received output symbols has a value that is from an output symbol alphabet, the method comprising:
-
determining a key for each of the received output symbols to be used in decoding; if an output symbol'"'"'s key is a systematic key, storing that output symbol'"'"'s value as the value for at least one of the K input symbols corresponding to the systematic key, thereby recovering at least one input symbol, and indicating that the output symbol is used up; determining if any of the K input symbols are not yet recovered; and if any unrecovered input symbols remain, performing the steps of; a) determining at least one non-systematic key for output symbols that are not used up; b) determining, based on a non-systematic key, a mapping between input symbols and the output symbol corresponding to that non-systematic key; c) identifying if any input symbols can be recovered from the available not used up output symbols; d) recovering input symbols that can be recovered; e) removing dependency of the not used up output symbols on the recovered input symbols; and f) repeating steps c), d) and e), until a threshold number of the K input symbols are recovered. - View Dependent Claims (25, 26, 27, 28, 29, 30)
-
-
31. A decoder, having an input to electronically receive data to be decoded and an output to output decoded data wherein the received data represents, at least in part, encoded data that is, at least in part, decodable into the encoded data, wherein the encoded data is representable as a plurality of output symbols, the received data is a set of output symbols comprising all or some of a plurality of output symbols generated using a rateless encoding process and encoding for K input symbols, the decoder comprising:
-
an input for receiving the received set of output symbols; storage for at least some recovered input symbols; logic for determining, for each one of at least some of the received output symbols, a key corresponding to the output symbol; logic for designating or storing values of output symbols as values of input symbols when the key of an output symbol is a systematic key; logic for determining mappings of output symbols to input symbols for output symbols that are not used up in decoding; and logic for determining values of input symbols not already recovered, from output symbols that are not used up in decoding and the mappings; and an output for outputting at least a threshold number of input symbols upon receiving a predetermined number of output symbols. - View Dependent Claims (32, 33, 34, 35, 36, 37)
-
-
38. A computer program product that comprises a non-transitory tangible media storing computer-executable code for execution upon a computer system including a processor to decode data received in a non-transitory form as a set of output symbols comprising all or some of a plurality of output symbols generated using a rateless encoding process and encoding for K input symbols, wherein K is an integer greater than one and a rateless encoding process is rateless in that the number of output symbols the process can generate is independent of K, wherein each of the K input symbols is representable by a value that is from an input symbol alphabet, and wherein each of the received output symbols has a value that is from an output symbol alphabet, the computer program product comprising:
-
program code for determining a key for each of the received output symbols to be used in decoding; program code for storing that output symbol'"'"'s value as the value for at least one of the K input symbols, if the output symbol'"'"'s key is a systematic key, thereby recovering at least one input symbol; program code for indicating that the output symbol is used up if its key is a systematic key and the corresponding input symbol is already recovered; program code for determining if any of the K input symbols are not yet recovered; program code for determining if any unrecovered input symbols remain; and program code, executable when unrecovered input symbols remain, for; a) determining at least one non-systematic key for output symbols that are not used up; b) determining, based on a non-systematic key, a mapping between input symbols and the output symbol corresponding to that non-systematic key; c) identifying if any input symbols can be recovered from the available not used up output symbols; d) recovering input symbols that can be recovered; e) removing dependency of the not used up output symbols on the recovered input symbols; and f) repeating steps c), d) and e), until a threshold number of the K input symbols are recovered. - View Dependent Claims (39, 40, 41, 42, 43, 44, 45, 46)
-
Specification