Error Correcting System and Device

The present invention relates to a system of and device for decoding and correcting many error-correctable codes (long distance code) at high speed in the correcting system.

Recording and reproducing of an optical disk or the like or the data transmission often employs data-coding and -decoding for correcting an error or errors included in a block consisting of many words such as 255 words by means of an error correcting code such as a BCH code or a Reed Solomon code.

In order to correct errors contained in many words by means of a BCH code or a Reed Solomon code, it is necessary to obtain coefficients of an error location polynomial on the basis of a syndrome generated from the received data.

Namely, this error location polynomial is a polynomial which has as a root a value corresponding with an error location. Thus, it is possible to calculate the location of the data containing an error by means of obtaining a coefficient of each term of an error location polynomial and by the Chien Algorithm.

This Chien Algorithm has a process of sequentially substituting elements except "0" of the Galois field used for correcting an error for an error location polynomial, obtaining the elements resulting in 0 which are as many as erroneous words and computing the error locations on these elements.

Accordingly, in an error correcting code for 4-word correction consisting of an extended Galois field (2.sup.8), if errors are caused at the locations corresponding with .alpha..sup.0, .alpha..sup.1, .alpha..sup.2 and .alpha..sup.2 5 4 of the GF (2.sup.8) elements .alpha..sup.0, .alpha..sup.1, . . . , .alpha..sup.2 5 4 except 0, the operation must be done for .alpha..sup.0 to .alpha..sup.2 5 4, that is, 255 times, so decoding has a shortcoming that it consumes too much time.

Heretofore, Peterson, Berlekamp Massey and Euclidean algorithms are well known as a system for obtaining coefficients of this type of error location polynomial. Yet, in the hardware arrangement, it is difficult to obtain practicable hardware due to very bulky arrangement. In the software arrangement, it has a problem of hard judgement, that is, slow processing speed.

An object of the present invention is to provide a system of and device for decoding the long distance code mentioned above at high speed and correcting an error when decoding the long distance code, the system and device as well as are suitable for hardware arrangement.

Another object of the present invention is to provide a system for reducing computing time for error locations and increasing decoding speed for an error correcting code much in case of decoding an error correcting code for correcting many words, such as a BCH code or a Reed Solomon code often employed in a recording and reproducing device or signal transmission.

The present invention provides an error correcting system for obtaining an error location polynomial from a syndrome or an error pattern from an error location and a syndrome when decoding a long distance code, said error correcting system comprising steps of:

setting a data word A.sub.(i+j-2) to each element qi, j of a matrix consisting of p rows and (p+1) columns [where 1.ltoreq.i.ltoreq.p, 1.ltoreq.j.ltoreq.p+1 and A.sub.0 to A.sub.2p-1 denote a syndrome or an error location];

performing left side fundamental transformation over said matrix; and

obtaining said coefficient of each term of said polynomial.

The present invention provides also an error correcting device for obtaining a coefficient of each term of an error pattern of an error location polynomial from a syndrome when decoding a long distance code, said error correcting device comprising:

a memory (M.sub.i, j) for storing each data word A.sub.(i+j-2) corresponding to each element qi, j of a matrix consisting of p rows and (p+1) columns; and

a computing means (C) with Galois field connected to an input and output bus (B) of said memory.

The error correcting system and device according to the present invention can obtain solutions of a matrix not by the immediate operation but by transformation of a matrix and the operation of the data words composing the matrix. Accordingly, it has an excellent effect that the process of obtaining solutions is very simple and is very rapid without excessively burdening the operation unit.

In particularly, if the error correcting device is arranged to concurrently process the elements in each row by providing an operating means for each row, this device consumes shorter processing time.

The present invention further provides an error correcting system for obtaining values corresponding to n error locations from an error location polynomial in case of decoding an error correcting code for correcting a plurality of errors, said error correcting system comprising steps of:

adding n-1 values corresponding to n-1 error locations which are obtained from said error location polynomial to a coefficient which is obtained from said polynomial and forms an added value of n values corresponding to n error locations by means of a computing means;

obtaining n-1 values corresponding to n-1 error locations from said polynomial;

adding said n-1 values to a coefficient which is obtained from said polynomial and forms an added value of n values corresponding to n error locations; and

computing nth value corresponding to nth error location.

The error correcting system according to the present invention detects error locations less than correctable words n by 1 is number and computes the remaining 1 error location on the error locations and coefficients of an error location polynomial. Thus, an expected value of operation times is reduced to (n-1)/n on the operation of the conventional Chien Algorithm, so that an error correcting code can be decoded at high speed.

The present invention provides further an error correcting device for obtaining an error location polynomial from a syndrome or an error pattern from an error location and a syndrome when decoding a long distance code by steps of setting a data word A.sub.(i+j-2) to each element a.sub.i, j of a matrix consisting of p rows and (p+1) columns [where 1.ltoreq.i.ltoreq.p, 1.ltoreq.j.ltoreq.p+1 and A.sub.0 to A.sub.2p-1 denote a syndrome or an error location], performing left side fundamental transformation over said matrix, and obtaining a coefficient of said polynomial, said error correcting device comprising a computing means and a buffer register provided respectively in every row of a memory for respectively storing data words A.sub.(i+j-2) corresponding to each elements a.sub.i, j in matrix consisting of p rows and (p+1) columns so as to concurrently process data words contained in each column said buffer register being adapted for replacing data words with each other in each column.

The error correcting device according to the present invention is arranged to transform elements in each row concurrently, that is, one column as a block at a time by providing a computing means for each row without obtaining solutions of a matrix expression. Thus, it does not burden the arithmetic and logic unit too excessively and reduces the processing time remarkably.

FIGS. 1a-1d is a flowchart for obtaining coefficients of an error location polynomial by means of the error correcting system of the system invention;

FIGS. 2a-2b is a modified flowchart for obtaining an error pattern by means of the embodiment of the error correcting system of the present invention;

FIGS. 4, 5i, 5ii, 6i and 6ii are diagrams showing the embodiment of the error correcting device of the present invention;

FIGS. 7a-7d is a flowchart for obtaining coefficient of an error location polynomial by means of the error correcting device shown in FIG. 6;

FIGS. 8a-8c shows examples of an operation table;

FIG. 9 is a table showing the correspondence between the multiplication expression on a Galois field and the decimal expression;

FIGS. 10i-10ii is a diagram showing an error location detecting circuit according to the embodiment of the error correcting and decoding system;

FIG. 11 is a diagram showing the principle of an error correcting device of the present invention;

FIGS. 12i -12ii shows the embodiment of the error correcting and decoding device of the present invention; and

FIGS. 13 to 21 are flowcharts showing the processing operations.

The arrangement of the present invention is described on the basis of the embodiment which is applied to the Reed Solomon code of 256 original Galois field GF (2.sup.8) for correcting 4 words of a block consisting of 255 words, each of which consists of 8 bits.

The Reed Solomon code is decoded in accordance with the following five steps:

(1) obtaining a syndrome from the received data

(2) obtaining an error location polynomial from this syndrome

(3) obtaining an error location from this error location polynomial

(4) obtaining an error pattern from an error location

(5) correcting an error on the basis of the error location and the error pattern

The present invention provides a decoding system which obtains computation of an error location polynomial from the syndrome mentioned in (2) as well as that of an error pattern from the error location mentioned in (4) at high speed by means of the same processing system.

The operation described below (+denotes an addition, .times.denotes a multiplication and / denotes a division) means the operation of Galois field. In general, it is executed with reference to the table. As one example of the table, FIG. 8 illustates a part of the above-mentioned operation table formed modulo G.sub.(x) =x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1 on GF (2.sup.8). In addition, FIG. 8(a) denotes an addition table. FIG. 8(b) denotes a multiplication table. FIG. 8(c) denotes a division table, where the uppermost line is a dividend and the leftmost column is a divisor.

Assuming that each word value of the received data containing an error is r.sub.0 to r.sub.254, the received data R(x) is given by the following (1) expression:

The syndromes S.sub.0 to S.sub.7 generated from this received data are obtained by substituting .alpha..sup.1, .alpha..sup.2, . . . .alpha..sup.7 for x in that (1) expression: ##EQU1##

