(44-2) 18 * << * >> * Russian * English * Content * All Issues

Parallel machine arithmetic for recurrent number systems in non-quadratic fields
V.M. Chernov 1,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, 852 kB

DOI: 10.18287/2412-6179-CO-666

Pages: 274-281.

Full text of article: Russian language.

Abstract:
The paper proposes a new method of synthesis of computer arithmetic systems for "error-free" parallel calculations. The difference between the proposed approach and calculations in traditional systems of Residue Number Systems for the direct sum of modular rings is the parallelization of calculations in non-quadratic extensions of simple finite fields whose elements are represented in number systems generated by sequences of powers of roots of the characteristic polynomial of the recurrent sequence.

Keywords:
finite fields, recurrent number system, parallel machine arithmetic.

Citation:
Chernov VM. Parallel machine arithmetic for recurrent number systems in non-quadratic fields. Computer Optics 2020; 44(2): 274-281. DOI: 10.18287/2412-6179-CO-666.

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 ("Number systems") and by the Russian Foundation for Basic Research under grants 19-07-00357 А and 18-29-03135_ мк ("Machine arithmetic").

References:
  1. Ananda Mohan PV. Residue number systems. Basel: Birkhäuser; 2016. ISBN: 978-3-319-41383-9.
  2. Molahosseini AS, de Sousa LS, Chang Ch-H, eds. Embedded systems design with special arithmetic and number systems. Cham: Springer; 2017. ISBN: 978-3-319-49741-9.
  3. Varichenko LV, Labunets VG, Rakov MA. Abstract algebraic systems and digital signal processing [In Russian]. Kyiv: “Naukova Dumka” Publisher; 1986.
  4. Nussbaumer HJ. Fast Fourier transform and convolution algorithms. Berlin, Heidelberg: Springer Verlag; 1982.
  5. Golomb SW. Properties of the sequence 3∙2n+1. Math Comput 1976; 30(135): 657-663.
  6. Alfredson L-I. VLSI Architectures and arithmetic operations with application to the Fermat number transform. Linkӧping: Linkӧping University Publisher; 1996.
  7. Chernov V. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes. Chaos, Solitons and Fractals 2006; 29: 372-380. DOI: 10.1016/j.chaos.2005.08.081.
  8. 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.
  9. 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.
  10. Chernov VM. Arithmetic methods for fast algorithms of discrete orthogonal transforms synthesis [in Russian]. Мoscow: “Fizmatlit” Publisher, 2007. ISBN: 978-5-9221-0940-6.
  11. Chernov VM. Fibonacci, tribonacci, ..., hexanacci and parallel “error-free” machine arithmetic. Computer Optics 2019; 43(6): 1072-1078. DOI: 10.18287/2412-6179-2019-43-6-1072-1078.
  12. Gel’fond AO. Calculus of finite differences [In Russian]. 4th ed. Мoscow: “URSS” Publisher, 2006.
  13. Wimp J. Computations with recurrence relations. Boston, MA: Pitman; 1984.
  14. Shparlinski E. On some problems in the theory of finite fields. Russian Math Surveys 1991; 46(1:277): 199-240.
  15. Brown JL. Note on complete sequences of integers. The American Mathematical Monthly 1961; 68(6): 557-560. DOI: 10.2307/2311150.
  16. Gregory RT, Krishnamurty EV. Method and applications of error-free computation. New York: Springer-Verlag; 1984.
  17. Davenport JH, Siret Y, Tournier E. Computer algebra: Systems and algorithms for algebraic computation. London: Academic Press; 1988.
  18. Von Zur Gathen J, Panario D. Factoring polynomials over finite fields: A survey. J Symb Comput 2001; 31(1-2): 3-17.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ko@smr.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20