Reed-Solomon code system employing k-bit serial techniques for e

Details Reed-Solomon code system employing k-bit serial techniques for e Reed-Solomon code system employing k-bit serial techniques for e

1997-03-28

1999-02-23

Baker, Stephen M.

Excavating

371 391, H03M 1300, H03M 1322

Patent

active

058752005

ABSTRACT:
Apparatus and methods are disclosed for providing an improved system for encoding and decoding of Reed-Solomon and related codes. The system employs a k-bit-serial shift register for encoding and residue generation. For decoding, a residue is generated as data is read. Single-burst errors are corrected in real time by a k-bit-serial burst trapping decoder that operates on this residue. Error cases greater than a single burst are corrected with a non-real-time firmware decoder, which retrieves the residue and converts it to a remainder, then converts the remainder to syndromes, and then attempts to compute error locations and values from the syndromes. In the preferred embodiment, a new low-order first, k-bit-serial, finite-field constant multiplier is employed within the burst trapping circuit. Also, code symbol sizes are supported that need not equal the information byte size. The implementor of the methods disclosed may choose time-efficient or space-efficient firmware for multiple-burst correction.

REFERENCES:
patent: 3811108 (1974-05-01), Howell
patent: 4099160 (1978-07-01), Flagg
patent: 4142174 (1979-02-01), Chen et al.
patent: 4162480 (1979-07-01), Berlekamp
patent: 4355391 (1982-10-01), Alsop IV
patent: 4410989 (1983-10-01), Berlekamp
patent: 4413399 (1983-11-01), Riggle et al.
patent: 4455655 (1984-06-01), Galen et al.
patent: 4494234 (1985-01-01), Patel
patent: 4525838 (1985-07-01), Patel
patent: 4566105 (1986-01-01), Oisel et al.
patent: 4567594 (1986-01-01), Deodhar
patent: 4584686 (1986-04-01), Fritze
patent: 4604750 (1986-08-01), Manton et al.
patent: 4633470 (1986-12-01), Welch et al.
patent: 4706250 (1987-11-01), Patel
patent: 4730321 (1988-03-01), Machado
patent: 4733396 (1988-03-01), Baldwin et al.
patent: 4769818 (1988-09-01), Mortimer
patent: 4777635 (1988-10-01), Glover
patent: 4782490 (1988-11-01), Tenengolts
patent: 4833678 (1989-05-01), Cohen
patent: 4833679 (1989-05-01), Anderson et al.
patent: 4839896 (1989-06-01), Glover et al.
patent: 4843607 (1989-06-01), Tong
patent: 4845713 (1989-07-01), Zook
patent: 4849975 (1989-07-01), Patel
patent: 4856003 (1989-08-01), Weng
patent: 4866716 (1989-09-01), Weng
patent: 4890287 (1989-12-01), Johnson et al.
patent: 4916702 (1990-04-01), Berlekamp
patent: 4975915 (1990-12-01), Sako et al.
patent: 4979173 (1990-12-01), Geldman et al.
patent: 5001715 (1991-03-01), Weng
patent: 5099482 (1992-03-01), Cameron
patent: 5107503 (1992-04-01), Riggle et al.
patent: 5107506 (1992-04-01), Weng et al.
patent: 5109385 (1992-04-01), Karp et al.
patent: 5136592 (1992-08-01), Weng
patent: 5267241 (1993-11-01), Kowal
patent: 5280488 (1994-01-01), Glover et al.
patent: 5659557 (1997-08-01), Glover et al.
Glover et al., Practical Error Correction for Engineers, Second Edition, Dec. 1988, Data Systems Technology Corp., pp. 11-13, 32-34, 89-90, 112-113, 129-134, 181-184, 186, 194-196, 242, 256-268, 270, 285, 296, 298, 350.
Blahut, "Transform Techniques for Error Control Codes", IBM Journal of R&D, vol. 23, No. 3, May 1989.
Heise et al., "Serial Implementation of b-adjacent Codes", IBM Technical Disclosure Bulletin, vol. 24, No. 5, Oct. 1981.
Bossen et al., "Serial Processing of Interleaved Codes", IBM Technical Disclosure Bulletin, vol. 17, No. 3, Aug. 1974.
Berlekamp, "Algebraic Codes for Improving the Reliability of Tape Storage", National Computer Conference, Dec. 1975, pp. 497-499.
Data Sheet for: "Advanced Burst Error Processor", Part No. Am95C94, Advanced Micro Devices, May, 1989.
Product Description for: "Low-Cost High Performance Error Correcting Code Chip", Part. No. NG-8250, Cirrus Logic, Inc., Jan. 1988.
Clark et al., Error Correction Coding for Digital Communications, Plenum Press, Dec. 1981, Chapter 5, pp. 181-225.
Berlekamp, "Bit-Serial Reed-Solomon Encoders", IEEE Transactions on Information Theory, vol. IT-28, No. 6, Nov. 1982, pp. 869-874.
Maki et al., "A VLSI Reed-Solomon Encoder: An Engineering Approach", IEEE Custom Integrated Circuits Conference, Dec. 1986, pp. 177-181.
Beth et al., "Architectures for Exponentiation in GF(2* *n)", Advances in Cryptology-CRYPTO Dec. 1986 Proceedings, Springer-Verlag, pp. 302-310.
Peterson et al., Error Correcting Codes, MIT Press, Dec. 1972, pp. 277, 472-476.

Affiliated with

Also associated with

Rating

Reed-Solomon code system employing k-bit serial techniques for e does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reed-Solomon code system employing k-bit serial techniques for e, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-Solomon code system employing k-bit serial techniques for e will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-313228