JPH011332A - Decoding method of Reed-Solomon code - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] (Industrial Application Field) [This invention relates to a Reed-Solomon code decoding method, in particular,
This invention relates to an erasure correction method.

[Summary of the invention]

In this invention, a syndrome is calculated using a parity check matrix and a received word, an error locator polynomial σ(x) and an error evaluation polynomial ω(x) are calculated from the syndrome, and the formal first derivative of the error locator polynomial σ(x) is calculated. The polynomial σ′(
x) and error evaluation polynomial ω(x), [ep=ω(
In the Reed-Solomon code decoding method, the error pattern ep is obtained by calculating the error pattern ep and the symbol at the error position p is corrected by calculating the error position indicated by the pointer. Let the error locator polynomial formed by the corresponding values be σ1(x), and the error locator polynomial σ″
σ* (x) obtained by multiplying ``(x) and syndrome polynomial S(x) When 5(x) is a polynomial ω*(x), deg σ* (x) > deg (1)'' (x ), the pointer is considered to be correct and erasure correction is performed when the following conditions are met, making it possible to reliably check the reliability of the pointer.

[Conventional technology]

Reed-Solomon code (Reed 5oloson C
l) Calculation of syndrome ii) Error locator polynomial σ(x), error evaluation polynomial ω(x
) derivation 1 ii) estimation of error position and error value iv) execution of error correction. Conventional decoding methods that use solutions using the roots of equations cannot be applied in the case of correction of multiple errors of 5 or more errors. Are known.

That is, the Euclidean algorithm is used to generate the error locator polynomial σ(x) and the error evaluator polynomial ω(x).

The parity check matrix H for t-fold error correction of a Reed-Solomon code is (t: correctable number, n: code length). From the product of the above parity check matrix H and the received signal, the syndrome is calculated as follows. is generated and a syndrome polynomial is defined.

