|
This article is cited in 1 scientific paper (total in 1 paper)
Applied mathematics
Matrix formalism of the Reed–Solomon codes
A. V. Marov, A. Yu. Uteshev St. Petersburg State University, 7–9, Universitetskaya nab.,
St. Petersburg, 199034, Russian Federation
Abstract:
The paper is focused onto modification of the involved algorithms of coding and error (i. e., failures and
silent data corruptions) correction in the Reed–Solomon codes. These modifications involve matrix formalism and are based on an algorithm for the
Vandermonde matrix inversion. For such a matrix $ V=\left[
\lambda_j^{i-1} \right]_{i,j=1}^{n} $ the suggested algorithm
computes the columns $ V_{[1]}^{-1},\dots, V_{[n-1]}^{-1},
V_{[n]}^{-1} $ of the matrix $ V^{-1} $ recursively, starting
from the last column, via the formulas
$$ V_{[n]}^{-1}=\Xi_0,\ V_{[j]}^{-1}=\Xi_{n-j}- \sigma_1 V_{[j+1]}^{-1} - \sigma_2 V_{[j+2]}^{-1}- \dots - \sigma_{n-j} V_{[n]}^{-1} ,~ \ j=n-1,n-2,\dots,1 \, .
$$
Here $ \Xi_k=\left[\lambda_1^k/W^{\prime}(\lambda_1),\dots,
\lambda_n^k/W^{\prime}(\lambda_n) \right]^{\top}, \sigma_k =
\sum_{j=1}^n \lambda_j^{n+k-1}/W^{\prime}(\lambda_j) $, $
k=\overline{1,n} $, and $ W(x)=\prod_{k=1}^n (x-\lambda_k) $. The
obtained result is applied for realization of systematic coding of
the $ n $-vector of the information blocks with the aid of
multiplication (in an appropriate Galois field) by the matrix $
\mathbf K=[\widetilde{W_i}(a^{N-j-1})],\ i=\overline{1,m},j=\overline{0,n-1} $. Here $ \widetilde{W_\ell} (x),\ell=\overline{1,m} $, denote the basic Lagrange interpolation
polynomials generated by the powers of a primitive element of the
field, while $ m $ stands for the number of redundancy blocks
(syndromes). In the framework of this ideology, an error
correcting procedure is also realized. The program implementation
in C demonstrates high performance results (compared to existing
software) with solid perspectives for parallelization. Refs 17.
Fig 1.
Keywords:
error-correcting codes, Reed–Solomon codes, Vandermonde matrix.
Received: July 15, 2016 Accepted: September 29, 2016
Citation:
A. V. Marov, A. Yu. Uteshev, “Matrix formalism of the Reed–Solomon codes”, Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 2016, no. 4, 4–17
Linking options:
https://www.mathnet.ru/eng/vspui306 https://www.mathnet.ru/eng/vspui/y2016/i4/p4
|
Statistics & downloads: |
Abstract page: | 185 | Full-text PDF : | 73 | References: | 28 | First page: | 9 |
|