JPH03195217A - Eucledian algorithm circuit - Google Patents

Abstract

PURPOSE:To make the entire circuit scale small by using a division means obtaining quotients for plural Eucledian algorithm units in common for the plural Eucledian algorithm units connected in cascade and differentiating the timing of obtaining the quotients in the plural Eucledian algorithm units. CONSTITUTION:A quotient and a residue RiX when a polynomial including a 1st input polynomial Ri-1X as its factor is divided by a 2nd input polynomial Qi-1X are obtained and the entire quotient lambdaiX so far is obtained from the former quotient and a 3rd input polynomial lambdai-1X. Plural Eucledian algorithm units 41A-41Z with 1st, 2nd and 3rd output polynomials from the residue RiX, the 1st and 2nd input polynomials and the entire quotient are connected in cascade. A division means 42 obtaining the quotient for the plural Eucledian algorithm units is used in common. Then each of the Eucledian algorithm units uses sequentially the division means 42 to obtain the quotient. Thus, one division means 42 is enough for the purpose and then the entire circuit scale is made small.

Description

[Detailed description of the invention] The present invention will be explained in the following order.

A. Field of industrial application B. Summary of the invention C. Prior art C1. Explanation of an encoder for an error correction code. C2. Explanation of the overall configuration of a decoder for an error correction code (Fig. 9). C3. Conventional error location using Euclid's mutual division method. Explanation of the polynomial derivation circuit (Figs. 10 and 11) C4 Explanation of the conventional improved error locator polynomial derivation circuit (Figs. 12 and 13) D Problem to be solved by the invention E Solving the problem Embodiment G, explanation of mutual division unit used in one embodiment (FIGS. 14 to 18) G2 Description of error locator polynomial derivation circuit of one embodiment (first embodiment)
(Fig. 2) Explanation of a more specific configuration of the G3 mutually exclusive unit (Fig. 3, Fig. 2)
Figure 4) Explanation of other examples of the G4 mutually exclusive unit (Figures 5 and 6) G1 Explanatory diagram of other embodiments of the present invention) I] Effects of the invention (Figures 7 and 8 A) Industrial effects FIELD OF THE INVENTION The present invention relates to a Euclidean mutual divider circuit suitable for application to, for example, an error correction code decoder.

B. Summary of the Invention The present invention relates to a Euclidean mutual divider circuit suitable for application to, for example, an error correction code decoder, and relates to a Euclidean algorithm that calculates the quotient and remainder when a polynomial including a first human polynomial as a factor is divided by a second input polynomial. At the same time, find the quotient of the whole up to that point from the quotient and the third human polynomial, and calculate the remainder, the first
A plurality of mutually dividing units are continuously connected, each of which makes the input polynomial or the second input polynomial and its total quotient a first output polynomial, a second output polynomial and a third output polynomial, and By sharing the division means for calculating the quotient and making the timing for calculating the quotient different for each of the plurality of mutual division units,
The number of dividing means, which is relatively large in circuit scale, is reduced to one, thereby making it possible to reduce the overall circuit scale.

C. Prior Art C1. Description of Error Correction Code Encoder Digital processing technology for recording and reproducing audio signals, video signals, etc. in the form of digital signals is becoming widespread. An important technology in this digital signal processing technology is error correction code encoding and decoding technology. Error correction codes include BCH codes in a broad sense, Goppa codes, etc., and the present invention can also be applied to these error correction codes, but in this specification, Reecl-- which is a special case of BCH codes
Only 3olomon codes are handled.

