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.
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 xcex1 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=2mxe2x88x921, assuming that roots xcex1 as primitive elements of a Galois field GM2m are xcex10, xcex11, . . . , xcex12mxe2x88x921. According to this code, m bits is one processing unit, i.e., one symbol. The amount of original information is (nxe2x88x922t) 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.
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 counted, and when the synchronous signal counter counts the predetermined number of synchronous byte suggestion signals, outputting the previously computed total number of bits.
According to a 6th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 3rd aspect, the bit error rate comprises: a determining unit, wherein plural assumable ranges of the error bit number are previously set, for determining a range including the number of the error bits which are counted by the error bit number counter while the predetermined number of synchronous byte suggestion signals are counted, in the set ranges; and an error rate output unit for previously computing bit error rates from values, each of which is arbitrarily selected from each of the ranges set in the determining unit, and the total number of bits in the input data, and outputting a bit error rate corresponding to the range determined by the determining unit form the previously computed bit error rates.
According to the 7th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 2nd aspect, the correction state monitor comprises an error symbol number counter for counting the number of the error bytes indicated by the error location, and the signal indicating the degree of error in the input data includes the total number of symbols in data which is input to the Reed-Solomon decoding apparatus while the synchronous signal counter counts the predetermined number of synchronous byte suggestion signals, and the number of the error symbols which are counted by the error symbol number counter while the synchronous byte suggestion signals are counted.
According to an 8th aspect of the present invention, in the Reed-Solomon decoding apparatus of any of the 1st and 3rd to 6th aspects, the correction state monitor comprise: an error symbol number counter for counting the number of the error bytes indicated by the error location; and a symbol error rate computer for computing a symbol error rate from the total number of symbols in data which is input to the Reed-Solomon decoding apparatus while a predetermined number of synchronous byte suggestion signals which are output in synchronization with synchronous signals of the input data, are counted, and the number of the error symbols which are counted by the error symbol number counter while the predetermined number of synchronous byte suggestion signals are counted, and the signal indicating the degree of error in the input data includes the symbol error rate.
According to a 9th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 8th aspect, the symbol error rate computer comprises: a divider for dividing the number of the error symbols by the total number of symbols in the input data.
According to a 10th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 9th aspect, the symbol error rate computer comprises: a constant output unit for previously computing the total number of symbols in data which is to be input to the Reed-Solomon decoding apparatus while the predetermined number of synchronous byte suggestion signals are counted, and when the synchronous signal counter counts the predetermined number of synchronous byte suggestion signals, outputting the previously computed total number of symbols.
According to an 11th aspect of the present invention, in the Reed-Solomon decoding apparatus of the 8th aspect, the symbol error rate computer comprises: a determining unit, wherein plural assumable ranges of the error symbol number are previously set, for determining a range including the number of the error symbols which are counted by the error symbol number counter while the predetermined number of synchronous byte suggestion signals are counted, in the set ranges; and an error range output unit for previously computing symbol error rates from values, each of which is arbitrarily selected from each of the ranges set in the determining unit, and the total number of symbols in the input data, and outputting a symbol error rate corresponding to the range determined by the determining unit from the previously computed symbol error rates.
According to a 12th aspect of the present invention, a method for controlling a Reed-Solomon decoding apparatus which performs error correction for input data with a Reed-Solomon code, comprises: a syndrome computing step of computing a syndrome from the input data; a Eucledean algorithm computing step of computing an error location polynomial and an error evaluation polynomial using the syndrome; an error location computing step of computing an error location indicating an error byte in the input data from the error location polynomial and the error evaluation polynomial; an error magnitude computing step of computing an error magnitude indicating an error bit among bits constituting the error byte indicated by the error location by using the error location polynomial and the error evaluation polynomial; an error correcting step of correcting the input data using the error location and the error magnitude; and a correction state montiroing step of monitoring the Eucledean algorithm computing step, and the error location computing step, and the error magnitude computing step, generating a signal indicating the presence or absence of a process error in each step, and generating a signal indicating the degree of error in the input data, from the error location and the error magnitude.
According to a 13th aspect of the present invention, in the Reed-Solomon decoding apparatus control method of the 12th aspect, the correction state monitoring step comprises: an error bit number counting step of counting the number of the error bits indicated by the error magnitude; a synchronous signal counting step of counting synchronous byte suggestion signals which are output in synchronization with synchronous signals of the input data; and a bit error rate computing step of 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 in the error bit number counting step, while a predetermined number of the synchronous byte suggestion signals are counted in the synchronous signal counting step, and the signal indicating the degree of error in the input data includes the bit error rate.
According to a 14th aspect of the present invention, in the Reed-Solomon decoding apparatus control method of the 13th aspect, the bit error rate computing step comprises: a determining step of previously set plural assumable ranges of the error bit number, and determining a range including the number of the error bits which are counted in the error bit number counting step while the predetermined number of synchronous byte suggestion signals are counted, in the set ranges; and an error rate outputting step of previously computing bit error rates from values, each of which is arbitrarily selected from each of the ranges set in the determining step, and the total number of bits in the input data, and when a range is determined in the determining step, outputting a bit error rate corresponding to the determined range from the previously computed bit error rates. According to a 15th aspect of the present invention, in the Reed-Solomon decoding apparatus control method of any of the 12th to 14th aspects, the correction state monitoring step comprises: an error symbol number counting step of counting the number of the error bytes indicated by the error location; and a symbol error rate computing step of computing a symbol error rate from the total number of symbols in data which is input to the Reed-Solomon decoding apparatus while a predetermined number of synchronous byte suggestion signals which are output in synchronization with synchronous signals of the input data, are counted, and the number of the error symbols counted in the error symbol number counting step while the predetermined number of synchronous byte suggestion signals are counted, and the signal indicating the degree of error in the input data includes the symbol error rate.
According to a 16th aspect of the present invention, in the Reed-Solomon decoding apparatus control method of the 15th aspect, the symbol error rate computing step comprises: a determining step of previously setting plural assumable ranges of the error symbol number, and determining a range including the number of the error symbols counted in the error symbol number counting step while the predetermined number of synchronous byte suggestion signals are counted, in the set ranges; and an error rate outputting step of previously computing symbol error rates from values, each of which is arbitrarily selected from each of the ranges set in the determining step, and the total number of symbols in the input data, and when a range is determined in the determining step, outputting a symbol error rate corresponding to the determine range, from the previously computed symbol error rates.
According to a 17th aspect of the present invention, in a computer-readable storage medium storing a code of a program for controlling a Reed-Solomon decoding apparatus which performs error correction for input data with a Reed-Solomon code, the code of the program includes: a code of a syndrome computing step of computing a syndrome from the input data; a code of a Eucledean algorithm computing step of computing an error location polynomial and an error evaluation polynomial using the syndrome; a code of an error location computing step of computing an error location, indicating an error byte in the input data, from the error location polynomial and the error evaluation polynomial; a code of an error magnitude computing step of computing an error magnitude indicating an error bit among bits constituting the error byte indicated by the error location; a code of an error correcting step of correcting the input data using the error location and the error magnitude; and a code of a correction state monitoring step of monitoring the Eucledean algorithm computing step, the error location computing step, and the error magnitude computing step, generating a signal indicating the presence or absence of a process error in each step, and generating a signal indicating a degree of error in the input data from the error location and the error magnitude.
USPTO Backgrounds
USPTO Backgrounds