(44-2) 18 * << * >> * Русский * English * Содержание * Все выпуски

Параллельная машинная арифметика для рекуррентных систем счисления в неквадратичных полях
В.М. Чернов 1,2

1 Самарский национальный исследовательский университет имени академика С.П. Королёва,
443086, Россия, г. Самара, Московское шоссе, д. 34,
2 ИСОИ РАН – филиал ФНИЦ «Кристаллография и фотоника» РАН,
443001, Россия, г. Самара, ул. Молодогвардейская, д. 151

 PDF, 853 kB

DOI: 10.18287/2412-6179-CO-666

Страницы: 274-281.

Аннотация:
В работе предлагается новый метод синтеза систем машинной арифметики для «безошибочных» параллельных вычислений. Отличием предлагаемого подхода от вычислений в традиционных системах остаточных классов для прямой суммы модулярных колец является параллелизация вычислений в неквадратичных расширениях простых конечных полей, элементы которых представлены в системах счисления, порождёнными последовательностями степеней корней характеристического полинома рекуррентной последовательности. Работа продолжает и обобщает исследования автора, в которых, в частности, рассматривались рекуррентные соотношения n-боначчи (трибоначчи, тетрабоначчи и т.д.).

Ключевые слова:
конечные поля, рекуррентная система счисления, параллельная машинная арифметика.

Цитирование:
Чернов, В.М. Параллельная машинная арифметика для рекуррентных систем счисления в неквадратичных полях / В.М. Чернов // Компьютерная оптика. – 2020. – Т. 44, № 2. – С. 274-281. – DOI: 10.18287/2412-6179-CO-666.

Благодарности:
Работа выполнена при поддержке Министерства науки и высшего образования РФ в рамках выполнения работ по Государственному заданию ФНИЦ «Кристаллография и фотоника» РАН (соглашение № 007-ГЗ/Ч3363/26) в части исследования систем счисления и Российского фонда фундаментальных исследований (проекты РФФИ №19-07-00357 А № 18-29-03135_ мк) в части исследования машинной арифметики.

Литература:

  1. Ananda Mohan, P.V. Residue number systems / P.V. Ananda Mohan. – Basel: Birkhäuser, 2016. – 351 p. – ISBN: 978-3-319-41383-9.
  2. Embedded systems design with special arithmetic and number systems / ed. by A.S. Molahosseini, L.S. de Sousa, Ch.-H. Chang. – Cham: Springer, 2017. – 389 p. – ISBN: 978-3-319-49741-9.
  3. Вариченко, Л.В. Абстрактные алгебраические системы и цифровая обработка сигналов / Л.В. Вариченко, В.Г. Лабунец, М.А. Раков. – Киев: Наукова думка, 1986.
  4. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток / Г. Нуссбаумер; пер. с англ. – М.:Радио и связь, 1985. – 248 с.
  5. Golomb, S.W. Properties of the sequence 3∙2n+1 / S.W. Golomb // Mathematics of Computation. – 1976. –Vol. 30, Num. 135. – P. 657-663.
  6. Alfredson, L.-I. VLSI Architectures and arithmetic operations with application to the Fermat number transform / L.-I. Alfredson. – Linkӧping: Linkӧping University, 1996.
  7. Chernov, V.M. Fast algorithm for “error-free” convolution computation using Mersenne-Lucas codes / V.M. Chernov // Chaos, Solitons and Fractals. – 2006. – Vol. 29. – P. 372-380. – DOI: 10.1016/j.chaos.2005.08.081.
  8. Чернов, В.М. Квазипараллельный алгоритм для безошибочного вычисления свёртки в редуцированных кодах Мерсенна–Люка / В.М. Чернов // Компьютерная оптика. – 2015. – Т. 39, № 2. – C. 241-248. – DOI: 10.18287/0134-2452-2015-39-2-241-248.
  9. Чернов, В.М. Системы счисления в модулярных кольцах и их приложения к «безошибочным» вычислениям / В.М. Чернов // Компьютерная оптика. – 2019. – Т. 43, № 5. – С. 901-911. – DOI: 10.18287/2412-6179-2019-43-5-901-911.
  10. Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований / В.М. Чернов. – М.: Физматлит, 2007. – 264 с. – ISBN: 978-5-9221-0940-6.
  11. Чернов, В.М. Фибоначчи, трибоначчи, …, гексаначчи и параллельная безошибочная машинная арифметика / В.М. Чернов // Компьютерная оптика. – 2019. – Т. 43, № 6. – С. 1072-1078. – DOI: 10.18287/2412-6179-2019-43-6-1072-1078.
  12. Гельфонд, А.О. Исчисление конечных разностей / А.О. Гельфонд. – 4-е изд. – М.: URSS, 2006.
  13. Wimp, J. Computations with recurrence relations / J. Wimp. – Boston, MA: Pitman, 1984.
  14. Шпарлинский, И.Е. О некоторых вопросах теории конечных полей / И.Е. Шпарлинский // Успехи математических наук. – 1991. – Т. 46, Вып. 1(277). – С. 165-200.
  15. Brown, J.L. Note on complete sequences of integers / J.L. Brown // The American Mathematical Monthly. – 1961. – Vol. 68, Issue 6. – P. 557-560. – DOI: 10.2307/2311150.
  16. Грегори, Р. Безошибочные вычисления. Методы и приложения / Р. Грегори, Е. Кришнамурти; пер. с англ. – М.: Мир, 1988. – 207 с.
  17. Дэвенпорт, Дж. Компьютерная алгебра / Дж. Дэвенпорт, И. Сирэ, Э. Турнье. – М.: Мир, 1991. – 352 с.
  18. Von Zur Gathen, J. Factoring polynomials over finite fields: A survey / J. Von Zur Gathen, D. Panario // Journal of Symbolic Computation. – 2001. – Vol. 31, Issues 1-2. – P. 3-17.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20