In the Reed-Solomon code, the finite field CF (21
N) (m is an integer of 1 or more) is associated with each symbol. Also, if the irreducible generator polynomial of the finite field CF (2''') is G(X) and the root of G(X)=O is α, then each element of the finite field CF (211'), that is, each symbol can be expressed as a power of α.Furthermore, this α
The power αh (+ is an integer) can be expressed as an m-bit binary number in vector representation, and this vector representation is convenient in digital signal processing.

To encode the Reed-5 olomon code, first define the following parity check matrix H using the above α.

In this case, n is the code length, t is the number of symbols that can be corrected, and the original information is (n-2t) symbols U. ~u,,
□, -0, parity information of 2 symbols p. -22
4,□I, the transmission code word f can be expressed as a vector having n symbols as elements as follows. still,〔·
...] 1 indicates a transposed matrix.

f −(PoP+""Pzt-+uou+..."tln
-zzj-+) '... (28) Then, the encoder encodes the parity information symbol p so that Hf = 0...(3) holds true. Determine ~pzt-+. Also, the transmission code word f is expressed as a polynomial by f(X)
Then, f (X)=po + p+X ++・++ ++)z
t-+X2t+uoX2t-1-...+un-zt
-+X"-'""(2B), and this formula (2B)
α, α2. ..., α2t can be expressed as follows by sequentially substituting α2t.

f(α)−Of(α2) −〇 ,..., f(α2
t)=0...(4) Explanation of the overall configuration of the C2 error correction code decoder (Figure 9) If the transmission error is e for the transmitted code word f, then the received code word r is expressed as r in vector representation. =f1e...(5A)
Then, when this 2 (5A) is expressed as a polynomial, r (X)
= f (X)→-e (X)= rO+r+X'(-
...-+r, l-+X''...(5B) In the Reed-3 olomon code, assuming that the code length is n and the number of parity information symbols is 2, transmission errors other than O in the transmission error e Error correction can be performed when the number of error symbols is L or less.

FIG. 9 shows the overall configuration of an error correction code decoder. In this FIG. 9, (1) is a syndrome generation circuit, and this syndrome generation circuit (1) is a parity check matrix A syndrome S is generated by multiplying 1 by the received code word r. In hectorian representation, this syndrome S is S = (S, S 2 ... 52t)
t... (68),
In polynomial expression, 5(X)=SI+S2X+S3χ2+ ” ” + S
zt X 2t...(6B). When 5=Hr is expressed using each element, it becomes as follows.

Sj-Σ r, α”=r(α') (j = L2+...-
・2t)...(7B) However, the polynomial expression of the transmission error e is expressed as e(X)-eoX
+e, X2+−−−−+e, l−, X”−’,
Using the condition in the encoder of equation (4), equation (7
B) can be expressed as follows.

S J= e (α') (j = L2. = =2t
) = ... (7C) In Fig. 9, (2) shows the derivation circuit of the error locator polynomial, and this derivation circuit (2) of the error locator polynomial is derived from the syndrome polynomial 5(X) (
In fact, the error locator polynomial σ(X
) and each coefficient of the error evaluation polynomial ω(X) are calculated, and these coefficients are supplied to an error position detection circuit (3) and an error pattern calculation circuit (4).

In this case, when an error occurs at the j-th position from the beginning of the received code word r (ie, when e is ~0), αJ is called the error position. Then, let the number of non-zero elements of the transmission error e be ν (ν≦t), the error position of these ν non-zero elements (error symbols) is Xl, the error pattern is Y, (i = L2. ...ν), then each of the ν error symbols is (X, .

Y, ), and equation (7C) can be expressed as follows.

S, H = e (α') - Σ YIXtj (j = L2.・
-, 2t) Equation (7D) shows the equation of can. However, in order to easily obtain =L2+...,ν) for the unknown quantity (x8°y;) that satisfies 2(7D), the error locator polynomial σ(X) and the error evaluation polynomial ω X) will be introduced.

σ(X)=TT (1-XX,) =1+σ1X+σ X2+...+σ, Xν...
(8) ω(X)=S(X)−ty(X)(modX2t
)...(9) From equation (8), σ(X+-')=O(i=L2.....
, ν) holds, so if the coefficient σ of this error locator polynomial σ(X) is found, α−' (j = 0.1.・
...nl) to σ(X) sequentially to obtain σ(α−')−
The error position xt (1=L2+ . . . , ν) can be detected by performing a complete search for α−″ when 〇.

On the other hand, error position X. Let Yl be the error pattern for the error pattern Y, using the error evaluation polynomial ω(X).
It is known that can be calculated as follows.

(10) As described later, the error locator polynomial σ(X) and the error evaluation polynomial ω(X) can be derived from the syndrome polynomial S (X) by Euclidean's algorithm. Then, the error position detection circuit (3) in FIG. 9 detects the error position MX from the error position polynomial σ(X), and generates a digital signal that becomes high level "1" at the error position. is supplied to one input terminal of each of the ant gate group (5). In addition, the error pattern calculation circuit (4) is calculated using the formula (10
) is applied to the other input terminal of the AND gate group (5) at each error position. ), a vector representation of each coefficient of the transmission error polynomial e (X) is generated in time series. Then, each coefficient of the polynomial r (X) of the received code word is transferred to a delay circuit (
Errors are corrected by adding the hector representation of the coefficients delayed by a predetermined time in step 7) and the vector representation of each coefficient of the transmission error polynomial e(X) using mod 2 adder group (6). A vector representation of each coefficient of the polynomial f(X) of the transmitted codeword is determined. Koreba mod 2
This uses the fact that addition and subtraction are the same operation.

Explanation of the conventional derivation circuit for error locator polynomials using C3 Euclid's algorithm (Figures 10 and 11) Two polynomials r-+(X) and r o(X) are given, and deg (order) If ro≦degr−+,
In Euclidean's mutual division method, the following division is repeatedly executed.

r-+(X)-q 100-r o(Xl+r 1(X
i), deg r 1< deg r a...(I
IA) ro (Xl=qz(XL ri(X)±r 2(X)
), deg r z < deg r...(IIB
) ri-zoo=q=(Xi rJ-+(Xl+rj(X
), degr;<degr;-+...(IIY) r J-+0O-q j++(Xi-r;tJJ
-・-(11Z) Then, the finally divisible non-zero r; (X) is the greatest common polynomial (GreatestCommon D) of r(X) and ro(X)
evisor: GCD).

Furthermore, the following theorem can be derived based on Euclid's algorithm of mutual division. That is, two polynomials r-+(X).

ro(X) is given, deB r ,≦deg r
−, and the CCD is h (X), then U(X) ・r−+(X)+V(X) ・ro(X)=
h(X)...(12)? There exist U(X) and V(X) that satisfy degU
Both deg V are smaller than deg r −I. U(X
) and V[X), use U−+(χ)=0. Uo(X)=i
... (138)V-, (X)=1. V
, (X)=0 (13B), and the quotient q appearing in formulas (IIA) to (11Z).

Using (i=1+2+..., j-1-1), Ui(X), V, and (X) are calculated from the following equations.

Ui(X) = qt(X), Ut-+(X)+tJ+-
z(X)...(14A)V, (X)-q +(X)
・VH-+(X)+V+-z(X)...(14B)
In this case, (-1)''''Vj(X) becomes U(X), and (-1EUj(X) becomes V(X).

Formula (11) to (IIZ) and formula (148), (14
When Euclidean's algorithm in B) is applied, the error locator polynomial σ(X) and the error evaluation are obtained from the syndrome polynomial 5(X) (Equation (6B)) by the algorithm of steps (100) to (105) shown in FIG. It is known that a polynomial ω(X) can be obtained.

Step (100) If the upper limit of the number of symbols that can be error corrected is t, then r
−+(X) and ro(χ) respectively)(2 and S(X
) as U-1(X) and U. (X) is 0 and 1 respectively
Set to .

Step (101) Set the step number i to 1.

Step (102) The quotient of rt-z(X) divided by ri-1(X) is qt(X
), the formula (IIY) with j replaced by i and the formula (
14A), calculate r + (X) and Ui (X).

That is, r + (X) - r tz (X) Q + (X) r
;-+(X)...(15A) Ui(X)=Ut-z(X)+qH(X)Ut-+(X
)...(15B) Step (103) Check whether the order of ri(X) has become the (t-1) order or less. When degr+(X)≦t-1, the process moves to step (105), and when degr+(X)>tl, the process moves to step (104).

Step (104) Increment step number 1 by 1 and return to step (102).

Step (105) δ times Ui(X) becomes the error locator polynomial σ(X), and r
The error evaluation polynomial ω(X) is (-1) δ times t(X).

δbaσ. It is a constant to set (the 0th order coefficient of equation (8)) to 1, and in actual calculations, only X for which σ(X i) = 0 is a problem, so it can be set to δ-1. .

Furthermore, since addition and subtraction are the same in the finite field CF (2'') u-, (-1)' can also be set to 1.

FIG. 10 shows a virtual circuit (specific configuration of the conventional error locator polynomial derivation circuit (2)) for executing the algorithm shown in FIG.
) to (8Z) are mutually exclusive units having the same configuration as a whole, and (98) to (9Z) are respectively identical to step (10) in FIG.
The main calculation unit that calculates qi (X) and rt (X) in 2), (IOA) to (10Z) are U and (X), respectively.
It is a sub-computation unit that calculates . In addition, the initial values r−+(X)−X”+ro(X)−3(XLU
−+(X), U.

(X), these functions reduce the mutually divisible unit to 1
(ro(X), rt(X), U).

(X), Ui(X)), (r, (X), r2
(X), U, (X), U2(X)), etc., and ω(X) and σ(X) are output from the mutually dividing unit (8Z) at the rear end.

In this way, when Euclid's algorithm is used, a systolic structure (systolic-array) can be created by cascade-connecting mutually dividing units (8A) to (8Z) with the same configuration.
There are benefits that can be taken by building a yard.

However, the problem is how to realize division between the polynomials r = -z (X) and r + - + (X) in the main calculation units 1-(9A) to (9Z).

C4 Explanation of the conventional improved error locator polynomial derivation circuit (Figures 12 and 13) This conventional improvement divides the above-mentioned division between polynomials and reduces it to division between the coefficients of those polynomials. This algorithm is based on Euclidean algorithm, and this algorithm is TBEE Trans, onCompute
rs, Vol, C-34, No, 5. May 19
85. It was proposed in pp. 393403. This improved algorithm is basically based on equation (12
), and in the i-th iterative step r
t(X)-X''10λ, (X)-5(X)=Rt(X)・
...(16) Polynomials Ri(X), r 1(X), λ that satisfy
, (X) are calculated in order. The algorithm is then stopped when the order of the remainder Ri(X) becomes less than the first order. This algorithm is shown in steps (106) to (114) in FIG.

Step (106) If t is the number of symbols that can be error corrected, -FT@, then Ro(X), Qo(X), λo(X)μo as initial settings.
(X), r o(X) and η0(X) respectively as X2tS
(X), 0, 1.1 and O.

Step (107) Set step i to 1.

Step (108) Difference between the order of Ri-+(X) and the order of Qi-1(X)! , -1, and calculate R+-+ (X) and Qi-1(X
) are respectively a, -3 and s, -.

Step (109) Depending on the order difference, the sign of -8, if Ni-1≧0, proceed to step (110) and proceed to step (112), and if ffi+-+<O, proceed to step (111). Proceed to step (112).

Step (110) (normal mode) 1 i-1≧O
This is the operation when the order of Rt-+ (X) is higher than or equal to the order of Q+-+ (X), and R4(X
), λrCX>, r t (X).

