Error Correction System Including a Plurality of Processor Elements Which Are Capable of Performing Several Kinds of Processing for Error Correction in Parallel

1. Field of the Invention

This invention relates to an error correction system which detects and corrects errors in a storage medium, such as an optical disk, a magnetic disk or the like, or in a communication channel of satellite communications or the like, utilizing error correcting codes.

2. Description of the Prior Art

Recently, error correcting codes have been utilized more and more as means for increasing reliability in various kinds of digital systems, such as in a memory system using optical disks or the like. Among various kinds of error correcting codes which have the same code length and correcting capability, a Reed-Solomon code (hereinafter termed an "RS code") is the most important from the viewpoint of practical use, because it includes the feature of providing the smallest redundancy. Accordingly, the RS code has been widely utilized in satellite communications, optical disks, magnetic disks or the like.

An encoder/decoder or a decoder for performing processing of the RS code at a high speed may be relatively easily provided if the correcting capability of the RS code is as small as about 1 or 2.

However, if the correcting capability is increased, the size and control of the device becomes very complicated, and the calculation time needed for decoding processing is also increased.

In order to solve the above-described problems, an error correction method using systolic arrays, which is one of many parallel processing methods, has been proposed (e.g., the Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J71-A, No. 3, pp. 751-759, referred to as the IEICE Article, and which generally corresponds to copending U.S. patent application, Ser. No. 07/982,062).

According to this method, high-speed processing can be realized with a simple control and a simple circuit configuration for a code having a large correcting capability by performing all the processing necessary for encoding/decoding using the RS code with a configuration of systolic arrays having the same processing elements (hereinafter referred to as "PEs").

An example of the system configuration using the conventional systolic array configuration is shown in FIG. 7. An example of the circuit configuration of the PEs is shown in FIG. 8.

In this method, as shown in FIG. 7, a series of processing steps necessary for encoding/decoding using an RS code are performed in a sequential pipeline system using processing units 1-6 comprising the same PEs each having, for example, the configuration shown in FIG. 8.

In FIG. 8, there are shown a selector 11 controlled by signals S1 and S2, multipliers 12 and 13 on a Galois field, an adder 14 on a Galois field, and registers 15-19.

However, the conventional processing system, wherein all the processing necessary for encoding/decoding using the RS code is performed using the configuration of the systolic arrays having the same PEs, has a problem that respective processing units have different frequencies, that is, calculation loads, necessary for one processing step due to differences in the contents of the respective processing steps, such as the generation of a syndrome polynomial, the generation of an error locator polynomial or the like.

That is, when trying to perform all the processing steps necessary for encoding using the RS code by the systolic arrays, units which await processing are present within the system during the execution of the processing, because the calculation load differs for each processing unit. Hence, the overall system is not very efficient.

When correcting an erasure, a case may occur wherein the number "s" of erasures is "0" (no erasure is present) according to a codeword. In such a case, in the conventional method, (d-2t-1) PEs are always allocated for the generation of an erasure locator polynomial, where d represents a minimum distance and t represents the correcting capability). Hence, a delay time is needed for such an allocation.

It is an object of the present invention to provide an efficient error correction system, by removing elements which await processing due to any unevenness in the calculation load, in a system which executes error correction by parallel processing using a plurality of processing elements.

It is another object of the present invention to provide an error correction system which does not need a control unit for the entire system, by arranging the system so that each element can control the execution of its own processing while determining the operating state for the entire system, in a system which executes error correction by parallel processing using a plurality of processing elements.

It is still another object of the present invention to provide an efficient error correction system which eliminates wasteful processing for erasure correction, when erasure correction is unnecessary, in a system which executes error correction by parallel processing using a plurality of processing elements.

According to one aspect, the present invention which achieves these objectives relates to an error correction system comprising a plurality of processing elements capable of parallel operation while being connected to one another, each of which comprises detection means for detecting a condition of a respective element and conditions of elements having a higher priority than the respective element, processing means capable of executing each step in a series of processing steps for error correction, recognition means for recognizing processing step to be performed for data serving as an object of processing among the series of processing steps, and control means for controlling the processing means to execute the processing recognized by the recognition means when the detection means detects that all the elements having higher priority are incapable of performing processing and the respective element is capable of performing the processing.

