Matrix formalism of the Reed--Solomon codes

A. V. Marov ; A. Yu. Uteshev

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 4 (2016), pp. 4-17

Résumé

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.

Détail

Keywords: error-correcting codes, Reed–Solomon codes
Mots-clés : Vandermonde matrix.