ПРОГРАММНО-АЛГОРИТМИЧЕСКАЯ РЕАЛИЗАЦИЯ КОДОВ РИДА-СОЛОМОНА ДЛЯ ПОЛЕЙ ГАЛУА ВЫСОКОГО ПОРЯДКА

  • Владимир Владимирович Винников ООО "Акронис"; Федеральный исследовательский центр "Информатика и управление" РАН
  • Людмила Владимировна Иваничкина ООО "Проект Икс"; Московский физико-технический институт (государственный университет)

Аннотация

В статье приводится оригинальный подход к программно-алгоритмической реализации кодов Рида—Соломона для систем хранения сверхбольших объемов данных. Сравниваются самые популярные алгоритмы алгебраических операций умножения над конечными полями, рассматриваются их преимущества и недостатки, зависящие от мощности алфавитов кодируемых сообщений. В работе показаны различия в требованиях к параметрам избыточного кодирования для систем помехоустойчивой передачи данных по каналам связи и систем долгосрочного надёжного хранения данных с отказоустойчивым доступом. Предложен алгоритм умножения, в котором подходы к быстрому умножению с помощью таблиц и методов «разделяй и властвуй» скомбинированы с целью достижения компромисса между объемом выделяемой оперативной памяти и количеством затрачиваемых арифметических операций. Приведено описание программной реализации алгоритма на языке C++ в виде листингов.

Сведения об авторах

Владимир Владимирович Винников, ООО "Акронис"; Федеральный исследовательский центр "Информатика и управление" РАН

технический писатель; кандидат физико-математических наук, старший научный сотрудник отдела вычислительной физики Вычислительного центра им. А.А. Дородницына

Людмила Владимировна Иваничкина, ООО "Проект Икс"; Московский физико-технический институт (государственный университет)

старший разработчик; аспирант факультета управления и прикладной математики 

Литература

1. Ivanichkina L. Computer Simulator of Failures in Super Large Data Storage / L. Ivanichkina, A. Neporada // Contemporary Engineering Sciences. – 2015. – Т. 8. – № 28. – C. 1679–1691.
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.
Опубликована
2016-11-26
Как цитировать
ВИННИКОВ, Владимир Владимирович; ИВАНИЧКИНА, Людмила Владимировна. ПРОГРАММНО-АЛГОРИТМИЧЕСКАЯ РЕАЛИЗАЦИЯ КОДОВ РИДА-СОЛОМОНА ДЛЯ ПОЛЕЙ ГАЛУА ВЫСОКОГО ПОРЯДКА. Современные информационные технологии и ИТ-образование, [S.l.], v. 12, n. 3-2, p. 125-130, nov. 2016. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/131>. Дата доступа: 01 feb. 2023
Раздел
Исследования и разработки в области новых ИТ и их приложений