AN2407 データシートの表示（PDF） - Freescale Semiconductor

部品番号

コンポーネント説明

メーカー

AN2407

Reed Solomon Encoder/Decoder on the StarCore™ SC140/SC1400 Cores, With Extended Examples

Freescale Semiconductor 

Theory

2. Derivation of the error-location polynomial: The output of the Berlekamp-Massey algorithm is the

error-location polynomial Λ(x), defined as:

Λ(x) = (1 + xX1)(1 + xX2)(1 + xX3)…(1 + xXν) ≡ 1 + λ1x + λ2x2 + λ3x3 + …λνxν

Λ(x) has at most ν different roots. The inverses of the roots have the form αik , where ik is the error-

location index. It can be proven [6] that the so-called Newton identity holds for the coefficients of Λ(x)

and the syndromes:

.

Sj + ν + λ1Sj + ν – 1 + λ2Sj + ν – 2…λνSj = 0

The Berlekamp-Massey algorithm is an iterative way to find a minimum-degree polynomial that

satisfies the Newton identities for any j. If the degree of Λ(x) obtained by the Berlekamp-Massey

algorithm exceeds T, this indicates that more than T errors have occurred and the block is therefore not

correctable. In this case, the decoder detects the occurrence of errors in the block, but no further

attempt of correction is made, and the decoding procedure stops at this point for this block.

3. Roots search: The roots of the error-location polynomial are obtained by an exhaustive search, that is,

by evaluating Λ(x) at all Galois field elements, checking for possible zero results. The exponents of the

inverses of the roots are equal to the error-location indices.

If the number of roots is less than the degree of Λ(x), more than T errors have occurred. In this case,

errors are detected, but they are not corrected, and decoding stops at this point for this block.

4. Derivation of error values: The error values are obtained from the Forney algorithm in this implemen-

tation. Once the error locations Xk are found, the error values Yk are found from the ν first syndromes

equation by solving the following:

X1 X2 … Xν Y1

S1

… … …… … =–…

X1ν X2ν … Xνν Yν

Sν

The Forney algorithm is an efficient way to invert the matrix and solve for the errors values Y1 – Yk.

2.3 Error-Correcting Performance of Reed-Solomon Codes

The Reed-Solomon code ensures error detection and correction as long as the number of errors is at most T. If more

than T errors occur, one of two things happen:

• An uncorrectable error is detected. No attempts are made by the decoder to correct the block.

• The received block accidentally resembles a valid code word different from the correct one and the

decoder decodes the block into an incorrect code word.

Under the assumption

the following: Ps= 1

of

–

completely

(1 – Pb)m

random bit errors, the bit-error rate Pb is related to the symbol-error rate

On the other hand, if the symbol errors are independent, the probability

Ps

of

by

more than T errors occurring in a block is given by:

T

∑ PE > T = 1 –

⎛ N⎞

⎝ i⎠

(Ps)i(1

–

Ps)N

–

i

i=0

Reed Solomon Encoder/Decoder on the StarCore™ SC140/SC1400 Cores, With Extended Examples, Rev. 1

Freescale Semiconductor

9

Share Link: