Reed Solomon error correcting circuit and method and device for Euclidean mutual division

[0010] 1. Field of the Invention

[0011] The present invention relates to a Reed-Solomon error-correcting circuit that is used as a system of error correction, and also to the Euclidian algorithm and apparatus that are used in systems of error correction such as BHC error-correcting systems and Reed-Solomon error correcting systems.

[0012] 2. Description of the Related Art

[0013] Error correcting systems such as BHC error-correcting systems and Reed-Solomon error-correcting systems are used as error correcting systems in various fields such as recording media like optical fibers and digital transmission systems like digital satellite broadcasting systems. Of recent years, as the scale of recording and transmission has become greater, error-correcting circuits that accommodate high-speed processing have been developed.

[0014] So far, as a Reed-Solomon error-correcting circuit that accommodates high-speed processing, there has been known the one disclosed in Japanese Patent Laid-Open Publication No. 3-195216.

[0015] This Reed-Solomon error-correcting circuit comprises, as shown in FIG. 18, a syndrome generating circuit 1 (equivalent to the syndrome generating circuit in the Reed-Solomon error-correction circuit of the present invention), an error-locator-polynomial deriving circuit 2 (equivalent to the error-locator-polynomial/error-evaluator-polynomial calculating circuit within the error correcting circuit in the Reed-Solomon error-correcting circuit of the present invention), an error-location detecting circuit 3 and an error-pattern detecting circuit 4 and an AND gate 5 and an EXOR gate 6 (equivalent to the correcting circuit within the error correcting circuit in the Reed-Solomon error-correcting circuit of the present invention), and a delay circuit 7 (equivalent to the memory in the Reed-Solomon error-correcting circuit of the present invention).

[0016] The error-locator-polynomial deriving circuit in this Reed-Solomon error-correcting circuit requires, as described in the embodiment of the patent disclosure, a great number of Galois-field calculating circuits installed between the registers of the shift registers, in order to accommodate high-speed processing. Therefore, there is a problem that the scale of hardware is large.

[0017] Also, in order to limit internal delays and increases in power consumption due to large-scale hardware, a high-speed clock is not used, and a received symbol clock is used for operation. Therefore, one packet of time is taken for processing in the error-locator-polynomial deriving circuit.

[0018] Therefore, there is required, at least, parallel operation with three-step pipelined processing by the syndrome generating circuit, the error-locator-polynomial deriving circuit, and the error-location detecting circuit, error-pattern detecting circuit, AND gate, and EXOR gate. Therefore, the delay circuit must hold three packets of data, so that the scale of hardware becomes still larger.

[0019] Next, the operation of the above circuit is described. In error correcting systems such as BHC error-correcting systems and Reed-Solomon error-correcting systems, first a syndrome equation S(z)=s_k−1z^k−1+s_k−2z^k−2+ . . . +s₀based on the received signal is obtained on the receiver side. In the Reed-Solomon error-correcting circuit described above, the syndrome generating circuit performs this operation.

[0020] If there exists no error in the signal, then the coefficients S_k−1to s₀of the syndrome equation S(z) become s_k−1=s_k−2= . . . =s₀=0, that is, the syndrome equation becomes S(z)=0. If there exist some errors in the signal, the syndrome equation becomes S(z)≠0.

[0021] If there exist some errors in the received signal, so that the syndrome signal becomes S(z)≠0, then, the error-locator-polynomial σ(z) is obtained from the syndrome equation S(z). In the Reed-Solomon error-correcting circuit described above, the error-locator-polynomial deriving circuit performs this operation.

[0022] Finally, errors are corrected by using the error-locator-polynomial σ(z).

[0023] Generally, in order to obtain the error-locator-polynomial σ(z) from the syndrome equation S(z), an Euclid's algorithm is used. In the past, as the Euclid's algorithm, the one described in “Development of Error correcting methods and LSI for optical disk drives,” Computer Architecture,67-3 (Sep. 16, 1987) is known.

[0024] A description is given in the following with the Reed-Solomon error-correcting method based on a report of the Committee on Digital Broadcasting Systems in the Council of Electronic Communication.

[0025] Code generating polynomial:

[0026] g(z)=(z+α0)(z+α1)(z+α2) . . . (z+α15), (α=02h).

[0027] Field generating polynomial: x8+x4+x3+x2+1.

[0028] Packet length: 204 bytes.

[0029] Information bytes therein: 188 bytes.

[0030] Error correcting number: 8 bytes.

[0031] In the Euclid's algorithm of the Reed-Solomon error-correcting system described above, initial setting for the polynomials A(z), B(z), L(z), and M(z) is made from the syndrome equation

[0032] S(z)=s₁₅z¹⁵+s₁₄Z¹⁴+ . . . +s₀

[0033] based on the signal decoded with the Reed-Solomon code, where s₁₅, . . . , s₀are elements of the Galois field GF(28) . Then the error-locator-polynomial σ(z) is obtained through Galdis-field operations. Operations on Galois fields are described in Hideki Imai, Coding Theory,Chapter 3, Institute of Electronics and Communication Engineers of Japan.

[0034] In the following is described the Euclid's algorithm in a prior example in conjunction with figures.

[0035] FIG. 19 is a flowchart illustrating the method of initial setting in a prior exemplary Euclid's algorithm. FIG. 20 is a flowchart illustrating a general Euclid's algorithm after initial setting.

[0036] In the Euclid's algorithm in the prior example, according to the method of initial setting illustrated in FIG. 19, initial setting for the polynomials A(z), B(z), L(z), and M(z) is performed from the syndrome equation

[0037] S(z)=s₁₅z¹⁵+s₁₄Z¹⁴+ . . . +s₀

[0038] based on a signal decoded with the Reed-Solomon error correcting code, where s₁₅, . . , s₀are elements of the Galois field GF(28). Then, according to the general Euclid algorithm after the initial setting illustrated in FIG. 20, Galois-field operations are performed to obtain the error-locator-polynomial σ(z). In the Galois-field operations, processing for reducing the degrees of the polynomials A(z) and B(z) is performed. When at least one of the degrees of the polynomials A(z) and B(z) becomes equal to or less than 7, the processing is terminated.

[0039] In the following is described an example of the Euclid's algorithm in the prior example illustrated in FIGS. 19, 20.

[0040] In the following, a first example of operations in the Euclid's algorithm in the prior example is described. This example of operations is in the case where s₁₅, . . , s₈≠0 for the coefficients of the syndrome equation S(z). In this example of operations, after sixth operations on the Galois field, the error-locator-polynomial σ(z) is obtained.

[0041] First example of operations in prior Euclidean algorithm. Syndrome.

[0042] S(z)=85z¹⁵+EBz¹⁴+E9z¹³+A9z¹²+F8z¹¹+AEz¹⁰+C4z⁹+14z⁸+A7z⁷+72z⁶+A0z⁵+58z⁴+91z³+51z²+5Fz+FF