According to another aspect, the present invention which achieves these objectives relates to an error correction system comprising a plurality of processing elements capable of parallel operation while being connected to one another, each of which comprises detection means for detecting a condition of a respective element and conditions of elements having a higher priority than the respective element, processing means capable of executing each step in a series of processing steps for error correction, indication means for indicating whether or not erasure correction is necessary for data serving as an object of processing, recognition means for recognizing a processing step to be performed for the data serving as the object of processing among the series of processing steps by skipping processing for erasure correction among the series of processing steps when the indication means indicates that erasure correction is unnecessary, and control means for controlling the processing means to execute the processing recognized by the recognition means when the detection means detects that all the elements having a higher priority are incapable of performing processing and the respective element is capable of performing processing.

According to still another aspect, the present invention which achieves these objectives relates to an error correction system comprising a plurality of processing elements capable of parallel operation while being connected to one another, each of which comprises detection means for detecting a condition of a respective element and conditions of elements having a higher priority than the respective element, processing means, capable of executing encoding of data and each step in a series of processing steps of decoding of the data, comprising recognition means for recognizing processing to be performed for data serving as an object of processing among the series of processing steps, and control means for controlling the processing means to execute the processing recognized by the recognition means when the detection means detects that all the elements having a higher priority are incapable of performing processing and the respective element is capable of performing processing.

Other objectives and advantages besides those discussed above will be apparent to those skilled in the art from the description of preferred embodiments of the invention which follows. In the description, reference is made to the accompanying drawings, which form a part thereof, and which illustrate examples of the invention. Such examples, however, are not exhaustive of the various embodiments of the invention, and therefore reference is made to the claims which follow the description for determining the scope of the invention.

FIG. 1 is a block diagram of the configuration of a first embodiment of the present invention;

FIG. 2 is a flowchart showing decoding processing for error correction in the first embodiment;

FIG. 3 is a block diagram of the configuration of a second embodiment of the present invention;

FIG. 4 is a flowchart showing decoding processing for error correction in the second embodiment;

FIG. 5 is a block diagram of the configuration of a third embodiment of the present invention;

FIG. 6 is a flowchart showing encoding and decoding processing for error correction in the third embodiment;

FIG. 7 is a block diagram of the configuration of a conventional decoder; and

FIG. 8 shows an example of the configuration of a processing element (PE).

An explanation will now be provided of preferred embodiments of the present invention with reference to the drawings.

RS encoding/decoding is usually performed according to the following procedure.

An RS code having a code length n.ltoreq.2.sup.m -1, an error correcting capability t and a minimum distance d is used, and a generator polynomial ##EQU1## is used, where m is a positive integer and .alpha. is a primitive element. A code is defined on GF (2.sup.m).

Encoding is performed according to the following procedure.

A polynomial P(x)=I(x).multidot.x.sup.d-1 mod G(x) is generated from a polynomial ##EQU2## having coefficients of information series (I.sub.k-1, I.sub.k-2, . . . , I.sub.0) and a generator polynomial G(x). Coefficients of P(x) provide check symbols, and deg P(x)<n-k.

Various methods of decoding RS codes encoded as described above are present. In the present embodiments, the following method is adopted.

An explanation will be provided for a case wherein s erasures are present in positions j1, j2, . . . , js, and r errors are present in positions k1, k2, . . . , kr other than the positions of erasures. A decoder knows the positions j1, j2, . . . , js, but does not know the positions k1, k2, . . . , kr.

The erasures are indicated by flags, and symbols of the positions of erasures are elements on GF (2.sup.m) as well as symbols of other positions. It is assumed that 2t+s+1.ltoreq.d, and r.ltoreq.t.

First, a syndrome polynomial ##EQU3## is generated from received words (R.sub.n-1, R.sub.n-2, . . . , R.sub.1, R.sub.0), where ##EQU4##

Subsequently, Y.sub.i =.alpha..sup.ji (i=1, 2, . . . , s) is defined for the s positions j1, j2, . . . , js of erasures, and an erasure position polynomial .lambda. (x) for obtaining the positions of erasures is generated: ##EQU5##

If the product S'(x) of the erasure-position polynomial and the syndrome polynomial obtained as described above is obtained, an error position polynomial .rho. (x) and an error evaluator polynomial .omega. (x) satisfying the following expression for the obtained S'(x) and x.sup.d-1 are uniquely determined except for differences in the constant coefficients. That is:

where C(x) is a polynomial on GF (2.sup.m). The above-described .omega. (x) and .rho. (x) can be obtained in the course of a Euclidean algorithm for obtaining the greatest common divisor (GCD) polynomial of

