Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya, 2016, Issue 4, Pages 4–17
DOI: https://doi.org/10.21638/11701/spbu10.2016.401
(Mi vspui306)
 

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
Full-text PDF (398 kB) Citations (1)
References:
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
Bibliographic databases:
Document Type: Article
UDC: 004.056.3
Language: Russian
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
Citation in format AMSBIB
\Bibitem{MarUte16}
\by A.~V.~Marov, A.~Yu.~Uteshev
\paper Matrix formalism of the Reed--Solomon codes
\jour Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr.
\yr 2016
\issue 4
\pages 4--17
\mathnet{http://mi.mathnet.ru/vspui306}
\crossref{https://doi.org/10.21638/11701/spbu10.2016.401}
\elib{https://elibrary.ru/item.asp?id=28173682}
Linking options:
  • https://www.mathnet.ru/eng/vspui306
  • https://www.mathnet.ru/eng/vspui/y2016/i4/p4
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления
    Statistics & downloads:
    Abstract page:185
    Full-text PDF :73
    References:28
    First page:9
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024