Page 54 - ISCI’2017

th
After error’s localization – finding of the error locators Хj, error values in j symbol will need
to calculate, i.e. will calculate the elements of a vector e and will restore the code word c = c* – e.
To find the error values use the equation (11). Let us substitute the values found locators Хj and

variables (unknowns) ej in an equations system. The last ei at i ≠ j are equal to zero. Consequently,
the equations system (11) will write as:

i
e
s 0 = ∑ i X ,
0
i ∈J
i
s 1 = ∑ i X ,
e
1
i ∈J
…

e
s n −k −1 = ∑ i X n i −k −1 ,
i ∈J
where J is a set of indexes of non-zero elements of the error vector, i.e. a set of error locator numbers,

at the same J = u ≤ t. Obtained system from n – k linear equations has J = u ≤ t unknown error
volumes ei, at the same t < n – k. Consequently, this system is solvable; its solution gives the unknown

non-zero error volumes of the vector e. To solve the equations system from u variables (unknowns)
3
by the Gaussian elimination, will need to execute u arithmetic operations (additions and
m
multiplications over the elements of the field GF(q )). To restore the code word of n-code symbols
length is enough to remove the effect of the found error vector: c = c* – e, i.e. to execute u arithmetic
operations.

Thus, decoding problem of the algebraic (n, k, d)-block code (finding the error vector e = (e0,

 −1d 
e1, …, en-1)) reduces to solving two systems of linear equations from ≤ tu =   unknowns and
 2

3
to calculating n-variables of the polynomial Λ(x) of a degree u. u arithmetic operations will be to
need for the treatment of matrices and solving systems of linear equations that for large u may require

significant computational expenditures. In practice, the Berlekamp–Massey algorithm uses for a
algebraic codes decoding, an essence of which is finding the shortest linear feedback shift register

(LFSR) for a given binary output sequence. It also is generating the known sequence of the syndromes

2
s = (s0, s1, …, sn-k-1). The complexity this algorithm is u arithmetic operations. The Berlekamp–
Massey recurrent algorithm [38-40] is even more effective in terms of computational complexity. The

asymptotic complexity of decoding Reed-Solomon codes in this case does not exceed the volume
2
O(nlog n), and very close to the value O(nlogn).
,
Reed-Solomon codes have small length – a number of radicals X X 1 ,..., X nk 1 ∈ GF (q m )
0
−−
cannot be than a elements number of the field GF(q ) and, hence, n ≤ q – 1 (a code length can
m
m
54