WO1997011530A1

WO1997011530A1 - Method and device for decoding burst error of reed-solomon code

Info

Publication number: WO1997011530A1
Application number: PCT/JP1995/001883
Authority: WO
Inventors: Yasuhiro Hirano
Original assignee: Hitachi, Ltd.
Priority date: 1995-09-20
Filing date: 1995-09-20
Publication date: 1997-03-27

Abstract

A method and device for decoding error correcting codes by which the position of a burst error can be calculated with an extremely small amount of calculation by calculating a syndrome Si (i=0, .., 2t-1) of t-multiple byte error correcting RS codes at a first step and calculating the (j) (j≤t) factors of an error position polynominal (Z)=1+σ1Z+..+σjZj, by using the syndrome Si at a second step. At a third step, the positions of the (j) burst errors are found with BP(α).η by retrieving a burst pattern equation which satisfies η=σ¿i?/BP(α) and σ(η?-1¿)=0 of the burst pattern equation BP(α)=1+αp+..αr determined by (j) integers, 1, p, .., r (1 < p < ..< r≤t). At a fourth step, the (j) burst errors are corrected by finding (j) error patterns. Thus, the positions of burst errors can be calculated by an extremely small amount of calculation.

Description

TECHNICAL FIELD The present invention relates to a method for decoding a parity error of a Reed-Solomon code and a decoding device.

The present invention relates to a decoding method and a decoding device for an error correction code, and more particularly to a decoding method and a decoding device suitable for correcting a burst error in a Reed-Solomon code. Background art

The digital transmission 'recording system' employs a code is re-correction technology that decodes the original information even if a friendship occurs during the transmission or recording 'reproduction process.

In general, on the transmitting side, a code S is formed by adding a check bit for detecting an erroneous detection or correction to information to be transmitted or recorded, and transmitting or recording is performed; and On the receiving side, errors are detected and K-correction is performed using the check bits added on the transmitting side.

Various codes have been devised so far for detecting or correcting such errors. Among them, a Reed-Solomon code (hereinafter referred to as an “RS code”) has been proposed. ) Is a code that corrects errors in the noise level, and is widely used in fields such as compact discs, digital VTRs, and digital broadcasting.

The t-checker RS code can correct up to t pit errors contained in the code word. Therefore, the t-checker RS code is a random code in which the code is randomly generated. »Res can be used as t random correct codes. In addition, t-fold 38 re-correction RS code, code K is concentrated in one place. The burst error that occurs when the burst error occurs can be used as a code for correcting the burst error of length t-pites.

However, in the prior art, the decoding process is complicated because the error correction is assisted by the decoding method according to the random error correction decoding procedure even for the burst error correction. Therefore, a method of decoding a burst error with a simple decoding process is desired. In particular, for compact discs and digital VTRs, burst errors due to scratches on the recording medium, etc. frequently occur, so it is extremely important to determine how to simplify the decoding process of the burst errors. The present invention has been made in view of the above-described SJ8, and has as its object to provide a decoding method and a decoding device that can perform a burst IS recorrection decoding process on an RS code extremely efficiently. Inventive invention

In order to achieve the purpose of the above K, in the present invention, the decoding method shown in FIG. To correct the re-permission K

That is, for the received code, a syndrome; S, (i = 0, 1, 2, 2,..., 2t-1) is calculated in the first step.

In the second step, using this syndrome S [, erroneous rearrangement »polynomial; hi-丄 + b! + B: + · · + + σ j Calculates the coefficient σ, (i = 0, 1, · ·, j) of j 偭 (j ≤ t) of Z Z.

In the third step, j integers; 1, p, q, ···, r (1 <p <q <-· <r≤ t), a perfect pattern equation; BP (α) = 1 + α + a + · ·-+ a Search for a perfect pattern equation that satisfies the relationship of γ σ, / Β Ρ α), force, and σ (γ) = 0: Β Ρ (α) 、 Ρ (ίϊ) · γ for j burst ki Β Β; γ · α, · · ·, Γ · a, γ ·, y

In the fourth step, the j burst error positions; γ ·, · · · ·, γ-, γ-a, // and the syndrome obtained in the first step; S [(i-0, 1, 2,..., 2 t — 1), j error patterns corresponding to the erroneous position; E..., Ε ,, Ερ, are obtained. The error pattern is corrected by adding the error pattern to a position corresponding to the above-mentioned error position.

The first, second, and fourth steps in this decoding method are the same as those in the conventional technique, but the third step is a completely different technique from the conventional technique. Which enables the calculation of the position.

The basis of the decoding method in the present invention is to calculate a burst error position て using the burst pattern equation in the third step described above; Β α (α). To help understand this theory and work, first consider the triple error correction RS code shown in Fig. 2 as an example, the position of the parse error, the return pattern, the syndrome, and the coefficient of the erroneous position polynomial. And a relational expression that holds between the burst pattern equation and

Figure 2 shows the codeword of a triple error correction RS code with code length η and number of information points η-6, and its generator polynomial G ₀ (X) is