In case of the 4-word correction, assuming as V.sub.1 to V.sub.4 the elements .alpha..sup.0 to .alpha..sup.2 5 4 (hereinafter, referred to as an error location) of GF (2.sup.8) showing error locations, the error location polynomial .sigma.(x) is defined as follows: ##EQU2##

As mentioned above, V.sub.1 to V.sub.4 denote an error location, that is, a word location containing a error. They respectively correspond with a power of x in the (1) expression. In general, the word location expressing in decimal system is obtained with reference to a table. As an example of this table, FIG. 9 illustrates a part of a table showing the correspondence between the power expression of .alpha. formed modulo G.sub.(x) =x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1 on GF (2.sup.8), analogously to the operation table shown in FIG. 8.

According to this table, for instance, when V=1, .alpha..sup.0 .apprch.1 means the lowermost term of r.sub.254. When V=4, .alpha..sup.2 =4 means the term of r.sub.252.

Furthermore, this embodiment employs 8 types of syndromes S.sub.0 to S.sub.7. 8 unknowns expressing four error locations and four error patterns can be computed by means of these 8 types of syndromes. Yet, if the error patterns are obtained at first, it may become impossible to compute an error location in case of containing the same values, that is, the same error patterns. As a results, in general, an error location should be obtained at first.

In addition, this error location ranges from 0 to 254 (8 bits in binary system) since it is one of 255 word locations. As the error pattern, 255 types of patterns exist from "00000001" to "11111111". The error is corrected by adding this pattern to the word in which an error is detected.

The relation between each value of coefficients .sigma..sub.0 to .sigma..sub.3 in the (3) expression of the error location polynomial is estabilshed as follows: ##EQU3##

The (4) expression is made to be the following (5) expression by transposing the right side term to the left side and then transforming the matrix. ##EQU4##

.sigma..sub.0 to .sigma..sub.3 are obtained as shown in the following (7) by multiplying both sides of this (5) expression by a matrix A from the left hand and then transforming it to the following (6) expression: ##EQU5##

The matrix A by which both sides are multiplied for transforming the (5) expression into the (6) one has a right side value of 0, so that it may be any matrix. After all, what is required is to perform the left side fundamental transformation by which the matrix consisting of S.sub.0 to S.sub.7 shown in the (5) expression is transformed to the (6) expression.

This left side fundamental transformation will be concretely described below, assuming that the S.sub.0 to S.sub.7 values are 0, 15, 85, 115, 193, 115, 161 and 231.

The first term in the left side of the (5) expression is represented by the following (8) expression. ##EQU6##

At the first phase of transforming this (8) expression into the (6) one, the first column of the (8) expression is transformed into: ##EQU7## of the first column of the first term in the left side of the (6) expression.

Since the value in the first column and first row is 0, the first row must be replaced with the first column in any row havin any value except 0. Thus, the first row is replaced with the second row. The resulting expression is the following (9) expression: ##EQU8##

Next, in order to change the value 15 in the first column and first row to 1, there is performed the Galois field operation which means that the value in each column of the first row is divided by 15. The resulting expression is the following (10) one: ##EQU9##

Next, the values in the third and the fourth rows of the first column must be changed to 0. So, with regard to the third row, the values in the first row is multiplied by 85 and then the resulting ones are Galois field-added to respective values in the third row. With regard to the fourth row, the values in the first row is multiplied by 115 and then the resulting ones are Galois field-added to respective values in the fourth row. The resulting expression is the following (11) one: ##EQU10##

At the second phase of transforming the above-mentioned (8) expression into the (6) expression format, the second column of the (11) expression must be: ##EQU11## which is identical to the second column of the first term in the left side of the (6) expression. Like the same procedure with the above, the second row is multiplied by 15 and added to the first row. Next, the resulting values in the second row are multiplied by 87 and then are Galois field-added to respective values in the third row. Furthermore, the values in the second row are multiplied by 58 and are Galois field-added to respective values in the fourth row. The resulting expression is the following (12) one: ##EQU12##

Next, at the third phase of transforming the above-mentioned (8) expression into the (6) one, the third column of the (12) expression must be: ##EQU13## which is identical to the third column of the first term in the left side of the (6) expression. Like the first phase, the third row containing the value of 0 in the third column is replaced with the fourth row, resulting in: ##EQU14##

The third row is Galois field-divided by 101 in the third column and the resulting values in the third row are multiplied by 62 and then are Galois field-added to respective values in the first row. Further, the values in the third row are multiplied by 15 and then are Galois field-added to respective values in the second row. The resulting expression is the following (14) one: ##EQU15##

Next, at the final phase of transforming the above-mentioned (8) expression into the (6) expression, the fourth column of the (14) expression must be: ##EQU16## which is identical to the fourth column of the first term in the left side of the (6) expression. The fourth row is Galois field-divided by 101 in the fourth column. The resulting values in the fourth row are multiplied by 87 and then are Galois field-added to respective values in the first row. Furthermore, the resulting values therein are multiplied by 107 and then are Galois field-added to respective values in the second row. As a result, the following (15) expression: which is identical to the (6) expression can be obtained.

Accordingly, as described above with regard to the expression (6),

are obtained. These .sigma. values are susbstituted in the error location polynomial shown in the (3) expression, resulting in;

The roots of this (17) expression solved by the Chien Algorithm or the like mean the error locations. The roots of this case are;

As a result, as mentioned above, the terms r.sub.254, r.sub.253, r.sub.252 and r.sub.251 or the (1) expression are found to be errors.

As mentioned above, the error location is detected. Now, the method for detecting an error pattern, that is, a correct data pattern will be described. Y.sub.1 denotes an error pattern of an error location V.sub.1, Y.sub.2 denotes an error pattern of an error location V.sub.2. That is, the error locations V.sub.1, V.sub.2, V.sub.3 and V.sub.4 are respectively assumed to correspond with the error patterns Y.sub.1, Y.sub.2, Y.sub.3 and Y.sub.4.

In this case, there is provided the following relation among the error patterns Y.sub.1 to Y.sub.4, the error positions V.sub.1 to V.sub.4 and the syndromes S.sub.0 to S.sub.3 : ##EQU17##

Like the transformation from the (4) expression to the (5) one, the right side term of this (19) expression is transposed to the left side and then the transposed matrix is changed to another format, resulting in the following (20) expression: ##EQU18##

As the error locations, V.sub.1 =1, V.sub.2 =2, V.sub.3 =4, V.sub.4 =8, S.sub.0 =0, S.sub.1 =15, S.sub.2 =85 and S.sub.3 =115 are respectively substituted in the left-hand matrix in the left side of this (20) expression. Then, like the description of the (8) expression or the (15) one, the left side dundamental transformation is performed over the substituted matrix. As a result, it is transformed to the following (21) expression. ##EQU19##

According to the values of the fourth column, the error patterns Y.sub.1 to Y.sub.4 are assumed to have the following (22) expression:

Thus, all the error patterns are detected to be 1, so that error-caused words, that is, r.sub.254, r.sub.253, r.sub.252 and r.sub.251, are to be corrected by the pattern 1.

Moreover, this error pattern Y value is a value representing its error pattern in decimal number. The above-mentioned error pattern 1 can be corrected just by adding "00000001" to the words at error locations by the Galois field.

As an example of errors, assuming the error locations to be the last three terms, that is, the error patterns Y.sub.1 to Y.sub.3, the following (23) expression is; Error location . . . Error pattern ##EQU20##

When these values are substituted in the matrix in the left-hand matrix in the left side of the (5) expression, the expression corresponding with the above-mentioned (8) one results in the following (24) expression: ##EQU21##

At the first phase of transforming this (24) expression, the first column is transformed to be; ##EQU22## which is identical with the first column of the first term in the left side of the (6) expression. The resulting expression is the following (25) one: ##EQU23##

Next, the second column thereof is transformed to be; ##EQU24## The resulting expression is the following (26) one: ##EQU25##

Next, the third column thereof is transformed to be; ##EQU26## The resulting expression is the following (27) one: ##EQU27##

The fourth column of this (27) expression has all the values of 0 and .sigma..sub.3 does not exist. Thus, an error is identified to have been caused in three words.

When an error is caused in three words, the error location polynomial corresponding with the (3) expression is represented in the following (28) expression:

The relational expression between the coefficients and the syndromes S.sub.0 to S.sub.6 is transformed to be the following (29) expression: ##EQU28##

.sigma..sub.0 to .sigma..sub.2 can be obtained by performing left side fundamental transformation over this (29) expression. Yet, these values are obtained in the matrix consisting of three rows and four columns as shown in the upper left portion of the (27) expression. Namely, as shown in the values in the fourth column, those values are;

The error location polynomial is represented by the following (31) expression).

And, the roots of this expression indicating the error location are;

Next, these values are substituted in the (19) expression for obtaining the error pattern. The (19) expression results in; ##EQU29##

The error pattern can be obtained by solving this (33) expression. As the other means, the matrix in the left-hand matrix in the left side of the (33) expression is transformed into the following (34) expression and then the following (35) expression can be obtained by transforming the (34) expression using the method applied when the above-mentioned error positions are obtained. This (35) expression is used for obtaining the error patterns shown in the (36) expression. ##EQU30##

FIG. 1 is a flowchart for the operation procedure for obtaining an error location polynomial provided in case of extending the 4 words-correction as described above to the general t word(s)-correction.

In this flowchart, S.sub.0 to S.sub.2t-1 denote syndromes a.sub.i,j denote each element of the matrix shown in the following (40) expression. ##EQU31##

FIG. 1(a) shows the process for substituting the values of the syndromes S.sub.0 to S.sub.7 in the matrix; ##EQU32## of the first term in the left side of the (5) expression for each element a.sub.i,j. At the step [1], the element a.sub.i,j in the upper left of this matrix is specified. At the step [2], the syndrome containing a subscript of (i+j-2), that is, the syndrome S.sub.0 containing a subscript of (i+j-2)=(1+1-2)=0 is substituted for this element. At the step [3], the element a.sub.1,2 in the next column of the same row is specified. At the step [4], the number of elements in one row is assured to be less than, in this case, 5. Then, the program returns to the step [2], where the syndrome S.sub.1 is substituted for this element a.sub.1,2. Hereinafter, S.sub.2 to S.sub.4 are substituted for the elements, like the above, until the step [4] distinguishes that the substitution of syndromes for the elements is completed.

When the substitution for this row is completed, the judging result in the step [4] is y, so that at the step [4], the substitution for the next row, that is, the second row is performed from the elements a.sub.2,1 to a.sub.2,5 like the above. On completion of the substitution for a.sub.2,5, the substitution is performed for the third row. In such process, the syndromes in the above-mentioned [40] expression are substituted for all the elements in 5 rows and 4 columns. The resulting matrix at the step 1, that is, the matrix provided after completing the substitution for all the elements and substituting the numerical values shown in the (8) expression for the values of respective elements, is described in the following (42) expression: ##EQU33##

In addition, the subscript (i+j-2) of S to be set at the step [2] means the substitution of the same syndromes for the elements on a diagonal line.

FIG. 1(b) shows a flowchart for transforming the above-mentioned (42) expression to the following (43) expression corresponding with the (9) expression: ##EQU34##

At the step [7] shown in FIG. 1(b), the column number P is assumed as 1 so as to obtain [1000] of the first column. At the step [8], the row number is also assumed as 1 so as to specify the element a.sub.i,j. At the step [9], if the value of the element is 0, 1 is added to the row number at the step [10]. Then, at the step [11], the program looks for the row not having a value of 0 at the element of the first column in the range from the first row to the lowermost one.

If it finds the row not having a value of 0 at the element of the first column, the program goes to the step [12]. If the row number is any value except the initial value P=1, that is, if the element in the first row and first column has a value of 0, at the step [13], the subscript showing the row number of the element is assumed as 1 so as to specify the element in the first column of the row to be changed to the first row. Then, in order to change the rows with each other, at the step [14], the element a.sub.1,1 value is temporarily saved in a saving register d which includes storage capacity corresponding to one word. Further, the program substitutes for the element a.sub.1,1 the element a.sub.Lp,j in the first column of the row to be changed because of including the row number LP detected in the steps [9] to [11] and then moves the element a.sub.1,1 value saved in the saving register d to the element a.sub.Lp,j.

At the step [15], this process is carried out from the first to the last column as the number increases. As a result, the (42) expression leads to the .circle.3 state including the array of the (43) expression. Yet, if the value of the element a.sub.1,1 in the first column of the first row is not originally 0 as shown in the (43) expression, it is not necessary to change them. Accordingly, the program can go directly from the step [12] to the .circle.3 state.

At the steps [17] to [20] shown in FIG. 1(c), assuming as 1 the value of the element in the first column of the first row in the (43) expression, these steps process the division of respective element in the second column or later of this row by the element value in the first column of the first row. They consists of the flow for transforming the (43) expression into the above-mentioned (10) expression, which is again shown as a (44) expression: ##EQU35##

At the step [17], in order to specify the element in the second row, 1 is added to the row number P as the subscript showing the column. At the step [18], these elements are divided by the value of the element in the first column of the first row. This process continues until all the elements in this row are processed. As a result, the matrix shown in the (44) matrix is obtained.

The next steps [21] to [27] process each value in the first columns of the third and the fourth rows to be 0. The value in the first column of the third row is made to be 0 by respectively adding 85-fold element values in the first row to corresponding element values in the third row. Furthermore, the value in the first column of the fourth row is made to be 0 by respectively adding 115-fold element values in the first row to corresponding element values in the fourth row.

At the step [21], the element in the second column of the first row is specified. If i=P, it is unnecessary to perform the operation because this P row changes the value in this row into a desired value such as [1000]. Thus, in this case, the step [22] excludes the row. The step [23] processes the rows except that case.

The process of the step [23] is to multiply the value of the element in the ith column of the row P to be a desired value by the value in the Pth column of the Jth row and to add the element a.sub.i,j to the multiplied values. This process continues until the end of the row at the steps [24] and [25]. Upon completion of this process, the steps [26] and [27] perform the process of the next row.

As a result, in .circle.4 , the following (45) expression matrix, which has been already shown as the (11) expression, can be obtained: ##EQU36##

In order to process change of the next column to a predetermined value, for example, change of the second column to [0100], the next step [28] adds 1 to the number of the column and then returns it to the step [8] as long as the unprocessed row remains.

Furthermore, 2 denotes a route provided in case the process has already become unnecessary in the step [11], that is, in case there exist few errors.

The matrix obtained by completing all the process in the first half of the step [30] is; ##EQU37## which has been shown as the (15) expression.

In order to obtain coefficients of an error location polynomial from this matrix, the step [30] sets 0 as an initial value of a subscript of this coefficient .sigma..

If 1 is added to this subscript, it is made to be a column number holding this coefficient, so that the step [31] sequentially reads out the value in the final column P=t by the process of the steps [31] to [33].

In addition, the step [34] provides a coefficient of the highest order term in the error location polynomial. This coefficient is always 1, so that it needs no operation.

FIG. 2 is a flowchart for the process of obtaining an error pattern. This flowchart shows only the different processing steps from those shown in FIG. 1. The steps marked with the same step number with FIG. 1 respectively do the same process. Further, the steps marked with the step number of FIG. 1 plus 100 respectively do the process corresponding with that of FIG. 1.

FIG. 2(a) shows the process corresponding with FIG. 1(a). This process is to expand; ##EQU38## It is different from the process in FIG. 1 in the respect of substituting error locations V.sub.j.sup.i-1 for syndromes in the first column or the fourth column of the matrix in the step [2] and the syndromes S.sub.0 to S.sub.i for the fifth column.

The step [100] is a step for substituting the error location for each element. The step [103] is a step for substituting the syndromes S.sub.0 to S.sub.3 in the fifth column for the corresponding elements. The matrix in .circle.1 provided on completion of the process in FIG. 2(a) is shown in the following (51) expression: ##EQU39##

FIG. 2(b) corresponds with FIG. 1(d). The similar process to that in the step [7] or [27] shown in FIG. 1 has been executed over the matrix shown in the above-mentioned (51) expression, resulting in the matrix in the first half step .circle.4 ' of the step [128], which is shown as follows: ##EQU40##

As described above with regard to the (21) expression, the first row to the fourth row of this [52] expression respectively denote error patterns corresponding with the error locations Y.sub.1, Y.sub.2, Y.sub.3 and Y.sub.4. In this case, all the error patterns are 1, that is, "00000001", so that the errors can be corrected by adding this "00000001" to the data word to be decoded on the error location.