[0043] After initial setting. $\begin{array}{c}A\left(z\right)=z^{16}\\ B\left(z\right)=85z^{15}+{\mathrm{EBz}}^{14}+{\mathrm{E9z}}^{13}+{\mathrm{A9z}}^{12}+{\mathrm{F8z}}^{11}+{\mathrm{AEz}}^{10}+{\mathrm{C4z}}^9+14z^8+{\mathrm{A7z}}^7+72z^6+{\mathrm{A0z}}^5+58z^4+91z^3+51z^2+5\mathrm{Fz}+\mathrm{FF}\\ L\left(Z\right)=0\\ M\left(Z\right)=1\end{array}$

[0044] After first Galois-field operations. $\begin{array}{c}A\left(z\right)={\mathrm{EBz}}^{15}+{\mathrm{E9z}}^{14}+{\mathrm{A9z}}^{13}+{\mathrm{F8z}}^{12}+{\mathrm{AEz}}^{11}+{\mathrm{C4z}}^{10}+14z^9+{\mathrm{A7z}}^8+72z^7+{\mathrm{A0z}}^6+58z^5+91z^4+51z^3+5{\mathrm{Fz}}^2+\mathrm{FFz}\\ B\left(z\right)=85z^{15}+{\mathrm{EBz}}^{14}+{\mathrm{E9z}}^{13}+{\mathrm{A9z}}^{12}+{\mathrm{F8z}}^{11}+{\mathrm{AEz}}^{10}+{\mathrm{C4z}}^9+14z^8+{\mathrm{A7z}}^7+72z^6+{\mathrm{A0z}}^5+58z^4+91z^3+51z^2+5\mathrm{Fz}+\mathrm{FF}\\ L\left(Z\right)=z\\ M\left(Z\right)=1\end{array}$

[0045] After second Galois-field operations. $\begin{array}{c}A\left(z\right)=96z^{14}+6z^{13}+48z^{12}+{\mathrm{A7z}}^{11}+71z^{10}+88z^9+{\mathrm{D4z}}^8+{\mathrm{C8z}}^7+20z^6+{\mathrm{E7z}}^5+27z^4+{\mathrm{C9z}}^3+{\mathrm{E6z}}^2+4\mathrm{Cz}+C\\ B\left(z\right)=85z^{15}+{\mathrm{EBz}}^{14}+{\mathrm{E9z}}^{13}+{\mathrm{A9z}}^{12}+{\mathrm{F8z}}^{11}+{\mathrm{AEz}}^{10}+{\mathrm{C4z}}^9+14z^8+{\mathrm{A7z}}^7+72z^6+{\mathrm{A0z}}^5+58z^4+91z^3+51z^2+5\mathrm{Fz}+\mathrm{FF}\\ L\left(Z\right)=z+68\\ M\left(Z\right)=1\end{array}$

[0046] After third Galois-field operations. $\begin{array}{c}A\left(z\right)=96z^{14}+06z^{13}+48z^{12}+{\mathrm{A7z}}^{11}+71z^{10}+88z^9+{\mathrm{D4z}}^8+{\mathrm{C8z}}^7+20z^6+{\mathrm{E7z}}^5+27z^4+{\mathrm{C9z}}^3+{\mathrm{E6z}}^2+4\mathrm{Cz}+0C\\ B\left(z\right)=91z^{14}+18z^{13}+3{\mathrm{Bz}}^{12}+4{\mathrm{Dz}}^{11}+{\mathrm{A4z}}^{10}+3{\mathrm{Ez}}^9+{\mathrm{BCz}}^8+{\mathrm{F6z}}^7+42z^6+6{\mathrm{Bz}}^5+10z^4+41z^3+7z^2+\mathrm{ABz}+\mathrm{FF}\\ L\left(Z\right)=z+68\\ M\left(Z\right)={\mathrm{E0z}}^2+\mathrm{A0z}+1\end{array}$

[0047] After fourth Galois-field operations. $\begin{array}{c}A\left(z\right)=71z^{13}+{\mathrm{E1z}}^{12}+41z^{11}+{\mathrm{B7z}}^{10}+9{\mathrm{Fz}}^9+65z^8+6{\mathrm{Dz}}^7+19z^6+61z^5+7{\mathrm{Dz}}^4+9{\mathrm{Az}}^3+14z^2+55z+\mathrm{A2}\\ B\left(z\right)=91z^{14}+18z^{13}+3{\mathrm{Bz}}^{12}+4{\mathrm{Dz}}^{11}+{\mathrm{A4z}}^{10}+3{\mathrm{Ez}}^9+{\mathrm{BCz}}^8+{\mathrm{F6z}}^7+42z^6+6{\mathrm{Bz}}^5+10z^4+41z^3+7z^2+\mathrm{ABz}+\mathrm{FF}\\ L\left(Z\right)=2{\mathrm{Bz}}^2+5\mathrm{Fz}+4E\\ M\left(Z\right)={\mathrm{E0z}}^2+\mathrm{A0z}+1\end{array}$

[0048] After fifth Galois-field operations. $\begin{array}{c}A\left(z\right)=71z^{13}+{\mathrm{E1z}}^{12}+41z^{11}+{\mathrm{B7z}}^{10}+9{\mathrm{Fz}}^9+65z^8+6{\mathrm{Dz}}^7+19z^6+61z^5+7{\mathrm{Dz}}^4+9{\mathrm{Az}}^3+14z^2+55z+\mathrm{A2}\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{EBz}}^{12}+37z^{11}+49z^{10}+6{\mathrm{Az}}^9+61z^8+{\mathrm{CCz}}^7+{\mathrm{DCz}}^6+{\mathrm{B9z}}^5+8{\mathrm{Bz}}^4+84z^3+42z^2+\mathrm{A8z}+\mathrm{FF}\\ L\left(Z\right)=2{\mathrm{Bz}}^2+5\mathrm{Fz}+4E\\ M\left(Z\right)=4{\mathrm{Ez}}^3+49z^2+\mathrm{BAz}+1\end{array}$

[0049] After sixth Galois-field operations. $\begin{array}{c}A\left(z\right)=59z^2+93\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{EBz}}^{12}+37z^{11}+49z^{10}+6{\mathrm{Az}}^9+61z^8+{\mathrm{CCz}}^7+{\mathrm{DCz}}^6+{\mathrm{B9z}}^5+8{\mathrm{Bz}}^4+84z^3+42z^2+\mathrm{A8z}+\mathrm{FF}\\ L\left(Z\right)=6{\mathrm{Az}}^3+9{\mathrm{Cz}}^2+\mathrm{FEz}+E\\ M\left(Z\right)=4{\mathrm{Ez}}^3+49z^2+\mathrm{BAz}+1\end{array}$

[0050] Result.

[0051] σ(z)=L(Z)=6Az³+9Cz²FEz+E

[0052] In the following, a second example of operations in the Euclid's algorithm in the prior example is described. This example of operations is in the case where s₁₅≠0 and at least one of s₁₄, . . , s₈is 0 for the coefficients of the syndrome equation S(z). In this example of operations, after fourth operations on the Galois field, the error-locator-polynomial σ(z) is obtained.