Ri(X)-Ri-+(Xl+(a t-+/b+-+
)Qi-+CX1. X"-'(17/l) λI(X)-λ1-1(X)+ (a l-1/b
1-1)/I l-1(Xi, X"-'... (1
7B) r, 0O−r i−+(X) ten(a +−1/ b
+-+) 77 r-100-X"-'... (1
7B) Also, Qi(X)=Qi-, (X), μ, (X)-μ1
−1(XLη, (X)−ηi−, (X). Then, the division R,−, (X)/Qi−1(X) is the division between the highest order coefficients a i−1/b i -1.

Step (111) (cross mode) n, -1<Q i.e. Ri-, (X) (7) Order power Q+-+
This is an operation when the order is smaller than the order of (X), and Ri(X), λ+(X), and r=(X) are calculated using the following formula.

R+oO=Qi-+fXl+(b+-+7 a+
-+) Rr-+CO-X '-'... (18A) λtoo-μ, -1(3)+(b r-+7 a 1-
1) λ, -1 flash x
a ;-+) 'r +-+(XL X-"-'...
...(18C) Also, Qi(X)=R4-+(X), μt(X)-λ1
−1(X)77 +(X)=T +−+(X). This corresponds to exchanging R1-1(X) and Qi-+(X).

Step (11, 2) Check whether the order of the remainder R, (X) in equation (16) has become smaller than the t order, and if the order of R, (χ) has become smaller than the t order, step (114) If it is the tth order or higher, the process advances to step (113).

9 Step (113) Increment step number 1 by 1 and return to step (108).

Step (114) As a final process, λ8(X) and Ri(X) are made into error locator polynomial σ(X) and error evaluation polynomial ω(X), respectively.

In this case, i is 2t.

FIG. 12 shows a specific configuration of the conventional improved error locator polynomial derivation circuit (2) for executing the algorithm of FIG.
(110) are mutually exclusive units having the same structure as a whole. For example, in the first mutually exclusive unit (118),
(12A) and (13A) are a pair of switch circuits, (
14A) and (1511) indicate another pair of switch circuits, and the input ports of these switch circuits (12A) to (15A) are R0(X), QO(X), and λ0(X), respectively.
and the coefficients of μo(X). degRo(X)
deg Q.

<x>=i. is 0 or positive, the switch circuit (L2
A) to (15A) each transmit the coefficients supplied to the human-powered boat directly to the output boat side. on the other hand,! .

If 0 is negative, switch circuits (12A) and (13A)
The switch circuit (1
4A) and (15A) operate as if they intersect.

The coefficient appearing at the output port of the switch circuit (12A) is connected to the dividend input port of the divider (19A) and the adder (2O
A) to one input port of the switch circuit (13
The coefficient appearing at the output port of A) is supplied to the divisor capo-1- of the divider (19A) and one input port of the multiplier (23A), and the quotient obtained first in the divider (19A) is inputted as data. The multiplier (2
3A) to the other input port of this multiplier (23
The output of A) is supplied to the other input port of the adder (2OA). In addition, the switch circuit (148) and (15/l
) are added to the coefficients appearing at the output ports of the respective adders (21Δ).
and one input port of the multiplier (24A), and supplying the coefficient held in the register (22A) to the other input port of the multiplier (24A);
The output of this multiplier (24Δ) is sent to the adder (21A) at 4.
Supplied to the b-side input port.

Note that the adder, multiplier, and divider in this example are all finite field G F
It performs operations between the elements of (2″).

In addition, (16A) to (18A) each indicate a delay register consisting of a D-type flip-flop, and a start flag signal SF for synchronizing with the highest order coefficient of the input coefficients is transmitted through the register (16Δ). It is supplied to the next-stage mutual division unit (IIB), and the switch circuit (13A) and (
The coefficients appearing at the output ports of 15A) are stored in respective registers (
17A) and (18A) as coefficients of the polynomials Ql(X) and μm(X) to the next stage mutual division unit (IIB)
and the output capacitors of adders (208) and (218)
The coefficients appearing in I. are supplied to the next-stage mutual division unit (IIB) as coefficients of polynomials R, (X) and S(X).

Other mutually exclusive units (1] [) , (IIC) ,...
... are also input polynomials R7-1(X), Qi-, (X
), λ1-1(X).

From the coefficients of μi−+(X), the polynomial R+(XLQ;(X), λ+(XLμ1
The coefficients of (X) are generated.

To explain a specific application example of the circuit shown in FIG. 12, the irreducible generator polynomial G(χ) is a finite field CF of
Each symbol is expressed by each element of (2'). That is, if the root of X'+X+1=0 is α, then each symbol is α
It can be expressed as a power of Furthermore, if the code length n is 11 and the number of correctable symbols t is 2, then the number of original information symbols is 7, and the number of parity information symbols is 2 (・-4
). In this case, let the vector of original information be m,
Specifically, m = (αth cxlOo:9cx”a7rx
6a5) ' - (19), then the symbol p of parity information is obtained from equation (3).

~p3 are each 0. α12. α6. α′1, and the transmitted code word f is as follows.

f-[0αI2α6αIIα11α10α9α8α7α
6αs)t...(20) Also, the vector e of transmission error is e=(α3α9000000000)'...(
21), there are two error symbols in the received codeword r(=f+e). In this case, the syndrome polynomial 5(X
) is as follows, 5(X)-3,-1,-32X-1,,-33X2+-
34X"3 -α12+α5X+αI OX 2+α8 X 3...
(22) The initial values of each polynomial in step (106) in FIG. 13 are as follows.

RO(X)=X', QQ(X)-3(X)λa(X
)=0. tto(X)=1.60(X)=1,770
(X)-〇As shown in FIG. 12, RO(X) and λ. (
The coefficients of X) are divided in order from the coefficients of higher order (X4)
(11A), Q, (X) and μ. The coefficients of (X) are sequentially divided into a division unit (IIA)
) and raises the start flag signal SF to high level "1' in synchronization with the highest order coefficient.

(Operation in mutually exclusive unit (IIA)) In this case, f
io=deg Ro(X) deg Qo(X)=4
Since -3-1≧0, the switch circuit (1211) ~
(15A) allows each supplied coefficient to pass through as is. Also, the highest order coefficient a of R, (X) and QO(X). And. are 1 and α8, respectively, so the register (22Δ) has a o/bo=1/α8=α7
is set, and R, (X) and X + (χ) are respectively as follows.

R,0O=X'+α7(αB X 3+α1°X2+α
(5
=1,7 I(X)-1, η1(χ)-〇. still,
In equations (17A) and (17B), XZO, that is, the multiplication of X, is Q in advance in this example.

(X) and μ. It is executed by shifting the coefficient of (X) by one digit to the higher order side, and register (17A)
and those Q by way of (18A).

(X) and μ. The coefficient of (X) is shifted by one digit to the lower order side.

(Mutual division unit) (Operation in IIB)) ff+=d
eg R+(X) deg R+(X)=3 3=0
Therefore, the switch circuits (12B) to (15r() pass the supplied coefficients as they are. Also,
The highest order coefficients a and bl of R, (X) and Q, (X)
are α2 and α8, respectively, so al/b+-α2/α8-α9 is set in the register (22B), and R2(X
) and X2(X) are respectively as follows.

R2(X)-R+(X)+ (at/l)+)QI(X
)-α6X2]-α9X+α'' X2(X)-X1(X)→-(at/b+)μ+(X)
-α2x+α9 Also, Qz(X)-QI(XLμz(X)=Lrz(X
)−1, η2(X)=O.

(Operation in mutual division unit (11C)) ffz=de
g R2(X) deg Q2(X)=2-3=1×0, so the switch circuits (12G) and (13C) and the switch circuits (14C) and (15C) each calculate the coefficients of the input polynomial. Cross them and transmit to the output port side. Therefore, the operation is substantially the step (111) of FIG.
). Then, since the highest order coefficients a2 and b2 of R, (X) and QZ(X) are α6 and αB, respectively, bz/az-α8/α6-α2 is set in the register (22C) and R3(X ) and X3(X) are respectively as follows.