FIGS. 3 to 6 respectively show the arrangement of the device for executing the error correcting system of the present invention.

The arrangement shown in FIG. 3 is the similar one to the conventional error correcting device. A CPU 31, a RAM 32, a ROM 33 and an I/O port 34 are respectively connected on a bus 30. The CPU 31 reads out the program and the table saved in the ROM 3 and then stores them in the RAM 32 so as to process the Galois field operation on the program and the table. The syndrome obtained from the received data word is input at the I/O port 34 and processed by the CPU 31. Then, the error location and the error pattern are respectively output at this I/O port 34, by which the decoded data word are corrected.

The arrangement shown in FIG. 3 has a shortcoming that the operation consumes long time and thus the processing speed is slow, because the CPU processes the Galois field operation.

FIG. 4 shows the embodiment of the present invention which is designed to overcome the above-mentioned shortcoming. A CPU 41, a RAM 42, a ROM 43 and an I/O port 44 are respectively connected on a bus 40. Furthermore, in this invention, there is provided a Galois field arithmetic and logic unit 45 including a Galois field multiplier 45.sub.1 and a Galois field divider 45.sub.2. Thus, this arithmetic and logic unit 45 executes the Galois field operations in the steps [14], [18] and [23] shown in the flowchart of FIG. 1, which are hard to be processed by the CPU, so that the processing speed becomes faster.

FIG. 5 shows a device for executing the operation of the flowchart shown in FIG. 1 mainly by the transfer. There are connected on a bus 50 a divider 54 for executing the division in the step [18], an arithmetic unit 55 for executing the multiplication and the division in the step [23] and a saving register 56 required for changing the data words in the step [14]. Furthermore, this bus 50 connects a RAM 52, an I/O port 53 and a transfer control unit 51 including a CPU for mainly executing the transfer control of data.

The divider 54 and the arithmetic unit 55 correspond to the arithmetic and logic unit 45 shown in FIG. 4. The saving register 56 provides two pairs of storage means consisting of latches 561.sub.1, 561.sub.2 and three states-buffers 562.sub.1, 562.sub.2. This register 56 stores two data words to be replaced in respective latches 561.sub.1 and 561.sub.2 and then sequentially reads out them so as to replace these data words with each other.

FIG. 6 shows the embodiment of an error correcting device for processing a 4 rows and 5 columns-arranged, that is, t=4 matrix. This device is invented in consideration of the respect that the error correcting system of the present invention is processed on the basis of the rows of the matrix. It is comprised of a matrix storage unit 60, a data word-replacing unit 70, an arithmetic and logic unit 80 and a 0-detecting unit 90. These marks A to H enclosed in .quadrature. mean the gates.

The operation of this embodiment is described on the flowchart shown in FIG. 7, considering as an example the case of processing the following matrix [60] of the first term in the left side of the above-mentioned [5] expression. ##EQU41##

The registers (R in FIG. 6) shown in 4 rows and 5 columns format are used for saving the data words of the elements corresponding with the above-mentioned matrix. These registers a.sub.1,1 to a.sub.4,5 respectively correspond with the locations of the elements in the matrix of the data words to be saved.

The steps [201] to [213] shown in FIG. 7(a) process substitution of the matrix values for these registers. At the step [201], an input gate K is in a conducting state. At the step [202], an initial value is set to 1. Then, at the step [203], a syndrome S.sub.(i-1), that is, S.sub.0 are output on an input line 6.

Next, at the step [204], j is made identical to i, that is, 1 and the step [205] makes sure it is in the range of the row. Then, at the step [207], a subscript k is obtained and then the syndrome S.sub.0 is saved in the a.sub.j,k register at the step [208].

The values of the elements a.sub.1,2 and a.sub.2,1 in the (60) expression are both the syndrome S.sub.1 and the values of the elements a.sub.1,3, a.sub.2,2 and a.sub.3,1 are all the syndrome S.sub.2. Similarly, the same data word is substituted for elements on the oblique line till the syndrome S.sub.3 to S.sub.7, so that the process executed from the steps [201] to [208] selects the subscripts i and k of the register, a latch pulse is outputted to register for a.sub.i,k and then saves them in accordance with the process shown in the steps [204] to [208]. The process of the step [206] excludes the subscript generated to specify the element belonging to the row below the lowermost one.

The step [209] saves the syndrome S including a subscript plus 1 made at the step [212] in the element on the next oblique line by subtracting 1 from the row number and adding 1 to the column number. The steps [210], [211] and [213] exclude the selected subscript when there is no element to be specified by the subscript.

The steps [214] to [226] shown in FIG. 7(b) correspond to the process of FIG. 1(b). The steps [214] to [219] identifies whether the value of the data word is 0 or not. The steps [220] to [226] replace the rows with each other.

As an initial value, the step [214] sets 1 to the column number and the step [215] sets 1 to the row number so as to specify the register of a.sub.1,1. The step [216] activates a gate C and the step [217] sends the data word saved in this register to the 0-detector 90 and identifies whether the value is 0 or not.

If the value is 0, the step [218] adds 1 to the row number, the step [219] makes sure that this row number exists in the matrix and the program returns to the step [216], which, as mentioned above about the transformation from the (8) expression to the (9) one, finds the row where the value of the element specified by the step [215] does not contain 0.

The step [220] determines whether the row is to be replaced or not. If it is not to be done, the matrix shown in the (9) expression is directly generated in .circle.3 . If it is to be done, this matrix is generated through the process of the steps [221] to [226].

These steps [221] to [222] activates the gate F belonging to the P row and outputs a latch pulse to the replacing register R.sub.1. Further, they activate the gate F of the register in the LPth row and store the value of the register saving the data word to be replaced in this replacing register R.sub.1. The next steps [223] to [224] store the value of the element to be replaced in the replacing register R.sub.2 after outputting a latch pulse to R.sub.2. Then, the steps [225] to [226] return the data words stored in the replacing registers R.sub.1 and R.sub.2 to other registers for saving the elements. As a result, the matrix shown in the (9) expression can be obtained.

This process is concurrently done in all the registers for one row, so that the replacement of a row does not need processing time for each element in the row.

FIG. 7(c) is a flowchart for executing the process corresponding to that shown in FIG. 1(c). The step [227] switches a selector to supply the output of a reciprocal table 1/x to a multiplier x provided in each row and concurrently executes the division described in the step [19] of FIG. 1(c) for all the elements in one row. Then, the step [228] outputs a latch pulse to the registers for the pth row and writes the result into the original register.

The step [229] does the process of the step [22] shown in FIG. 1(c), that is, excludes the row in which the operation has already completed. Then, the steps [230] to [223] do the process corresponding with the [23] step, that is, outputs a latch pulse to registers in the ith row at the [233] step and transforms the (10) expression into the (11) one. Next, the step [234] specifies the next row and the step [235] makes sure the specified row exists in the matrix. This process is repeated for each row.

The gate B of the register a.sub.i,p is activated and then the value of the register is supplied to the arithmetic and logic unit 80. The selector 82 does switching to directly supply this value to one input terminals of the multipliers 83.sub.1 to 83.sub.5. The other input terminals of these multipliers receive the values saved in these registers applied from respective ones belonging to the i row through the gate E. Accordingly, the multiplication is concurrently done in each row. The resulting values are added to the values saved in respective registers supplied through the gate D and then are saved in respective registers in the ith row. In the final phase of this process, that is, 4, the matrix shown in the (11) expression is generated in each register of the matrix storage unit 60.

FIG. 7(d) corresponds with FIG. 1(d). The step [226] adds 1 to the column number. Then, the process of the step [215] or later is repeated. When the step [237] detects completion of the process of the last row, the above-mentioned matrix is generated in each register.

The process of the steps [238] to [242] shown in FIG. 7(d) is similar to that of the steps [30] to [34] shown in FIG. 1(d). Thus, this process is executed for sequentially obtaining coefficients of this error location polynomial. In addition, the coefficient of the term of the highest order in this error location polynomial is always 1, so that it is not always required to be computed, as mentioned above.