[0053] Second example of operations in prior Euclidean algorithm. Syndrome. $S\left(z\right)=9{\mathrm{Fz}}^{15}+94z^{12}+{\mathrm{F4z}}^{11}+{\mathrm{ECz}}^{10}+6{\mathrm{Dz}}^9+5{\mathrm{Fz}}^8+27z^7+5{\mathrm{Cz}}^6+96z^5+21z^4+{\mathrm{A0z}}^3+{\mathrm{BFz}}^2+7\mathrm{Fz}+46$

[0054] After initial setting $\begin{array}{c}A\left(z\right)=z^{16}\\ B\left(z\right)=9{\mathrm{Fz}}^{15}+94z^{12}+{\mathrm{F4z}}^{11}+{\mathrm{ECz}}^{10}+6{\mathrm{Dz}}^9+5{\mathrm{Fz}}^8+27z^7+5{\mathrm{Cz}}^6+96z^5+21z^4+{\mathrm{A0z}}^3+{\mathrm{BFz}}^2+7\mathrm{Fz}+46\\ L\left(Z\right)=0\\ M\left(Z\right)=1\end{array}$

[0055] After first Galois-field operations $\begin{array}{c}A\left(z\right)=+94z^{13}+{\mathrm{F4z}}^{12}+{\mathrm{ECz}}^{11}+6{\mathrm{Dz}}^{10}+5{\mathrm{Fz}}^9+27z^8+5{\mathrm{Cz}}^7+96z^6+21z^5+{\mathrm{A0z}}^4+{\mathrm{BFz}}^3+7{\mathrm{Fz}}^2+46z\\ B\left(z\right)=9{\mathrm{Fz}}^{15}+94z^{12}+{\mathrm{F4z}}^{11}+{\mathrm{ECz}}^{10}+6{\mathrm{Dz}}^9+5{\mathrm{Fz}}^8+27z^7+5{\mathrm{Cz}}^6+96z^5+21z^4+{\mathrm{A0z}}^3+{\mathrm{BFz}}^2+7\mathrm{Fz}+46\\ L\left(Z\right)=z\\ M\left(Z\right)=1\end{array}$

[0056] After second Galois-field operations $\begin{array}{c}A\left(z\right)=94z^{13}+{\mathrm{F4z}}^{12}+{\mathrm{ECz}}^{11}+6{\mathrm{Dz}}^{10}+5{\mathrm{Fz}}^9+27z^8+5{\mathrm{Cz}}^7+96z^6+21z^5+{\mathrm{A0z}}^4+{\mathrm{BFz}}^3+7{\mathrm{Fz}}^2+46z\\ B\left(z\right)={\mathrm{Bz}}^{14}+2{\mathrm{Ez}}^{13}+81z^{12}+91z^{11}+38z^{10}+2{\mathrm{Fz}}^9+{\mathrm{FAz}}^8+{\mathrm{BDz}}^7+{\mathrm{FDz}}^6+41z^5+{\mathrm{C3z}}^4+{\mathrm{FDz}}^3+{\mathrm{BFz}}^2+7\mathrm{Fz}+46\\ L\left(Z\right)=z\\ M\left(Z\right)=1{\mathrm{Dz}}^3+1\end{array}$

[0057] After third Galois-field operations $\begin{array}{c}A\left(z\right)=94z^{13}+{\mathrm{F4z}}^{12}+{\mathrm{ECz}}^{11}+6{\mathrm{Dz}}^{10}+5{\mathrm{Fz}}^9+27z^8+5{\mathrm{Cz}}^7+96z^6+21z^5+{\mathrm{A0z}}^4+{\mathrm{BFz}}^3+7{\mathrm{Fz}}^2+46z\\ B\left(z\right)={\mathrm{D1z}}^{13}+43z^{12}+{\mathrm{E9z}}^{11}+2z^{10}+{\mathrm{DCz}}^9+{\mathrm{E4z}}^8+8{\mathrm{Ez}}^7+46z^6+40z^5+{\mathrm{ABz}}^4+60z^3+{\mathrm{A4z}}^2+7\mathrm{Fz}+46\\ L\left(Z\right)=z\\ M\left(Z\right)=1{\mathrm{Dz}}^3+1{\mathrm{Cz}}^2+1\end{array}$

[0058] After fourth Galois-field operations $\begin{array}{c}A\left(z\right)=79z^2+10z+96\\ B\left(z\right)={\mathrm{D1z}}^{13}+43z^{12}+{\mathrm{E9z}}^{11}+2z^{10}+{\mathrm{DCz}}^9+{\mathrm{E4z}}^8+8{\mathrm{Ez}}^7+46z^6+40z^5+{\mathrm{ABz}}^4+60z^3+{\mathrm{A4z}}^2+7\mathrm{Fz}+46\\ L\left(Z\right)=84z^3+3{\mathrm{Cz}}^2+z+\mathrm{B8}\\ M\left(Z\right)=1{\mathrm{Dz}}^3+1{\mathrm{Cz}}^2+1\end{array}$

[0059] Result

[0060] σ(z)=L(Z)=84z³+3Cz²+z+B8

[0061] A third example of operations in the Euclid's algorithm in the prior example is described in the following. This example of operations is in the case where S₁₅= . . . =s_n=0 and s_n−1≠0, where n≦15, and n is an integer, for the coefficients of the syndrome equation S(z). In this example of operations, after fourth operations on the Galois field, the error-locator-polynomial σ(z) is obtained.

[0062] Third example of operations in prior Euclidean algorithm. Syndrome.

[0063] S(z)=FEz¹³+D8z¹²+9Fz¹¹+D8z¹⁰+09z⁹+9Dz⁸+E7z⁷+B7z⁶+91z⁵+0Bz⁴+6Bz³+79z²+FDz+90