Ra(X)=Qz(X)+(bz/az)R2(X)
・X=αl4xz+α4X+αI2 X3(X)-〇 z(x)-1-(b z/a 2)
X2(X), X-αQ X 2+αth X+1 Also, CL+(X)= R2(X)= cr'X 2+
α9X + tx'.

μ3(X)=/z(X)=α7X+α9.73(X)=
77z(X) ten α2X−α2xlη, (X)−1.

(Operation to enter mutual division unit I-(LID)) fl s=
deg R3(X) deg Q3(X)= 2 2
= 0, the switch circuits (120) to (15
D) allows each supplied coefficient to pass through as is.

Also, since the highest order coefficients a and b3 of R3(X) and Q3(X) are α14 and α6, respectively, register (2
2D) has a 3/ b 3= α”/ tx6= c
x'' is set, and R4(X) and λ4(X) are as follows.

R4(X)=R3(X)+ (a,/b3)Q3(X)
−αIOX+α5 λ4(X)=λ3(X)+(a3/b3)μ3(X)−
α9 X 2+α12X+α8 Also, (L(X)=(lh(X), μ4(X)=μ:+
(X) There is a chance. In this case, deg R4(X)=1
< 2, so step (112) in Figure 13
The algorithm stops and the error locator polynomial σ(X
) and the error evaluation polynomial ω(X) are σ(X) − λa(X) = α9X2 + αI2X + αθ7 - α8 (αX2 + α'x+1) ω(X) − α''X + α5. In this example, G(α) − α4+α”-1=O, σ(α0)-α8(α+α4+1)-〇, σ(
α-I)-α7(α]α'+4)-0 holds, and X, -
α0. Two error positions, X2-α1, could be detected accurately (see equation (21)).

As mentioned above, according to the algorithm shown in FIG.
If the order of (X) does not decrease by one degree but decreases by two or more degrees, the process proceeds to the normal mode of step (110) even if E t-<O. In addition, in this algorithm based on Euclidean algorithm, R, (
In principle, the order of
IIB), 2L pieces are required.

D Problem 8 to be solved by the invention When using the Reed-5olomon code, 3-symbol correction has already been realized in applications that require real-time performance (clock frequency of about 15 MHz), such as digital VTRs. On the other hand, for applications such as optical discs that do not require real-time performance, up to 8-symbol correction has been realized.

Furthermore, recently there has been a demand for the development of a decoder for multiple error correction codes in which the code length n is about 150 and the number of error-correctable symbols is about 16.

However, in the conventional error locator polynomial derivation circuit (FIG. 12) described above, if the number t of symbols that can be corrected is 16, the mutual division units 1-(118), (IIB), . . .
2, that is, 32 symbols, must be connected in cascade, resulting in an inconvenience that the circuit size increases in proportion to the number t of symbols that can be corrected.

In view of this point, the present invention provides the number of error-correctable symbols t
The purpose of this study is to propose a Euclidean mutually dividing circuit that can increase the circuit size and reduce the circuit scale.

E. Means for Solving the Problems The Euclidean mutual division circuit according to the present invention has a first input polynomial Rt-+ (X
) as a factor as the second input polynomial Q+−+(X
), the quotient and remainder R4(X) are determined, and the entire quotient λ, (X) up to that point is determined from the quotient and the third input polynomial λ1-1(X), and the remainder Ri(X ),
The first input polynomial Ri −1(X) or the second input polynomial Qi−+(X) and their total quotient λ8(X) are converted into the first output polynomial, the second output polynomial, and the third output polynomial, respectively. Mutual division unit formed with the output polynomial) (41A) to (41Z)
A plurality of mutual division units (41A) to (41Z) are connected in cascade, and the division means (42) for calculating the quotient are shared among the plural mutual division units, and the timing for calculating the quotient is made different in each of the plural mutual division units (41A) to (41Z). This is how it was done.

F Function According to the present invention, the plurality of mutually exclusive units (
41A) to (41Z), the timing for calculating the quotient is different, so each mutual division unit I・(41A
) to (41Z), their quotients can be obtained by sequentially using the dividing means (42). Therefore, the division means (42
), the overall circuit scale can be reduced.

Normally, the output of the first mutual division unit (4 rare) gradually propagates to the last mutual division unit (41Z), so these mutual division units (41Δ) to (41
There is no conflict in the timing of finding the quotient in Z). However, when a loop structure is used as in the example shown in FIG. 7, or when data is processed continuously, it may be necessary to intentionally vary the timing at which the quotient is calculated.

G Example G, Description of mutual division unit used in one embodiment (FIGS. 14 to 18) The mutual division unit 1- used in the conventional improved error locator polynomial derivation circuit shown in FIG. (IIA)～(
IID) has the following two disadvantages.

1 ■ deg Rt-+(X)<deg Qt-+(X)
holds true and the input coefficients intersect, then its Rt, (X
) becomes 0, the divider (19A) ~
A calculation error occurs because the division in (190) cannot be performed. This is the mutually exclusive unit (11A) in the example in Figure 12.
) to (LID) are caused by the fact that the order can always be lowered by only one order.

■ Initial value Q of Q, -1(X). Even when the coefficient of the highest degree of the syndrome polynomial S (X), which is (X), is 0, the division in the divider (19A) cannot be performed and a calculation error occurs.

In this embodiment, the mutually exclusive unit shown in FIG. 12) (IIA
) to (LID) are used, so the mutual unit used in this embodiment will first be explained.

FIG. 14 shows the configuration of the mutual division unit (25) of this example, and in this FIG. 14, (26) to (28) are delay registers, respectively, and these delay registers (26),
Start flag signal SF is applied to (27) and (28), respectively.
, the coefficients of the polynomial Qi-1(X), and the coefficients of μi-,(X). The output signal of register 2 (26) is used as a start flag signal SFO to the subsequent circuit. (29) to (31) respectively show switch circuits that transmit the supplied coefficients in parallel or in a crosswise manner, and variables dRi-, dRi-, and dRi-, which do not indicate the degree of the polynomial, are input to the two input ports of the switch circuit (29), respectively. and dQt-+, and an adder (32) adds -1 to the variable appearing on one output port of the switch circuit (29) to create a variable dR.
8, this variable dR, and the switch circuit (29)
The variable dQi appearing at the other output port of is supplied to the subsequent circuit.

Further, the coefficients of the polynomial R1-1(X) and the register (2
7) and supplies the coefficients output from the switch circuit (30
) divider (33) by the coefficient appearing at one output port of
is supplied to the dividend input port of the divider (33) and one input port of the adder (34), and the coefficient appearing in the other input port of the switch circuit (30) is supplied to the divisor input port of the divider (33) and one input port of the divider (37). input port. Further, coefficients of polynomials λi-, (X) and registers (28) are provided at one and the other input ports of the switch circuit (31), respectively.
and supplies the coefficients appearing at one and the other output ports of the switch circuit (31) to one input port of the adder (35) and one input port of the multiplier (38), respectively. , the quotient output from the divider (33) is held in a register (36), and the held quotient is supplied to the other input port of each of the multipliers (37) and (38). and (38) are supplied to the other input ports of adders (34) and (35), respectively. Polynomial Ri(X) from the output port of the adder (34), the other output port of the switch circuit (30), the output port of the adder (35), and the other output port of the switch circuit (31).

The coefficients of Qi(X), λ, (X) and μ8(X) are supplied to subsequent circuits.