Moreover, the description about FIGS. 7 and 6 is directed to computation of coefficients of an error location polynomial. Yet, if, in the flow shown in FIG. 6(a), the data word to be stored in each register of the matrix storage unit 60 is assumed as a data word in the matrix of the first term in the left side of the (20) expression, an error pattern can be obtained by means of executing the identical process to that of obtaining the coefficients of the error location polynomial, as mentioned above.

The description mentioned above is relevant to a Reed Solomon code on GF (2.sup.8), but the present invention is not limited by the Galois field. Further, it is obvious that this invention may be applied to the arrangement employing another long distance code such as a 6 adjacent code as a correction code.

In addition, it is also obvious that the error correcting device of this invention may be applied to the inverted matrix.

Next, a description will be directed to the embodiment wherein the arrangement of the error correcting system of the invention employs a Reed Solomon SOLOMON code (mentioned above) for 4-word correction of the Galois field (2.sup.8). Namely the 4-word correction is executed over a received word train consisting of 2.sup.8 -1=255 received words r.sub.0, r.sub.1. . . , r.sub.254 including a parity. This invention improves the speed of the operation in the step (3) of the Reed Solomon code for obtaining an error location(s).

The received word train can be expressed in the polynomial shown below:

Thus, the syndromes S.sub.0 to S.sub.7 are obtained as follows: ##EQU42##

In case of the 4-word correction, assuming as V.sub.1 to V.sub.4 the elements .alpha..sup.0 to .alpha..sup.254 (hereinafter, referred to as an error location) of GF(2.sup.8) showing error locations, the error location polynomial .sigma.(x) is; ##EQU43## There is established the following relation between the coefficients .sigma..sub.3 to .sigma..sub.0 in respective terms shown in the expression (3): ##EQU44##

If even one of the syndromes S.sub.0 to S.sub.7 has a value except 0, the error location polynomial .sigma.(x) is computed on these syndromes and the expression by means of the Peterson, Berlekamp Massey an Euclidean algorisms so as to obtain the coefficients .sigma..sub.3 to .sigma..sub.0 of respective terms in the expression (3). The corresponding V.sub.1, V.sub.2, V.sub.3 and V.sub.4 have error locations, that is, any value within the elements .alpha..sup.0 to .alpha..sup.254 except 0 on the Galois field GF(2.sup.8).

If errors are caused in r.sub.0, r.sub.1 and r.sub.254, the V's have .alpha..sup.254, .alpha..sup.253 and .alpha..sup.0. As mentioned above, sequentially substitute the elements .alpha..sup.0 to .alpha..sup.254 except 0 on the Galois field GF(2.sup.8) for the error location polynomial .sigma.(x) and, when .alpha..sup.254, .alpha..sup.253 and .alpha..sup.0 are substituted therefor,

is given to each element as is understood from the expression (3). Thus, these .alpha. are proved to be error locations.

Then, the expression (2) is expanded to be; ##EQU45## Comparing this expression (5) with the expression (3), ##EQU46## is given. Thus, the expression (6) provides the following relation:

As a result, in case of the 4-word correction, the fourth error location can be obtained by these three error locations.

Accordingly, after the third error location is proved, it is not necessary to substitute the elements for the polynomial on the Chien Algorithm. If three error locations are detected at the outset of the received word train, the computing speed is remarkably increased.

Furthermore, if the error polynomial is transformed to; ##EQU47## which is a dual expression to the expression (2), it gives the following expression of;

Thus, the expression (8) can be used in place of the expression (7).

FIG. 10 is a diagram showing an embodiment of the circuit for obtaining error locations. This circuit if arranged to substitute the elements .alpha..sup.0, .alpha..sup.1, . . . for the error location polynomial .sigma.(x) in sequence for obtaining three error locations and compute the fourth error location on the expression (7).

As shown in the diagram, four multiplier units K.sub.4 to K.sub.1 for computing the first to the fourth terms (four-to one-order terms) of the expression (3), respectively include a selector 2, a register 3 and a multiplier 4 connected in a loop.

In this multiplier unit K.sub.3, if, at the outset of detecting error locations of a received data train, the coefficient .sigma..sub.3 of the error location polynomial .sigma.(x) is entered to the register 3.sub.3 through the selector 2.sub.3 and then latched, this register 3.sub.3 outputs ".sigma..sub.3 " as a value of the second term provided in case of substituting .alpha..sup.0 for .sigma.(x). Further, this ".sigma..sub.3 " is also supplied to the multiplier 4.sub.3 in which ".sigma..sub.3 " is multiplied by .alpha..sup.3. Then the resulting value ".sigma..sub.3 .alpha..sup.3 " is applied to the register 3.sub.3 through the selector 2.sub.3 switched after input of .sigma..sub.3.

When the clock signal supplied by the computer control unit 1 is applied to the register 3.sub.3, this register latches value ".sigma..sub.3 .alpha..sup.3 " supplied by the multiplier 4.sub.3 and outputs this value, that is, the second term for which ".alpha..sub.1 " is substituted, from the multiplier unit K.sub.3.

Like this multiplier unit K.sub.3, the other multiplier units K.sub.4, K.sub.2 and K.sub.1 respectively output the values provided when the elements .alpha..sup.0,.alpha..sup.1, . . . are substituted for the first, the third and the fourth terms of the expression (3) in sequence. The constant term (.sigma..sub.0) value is latched by the register 5 and thus is always output from this register 5.

Next, the adders A.sub.1 to A.sub.4 add the values output by the multiplier units K.sub.4 to K.sub.1 and the register 5, that is, the values of respective terms of the expression (3) output by a clock signal supplied by the computer control unit 1. Finally, the adder A.sub.4 outputs the value provided by substituting the elements .alpha..sup.0,.alpha..sup.1, . . . for the error location polynomial .alpha.(x) to an output control unit 6.

This output control unit 6 supplies a data valid signal when the value of the error location polynomial to be entered is "0" and also supplies a select signal to the selector 7. Furthermore, it outputs a strobe signal to a register 13 of a final error location generating circuit unit 10 mentioned below.

On the other hand, the fifth multiplier unit K.sub.5 has the arrangement which is similar to that of the upper first to fourth multiplier units K.sub.1 to K.sub.4. This multiplier unit K.sub.5, on receiving the clock signal output by the computer control unit 1, sequentially generates .alpha..sup.0,.alpha..sup.1, . . . indicating the locations of received words in the received word train as synchronized with the substituting operation for the error location polynomial .sigma.(x). It means that ".alpha..sup.0 =1" latched by the register 3.sub.5 is output through the selector 2.sub.5 and the values ".alpha..sup.1,.alpha..sup.2, . . . " provided by the multiplier 4.sub.5 are output in sequence.

The values indicating the locations of the received words, which are output from this fifth multiplier unit K.sub.5, are applied to the selector 7. This selector 7 supplies the values indicating the locations of the received words, that is, error locations V when it receives the select signal applied by the output control unit 6.

Furthermore, the values indicating the locations of the received words, output by the fifth multiplier unit K.sub.5, are supplied to the final error location generating circuit unit 10 in which these values are applied to the register 13 through the adder 11 and the selector 12.

This register 13 latches as an initial value the coefficient ".sigma..sub.3 " of the second term in the error location polynomial to be entered into the multiplier unit K.sub.3. This latched ".sigma..sub.3 " is applied to one of input terminals of the adder 11.

The register 13 performs latching operation by virtue of the strobe signal output by the output control unit 6 when an error location is detected. Namely, every time an error location is detected, the value indicating the location is latched in sequence as follows: ##EQU48## when the third error location is detected,

is latched and then is output as the fourth error location through the selector 7.

Under the process mentioned above, the error pattern is obtained on the computed error locations so as to correct the erroneous received words.

The embodiment mentioned above describes the present invention applied to a Reed Solomon code for 4-word correction on the Galois field GF(2.sup.8). Yet, this invention is not limited by the size of the Galois field or the number of errors to be corrected. Moreover, the similar processing can be done for a correcting code except the Reed Solomon code for obtaining an error location on the Chien Algorithm.

A description will be directed to the another embodiment of the error correcting device of this invention.

The operation processing described above can be executed for a unit consisting of each column in a matrix. The embodiment of this invention provides a device for rapid processing with each column as a unit by means of hardware arrangement.