[0064] After initial setting $\begin{array}{c}A\left(z\right)=z^{16}\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{D8z}}^{12}+9{\mathrm{Fz}}^{11}+{\mathrm{D8z}}^{10}+09z^9+9{\mathrm{Dz}}^8+{\mathrm{E7z}}^7+{\mathrm{B7z}}^6+91z^5+0{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90\\ L\left(Z\right)=0\\ M\left(Z\right)=1\end{array}$

[0065] After first Galois-field operations $\begin{array}{c}A\left(z\right)={\mathrm{D8z}}^{15}+9{\mathrm{Fz}}^{14}+{\mathrm{D8z}}^{13}+09z^{12}+9{\mathrm{Dz}}^{11}+{\mathrm{E7z}}^{10}+{\mathrm{B7z}}^9+91z^8+0{\mathrm{Bz}}^7+6{\mathrm{Bz}}^6+79z^5+{\mathrm{FDz}}^4+90z^3\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{D8z}}^{12}+9{\mathrm{Fz}}^{11}+{\mathrm{D8z}}^{10}+09z^9+9{\mathrm{Dz}}^8+{\mathrm{E7z}}^7+{\mathrm{B7z}}^6+91z^5+0{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90\\ L\left(Z\right)=z^3\\ M\left(Z\right)=1\end{array}$

[0066] After second Galois-field operations $\begin{array}{c}A\left(z\right)={\mathrm{ECz}}^{14}+7{\mathrm{Az}}^{13}+7{\mathrm{Az}}^{12}+{\mathrm{C1z}}^{11}+83z^{10}+4{\mathrm{Dz}}^9+{\mathrm{F0z}}^8+{\mathrm{C1z}}^7+{\mathrm{F1z}}^6+{\mathrm{FAz}}^5+{\mathrm{C6z}}^4+{\mathrm{EDz}}^3+{\mathrm{A9z}}^2\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{D8z}}^{12}+9{\mathrm{Fz}}^{11}+{\mathrm{D8z}}^{10}+9z^9+9{\mathrm{Dz}}^8+{\mathrm{E7z}}^7+{\mathrm{B7z}}^6+91z^5+{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90\\ L\left(Z\right)=z^3+63z^2\\ M\left(Z\right)=1\end{array}$

[0067] After third Galois-field operations $\begin{array}{c}A\left(z\right)=1{\mathrm{Az}}^{13}+87z^{12}+{\mathrm{A1z}}^{11}+87z^{10}+2{\mathrm{Cz}}^9+8{\mathrm{Cz}}^8+43z^7+{\mathrm{FFz}}^6+62z^5+z^4+22z^3+97z^2+40z\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{D8z}}^{12}+9{\mathrm{Fz}}^{11}+{\mathrm{D8z}}^{10}+9z^9+9{\mathrm{Dz}}^8+{\mathrm{E7z}}^7+{\mathrm{B7z}}^6+91z^5+{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90\\ L\left(Z\right)=z^3+63z^2+4\mathrm{Ez}\\ M\left(Z\right)=1\end{array}$

[0068] After fourth Galois-field operations $\begin{array}{c}A\left(z\right)={\mathrm{EDz}}^2+\mathrm{EFz}+\mathrm{FA}\\ B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{D8z}}^{12}+9{\mathrm{Fz}}^{11}+{\mathrm{D8z}}^{10}+9z^9+9{\mathrm{Dz}}^8+{\mathrm{E7z}}^7+{\mathrm{B7z}}^6+91z^5+{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90\\ L\left(Z\right)=z^3+63z^2+4\mathrm{Ez}+98\\ M\left(Z\right)=1\end{array}$

[0069] Result

[0070] σ(z)=L(Z)=z³+63z²+4Ez+98

[0071] As described above, in the prior Euclid's algorithm, a great number of Galois-field operations are required, and this fact has been an obstacle to increase the speed of processing.

[0072] As described above, there has been a problem that the scale of hardware becomes large in order to accommodate high-speed processing in the prior Reed-Solomon error-correcting circuit. Also, a great number of Galois-field operations are required and become an obstacle to increase the speed of processing.

[0073] FIG. 1 is a block diagram illustrating the Reed-Solomon error-correcting circuit in a first embodiment of the present invention.

[0074] FIG. 2 is a block diagram illustrating the internal construction of the error-correcting circuit 503.

[0075] FIG. 3 is a block diagram illustrating the internal construction of the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504.

[0076] FIG. 4 is a flowchart illustrating the method of initial setting in the Euclid's algorithm in a second embodiment of the present invention.

[0077] FIG. 5 is a flowchart illustrating the method of initial setting in the Euclid's algorithm in a third embodiment of the present invention.

[0078] FIG. 6 is a flowchart illustrating the method of initial setting in the Euclid's algorithm in a fourth embodiment of the present invention.

[0079] FIG. 7 is a block diagram illustrating the construction of the Euclid's algorithm apparatus in a fifth embodiment of the present invention.

[0080] FIG. 3 is a state diagram of the polynomial storage devices in a first operation example of the same Euclid's algorithm apparatus.

[0081] FIG. 9 is a state diagram of the polynomial storage devices in a second operation example of the same Euclid's algorithm apparatus.

[0082] FIG. 10 is a block diagram illustrating the construction of the Euclid's algorithm apparatus in a sixth embodiment of the present invention.

[0083] FIG. 11 is a state diagram of the polynomial storage devices in a first operation example of the same Euclid's algorithm apparatus.

[0084] FIG. 12 is a state diagram of the polynomial storage devices in a second operation example of the same Euclid's algorithm apparatus.

[0085] FIGS. 13A and 13B are state diagrams of the polynomial storage devices in a third operation example of the same Euclid's algorithm apparatus.

[0086] FIG. 14 is a block diagram illustrating the construction of the Euclid's algorithm apparatus in a seventh embodiment of the present invention.

[0087] FIG. 15 is a state diagram of the polynomial storage devices in a first operation example of the same Euclid's algorithm apparatus.

[0088] FIG. 16 is a state diagram of the polynomial storage devices in a second operation example of the same Euclid's algorithm apparatus.

[0089] FIG. 17 is a state diagram of the polynomial storage devices in a third operation example of the same Euclid's algorithm apparatus.

[0090] FIG. 18 is a block diagram of a prior Reed-Solomon error-correcting circuit.

[0091] FIG. 19 is a flowchart illustrating the method of initial setting in a prior exemplary Euclid's algorithm.

[0092] FIG. 20 is a flowchart illustrating a general Euclid's algorithm after initial setting.

[0093] FIG. 1 is a block diagram illustrating the Reed-Solomon error-correcting circuit in a first embodiment of the present invention.

[0094] In FIG. 1, 401 is a received packet, 402 is a syndrome, 403 is a delayed packet, 404 is a decoded packet, 407 is a clock with a period of ¼ the period of the received symbol clock, 501 is a memory that inputs the received packet 401 and delays it by an amount for 2 packets to output as the delayed packet 403, 502 is a syndrome generating circuit that inputs the received packet 401 to output the syndrome 402, and 503 is an error-correcting circuit that inputs the delayed packet 403 and the syndrome 402 to output the decoded packet 404.

[0095] The syndrome generating circuit 502 and the error-correcting circuit 503 have a pipelined structure for each packet. The clock 407 with a period of ¼ the period of the received symbol clock is supplied to the error-correcting circuit 503.

[0096] FIG. 2 is a block diagram illustrating the internal construction of the error-correcting circuit 503. In FIG. 2, 504 is an error-locator-polynomial/error-evaluator-polynomial calculating circuit that inputs the syndrome 402 to output the error-locator-polynomial 405 and the error-evaluator-polynomial 406. 505 is a correcting circuit that inputs the delayed packet 403, the error-locator-polynomial 405, and the error-evaluator-polynomial 406, obtains errors contained in the delayed packet 403 from the error-locator-polynomial 405 and the error-evaluator-polynomial 406, removes the errors from the delayed packet 403, and outputs the decoded packet 404.

[0097] FIG. 3 is a block diagram illustrating the internal construction of the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504. In FIG. 3, 408 and 409 are candidates for the error-evaluator-polynomial. 410 and 411 are candidates for the error-locator-polynomial. 506 is a shift register that inputs the syndrome 402 as its initial value, successively inputs, in its first step after that, the output of a Galois-field operations circuit, performs shift operations, outputs the data in the last step, and outputs, after the operations, the data stored therein as the candidate 408 for the error-evaluator-polynomial. 507 is a shift register that inputs a constant as its initial value, successively inputs, in its first step after that, the output of a Galois-field operations circuit, performs shift operations, outputs the data in the last step, and outputs, after the operations, the data stored therein as the candidate 409 for the error-evaluator-nolynomial. 508 is a shift register that inputs a constant as its initial value, successively inputs, in its first step after that, the output of a Galois-field operations circuit, performs shift operations, outputs the data in the last step, and outputs, after the operations, the data stored therein as the candidate 410 for the error-locator-polynomial. 508 is a shift register that inputs a constant as its initial value, successively inputs, in its first step after that, the output of a Galois-field operations circuit, performs shift operations, outputs the data in the last step, and outputs, after the operations, the data stored therein as the candidate 411 for the error-locator-polynomial.

[0098] 510 is a Galois-field operations circuit that inputs the data in the last step of the shift registers 506 to 509 and performs Galois-field operations to output the results. 511 is a selector that inputs the candidates 408, 409 for the error-evaluator-polynomial and the candidates 410, 411 for the error-locator-polynomial, to output the error-locator-polynomial 405 and the error-evaluator-polynomial 406.

[0099] The operation of the Reed-Solomon error-correcting circuit constructed in this way in the first embodiment of present invention is described in the following.

[0100] The memory 501 inputs the received packet 401 to output the delayed packet 403 by delaying by an amount for 2 packets. This corresponds to the fact that the syndrome generating circuit 502 and the error-correcting circuit 503 have a two-step pipelined structure for each packet.

[0101] The syndrome generating circuit 502 inputs the received packet 401 to output the syndrome 402.

[0102] The error-correcting circuit 503S inputs the syndrome 402 and the delayed packet 403, obtains, in the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504, the error-locator-polynomial 405 and the error-evaluator-polynomial 406 from the syndrome 402, obtains errors contained in the delayed packet 403, removes the errors from the delayed packet 403, and outputs the decoded packet 404.

[0103] The syndrome generating circuit 502 and the error-correcting circuit 503 perform parallel operation by pipelined processing for each packet.

[0104] The error-correcting circuit 503 operates in synchronization with a clock 7 with a period of ¼ the period of the received symbol clock.

[0105] The operation of the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504 within the error-correcting circuit 503 is described in the following.

[0106] The shift register 506 inputs the syndrome 402 as its initial value. The shift registers 507 to 509 input constants as their initial values.

[0107] After that, the shift register 506 to 509 successively input, in their first steps, the output of a Galois-field operations circuit 510, perform shift operations, and output the data in their last steps.

[0108] The Galois-field operations circuit 510 inputs the data in the last steps of the shift registers 506 to 509 and performs Galois-field operations, and outputs the results.

[0109] After the operations are finished, the shift registers 506 to 509 respectively output the data stored therein as the candidates 408, 409 for the error-evaluator-polynomial and the candidates 410, 411 for the error-locator-polynomial.

[0110] The selector 511 inputs the Candidates 408, 409 for the error-evaluator-polynomial and the candidates 410, 411 for the error-locator-polynomial and outputs the error-locator-polynomial 405 and the error-evaluator-polynomial 406.

[0111] The Reed-Solomon error-correcting circuit in the first embodiment of the present invention performs error correction by performing the operation described above.

[0112] In this way, the Reed-Solomon error-correcting circuit in the first embodiment of the present invention performs a similar operation as the Reed-Solomon error-correcting circuit in the prior example described above. However, the error-locator-polynomial deriving Circuit (equivalent to the error-locator-polynomial/error-evaluator-polynomial calculating circuit of the Reed-Solomon error-correcting circuit in the present invention) of the Reed-Solomon error correcting circuit in the prior example had a large number of Galois-field operations circuits between the shift registers. On the other hand, the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504 of the Reed-Solomon error-correcting circuit in the first embodiment of the present invention does not have any Galois-field operations circuit between the shift registers and has only a Galois-field operations circuit that inputs the outputs in the last steps of the shift registers, so that the scale of hardware is small.

[0113] Therefore, the internal delay and power consumption are small, so that a high-speed clock can be used. Therefore, as described above, the operation can be synchronized with the clock 7 that has a period of ¼ the period of the received symbol clock. Therefore, as the Reed-Solomon error-correcting circuit in the first embodiment of the present invention, the construction of the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504 that has no Galois-field operations circuits between the shift registers can sufficiently accommodate high-speed processing, and also, parallel operation by two-step pipelined processing can accommodate high-speed processing. As a result, it is sufficient for the memory 501 to hold two packets of data, so that the scale of hardware becomes still smaller.

[0114] In the above description, the error-correcting circuit 503 has been constructed so as to operate with a clock with a period of ¼ the period of the received symbol clock. However, the implementation can be made with another period such as ½ or ⅛.

[0115] Also, in the above description, the error-locator-polynomial/error-evaluator-polynomial calculating circuit 504 has been equipped with four shift registers, but can be equipped with a different number of registers. For example, two shift registers arranged in serial or eight registers divided from the above and others can be implemented in various embodiments. Also, one memory can be used to substitute the shift registers.

[0116] Further, in the error-locator-polynomial/error-evaluator-polynomial evaluator-polynomial calculating circuit 504, the outputs of the shift registers in their last steps are input again to the shift registers through the Galois-field operations circuit, the circuit 504 can be operated in the same way as in a construction that has Galois-field operations circuits between the registers.

[0117] The present invention is independent of any of these minor differences in embodiments. In a Reed-Solomon error-correcting circuit that receives a transmitted packet encoded with a Reed-Solomon code, decodes the received packet with a Reed-Solomon code, and outputs the decoded packet, the present invention has a memory that inputs and delays the received packet to output a delayed packet, a syndrome generating circuit that inputs the received packet to output a syndrome, and an error-correcting circuit that inputs the delayed packet and the syndrome to output the decoded packet. The error-correcting circuit comprises an error-locator-polynomial/error-evaluator-polynomial calculating circuit that inputs the syndrome and outputs an error-locator-polynomial and an error-evaluator-polynomial and a correcting circuit that inputs the delayed packet, the error-locator-polynomial, and the error-evaluator-polynomial, obtains errors contained in the delayed packet from the error-locator-polynomial and the error-evaluator-polynomial, removes the errors from the delayed packet, and outputs the decoded packet. The error-locator-polynomial/error-evaluator-polynomial calculating circuit has a memory, to which a syndrome equation and initial values are input, and a Galois-field operations circuit that is connected to the memory with data input/output capability. The present invention is characterized in that the syndrome generating circuit and the error-correcting circuit perform parallel operation by pipelined processing for each packet, and the error-correcting circuit operates in synchronization with a clock with a period of 1/N the period of the received symbol clock, where N≧1, and N is an integer. Therefore the present invention accommodates high-speed processing with small-scale hardware.

[0118] Next, the Euclid's algorithms and apparatus in the second to seventh embodiments of the present embodiment are described in conjunction with figures.

[0119] The Euclid's algorithms and apparatus of the present invention can employ the general Euclid's algorithm after initial setting illustrated in FIG. 20. The features of the Euclid's algorithm and apparatus in the present invention lie in methods of initial setting. Therefore, the methods of initial setting are described in details, and the general Euclid's algorithm after initial setting is briefly described in conjunction with FIG. 20.

[0120] FIG. 4 is a flowchart illustrating the method of initial setting in the Euclid's algorithm in a second embodiment of the present invention. In the Euclid's algorithm in the second embodiment of the present invention, according to the method of initial setting illustrated in FIG. 4, initial setting for the polynomials A(z), B(z), L(z), and M(z) is performed from the syndrome equation

[0121] S(z)=s₁₅z¹⁵+s₁₄Z¹⁴+ . . . +S₀

[0122] based on a signal encoded with a Reed-Solomon code, where s₁₅, . . . , s₀are elements of the Galois field GF(28). Then according to the general Euclid's algorithm after initial setting illustrated in FIG. 16, Galois-field operations are performed to obtain the error-locator-polynomial σ(z). In the Galois-field operations, processing for reducing the degrees of the polynomials A(z) and B(z) is performed. When at least one of the degrees of the polynomials A(z) and B(z) becomes equal to or less than 7, the processing is terminated.

[0123] Examples of operations in the Euclid's algorithm in the second embodiment of the present invention illustrated in FIGS. 4 and 20 are described in the following.

[0124] A first example of operations in the Euclid's algorithm in the second embodiment of the present invention is described in the following. This example of operations uses the same syndrome equation as the one in the first example of operations in the Euclid's algorithm described previously. For the coefficients of the syndrome equation S(z), s₁₅, . . , s₈≠0 in this case.

[0125] Syndrome.

[0126] S(z)=85z¹⁵+EBz¹⁴+E9z¹³+A9z¹²+F8z¹¹+AEz¹⁰C4z⁹+14z⁸+A7z⁷+72z⁶+A0z⁵+58z⁴+91z³+51z²5Fz+FF

[0127] After initial setting. $A\left(z\right)=\mathrm{EB}{z}^{15}+E9z^{14}+A9z^{13}+F8z^{12}+{\mathrm{AEz}}^{11}+C4z^{10}+14z^9+A7z^8+72z^7+A0z^6+58z^5+91z^4+51z^3+5F{z}^2+FFz$ $B\left(z\right)=85z^{15}+{\mathrm{EBz}}^{14}+E9z^{13}+A9z^{12}+F8z^{11}+{\mathrm{AEz}}^{10}+C4z^9+14z^8+A7z^7+72z^6+A0z^5+58z^4+91z^3+51z^2+5\mathrm{Fz}+\mathrm{FF}$ $L\left(Z\right)=z$ $M\left(Z\right)=1$

[0128] After first Galois-field operations $A\left(z\right)=96z^{14}+6z^{13}+48z^{12}+A7z^{11}+71z^{10}+88z^9+D4z^8+C8z^7+20z^6+E7z^5+27z^4+C9z^3+E6z^2+4\mathrm{Cz}+C$ $B\left(z\right)=85z^{15}+{\mathrm{EBz}}^{14}+E9z^{13}+A9z^{12}+F8z^{11}+{\mathrm{AEz}}^{10}+C4z^9+14z^8+A7z^7+72z^6+A0z^5+58z^4+91z^3+51z^2+5\mathrm{Fz}+\mathrm{FF}$ $L\left(Z\right)=z+68$ $M\left(Z\right)=1$

[0129] After second Galois-field operations $A\left(z\right)=96z^{14}+06z^{13}+48z^{12}+A7z^{11}+71z^{10}+88z^9+D4z^8+C8z^7+20z^6+E7z^5+27z^4+C9z^3+E6z^2+4\mathrm{Cz}+0C$ $B\left(z\right)=91z^{14}+18z^{13}+3{\mathrm{Bz}}^{12}+4{\mathrm{Dz}}^{11}+A4z^{10}+3{\mathrm{Ez}}^9+{\mathrm{BCz}}^8+F6z^7+42z^6+6{\mathrm{Bz}}^5+10z^4+41z^3+7z^2+\mathrm{ABz}+\mathrm{FF}$ $L\left(Z\right)=z+68$ $M\left(Z\right)=E0z^2+A0z+1$

[0130] After third Galois-field operations $A\left(z\right)=71z^{13}+E1z^{12}+41z^{11}+B7z^{10}+9{\mathrm{Fz}}^9+65z^8+6{\mathrm{Dz}}^7+19z^6+61z^5+7{\mathrm{Dz}}^4+9{\mathrm{Az}}^3+14z^2+55z+A2$ $B\left(z\right)=91z^{14}+18z^{13}+3{\mathrm{Bz}}^{12}+4{\mathrm{Dz}}^{11}+A4z^{10}+3{\mathrm{Ez}}^9+{\mathrm{BCz}}^8+F6z^7+42z^6+6{\mathrm{Bz}}^5+10z^4+41z^3+7z^2+\mathrm{ABz}+\mathrm{FF}$ $L\left(Z\right)=2{\mathrm{Bz}}^2+5\mathrm{Fz}+4E$ $M\left(Z\right)=E0z^2+A0z+1$

[0131] After fourth Galois-field operations $A\left(z\right)=71z^{13}+E1z^{12}+41z^{11}+B7z^{10}+9{\mathrm{Fz}}^9+65z^8+6{\mathrm{Dz}}^7+19z^6+61z^5+7{\mathrm{Dz}}^4+9{\mathrm{Az}}^3+14z^2+55z+A2$ $B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{EBz}}^{12}+37z^{11}+49z^{10}+6{\mathrm{Az}}^9+61z^8+{\mathrm{CCz}}^7+{\mathrm{DCz}}^6+B9z^5+8{\mathrm{Bz}}^4+84z^3+42z^2+A8z+\mathrm{FF}$ $L\left(Z\right)=2{\mathrm{Bz}}^2+5\mathrm{Fz}+4E$ $M\left(Z\right)=4{\mathrm{Ez}}^3+49z^2+\mathrm{BAz}+1$