FIG. 15 shows an example in which two mutually exclusive units (25A) to (25Z) having the same configuration as (25) in the example shown in FIG. 14 are connected in cascade. In FIG. 15, the first stage mutual division unit (25A) includes initial values of each variable and polynomial (syndrome polynomial 5(X), X2, etc.).

), and the error locator polynomial σ(X) (=λ2t(X)) and the error evaluation polynomial ω(X) (=R2t(X)) are taken out from the mutual division unit (25Z) at the final stage.

Referring to steps (115) to (125) in FIG. 16, the algorithm based on the improved Euclidean algorithm applied to the example algorithm in FIG. 14 will be described. shall be. Also,
This algorithm also basically uses polynomials Rt(X), r that satisfy equation (16) in the first iteration step.
1(X) and λ8(X) are calculated in order, but the processing for r+(X) is omitted.

Step (115) R6(X), Qo(x), λo(X) as initial settings
, μ.

(X), dR, and dQo are each given by the syndrome polynomial 5.
(X), X2t, 1.0. 2 Set t-1 and 2t. R6(X) compared to the algorithm in Figure 13
and Q. The initial values of (X) are exchanged and λ. (X) and μ
. The initial value of (X) is also exchanged. According to this, Qi
Initial value Q of (X). The coefficient of the highest degree of Xzt, which is
A) Inconveniences (2) to (LID) can be resolved.

Step (116) Set the step number i to 1.

Step (117) -5 is calculated from the difference between dR8- and dQi-+, and R1
−1 (X) no dRt−+ the coefficient of order and Q, −, (X) no d Q.

Let the following coefficients be a, -1 and s, -1, respectively. In this case, the highest order coefficient of the syndrome polynomial S (X), which is R, (X), can be 0, so the value of the coefficient a8 can also be 0.

Step (118) Depending on the sign of the order difference n1-1, if R8,, l≧0, proceed to step (119) and step (123); if l i-+ < O, proceed to step (120). move on.

Step (119) (Normal mode)! , -1≧0, that is, dR, is greater than or equal to dQi-, and R, (X), λ, and (X) are calculated using the following equations.

R, (X)=R, −+(X)+(a +−+/ II−
+LX-Q+-+(X)... (238) λ8(X)-λt-+(X)+(a i-1/bi-1
)-X・μ1-1(X)...(23B) Also, Qi(X)=Q+-+(X), μ, (X)-μ,
-, (X).

Let dRH=dR+-+ L and dQ+=dQ+-+. This is the result of replacing the division R1-+(X)/Q;-+(X) with the division a +-1/b i-1 between the virtual highest-order coefficients. In formulas (238) and (23B), (a r-+/b t-+) is multiplied by X,
In this example, e =-+ = d Rr-+ d Qi-
This is because + is normally controlled to be ±1.

Step (120) If Ri-, dR,- of (X), next coefficient is 0, step (121) to step (123)
If a, -1 is not O, step (122
) to step (123).

Step (122) (, cross mode) Ri-+ (
This is the operation when the order of Q, -, (X) is larger than the coefficient of X) and the coefficients a, -4 are not O. Rt-1(X) and Qi- +(X)
By exchanging , Ri(X) and λ,(X) are calculated using the following equation.

R4(X)=Qi-1(X)+(bi-1/a 1-1
)-X, R4-1(X)...(24A) λ1(X)-u r-+ (X) + (b +-+/
ai−+) ・X ・λ1−1(X)・・・(24
B) Also, Qi(X)-Ri-, (X), μ, (X)-λi
,,I(X)d R(-d Qi-+ L d Qt
= d Rr-+ and proceed to step (123).

Step (121) (shift mode) dR,- of R, (X), the next (highest order) coefficient at-1 is O, and the actual order of this Ri-1(X) is (dR
, -, -1) This is the operation in the following cases. In this case R
R+-+ so that division by i-, (X) is possible
(X) is multiplied by X, Ri-, and (X) is shifted to the higher order side. That is, the following equation holds true.

Ri(X)=X −Ri−, (X)...
・(25A)λ1(X)−X・λi−,(X)
-...(25A) Also, Qt(X)-Qi-+(X
), μ, (X)−μ+−1(X).

d R,= d R,, □, -L d Ri= d Q
As i-1, proceed to tip (123). in this case,
Since dR, decreases by 1, when the highest order (dR4th order) coefficient of Ri(X) becomes a number other than O, dR,
will match deg(R4(X)), and only then will cross mode processing be performed in step (122). As a result, the disadvantage (2) in mutually exclusive units l-(IIA) to (LID) in the example of FIG. 12 is resolved.

Step (123) Check whether the step number i has reached 2t, and if it has not reached 21, proceed to step (124), and if it has reached 2t, proceed to step (125), which is the final process.

Therefore, even if the number of error symbols is only ν (ν x t), the entire error locator polynomial derivation circuit always performs steps (117) to (123) in FIG. 16 only 2 times. It will be repeated. However, one mutual division unit executes each of steps (117) to (123) only once. In this case, step (117)
In the solution obtained in 9 after repeating the operation of ~(123) 2 times, dR2t is the error correction polynomial σ
It represents the number obtained by subtracting 1 from the order ν of (X). On the other hand, due to the shift mode operation in step (121), the polynomial R2t(X) is shifted to the higher order side by (L-1ν), so in order to obtain σ(X) and ω(X), ．． It is necessary to shift (X) and Rzt(X) to the lower order side using shift polynomials P (X), which will be described later.

Step (124) Increment the step number i by 1 and return to step (117).

Step (125) As final processing, the number of error symbols ν, the shift polynomial P
(X) is calculated from the following formula.

Seed d Rzt + 1 P(x)-Xt Then, using this shift polynomial P (X), an error locator polynomial σ(X) and an error evaluation polynomial ω(X) are calculated from the following equations.

σ(X)=λZt(X)/P(X)...
・(26)0 ω(X)=R2t(X)/P(X)...
・(27) Mutual division unit in the example in Figure 14) To explain a specific application example of (25), as shown in Figure 17,
Four mutual division units (25A) to (25D) having the same configuration as the mutual division unit I-(25) are connected in cascade to constitute an error locator polynomial derivation circuit. Also, finite field CF (2
'), and represent each symbol by each element of
Similarly to the example in FIG. 2, the code length n is set to 11, the number of correctable symbols is set to 2, and the transmission code word f and transmission error vector e are expressed by equations (20) and (21), respectively.

In this case, the syndrome polynomial S (X) is expressed as Equation (22)
The initial values of each variable and each polynomial in steps (11, 5) in FIG. 16 are as follows.

RO(X)=S(X), QO(X)=X'λo(X
)-1, II o(X)-〇, d Ro=3. d
Qo=4, and as shown in FIG. 17, R, (X) ~
μ. The coefficients of (X) are supplied to the mutual division unit (25Δ) in order from the highest order coefficient, the values of dR and dQo are supplied to the mutual division unit (25A), and the start flag is set in synchronization with the highest order coefficient. The signal SF is raised to high level "1'."

In the mutual division unit (25A), the difference in order is 1°-d
Rod Q o = 3 4-1 < O and a, = α8. Since b, = 1, the operation is the first
The process moves to step (122) (cross mode) in FIG. 6, and the switch circuits (29A) to (31Δ) respectively cross and transmit the supplied variables or coefficients. Also, b is in the register (368). /a. = 1 / tx
8-rx7 is set, and R, (X) and λ, (X) are respectively as follows.

R, (Xl-X'ten α7.X・(α8X″+αI OX
2+α5X+α12)=α2X 3+α12X2+
α4X λ+(Xl-0+α'・X=α7X Also, Q, (X)-R6(X)-3(X), μl(χ)
−λ.

(X) = 1, but these results are similar to the mutually dividing unit (11^
) is the same as the processing result.

Similarly, the mutually exclusive units in the example in Figure 17) (25B) to (2
5D) are respectively equal to the processing results in mutual division units (IIB) to (110) in FIG.
(X)) and error evaluation polynomial ω(X) (= R4(X
)) is obtained. In the example of FIG. 17, both the number of correctable symbols and the actual number of erroneous symbols ν are 2.
Therefore, the shift polynomial P(X) at step (125) in FIG. 61 is 1.

