ALGORITHMIC AND SOFTWARE IMPLEMENTATION OF REED–SOLOMON ERASURE CODES FOR GALOIS FIELDS OF HIGH ORDER
Abstract
This paper is concerned with the novel approach to algorithmic and software implementation of Reed–Solomon codes for super large data storage systems. We compare the most popular algorithms of multiplication over finite fields and consider their pros and cons depending on the alphabet power of messages to encode. This work emphasizes differences in the redundancy parameter requirements for erasure codes designed for either noise-resistant data transfer over communication channels or long term reliable data storing with fault-tolerant access. We propose the multiplication algorithm that combines table and “divide and conquer” approaches to fast multiplication to achieve a compromise between the volume of allocated random access memory and the number of required arithmetic operations. The paper provides the listings with C++ program implementation of the presented algorithm.
References
2. Ivanichkina L. Mathematical methods and models of improving data storage reliability including those based on finite field theory / L. Ivanichkina, A. Neporada // Contemporary Engineering Sciences. – Т. 7. –№ 28. – 2014. – C. 1589 – 1602.
3. ETSI EN 300 744 V1.6.1 (2009-01) Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for digital terrestrial television // European Standard (Telecommunications series). – 2009. – 66 С.
4. Seroussi G. Table of low-weight binary irreducible polynomials. – Hewlett-Packard Laboratories, 1998.
5. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах //ДАН СССР. – 1961. – Т. 145. – № 2. – С. 293-294.
6. Toom A. L. The complexity of a scheme of functional elements realizing the multiplication of integers //Soviet Mathematics Doklady. – 1963. – Т. 3. – №. 4. – С. 714-716.
7. Schönhage D. D. A., Strassen V. Schnelle multiplikation grosser zahlen //Computing. – 1971. – Т. 7. – № 3-4. – С. 281-292.
8. Fürer M. Faster integer multiplication //SIAM Journal on Computing. – 2009. – Т. 39. – № 3. – С. 979-1005.
9. Koc C. K., Acar T. Montgomery multiplication in GF (2k) //Designs, Codes and Cryptography. – 1998. – Т. 14. – № 1. – С. 57-69.
10. Wang B. F., Chen C. L., Chen G. H. A simple approach to implementing multiplication with small tables //Information Processing Letters. – 1991. – Т. 37. – № 6. – С. 327-329.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