[0132] After fifth Galois-field operations $A\left(z\right)=59z^2+93$ $B\left(z\right)={\mathrm{FEz}}^{13}+{\mathrm{EBz}}^{12}+37z^{11}+49z^{10}+6{\mathrm{Az}}^9+61z^8+{\mathrm{CCz}}^7+{\mathrm{DCz}}^6+B9z^5+8{\mathrm{Bz}}^4+84z^3+42z^2+A8z+\mathrm{FF}$ $L\left(Z\right)=6{\mathrm{Az}}^3+9{\mathrm{Cz}}^2+\mathrm{FEz}+E$ $M\left(Z\right)=4{\mathrm{Ez}}^3+49z^2+\mathrm{BAz}+1$

[0133] Result.

[0134] σ(z)=L(Z)=6Az³+9Cz²+FEz+E

[0135] The polynomials A(z), B(z), L(z), M(z) after initial setting in the present example are the polynomials A(z), B(z), L(z), M(z) after the first Galois-field operations in the first example of operations in the Euclidean algorithm of the prior example. As a result, the number of Galois field operations before obtaining the error-location polynomial σ(z) is five, that is, one less than in the first example of operations in the Euclidean algorithm of the prior example.

[0136] A second example of operations in the Euclidean algorithm in the second embodiment of the present invention is described in the following. This example of operations uses the same syndrome equation as the one in the second example of operations in the prior Euclidean algorithm described previously. For the coefficients of the syndrome equation S(z), s15≠0, and at least one of s14, . . , s8 is 0 in this case.