Next, consider the case where the code length n is 150 and the number of error-correctable symbols is 16.
Repeat steps (117) to (123) in the figure 32 times (
You need to repeat step 2). Therefore, if the mutually dividing units are simply connected in cascade as in the conventional example, 32 mutually dividing units (25) of the example shown in FIG. 14 are required. Furthermore, assuming that the received code word is transmitted one symbol at a time in synchronization with the clock pulse CK, it is assumed that the received code word is transmitted symbol by symbol in synchronization with the clock pulse CK.
Assuming that the period is ITc, as shown in FIG. 18A, there are received code words 1 . Il, I,
... is transmitted at a cycle of 150Tc. Also,
In the case of t-16, the highest degree of syndrome polynomial 5(X) is 31 (-2t-1), and the number of coefficients of polynomial X2t is 33 (= 2 t +1). Therefore, if 32 mutually exclusive units (25) of the example in FIG. 14 are simply connected in series as in the conventional example, the received code words (, r, n, m, . . . The period of 33Tc after the end of reception of (398), (39B),
(39C), -..., respectively, are supplied with pairs of 33 coefficients of the syndrome polynomial 5(X) and the polynomial)(zt) to the first mutually dividing unit of the cascaded circuit.

Also, one mutually exclusive unit is 1 of S (X) and X2t
It takes 4 clock pulses (4TC) to process a pair of coefficients.
In short, each pair of coefficients needs to pass through 32 division units, so 32×4Tc-128T
c, the period (40
A) , (40B) , (40C) , ... are the error locator polynomials σ(X) corresponding to those received code words.
The coefficients are sequentially output from the rear-end mutual division unit. Since no input is made to the leading mutual division unit during the period ■T, which is the period 150TC minus the period 33Tc, this period IT can be considered as a kind of idle time. Therefore, in general, if the number t of error-correctable symbols for the code length N3 satisfies the relationship N>2t, simply cascading mutually dividing units as in the conventional example requires a large circuit scale. Not only that, but also the idle time length becomes longer.

Gz-Explanation of the error locator polynomial derivation circuit of the embodiment (first
2) Hereinafter, an embodiment of the Euclidean mutual divider circuit according to the present invention will be described with reference to FIGS. 1 and 2. This example describes an error locator polynomial derivation circuit (
This corresponds to (2) in FIG. ) to which the present invention is applied. In addition, in this example, two alternating units having the same structure as the example in FIG. 14 are used, and the data delay time in each alternating unit is 4 clock pulses (4
). Further, the algorithm used in each division unit of this example is the same as the algorithm based on the improved Euclidean division method shown in FIG.

FIG. 1 shows the circuit for deriving the error locator polynomial of this example, and in this FIG. 2t mutually connected units cascaded in configuration, (42)
is a divider that executes division between the elements of the finite field CF (2″′), and there is a hass line that outputs the dividend NMI and divisor DNM from mutual division units (4LA) to (41Z), respectively, and a path that manually calculates the quotient SHO. Derive the line, supply the dividend NML and divisor DNM to the dividend manual port and divisor manual port of the divider (42), respectively, and connect the output port of the divider (42) to the path line that inputs the quotient SHO. Do as you will.

Further, the first mutual division unit I- (41A) has a variable dR.

d Q, and the polynomial R, −, (X), Qt−+ (
d R,, d QO which is the initial value of X), 1 +-+(X), μ+-+(X).

R, (X) (=S(X)), Q, (X) (=X2t)
, λo(X).

μ. (X) and the mutually exclusive unit 1-(41Z) at the rear end.
Then, the error locator polynomial σ(X) (=λzt(X)) and the error evaluation polynomial ω(X) (=RZt(X)) are extracted.

A specific configuration example of the divider (42) in the example of FIG. 1 is shown in FIG. 2, and in this FIG.
OM, (44) is a matrix-vector multiplier, (45)
is a representation conversion circuit that converts the original representation of a finite field from a vector representation to a matrix representation. Each element of the dividend X expressed as a vector is supplied to the input port of this representation conversion circuit (45), and this representation conversion circuit Each element of the matrix representation T(X) of the dividend χ outputted from (45) is supplied to the matrix element input port of the multiplier (44).

In addition, each element of the divisor y expressed as a vector is supplied to the address bus of the backlight generation ROM (43), and the backlight y'' of the divisor y output from the data bus of the backlight generation ROM (43). Each element of the ver1-le representation is supplied to the hector element input port of the multiplier (44).The matrix representation of the elements of the finite field is described in Japanese Patent Application Laid-Open No. 14483/1983.
It is disclosed in Publication No. 4.

According to the example in FIG. 2, in order to calculate the quotient X/y between the dividend X and the divisor y, the backlight y-1 of the divisor y is first determined and the dividend X is multiplied by this backlight y''I.

In this case, since the backlight generation ROM (43) and the expression conversion circuit 7 (45) operate in parallel, the calculation time required for division can be significantly reduced.

Furthermore, each element of the finite field G F (2″′) is expressed as a power of the root α except for 0, so if the dividend X and the divisor y are α″ and αJ, respectively, the quotient Z is αs− It can be easily obtained as s. Therefore, the divider (42) is
For example, the exponents i and j of the power representation of the dividend X and the divisor y
A ROM table for calculating , a subtractor for calculating i-j, and an R for calculating the vector representation of α゛-・ from this index i-j.
It can also be configured from an OM table.

To explain the operation in Fig. 1, the first mutual division unit 1-
The initial data shown in step (115) in FIG. 16 is supplied to (41A). In addition, a start flag signal S is synchronized with the highest order coefficient of the polynomial among these initial data.
Set F to high level "1", and each mutually exclusive unit (4
1A) to (41z) each identify that the highest order coefficient of the polynomial has been supplied since the start flag signal SF has reached the high level "1pa".

Therefore, the 8-processed data in the first mutual division unit (41A) is supplied to the next stage mutual division unit (41B), and the SF-1 flag signal SF supplied to this mutual division unit (41B) goes high. When the level reaches "1", the operation shown in FIG. 16 is started in this mutual division unit (4]-B).Similarly, as the high level "1" portion of the start flag signal SF propagates, each mutual division The unit starts the operation shown in FIG. 16, and finally the coefficients of the error locator polynomial σ(X) and the error evaluation polynomial ω(X) are obtained from the mutual division unit (41Z) at the rear end.

In this case, the high level "1" portion of the start flag signal SF is divided serially on the time axis for a period of a predetermined clock pulse after a predetermined period has elapsed since the start flag signal SF became high level helper 1. Because it is within
Division in each mutual division unit l-(41A) to (41Z) is never executed at the same timing. Therefore, according to this example, it is possible to serially and accurately execute the division for the mutual division units (41A) to (41Z) by using one divider (42).
Since only one circuit is required, there is an advantage that the overall circuit scale can be reduced even if the number t becomes large.

