Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2007-05-15
2007-05-15
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000, C714S770000
Reexamination Certificate
active
11080093
ABSTRACT:
An improved and extended Reed-Solomon-like method for providing a redundancy of m≧3 is disclosed. A general expression of the codes is described, as well as a systematic criterion for proving correctness and finding decoding algorithms for values of m≧3. Examples of codes are given for m=3, 4, 5, based on primitive elements of a finite field of dimension N where N is 8, 16 or 32. A Horner's method and accumulator apparatus are described for XOR-efficient evaluation of polynomials with variable vector coefficients and constant sparse square matrix abscissa. A power balancing technique is described to further improve the XOR efficiency of the algorithms. XOR-efficient decoding methods are also described. A tower coordinate technique to efficiently carry out finite field multiplication or inversion for large dimension N forms a basis for one decoding method. Another decoding method uses a stored one-dimensional table of powers of α and Schur expressions to efficiently calculate the inverse of the square submatrices of the encoding matrix.
REFERENCES:
patent: 4142174 (1979-02-01), Chen et al.
patent: 4763332 (1988-08-01), Glover
patent: 4782490 (1988-11-01), Tenengolts
patent: 5285455 (1994-02-01), Tong et al.
patent: 5333143 (1994-07-01), Blaum et al.
patent: 5473620 (1995-12-01), Zook et al.
patent: 5579475 (1996-11-01), Blaum et al.
patent: 6012159 (2000-01-01), Fischer et al.
patent: 6557123 (2003-04-01), Wiencko et al.
patent: 6678855 (2004-01-01), Gemmell
patent: 6694479 (2004-02-01), Murthy et al.
patent: 2004/0117718 (2004-06-01), Manasse
Lacan et al., “Systematic MDS Erasure Codes Based on Vandermonde Matrices”, IEEE Communications Letters, vol. 8, No. 9, Sep. 2004, pp. 570-572.
1. M. Blaum, J. Brady, J. Bruck and J. Menon: “EVENODD: An Optimal Scheme for Tolerating Double Disk Failures in RAID Architectures”. IEEE, 1994, pp. 245-254. 1063-6897/94.
2. M. Blaum, J. Bruck and A. Vardy: “MDS Array Codes with Independent Parity Symbols.” IEEE Trans. Information Theory, vol. 47, No. 2, Mar. 1996, pp. 529-542.
3. M. Blaum, J. Brady, J. Bruck, J. Menon and A. Vardy: “The EVENODD Code and its Generalization: An Efficient Scheme for Tolerating Multiple Disk Failures in RAID Architectures”, Chapter 8, “High Performance Mass Storage and Parallel I/O: Technologies and Applications”, H. Jin, T. Cortes and R. Buyya, Eds., IEEE Computer Society Press and Wiley, 2001.
4. F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, pp. 317-331, North-Holland 1977.
5. J. Sankaran : “Reed Solomon Decoder: TMS320C64x Implementation”, Application Report SPRA686, Texas Instruments, Dec. 2000.
6. P. Scott, S. Tavares and L. Peppard, A Fast VLSI Multiplier for GF(2m), IEEE J. Selected Areas In Communications, vol. SAC-4, No. 1, 62-66, Jan. 1986.
7. H. Anvin, The mathematics of RAID-6, Dec. 1, 2004, http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf.
8. K. Aoki and K. Ohta, Fast Arithmetic Operations Over F2n for Software Implementation, SAC '97, 1997, www.scs.carleton.ca/˜sac97/program/FinalPapers/paper24.ps.
9. C. Ko and T. Acar, Montgomery multiplication in GF(2k), Designs, Codes and Cryptography, 14 (1998), 57-69, http://islab.oregonstate.edu/papers/j47mmugf.pdf.
10. Intel(R) 80333 I/O Processor Developer's Manual, pp. 409-488, Mar. 2005, http://download.intel.com/design/iio/manuals/30543201.pdf.
11. P. Hsieh, I. Chen, Y. Lin and S. Kuo, An XOR Based Reed-Solomon Algorithm for Advanced RAID Systems (Abstract), Defect and Fault Tolerance in VLSI Systems, 19th IEEE International Symposium on (DFT'04), Oct. 10-13, 2004, http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/proceedings/dft/&toc=comp/proceedings/dft/2004/2241/00/2241toc.xml&DOI=10.1109/DFT.2004.10
12. C. Park and Y. Han, A Practical Parity Scheme for Tolerating Triple Disk Failures in RAID Architectures, Advances in Computer Science—ASIAN 2000, pp. 58-68, J. He and M. Sato (Eds.), Springer 2000.
13. M. Cohen and C. Colbourn, Steiner Triple Systems as Multiple Erasure Correcting Codes in Large Disk Arrays, 2000 Int. Conf. on Performance, Computing and Communications 288-294, 2000.
14. C. Tau and T. Wang, Efficient Parity Placement Schemes for Tolerating Triple Disk Failures in RAID Archetecture, Proc. of the 17th Int. Conf. on Advanced Information Networking and Applications (AINA .03), 0-7695-1906-7/03, 2003.
Chen Yoshimura LLP
Tandberg Data Corporation
LandOfFree
Multiply redundant raid system and XOR-efficient method and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiply redundant raid system and XOR-efficient method and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiply redundant raid system and XOR-efficient method and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3814213