σ ₀ (Χ) = (Χ-1) (Χ-α) (Χ-α ² ) (Χ-α ³ ) (Χ-α ⁴ ) (Χ-α ⁵ ) ... (Equation 1). The dot part in the code firewood shown in FIG. 2 indicates the region where the code error occurs, and the code new i + 2, i + 1, i-th position is a peri-pattern; E [ ₊ E1 _{+ 1} , Ε ₍ There is a parse error of length 3 bits. Therefore, the receiving polynomial; Υ (Χ) is the transmitting polynomial; W (X) plus the L polynomial EB (X). .

Y (X) = W (X) + EB (X) (Equation 2)

EB (X) = (E _{i +} , X + E _{t + 1} X + E [) X

In the present invention, X (i = 0, 1,... J) is a polynomial representing a position B where a code error has actually occurred in a burst error region having a length of j bytes. BP (X), a new burst pattern equation that uses 1 as the coefficient of X when there is a code error in 1) and 0 when there is no code error, is introduced. In the code S of the triple error correction R S code in FIG. 2, this burst pattern equation; BP (X) is

BP (X) = 1 + Χ + X ¹ (Equation 3)

Becomes

Now, the syndromes; _St (i = 0, 1, 25) are given by the following equations, respectively.

(Equation 4)

Here, the transmission polynomial; W (X) is divisible by the generator polynomial; G ₀ (X), so the syndrome of this perfect game is

(Equation 5)

Next, Eq. 5 is transformed to eliminate E, EE, and γ = α and Eq. 3 Perth preparative pattern equations; Β Ρ (α) = 1 + α + α 2 can be obtained and the following equation organized by.

BP (a) y S ₂ + a BP (a) r ^I S, -l- a ⁱ r ⁵

BP (a) r S, + a BP (a) y ² S ₂ + a ³ Y ⁵ (Equation 6) BP (a) r S4 + a BP (a) r ^l S, + ³ r ⁵

—That ’s wrong! Polynomial; σ (Z) is

σ (Ζ) = (1-Z) (1-a 'Z) (1-a Z)

(Formula Ί) = 1 + σ, Z + σ, Z + σ, Ζ

Where σ (α) = 0 (k = i + 2, i + 1, i). Substituting this relation into Equation 5 gives the following well-known relation:

(Equation 8)

From Equations 6 and 7, the error level! Between the coefficient of the polynomial;, γ, and the burst pattern equation; Β Ρ (a) = 1 + a + ²

(Equation 9)

σ (y) = 0

Can be derived,

In the above, Equation 9 is derived by taking a triple permutation positive RS code as an example, but Equation 9 is also valid for a t-weight correction RS code. In general, a burst tick of length t bytes is used. Ri's position polynomial; σ (Ζ) is

σ (Z) = (1-Z) (1-a Z)-

= 1 + (1 + a + ·,-+ a + a) a Z +-

= 1 + σ, Z + · · · · + _non-t Z

And the coefficient of the position polynomial;

σ = (1 + a + · '' + a + a) a = BP ta) γ Therefore, the relation of Equation 9 can be derived for a t-error-correcting RS code.

Then, add Equation 9 to γ and the burst pattern equation; パー Ρ (α) Product defined by the burst position polynomial; (a)

/ 3 (α) = Β Ρ (α) r (Equation 10)

Indicates the position where the bursting occurs.

The present invention is based on the following: y of equation 9 newly derived for the burst and the burst pattern equation; B8 relation of Β α (α); and 85 of the position locator polynomial of equation 10; β (α). The search for the position of the parse error is performed with extremely small number of operations using

Fig. 3 shows the burst pattern equation; B Ρ (α) in the t-ary positive RS code. The »real number in the figure is the actual code Is the number of occurrences. Then, the burst pattern equation BP (a) that can be taken for this number of S is listed for each of t = 2, 3, 4, and 5.

For example, at t = 4, the Noost pattern equation; B Ρ (α) is a kind of 1 when the number of errors is 1 ¾, and when 2 is 1 + α, 1 + ¹ , 1 + a ³ 3 kinds of votes, 3 = l + ίΐ10 α ² , 1 + a + a ³ , 1 + a ¹ + a ³ 3, 4 = Ι + α + ίΐ '+ α ³ is there,

Therefore, in the third step of the decoding procedure shown in FIG. 1 at the time of combining t = 4, the search by the burst pattern polynomial is performed once when the number of res is 1 and three times when the number of res is 2. In the case of 3, 3 times, and in the case of 4, only once, the position of the burst error can be obtained with extremely little hand.

Fig. 4 compares the worst value of the number of searches required to find the position of a burst error between the present invention and the prior art.

The numbers in parentheses in the figure are for the Chien search method used in the prior art. Is shown. In the prior art, when the number of errors is 2 or more, the number is n-1 times (n is the code length). In many cases, the code length n is about 100 to 200. Therefore, the present invention makes it possible to efficiently obtain the position of a burst error with a very small number of steps, from one-several to several tenths of the prior art.

As described above, in the present invention, a search is made for a burst pattern equation with a small number that satisfies the newly derived equation 9 with respect to the burst error, and the burst position polynomial of the equation 10 is used to find the burst error. The position can be obtained. Therefore, the position of the error can be calculated in a very small number of times compared with the prior art.

FIG. 1 is a schematic diagram of a decoding procedure for the RS code in accordance with the present invention, FIG. 2 is a schematic diagram of the RS code being close to burst, and FIG. FIG. 4 shows a burst pattern equation in a positive RS code. FIG. 4 shows a bad calculation amount in the third step of the third embodiment. FIG. 5 shows an entire block configuration of the first embodiment of the present invention. FIG. 6 is a diagram showing an element on GF (2 *) defined by a generator polynomial G (X) -X * 10X + 1, and FIG. 7 is a diagram showing the syndrome of the first embodiment. FIG. 8 is a configuration example of an operation IB, FIG. 8 is a configuration example of a multiplication circuit of the first embodiment, and FIG. 9 is a configuration example of a division circuit of the first embodiment. FIG. 10 is a diagram illustrating a second decoding procedure of the JS recorrection of the RS code according to the present invention. FIG. 11 is a diagram illustrating a second embodiment of the present invention. FIG. Best of Katachiso for carrying out

FIG. 5 is a block diagram showing the overall configuration of the first embodiment of the present invention. I will explain. The present embodiment is suitable for performing the RS error correction of the RS code by the decoding procedure shown in FIG.

In FIG. 5, 1 is a syndrome operation unit, 2 is an error position polynomial operation unit, 3 is a burst pattern detection unit, 4 is a peri-pattern operation unit, 5 is a delay unit, and 6 is an addition ffi.

t Double error correction Receiving code of RS code; Y0 is input to the syndrome calculation section 1 and the extension section 5.

The syndrome calculation unit 1 calculates the syndrome, which is the first step of the sign procedure, that is, performs the Hamama calculation shown in Equation 4 for the received code; Y0, and calculates the syndrome: S i-O, 1,... 2 t-1) is calculated. Then, this S.U-O, 1,..., 2 t—1) is output as a syndrome sequence; S, where S, = 0 (i−0,1,..., 2 t— In the case of 1), it is determined that there is no game, and a signal is output to EN; 0 is output. On the other hand, when at least one is S, ≠ 0, the signal is output to EN; 1 is output.