Here, with reference to FIG. 17, each mutually divided unit (25A)
The timing at which division is performed in ~(25D) will be considered in detail. For example, mutual exclusion unit) (25A)
In the divider (33A), the highest order coefficient of QO(X) is calculated. (=1) is the highest order coefficient a of R8(X). (−
αl+) and the obtained quotient α7 is held in the register (36A). That is, the divider (33^) is a polynomial RO(X) and Q. Since only the highest-order coefficients of (X) are divided, the time required for the division may be about 1 cross pulse (ITC) to 2Tc. Also, the quotient obtained by the divider (33A) is R8(X
) and all other order coefficients of QO(X) are held in that register (36A) until processing is completed. Therefore, the divider (33A) is in an idle state after the division for the period from ITC to 2Tc is completed. Other mutual division units (25B) ~ (25D) Middle divider (33B) ~
Similarly, (33D) is in an idle state when no division is performed for each mutual division unit. In view of this point, the present invention provides dividers (33A) to (33D).
It is a collection of .

On the other hand, for example, the multiplier 3A) in the mutual division unit (IIA) must always perform multiplication of a new coefficient by its quotient α7 and has a short idle state. Multiplier (23A
) to (23D) are difficult to combine into one.

A more specific explanation of the configuration of the G3 mutually exclusive unit (Fig. 3,
Figure 4) In the example in Figure 1, the data delay time is 4 clocks (4T).
Figure 3 shows a specific example of a synchronized configuration of a mutual unit with a delay time of 4T. Portions and signals corresponding to those in FIG. 14 are given the same reference numerals, and detailed explanation thereof will be omitted.

1 In FIG. 3, (51) to (68) are delay registers each consisting of a D-type flip-flop, and (69) to (7
4) are two-man-powered take selectors, and the data selectors pairs (69), (70), (71), (7
2) and pairs (73) and (74) correspond to switch circuits (29), (30) and (31) in FIG. 14, respectively. (75) indicates a comparison circuit, and this comparison circuit (75
) generates a comparison signal REV which has a low level of 0 when dR=dQi≧0 and a high level of 1 when dRi−1dQi<0, and converts this comparison signal REV into one of the following (77). Supplied to the input terminal. (7
6) shows a zero detection circuit, and this zero detection circuit (76)
generates a zero detection signal RZ that becomes high level "1" only when the coefficient of the polynomial R, , (X) becomes O, and connects this signal RZ to the other negative logic input terminal of (77) The output signal of this AND gate (77) is held in a register (58) as a signal CR3, and this signal CR3 controls switching of data selectors (69) to (74).

Also, a register (5) is provided on the input side of the data selector (71).
4), two registers (59) and (63) are provided on the output side of this data selector (71), and similarly registers are provided before and after the data selectors (72) to (74). Then, the output data A of the register (59) is taken out as the dividend NML through the buffer circuit (46), and the output data B of the register (60) on the output side of the data selector (72) is taken out through the buffer circuit (47). Divisor DNM
The outputs of the buffer circuits (46) and (47) are set to high impedance when they are not strobed. Also, start flag signal SF is sent to registers (26), (51), (52) and (
53), the flag signals SF1, SF2 . SF3
and SFO, and register (5
8) and register (36) with flag signal SF3.
, (67) and (68) and buffer circuit (46)
and (47), and the other registers are controlled by the clock pulse CK.

In this case, the intermediate signals are indicated by the symbols shown in FIG. 3, and the variables dRi-1+dQi-I and the polynomial R8(
Assuming that X) ~ μ = I (X), the mutually dividing unit (2
5A) variables dR,, dQ and polynomial R8(X)~μ. Assuming (X) (i.e., Qi-.

(X)=Qo(X)=X'), the various signals in FIG. 3 change as shown in FIG. 4 in synchronization with the clock pulse CK.

Note that the frequency of this clock pulse CK is assumed to be about 20 MHz.

In FIG. 4, the coefficients of the polynomials Ri(X) to .mu., (X) are generated with a delay of 4Tc relative to the coefficients of the polynomials Ri-, (X) to .mu.m-+(X). Therefore, it can be seen that the delay time in the example of FIG. 3 is 4Tc. Furthermore, this fourth
The timing chart in the figure shows that the division between the elements of the finite field in the divider (42) is completed within IT, and that the multiplication and addition of the elements of the finite field by the multiplier (37) and the adder (34) is completed within IT. It is assumed that the process ends within ITc.

Description of another example of the G4 mutually dividing unit (FIGS. 5 and 6) Another example of the mutually dividing unit will be explained with reference to FIG. 5. This example is a configuration example in which 2 T c is consumed for division between elements of a finite field, and in FIG. 5, where parts corresponding to FIG. Later, a delay register (88) is further provided, and a register (53) is provided.
) is output from the register (
36), (67) and (68).

Further, the output port of the data selector (71) is connected to the buffer circuit (47) via the register (78), and the output port is further connected to the adder ( 34), the output port of the data selector (72) is connected to the buffer circuit (46) via the register (81), and the output port is further connected to the buffer circuit (46) via the registers (82), (83) and (60). and connect to the multiplier (37). In this case, register (78
) and (81) are controlled by the flag signal SF2. The buffer circuits (46) and (47) also receive flag signals SF2. through a two-man OR circuit (48) and a register (49). The controller is controlled by SF3. Similarly, registers (84), (85) and (61) are arranged between the data selector (73) and the adder (35),
Registers (86), (87) and (62) are arranged between the data selector (74) and the multiplier (38). Further, FIG. 6 shows a timing chart for the example in FIG. 5 under the same conditions as the example in FIG. 3. According to this example, IT is used for division.
It can be seen that the total delay time is 5TC because it requires more time by c.

G3 Description of Other Embodiments of the Present Invention (FIGS. 7 and 8) Hereinafter, other embodiments of the Euclidean mutual divider circuit according to the present invention will be described with reference to FIGS. 7 and 8. This example corresponds to an error locator polynomial derivation circuit (corresponding to (2) in FIG. 9) in which the code length n is 150 and the number of correctable symbols is 16 in a Reed-5o IPmon code decoder.

) to which the present invention is applied. Also, in this example, the third
In addition to using eight mutually exclusive units with the same configuration as the example in the figure,
It is assumed that the data delay time in each division unit is 4 clock pulses (4To). Further, the algorithm used in each division unit of this example is the same as the algorithm based on the improved Euclidean division method shown in FIG.

Figure 7 shows the circuit for deriving the error locator polynomial in this example. In Figure 7, (89) is the data bus, (9
0) is a data selector, and this data bus (89)
via the syndrome polynomial S (X) and the polynomial x2
The coefficients of t, etc. are supplied to one input port of the data selector (90). (91A) to (91H) are mutually exclusive units each having the same configuration as the mutually dividing unit shown in FIG. Mutual division units I-(91A) to (91H) are connected in cascade between the output port and the input port of the delay register (92). (93)
indicates a data bus, through which the output port of the delay register (92) and the other input port of the data selector (93) are connected, and a part (93a) of this data husk 93) is connected. ), the coefficients of the error locator polynomial σ(X) and the error evaluation polynomial ω(X) finally obtained are taken into the subsequent circuit numbers (not shown). Also,
In this example, as in the example in Figure 1, the mutually exclusive unit) (9
Divider (42) shared by 1A) to (911())
Allocate.

The operation of the example in FIG. 7 will be explained with reference to FIG. 8. In this example as well, as shown in FIG. 8A, received codewords I, II, III, . It is transmitted at a cycle of 150Tc. Also, since the number of error-correctable symbols is 16, the syndrome polynomial S
The order of (X) is 31 (-2t -1), and the initial value is S (X) and the coefficient of polynomial X2t is 33
(, = 2 t + 1.) A string is supplied. Note that the polynomial λ in step (115) in FIG. (X)
,μ. (X) and variables dR, , dQo are also supplied accordingly.