The above-mentioned matrix consisting of 4 rows and 5 columns can be expressed as a general expression of the (61) expression shown below: ##EQU49##

In this matrix, if the element a.sub.1,1 in the first column is transformed to "1" and the elements a.sub.2,1, a.sub.3,1 and a.sub.4,1 therein are also transformed to "0", after the transformation, the values of respective elements a.sub.1,2 ', a.sub.2,2 ', a.sub.3,2 ' and a.sub.4,2 ' can be obtained by the following method:

FIG. 11 shows a principle of an operation circuit of the present invention for executing the operation shown in the above-mentioned (62) expression. Thus, the operations in the third to the fifth columns can be processed like the above.

Furthermore, the first column is processed to be; ##EQU50## As is obvious from the (6) expression shown above, in order to obtain an coefficient of an error location polynomial, the values in the first to the fourth columns must be processed to have a unit matrix format. Thus, these values are irrelevant to those saved in respective registers of the first to the fourth columns. Moreover, more efficient processing can be achieved using the previous values as will be described below. So, the values in the processed column including the first column do not need the rewriting process to the values mentioned above, for example, so that a concrete description will be directed to the processing of the second column.

The computing circuit is comprised of a multiplier M.sub.0 connected to a reciprocal generator D.sub.0 for generating a reciprocal of an input data word on one of the input terminals, multipliers M.sub.1 to M.sub.4 connected to the output terminal of the multiplier M.sub.0 on each one of their input terminals and adders A.sub.1 to A.sub.4 connected to the output terminals of these multipliers M.sub.1 to M.sub.4 on each one of their input terminals. The outer input terminals of these multiplier M.sub.0 and M.sub.1 to M.sub.4 and adders A.sub.1 to A.sub.4 receives the data words as described below.

In FIG. 11, .circle.1 denotes an input terminal of the reciprocal generator D.sub.0. .circle.2 , .circle.3 , .circle.5 , .circle.7 and .circle.9 respectively denote the other terminals of the multipliers M.sub.0 to M.sub.4. .circle.4 , .circle.6 , .circle.8 and .circle.10 respectively denote the other terminals of the adders A.sub.1 to A.sub.4. .circle.11 denotes the output terminal of the multiplier M.sub.0. .circle.12 to .circle.15 respectively denote the output terminals of the adders A.sub.1 to A.sub.4. In addition, for the convenience's sake, the marks indicating each element of the matrix shown above are identical to those indicating each register for saving an element.

With regard to the second column described above, the (62) expression must be transformed to give the first column the following values: ##EQU51## For realizing that, the following element data is required to be input to respective input terminals: ##EQU52##

As a result, the transformed data is output at each output terminals as follows: ##EQU53##

Namely, a.sub.1,2 /a.sub.1,1 is obtained by generating a reciprocal 1/a.sub.1,1 of the element a.sub.1,1 input from the terminal 1 in the reciprocal generator D.sub.0 and then multiplying the reciprocal by a value a.sub.1,2 of the element a.sub.1,2 input from the input terminal 1 in the multiplier M.sub.0. This is equal to the value of the element a.sub.1,2 in the row containing the element a.sub.1,1 to be given 1, that is, the first element of the (62) expression. Further, it is the resulting value of the operation a.sub.1,2 .div.a.sub.1,1 in the right side with regard to the elements a.sub.2,2, a.sub.3,2 and a.sub.4,2 of the (62) expression.

The multipliers M.sub.2 to M.sub.4 provides the resulting values obtained by multiplying each element value in the first column of each row containing the elements a.sub.2,2, a.sub.3,2 and a.sub.4,2 in the second to the fourth columns, that is, the element values a.sub.2,1, a.sub.3,1 and a.sub.4,1 to be given "0" by the value of a.sub.1,2 /a.sub.1,1. Then, the adders A.sub.2 to A.sub.4 respectively add the resulting values to the original values a.sub.2,2, a.sub.3,2 and a.sub.4,2. As a result, the transformation by the (62) expression is completed.

FIG. 12 shows an embodiment of the error correcting device of the present invention which is made by modifying the computing device shown in FIG. 11 to apply to the processing of a matrix consisting of 4 rows and 5 columns. This device is comprised of a matrix storage unit 10 consisting of registers arranged in 4 rows and 5 columns for saving data words for respective elements, a data word replacing unit 20 consisting of buffer registers R.sub.1, R.sub.2, each two provided in one column, an arithmetic and logic unit 30 as shown in FIG. 11 and a "0" detecting unit 40.

The matrix storage unit 10 consists of registers for saving respective elements of the following matrix as has been shown before in the (61) expression: ##EQU54## These registers are respectively named as a.sub.1,1 to a.sub.4,5, which correspond with the positions of the elements a.sub.1,1 to a.sub.4,5 saved therein.

The marks A to H enclosed in .quadrature. in this matrix storage 10 mean gates. All the gates with the same mark perform the same function. The gate A is an input side gate for saving a data word. The gate G is an output gate for outputting the processed data word. The functions of the other gates are described below.

The data word replacing unit 20 provides each two buffer registers in each column, for example, the buffer registers R.sub.11, R.sub.12 in the first column. They store the data words from the gate L of the registers for their territory and return the data words stored in them to the registers in their territorial column through the gate B or C.

The arithmetic and logic unit 30 includes the similar arrangement and function to that shown in FIG. 11. The computing elements corresponding with that in FIG. 11 are shown by the same mark. These computing elements execute the operation shown in FIG. 11 with regard to the data words sent from the gates H, I, J, K of respective registers of the matrix storage unit 10 and supply the results to respective registers through the gate D or E.

The 0-detecting circuit 40 is a circuit which distinguishes whether or not the data words from the gates F provided in the first to the fourth columns are "0".

The operation of the embodiment of the error correcting device for a long distance code of the present invention in FIG. 12 will be described with referennce to the case where the subject device is used for correcting an error in a matrix consisting of eight syndromes S.sub.0 to S.sub.7.

The flowchart consisting of the steps [101] to [113] steps shown in FIG. 13 describes the process of substituting the syndromes S.sub.0 to S.sub.7 for respective registers in the matrix storage unit 10 as shown in the first term in the left side of the (5) expression, that is, the (63) expression described below. ##EQU55##

The step [.PHI.] brings the gate A into the conducting state so as to allow the register selected by a latch signal to save a syndrome input from an input line 11. The step [102] sets an initial value of i to 1 and then the step [103] outputs a syndrome S.sub.(i-1), that is, S.sub.0 on an input line 11.

Next, the step [104] sets a column number j to a value which is identical to the i (in this case, 1) and the step [105] makes sure that j is equal or less than the range of rows t, in other words, number of errors to be corrected as is obvious from the (6) expression. Then, the step [107] obtains a subscript indicating a column number and supplies a latch signal to the a.sub.j,k register (in this case, a.sub.1,1), so that the syndrome S.sub.0 is saved in the register a.sub.1,1 in the step [108].

In the next step [109], as is obvious from the (63) expression, the values of the elements a.sub.1,2 and a.sub.2,1 both have the same syndrome S.sub.1 and the values of the elements a.sub.1,3, a.sub.2,2 and a.sub.3,1 have the same syndrome S.sub.2. Later, from the syndromes S.sub.3 to S.sub.7, the same data word is substituted for the elements on a oblique line. Thus, if -1 added to the subscript j indicating the row number and +1 is also added to the subscript k indicating the column number, the register in the upper right hand of the just-written one is specified as the next object to be written. Yet, there is no register in the upper right hand of the a.sub.1,1 register. If there is no actual register to be specified by the step [109], the step [110] checks the column number and the step [111] also checks the row number so as to exclude this specification by the step [109]. The next step [112] adds +1 to i and then returns to the step [103].

The step [103] supplies the syndrome S.sub.1 on the input line because of i=2. Then, the step [104] sets the row number j to the value of i, that is, 2 and the step [105] makes sure that j is less than the row value and then the column number k is set as i-j+1=2+1=1. The step [108] writes the syndrome S.sub.1 to the register a.sub.2,1 specified by these row and column numbers.

The next step [109] specifies the register a.sub.1,2 by subtracting 1 from the row number j and adding 1 to the column number k. According to these values of j and k, the program goes from the step [110] to the step [111] and then returns to the [108] in which the syndrome S.sub.1 is also written in this register a.sub.1,2.

