JP2553571B2 - Galois field arithmetic unit - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a code error check / correction device used for recording / reproducing data on / from a medium such as an optical disk.

2. Description of the Related Art In recent years, development of a data recording / reproducing device using an optical disc has been actively conducted. The optical disk memory can record a large amount of data as compared with the magnetic disk, but has a drawback that the raw error rate of the recording medium is high. Therefore, at the time of recording, a check symbol is added to the information symbol that is data to form a code word, and this code word is recorded as an error check correction code on the optical disk. Is generally used. A Reed-Solomon code with a minimum distance of d = 17 is recently receiving attention as such an error checking / correcting code. However, such a code with a large minimum distance is very complicated to decode and requires a long time or a large circuit, and it is mainstream to perform decoding by software such as a microcomputer at the expense of time except for some processing. Is. In such a Reed-Solomon code, after the parity calculation by encoding the data as the encoding process, the data is written to the medium together with the parity, and the decoding process, that is, the calculation of the syndrome, the estimation of the number of errors and the read data are performed. The coefficient of the error locator polynomial is calculated, the error position is calculated, and the error value is sequentially calculated. However, the number of correctable errors is (d-1) / 2 (normal correction) when the error position is unknown. ), When the error position is known, it is d-1 (erasure correction). Further, when only a part of the error position is known and there is an error whose position is unknown, the number of errors whose error position is known is t.
If the number is (d−t−1) / 2 + t, the number of errors can be corrected. However, conventionally, codes for such purposes are often used in the form of product codes by combining codes with short distances, and it is customary to perform error detection with one code and erasure correction with the other code. It was There is a method in the literature for obtaining the error amount when the error position has a known error and an unknown error, but it is known that the calculation amount increases considerably (on-decoding BCH code David Forney JR IEEE Trans. IT-11, pp549-55
7, 1965). According to this document, a method of calculating σ _{i, L} used when obtaining the modified syndrome T _k is introduced as a method for speeding up. However, the algorithm for obtaining the actual error amount is rather complicated, and it is easier to perform the erasure correction after obtaining the error position. FIGS. 3 and 4 show a conventional example by this method. The configuration of the conventional example will be described below with reference to the drawings. FIG. 3 shows a syndrome generation circuit, and FIG. 4 shows a flowchart of decoding by the Galois field arithmetic method used in the conventional correction processing. In FIG. 3, 1 is a logical product gate circuit that makes a total of 8 bits, 2 is an input changeover switch logic circuit, 3 to 8 are 0th to 5th 8-bit register circuits, and 18 is a 15th 8bits. Register circuits, 19 to 24 are 0th to 5th changeover switch logic circuits, 34 is a 15th switch logic circuit, 35 to 40 are Galois field multiplication circuits from α ⁰ to α ⁵ , and 50 is This is a Galois field multiplication circuit of α ¹⁵ . Further, 51 is a Galois field addition circuit (exclusive OR operation circuit). In this figure, the sixth to fourteenth circuit elements are omitted for description. Next, this operation will be described. In this example, the operation is performed on GF (2 ⁸ ). First, the received word sent from the demodulation circuit is sent to the syndrome circuit for decoding. The 8-bit register circuits 3 to 18 are previously set by the AND gate 1 and the input changeover switch logic circuit 2.
Initialize so that the content of is 0 element. Next, the received word of n symbols from the demodulator is input and the AND gate circuit 1
The logical product operation is performed via the above, and the obtained results are input to the Galois field addition circuit (exclusive OR operation circuit) 51 and the input changeover switch circuit 2 is connected to the Galois field multiplication circuits 35 to 35.
The input of n symbols is completed by adding the value fed back as the multiplication result of 50. After that, the register contents 3 to 18 are selected by the changeover switch logic circuits 19 to 34 to obtain the syndromes S ₀ to S ₁₅ . The number of error positions of L error positions known in advance to this syndrome X ₀ , X ₁ ... X _L-1
From the flowchart according to FIG.
Let σ _{j, j} = 1 under the condition that L and j ≧ i ≧ 0 and the variable whose subscript does not satisfy the above inequality sign on the right side are 0, and σ _{i, j} = σ _{i, j−1} × X _{j − 1} + σ _{i−1, j−1} as j
From 0 to L and i for each of the above j is changed under the above conditions to obtain σ _{0, L} ... σ _{L, L} by sequential calculation, and this σ _{i, L} and the syndrome generation circuit calculate From the syndrome At 0 to d-2-L, the corrected syndrome T _k is obtained and the error locator polynomial σ for the number t of unknown errors is obtained by the Euclidean decoding method in the same manner as the ordinary correction.
_{Calculate t} (Z) and use Chien's method to calculate the number of error positions X _L …… X
_{Find L + t-1} . The error amount can be obtained by calculating the erasure error of all the errors from all the error position numbers and the syndromes obtained. These calculations can be realized by the syndrome hardware and the microcomputer shown in FIG.

Problems to be Solved by the Invention However, with the above configuration, it is very difficult to increase the speed, and especially when the code distance is large, the amount of calculation becomes too large and real-time correction is practically impossible. Further, dedicated hardware can be provided to increase the speed, but there is a problem that the circuit amount increases too much and the practicability decreases.

In view of the above problems, the present invention provides a Galois field arithmetic unit that achieves both high speed and a small amount of hardware.

Means for Solving Problems To solve the above problems, the codeword is Galois field GF.
Generate a known L number of error positions from X ₀ to Y _L-1 and a syndrome from S ₀ to S _{d-2 of} an error-correcting linear code with a minimum distance d composed of (2 ^r ) elements Σ _{j, j} = 1 under the condition that j is 0 ≦ j ≦ L and j ≧ i ≧ 0 and the variable whose subscript does not satisfy the above inequality sign on the right side is 0. As follows, σ _{i, j} = σ _{i, j−1} × X _j−1 + σ _{i−1, i−1} and j
From 0 to L, and for each of the above j, i is changed under the above conditions to obtain a result, and σ _{i, L} obtained from the first sequential calculation means and the syndrome From the syndrome calculated by the generation circuit A second calculating means for calculating a modified syndrome T _k for k from 0 to d-2-L, and a modified syndrome T _k
Is treated like a syndrome in an error correction in which the number of error positions is unknown, and Euclidean decoding is performed to obtain an error locator polynomial for t errors whose number of error positions is unknown and an error evaluation polynomial of an intermediate value of the error amount to be obtained. Chie that obtains an error position from a third calculation means such as the method and an error position polynomial
From the fourth calculation means such as the method of n and the error amount intermediate value Y _{L, L} to be obtained by substituting t error position numbers obtained by the fourth calculation means into the error evaluation polynomial and the error locator polynomial. Y
_A fifth calculation means for calculating _{L + t−1, L} and Y _{j, 0} which is the total error amount for the L + t known and unknown error position numbers to be obtained are changed from j to L−1 to 0. Then, under the condition of i ≦ j, Then, Y _{j, j} is calculated and Y _{i, j} = Y _{i, j + 1} / (X _i + X _j ) on the right side is set, and Y _{j, j} of the calculation result on the left side are sequentially calculated. It comprises sixth sequential calculation means for obtaining a result by substituting _j into the above equation for obtaining Y _{j, j} by subtracting 1, or j is 0 ≦ j ≦ L
And when σ _{i, j} σ _{i, j} calculated by the calculation process is obtained with respect to j by said first calculating means to the original condition of j ≧ i ≧ 0, with the syndrome S _i, the intermediate result P _j , And if j = L and j ≧ i ≧ 0, then P ^L
Instead of And a seventh computing means for storing to obtain a modified syndrome T ₀ of k = 0 at, for k from 1 to d-2-L seeking modified syndrome T _k by the second calculating means, further L + t to be obtained instead of the sixth calculating means
The error amount Y _{j, 0} for the number of known and unknown error positions is changed by changing j from L-1 to 0, At Y _j, Y i on the right side by calculating the _{j, j = Y i, j} + 1 / (X i + X j) of the respective calculated results and the left side of the calculation results at Y _j, the sequentially j a _j 1 above minus Y
_The error amount is obtained by the eighth sequential calculation means that obtains the result by the procedure of substituting into the equation for obtaining _{j, j} .