[0137] Syndrome.

[0138] S(z)=9Fz¹⁵+94z¹²+F4z¹¹+ECz¹⁰+6Dz⁹+5Fz⁸+27z⁷+5Cz⁶+96z⁵+21z⁴+A0z³+BFz²+7Fz+46

[0139] After initial setting $A\left(z\right)=+94z^{13}+F4z^{12}+{\mathrm{ECz}}^{11}+6{\mathrm{Dz}}^{10}+5{\mathrm{Fz}}^9+27z^8+5{\mathrm{Cz}}^7+96z^6+21z^5+A0z^4+{\mathrm{BFz}}^3+7{\mathrm{Fz}}^2+46z$ $B\left(z\right)=9{\mathrm{Fz}}^{15}+94z^{12}+F4z^{11}+{\mathrm{ECz}}^{10}+6{\mathrm{Dz}}^9+5{\mathrm{Fz}}^8+27z^7+5{\mathrm{Cz}}^6+96z^5+21z^4+A0z^3+{\mathrm{BFz}}^2+7\mathrm{Fz}+46$ $L\left(Z\right)=z$ $M\left(Z\right)=1$

[0140] After first Galois-field operations $A\left(z\right)=94z^{13}+F4z^{12}+{\mathrm{ECz}}^{11}+6{\mathrm{Dz}}^{10}+5{\mathrm{Fz}}^9+27z^8+5{\mathrm{Cz}}^7+96z^6+21z^5+A0z^4+{\mathrm{BFz}}^3+7{\mathrm{Fz}}^2+46z$ $B\left(z\right)={\mathrm{Bz}}^{14}+2{\mathrm{Ez}}^{13}+81z^{12}+91z^{11}+38z^{10}+2{\mathrm{Fz}}^9+{\mathrm{FAz}}^8+{\mathrm{BDz}}^7+{\mathrm{FDz}}^6+41z^5+C3z^4+{\mathrm{FDz}}^3+{\mathrm{BFz}}^2+7\mathrm{Fz}+46$ $L\left(Z\right)=z$ $M\left(Z\right)=1{\mathrm{Dz}}^3+1$

[0141] After second Galois-field operations $A\left(z\right)=94z^{13}+F4z^{12}+{\mathrm{ECz}}^{11}+6{\mathrm{Dz}}^{10}+5{\mathrm{Fz}}^9+27z^8+5{\mathrm{Cz}}^7+96z^6+21z^5+A0z^4+{\mathrm{BFz}}^3+7{\mathrm{Fz}}^2+46z$ $B\left(z\right)=D1z^{13}+43z^{12}+E9z^{11}+2z^{10}+{\mathrm{DCz}}^9+E4z^8+8{\mathrm{Ez}}^7+46z^6+40z^5+{\mathrm{ABz}}^4+60z^3+A4z^2+7\mathrm{Fz}+46$ $L\left(Z\right)=z$ $M\left(Z\right)=1{\mathrm{Dz}}^3+1{\mathrm{Cz}}^2+1$

[0142] After third Galois-field operations $A\left(z\right)=79z^2+10z+96$ $B\left(z\right)=D1z^{13}+43z^{12}+E9z^{11}+2z^{10}+{\mathrm{DCz}}^9+E4z^8+8{\mathrm{Ez}}^7+46z^6+40z^5+{\mathrm{ABz}}^4+60z^3+A4z^2+7\mathrm{Fz}+46$ $L\left(Z\right)=84z^3+3{\mathrm{Cz}}^2+z+B8$ $M\left(Z\right)=1{\mathrm{Dz}}^3+1{\mathrm{Cz}}^2+1$

[0143] Result

[0144] σ(z)=L(Z)=84z³+3Cz²+z+B8

[0145] The polynomials A(z), B(z), L(z), M(z) after initial setting in the present example are the polynomials A(z), B(z), L(z), M(z) after the first Galois-field operations in the second example of operations in the Euclid's algorithm of the prior example. As a result, the number of Galois field operations before obtaining the error-locator-polynomial σ(z) is three, that is, one less than in the second example of operations in the Euclid's algorithm of the prior example.

[0146] In this way, the Euclid's algorithm in the second embodiment of the present embodiment allows the execution of the Euclid's algorithm under the condition s₁₅≠0 for coefficients of the syndrome equation S(z) and reduces the number of Galois-field operations necessary for the execution of the Euclid's algorithm. Under the other conditions, the execution of the Euclid's algorithm is impossible. However, there is extremely little probability that some errors exist in the received signal, that is, the syndrome equation S(z)≠0, and the coefficient s₁₅of the syndrome equation S(z) is 0. Therefore, there is no problem in practice.

[0147] As described above, the Euclid's algorithm in the second embodiment of the present invention allows the execution of the Euclid's algorithm depending on the coefficients of the syndrome equation S(z) and reduces the number of Galois-field operations necessary for the execution of the Euclid's algorithm, to accommodate an increase in the speed of processing.

[0148] The Euclid's algorithm in the second embodiment of the present invention has performed initial setting for the polynomials A(z) and L(z) as

[0149] A(z)=s_k−2z^k−1+s_k−3z^k−2+ . . . +s₀z,

[0150] L(z)=z,

[0151] when s_k−1≠0 for the coefficients in the syndrome equation

[0152] S(z)=s_k−1z^k−1+s_k−2z^k−2+ . . . +s₀,

[0153] where k>0, k is an integer, and s_k−1, . . , s₀are elements of a Galois field. By these means, the Euclid's algorithm in the second embodiment has allowed the execution of the Euclid's algorithm, under the condition s_k−1≠0 for the coefficients of the syndrome equation S(z), and reduced the number of Galois-field operations necessary for the execution. However, the condition on the coefficients of the syndrome equation S(z) may be different from the above. For example, even if, regardless of the coefficients of the syndrome equation S(z), the initial setting for the polynomials A(z) and L(z) is performed as

