Systematic rate-independent Reed-Solomon erasure codes
View Patent ↗The present disclosure is directed to a system and method for encoding k input symbols, using a Reed-Solomon erasure correction code, into a longer stream of n output symbols for transmission over an erasure channel. The present disclosure is further directed to a system and method for recovering the original k input symbols from only (and any) k output symbols (out of the n output symbols) received over the erasure channel. A symbol is a generic data unit consisting of one or more bits that can be, for example, a packet. The systems and methods of the present disclosure provide for an adjustable code rate that can be readily adapted based on changing channel conditions without having to reconstruct the encoder/decoder. As a result, such an encoder/decoder can be referred to as rate-independent.
1. A transmit payload processor comprising: a segmentation module configured to segment a file into k source working symbols; a systematic, rate-independent Reed-Solomon (SR-RS) encoder configured to encode the k source working symbols into n output working symbols, wherein the SR-RS encoder comprises a first interpolating polynomial evaluator configured to evaluate a first interpolation polynomial, constructed from a first linear combination of basis polynomials, at n-k distinct locations that are different from k locations of the k source working symbols; and a packing module configured to pack the n output working symbols into output transmit symbols for transmission over an erasure channel, wherein the segmentation module, the SR-RS encoder and the packing module are each implemented at least in part using hardware.
2. The transmit payload processor of claim 1 , wherein the SR-RS encoder comprises:
a second interpolating polynomial evaluator configured to evaluate a second interpolation polynomial, constructed from a second linear combination of the same basis polynomials used by the first interpolating polynomial evaluator, at the n−k distinct locations.
3. The transmit payload processor of claim 2 , wherein the first linear combination of the basis polynomials is determined based on the k source working symbols, and the second linear combination of the same basis polynomials is determined based on a different set of k source working symbols.
4. The transmit payload processor of claim 2 , wherein the first interpolating polynomial evaluator and the second interpolating polynomial evaluator are configured to operate in parallel.
5. The transmit payload processor of claim 1 , wherein the first interpolating polynomial evaluator is configured to evaluate the first interpolation polynomial using the fast Walsh-Hadamard transform.
6. The transmit payload processor of claim 1 , wherein the first interpolating polynomial evaluator is configured to evaluate the first interpolation polynomial using the fast Fourier transform.
7. The transmit payload processor of claim 1 , wherein n is adjusted based on a change in a condition of the erasure channel.
8. The transmit payload processor of claim 1 , wherein n is adjusted based on a change in a condition of the erasure channel without having to reconstruct the SR-RS encoder.
9. A receive payload processor comprising:
an unpacking module configured to unpack k output working symbols from k output transmit symbols received over an erasure channel;
a systematic, rate-independent Reed-Solomon (SR-RS) decoder configured to recover k or less source working symbols from the k output working symbols, wherein the SR-RS decoder comprises a first interpolating polynomial evaluator configured to evaluate a first interpolation polynomial, constructed from a first linear combination of basis polynomials, at k or less distinct locations; and
a de-segmentation module configured to de-segment a file using the recovered k or less source working symbols, wherein the unpacking module, the SR-RS decoder and the de-segmentation module are each implemented at least in part using hardware.
10. The receive payload processor of claim 9 , wherein the SR-RS decoder comprises:
a second interpolating polynomial evaluator configured to evaluate a second interpolation polynomial, constructed from a second linear combination of the same basis polynomials used by the first interpolating polynomial evaluator, at the k or less distinct locations.
11. The receive payload processor of claim 10 , wherein the first linear combination of the basis polynomials is determined based on the k output working symbols, and the second linear combination of the same basis polynomials is determined based on a different set of k output working symbols.
12. The receive payload processor of claim 10 , wherein the first interpolating polynomial evaluator and the second interpolating polynomial evaluator are configured to operate in parallel.
13. The receive payload processor of claim 9 , wherein the first interpolating polynomial evaluator is configured to evaluate the first interpolation polynomial using the fast Walsh-Hadamard transform.
14. The receive payload processor of claim 9 , wherein the first interpolating polynomial evaluator is configured to evaluate the first interpolation polynomial using the fast Fourier transform.
15. The receive payload processor of 9 , wherein the receive payload processor is implemented in a desktop computer, a laptop computer, a tablet, a smart phone, or a set-top box.
16. A systematic, rate-independent Reed-Solomon (SR-RS) coding module comprising:
a basis polynomial generator configured to generate basis polynomials based on k locations;
a first interpolating polynomial evaluator configured to evaluate a first interpolation polynomial, constructed from a first linear combination of the basis polynomials, at a first set of one or more distinct locations that are different from the k locations, wherein a number of distinct locations in the first set is adjusted to adjust a code rate of the SR-RS coding module; and
a second interpolating polynomial evaluator configured to evaluate a second interpolation polynomial, constructed from a second linear combination of the basis polynomials, at a second set of one or more distinct locations that are different from the k locations, wherein a number of distinct locations in the second set is adjusted to adjust the code rate of the SR-RS coding module, wherein the basis polynomial generator, the first interpolating polynomial evaluator and the second interpolating polynomial evaluator are each implemented at least in part using hardware.
17. The SR-RS coding module of claim 16 , wherein the first linear combination of the basis polynomials is determined based on k symbols to be transmitted over an erasure channel, wherein the k locations correspond to the k symbols.
18. The SR-RS coding nodule of claim 16 , wherein the first interpolating polynomial evaluator and the second interpolating polynomial evaluator are configured to operate in parallel.
19. The SR-RS coding module of claim 16 , wherein the first interpolating polynomial evaluator is configured to evaluate the first interpolation polynomial using the fast Walsh-Hadamard transform.
20. The SR-RS coding module of claim 16 , wherein the SR-RS coding module is implemented in a desktop computer, a laptop computer, a tablet, a smart phone, or a set-top box.