x=.alpha..sup.-n+i (i=1, . . . , n) is substituted for the polynomials .rho. (x), .omega. (x), formal differential .rho.' (x) of .rho. (x), erasure position polynomial .lambda. (x) and its formal differential.

It is possible to estimate that an error e.sub.n-i =.omega.(.alpha..sup.-n+i)/.rho.'(.alpha..sup.-n+i).multidot..lambda.(.alp ha..sup.-n+i)) is generated in the i-th symbol (R.sub.n-i) of the received word for i which makes the value .rho.(.alpha..sup.-n+i) of the error position polynomial obtained as described above "0".

It is also possible to estimate that an erasure E.sub.n-i =.omega.(.alpha..sup.-n+i)/(.lambda.'(.alpha..sup.-n+i).multidot.(.rho..su p.-n+i)) is present at the position of erasure.

Accordingly, an error can be corrected by obtaining R'.sub.n-i =R.sub.n-i +p.sub.n-i, where ##EQU6##

In the present embodiments, the above-described respective processing is executed with a unifirm load of processing units comprising the same PEs.

FIG. 1 is a block diagram of the configuration of processing in the first embodiment of the present invention wherein respective processing units are independently arranged in parallel.

As described in detail in the above-described IEICE Article, respective processing in the above-described error correction may be reduced to the repetition of a calculation (a.b+c.d), which may be realized using PEs 7 having the configuration shown in FIG. 8.

In the present embodiment, as in the above-described IEICE Article, each processing unit comprises the same PEs, and includes circuitry for outputting a token signal indicating whether the unit is in a busy state or in a waiting state, and a multiple data MD signal indicating a processing mode. These signals are input to other units as shown in FIG. 1.

The MD signal is allocated as the generation of a syndrome polynomial=1, the generation of an erasure position polynomial=2, the multiplication of an erasure position polynomial by a syndrome polynomial=3, the generation of an error position polynomial and an error evaluator polynomial=4, the generation of an error position and an error evaluator=5, and the execution of error correction=6 for each processing.

In the present embodiment, a priority order among units is determined for the execution of the above-described respective processing.

As shown in the flowchart of FIG. 2, which will be described later, if data input to a certain unit is started when units having a higher priority are busy and output busy signals, and a respective unit is in a waiting state, the unit generates the token busy signal, outputs a value incremented by one as the MD, and starts processing of a mode represented by the MD.

According to the above-described configuration, the MD signal is controlled by merely counting its output value, and a processing unit for each token may be simply configured by a ROM (read-only memory) which inputs the values of the tokens of units having a higher priority and outputs the value of the token of a respective unit.

An explanation will now be provided of error correction processing by each processing unit of the first embodiment having the above-described configuration with reference to the flowchart shown in FIG. 2.

At first, all tokens are in a waiting state, and MD=0.

If the input of the above-described received word (code word) starts with the unit having the priority 1, the unit starts processing of MD=1, that is, the generation of a syndrome polynomial S(x), and makes the token busy. At that time, the position of erasure is input to the unit having the priority 2. The unit having the priority 2 thereby outputs a busy signal, and sets MD=2.

The frequency of the calculation of the syndrome polynomial S(x) equals the code length N, and the frequency of the calculation of an erasure position polynomial .lambda. (x) equals the number S (N>S) of erasures. Hence, the unit having the priority 2 terminates processing before the unit having the priority 1, and sets the token in a waiting state.

When the input of the first codeword has ended and the second codeword has subsequently been input, the unit having the priority 1 continues to be busy in order to generate the syndrome polynomial of the second codeword. Hence, the output of the syndrome polynomial S(x) of the first codeword is transmitted to the unit having the priority 2 in a waiting state. As a result, the unit having the priority 2 performs the processing of MD=3, that is, the processing of multiplying the syndrome polynomial S(x) by the erasure position polynomial .lambda.(x) to obtain the product S'(x).

By subsequently performing the same operation in accordance with the flowchart shown in FIG. 2, processing of all the above-described error correction is efficiently executed.

As explained above, according to the present embodiment, it is possible to prevent an increase in the size of the circuit due to any unevenness in the allocation of processing, and to execute error correction processing more efficiently. Furthermore, by providing a priority order among units, a control unit for controlling the entire system becomes unnecessary. As a result, it is possible to configure an error correction system which may be easily provided as a VLSI (very-large-scale integrated circuit).

In the above-described first embodiment, a case may be present wherein the number s of erasures is "0" according to a codeword. In the conventional method having the systolic array configuration, however, the allocation of unnecessary PEs for the generation of an erasure position polynomial cannot be prevented even if the number s of erasures is "0". Hence, a wasteful processing time is inevitably present.

In order to solve such a problem, in addition to the configuration shown in FIG. 1, a configuration is adopted wherein it is possible to input a signal indicating the number s of erasures=0. FIG. 3 shows a block diagram of the configuration of processing in a second embodiment of the present invention.

An explanation will now be provided of a correction control when the configuration shown in FIG. 3 is adopted with reference to the flowchart shown in FIG. 4.

The processing in this case is different from the processing shown in FIG. 2 in that the input state of the s=0 signal is determined, and when the s=0 signal is present, the MD is incremented by two, from MD=1, and the corresponding processing is performed.

That is, as in the FIG. 2 processing, all tokens are at first in a waiting state, and MD=0.

If the input of the above-described received word (codeword) to the unit having the priority 1 is started, the unit starts the processing of MD=1, that is, the generation of a syndrome polynomial S(x), and makes the token busy. At that time, if an erasure is present, MD=1 is output, and the process proceeds to the same processing as in the first embodiment. In the present embodiment, however, when a signal indicating the number s of erasures=0 has been input, both the processing of the generation of an erasure position polynomial (MD=2) and the multiplication of the erasure position polynomial by a syndrome polynomial (MD=3) are skipped by outputting MD=3 which is a result of further incrementing the MD by two.

When the input of the first codeword has ended and the second code word has subsequently been input, the unit having the priority 1 continues to be busy. Hence, the output of the syndrome polynomial S(x) of the first codeword is transmitted to the unit having the priority 2. As a result, the unit having the priority 2 starts the processing of MD=4, that is, the generation of an error position polynomial .rho.(x) and an error evaluator polynomial .omega.(x).

By subsequently performing the same operation in accordance with the flowchart shown in FIG. 4, all the processing of the above-described error correction is efficiently executed.

It is thereby possible to prevent an increase in the size of the circuit due to any unevenness in the allocation of processing, and to execute processing more efficiently. At that time, since processing is automatically selected by inputting a signal indicating whether or not the number of erasures is "0", it is possible to utilize processing units more efficiently.

In the foregoing explanation, efficient decoding processing is made possible using a signal indicating that the number s of erasures is "0". However, the present invention is not limited to the above-described decoding processing, but may also be applied to encoding processing.

In such a case, as shown in FIG. 5, an input terminal for an encode signal for selecting whether each PE is to be used as a decoder or as an encoder is added to each PE in the block diagram of the configuration of the second embodiment shown in FIG. 3, and encoding processing is executed when an encode signal has been output.

Encoding processing/decoding processing is performed in accordance with the procedure shown in FIG. 6.

In the present embodiment, encoding processing is made possible in addition to the decoding processing shown in FIG. 4. It is determined whether encoding processing is to be executed or decoding processing is to be executed according to an encode signal. If an encode signal has been output, encoding processing is performed.

In this case, the unit having the highest priority among units whose tokens are in a waiting state executes encoding processing, and generates the above-described P(x).

In this case, however, since encoding processing ends with one processing step as described above, other units are not required to be linked. Hence, the MD is not incremented.

By subsequently performing the same operation in accordance with the flowchart shown in FIG. 6, all the processing of the above-described error correction is efficiently executed.

As explained above, according to the present embodiment, it is possible to prevent an increase in the size of the circuit due to any unevenness in the allocation of processing.

While the present invention has been described with respect to what is presently considered to be the preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, the invention is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. The scope of the following claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions.

Furthermore, since processing is automatically selected by inputting a signal (s=0) indicating whether or not the number of erasures is "0" and a signal (encode) indicating encoding, the present embodiment provides the effect that processing units can be utilized more efficiently than in a conventional method, for example, the method shown in the above-noted IEICE Article.

Furthermore, by providing a priority order among units, a control unit for controlling the entire system becomes unnecessary. As a result, it is possible to configure an error correction system which is more suitable for a VLSI.

As described above, according to the present invention, it is possible to prevent an increase in the size of the circuit due to any unevenness in the allocation of processing, and to execute processing more efficiently.

Furthermore, it is possible to utilize processing units more efficiently by automatically selecting processing by inputting a signal indicating whether or not the number of erasures is "0".

Moreover, by providing a priority order among units, a control unit for controlling the entire system becomes unnecessary. As a result, it is possible to configure an error correction system which is more suitable for a VLSI.