The process described above is repeated until i becomes twice as large as the number of syndromes, that is, the number t in the range of the row as shown in the step [113]. By this process, the syndromes are written in respective registers a.sub.1,1 to a.sub.4,5 as shown in the (63) expression.

In the description stated below, the syndromes S.sub.0 to S.sub.7 are given concrete numerical values of 0, 15, 85, 115, 193, 115, 161 and 231 like the (8) expression, for better understanding of the description. The matrix given these numerical values is as follows: ##EQU56##

In order to obtain the coefficients .sigma..sub.0 to .sigma..sub.3 in an error position polynomial by performing left side fundamental transformation over this matrix, it is necessary to transform this (64) matrix into the (65) matrix shown below by means of the (6) and the (7) expressions as mentioned above. ##EQU57##

The flow shown in FIG. 14 means a routine which replaces the element value "0" with another element value except "0" within the same column when the element value to have the data word value of "1" is actually "0". Concretely, with regard to the above-mentioned (64) expression, it is a routine which replaces the first row with the second row containing a data word value except "0" because the data word value of a.sub.1,1 in the first column of the first row is "0".

The step [114] sets "1" as an initial value of a row number P to be processed. Then the step [115] causes the output gate F in the first column to be in the conducting state and checks the values of the elements a.sub.1,1, a.sub.2,1, a.sub.3,1 and a.sub.4,1 so as to output the data words from the registers a.sub.1,1 to a.sub.4,1 to the "0" detecting circuit 40.

In the step [116], the 0-detecting circuit 40 executes the "0" detecting process in FIG. 14 so as to check whether all elements contained in the first column are "0" or not and whether the element to have a value of "1" is "0" or not.

FIG. 17 is a flow chart for processing "0" detection. The step [201], at first, specifies the element a.sub.1,1 to have a value of "1" by making the row number LP identical to the column number P. The step [202] checks whether the element value is "0" or not.

In this embodiment, the element value is "0", so that the step [203] adds 1 to the row number LP to specify the element a.sub.2,1 in the next row. Then, the step [204] makes sure that this row is allowed to exist in the matrix. If so, the program returns to the step [202] which checks whether this element value is "0" or not. In this case, since this element a.sub.2,1 has a value of 15, the routine goes to the step [206].

If the step [204] judges that the row is not allowed to exist in the matrix, it means that there is no element having any value except "0" in this column. So, a flag Az is set to "1" and a flag z is also set to "1". The former indicates that all the elements in the checked row are "0" and the latter indicates that the element to have a value of "1" is "0".

As mentioned above, in this case, a.sub.2,1 is an element having a value except "0" and the relation between L and P is LP=2, P=1 and LP.noteq.L. Thus, the routine goes from the step [206] to [208], in which the flag Az is set to "0" to indicate that the element of the checked row has a value except "0" and the flag z is set to "1" to indicate that the element a.sub.1,1 to have a value of "1" is "0".

If the element to have a value of "1", that is, a.sub.p,p having the same column number P and row number LP does not have a value of "0", the routine goes from the steps [202] and [206] to the step [207], in which the flags Az and z are both set to "0" to indicate the element to have a value of "1" does not have a value of "0".

After those flags Az and z are set, the program returns to the routine shown in FIG. 14, in which the step [117] checks the flag Az. In this case, the element a.sub.1,1 is "0" and the element a.sub.2,1 is not "0". Thus, the flag Az is set to "0" and the flag z is set to "1", as mentioned above. Then, the routine goes from the steps [117] and [118] to the steps [119] to [124] in which a column in the matrix are replaced with another one, concretely, the first column is replaced with the second column.

Moreover, if the element values in the column being processed are all "0" and the flag Az is set to "1" in the step [116], the step [117] judges that no error exists or will be found in the process in the later steps. This routine finishes the process and goes to the step [132] or later shown in FIG. 16 which reads out coefficients of an error location polynomial. Furthermore, it the flag z is 1 in the step [118], it is not necessary to replace the rows with each other, so that the program exits from this routine at .circle.3 and goes to the step [125] shown in FIG. 15 as described later.

Of the steps [119] to [124] for replacing the rows, the step [119] reads out the data words from all the registers in the Pth row saving the data words of the elements to be replaced, in this case, the first row. The step [120] supplys a latch pulse to R.sub.1 and temporarily saves these data words in one buffer register R.sub.1 belonging to that row and then the step [121] reads out the data words from all the registers in the LPth row saving these data words of the elements to be replaced. The step [122] supplys a latch pulse to R.sub.2 and temporarily saves these data words in the other buffer register R.sub.2. Next, the step [123] causes the data B in the Pth row and the gate C in the LPth row to be conducted and then the step [124] supplies a latch signal to all the registers belonging to the first and the second (Pth and LPth) rows so as to make these registers store the data word in the replaced rows. This is the finish of the replacement or rows.

This replacement results in the following (66) expression formed by replacing the first row in the (64) expression with the second therein: ##EQU58##

The steps [125] to [129] in FIG. 15 consists of a routine which sequentially transforms the rows so as to bring the values in the first to the fourth rows to the following: ##EQU59##

With regard to the process of the first column being described, the step [125] sets the column number i=P+1=2 as an initial value of the column to be processed. Now, a concrete description will be directed to an operation for obtaining respective elements in the second to the fifth rows when the first column in the above-mentioned matrix is transformed to; ##EQU60##

The step [126] causes the gate H for the register corresponding with the element a.sub.1,1 in the first column to have a value of "1", the gate 1 for the register corresponding with the element a.sub.1,1, the gate K for the registers corresponding with the elements a.sub.2,1, a.sub.3,1 and a.sub.4,1 and the gate J for the registers corresponding with the elements a.sub.2,2, a.sub.3,2 and a.sub.4,2 to be conducted. Then this step supplies the values from these registers to an arithmetic and logic unit 30 in FIG. 12 corresponding with the computing circuit shown in FIG. 11 and also supplies the resulting values to those registers by causing an input side gate E for the register a.sub.1,2 and an input side gate D for the resisters a.sub.2,2, a.sub.3,2 and a.sub.4,2 to be conducted. Next, the Step [127] makes these registers save the resulting values by supplying a latch pulse to each register in j column.

Under the process of setting a value of the element a.sub.1,1 in the first column of the first row to "1" and values of the elements a.sub.2,1, a.sub.3,1 and a.sub.4,1 to "0", if the process in the second column finishes, that is, the step [127] finishes, the values saved in respective registers of the matrix storage unit 10 are shown below (67): ##EQU61##

It is to be noted that the syndromes saved in the registers a.sub.1,1 to a.sub.4,1 respectively corresponding with the elements a.sub.1,1 to a.sub.4,1 in the first column do not have the values modified as follows: ##EQU62## but they have the previous values.

In these values, the values in the second column have the values in the first column transformed to the above-mentioned values. For obtaining coefficients of an error location polynomial, what is required is just the values in the fifth column provided when the first to the fourth columns are transformed into a unit matrix and thus the values stored in the registers in the processed column are not used for obtaining coefficients of an error location polynomial, so that these values are not required to be modified. The embodiment of the present invention employs the values stored in these registers for efficient operation.

The next step [128] specifies the third column by adding 1 to the column number j for setting j=3 and the step [129] makes sure that this column is allowed to exist. Then, the program returns to the step [126] for processing the third column. The loop consisting of the steps [126] to [129] processes the second to the fifth columns by repeating this process four times, that is, the column number j=2 to j=5.

After the value of element a.sub.1,1 is set to "1" and the values of the elements a.sub.2,1, a.sub.3,1 and a.sub.4,1 are set to "0", the program exits from this step [129] to .circle.4 . At this time, the values saved in each register of the matrix storage unit 10 are as follows (68): ##EQU63##

Next, turning to the flowchart shown in FIG. 16, in the process from .circle.4 to the step [130], the number P of the column to be processed is made 2 by adding 1 thereto for changing the column to be processed from the first to the second column and this second column is transformed to; ##EQU64##

The step [131] makes sure that the column specified as the above has the column number which is equal or less than the error-correctable number which is equal or less than the error-correctable number t, that is, less than 5. Yet, in this case, the column to be processed is the second one, so that the program goes from .circle.5 to the step [115] shown in FIG. 14.

