ПРОГРАММНО-АЛГОРИТМИЧЕСКАЯ РЕАЛИЗАЦИЯ КОДОВ РИДА-СОЛОМОНА ДЛЯ ПОЛЕЙ ГАЛУА ВЫСОКОГО ПОРЯДКА
Аннотация
В статье приводится оригинальный подход к программно-алгоритмической реализации кодов Рида—Соломона для систем хранения сверхбольших объемов данных. Сравниваются самые популярные алгоритмы алгебраических операций умножения над конечными полями, рассматриваются их преимущества и недостатки, зависящие от мощности алфавитов кодируемых сообщений. В работе показаны различия в требованиях к параметрам избыточного кодирования для систем помехоустойчивой передачи данных по каналам связи и систем долгосрочного надёжного хранения данных с отказоустойчивым доступом. Предложен алгоритм умножения, в котором подходы к быстрому умножению с помощью таблиц и методов «разделяй и властвуй» скомбинированы с целью достижения компромисса между объемом выделяемой оперативной памяти и количеством затрачиваемых арифметических операций. Приведено описание программной реализации алгоритма на языке C++ в виде листингов.
Литература
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.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
