Information additive code generator and decoder for communication systems
View Patent ↗An encoder uses an input file of data and a key to produce an output symbol. An output symbol with key I is generated by determining a weight, W(I), for the output symbol to be generated, selecting W(I) of the input symbols associated with the output symbol according to a function of I, and generating the output symbol's value B(I) from a predetermined value function F(I) of the selected W(I) input symbols. An encoder can be called repeatedly to generate multiple output symbols. The output symbols are generally independent of each other, and an unbounded number (subject to the resolution of I) can be generated, if needed. A decoder receives some or all of the output symbols generated. The number of output symbols needed to decode an input file is equal to, or slightly greater than, the number of input symbols comprising the file, assuming that input symbols and output symbols represent the same number of bits of data.
1. A method for processing encoded data in a decoder, the method comprising:
receiving a first set of output symbols at the decoder, wherein the output symbols are derived from an ordered set of input symbols representing a data that is to be recovered, wherein the number of possible output symbols is much larger than the number of input symbols, wherein the total number of input symbols is estimated to be equal to K, wherein at least one output symbol is generated from more than one, but less than all, of the input symbols in the ordered set of input symbols;
organizing the output symbols in the first set of output symbols at the decoder, wherein organizing the output symbols comprises:
determining a key for each output symbol;
computing a weight for each output symbol;
computing a set of associates for each output symbol; and
computing a value for each output symbol;
processing the output symbols in the first set of output symbols to recover input symbols at the decoder; and
processing the recovered input symbols to recover the data that is to be recovered at the decoder.
2. The method of claim 1 further comprising:
sorting the output symbols using the weight of the output symbols at the decoder.
3. The method of claim 1 wherein the weight for an output symbol is computed as a function of the number of input symbols, K, and the key of the output symbol.
4. The method of claim 1 wherein the set of associates for an output symbol is computed as a function of the weight of the output symbol, the number of input symbols, K, and the key of the output symbol.
5. The method of claim 1 wherein the value of each output symbol is computed using an output value function.
6. The method of claim 5 wherein the output value function is selected as a function of the number of input symbols, K, and the key of the output symbol.
7. The method of claim 1 wherein processing the output symbols to recover input symbols at the decoder comprises:
(i) identifying output symbols that are members of a decodable set;
(ii) recovering input symbols associated with the output symbols in the decodable set;
(iii) adjusting the value, the weight, and the set of associates of any output symbols that are not members of the decodable set using the recovered input symbols; and
(iv) repeating steps (i)-(iii) until an adequate number of input symbols have been recovered or no additional input symbols can be recovered from the first set of output symbols.
8. The method of claim 7 wherein the step of identifying output symbols that are members of a decodable set first examines output symbols with a lower weight before examining output symbols with a higher weight.
9. The method of claim 7 wherein the number of output symbols in the first set of output symbols is equal to K plus A, wherein A is a small percentage of K.
10. The method of claim 9 wherein if no additional input symbols can be recovered from the first set of output symbols and an adequate number of input symbols have not been recovered, then receiving G additional output symbols and the G newly received output symbols are organized and processed as the original K plus A output symbols were organized and processed.
11. The method of claim 7 wherein the step of recovering input symbols associated with the output symbols in the decodable set is deferred while other output symbol processing is occurring.
12. The method of claim 11 wherein the step of recovering input symbols associated with the output symbols in the decodable set is deferred until it is determined that an adequate number of input symbols can be recovered from the output symbols.
13. The method of claim 11 wherein the step of recovering input symbols associated with the output symbols in the decodable set is deferred until it is determined that the input symbols are needed.
14. A method for processing encoded data in a decoder, the method comprising:
receiving a first set of output symbols at the decoder, wherein the output symbols are derived from an ordered set of input symbols representing a data that is to be recovered, wherein the number of possible output symbols is much larger than the number of input symbols, wherein the total number of input symbols is estimated to be equal to K, wherein at least one output symbol is generated from more than one, but less than all, of the input symbols in the ordered set of input symbols;
organizing the output symbols in the first set of output symbols at the decoder, wherein organizing the output symbols comprises:
determining a key for each output symbol;
computing a weight for each output symbol;
computing a value for each output symbol; and
computing a functional index for each output symbol;
processing the output symbols in the first set of output symbols to recover input symbols at the decoder; and
processing the recovered input symbols to recover the data that is to be recovered at the decoder.
15. The method of claim 14 further comprising:
sorting the output symbols using the weight of the output symbols at the decoder.
16. The method of claim 14 wherein the functional index of an output symbol is computed as the xor of the positions of any unrecovered input symbols in the ordered set of input symbols that are also associated with the output symbol.
17. The method of claim 15 wherein the weight for an output symbol is computed as a function of the number of input symbols, K, and the key of the output symbol.
18. The method of claim 14 wherein the value of each output symbol is computed using an output value function.
19. The method of claim 14 wherein the output value function is selected as a function of the number of input symbols, K, and the key of the output symbol.
20. The method of claim 14 wherein processing the output symbols to recover input symbols at the decoder comprises:
(i) identifying a decodable set of output symbols from the first set of output symbols;
(ii) recovering input symbols associated with the output symbols in the decodable set;
(iii) reducing the weight of any output symbols that are not members of the decodable set but are associated with recovered input symbols using the recovered input symbols;
(iv) recalculating the functional index of any output symbols that are not members of the decodable set but are associated with recovered input symbols using the recovered input symbols;
(v) repeating steps (i)-(iv) until an adequate number of input symbols have been recovered or no additional input symbols can be recovered from the first set of output symbols.
21. The method of claim 20 wherein the step of identifying a decodable set of output symbols from the first set of output symbols first examines output symbols with a lower weight before examining output symbols with a higher weight.
22. The method of claim 20 wherein the number of output symbols in the first set of output symbols is equal to K plus A wherein A is a small percentage of K.
23. The method of claim 22 wherein if no additional input symbols can be recovered from the first set of output symbols and an adequate number of input symbols have not been recovered, then G additional output symbols are received and the G newly received output symbols are organized and processed as the original K plus A output symbols were organized and processed.
24. The method of claim 20 wherein the step of recovering input symbols associated with the output symbols in the decodable set is deferred while other output symbol processing is occurring.
25. The method of claim 24 wherein the step of recovering input symbols associated with the output symbols in the decodable set is deferred until it is determined that an adequate number of input symbols can be recovered from the output symbols.
26. The method of claim 24 wherein the step of recovering input symbols associated with the output symbols in the decodable set is deferred until it is determined that the input symbols are needed.