The re-position polynomial Hamari ffi2 calculates the Qi-position polynomial, the second step of the decoding procedure; the coefficient _{σ ι} of σ (Ζ), where ί = 1, 2, , 倌; when EN is 1, a syndrome sequence; a known syndrome for S as shown in Equation 8; S, and a coefficient; σ, the number of errors from §8. Calculate the coefficients σ, (i = l, 2, ···, j) of the error locator polynomial. Then, the individual loss of this K; j and the coefficients; o, (i = 1.2, ···. , j) are output as a coefficient sequence; σ.

Perspective pattern detection ffi3 calculates the erroneous position of the pallet which is the third step of the ffi hand, ie, when the signal is EN = 1, the singularity of the ri shown in Fig. 3 is specified by j. Γ is calculated by successively substituting BP (α) into Equation 9; and if there is a key that satisfies σ) = 0, the burst position polynomial shown in Equation 10; 3 (a) = Β Ρ (N) · Outputs the burst error position s found by γ as the error position a sequence; and outputs 0 to the signal; ED. If する (γ)-0 is not added, the correction is impossible because the position of the 珙 is unknown. Therefore, in this case, no output is output to the Qiri position sequence; No, and 1 is output to the ED;

The error pattern calculation unit 4 calculates the error pattern; Ei, which is the fourth step in the decoding procedure. That is, when the signal; EN is 1, the erroneous position sequence: β hysteresis sequence; Ei is measured at each error position; Ei is calculated; and an error pattern sequence is output; E is added. The adder 6 is a signal delayed by Noburo 5; Y0D error occurs. No place! Correcting the error by adding the error pattern corresponding to, and obtaining an RS code; YD that has undergone burst 18 correction decoding processing on the output.

In the following, a quadratic source polynomial; G (X) = X * + X + 1 Defined as an element on GF (2 «), and a triple error correction of t = 3 (15, 9, 3 ) Using the RS code as an example, the decoding work of this embodiment will be described in detail.

