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

Системы счисления в модулярных кольцах и их приложения к «безошибочным» вычислениям

В.М. Чернов 1,2

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

 PDF, 843 kB

DOI: 10.18287/2412-6179-2019-43-5-901-911

Страницы: 901-911.

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

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

Цитирование:
Чернов, В.М. Системы счисления в модулярных кольцах и их приложения к «безошибочным» вычислениям / В.М. Чернов // Компьютерная оптика. – 2019. – Т. 43, № 5. – С. 901-911. – DOI: 10.18287/2412-6179-2019-43-5-901-911.

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

Литература:
  1. Bergman, G. A number system with an irrational base / G. Bergman // Mathematics Magazine. – 1957. – Vol. 31, Issue 2. – P. 98-110.
  2. Rousseau, C. The Phi number system revisited. / G. Rousseau // Mathematics Magazine. – 1995. – Vol. 48, Issue 4. – P. 283-284.
  3. Стахов, А.П. Коды золотой пропорции / А.П. Стахов // М.: Радио и связь, 1984. – 152 с.
  4. Katai, I. Canonical number systems for complex integers / I. Katai, J. Szabo // Acta Scientiarum Mathematicarum. – 1975. – Vol. 37. – P. 255-260.
  5. Thuswardner, J. Elementary properties of canonical number systems in quadratic fields / J. Thuswaldner. – In: Application of Fibonacci numbers / ed. by G.E. Bergum). – Dordrecht, Boston, London: Kluwer Academic Publishers, 1996. – Vol. 7. – P. 405-414.
  6. Ananda Mohan, P.V. Residue number systems / P.V. Ananda Mohan. – Basel: Birkhäuser, 2016. – 351 p. – ISBN: 978-3-319-41383-9.
  7. Embedded systems design with special arithmetic and number systems / ed. by A.S. Molahosseini, L.S. de Sousa, C.-H. Chang. – Springer International Publishing AG, 2017. – 389 p. – ISBN: 978-3-319-49741-9.
  8. Chernov, V. Fast algorithm for “error-free” convolution computation using Mersenne-Lucas codes / V. Chernov // Chaos, Solitons and Fractals. – 2006. – Vol. 29. – P. 372-380.
  9. Чернов, В.М. Квазипараллельный алгоритм для безошибочного вычисления свёртки в редуцированных кодах Мерсенна–Люка / В.М. Чернов // Компьютерная оптика. – 2015. – Т. 39, № 2. – C. 241-248. – DOI: 10.18287/0134-2452-2015-39-2-241-248.
  10. Nussbaumer, H.J. Fast Fourier transform and convolution algorithms / H.J. Nussbaumer. – Berlin, Heidelberg: Springer-Verlag, 1981.
  11. Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов / Р. Блейхут; пер с англ. – М: Мир, 1989. – 448 с.
  12. Wimp, J. Computations with recurrence relations / J. Wimp // Boston, MA: Pitman, 1984.
  13. Masáková, Z. Arithmetics in number systems with a negative base / Z. Masáková, E. Pelantová, T. Vávra // Theoretical Computer Science. – 2011. – Vol. 412, Issues 8-10. – P. 835-845.
  14. Schönhage, A. Schnelle Multiplikation großer Zahlen / A. Schönhage, V. Strassen // Computing. – 1971. – Vol. 7. – P. 281-292.
  15. Чернов, В.М. Реализация теоретико-числовых преобразований в кодах, порождённых избыточными системами счисления / В.М. Чернов // Электронное моделирование. – 1992. – Т. 15(4). – С. 33-37.
  16. Chernov, V.M. fast algorithms of discrete orthogonal transforms realized in the number system with an irrational base / V.M. Chernov, D.V. Sobolev // Optical Memory & Neural Networks. – 2000. – Vol. 9(1). – P. 91-100.
  17. Chernov, V.M. Fibonacci-Mersenne and Fibonacci-Fermat discrete transforms / V.M. Chernov, M.V. Pershina // The golden section: Theory and applications. Boletim de Informatica. – 1999. – No. 9/10. – P. 25-31.
  18. Stakhov, A.P. The mathematics of harmony: From Euclid to contemporary mathematics and computer science / A.P. Stakhov. – Singapore: World Scientific, 2009.
  19. Feinberg, M. Fibonacci-Tribonacci / M. Feinberg // The Fibonacci Quarterly. – 1963. – Vol. 1(30). – P. 71-74.

 

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