[0154] A(z)=s_k−2z^k−1+s_k−3z^k−2+ . . . +s₀z,

[0155] L(z)=z,

[0156] the execution of the Euclid's algorithm under the condition s_k−1≠0 for the coefficients of the syndrome equation S(z) is possible and the number of Galois-field operations necessary for the execution can be reduced.

[0157] The Euclid's algorithm in the second embodiment of the present invention is characterized in that, in the Euclid's algorithm that performs initial setting for the polynomials A (z), B(z), L(z), and M(z) from the syndrome equation

[0158] S(z)=s_k−1z^k−1+s_k−2z^k−2+ . . . s₀,

[0159] where k>0, k is an integer, and s_k−1, . . , s₀are elements of a Galois field, and obtains an error-locator-polynomial by performing Galois-field operations, the method of the initial setting sets the above polynomials as

[0160] B(z)=s_k−1z^k−1+s_k−2z^k−2+ . . . +s₀,

[0161] M(z)=1,

[0162] and, depending on the coefficients of the syndrome equation S(z), as

[0163] A(z)=s_k−2z^k−1+s_k−3z^k−2+ . . . +s₀z,

[0164] L(z)=z.

[0165] The Euclid's algorithm in the second embodiment allows the execution of the Euclid's algorithm, depending on the coefficients of the syndrome equation S(z), and reduces the number of Galois-field operations necessary for the execution of the Euclid's algorithm, to accommodate an increase in the speed of processing.

[0166] FIG. 5 is a flowchart illustrating the method of initial setting in the Euclid's algorithm in a third embodiment of the present invention. In the Euclid's algorithm in the third embodiment of the present invention, according to the method of initial setting illustrated in FIG. 5, initial setting for the polynomials A(z), B(z), L(z), and M(z) is performed from the syndrome equation

[0167] S(z)=s₁₅z¹⁵+s₁₄z¹⁴+ . . . +s₀

[0168] based on a signal encoded with a Reed-Solomon code, where s₁₅, . . . s₀are elements of the Galois field GF(28). Then according to the general Euclid's algorithm after initial setting illustrated in FIG. 20, Galois-field operations are performed to obtain the error-locator-polynomial σ(z) . In the Galois-field operations, processing for reducing the degrees of the polynomials A(z) and B(z) is performed. When at least one of the degrees of the polynomials A(z) and B(z) becomes equal to or less than 7, the processing is terminated.

[0169] Examples of operations in the Euclid's algorithm in the third embodiment of the present invention illustrated in FIGS. 5 and 20 are described in the following.

[0170] The first example of operations in the Euclid's algorithm in the second embodiment of the present invention described previously is also a first example of operations in the Euclid's algorithm in the third embodiment of the present invention. This example of operations uses the same syndrome equation as the one in the first example of operations in the Euclid's algorithm described previously. For the coefficients of the syndrome equation S(z), s₁₅, . . . , s₈≠0 in this case.

[0171] The polynomials A(z), B(z), L(z), M(z) after initial setting in the present example are the polynomials A(z), B(z), L(z), M(z) after the first Galois-field operations in the first example of operations in the Euclid's algorithm of the prior example. As a result, the number of Galois field operations before obtaining the error-locator-polynomial σ(z) is five, that is, one less than in the first example of operations in the Euclid's algorithm of the prior example.

[0172] The second example of operations in the Euclid's algorithm in the second embodiment of the present invention described previously is also a second example of operations in the Euclid's algorithm in the third embodiment of the present invention. This example of operations uses the same syndrome equation as the one in the second example of operations in the prior Euclid's algorithm described previously. For the coefficients of the syndrome equation S(z), s₁₅≠0, and at least one of s₁₄, . . , s₈is 0 in this case.

[0173] The polynomials A(z), B(z), L(z), M(z) after initial setting in the present example are the polynomials A(z), B(z), L(z), M(z) after the first Galois-field operations in the second example of operations in the Euclid's algorithm of the prior example. As a result, the number of Galois field operations before obtaining the error-locator-polynomial σ(z) is three, that is, one less than in the second example of operations in the Euclid's algorithm of the prior example.

[0174] A third example of operations in the Euclid's algorithm in the third embodiment of the present invention is described in the following. This example uses the same syndrome equation as the one in the third example of operations in the prior Euclid's algorithm described in the equations (3). For the coefficients of the syndrome equations S(z), s₁₅= . . . =s_n=0 and s_n−1≠0, (n≦15; n is an integer) in this case.

[0175] Syndrome.

[0176] S(z)=FEz¹³+D8z¹²+9Fz¹¹+D8z¹⁰+09z⁹+9Dz⁸+E7z⁷+B7z⁶+91z⁵+0Bz⁴+6Bz³+79 z²+FDz+90

[0177] After initial setting $A\left(z\right)=D8z^{15}+9{\mathrm{Fz}}^{14}+D8z^{13}+09z^{12}+9{\mathrm{Dz}}^{11}+E7z^{10}+B7z^9+91z^8+0{\mathrm{Bz}}^7+6{\mathrm{Bz}}^6+79z^5+{\mathrm{FDz}}^4+90z^3$ $B\left(z\right)={\mathrm{FEz}}^{13}+D8z^{12}+9{\mathrm{Fz}}^{11}+D8z^{10}+09z^9+9{\mathrm{Dz}}^8+E7z^7+B7z^6+91z^5+0{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90$ $L\left(Z\right)=z^3$ $M\left(Z\right)=1$

[0178] After first Galois-field operations $A\left(z\right)={\mathrm{ECz}}^{14}+7{\mathrm{Az}}^{13}+7{\mathrm{Az}}^{12}+C1z^{11}+83z^{10}+4{\mathrm{Dz}}^9+{F0z}^8+C1z^7+F1z^6+{\mathrm{FAz}}^5+C6z^4+{\mathrm{EDz}}^3+A9z^2$ $B\left(z\right)={\mathrm{FEz}}^{13}+D8z^{12}+9{\mathrm{Fz}}^{11}+D8z^{10}+9z^9+9{\mathrm{Dz}}^8+E7z^7+B7z^6+91z^5+{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90$ $L\left(Z\right)=z^3+63z^2$ $M\left(Z\right)=1$

[0179] After second Galois-field operations $A\left(z\right)=1{\mathrm{Az}}^{13}+87z^{12}+A1z^{11}+87z^{10}+2{\mathrm{Cz}}^9+8{\mathrm{Cz}}^8+43z^7+{\mathrm{FFz}}^6+62z^5+z^4+22z^3+97z^2+40z$ $B\left(z\right)={\mathrm{FEz}}^{13}+D8z^{12}+9{\mathrm{Fz}}^{11}+D8z^{10}+9z^9+9{\mathrm{Dz}}^8+E7z^7+B7z^6+91z^5+{\mathrm{Bz}}^4+6{\mathrm{Bz}}^3+79z^2+\mathrm{FDz}+90$ $L\left(Z\right)=z^3+63z^2+4\mathrm{Ez}$ $M\left(Z\right)=1$