Circuit for calculating error position polynomial at high speed

Details Circuit for calculating error position polynomial at high speed Circuit for calculating error position polynomial at high speed

1998-08-12

2001-09-04

Moise, Emmanuel L. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S784000, C714S785000

Reexamination Certificate

active

06286123

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a circuit for calculating an error position polynomial in an error correcting system using a Reed-Solomon code, and more particularly, to a circuit which can rapidly calculate an error position polynomial by using the Berlekamp-Massey iterative algorithm.
2. Description of the Related Art
In digital communication and storage systems, a Reed-Solomon (hereinafter, referred to as the RS) code for controlling an error has widely been used. In data coded to the RS code, an error is frequently generated during data transmission or reproduction. Since incorrect data is received due to this error, the data coded into the RS code needs to be error-corrected by RS decoding. In this RS decoding process, it is necessary to calculate an error position polynomial having an error position as a root. Examples of such error position polynomial calculation are described in papers, R. E. Blahut, “Theory and Practice of Error Control Code”, Addison-Wesley, 1983, and J. L. Massey, “Shift Register Synthesis and BCH Decoding” IEEE Transactions on Information Theory, Vol. IT-15, pp. 122-127, January, 1969. As a circuit using the Berlekamp-Massey algorithm (BMA) to calculate the error position, there is an example using a linear feedback shift register (LFSR) published by Massey, 1965. A discrepancy is calculated from a syndrome and an error position polynomial. If the discrepancy is 0, the previous error position polynomial is used. If it is not 0, the error position polynomial is again calculated. In order to again calculate the error position polynomial, a correction polynomial is given. That is, a new error position polynomial is calculated by using the correcting polynomial and the discrepancy. However, since such a circuit has a parallel structure, many multipliers are required to calculate the error position polynomial, and thus, the size of the circuit is increased. Moreover, since there is a long delay time in a circuit for calculating the discrepancy and a circuit for calculating the error position polynomial using the discrepancy, it is difficult to apply such a conventional circuit to a digital communication system which pursues a high-speed operation or to a storage system which has high storage capacity and requires high-speed access.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a circuit for calculating an error position polynomial which has a small circuit size and can rapidly calculate an error position polynomial.
To achieve the foregoing and other objects, the error position polynomial is calculated by using the Berlekamp-Massey iterative algorithm of a serial structure to simplify calculation and obtain a high-speed operation.


REFERENCES:
patent: 5463642 (1995-10-01), Gibbs et al.
patent: 5898708 (1999-04-01), Tateishi et al.
patent: 5983383 (1999-11-01), Wolf
patent: 5983389 (1999-11-01), Shimizu
patent: 6031875 (2000-02-01), Im

Affiliated with

Also associated with

Rating

Circuit for calculating error position polynomial at high speed does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Circuit for calculating error position polynomial at high speed, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit for calculating error position polynomial at high speed will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2498508