Page 53 - ISCI’2017

e i X i j +u + e λ u − 1 X i j +u − 1 + ...+ e λ 1 X i + j 1 + e λ 0 X i j = 0
i
i
i
The last equality holds for any j and i. Will sum by all i = 0…n – 1:
N
−
∑ 1 ( X i j +u + e λ u − 1 X i j +u − 1 + ...+ e λ X i + j 1 + e λ 0 X i j ) 0 .
=
e
i
i
i
i
1
= i 0
Change the order of summation, will get out the coefficients of the polynomial Λ(x) to a sign
of summation, we will get:
N − 1 N − 1 N − 1 N − 1
e X i + λ ⋅ e X i + ...+ λ ⋅ e X i + λ ⋅ e X i = 0.
∑ i j +u u − 1 ∑ i j +u − 1 1 ∑ i + j 1 0 ∑ i j
= i 0 = i 0 = i 0 = i 0
The value of each summand in the last expression corresponds to a multiplication of the
coefficients of the polynomial Λ(x) to the corresponding syndromes in the expression (11), so we can

write
sj+u + λu-1 ∙ sj+u-1 + … + λ1 ∙ sj+1 + λ0 ∙ sj = 0.

We rewrite the expression for each j = 0…u, we obtain a system of linear equations:

su + λu-1 ∙ su-1 + … + λ1 ∙ s1 + λ0 ∙ s0 = 0,
su+1 + λu-1 ∙ su + … + λ1 ∙ s2 + λ0 ∙ s1 = 0, (14)

…

s2∙u + λu-1 ∙ s2∙u-1 + … + λ1 ∙ su+1 + λ0 ∙ su = 0.
System from u linear equations (14) withe u variables (unknowns) can be solve, the complexity

of its solution increases polynomial from the number of variables (unknowns) [38-40]. For example,

3
the solution for systems (14) by the Gaussian elimination will need to execute u arithmetic operations
(additions and multiplications over the elements of the field GF(q )).
m
Solution of the system (14) gives the values of the error locator polynomial coefficients (13).
m
Radicals of the polynomial (13) are the locators, which are elements of the field GF(q ), which clearly
indicate the location of the non-zero elements of the error vector e. Consequently, the radicals of the

equation (13) is necessary to find for fault isolation.
The most simple procedure of the radicals search Λ(x) consists in a substitution into a

polynomial all n elements Xj ∈ GF(q ) and selecting those elements that become zero Λ(x). In the
m
literature, this technique is called the procedure Chenya [38-40]. Based on Horner scheme will rewrite
the polynomial Λ(x) as

x
x
x
Λ (x ) = x u + λ − 1 x u − 1 + λ − 2 x u − 1 ... λ ++ 1 x λ = (...(( + λ u − 1 ) + λ u − 2 ) + ... λ+ 1 ) + λ .
x
0
0
u
u
For a calculation of a volume of the polynomial Λ(x) in this form, will need no more u – 1
m
arithmetic operations (additions and multiplications over the elements of the field GF(q )), i.e.
complexity of this decoding step does not exceed n(u – 1) arithmetic operations.
53