The present invention provides a series of Galois field multiplication / division and addition by giving the position assumed to be an error after the calculation of the codeword's syndrome or the position having the error when the Reed-Solomon code is encoded or decoded by the above-mentioned procedure. It performs repetitive operations to perform normal correction and erasure correction during check code encoding or decoding. This procedure requires far fewer calculations than in the past, and therefore requires real-time processing. Can be applied, and the circuit amount is very small, so that this can be realized.

Example Hereinafter, a Galois field arithmetic unit according to an example of the present invention will be described with reference to the drawings. FIG. 1-a shows the first of the present invention.
FIG. 4 is a block diagram of an embodiment of FIG. Fig. 1-b is Fig. 1-a.
3 is a flow chart of a first calculation means of the first embodiment in FIG. Further, FIG. 1-c shows a flow chart of the second, third and fourth calculating means of the first embodiment in FIG. 1-a. Also, Fig. 1-d and Fig. 1-
e shows a flow chart of the fifth calculating means of the first embodiment in FIG. 1-a. In FIG. 1-a, 52 is a syndrome generation circuit which is the same as that shown in FIG. 3, and 53 is a memory circuit. Further, 54 is a Galois field arithmetic circuit, which executes a Galois field arithmetic operation at high speed by a microprogram. The first calculation means in FIG. 1-b calculates and stores σ _{i, j} used in the process of obtaining the correction syndrome T _k and the error value Y _{j, 0} . Further, in FIG. 1-c, 55 is a second calculation means, which is a part for obtaining a modified syndrome from σ _{i, L} and syndrome S _i , and 56 is an error locator polynomial σ from the modified syndrome.
It is a part of the third calculating means for obtaining _t (z) and the error evaluation polynomial η _t (z). 57 is the error locator polynomial σ
_This is a part of a fourth calculating means for obtaining the number of unknown error positions X _L ... X _{L + t-1} from _t (z). In addition, in FIG. 1-d,
58 is a part for substituting the number of error positions calculated in the error evaluation polynomial for calculating an intermediate value Y _{L, L} ... Y _{L, L + t−1} , and 59 is a part for calculating the error amount Y _{i, 0.} In the first half, the calculation is performed using the intermediate value between the error position number and the error amount. In FIG. 1-e, 59 is the latter half of the part for calculating the error amount Y _{i, 0,} and is calculated by σ _{i, j} and the syndrome S _i , and 60 is the flowchart of the part for finally correcting the error. Is. A first embodiment of the Galois field arithmetic method constructed as above will be described below with reference to FIGS. 1-a, 1-b, 1-c, 1-d, 1-e and The method will be described with reference to FIG. It is assumed that Y _{j, 0} which is the value of the error to be obtained is a total of 9 values of errors of J = 8 to 6 in which the error position is unknown and errors in which the error positions from j = 5 to j = 0 are known.
Let j be 0 ≦ j ≦ L, j ≧ i ≧ 0, and σ _{j, j} under the condition that the variable whose subscript does not satisfy the above inequality sign on the right side is 0.
= 1 and σ _{i, j} = σ _{i, j−1} × X _j−1 + σ _{i−1, j−1} and j is 0.
To L and changing i for each j under the above conditions _, the calculation procedure for σ _{i, j} is σ _{i, j} = σ _{i, j-1} × X _j-1 + σ _{i−1, j This} is performed as _−1, and σ _{i, j} obtained here is stored. This is σ
_In order to calculate _{i, j} , σ _{i, j-1} and σ _{one step} before
This is because the values of _{i−1, j−1} must be used, and this σ _{i, j} is also required when obtaining the error amount. Next, from σ _{i, L} and the syndrome obtained here, the modified syndrome is Is calculated for k from 0 to d-2-L, and this T _k
Is treated in the same manner as the syndrome in error correction in which the number of error positions is unknown, and the error locator polynomial σ for t errors of which the number of error positions is unknown in the Euclidean decoding method is treated.
An error evaluation polynomial η _t (n), which is an intermediate value of _t (z) and the error amount to be calculated, is calculated. After that, the error position obtained by the method of Chien for obtaining the number of error positions from the error position polynomial is substituted into the error position polynomial σ _t (z) and the error evaluation polynomial η _t (z) of the intermediate value of the error amount to be obtained. Thus, the intermediate value Y _{L + t−1, L} ... Y _{L, L} of the error amount is obtained, and the error amount is calculated in the flowchart of 59. The calculation formula of each value at this time is Y _5,5 = Y _8,6 / (X ₈ + X ₅ ) + Y _7,6 / (X ₇ + X ₅ ) + Y _6,6 / (X ₆ + X ₅ ) + P ₅ P ₅ = S ₅ + σ _4,5 × S ₄ + σ _3,5 × S ₃ + σ _2,5 × S ₂ + σ _1,5 × S ₁ + σ _0,5 × S ₀ σ _4,5 = X ₀ + X ₁ + X ₂ + X ₃ + X ₄ = 1 x X ₄ + σ _3,4 σ _3,5 = (X ₀ + X ₁ + X ₂ + X ₃ ) x X ₄ + (X ₀ + X ₁ + X ₂ ) x X ₃ + (X ₀ + X ₁ ) × X ₂ + X ₀ × X ₁ = σ _3,4 × X ₄ + σ _2,4 σ _2,5 = ((X ₀ + X ₁ + X ₂ ) × X ₃ + (X ₀ + X ₁ ) × X ₂ + X ₀ × X ₁ ) × X ₄ + ((X ₀ + X ₁ ) × X ₂ × X ₀ × X ₁ ) × X ₃ + X ₀ × X ₁ × X ₂ = σ _2,4 × X ₄ + X _1,4 σ _{1 , 5} = (((X ₀ + X ₁ ) × X ₂ + X ₀ × X ₁ ) × X ₃ + X ₀ × X ₁ × X ₂ ) × X ₄ + X ₀ × X ₁ × X ₂ × X ₃ = σ _{1, 4} x X ₄ + σ _0,4 σ _0,5 = X ₀ x X ₁ x X ₂ x X ₃ x X ₄ = σ _0,4 x X ₄ + ₀ Y _4,4 = Y _8,5 / (X ₈ + X ₄ ) + Y _7,5 / (X ₇ + X ₄ ) + Y _6,5 / (X ₆ + X ₄ ) + Y _5,5 / (X ₅ + X ₄ ) + P ₄ However, Y _8,5 = Y _8,6 / (X ₈ + X ₅ ) Y _7,5 = Y _7,6 / (X ₇ + X ₅ ) Y _6,5 = Y _6,6 / (X ₆ + X ₅ ) P ₄ = S ₄ + σ _{3, 4} × S ₃ + σ _2,4 × S ₂ + σ _1,4 × S ₁ + σ _0,4 × S ₀ σ _3,4 ＝ X ₀ ＋ X ₁ ＋ X ₂ ＋ X ₃ ＝ 1 × X ₃ ＋ σ _2,3 σ _{2, 4} = (X ₀ + X ₁ + X ₂ ) × X ₃ + (X ₀ + X ₁ ) × X ₂ + X ₀ × X ₁ = σ _2,3 × X ₃ + σ _1,3 σ _1,4 = ((X ₀ + X ₁ ) × X ₂ ＋ X ₀ × X ₁ ) × X ₃ ＋ X ₀ × X ₁ × X ₂ ＝ σ _1,3 × X ₃ ＋ σ _0,3 σ _0,4 ＝ X ₀ ＋ X ₁ ＋ X ₂ ＋ X ₃ ＝ σ _{0 , 3} × X ₃ +0 Y _3,3 = Y _8,4 / (X ₈ + X ₃ ) + Y _7,4 / (X ₇ + X ₃ ) + Y _6,4 / (X ₆ + X ₃ ) + Y _5,4 / ( _{X 5 + X 3) + Y} 4,4 / (X 4 + X 3) + P 3 where _{Y 8,4 = Y 8,5 / (X} 8 + X 4) Y 7,4 = Y 7,5 / (X 7 + X 4 ) Y _6,4 = Y _6,5 / (X ₆ + X ₄ ) Y _5,4 = Y _5,5 / (X ₅ + X ₄ ) P ₃ = S ₃ + σ _2,3 × S ₂ + σ _1,3 × _{S 1 + σ 0,3 × S 0} σ 2,3 = X 0 + X 1 + X 2 = 1 × X 2 + σ 1,2 σ 1,3 = (X 0 + X 1) × X 2 + X 0 × X 1 = _{1,2 × X 2 + σ 0,2 σ} 0,3 = X 0 × X 1 × X 2 = σ 0,2 × X 2 +0 Y 2,2 = Y 8,3 / (X 8 + X 2) + Y 7 _{, 3} / (X ₇ + X ₂ ) + Y _6,3 / (X ₆ + X ₂ ) + Y _5,3 / (X ₅ + X ₂ ) + Y _4,3 / (X ₄ + X ₂ ) + Y _3,3 / (X ₃ + X ₂ ) + P ₂ However, Y _8,3 = Y _8,4 / (X ₈ + X ₃ ) Y _7,3 = Y _7,4 / (X ₇ + X ₃ ) Y _6,3 = Y _6,4 / (X _{6 + X 3) Y 5,3 =} Y 5,4 / (X 5 + X 3) Y 4,3 = Y 4,4 / (X 4 + X 3) P 2 = S 2 + σ 1,2 × S 1 + σ 0 _{, 2} × S ₀ σ _1,2 = X ₀ + X ₁ = 1 × X ₁ + σ _0,1 σ _0,2 = X ₀ × X ₁ = σ _0,1 × X ₁ +0 Y _1,1 = Y _{8, 2} / (X ₈ + X ₁ ) + Y _7,2 / (X ₇ + X ₁ ) + Y _6,2 / (X ₆ + X ₁ ) + Y _5,2 / (X ₅ + X ₁ ) + Y _4,2 / (X ₄ + X _{1) + Y 3,2 / (X} 3 + X 1) + Y 2,2 / (X 2 + X 1) + P 1 where _{Y 8,2 = Y 8,3 / (X} 8 + X 2) Y 7,2 = Y 7 _{, 3 / (X 7 + X} 2) Y 6,2 = Y 6,3 / (X 6 + X 2) Y 5,2 = Y 5,3 / (X 5 _{X 2) Y 4,2 = Y 4,3} / (X 4 + X 2) Y 3,2 = Y 3,3 / (X 3 + X 2) P 1 = S 1 + σ 0,1 × S 0 σ 0, ₁ = X ₀ Y _0,0 = Y _8,1 / (X ₈ + X ₀ ) + Y _7,1 / (X ₇ + X ₀ ) + Y _6,1 / (X ₆ + X ₀ ) + Y _5,1 / (X ₅ + X ₀ ) + Y _4,1 / (X ₄ + X ₀ ) + Y _3,1 / (X ₃ + X ₀ ) + Y _2,1 / (X ₂ + X ₀ ) + Y _1,1 / (X ₁ + X ₀ ) + P ₀ However, Y _8,1 = Y _8,2 / (X ₈ + X ₁ ) Y _7,1 = Y _7,2 / (X ₇ + X ₁ ) Y _6,1 = Y _6,2 / (X ₆ + X ₁ ) Y _{5 , 1} = Y _5,2 / (X ₅ + X ₁ ) Y _4,1 = Y _4,2 / (X ₄ + X ₁ ) Y _3,1 = Y _3,2 / (X ₃ + X ₁ ) Y _2,1 = Y _2,2 / (X ₂ + X ₁ ) P ₀ = S ₀ Also, in the middle of calculation of the 0th error value Y _0,0 obtained here, the 1st to 8th other error values Y _{1 , 0} = Y _1,1 / (X ₁ + X ₀ ), Y _2,0 = Y _2,1 / (X ₂ +
X ₀ ), Y _3,0 = Y _3,1 / (X ₃ + X ₀ ), Y _4,0 = Y _4,1 / (X ₄
+ X ₀ ), Y _5,0 = Y _5,1 / (X ₅ + X ₀ ), Y _6,0 = Y _6,1 /
_{(X 6 + X 0),} Y 7,0 = Y 7,1 / (X 7 + X 0), Y 8,0 = Y 8,1
/ (X ₈ + X ₀ ) is obtained at the same time. Note that here I said. As described above, in order to obtain Y _{j, 0} , Y _{j, j} is calculated from j = L−1 to 0. When calculating the error amount, calculate Y _{j, j} Also when calculating according to the formula of Y, as in the calculation of σ _{i, j
i, j + 1} , that is, Y _{j, j} from the maximum value L−1 of _j to 0
The calculation result of Y _{i, j} = Y _{i, j + 1} / (X _i + X _j ), in which j is increased by 1 before the calculation process of 1, must be used. For this reason, when Y _{i.j + 1} / (X _i + X _j ) is calculated, it is always stored in the memory, and in the next process, the contents of the memory are read and the updated value is written again. convenient. Similarly, the newly obtained left side result Y _{j, j} is also written in the memory. When the calculation is continued and j = 0,
The memory stores Y _{j, 0,} that is, the amount of error to be obtained. In addition, when obtaining the error amount,
_{i, j} are read again and used for calculation. Next, a Galois field arithmetic unit according to a second embodiment of the present invention will be described with reference to the drawings. FIG. 2A is a block diagram of the second embodiment of the present invention. FIG. 2B is the second line in FIG. 2A.
9 is a flowchart of the first and seventh calculation means of the embodiment. 2C shows a flow chart of the second, third and fourth calculating means of the second embodiment in FIG. 2A, which is basically the same as that of FIG. 1C. However, in the flowchart part of 55, the corrected syndrome T ₀
The calculation of is not performed because it has already been completed. Further, FIG. 2D shows a flow chart of the fifth and eighth calculating means of the second embodiment in FIG. 2A. Fig. 2-
In a, 52 is a syndrome generation circuit which is the same as that shown in FIG. 3, and 53 is a memory circuit. Further, 54 is a Galois field arithmetic circuit, which executes a Galois field arithmetic operation at high speed by a microprogram. In FIG. 2B, the first and seventh calculation means are combined and applied, and
The σ _{i, j} calculated by the calculation means is retained in the register and multiplied by S _i to calculate and store the intermediate value P _j and a part T _{0 of the} corrected syndrome. Further, in FIG. 2C, the correction syndrome T ₁ ... T _dL-2 is performed in the same manner as in FIG. 1C.
And the number of error positions is unknown by 56 Euclidean decoding
An error locator polynomial σ _t (z) for each error and an error evaluation polynomial η _t (z) of an intermediate value of the error amount to be obtained are obtained. After that, the flowchart of substituting the error position obtained by the Chien method of 57 into the error locator polynomial σ _t (z) of FIG. 2D and the error evaluation polynomial η _t (z) of the intermediate value of the error amount to be obtained. By executing 58, the intermediate value Y of the error amount
_{L + t−1, L} ... Y _{L, L} is obtained and the error amount is calculated in the flowchart of 61. At 61 in FIG. 2D, the error value Y _{j, 0} is finally obtained from the intermediate value Pj and the number of error positions stored by the seventh calculating means in FIG. 1B. A second embodiment of the Galois field arithmetic method configured as described above will be described below with reference to FIGS. 2A, 2B, 2C, 2D and 3D.
The method will be described with reference to the drawings. The error value Y _{j, 0} of the error to be obtained is set to the error of J = 8 to 6 and j = 5 whose error position is unknown.
It is assumed that the error positions from to j = 0 are 9 values in total of known errors. The calculation formula of each value at this time is j = L-1 for calculating Y _{j, j in} order to obtain Y _{j, 0} as in the first embodiment.
Although it is performed from 0 to 0, it is more efficient to obtain the values of the intermediate values P ₀ to P _j−1 prior to this. That is, when obtaining P _{j ,} the calculation procedure of σ _{i, j} is σ _{i, j} = σ _{i, j-1} × X _j-1 +
σ _{1, j-1} and at the same time σ obtained here
_{From i, j} and syndrome S _i Is calculated. Intermediate value P _j obtained in this way
Should be stored somewhere else in memory. The L-th intermediate value And T _{0 of the} modified syndrome is obtained here. Thereafter, in the same manner as in the first embodiment, the remaining correction syndrome and the intermediate value Y _{L + t−1, L} ... _{L, L} of the error amount are obtained. It is calculated according to the formula. At this time, as in the first embodiment, Y _{i, j + 1} , that is, Y from the maximum value L−1 of j to 0.
The calculation result of Y _{i, j} = Y _{i, j + 1} / (X _i + X _j ) one step before the _{j, j} calculation step is used.
In this way, when the calculation is continued and j = 0, Y _{i, 0,} that is, the amount of error to be obtained is stored in the memory. In this way, if the number of error positions is known by other means, it is possible to efficiently perform erasure correction by giving the number of positions, and if it is within the range allowed by the code distance, It is possible to correct it systematically by the procedure.
The computational effort of this procedure is 1.5
× L ² + t ² . In the first embodiment of the present invention, 0
The original multiplication can be omitted from the beginning with the result being 0, and 1
Similarly, multiplication of can be omitted. Further, instead of setting the initial value, it is naturally conceivable to substitute the value while performing the condition determination such as inputting 0-element in the middle of the calculation. In addition, when performing sequential calculation, it is possible to perform calculation with some results stored in a register or the like. Further, these calculations may be executed by a usual microprocessor, and since the Galois field multiplication is usually carried out by a logarithmic table, the algorithm of the present invention is particularly efficient. By the way, the parity calculation of encoding requires a lot of speed along with the calculation of syndrome, so parallel arithmetic hardware is often used even when it is executed by software, but even when high speed is required, it is pure. It is also possible to perform these processes as software at a speed close to that of hardware by a microprogramming method including correction instead of hardware.

_C'n-1 , _C'n-2 ... _C'd-1 has no error in the received information words, and C'corresponds to d-1 parity words to be generated.
_d-2 , _C'd-3 ... _C'0 are all erroneous to 0 elements If these are lost and erasure correction is performed, decoding with ₀ elements input with the error position number as the parity position is exactly the encoding process. Is equivalent to performing on an information word, and if erasure correction can be performed at high speed by a microprogram, encoding can be performed in the same manner as decoding. In this case, the number t of unknown errors is naturally t = 0, and the number L of known errors is L.
Is L = d-1. In this way, it is possible to use only the syndrome calculation circuit as dedicated hardware and omit the encoding circuit.

As described above, according to the present invention, the normal correction and the erasure correction can be executed at high speed by using the syndrome generation circuit and the memory circuit in the code error check / correction device. For this reason, the decoding of a recording medium having a high raw error rate can be practically executed in an optical disk device or the like that requires high speed and high functionality, and the effect is great.

[Brief description of drawings]

FIG. 1a is a block diagram of a first embodiment of the present invention, FIG. 1b is a flow chart of the first calculating means of the first embodiment in FIG. 1a, and FIG. 1c is FIG. 1a. Flowchart of the second, third, and fourth calculation means of the first embodiment in FIG.
FIG. D and FIG. 1e show the first embodiment of FIG. 1a.
5, the flow chart of the sixth calculating means, FIG. 2a is a block diagram of the second embodiment of the present invention, and FIG. 2b is the first and seventh calculations of the second embodiment in FIG. 2a. FIG. 2c is a flow chart of the means, FIG. 2c shows the second embodiment of FIG.
Flow charts of the second, third and fourth calculating means, FIG. 2d is a flow chart of the fifth and eighth calculating means of the second embodiment in FIG. 2a, and FIG. 3 is a block diagram of the syndrome generating circuit. FIG. 4 is a flowchart of the decoding process by the Galois field arithmetic method in the conventional example. 52 …… Syndrome generation circuit, 53 …… Memory circuit, 54
... Galois field arithmetic circuit.

Claims (2)

(57) [Claims] _1. A known L number of error positions from X ₀ to Y _L-1 and S _{0 of} an error-correcting linear code of a minimum distance d whose codeword is composed of elements of a Galois field GF (2 ^r ). To S _d−2, a circuit for generating the syndrome, a means for storing the value, and j is 0 ≦ j
Let σ _{j, j} = 1 under the condition that ≦ L and j ≧ i ≧ 0 and the variable whose subscript does not satisfy the above inequality sign on the right side is 0, and σ _{i, j} = σ _{i, j−1} × X _{j −1} + σ _{i−1, i−1} as j
From 0 to L, and for each of the above j, i is changed under the above conditions to obtain a result, and σ _{i, L} obtained from the first sequential calculation means.
And from the syndrome calculated by the syndrome generation circuit At the second calculation means for calculating the correction syndrome T _k for k from 0 to d-2-L, and the correction syndrome T _k is treated in the same manner as the syndrome in error correction in which the number of error positions is usually unknown. , A third calculation means such as a Euclidean decoding method for obtaining an error evaluation polynomial of an intermediate value of an error amount to be obtained and a coefficient of an error locator polynomial for t errors whose number of error positions is unknown, and an error from the error locator polynomial. A fourth calculation means such as Chien's method for obtaining the position, and t error position numbers obtained by the fourth calculation means are substituted into the error locator polynomial and the error evaluator polynomial to obtain an intermediate error amount to be obtained. Fifth to calculate Y _{L + t−1, L} from the value Y _{L, L}
And the error amount Y _{j, 0} that is the total error amount for the L + t known and unknown error positions to be calculated, under the condition of i ≦ j by changing j from L−1 to 0. Then, Y _{j, j} is calculated and Y _{i, j} = Y _{i, j + 1} / (X _{i + Xj} ) on the right side is set, and Y _{j, j} of the calculation result on the left side is sequentially calculated. A Galois field arithmetic unit comprising sixth sequential calculation means for obtaining a result by a procedure of substituting _j into the above equation for obtaining Y _{j, j} . 2. Under the conditions of 0 ≦ j ≦ L and j ≧ i ≧ 0 _{, j} obtains σ _{i, j} calculated in the process of calculating σ _{i, j} for _j by the first calculating means. Syndrome S
with _i , At the intermediate result P _j , instead of P _L when j = L and j ≧ i ≧ 0 And a seventh computing means for storing to obtain a modified syndrome T ₀ of k = 0 at, for k from 1 to d-2-L seeking modified syndrome T _k by the second calculating means, further L + to be obtained instead of the sixth calculating means
The error amount Y _{j, 0} for t known and unknown error positions is changed from j to L−1 to 0, At Y _j, Y i on the right side by calculating the _{j, j = Y i, j} + 1 / (X i + X j) of the respective calculated results and the left side of the calculation results at Y _j, the sequentially j a _j 1 above minus Y
The Galois field arithmetic unit according to claim 1, comprising an eighth sequential calculation means for obtaining a result by the procedure of substituting into the equation for obtaining _{j, j} .