Therefore, it takes 337C until all the initial values S (X) and coefficients of Since the delay time in the delay register (92) is ITo, mutual division unit 1-(9
The total delay time from 1Δ) to the delay register (92) is 33 (=4·8+1.)TC, which is set equal to the time required for all of these coefficients to be supplied.

Therefore, in this example, as shown in FIG. 8B, transmission code word 1.
33Tc period from the end of reception of n, I, ... (948), (94B), (94G),
..., the data selector (90) selects S (X
) and Xzt coefficients, etc. are supplied to the first mutual division unit ) (91A). As a result, intermediate processing data of these 33 sets of data is stored from the mutual division unit (91A) to the delay register (92).

Next, the data selector (90) is switched so that the data output from the delay register (92) is supplied to the leading division unit (91A). As a result, as shown in Figure 8C, D and Figure 8, following period (94A) <3
3Tc period (95A), (96A) and (97^
) has a mutual division unit (91A) and a delay register (92).
The 33 sets of intermediate processing data held between the Processing is performed by moving around the loop one turn at a time.

Then, as shown in Figure 8F, 3 following the period (97A)
During the 3TC period (98A), part of the data bus (93) (
Error locator polynomial σ(X) and error evaluation polynomial ω(X
) are extracted. Similarly, period (94B), (9
4C) In each period following . . . , the intermediate processing data also circulates in the loop.

According to this example, the 33 sets of initial data supplied via the data bus (89) each go around the loop four times, and the loop includes eight mutually dividing units (91).
Since A) to (91H) are included, each of these 33 sets of initial data is equivalent to having passed through a total of 32 mutually dividing units, and the coefficients of the error locator polynomial can be accurately determined. In this case, while the conventional example requires 32 mutually dividing units, the present example requires 1/4 of that, 8
Since it is only necessary to use the mutual division units (91A) to (91H), there is an advantage that the circuit scale can be significantly reduced.

Furthermore, in this example, as shown in FIG. 8, received codewords 1.
The coefficients of the error locator polynomial σ(X) are obtained with a delay time of 132(-33x 4 ) Tc after the completion of reception of the 18th
Delay time when using the conventional method shown in the figure: 128Tc
The delay time is almost the same compared to . Therefore, according to Example 0, even if the circuit scale is reduced to 1/4, there is an advantage that the delay time hardly changes. In addition, the idle time IT in this example is as shown in FIG.
This is the time after subtracting Tc, and is significantly shortened compared to the example in FIG.

Generalizing the example in FIG. 1, let us consider the number of mutual division units required in the case where the code length is n and the number of correctable symbols is t. In this case, the syndrome polynomial S (X
) and polynomial > (Since there are (2t + 1) sets of coefficients, etc. of zt, the maximum number of times that a series of mutually dividing units can be used repeatedly is R, RM = 1nt (n / (2t + 1))
” ” (28). 1nt(A) means an integer not exceeding A.

Furthermore, when a series of mutually dividing units is used repeatedly R times, the number G of the mutually dividing units is G = int(
(2t -1)/R) + 1...(2
9), and once (one round) with these series of mutually exclusive units.
The time TC in lock pulse units required to process
The upper limit Tu of K is To=int((n-1)/R) +1 ・=
・It becomes (30). Furthermore, initial coefficients etc. are (2t-14
) Since the string must be supplied, the lower limit T of that time TCK.

is T++-2t + l
...(31). Therefore, according to equation (29), by increasing the number of times R of repeated use, the number G of mutually dividing units can be reduced to one at the minimum. In this case, the delay time T. A delay register is provided to keep K within the range of TD≦Tcx≦TV.

Incidentally, as in the example in Figure 7 (in the case of n=150, L-16, R=int(150/33)-4, G=int(31
/4) Ze1-8, To-4nt (149/4)
+ 1 = 38, TD = 33, and these conditions are satisfied.

Also, to describe the timing of division by the divider (42) in the example in FIG. 7, the period (94A) to (94A) to (9
4D), the divider (42) is a sequential division unit (
91^) to (91H), and in the period (95A) to (95H) that follow them, the divider (42)
again sequentially executes division for mutual division units l-(91A) to (91+1). Therefore, even if the configuration uses the mutual division units ) (91A) to (91H) repeatedly as in the example in FIG. 7, generally each mutual division unit) (91A) to
(The timing of the use of divider (42) by 911() does not interfere.

Furthermore, if the timing of use of the divider interferes with the configuration, the interference can be easily avoided by adjusting the delay time in the delay register (92). On the other hand, when different syndrome polynomials 5(X) are processed continuously, there is a risk that the timing of the use of the divider may interfere with each other. All you need to do is place a register.

As described above, the present invention is not limited to the above-described embodiments, and it goes without saying that various configurations may be adopted without departing from the gist of the present invention.

H Effects of the Invention According to the present invention, the division means for a plurality of mutually dividing units can be combined into one division unit.
Since the circuits can be combined into individual units, there is an advantage that the overall circuit size can be reduced even if the number of connected units increases.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an error locator polynomial derivation circuit according to an embodiment of the present invention, FIG. 2 is a block diagram showing an example of the divider of the embodiment shown in FIG. 1, and FIG. 3 is a mutual division unit of an embodiment. FIG. 4 is a timing diagram for explaining the operation of the example in FIG. 3, FIG. 5 is a configuration diagram showing another example of the mutually exclusive unit, and FIG. FIG. 7 is a configuration diagram showing another embodiment of the present invention. FIG. 8 is a timing chart diagram explaining the operation of the example shown in FIG. 7. FIG. 9 is a diagram of an error correction code. Fig. 10 is a block diagram showing the overall configuration of the decoder; Fig. 10 is a block diagram showing a conventional error locator polynomial derivation circuit; Fig. 11 is a flowchart showing the conventional algorithm based on Euclidean algorithm;
Fig. 2 is a block diagram showing a conventional improved error locator polynomial derivation circuit, Fig. 13 is a flow chart showing an algorithm based on the conventional improved Euclidean algorithm, and Fig.
Figure 4 is a configuration diagram showing a mutually exclusive unit used in an embodiment of the present invention;
Part 15 is a block diagram showing a connection example of the conventional method in Fig. 14, Fig. 16 is a flowchart showing an algorithm based on the improved Euclidean algorithm used in an embodiment of the present invention, and Fig. 17 is a block diagram showing an example of connection of the conventional method. Fig. 14 is a block diagram showing an error locator polynomial derivation circuit configured by connecting examples in the conventional manner, 1st
FIG. 8 is a timing chart diagram for explaining the operation of the conventional system. (34) and (35) are adders, (37) and
(38) are multipliers, (41A) to (41Z) are mutual division units, (42) are dividers, (69) to (74)
are data selectors, (75) are comparison circuits, and (76) are respectively data selectors.
is a zero detection circuit, (90) is a data selector, (92)
is a delay register, and (93) is a data bus for data feedback. Agent Hidemori Matsukuma No. 142- Including Q JP-A-3-195217 (23) JP-A-3 195217 (24) JP-A-3 195217 (27) JP-A-3 195217 (29) JP-A-3 195217 (31): i-ku Kuan ζri

Claims (1)

[Claims] Find the quotient and remainder when a polynomial that includes the first input polynomial as a factor is divided by the second input polynomial, and also find the overall quotient up to that point from the above quotient and the third input polynomial. , a plurality of mutually divisible units are connected in cascade to form the remainder, the first input polynomial or the second input polynomial, and the quotient of the whole into a first output polynomial, a second output polynomial, and a third output polynomial, respectively. , A Euclidean mutual division circuit, characterized in that the plurality of mutual division units each share a division means for calculating the quotient, and the plurality of mutual division units each have different timings for calculating the quotient.