First, this GF (the element two above is shown in Fig. 6. The number of elements is 2 *, and each element is represented by a 4-bit vector from 0000 to 1 1 1 1. Also, if the root of primitive polynomial; G (X) is α, these elements can be represented by a power-of-representation.

GF (On the two above, the addition between elements is defined by the addition of vectors, that is, the addition of mod 2 between each element of the vector. For example, in FIG. The addition of α 'and ⁷ is

"+ α '= 0 1 1 0 + 1 0 1 1 = 1 1 0 I ="

Becomes

The multiplication and division between elements are defined by the following equations.

a a / a = a

For example, it ^s 'a = ii *, na ^ / na,: na' ¹ .

By the way, the triple error correction (15, 9, 3) R S code of t = 3 is represented by the following generator polynomial G. (X),

G ₀ (X) = (X- l) (Xa) (Xa ⁱ ) (Xa ³ ) (X- ⁴ ) (Xa ^s )

= X * + ct9 X ^s + na '' X '+ a Xs + ai Xz + c ^ X

Next, the decoding assistance according to the present invention is shown for some received codewords.

Example 1> Received codeword; When Y0 is Ο Ο Ο Ο Ο Ο Ο Ο Ο Ο Ο Λ Ο Ο Y Y

(1st step) Syndrome measurement

The operation shown in Equation 4 is performed on the received code S; Υ0, and the following syndrome is obtained.

S a

S, a

S a a a '

S aa ¹

S = aa ^{1 2} = a ¹³

S = aa ¹ '= a

[Second step] Calculating wrong position polynomial

Syndrome; S i ≠ 0 and S i S ′ + So S z-O, so the number of errors; j is j = 1, so the error locator polynomial is σ (Z) = 1 + σ, 、 and its coefficient; a ₁ -S ₁ ZS. = a :,

[Third step] Calculating the location of the pastry

Since the error j: j = l, the burst pattern equation; BP (N) = 1 as shown in Fig. 3. By substituting this into Eq. γ = σ, / Β Ρ ( α) = α 3/1 = a 3

a (y) = 1 + σ i γ = 1 + a a = 0

Get. Therefore, the burst position indicating the position of the burst error バース polynomial; β (a) is

β () = BP () · γ = a 3

The code error exists at the fourth (α ³ ) from the right end of the received code word. [4th step] Calculation of error pattern and correction

If the R re-pattern of the position of the burst error is assumed, the following equation is obtained from Equation 5.

Ε! = S = α

Therefore, add the fourth information from the right end of the received code word; a to this error pattern; E _{1 =} .. And the decoded code S with the corrected code S; YD = 0 0 0 0 0 0 0 0 0 Decode 0 0 0 0 0 0.

<Example 2> Received codeword; Y0 is 0 0 0 0 0 0 0 0 0 0 0 0 ³⁰ [First step] Syndrome calculation

The received code S; Y0 is subjected to the arithmetic operation shown in Equation 4 to obtain the following syndrome,

S 0 = α + '= a'

S i = α α ⁵ + a ¹ = 0

S = '-a ^{3 1} = a ¹³

S j = aa '+ a ³ a ³ = a ⁷

S _A = ^{, l} + ³ a * = a ^s

S j = a '* + a ^J a * = a' °

(2nd step) Calculate IS position polynomial

Syndrome; S [≠ 0, and S t S i + S o S, -na ⁷ , S, S ₂ S, + ε, ε, εο + Β, ε, ε, + ε, ε, εο θ So, the number of ss j = 2. Therefore, the error locator polynomial is σ (Z) = 1 + σ, Z + σ ₂ Z ² , and its coefficient is

Hi '-(S t S i + S s S o) no (S i S i + S i S ^-a ⁹

a _I = (S ₁ S, + S, S ₂ ) / (S ₁ S ₁ + S ₂ So) = a ⁴

Becomes

[Third step] Finding the wrong burst position

Since j = 2 as shown in Fig. 3, the burst pattern equation; BP (a) is of two types, l + a and 1+. Substituting this into Equation 9 sequentially gives

γ = σ ₁ / Β Ρ (α) = α / (1 + a) =, σ (a) = a

γ = σ ι / Β Ρ (α) = α / (1 + a) = a, σ () = 0

Thus, a burst position 31 polynomial indicating the position of the burst »it; β (a) is

β (a) = (\ + a ¹ ) a

Where the code exists at the second (α) and fourth (a ¹ ) places from the right code of the received codeword,

[4th step] | Calculation and correction of peri-pattern

Position Perth preparative error; alpha of »re pattern E ,, position; if alpha ³ of拱Ripata over down the E ₁ and, the following expression is obtained from the formula 5.

Ε, + Ε ₂ = S = α '

a 'E, + a E ₂ = S ₁ = 0

Solving this system of equations yields E, = a. Therefore, the fourth information from the right edge of the received code word: this Ribatan to a; -; in a ³ »Li pattern; E a, 2-th information E, adds =« No. code obtained by correcting a code error R; YD = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. Therefore, in the present invention, the calculation of the Qi rank B in the third step is performed. It can be performed in two operations. On the other hand, in the conventional Chien search method, 誤り = α (i = 1, 13, · · ·, 1, 0) is sequentially substituted into the error locator polynomial, and the value Calculate the value of which is 0 as the position of the error. In this example, i = 3 and 1 means 0, so 14 calculations are required.

<: Example 3> received codeword: Y0 is 0 0 0 0 0 0 0 0 0 0 0 Bingo of ^α α ζ α '0

[First step] Syndrome calculation

Useful codeword: Perform the operation shown in Equation 4 for $ 0 to obtain the following syndrome.

S 0 = α + a ¹ + a ³ a

S 1 = a ³ + ^z a ¹ + ^J aa

S j = aa '+ a ¹ * -ha ⁵ a ² = 1

S j = aa '+ ² ' + ³ a ³ = a ¹¹

S _t = a ' ¹ + a ¹ * + a ^J a ⁴ = 1

S 5 = aa ¹⁵ + a ² a ¹⁰ + a ⁵ a: ^s = na ³

[Second step] Calculation of angle position polynomial

Shin Drome; S [≠ 0 _{and,, S, S, S 2} + S, S, S 0 + S «S l S [+ S * S, S. = a, so the number of errors; j is j = 3. Therefore, the Qi position polynomial is σ (Ζ) = 1 + σ _ι Ζ + σ, Ζ ^ί + σ, Ζ, and its ^coefficient is

σ, = Ν 1 / U = ^{1 1}

σ, = Ν 2 / M = a ¹³

σ, = N 3 / U = a '

N 1 = S, S, S ₂ + S _s S ₁ S ₁ -l- S _< S, So + S »S _J S ol- S 4 S _J S ₁

+ s, s _s s,

N 2 = S _< S, S ₂ + S, S _s S ₀ + S _< S _s S, + S «S« So + S _s S, S ₁ + S _s S, S, N 3 = S 6 S, S _I + S ₃ S _s S, + S _< S «S ₁ + S _< S _s S ₂ -i- S 5 S _> S ₁ + S _t S, S,

M = S, S ₁ S ₂ -l- S * S ₁ S ₁ + S ₃ S, S o + S 4 S _l S o

Becomes

[Third step] Calculation of burst error position

Since R = j = 3, the burst pattern equation; BP (ct) is 1 + α + ² S, as shown in Fig. 3. Substituting this into equation 9 If

y = σ _ι / Β Ρ (α) = α / (1 + α + α) = α, σ (α) = 0, and therefore the rank of the burst! ! Β (α) is a position polynomial that indicates

β (a) = (I + a + a ¹ ) a

The code S is located at the second (N), third (α ¹ ) and fourth (α positions) from the right end of the received code fi.

[Fourth step] Calculate and correct R-return

Position of Pasuto拱Ri; alpha of »re pattern E ,, position; alpha ¹ of Κ Ripata over down the E i, position Y; if alpha, of K Ri pattern E _t, the equation 5 the following formula obtain,

E, + E, + E, = S ο = α "

a ³ E i + ^ι E j + a E _s = S! = α

a 'E _l + a ⁴ E ₁ + a ^, E, = S i = 1

Solving this speed equation yields E, = ^az , E, = <r '. Therefore, the fourth information from the right end of the received code S; α is this false return; E, = a. Decoding code 15; YD = 0 0 0; a ', K repattern; E, = a :, second information a, K return pattern; E, = a 0 0 0 0 0 0 0 0 0 0 0 0 Therefore, in the present invention, the calculation of the error position in the third step can be performed by one operation. On the other hand, in the conventional chain search method, Ζ = α (i = 1, 13,..., 1, 0) is sequentially substituted into the error locator polynomial, and the one that takes a value of 0 is defined as the error location. In this example, i = 3, 2, and 1 means 0, so 14 calculations are required.

Example 4> Received codeword; When Y0 is 0 0 0 0 0 0 0 0 0 0 0 a ² ³ a [First step] Syndrome calculation

Perform the operation shown in Equation 4 on the received codeword 0 to obtain the following syndrome,

S 0 = α + ¹ + a ³ + a = '

S 1 = α α ³ + N ² α ^ζ + ³ a + a = I

S 2 = aa '+ ¹ * + a ³ a ² + a = ⁴

S 3 = aa '+ a ² a * + ^{3 3} + a = a ¹

S = aa ¹¹ + a ¹ a * + ³ a * + a = a *

S5 = aa ^ls + ¹ a ¹⁰ + ^is + a = a '

[Second step] Re-position polynomial calculation

Shin Drome; S i ≠ 0 and,, 5, 5, 52+ 5 , 5, 50+ 545, 5, + S ^ S i So: Since the Do 'is ^3,偭数of拱Ri; j is, j = 3, cowpea Te, error position polynomial is o CZ sl + o! Z + ai Zz + O i Z 3, the coefficient of the Soviet Union,

σ 1 = N 1 / Μ = a ⁵

σ 2 = N 2 / M = a ³

σ, = N 3 / = a ^s

N 1-S s S j Sa + S s St S! + S ^ S i S o + S i S i So + S ^ S ^ S, + S, S _s S,

N 2 = S 4 S, S _J + S, S, So + S «S, S ₁ + S 4 S 4 S o + S 5 S ₁ S ₁ + S ₃ S, S

N 3 = S. S ₂ S _J + S, S _S S ₃ + S. S 4 S ₁ + S, S ₅ S _I -1- S _S S _J S ₁ + S, S _s S ₂

= S ₂ S ₁ S ₂ + SS _l S, + S _J S _s S o + S «S _I S o

Becomes

[Third Step] Calculation of Perspective Position

Since at j = 3, burst pattern equations as shown in FIG. 3;默Ri偭数. BP (a) is, 1 + a + alpha 1 type of ^ζ Substituting this into equation 9 ,

β y = σ, P () = a / {1 + a + a) =, σ (a) =. In this case, the equation (9) that sigma (γ) ≠ 0 is not added. Therefore, this code error cannot be corrected, and the subsequent processing is stopped, and the received code SΥ0 is directly decoded and decoded: Output as YD, and output 1 to signal;

As is evident from the decoding examples described above, according to the present invention, it is possible to correct the perfect game by a simple decoding process.

Next, the above-mentioned fourth-order primitive polynomial; G (X) = X * + X + 1 GF (2) (3) The configuration of each part of the present embodiment will be described in detail using an RS code as an example.

7th is a configuration example diagram of the syndrome operation unit 1 in the first step of the decoding method. The combination of an EXOR circuit 7, a shift register circuit 8, and a coefficient multiplication unit 9 has the syndrome S. The calculation of to S _S Note that coefficient multiplying portion 9, the coefficient values;. Performs 1, α ', · · · , a multiplication of a ^s respectively, an input signal (a,, a _2, a, a ₀ ), each output can be obtained by the following calculation,

Power of coefficient value 1; (a ,, a,, aa ₀ ) Multiplication by coefficient value α; (a ₂ , a, as ₊ a ο, a,)

Multiplication coefficient value α '; (. A, a 3 + a, a s + a 2, a 2)

Multiplication of the coefficient value of ^3; (.! A, ten _{_{a, a 3 + a 2,}} a 2 + a, a,)

Multiplication of coefficient value a *; (a, + a:, a ₂ + a,, a! + A! + Ao, a, + a ₀ ) multiplication of coefficient mold a ′; (a ₂ + a,, a, _{_{+ a 2 + a, a 3}} + a 2) each information received codeword;..!. (i ,, i 2 i, i) with respect to, multiplied by the coefficient value by the coefficient multiplying unit, the received code quotient When the last information is input, a syndrome expressed in vector is obtained from the output of each shift register circuit.

FIG. 8 is a structural example diagram of a circuit that performs multiplication of a in the second, third, and fourth steps of the decoding method. Perform multiplication Hama operation by a combination of AND circuit 10 and EX OR circuit 11 1, input: a (i ,, i 2, i ,, io). For a (j ,, j _lt jj ₀ ) performs 16 management operations, to multiply the output calculation result; get _{α = a 'a (k s} , k 2, kk 0).

FIG. 9 is a diagram showing a configuration example of a circuit that divides a′Zii ′ in the second, third, and fourth steps of the decoding method. It is composed of a ROM circuit 12 and a multiplication circuit 13 shown in FIG. 8. The ROM circuit 12 has an input; α (j j ,,

-J

j., j. ) Is a table lookup and outputs (j ,, j1, j. J-). The multiplication circuit 13 multiplies this by (ii2, i !, io). , Obtain the operation result in the output; α 'a' (k ,, kkk.)

As described above, according to the present embodiment, it is possible to correct the burst error of the RS code by a very simple decoding process, and it has a significant effect on the correction of the burst error in the storage medium. Obtainable,

Next, a second embodiment of the present invention will be described with reference to FIGS. 10 to 11, and FIG. 10 shows a decoding procedure in the present embodiment. The third, fourth and fourth steps are the same as the decoding procedure shown in FIG. 1. In the calculation of the error position by the burst pattern equation in the third step, if it is not possible to calculate the burst position »polynomial; indicating the position of the burst error (if it is not possible in the figure), a new In the fifth step, the error position is calculated by the conventional Chien search method. According to this decoding process, the error position of a random error included in the received code S can be calculated. Therefore, in the decoding procedure according to the present embodiment, the present invention can be applied to a burst error. For the ffi-go method, it is possible to perform the same Didi correction as in the prior art for random attacks.

FIG. 11 is an example of a configuration for performing this decoding method. In FIG. 11, 1 is a syndrome operator, 2 is a periposition polynomial operation unit, 3 is a burst pattern detector, and 4 is a burst pattern detector. Peripattern calculation unit, 5 is the delay unit, 6 is the addition unit, and 14 is the Chien search ffi.

The received code of the t-ary re-correction RS code; Y0 is input to the syndrome calculation unit 1 and «Noburou 5;

The syndrome calculation unit 1 calculates the syndrome, which is the first step of the signing procedure. That is, the syndrome calculation unit 1 performs the calculation shown in Expression 4 on the received code; Y0, and calculates the syndrome: S ^ i-O, ,..., 2 t — 1) is calculated, and this S i−O, 1,..., 2 t—1) is output as a syndrome sequence; When S, = 0 (i = 0, 1, · · ·, 2t-1), it is determined that there is no signal and a signal is output to EN; 0 is output to EN. , ≠ When 0, output signal 1;

Re-position polynomial Namiro 2 calculates the error-position polynomial, which is the second step in the decoding procedure; the coefficient of σ (Z); σ, (i = 1, 2,, ·, jj ≤ t). That is, when EN is 1, a syndrome series; for S, a well-known syndrome as shown in Equation 8; S, and a coefficient; O, (i = l, 2, · · ·, j) Is calculated. Then, the number of errors; j and a coefficient; σ i = 1, 2,-, j) are output as a coefficient sequence; σ.

The burst pattern detection unit 3 calculates a burst error position, which is the third step of the decoding procedure. That is, when the signal; ΕΝ is 1, the burst pattern specified by the number j of errors shown in FIG. Tobatan equation; BP (a) is successively substituted into Equation 9 to calculate γ; and if σ (γ) = 0 is added, the burst position St polynomial shown in Equation 10; 3 (α) = Β P (α) · γ Outputs the position of the parse error as a peri-position sequence; / 3, and outputs 0 for the signal; ED. If γ that satisfies σ) = 0 does not exist, correction cannot be performed because the order B is unknown. Therefore, in this case, no signal is output to the error position sequence; and 1 indicating the detection of the beam is output to the signal; ED.

The chain search unit 14 performs the decoding process of the fifth step of the decoding procedure, and detects an error position by a chain search method. That is, when the signal is EN and the signal ED is 1, the number of errors output from the position locator polynomial operation unit 2; j and the coefficient of the error locator polynomial; σ> (i = 1, 2, , J); the K-order is calculated by the Chien search method based on the mouth, and output as an erroneous-order sequence; 3/3. The error position cannot be detected. In this case, nothing is output to the error location sequence; ββ, and 1 is output to the signal: EDD to indicate error detection.

The error return pattern calculation unit 4 calculates the error pattern; ある, which is the fourth step in the decoding procedure. That is, when the signal: ΕΝ is 1, the position sequence sequence of the game: β or / 9/9 and Calculate the erroneous return pattern of the erroneous position; And output an error pattern sequence;

Adder 6 is the signal delayed by delay 5; Y0D error has occurred The Q code is corrected by adding the pattern corresponding to the position, and an RS code; YD, which has been subjected to decoding processing for burst error correction, is obtained from the output.

As described above, according to the present embodiment, the burst correction of the RS code can be performed by a very simple decoding process, and the random number can be corrected in the same manner as in the related art. A code in which a burst error and a random error in a storage medium and the like are wetted can have a significant effect on correcting the code K. As described above, according to the present invention, a burst error in an RS code can be obtained. Can be corrected by an extremely simple decoding process, which can provide a remarkable effect in correcting bursty and random error codes generated in storage media. Availability

As described above, the decoding method and decoding device for a parse error of a Reed-Solomon code according to the present invention are used as a decoding method and a decoding device 31 for an R-read positive code in a reproducing device such as a compact disk or digital VTR. It is useful, and in particular, since bursting in the Rs code can be corrected by extremely simple decoding processing, it is possible to reduce bursting that occurs in storage media such as storage compact disks and digital VTRs. Or a sign error of a random string can have a significant K effect.

Claims

The scope of the claims

1. Degree; primitive polynomial of m; Galois extension field defined by G (X); element on GF (2), primitive polynomial; root of G (X) = 0; generator by α Term; G. (X)

G ₀ (X) = (X-1) (Χ-α) (Χ-α) (X-α)

In the decoding method of the t-double bit error-correcting lead-Solomon code given by, the following processing is performed on the received code polynomial; Y (X),

S ₀ = Y (X) mod X— 1

S, = Y (X) mod X- α

S ₂ = Y (X) mod X- α

S ,,-, = Υ (X) mod X— α

, 2 t-1), and at least one of the above 3E syndromes; S, when at least one is non-zero, the above syndromes; S, S, (i = 0, 1, 2,..., 2 t-1)

σ (Ζ) = 1 + σ, Ζ + σ, Ζ + · · + σ, Ζ

The second step of calculating j (j ≤ t) coefficients of σ, (i = 0, 1, ···, j); the primitive polynomial; the root of G (X); a and j Number of integers; 1, P, q, ···, r (1 <p <q <· · '<r ≤ t), a perfect pattern equation; Β Ρ (α) = 1 + α + From α +-·-+ a, a burst pattern equation that satisfies the relationship of γ = σ, / Β Ρ (na) and σ (γ) = 0; searches for Β Ρ (α);パー (α) · γ, j story locations «; γ · £ ΐ, · · ·, Υ-a, γ-a, γリ a Γ, · · ·, γ-a, Based on r-α, γ and the syndrome; S i-O, 1, 2, 2,..., 2 t-1), j error return patterns corresponding to the error position; , Ε, Ε, _ρ , Ε, and a fourth step of obtaining the syndrome; S, is S, = 0 (i = 0,1,2, ..., 2t-1) In this case, it is determined that there is no error, the correction code is not performed, and the received code is output as a decoded code as it is. If at least one of the syndromes S is non-zero, the second and third codes are used. According to 1), the reverse error position and the error pattern are obtained, and the error return pattern is added to the position corresponding to the error position of the received code, and the error is detected. performs correction勋作, in the third stearyl Tetsubu, gamma = _sigma, /, and, _{if σ (γ)} = 0 becomes to satisfy the relationship y does not exist, the received abort corrective action轵Ri and JP «to carry out« No. operation 织Ri detected indicating that there is, Lee Dosoromon sign-burst Li decoding method in EP.

2. In the third step, if there is no y that satisfies the relation of γ-σ, ΖΒ Ρ ίίτ) and σ (γ) = 0, the II reposition polynomial; σ (Ζ) −1+ σ ₁ Ζ + σ, Ζ + ·. · + σ, Ζ = 0 j roots are found by the Chien search method, and the peri-position β and erroneous re-pattern are calculated based on these roots and received. The method according to claim 1, wherein a correction operation is performed by adding an error pattern to a corresponding error position at of the code.

3. An order: an extension polynomial of m: Galois extension field defined by G (X): An element on GF (2) is a key figure, and the above primitive polynomial: the root of G (X) = 0; G. generator polynomial; (X)

G ₀ (X) = (X-1) (Χ-) (Χ-)

In the decoding device B of the t-byte byte positive Reed-Solomon code given by Code length; η, number of information points; n—2t, and a syndrome based on the received code; S, (i = 0, 1, 2, 2, '', 2t—1), and a syndrome sequence: a syn that outputs S Drome computing means;

The number of errors based on S; the number of errors based on S; j (j ≤ t) and the error locator polynomial; σ (Ζ) = 1 + σ ₁ Ζ + σ, Ζ + ·. ₍ i = 0, 1, ···, j) and a coefficient sequence; error place polynomial calculating means for outputting σ;

The number of the above errors; the same number of integers as j; one or more burst pattern equations determined by the combination of 1, p, q,..., R (l <Ρ <q <· <<Γ ≤ t); Α Ρ (α = 1 + α '+ α' + · · · ten 'and the above coefficient series; from σ, the parameter satisfying the relationship of γ = σ, ΖΒ Ρ (α), and σ (γ) = 0 — Search for the pattern equation; BP (cr) and γ, and search for the burst position polynomial; (α) = Β Ρ (na) · γ リ j The position of the j parses; γ · α, · · · error pattern sequence for obtaining γ-a, y-a, γ;

From the above error position sequence; β and the syndrome sequence; S, j error return patterns corresponding to the above j 偭 perspective position; Ε,,..., Ε, Ερ, Ε are obtained. Error pattern calculating means for outputting リ;

An adding means for adding and outputting the erroneous re-pattern sequence; E to a position at corresponding to the location of the received code at the at. Device for decoding lead somon codes.

4. Degree; primitive polynomial of m; Galois extension field defined by G (X); element on GF (2) is a key figure, and the above-mentioned primitive polynomial; root of G (X) -0; Regenerating polynomial; G. (X)

G ₀ (X) = (X-1) (Χ- α) (Χ- α) The decoding equipment for t-pilot-positive-lead Solomon code given by In,

Code length; η, number of information points; Syndrome S ■ (i = 0, 1, 2,... 2t-1) is obtained based on the received code of n-2t; Syndrome calculation means for outputting

The syndrome sequence; the number of errors based on S; j (j ≤ t) and the error locator polynomial; σ (σ) = 1 + σ ₁ Ζ + σ: Ζ +-· · + σ j 係数 coefficients; σ , (i = 0, 1,... *, j) and a coefficient sequence;

One or more burst pattern equations determined by the combination of the number of errors and the same number as j; 1, P, q..., R (1 <P <q <-... <r ≤ t) BP (a) = l + a + + ♦ · + α and the above coefficient series

; Σ-σ, Ζ Β Ρ ία) and σ (γ) = 0 from the past pattern equation; Β Ρ (α) and y are searched for, and the burst position polynomial; β (a ) = BP (α) · the position of j pastries from γ; γ · α, · ·

· A permutation calculation means for calculating, r-α, γ-a, γ and outputting a first K-position sequence;

Σ (Ζ) = 1 + σ, Ζ + σ, Ζ + · · ■ + a, 上記 and the above coefficient series: σ A second perimeter B sequence; a Chien search means for outputting 3/3,

From the above first error position sequence; 3 or 2nd parity B sequence; 0 and the upper Ei syndrome sequence; Find the corresponding j S-returns and return sequence

SS return pattern calculating means for outputting E,

The above-mentioned bursty order detection of the receiving code is performed by adding the above-mentioned S return pattern sequence; E to a position corresponding to the above-mentioned error position S, and outputting it. Have

In the above burst pattern calculating means, if there is no γ satisfying the relationship of a = σ, = Ρ (ίΐ) and σ (γ) = 0, the erroneous return calculating means 38. A decoding device for t-byte error correction lead Solomon code 38, wherein an error pattern is calculated based on the second error position S sequence ββ from the Chien search means.