JP3439309B2 - Double-extended Reed-Solomon decoder - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [0001] TECHNICAL FIELD The present invention relates to digital communication,
Or in decoding error-correcting codes to increase the reliability of storage.
And information on the reception status of the received codeword (reliability information)
The present invention relates to a soft decision decoding technique using. [0002] 2. Description of the Related Art Soft-decision decoding is a method of decoding errors contained in a received codeword.
When estimating the transmission codeword, the
Uses information (reliability information) on the reception status of each symbol.
To increase the probability of correctly estimating the transmitted codeword.
ing. The theoretical principle of this soft decision decoding is
ー, David Jr., “Generalized Minimum Distance Decoding”, I
EEE Information Theory Subcommittee Bulletin, IT-12, 125-13
Page 1, April 1966 (Fornery, G.D. Jr.,
“Generalized Minimum Distance Decoding”, IEEETr
ansactions on Information Theory, vol.IT-12, pp.12
5-131, April 1966).
Is knowledge. The basic problem with soft decision decoding is that
To efficiently and efficiently construct a high-speed soft decision decoder.
You. As a decoder for double-extended Reed-Solomon code,
Yama, Fujiwara, Onishi, Ishida “Double-extended Reed-Solomon codes”
No. 13 decoding method, IEICE National Convention, No. 13.
91, 1984. This prior art
Is a configuration of a hard decision decoding device for a double-extended Reed-Solomon code.
Although it is related to the configuration, the configuration of the soft decision
Can be applied to The technique in this case is
A series of estimation error locator polynomials giving word candidates and estimation errors
Euclidean divider for fast calculation of numerical polynomials
Are provided. A schematic block diagram of a soft decision decoding apparatus according to the prior art
A lock diagram is shown in FIG. Received code to be input to decoding device
Word and reliability information for each symbol of the received codeword
Are stored in buffers 1 and 3, respectively. Syndrome arithmetic
The output processing device 2 calculates the syndrome using these as inputs.
Out and output. Syndrome consisting of d-1 symbols
Is t = [(d-1) / 2] parallelized Euc
Lid divider 9₁ ~ 9_t Entered into each Euclidean
Divider 9₁ ~ 9_t Is the estimated error locator polynomial and the number of estimated errors
Calculate the value polynomial. Each of these polynomial sets is d−1−
In k erasure error correction (k = 2, 4,..., 2t)
Estimation error position / corresponding to numerical polynomial, estimation of t sets in total
An error locator polynomial and a numerical polynomial are output. Note that d is
Indicates the minimum design distance of the code. [X] is less than or equal to x
Represents the maximum integer. Euclidean divider 9₁ ~ 9_t Out of
T estimated error locator polynomials and estimated error numerical polynomials
The equation is input to the error value calculating device 6, and first, the estimated error position is calculated.
The estimated error position corresponding to the zero of the polynomial is calculated, and
Estimate from the estimated error location polynomial and the estimated error numerical polynomial
An error value at the error position is estimated. Calculated error
The output value is output to the estimated codeword selecting device 7. [0005] SUMMARY OF THE INVENTION In soft decision decoding technology
The most basic problem is that a high-speed soft decision decoding
And the reception state of the received codeword is
Estimate a transmitted codeword without using reliability information
With the same processing time and device scale as hard decision decoding
It is desirable to configure. Double-extended Reed-Solomon mark
In the prior art relating to
Of a series of estimated error locator polynomials and estimated error numerical polynomials
As shown in FIG. 5, the output processing is performed by using a Euclidean divider.
This is realized by t-parallelization. Previous hard decision reversion
The Euclidean division process is executed once in the
Therefore, there is no need for such parallelization. You
That is, the conventional soft code for the double-extended Reed-Solomon code is used.
Necessary for Euclidean division processing in decision decoding
The device scale becomes t times. Also, to reduce the size of the equipment,
If column (repeated) processing is performed, t times the calculation time is required.
It becomes important. No effective method has been proposed for this task
Not. An object of the present invention is to provide a double-extended Reed-Solomon.
For soft decision decoding of codes,
Of computations required for parallelization of data division and the scale of the device
To solve the problem of the conventional soft decision decoding apparatus
More Economical and Efficient Double Stretch Reed-Solomon
It is to provide a decoding device. [0007] SUMMARY OF THE INVENTION A double-extended lead according to the present invention.
The Solomon decoding device has a code block length of q + 1 (q is a prime number).
Power of a number) for a double-extended Reed-Solomon code,
Received codeword and reliability information indicating the reception state of the received codeword
Is used to calculate an estimated codeword candidate.
From among the codewords most similar to the received codeword,
To correct a code error in the received codeword.
In the error correction decoding device, the reliability information and q + 1
Included in the q symbols in the received codeword
All estimated error locator polynomials and estimations corresponding to errors
A polynomial operation device for calculating a set of error numerical polynomials;
One symbol other than the q symbols in the codeword
Using the auxiliary polynomial calculated by the polynomial calculation device
To complement the estimated error locator polynomial and the estimated error numerical polynomial.
A correcting polynomial correction device and the corrected estimated error position
Calculate estimated codeword candidates from the polynomial and the estimated error numerical polynomial
Device that selects the most similar codeword after the received code.
Equipment. According to an embodiment of the present invention, a polynomial arithmetic unit is provided.
Is the received codeword and the confidence in the received codeword.
D-1 with the lowest reliability selected by the degree information (d is
Syndrome calculated from the index specifying the position of (natural number)
From the repetition operation algorithm consisting of a maximum of d-2 repetition operations.
Algorithm, the k-th iteration of the iterative algorithm
When an iterative operation is performed on an eye (k is a natural number),
Out of the q symbols of d−2−
The above-mentioned estimated error locator polynomial where k positions are erasure positions
And the set of estimated error numerical polynomials are calculated by
The estimated error locator polynomial calculated at the time of execution and the number of estimated errors
Calculated from a set of value polynomials,
The polynomial and the estimated error numerical polynomial to the polynomial correction device.
The auxiliary polynomials for correction in the (k-1) th time
Two kinds of auxiliary polynomials calculated at the time of execution of the iterative operation of the eye
Is calculated. According to an embodiment of the present invention, a polynomial correction
The apparatus executes the k-th iteration of the polynomial calculation processing apparatus.
The degree of the estimated error locator polynomial calculated at the time is (k +
1) / 2, one symbol in the received codeword
Syndrome corresponding to Bol and d of the error numerical polynomial
The above two types of sums with the coefficient of the term of −2− (k + 1) / 2 order
The estimated error locator polynomial of each of the polynomials multiplied by the auxiliary polynomial of
Correction of the polynomial added to the polynomial and the estimated error numerical polynomial
The estimated error locator polynomial and the estimated error numerical polynomial
It is characterized by doing. The present invention relates to a syndrome calculating device, a polynomial
An arithmetic device and a polynomial correction device are provided. Sindrow
The system calculating unit calculates a received codeword consisting of q + 1 symbols.
And the least reliable of q symbols in the received codeword
Calculate the syndrome from the index designating d-1 positions
And outputs it to a polynomial arithmetic unit and a polynomial correction unit. Many
The term operation unit calculates the syndrome and the
d−2−k symbols having the lowest reliability among the q symbols
Estimated error locator polynomial with position as erasure position and estimated error number
.., D−2 with respect to k = 0, 1,..., D−2
It is calculated sequentially. Also, the polynomial arithmetic device is calculated
The estimated error location polynomial and the estimated error numerical polynomial
Are simultaneously calculated. Multiple shifts
By using a method based on the register synthesis means method,
The auxiliary polynomial consists of the estimation error location polynomial and the estimation error numerical polynomial.
Efficiently calculated as a work polynomial when calculating the formula
You. That is, the auxiliary polynomial needed to perform the correction
Does not require a special device for calculating
With. Estimated error position polynomial calculated by polynomial arithmetic unit
Double expansion of equation and estimated error numerical polynomial with codeword length q + 1
Estimation error locator polynomial and estimation for Reed-Solomon codes
In order to correct the error numerical polynomial, the present invention uses a polynomial correction
Equipment. The polynomial correction device is calculated by a polynomial arithmetic device.
Estimated error location polynomial and estimated error numerical polynomial
And the aforementioned q symbols in the received codeword
The syndrome corresponding to one removed symbol
Estimated error locator polynomial and estimated error number
Output a value polynomial. The polynomial correction device and the polynomial operation device are
Plays a central role in the invention. By these,
Estimation of Double Decompressed Reed-Solomon Soft Decision Decoder
The total number of error locator polynomials and estimated error numerical polynomials
Reduce the number of calculations and device scale to 1 / t of the conventional technology
More economical and efficient double-stretching lead solo
This makes it possible to configure a Mont decoding device. [0013] Next, an embodiment of the present invention will be described.
This will be described with reference to the drawings. Used in the following description
Double-extended Reed-Solomon code has the following three conditional expressions
Satisfy all (1). Vector on finite field GF (q) [0014] [Outside 1] Is a set of [0015] (Equation 1) Here, α is a primitive element of finite GF (q).
You. The code length of this double-extended Reed-Solomon code is q + 1
And the number of information symbols is q−d + 2 (q is a prime power
Squared). FIG. 1 shows a double extended lead according to an embodiment of the present invention.
It is a block diagram showing a Dosolomon decoding device. buffer
1 is the d-1 place with the lowest reliability in the received codeword
To temporarily store the index specifying the position. Syndrome arithmetic
The output device 2 receives the received codeword consisting of q + 1 symbols.
(W₀ , W₁ , ..., w_q ) And 0,
1, 2,..., Q-1st received symbol
(Starting at the 0th), d-2 with the lowest reliability
Index to specify the position (stored in buffer 1)
As input, syndrome S consisting of d-2 symbols
₀ , S₁ , ..., S_d-3 Is output. Syndrome
Details of the calculation process will be described. Received codeword (w₀ ,
w₁ , ..., w_q ), S '₀ , S '₁ , ...
・, S '_d-2Is calculated as in the following equation (1). [0018] (Equation 2) Each S '_j Is the coefficient of the term d-3-j
A -3 order polynomial is determined as in the following equation (2). [0020] (Equation 3) With this S ′ (x), the syndrome is
Polynomial S (x) = S as a coefficient₀ + S₁ x + ... + S
_d-3 x^d-3 Is calculated according to the following equation (3). In addition,
x₀, X₁ , ..., x_d-3 Is stored in buffer 1.
, Q-1 th of the received codeword
D-2 positions with the lowest reliability in the received symbol
Is an index to specify. Also, modx^d-2 Remainder divided by
Means taking extra time [0022] (Equation 4) Syndrome S₀ , S₁ , ..., S_d-3
Are the 0th, 1st,..., Q−1th synths in the received codeword.
, And w in the received codeword_q Q
It corresponds to the symbol. Buffer 3 stores the received codeword
Save occasionally. The polynomial arithmetic unit 4 calculates the syndrome
Syndrome S which is the output of the delivery device 2₀ , S₁ , ...
・, S_d-3 And the index x relating to the aforementioned low reliability position₀ , X
₁ , ..., x_d-3 , And k = 0, 1, ...
., D-2, 0, 1, 2,.
.., the reliability is highest in q-1st received symbol
The lower d-2-k positions (x_k , X_{k + 1} , ..., x
_d-3 ) Is the estimated error locator polynomial P ^(k)(x)
And the estimation error numerical polynomial R^(k)Calculate and output the set (x)
You. In addition, the polynomial arithmetic unit 4 calculates k = 0, 1,.
, For d-2, P^(k)(x), R^(k)Correct (x)
Auxiliary polynomial U for^(k)(x), V^(k)Calculate (x)
You. Details of the procedure executed by the polynomial arithmetic unit 4
This will be described later. The polynomial correction device 5 is a polynomial
Output P^(k)(x), R^(k)(x), U^(k)(x), V
^(k)(x) (k = 0, 1,..., d−2)
S '_d-2(Equation (1)) is input. S '_d-2 Is received
Q-th symbol w in codeword_qDraw corresponding to
It is. The polynomial correction device 5 has a polynomial P^(k)Next to (x)
Number L^(k) Otherwise, 2L^(k) When ≠ k + 1, P
^(k)(x), R^(k)(x) is output as it is and 2L^(k) = K
When +1, the q-th received symbol w_q Thin corresponding to
Drome S '_d-2 Using the parameter β determined by
And P^(k)(x), R^{(k )}Correct (x) as follows and output
I do. [0025] (Equation 5) Procedures executed by the polynomial correction device 5
Will be described later. The error value calculation device 6 includes a polynomial correction device 5
Output (this is again P^(k)(x), R ^(k)(written as (x)) or
From among the q + 1 symbols in the received codeword, each j =
For 0, 2,..., 2t, d-
Error obtained when 1-j positions are lost positions
vector [0028] [Outside 2] Is calculated and output. This error value calculation device 6
Search processing and error value estimation processing. Changer
H processing that satisfies the following equation (4)_i To 0,1, α, α
^Two , ..., α^q-2 Processing to calculate by full search from
Α that satisfies equation (4)_i Indicates the position of the estimation error
Index. Note that the i-th position in the received codeword is displayed.
The index to pass is α_i (O ≦ i ≦ q−1). [0029] (Equation 6) The error value estimating process is performed by j = 0, 1,.
·, For d-1, the error vector [0031] [Outside 3] Is calculated by the following procedure.
The most reliable of q + 1 symbols in the received codeword
Index indicating low dij positions (saved in buffer 1)
D)_j It expresses. Also, the estimated error position
Polynomial P^(j)Let P be the formal derivative of (x)^(j) ’(X)
You. As shown below, the error value estimating process is represented by α_q Is D
_j Slightly different depending on whether or not it is the original. [0032] (Equation 7)The estimated codeword selecting device 7 includes an error value calculating device.
Output of device 6 [0034] [Outside 4] For each of the received codewords [0035] [Outside 5] Calculates the distance with reliability and the distance with reliability
Is the smallest error vector [0036] [Outside 6] Is output. [0037] [Outside 7]Is added to the received codeword stored in buffer 3.
You. This is the output of the decoding device of the present invention. In addition, correction
If an impossible error is detected, the received codeword
Output as is. FIG. 2 is a flowchart showing the processing of the polynomial arithmetic unit 4.
FIG. 2 is a flowchart of FIG.
It shows an iterative operation algorithm consisting of iterative operations,
The details of this iterative algorithm are described below.
I do. This iterative algorithm is based on the
0, 1,..., Q-1
(Starting at 0th), d-2 with the lowest reliability
Index (x ₀ , X₁ , ..., x_d-3 )
And the syndrome S shown in equation (3)₀ , S₁ , ...
・, S_d-3 Is a syndrome polynomial S (x)
For each k = 0, 1,..., D-2, the following four
P that satisfies the condition^(k)(x), R^{(k )}(x) and
A set U of auxiliary polynomials described below^(k) (x), V^(k)Calculate (x)
I do. [0039] (Equation 8) Note that S '(x) is d-
It is a cubic polynomial. Of a polynomial that satisfies the above four conditions
Set P^(k)(x), R^(k)Regarding (x), L^(k) = DegP
^(k)(x). From condition (d), L^(k) Value is unique
Is decided. In the following, P^(k)(x), R^(k)(x) is a condition
It is assumed that (a), (b), (c), and (d) are satisfied.
P^(k)(x), R^(k)Using (x), the four for k + 1
A set of polynomials P satisfying the condition^{(k + 1)} (x), R^{(k + 1)} (
A method for calculating x) will be described. Polynomial set P
^{(k )}(x), R^(k)(x) has the following properties. Property 1 Polynomial R^(k)(x) is xx_k so
When divisible, P^{(k + 1)}(x) = P ^(k)(x), R
^{(k + 1)}(x) = Q^(k)(x), P^{(k + 1)}(x), R
^{(k + 1)}(x) is the condition (a) (b) (c) for k + 1
(D) is satisfied. Note that Q^(k)(x) = R^(k)(x) /
(Xx_k )far. The polynomial R^(k)(x) is xx_k Divisible by
Sometimes, by the method of Property 1, P^{(k +1)}(x), R
^{(k + 1)}(x) can be calculated. Next, R^(k)(x)
Is xx_kA case in which it is not divisible by will be described. next
There is such a property. Property 2 Polynomial R^(k)(x) is xx_k Divided by
Unbreakable and 2L^(k) When ≤k, P^{(k + 1)}(x)
= (Xx_k ) P^(k)(x), R^{(k + 1)}(x) = R^(k)(x)
In other words, P^{(k + 1)}(x), R^{(k + 1)}(x) is related to k + 1
Conditions (a), (b), (c) and (d) are satisfied. Polynomial R^(k)(x) is xx_k Divisible by
And 2L^(k) ≤k, The property 2 method
, P^{(k + 1)}(x), R^{(k + 1)}(x) can be calculated
You. Next, R^(k)(x) is xx_k Not divisible by and 2
L^(k) ≧The case when k + 1 is described. First, each
For k = 0, 1, 2,..., d−2,
A set of satisfying polynomials (U^(k)(x), V^(k)(x))
I do. This set of polynomials (U^(k)(x), V^(k)(x))
In a polynomial correction device 5 described later, P^(k)(x), R
^(k)An auxiliary polynomial for correcting (x) is obtained. [0045] (Equation 9) In the following, a set of polynomials (U^(k)(x), V
^(k)(x)) satisfies the conditions (A), (B), (C), and (D).
The explanation will be made on the assumption that the Well, R^(k)(x) is x
-X_kIndivisible and 2L^(k) When ≧ k + 1
P^{(k + 1)}(x), R^{(k + 1)}Regarding the calculation of (x), the following gender
There is quality. Property 3 R^(k)xx in (x)_k Divisible by
And 2L^(K) It is assumed that ≧ k + 1. V^(k)(x)
xx_k When divisible by P^{(k + 1)}(x) = (xx−x
_k ) P ^(k)(x), R^{(k + 1)}(x) = R^(k)(x)
P^{(k + 1)}(x), R^{(k + 1)}(x) is the condition for k + 1
(A), (b), (c), and (d) are satisfied. Finally, V^(k)(x) is xx_k Divisible by
The case when there is not is described. R^(k)(x) is xx_k Divided by
Q^(k)(x) and the remainder is r_k And Also, V
^(k)(x) is xx_k Quotient divided by W^(k)(x) and the remainder
V_k And At this time, P
^{(k + 1)}(x), R^{(k + 1)}(x) is calculated. Property 4 R^(k)(x) is xx_k Divisible by
And 2L^(k) It is assumed that ≧ k + 1. V^(k)(x)
xx_k When divisible by, P^{(k + 1)}(x) = P^(k) −
(R _k / V_k ) U^(k)(x), R^{(k + 1)}(x) = Q^(k)(x)
− (R_k / V_k ) W^(k)(x), P^{(k + 1)}(x),
R^{(k + 1)}(x) is the condition (a) (b) (c) for k + 1
(D) is satisfied. From the properties 1, 2, 3, and 4, the condition on k
(A) a set of polynomials P satisfying (b), (c) and (d)
^(k)(x), R^(k)From (x), a set of polynomials for k + 1
P^{(k + 1)}(x), R^{(k + 1)}(x) can be calculated.
Also, conditions (A), (B), (C), and (D) regarding k are satisfied.
Set of polynomials U^(k)(x), V^(k)From (x) to k + 1
Set of polynomials U^{(k + 1)}(x), V^{(k + 1)}Calculate (x)
To do so, perform the following procedure. [0051] (Equation 10) According to the above description, as an initial state of k = 0, [0052] [Equation 11] This gives an iterative algorithm
You. Note that S (x) has been described by equation (3). The flowchart of FIG. 2 shows that k = 0, 1,.
.., with respect to d-2, P^(k)(x), R^(k)(x), U
^(k)(x), V^(k)Iterative calculation algorithm for sequentially calculating (x)
It is a gorhythm. P^(k)(x), R^(k)(x) is the estimation error
Position polynomial, estimated error numerical polynomial,
^(k)(x), V^(k)(x) is an auxiliary polynomial. The flow of FIG.
As is clear from the chart, the polynomial correction device described later
Auxiliary polynomial U for performing the correction process at 5
^(k)(x), V^(k)(x) is used in the iterative algorithm
It has been introduced as a working polynomial. That is, the present invention
Says that no special device is needed for calculating the auxiliary polynomial
Has characteristics. Specifics regarding the above iterative operation algorithm
Here is a typical execution example. GF (2^Four ) On (17,11,
7) Take a double-extended Reed-Solomon code as an example. Sign bro
And the minimum distance is 7.
is there. The parameters q and d are in this case q = 16 and d, respectively.
= 7. If the received codeword is (0,0,0,0,0,
α⁹, 0,0,0, α¹⁴, 0,0,0,0,0, α⁷ ,
0) and the corresponding reliability information is (1, 1, 1,
1,1,1,1,1,1,0.8,0.8,0.8,
0.8, 0.8, 0.8, 0.9, 1). here
Where α is α^Four GF (2) satisfying + α + 1 = 0^Four ) Hara
As the origin, the reliability information, the closer to 0, the lower the reliability,
It is assumed that the closer to 1, the higher the reliability. 0,
, ..., q-1st symbol has the highest reliability
The index indicating d-2 positions, which are also lower, is Δα^Ten, Α¹¹, Α
¹², Α¹³, Α¹⁴It becomes｝. Where αⁱ Is counted from the beginning
Indicates the i-th position (the beginning is the 0th position). syndrome
Is calculated by the equations (2) and (3). ₀ = Α¹², S₁
= Α^Ten, S_Two = Α^Two , S_Three = Α¹², S_Four = Α⁶ And calculated
It is. This input is shown in the flowchart of FIG.
The polynomial operation device 4 that executes the processing shown in FIG.
^(k)(x), R^(k)(x), U^(k)(x), V^(k)(x) to k =
Calculation is performed for each of 0, 1, 2, 3, 4, and 5. This
These calculation results are output to the polynomial correction device 5. FIG. 4 is a block diagram showing an example of the polynomial correction device 5.
It is a lock figure. The polynomial correction device 5 includes the aforementioned polynomial.
Estimation error locator polynomial calculated by the terminology operation device 4 and estimation
Set of error numerical polynomials P^(k)(x), R^(k)(x) and auxiliary polynomial
Expression set U^(k)(x), V^(k)(x), and the aforementioned S '_d-2
Is entered. As we will see later, this example actually
Correction of the polynomial only when the following condition is satisfied:
Is made. [0056] (Equation 12) Therefore, when conditional expression (6) is not satisfied,
Input P of term correction device ^(k)(x), R^(k)(x) as it is
In this case, U
^(k)(x), V^(k)There is no need to save (x). In the received code word, the above-mentioned ｛x_k , X_{k + 1} ,
.., x_d-3 Includes a correctable error with｝ as the erasure position
And the output P of the polynomial arithmetic unit 4
^(k)(x), R ^(k)(x) is 2 degP^(k)(x) <k + 1
Is satisfied, P^(k)(x), R ^(k)(x) is each positive
Error location polynomial and error value polynomial
The calculating device 6 correctly calculates the error vector. [0058] [Outside 8] Can be requested. If conditional expression (6) is satisfied,
In general, the estimated error level which is the output of the polynomial arithmetic unit 4 is
Set polynomial P^(k)(x), estimation error numerical polynomial R^(k)(x)
Do not match the error locator polynomial and the error numerical polynomial, respectively.
No. The polynomial corrector 5 outputs the output of the polynomial arithmetic unit 4
P^(k)(x), R^(k)From (x), amend this
To calculate the correct error locator polynomial and the error numerical polynomial.
Offers a way to get out. ｛X in the received codeword_k , X
_{k + 1} , ..., x_d-3 Correctable error with｝ as the vanishing position
If the error locator polynomial σ
(X), the error numerical polynomial ω (x) satisfies the following four conditions.
This is the only set of polynomials to be added. [0060] (Equation 13) Note that S '_d-2 Is described by equation (1)
You. If the conditional expression (6) is satisfied, the polynomial
Output P^(k)(x), R^(k)(x) is the condition (a) (b)
(C) and (d)^(k)(x), V^(k)(x) is the condition (A)
Since (B), (C) and (D) are satisfied, the error locator polynomial
Equation σ (x) and error numerical polynomial ω (x) are as follows:
Can be calculated. [0062] [Equation 14] Where r_u Is the polynomial R^(k)d- of (x)
2-degP^(k)(x) The coefficient of the next term. Equation (7) is
about ω (x) [0064] [Outside 9] Has no effect on the calculation of the error vector.
Can be omitted. For similar reasons, the polynomial
R^(k)Simplifying the process related to the correction of (x), R
^(k)The correction for (x) is P^(k)Exactly the same as (x) correction
The auxiliary polynomial V^(k)(x) is S '_d-2 + R_u Multiplied by
A term may be added. Therefore, the conditional expression
When (6) is satisfied, the polynomial correction processing of FIG.
Therefore, a desired set of polynomials can be obtained. In addition,
2degP^(k)If (x)> k + 1, the received codeword
消失 x_k , X_{k + 1} , ..., x_d-3 About｝
Therefore, an uncorrectable error is included. With respect to the above processing, the polynomial
This will be described with reference to a specific execution example used in the description. FIG.
In the output of the polynomial arithmetic unit 4 shown in FIG.
^(Five)(x), R^(Five) (x) is   P^(Five)(x) = x^Three + X^Two + Α, R^(Five)(x) = x^Two + Α^Three x + α¹³... (8) This is corrected by the processing already described. Many
Term P^(Five)Since the degree of (x) is 3, 2.3 = 5 + 1
This satisfies conditional expression (6). Also, from equation (1),
S '_Five = Α⁹ And R^(Five)2 (= 5-3) of (x)
Since the coefficient of the term is 1, S ′_Five + R_u = Α⁷ And total
Is calculated. Thus, the output P of the polynomial correction device 5
^(Five)(x), R^(Five)(x) is calculated as follows. P^(Five)(x) = x^Three + X^Two + Α + α⁷ (Α⁶
x^Two + Α⁷ x + α⁹ ) = X^Three + Α⁶x^Two+ Α¹⁴x R^(Five)(x) = x^Two + Α^Three x + α¹³+ Α⁷ (X^Two + Α¹³x
+ Α⁶ ) = Α⁹ x^Two + Α¹¹x Hereinafter, P^(Five)(x), R^(Five)(x) is transmitted to the error value estimating device 6.
Is processed. By the above-described chain search processing, P
^(Five)(0) = P^(Five)(α^Five ) = P^(Five)(α⁹ ) = 0 is calculated
Error in the fifth, ninth and fifteenth symbols
It is determined that the error has occurred (the beginning is the 0th). Next
The procedure for calculating the error value described above is described in P. ^(Five)(x),
R^(Five)Applying for (x), the error for k = 5
Vector is [0067] [Outside 10] Is calculated. Also, this error vector and the reception
The distance with reliability from the codeword is 2.7. P
⁽ⁱ⁾(x), R⁽ⁱ⁾(x), (i = 0,1,2,3,4)
The same applies to the correction, error vector, and reliability
Calculate the attached distance. In the estimated codeword selection device 7,
Eventually the aforementioned error vector [0068] [Outside 11]Is selected, and (0, 0, 0, 0, 0,
0,0,0,0,0,0,0,0,0,0)
The result is added by the adder 8 to the output of the buffer 3. This is
The output of the entire double-extended Reed-Solomon decoding device of the present invention and
Become. [0069] As described above, the present invention provides a polynomial
An arithmetic device and a polynomial correction device are provided.
And a polynomial corrector that performs subsequent processing.
Thus, t problems of the prior art,
Parallel processing (or iterative processing) by the pad division device
Does not need to be executed, and the number of calculations and the device scale are reduced by 1 /
t, and the double extended Reed-Solomon soft
The estimated codeword calculated by the decision decoding device is based on the conventional technology.
Exactly matches what the decoding device calculates, and
The error rate for each symbol of
It will be the same. That is, compared to the prior art,
Error rate without deteriorating the error rate of
The number of calculations required to calculate the
The installation scale can be reduced to about 1 / t, making it more economical.
An efficient double-extended Reed-Solomon soft decision decoder
Can be achieved.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing a double-extended Reed-Solomon decoding device according to an embodiment of the present invention. FIG. 2 is a flowchart illustrating a processing example of a polynomial operation device 4; FIG. 3 is a diagram illustrating an example of an iterative operation algorithm. FIG. 4 is a flowchart illustrating an example of a polynomial correction device 5; FIG. 5 is a block diagram showing a conventional soft decision decoding device. [Description of Code] 1 Buffer for storing symbols corresponding to low reliability positions 2 Syndrome calculation device 3 Buffer for storing received codewords 4 Polynomial operation device 5 Polynomial correction device 6 Error value calculation device 7 Estimated codeword selection device 8 Adder 9 _{1 to} 9 _t Euclidean divider

   ────────────────────────────────────────────────── ─── Continuation of front page       (56) References Noriyuki Kamiya, "Reed-Solomo               GMD decoding of n codes and generation of multiplexed sequence               Shift register synthesis ''               Academic report, IT93-113, March 24, 1994               Days, p. 43−48                 E. FIG. Berlekamp, "Bown               deed Distance +1 So               ft-Decision Reed-S               olomon Decoding, "I               EEE Transactions o               n Information Theo               ry, Vol. 42, No. 3, May               1996, pp. 704-720.

