Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2005-03-15
2008-08-26
Lamarre, Guy J (Department: 2112)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S756000, C375S260000, C375S261000
Reexamination Certificate
active
07418649
ABSTRACT:
A high-rate Reed-Solomon erasure resilient codes (ERC) system and method for generating and implementing Reed-Solomon erasure-resilient codes for use in high-rate applications. High-rate applications are applications where the number of coded messages is significantly higher (such as an order of magnitude) than the number of original messages. The Reed-Solomon ERC system uses a scalar vector multiplication and addition technique and a direct inversion technique. The direct inversion technique uses specific generator matrices, including a modified Vandermonde Matrix and a Cauchy Matrix, to directly calculate an inverse of the sub-generator matrix of receiving ERC-coded messages. The scalar vector multiplication and addition technique generates high-rate Reed-Solomon codes and performs scalar vector multiplication and addition on the Galois Field for the Reed-Solomon erasure encoding/decoding operations. In effect, the Reed-Solomon codes are “tuned” for use in the high-rate environment.
REFERENCES:
patent: 6393065 (2002-05-01), Piret et al.
patent: 2007/0253496 (2007-11-01), Giannakis et al.
Byers, J., Luby, M., Mitzenmacher, M. and Rege, A., “A digital fountain approach to reliable distribution of bulk data”, inProceedings of ACM SIGCOMM'98, Vancouver, Canada, Sep. 1998.
Barg, A., and Forney, G. D., “Random codes: minimum distances and error exponents”, inIEEE Trans. on Inform Theory, vol. 48, No. 9, Sep. 2002, pp. 2568-2573.
Bloemer, J., Kalfane, M., Karpinski, M., Karp, R., Luby M., and Zuckerman, D., “An xor-based erasure-resilient coding scheme”,ICSI TR-95-048, Aug. 1995, Berkeley, CA.
Gao, S., “A new algorithm for decoding Reed-Solomon codes”, inCommunications, Information and Network Security(V. Bhargava, H. V. Poor, V. Tarokh and S. Yoon, Eds.), Kluwer Academic Publishers, 2003, pp. 55-68.
Grigoriev, D., Karpinski, M., and Singer, M., “Fast parallel alogorithms for sparse multivariate polynomial over finite fields”, inSIAM Journal on Computing, vol. 19, 1990, pp. 1059-1063.
Kaufman, I., “The inversion of the Vandermonde matrix and transformation to the Jordan canonical form”,IEEE Trans. On Automatic Control, vol. 14, No. 6, Dec. 1969, pp. 774-777.
Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., “Efficient Erasure Correcting Codes”, inIEEE Trans. on Information Theory, vol. 47, No. 2, pp. 569-584, Feb. 2001.
Luby, M., “LT Codes”, in43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
Rabin, M. O., “Efficient dispersal of information for security, load balancing, and fault tolerance”, inJ. ACM, vol. 36, No. 2, Apr. 1989, pp. 335-348.
Tan, W., and Cruz., J. R., “Analyzing low-density parity-check codes on partial response channels with erasures using density evolution”, inIEEE Trans. on Magnetics, vol. 40, No. 5, Sep. 2004, pp. 3411-3418.
Zhang, C., and Li, J., “Distributed hosting of web content with erasure coding and unequal weight assignment”, inProc. IEEE International Conf. on Multimedia Expo' 2004, Taipei, Taiwan, Jun. 2004.
Fischer Craig S.
Lamarre Guy J
Lyon & Harr L.L.P.
Microsoft Corporation
LandOfFree
Efficient implementation of reed-solomon erasure resilient... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient implementation of reed-solomon erasure resilient..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient implementation of reed-solomon erasure resilient... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4019395