Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-10
2003-04-22
Decady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06553537
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an apparatus for decoding a multiple error correcting Reed-Solomon code, i.e., a Reed-Solomon decoding apparatus, and a method for controlling the Reed-Solomon decoding apparatus.
BACKGROUND OF THE INVENTION
As codes which enable multiple error correction for storage information in various mass storages, transmission information in high-speed communication and the like, Reed-Solomon codes are widely known.
The Reed-Solomon code is a code on the Galois field which contains roots &agr; of W(z) (primitive polynomial)=0 as primitive elements, and is known as one of block error correcting codes. Here, consider a Reed-Solomon code of a code length n=2
m−
1, assuming that roots &agr; as primitive elements of a Galois field GM
2m
are &agr;
0
, &agr;
1
, . . . , &agr;
2
m
−1. According to this code, m bits is one processing unit, i.e., one symbol. The amount of original information is (n−2t) symbols. In the following description, suppose that m=8 and one symbol is represented as 8 bits, i.e., 1 byte. A received word of one packet comprises n pieces of symbols. When t=8, it is possible to correct errors of 8 symbols.
Generally, decoding of a Reed-Solomon code is performed in accordance with the following procedures, i.e., syndrome computing, computations of an error evaluation polynomial and an error location polynomial, computations of an error location and an error magnitude, and error correction. A detail of the decoding method is disclosed in Japanese Published Patent Application Hei. 10-135846.
Usually, error correction according to the Reed-Solomon code has a significantly high correction capability. Moreover, the correction process is performed by utilizing not only the Reed-Solomon code alone but also in combination with a convolution code and an interleaving process, or performed dually with the Reed-Solomon code itself as a product code, whereby an error free state having few errors is obtained on a real transmission path.
However, when the state of the transmission path is so bad as to exceed the error correction capability for any reason, there is a possibility of error correction not being performed at all or improper correction being performed in the normal Reed-Solomon decoding process.
Conventionally, in the Reed-Solomon decoding process, the maximum value of the number of error corrections is determined for a transmission path in the expected worst state, whereby the error free condition is usually realized. However, in the conventional Reed-Solomon decoding process, when the number of error corrections exceeds the maximum value and the error correction cannot be performed, the fact that the correction is impossible is merely notified by a flag. The flag notifying that the correction is impossible is usually transmitted to a monitor for monitoring an error at the error correction, different from LSI including an apparatus for performing the Reed-Solomon decoding process. However, the monitor is used only for a test at the manufacture of LSIs. Therefore, when the Reed-Solomon decoding process is performed in a practical system, there is no means for monitoring an error at the error correction.
Therefore, even when a state exceeding the error correction capability occurs frequently, processes for dealing with that state are not performed at all in the practical LSI performing the Reed-Solomon decoding process. Further, there is no index for notifying LSI whether the error correction is performed or not, and if performed, to what extent the error correction is correctly performed.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a Reed-Solomon decoding apparatus comprising a device for monitoring occurrence of errors beyond an error correction capability and a degree of error correction, a method for controlling the Reed-Solomon decoding apparatus, and a storage medium containing a program for performing the control.
Other objects and advantages of the present invention will become apparent from the detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the spirit and scope of the invention will be apparent to those of skill in the art from the detailed description.
A Reed-Solomon decoding apparatus according to a 1st aspect of the present invention comprises: a Reed-Solomon decoder for performing error correction for input data with a Reed-Solomon code; and a correction state monitor for detecting a process error in the error correction by the Reed-Solomon decoder and monitoring a degree of error in the input data, the Reed-Solomon decoder comprises: a syndrome computer for computing a syndrome from the input data; a Eucledean algorithm computer for computing an error location polynomial and an error evaluation polynomial using the syndrome; an error location computer for computing an error location indicating an error byte in the input data form the error location polynomial and the error evaluation polynomial; and an error corrector for correcting the input data by using the error location and an error magnitude indicating an error bit among bits constituting the error byte indicated by the error location, the error magnitude being computed by either of the Eucledean algorithm computer or the error location computer by using the error location polynomial and the error evaluation polynomial, and the correction state monitor monitors the Eucledean algorithm computer and the error location computer, generates a signal indicating the presence or absence of a process error in each of the Eucledean algorithm computer and the error location computer, and generates a signal indicating the degree of error in the input data from the error location and the error magnitude.
According to a 2nd aspect of the present invention, in the Reed-Solomon decoding apparatus of the 1st aspect, the correction state monitor comprises: an error bit number counter for counting the number of the error bits indicated by the error magnitude; and a synchronous signal counter for counting synchronous byte suggestion signals which are output in synchronization with synchronous signals of the input data, and the signal indicating the degree of error in the input data includes the total number of bits in data which is input to the Reed-Solomon decoding apparatus and the number of the error bits which are counted by the error bit number counter, while the synchronous signal counter counts a predetermined number of the synchronous byte suggestion signals.
According to a 3rd aspect of the present invention, in the Reed-Solomon decoding apparatus of the 1st aspect, the correction state monitor comprises: an error bit number counter for counting the number of the error bits indicated by the error magnitude; a synchronous signal counter for counting synchronous byte suggestion signals which are output in synchronization with synchronous signals of the input data; and a bit error rate computer for computing a bit error rate from the total number of bits in data which is input to the Reed-Solomon decoding apparatus and the number of the error bits which are counted by the error bit number counter, while the synchronous signal counter counts a predetermined number of synchronous byte suggestion signals, and the signal indicating the degree of error in the input data includes the bit error rate.
According to a 4th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 3rd aspect, the bit error rate computer comprises: a divider for dividing the number of the error bits by the total number of bits in the input data.
According to a 5th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 4th aspect, the bit error rate computer comprises: a constant output unit for previously computing the total number of bits in data which is to be input to the Reed-Solomon decoding apparatus while the predetermined number of synchronous byte suggestion signals are counte
De'cady Albert
Dooley Matthew C.
Matsushita Electric - Industrial Co., Ltd.
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Reed-Solomon decoding apparatus and control method therefor 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 decoding apparatus and control method therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-Solomon decoding apparatus and control method therefor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3107096