Claims (1)

(57) Claims 1. A received codeword and a reliability representing the reception state of the received codeword for a double-extended Reed-Solomon code having a code block length of q + 1 (q is a power of a prime number). A codeword in the received codeword is corrected by calculating an estimated codeword candidate using the information and selecting a codeword most similar to the received codeword from the estimated codeword candidates. In the decompressed Reed-Solomon decoding device, the reception codeword consisting of q + 1 symbols and the reception codeword.
Selected from the q symbols in the word according to the reliability information.
D-2 positions (d is a natural number) with the lowest selected reliability
D-2 repetitions from the syndrome calculated from the information
Using an iterative algorithm consisting of
Low d-2- (k-1) (where 1 ≦ k ≦ d-2,
k indicates the number of executions of the iterative operation algorithm)
For the estimated error locator polynomial whose position is the erasure position,
In the corresponding auxiliary polynomial, "d-2-kth reliability
Error value polynomial value at the position where
Value of auxiliary polynomial corresponding to numerical polynomial "
By adding the values, q symboles in the received codeword
Of the d-2-k positions with the lowest reliability
Estimated error locator polynomial, estimated error numerical polynomial, and
And the estimated error locator polynomial and the estimated error numerical polynomial, respectively.
Calculating means for calculating two auxiliary polynomials corresponding to
If, calculated at the k-th iteration of the polynomial calculator
The degree of the estimated error locator polynomial is equal to (k + 1) / 2
If it corresponds to one symbol in the received codeword
D-2- (k) of the syndrome and the estimated error numerical polynomial
+1) / 2 sum of the coefficient of the term and the polynomial
The polynomials multiplied by the two auxiliary polynomials calculated by the means are respectively
Add the estimated error location polynomial and the estimated error numerical polynomial
A polynomial correction means for calculating a polynomial equation, the estimated error location polynomial calculated by the polynomial correction means
The estimated error numerical polynomial calculated by the polynomial correction means;
And a means for calculating an estimated codeword candidate from the above, and selecting a codeword most similar to the received codeword.