(43-5) 22 * << * >> * Russian * English * Content * All Issues

Number systems in modular rings and their applications to "error-free" computations

V.M. Chernov1,2

1 IPSI RAS – Branch of the FSRC “Crystallography and Photonics” RAS,  
Molodogvardeyskaya 151, 443001, Samara, Russia,  
2 Samara National Research University, Moskovskoye shosse 34, 443086, Samara, Russia

 PDF, 843 kB

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

Pages: 901-911.

Full text of article: Russian language.

Abstract:
The article introduces and explores new systems of parallel machine arithmetic associated with the representation of data in the redundant number system with the basis, the formative sequences of degrees of roots of the characteristic polynomial of the second order recurrence. Such number systems are modular reductions of generalizations of Bergman's number system with the base equal to the "Golden ratio". The associated Residue Number Systems is described. In particular, a new "error-free" algorithm for calculating discrete cyclic convolution is proposed as an application to the problems of digital signal processing. The algorithm is based on the application of a new class of discrete orthogonal transformations, for which there are effective “multipication-free” implementations.

Keywords:
number system, modular  arithmetic, discrete convolution, residue number systems.

Citation:
Chernov VM. Number systems in modular rings and their applications to "error-free" computations. Computer Optics 2019; 43(5): 901-911. DOI: 10.18287/2412-6179-2019-43-5-901-911.

Acknowledgements:
The work was partly funded by the Russian Federation Ministry of Science and Higher Education within a state contract with the “Crystallography and Photonics” Research Center of the RAS under agreement 007-ГЗ/Ч3363/26 in part of “number systems” and  by Russian Foundation for Basic Research (Grants 19-07-00357 А and 18-29-03135_ мк)  in part of “machine arithmetic”.

References:
  1. Bergman G. A number system with an irrational base. Mathematics Magazine 1957; 31(2): 98-110.
  2. Rousseau C. The Phi number system revisited. Mathematics Magazine 1995; 48(4): 283-284.
  3. Stakhov AP. Goden ratio codes [In Russian]. Moscow: “Radio i Svyas” Publisher; 1984.
  4. Katai I, Szabo J. Canonical number systems for complex integers. Acta Sci Math 1975; 37: 255-260.
  5. Thuswaldner J. Elementary properties of canonical number systems in quadratic fields. In Book: Bergum GE, ed. Application of Fibonacci numbers. Vol 7. Dordrecht, Boston, London: Kluwer Acad Publ, 1996: 405-414.
  6. Ananda Mohan, P.V. Residue number systems, Basel: Birkhäuser; 2016. ISBN: 978-3-319-41383-9.
  7. Molahosseini AS, de Sousa LS, Chang C-H, eds. Embedded systems design with special arithmetic and number systems, Springer International Publishing AG; 2017. ISBN: 978-3-319-49741-9
  8. Chernov V. Fast algorithm for “error-free” convolution computation using Mersenne-Lucas codes. Chaos, Solitons and Fractals 2006; 29: 372-380.
  9. Chernov VM. Quasiparallel algorithm for error-free convolution computation using reduced Mersenne-Lucas codes. Computer Optics 2015; 39(2): 241-248. DOI: 10.18287/0134-2452-2015-39-2-241-248.
  10. Nussbaumer HJ. Fast Fourier transform and convolution algorithms. Berlin, Heidelberg: Springer-Verlag; 1981.
  11. Blahut RE. Fast algorithms for digital signal processing. Addison-Wesley Publishing Company Inc; 1985.
  12. Wimp J. Computations with recurrence relations. Boston, MA: Pitman; 1984.
  13. Masáková Z, Pelantová E, Vávra T. Arithmetics in number systems with a negative base. Theoretical Computer Science 2011; 412(8-10): 835-845.
  14. Schönhage A, Strassen V. Schnelle Multiplikation großer Zahlen. Computing 1971; 7: 281-292.
  15. Chernov VM. The implementation of number-theoretic transforms in the codes generated by the redundant number systems [In Russian]. Electronic Simulation 1992; 15(4): 33-37.
  16. Chernov VM, Sobolev DV. Fast algorithms of discrete orthogonal transforms realized in the number system with an irrational base. Optical Memory & Neural Networks 2000; 9(1): 91-100.
  17. Chernov VM, Pershina MV. Fibonacci-Mersenne and Fibonacci-Fermat discrete transforms. The Golden Section: Theory and applications. Boletim de Informatica 1999; 9/10: 25-31.
  18. Stakhov AP. The mathematics of harmony: From Euclid to contemporary mathematics and computer science. Singapore: World Scientific; 2009.
  19. Feinberg M. Fibonacci-Tribonacci. The Fibonacci Quarterly 1963; 1(30): 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