So−Σr, αj −1, , Σekα(k−11
k(-#!S,=Σr i(x""-"=E e k(x"
(t"it S, = Σr, α(j*1) (+-1)-Σekα
(J+Il (k-114E S zc-+ =”, E r 1 (x” ”-”
= Σe z (x'') The following polynomial whose coefficients are the values generated by the above equation is called a syndrome polynomial.

5(x) = SO+S, x+Stx" + ,, -1-
There are various polynomials for S, t-, X2L-' error correction, which satisfy the following relational expression.

φ(x) ・x” +σ(x) ・5(x) −(
11) (x) However, ω(x)=Σe, ・rl (x −cx−”−”
): Error evaluation polynomial RigE (L lL In the above equation, two things are required for actual correction: the error locator polynomial σ(x) and the error evaluation polynomial ω(x). be.

If the above equation always holds, then X2L can of course be known, but only S(x) can be known from the received signal. From this xzt and S (x), σ(x) and ω(x) can be found by Euclidean algorithm. Here, as an example of the well-known Euclidean algorithm,
Given positive integers m and n, their greatest common divisor d
Calculate the integers a and b such that (am+bn=d)
Euclidean algorithm is used to solve this problem. The same applies not only to integers but also to polynomials. That is, (
m-'X'')(n-+5(x)).

However, in the above integer problem, the greatest common divisor d is obtained by executing the mutual division method to the end, but when calculating σ(x) and ω(x) in order to perform error correction, It does not mean that the algorithm is executed to the end to find the greatest common divisor.

If the following conditions are met midway through, the execution of the mutual division method is stopped.

t≧deg a (x) >deg ω(x) (deg
means the degree of the polynomial. ) Using the Euclidean algorithm, the derived σ(x) and ω(x) are used to estimate the error position and error value, and perform error correction. This process will be explained in the case of a 4-sample error correction code. As the received signal is shown in FIG. 8A,
In the case of n symbols, the value substituted as X in the error locator polynomial σ(x) is (1° α-1, α -9
・α, ...α-(a-11). That is, the number p is the number counted from the end of the received signal.

As an example, in FIG. 9A, if the last received signal is the 0th position, as indicated by diagonal lines, errors will occur at the 1st and 4th positions, and these errors will be reflected in FIG. 9B. As shown, let us consider correction in the case of an error pattern of (α■, α3). The syndrome polynomial in this case is as follows.

5(x)=rx" xfu +a"x" -zr
'x'+αle'x'+ax3+a"x" +
σ(
x) and ω(x). The results are as follows: error locator polynomial σ(x) and error evaluation polynomial ω
(x) is found.

σ(x)−x” +cx”x+cr” ω(x)=αS
Using these error locator polynomials and error evaluation polynomials, which are expressed as '(x) - αI0, the error locator and error pattern are determined. In the error locator polynomial σ(x), (1, α-1°α-3, . . .
), and if the value at that time becomes zero, it is estimated to be an error position. Further, the error pattern ep is obtained as follows: ep=ω(α−″′)/σ′ (α alone).

In the case of Fig. 9, 1, ((x-凰)-a-"+a'+.
Ward 0=0σ(α-4)-α-3+α6+α10=0, and the error position can be found.

The error patterns el and e4 are e, "= 6) (ff-') / (t """
α” / (t ”−(x−′=α■ e 4 =6)(ff−”) / (1!l0−(x”
/ (x"=I:t", and the correct error pattern can be found. Error correction is performed by adding (+*od, 2) to the above error pattern to the received sequence. Ru.

Regarding the Reed-Solomon code mentioned above, one error is
Contains two unknowns. Therefore, in the case of heavy error correction, 21 parities are added, and if the 2 syndromes generated on the receiving side are t errors, then
Corresponding to 2 independent equations, it is possible to solve 2 error positions and 2 error patterns.

In addition to this correction method, there is a method called erasure correction for Reed-Solomon codes.

Let us take up the equation below again.

φ(x) ・x” +6(x) ・5(x) =,
a>(x) From this, σ(r) ・5(x)mi ω(x) (sod,
The calculation is performed for the example of FIG. 9, where x '') holds.

5(x) −ex"x'+cx"x' +cx7
x'+crN)x4 +4K"10α3X"10"
x+cr"σ(x)=x'+α1@x+α10 1F(x)Sχx) mar"x"+ax"+c
r'x+a"=α"x+cr" (mod, x"
)−ω(x−) holds true.

1 in the case of erasure correction, a pointer is generated using another error detection code, etc. A pointer indicates that something is likely to be an error, and it must be noted that just because a pointer is set, it does not necessarily mean that the symbol is an error.

As shown in Figures 10-8 and 1-0, the same error as in Figure 9B has occurred, and on the other hand, regarding erasure correction when the pointer is at the position shown in Figure 10C. explain.

First, from the pointer, create the error locator polynomial σ(x) and the corresponding error locator polynomial σl" (x). As is clear from FIG.
Since we stood at a position corresponding to α-') (x=α-'') (x=α-4), σI''(x) is as follows.

σ, “(x)= (x+1)(x+α−1)(x+α−
2) (x+α-4) =X'+cx'x"+rx"x" +cx
“x+cx” Next, using this polynomial σ, ” (x) and the syndrome polynomial S (x), we create an entertainment evaluation polynomial ω
, ” Find (x).

σ1” (x) 5(x)mi ω, ” (x) When actually calculated, ω, ” (x) = cx s x”
+x" +tx lo (mod, x') Also, σ, "'(x)=αf xg +α10Therefore,
The error pattern is as follows.

eo=ω, ”(1)/σ,”(1)−〇/α6−
0 Since this is not an error, the error pattern can be O.

X÷α−1 ep=ω, ′(α−′)/σ, 1 ′(α−′)−α
eye/l-α1 X;α-2 ez =ωl'(cr-") / (JI"
((r-”)-0/α1t=O X=α-4 (!4 ””ωI” ((r-’) / (11”
'((r-') = αth/αth - α3 As described above, it can be seen that all error patterns can be correctly determined and corrected.

In the case of erasure correction, if the pointer is inaccurate, there is a risk of incorrect correction. For example, Figure 10A
11A and 11B, and a pointer that misses the error occurs as shown in FIG. 11C. think.

The error locator polynomial % expression % (
) Also, when calculating σz ” (x) 5(x), σ
x ” (x) 5(x) =txx' +cxIzx
"+cx"x'+a'x'+x3+α"x"
+a'4=ωt'' (x) (mod, x'
) was found to be. This polynomial cannot correct errors at positions where the pointer is not located.

[Problem that the invention seeks to solve]

In the conventional Reed-Solomon code decoding method, when erasure correction is performed, there is a problem in that it cannot be determined whether the pointer indicates all the error positions.

Therefore, an object of the present invention is to provide a Reed-Solomon code decoding method that can check whether the pointer indicates all error positions and can perform erasure correction with high reliability.

[Means for solving problems]

In this invention, a syndrome is calculated using a parity check matrix and a received word, an error locator polynomial σ(x) and an error evaluation polynomial ω(x) are calculated from the syndrome, and the formal first derivative of the error locator polynomial σ(x) is calculated. The polynomial σ′(
x) and error evaluation polynomial ω(x), [ep=ω(
In the Reed-Solomon code decoding method, the error pattern ep is obtained by calculating the error pattern ep and the error position Wp is corrected by calculating the error position indicated by the pointer. Let the error locator polynomial formed by the corresponding values be σ'''(x), and multiply the error locator polynomial σ''(x) by the syndrome polynomial 5(x) to obtain σ'(x) 5(x). When the polynomial ω9(x) is satisfied and the condition of deg σ″(x)>deg ω*(x) is satisfied, erasure correction is performed by assuming that the pointer is correct.

[Effect]

As shown in Figure 10C, when the pointer that includes all error positions is standing, σI* (x) = (x+1) (x+cr-') (x+
α−2)(x+α−4) =x4+α? x3+α2 xg+α′. x+α8ω,
” (*) =α' x3+x” +tx” (mo
dyx”).

On the other hand, as shown in the pointer shown in Figure 11C, even one
In the case of a pointer that does not contain an error location, at ” (x) = (x+1) (x+cr-'
) Cx+cr-2)-x” +cx” x” +r
x"x"+a' x tena"also at" (x)
When calculating 5(x), at ” (x) 5(x)
:=αx'+α"x"+oe"x'+α' x
' +x3+α3 xZ+αI4=ωt ” (x)
(sod,

When performing erasure correction using a heavy error correction code, ■If the pointers below 2 include all correct error positions deg a” (x) > deg ω* (x) (or deg ty” (x) − deg ω* (x)
It can be seen that deg a'' (x)≦deg ω*' (x) if the 021 or less pointers do not include even one error position, that is, if they do not work as correct pointers.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings. This description is given in the following order.

a. Decoding method Polynomial multiplier circuit a. Decoding method FIG. 1 is a flowchart showing the Reed-Solomon code decoding method of this embodiment. In FIG. 1, it is first checked whether the number of pointers Np is (Np≦2t) (step ■). If the number of pointers is less than or equal to Np, error correction is possible without using pointers.
Proceed to step ■, and from the syndrome polynomial S (x), the error locator polynomial σ(x) and the error evaluation polynomial ω(x)
is required. As this method, Euclidean algorithm can be used.

Move from step ■ to ■, (deg σ(x)<t)
It can be checked whether If this condition is not met, error correction is impossible, so error correction flags are set at all pointer positions (step ■).If the condition of step ■ is met, the process moves to step ■, where the error position is searched. It will be done. That is, (x=α−p凰) such that (σ(x)=O) is searched for.

It is checked whether the detected error position p is (0≦p1×n) (step ■). When the condition of step (2) is satisfied, the process moves to step (2) of error correction, and when the condition of step (2) is not satisfied, the process moves to step (2) of setting the error correction flag.

Error correction is based on the formal 1 of the error locator polynomial σ(x)
If the order differential is σ'(x), then the error pattern is obtained from the following equation, and this error pattern is added to the received word.

ep! "ω(α-p1)/σ'(α-p") Unlike the above-described processing, erasure correction is performed if the number Np of error pointers is 2 or more in step (2). In the case of erasure correction, the error locator polynomial σ1(x) is calculated from the pointer position (step ■). In the 0th-order step ■, ω*(x)(=σ* (x)
) ) is calculated.

Here, the reliability of the pointer is judged (step ■), (deg a” (x) > deg ω*
When (x)) is established, it is determined that the reliability of the pointer is high, and the error pattern ept is determined in step (3).

epL=ω* (α-”)/σ0′ (α-1ll
) If the reliability of the pointer is low, no erasure correction is performed.

As an example, as shown by diagonal lines in FIG. 12A, (
1, α1. An error occurs at the position α-2, α-3, α-4), and each error causes the error to occur at the position (12l8).
α4. α4. α3. α8. α, ), and the pointer is (1, α-1, α-g, α
Bow, α-4. The case where the user is standing at the position α″7) will be explained.

From the pointer, find the error locator polynomial σ".

6”! (x)= (x+1)(x+α-')(x+
cr-”) (x + α-3) (x+α-4)
(x+α−7)=x” +x” +rx” x' +a
IOx3+a'x"+ αllx+α13 Therefore, the syndrome polynomial 5(x) created from the received signal is
xA+α"x'10X"+rx'X+a' error evaluation polynomial ω", (x) is
4X+(x2=G)” s (x) (Illod
, x”), and deg a” 3 (x) = deg (111s (
x) + 1. Therefore, it can be seen that the pointer contains all true error locations. That is, this pointer is
It means you can trust it. Actually, when we find the error pattern from σ 2 (x) + ω", (x), we get
It will look like this:

x=1 e6=ω3''' (1) / 63 ''' (1)=
α”/α4; α4 X−α−1 el “”(d3 ” (α−′) / (f3 ”
' ((r-J=1/αth-α4
)=α4 /α=α3 X±α−3 ep−ω3′(α−3)/σ, 1′(α−3)−α13
/αth=α2
α3 = α χ=α−7 e7−ω3′(α−7)/σ3′″ ′(α−7)=
0/α1t=0 Since this position is not a true error, it is correct that it is 0.

b. Polynomial Multiplication Circuit In the erasure correction described above, it is necessary to perform the following two types of calculations.

■α-1” (i=1.2°・corresponding to the pointer position)
..., 2t) of the error locator polynomial σ8(χ), (j=1.2. . . 2t-1) is determined.

(2) Multiply the obtained σ*(x) by the syndrome polynomial S (x) obtained from the syndrome of the received signal to obtain the error evaluation polynomial ω9(x).

ω* (x) = σ“(x) ・S(x) And as an important check, deg d” (x) = deg ω* (x) +
Check whether 1 holds true.

FIG. 2 is an example of a calculation circuit for σ1(x).

In FIG. 2, r is a flip-flop that produces a delay of one clock, AD is a finite field adder circuit, and ML
is a finite field multiplication circuit. Input terminal 1 has (1,
The data is entered manually in the order of α-'', o, o, o...).

A unit configuration consisting of two flip-flops r, a multiplier circuit ML, and an adder circuit AD is connected in cascade in (2t-1) stages. The multiplier circuit ML of each stage includes: -11,tl
, and α-txt are supplied respectively. At the output terminal 2, σ2t is obtained first, and then σ
KL-In...σ is obtained sequentially, and finally σ.

is obtained.

The arithmetic circuit shown in FIG. 2 will be explained with reference to FIG. 3. - Boat fishing (x+a) (x+b) (x+c) (x+
Consider performing the calculation d).

As shown in FIG. 3A, one flip-flop, two multipliers, and two adder circuits output (
1, a+b, ab) is constructed. Third
As shown in FIG. A, the configuration of this circuit is replaced with a configuration of one flip-flop r, an adder circuit AD, and a multiplier circuit ML.

Since FIG. 3A is a circuit that calculates (x+a)(x+b), this result is expressed as (,X
+ C) multiplication circuit, and further, the result is (x+d
), (x+a)(x+b)
An arithmetic circuit of (x+c)(x+d) is realized. In this case, the human power is (1°a, O, O, . . . ), and the coefficients of the answer are output in descending order of power.

FIG. 4 shows another example of a calculation circuit for σ'''(x).
-Input terminal l has (α-", 1.O,O,O...
・) Data is input in this order.

Two flip-flops r, multiplier circuit ML, and adder circuit A
A unit configuration consisting of (2t-1) stages of D is connected in cascade. The multiplier circuit ML of each stage includes the α-th, α-L3
... α-L1 is supplied respectively. Output terminal 2
First, σ. is obtained, and the following σ8. ...σ2.
-1 is obtained one after another, and finally σc is obtained.

The arithmetic circuit shown in FIG. 4 will be explained with reference to FIG. 5. - Boat fishing (x+a) (x10b) (x+c) (x+
Consider performing the calculation d).

As shown in FIG. 5A, one flip-flop, two multipliers, and two adder circuits output (
1, a+b, ab) is constructed. Fifth
As shown in FIG. A, the configuration of this circuit is replaced with a configuration of one flip-flop r1 addition circuit AD and one multiplication circuit ML.

In the configuration shown in FIG. 5A, the multiplication circuit and the addition circuit are separated and the configuration is not good. Therefore, as shown in FIG. 5B, instead of exchanging 1 and b, the input is also changed to 1. Exchange with a.

Since FIG. 5B is a circuit that calculates (x+a)(x+b), the result is expressed as (x+C) as shown in FIG.
) and then passes the result through the (x+d) multiplication circuit, (x+a) (x + b) (x+
c) An arithmetic circuit of (x+d) is realized. In this case, the human power is (a.

1, O, O, ...), and the answer coefficients are output in the order in which they should be manipulated.

FIG. 6 and FIG. 7 show one example and other examples of a calculation circuit for ω0(x). Input terminal 11 in FIGS. 6 and 7
is supplied with 0. In the configuration shown in Figure 6, output terminal 1
2, outputs are obtained in order of descending powers. On the other hand, in the configuration shown in FIG. 7, outputs in the order of ascending powers are obtained at the output terminal 12.

〔Effect of the invention〕

According to this invention, the reliability of a pointer can be checked during erasure correction. If this invention is adopted, even if there is an error in the pointer, this error will be detected, erasure correction will be stopped, and a check will be made to see if regular error correction is possible, thereby increasing the number of cases in which errors can be corrected. .

[Brief explanation of drawings]

FIG. 1 is a flowchart for explaining an embodiment of the Reed-Solomon code decoding method according to the present invention, FIG. 2 is a block diagram of an example of a polynomial multiplication circuit, and FIG. 4 is a block diagram of another example of a polynomial multiplication circuit, FIG. 5 is a block diagram for explaining FIG. 4, and FIG. 6 is a block diagram of an arithmetic circuit for σ1(x)・S (x) An example block diagram, Figure 7, shows σ'''(x) ・S (
In addition to the arithmetic circuit of x), a block diagram of an example of
Figure, Figure 11. FIG. 12 is a route map for explaining each error pattern. Explanation of main symbols in the drawings ■, ■: Step for finding error pattern, [Phase]: Step for checking reliability of pointer. Agent Patent Attorney Tadashi Sugiura TomoA [Icho7 [[T]Tani] T Becho72N22F Rochoishi]
Miyagi Risutachi, Tohani Diagram 8A ``11 ryosai [=] 2 lower - weak 1 cho'' 2 cho 2 nininiguchi B [gu] Hijiri lg daan Diagram 9 A kuchishi m ryo possible [ [Douji Y - Futakuchi BE] Surrounded by Roasting Pattern B Country Utsuyoshi Milk Ri, 1 Turn゛ Figure 11 Wrong Noma Turn Figure 12

Claims (1)

[Claims] A syndrome is calculated using a parity check matrix and a received word, and an error locator polynomial σ(x
) and the error evaluation polynomial ω(x), and using the formal first-order differential polynomial σ′(x) of the error locator polynomial σ(x) and the error evaluation polynomial ω(x), [e_p=ω(
In the Reed-Solomon code decoding method, the error pattern e_p is obtained by calculating the error pattern e_p by calculating α^-^p)/σ'(α^-^p), and the symbol at the error position p is corrected. Let σ^*(x) be the error locator polynomial formed by the values corresponding to the error positions, and multiply the error locator polynomial σ^*(x) and syndrome polynomial S(x) to obtain x) S(x) is a polynomial ω^*(x
), and when the condition of degσ^*(x) > degω^*(x) is satisfied, the pointer is deemed to be correct and erasure correction is performed.