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.

Bibliographie

[1] Plank J., “A Tutorial on Reed–Solomon coding for fault-tolerance in RAID-like systems”, Software-Practice Experience, 27:9 (1997), 995–1012 | 3.0.CO;2-6 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[2] Plank J., Xu L., “Optimizing cauchy Reed–Solomon codes for fault-tolerant network storage applications”, The 5th IEEE Intern. symposium on network computing and applications (2006), 173–180

[3] Plank J., Blaum M., Hafner J., “SD codes: erasure codes designed for how storage systems really fail”, FAST-2013: 11th USENIX conference on file and storage technologies (2013), 95–104

[4] Papailiopoulos D., Luo J., Dimakis A., Huang C., Li J., “Simple regenerating codes: network coding for cloud storage”, INFOCOM. Proceedings IEEE (2012), 2801–2805

[5] Huang C., Simitci H., Xu Y., Ogus A., Calder B., Gopalan P., Li J., Yekhanin S., “Erasure coding in windows azure storage”, USENIX annual technical conference (2012) (data obrascheniya: 11.07. 2016) https://www.usenix.org/system/files/conference/atc12/atc12-final181_0.pdf

[6] Huang C., Chen M., Li J., “Pyramid Codes: flexible schemes to trade space for access efficiency in reliable data storage systems”, NCA-2007: IEEE Intern. symposium on network computing and applications (2007), 79–86

[7] Peterson W., Weldon E., Error-correcting codes, MIT Press, Cambridge, 1972, 572 pp. | MR

[8] Berlekamp E., Algebraic coding theory, World scientific Publishing Co, Singapore, 2015, 501 pp. | MR | Zbl

[9] Lidl R., Niederreiter H., Finite fields, v. 1, 2nd ed., Cambridge University Press, Cambridge, 1997, 755 pp. | MR

[10] Plank J., Greenan K., Miller E., “Screaming fast galois field arithmetic using Intel SIMD instructions”, FAST–2013: 11th USENIX conference on file and storage technologies (2013), 299–306

[11] Plank J., “XOR's lower bounds and MDS codes for storage”, IEEE Information theory workshop (2011), 529–551

[12] Trifonov P., “Low-complexity implementation of RAID based on Reed–Solomon codes”, ACM transactions on storage, 2015 (data obrascheniya: 26.10.2016) http://dl.acm.org/citation.cfm?id=2700308

[13] Knuth D., The art of computer programming, v. 1, 3rd ed., Addison-Wesley Press, Reading, Massachusetts, 1997, 672 pp. | MR

[14] Uteshev A., Kalinina E., Lectures in algebra, v. II, Solo Press, Saint Petersburg, 2007, 279 pp. (In Russian)

[15] Horn R. A., Johnson Ch. R., Matrix analysis, Cambridge University Press, Cambridge, 1986, 612 pp. | MR | MR

[16] Intel Intelligent Storage Acceleration Library, (data obrascheniya: 11.07.2016) https://01.org/intel

[17] Jerasure: Erasure Coding Library, (data obrascheniya: 11.07.2016) http://jerasure.org/