Системы счисления в модулярных кольцах и их приложения к "безошибочным" вычислениям
Автор: Чернов Владимир Михайлович
Журнал: Компьютерная оптика @computer-optics
Рубрика: Численные методы и анализ данных
Статья в выпуске: 5 т.43, 2019 года.
Бесплатный доступ
В статье вводятся и исследуются новые системы параллельной машинной арифметики, связанной с представлением данных в избыточной системе счисления с базисом, формируемым последовательностями степеней корней характеристического полинома рекуррентности второго порядка. Такие системы счисления являются модулярными редукциями обобщений системы счисления Дж. Бергмана с основанием, равным «золотому сечению». Описывается ассоциированная система остаточных классов. В качестве приложения к задачам цифровой обработки сигналов в работе предлагается, в частности, новый «безошибочный» алгоритм вычисления дискретной циклической свёртки. Алгоритм основан на применении нового класса дискретных ортогональных преобразований, для которых существуют эффективные реализации, не использующие умножений.
Система счисления, модулярная арифметика, дискретная свертка, система остаточных классов
Короткий адрес: https://sciup.org/140246524
IDR: 140246524 | DOI: 10.18287/2412-6179-2019-43-5-901-911
Список литературы Системы счисления в модулярных кольцах и их приложения к "безошибочным" вычислениям
- Bergman, G. A number system with an irrational base / G. Bergman // Mathematics Magazine. - 1957. - Vol. 31, Issue 2. -P. 98-110.
- Rousseau, C. The Phi number system revisited. / G. Rousseau // Mathematics Magazine. - 1995. - Vol. 48, Issue 4. - P. 283284.
- Стахов, А.П. Коды золотой пропорции / А.П. Стахов // М.: Радио и связь, 1984. - 152 с.
- Katai, I. Canonical number systems for complex integers / I. Katai, J. Szabo // Acta Scientiarum Mathematicarum. - 1975. -Vol. 37. - P. 255-260.
- 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. 405414.
- Ananda Mohan, P.V. Residue number systems / P.V. Ananda Mohan. - Basel: Birkhauser, 2016. - 351 p. -
- ISBN: 978-3-31941383-9
- 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
- Chernov, V. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes / V. Chernov // Chaos, Soli-tons and Fractals. - 2006. - Vol. 29. - P. 372-380.
- Чернов, В.М. Квазипараллельный алгоритм для безошибочного вычисления свёртки в редуцированных кодах Мерсен-на-Люка / В.М. Чернов // Компьютерная онтика. - 2015. - Т. 39, № 2. - C. 241-248. -
- DOI: 10.18287/0134-2452-2015-39-2241-248
- Nussbaumer, H.J. Fast Fourier transform and convolution algorithms / H.J. Nussbaumer. - Berlin, Heidelberg: Springer-Verlag, 1981.
- Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов / Р. Блейхут; пер с англ. - М: Мир, 1989. - 448 с.
- Wimp, J. Computations with recurrence relations / J. Wimp // Boston, MA: Pitman, 1984.
- Masakova, Z. Arithmetics in number systems with a negative base / Z. Masakova, E. Pelantova, T. Vavra // Theoretical Computer Science. - 2011. - Vol. 412, Issues 8-10. - P. 835-845.
- Schonhage, A. Schnelle Multiplikation groBer Zahlen / A. Schonhage, V. Strassen // Computing. - 1971. - Vol. 7. - P. 281-292.
- Чернов, В.М. Реализация теоретико-числовых преобразований в кодах, порождённых избыточными системами счисления / В.М. Чернов // Электронное моделирование. - 1992. - Т. 15(4). - С. 33-37.
- 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.
- 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.
- Stakhov, A.P. The mathematics of harmony: From Euclid to contemporary mathematics and computer science / A.P. Stakhov. -Singapore: World Scientific, 2009.
- Feinberg, M. Fibonacci-Tribonacci / M. Feinberg // The Fibonacci Quarterly. - 1963. - Vol. 1(30). - P. 71-74.