Since the process from the steps [115] to [129] is similar to that described before, the detailed description thereof is skipped. The following (69) expression shows the matrix obtained as a result of the step [129] wherein the element in the second column of the second row is set to "1", those elements of the first, the third and the fourth row are set to "0": ##EQU65##

In the step [130] following this step [129], the third column is transformed to; ##EQU66## like the above. The following (70) expression shows the resulting values of the elements. ##EQU67## Likewise, the fourth column is transformed to; ##EQU68## The following (71) expression shows the resulting values of the elements: ##EQU69##

As shown in this matrix, the coefficients .sigma..sub.0, .sigma..sub.1, .sigma..sub.2 and .sigma..sub.3 of an error location polynomial are proved to respectively have values of 64, 120, 54 and 15.

Moreover, in the (69) to (71) expressions, as mentioned when the first column is transformed to; ##EQU70## the actual resulting values are as follows: ##EQU71## though the numerical values in respective registers have not been rewritten.

Next, a description will be directed to the second operation of the embodiment of the present invention which can execute very rapid processing if a fewer errors are caused.

Assuming that the syndromes S.sub.0 to S.sub.7 are respectively set to 1, 2, 4, 8, 16, 32, 64 and 128 as a result of an error for one word, the (73) expression shown below corresponding to the (63) is changed to the following (74): ##EQU72##

The operation example described above transforms this (74) expression into the following (75) expression by means of the procedure mentioned above and then obtains the error number, 1, on the basis of the resulting matrix: ##EQU73##

The number of errors is determined on the ground that the second, the third and the fourth rows of the second column are all "0", so that the values in the third to the fifth columns are not required for seeking the number of errors.

Accordingly, at the time of finishing the transformation of the second column, if the values in the second to the fourth rows of the second column are decided to be "0", the operation is not required further, so that the operation may stop so as to reduce the operation times.

FIGS. 18 to 20 are flowcharts for the operation example for executing the process mentioned above. They correspond with the flowcharts shown in FIGS. 14 and 15. Saving syndromes shown in FIG. 13 and the modification of columns to be processed and the readout of coefficients of an error location polynomial are identical to those of the first operation example mentioned above. So, all the flowcharts of this operation example are shown in FIGS. 13, 18, 19, 20, 16 and 17, the last of which shows the process for detecting "0".

The elements in the matrix are saved in the corresponding registers in accordance with the flowchart shown in FIG. 13, but the description of this process is left out because it has been already described above.

FIG. 18 is a flowchart for replacing the rows with each other. It is identical to the flowchart shown in FIG. 14 for describing the operation example mentioned above. The steps [301] to [311] shown in FIG. 18 respectively correspond with the steps [114] to [124] shown in FIG. 14. The difference between FIG. 14 and FIG. 18 is only the routine returning to the step [115] at 5 as shown in FIG. 14. Thus, the detailed description about FIG. 18 is left out.

In addition, the routine at 5 returns to the step [312] shown in FIG. 19.

The steps [312] to [314] shown in FIG. 19 respectively correspond with the steps [125] to [127] in FIG. 15. As described before, the first column is transformed to; ##EQU74## since it is a basic column P. At this time, if the number of errors is 1, the second to the fourth rows of the second column are all "0". The step [315] judges whether or not the column number j of the column being processed is the next one of the basic column, that is, in this case, the second column and that the column is not one showing coefficients of an error location polynomial, that is, the fifth column. If these conditions are satisfied, the routine goes from .circle.6 to the step [318] shown in FIG. 10 which judges whether the process is to be continued or not.

The process executed in the steps [319] to [320] is identical to that in the steps [116] to [117] shown in FIG. 14. Yet, the step [318] modifies the column to be processed to be the second column next to the basic column P, that is, the first column.

The step [319] performs "0" detecting process in the step [201] shown in FIG. 17. The step [201] makes the row number LP identical to the column number P and checks the value of the element a.sub.2,2. If it is "0", the step [203] specifies the element a.sub.3,2 in the next row and judges if it actually exists. If it exists, the routine returns to the step [202]. It checks the value of the element a.sub.3,2. The value of the element a.sub.4,2 is also checked in the same process. If all these elements a.sub.2,2, a.sub.3,2 and a.sub.4,2 have a value of "0", the flags Az and z are both set to "1".

If there is only a single error, when the step [320] next to this step [319] checks the flag Az, it is set to "1". Thus, the routine branches to the step [328] which specifies the second column by adding 1 to the column number P. Then the steps [132] to [136] shown in FIG. 16 read out the coefficients of the error location polynominal. This is the finish of the process.

If all the elements a.sub.2,2, a.sub.3,2 and a.sub.4,2 do not have a value of "0", the steps [320] to [321] judge whether the element to have a value of "1" is "0" or not. If it is to be replaced with "1", the steps [322] to [327] replace the rows with each other. Then, the routine returns to the steps [316] shown in FIG. 19 at .circle.7 . In this step or later, the operation mentioned above is similarly executed.

In addition, the steps [322] to [327] are provided in place of the steps [119] to [124] shown in FIG. 14 because the steps returning from the step [131] shown in FIG. 16 through .circle.5 are changed to the steps [312] shown in FIG. 19.

Next, a description will be directed to the third operation example of the embodiment of the present invention which can execute more rapid operation than the above-mentioned opertion example if few erros are caused.

Assuming that the syndromes S.sub.0 to S.sub.7 are respectively 3, 10, 36, 136, 42, 200, 199 and 166, the matrix formed by substituting these syndromes for the (74) expression is shown in the following (77) expression. In addition, these syndromes contain two errors. ##EQU75##

As has been described in the previous operation example, for transforming the first column of this matrix into; ##EQU76## transorming only the second column results in the following (78) expression: ##EQU77##

This result shows the elements in the second to the fourth rows of the second column are value except "0", so that more than one error is proved to be caused. The processing of the third column following that of the second column results in transformation of the (78) to the (79) expression: ##EQU78##

When the transformation of the first to the third columns is completed, the second column can be transformed to; ##EQU79## Thus, the transformation of the third column results in the following (80) expression: ##EQU80##

Since the values in the third and the fourth rows of the third column of the (80) expression are all "0", there is no error in the third and the fourth rows and the number of errors is proved to be 2.

FIG. 21 is a flowchart corresponding to FIG. 19 relevant to the second operation example. All the flowcharts relevant to the third operation example are FIG. 13, FIG. 18, FIG. 21, FIG. 20, FIG. 16 and FIG. 17 showing "0" detecting process.

The step [312] in the flowchart shown in FIG. 19 corresponding with the second operating example specifies the processing of the column from next to that to be transformed into to last one (p+1 column); ##EQU81## On the other hand, in FIG. 21, the third operation example shown in FIG. 13 has the different steps [401] and [406]. The former fixes (p+1) the column, as the column to be processed specifies the first column the basic j column transformed and transforms pth column, and the latter changes the condition j>t+1 for finishing a loop in the step [317] shown in FIG. 19 into i>P.

The matrix to be entered into this step [401] is shown in the (77) expression, but it is shown again as the following (81) expression: ##EQU82##

The step [402] transforms the values in the second column in order to give the first column the following values; ##EQU83## The step [403] supplys a latch pulse to registers in P+1 column and results in the following (82) expression corresponding to the (78) expression: ##EQU84##

The step [404] checks whether the processing is to be finished or not and whether the replacement of rows is required or not by the "0" detecting process shown in FIG. 17 and then sets the flags Az and z.

In this case, since the values in the second to the fourth rows of the second column are any value except "0", the step [405] makes sure that the column to be processed exists by adding 1 to the column number and then returns to the step [402]. Next, for transforming the third column, the first column must be transformed to; ##EQU85## and the second column must be transformed to; ##EQU86## The transforming process mentioned above for these columns results in the (80) expression. Since the values in the third and the fourth rows in the third column are both "0", the number of errors is proved to be 2, so that this transformation may be finished.

The description mentioned above has been developed with regard to 4 word-correction employing a Reed Solomon code on GF(2.sup.8), but the present invention is not limited by the Galois field. Furthermore, it is obvious that this invention may be applied to the case of using as a correcting code the other long distance code such as a b adjacent code and correcting more words.