|
Article information
2014 , Volume 19, ¹ 4, p.99-106
Solovyev R.A., Telpukhov D.V.
Methodology for basic selection in recursive residue number system
Recently, a new method for the representation of numbers in residue number system (RNS), called recursive residue number system (RRNS) was proposed. In this method, it becomes possible to represent large numbers using sets of modules with very small modules using the recursive decomposition. RRNS preserves all the advantages of traditional RNS related to parallel independent computations for each module. The method can increase the speed of computation by reducing complexity of arithmetic operations for each modular channel. But then RRNS increases the number of channels and imposes significant restrictions when choosing sets of modules. First-of-a-kind research on the choice of optimal sets of modules in RRNS is proposed in this paper. An algorithm for selecting a RRNS basis for the two given values: the required dynamic range (DR) and the maximum bit length of basic modules (MBLBM) (i. e. modules, which will be used for arithmetic operations in modular channels) are proposed in this paper. It is shown under which combinations of DR and MBLBM RRNS the proposed method has the advantage over traditional RNS. The graphs of data redundancy in RRNS and examples of RRNS for construction of sets of modules are presented. According to the results shown in the article it is appropriate to use MBLBM from 3 to 7 bits for typical tasks. Moreover, if DR is less than 64 bits, the most effective MRBM is from 3 up to 5 bits depending on the possible redundancy in the RRNS representation. Received 29 May 2014.
[full text]
Keywords: Modular arithmetic, residue number system, finite field, Chinese remainder theorem, remainder
Author(s):
Solovyev Roman Alexandrovich
PhD.
Position: Head of Departament
Office: Institute for Design Problems in Microelectronics of Russian Academy of Sciences
Address: 124365, Russia, Moscow, 3, Sovetskaya Street
Phone Office: (499) 729-98-90
E-mail: turbo@ippm.ru
Telpukhov Dmitriy Vladimirovich
PhD.
Position: Research Scientist
Office: Institute for Design Problems in Microelectronics of Russian Academy of Sciences
Address: 124365, Russia, Moscow, 3, Sovetskaya Street
Phone Office: (499) 729-98-90
E-mail: dmtr@ippm.ru
References:
[1] Leng S. Algebra. Moscow: Mir; 1968. (In Russ.)
[2] Uspensky J.V., Heaslet M.A. Elementary Number Theory. New York: McGraw-Hill; 1939.
[3] Jerdnieva N.S. Ispol’zovanie sistemy ostatochnyh klassov dlja malomoshhnyh prilozhenij cifrovoj obrabotki signalov [Application of residue number system for low power digital signal processing]. Inzhenernyj vestnik Dona. 2013; 2. (In Russ.)
[4] Solov’jov A.N., Alekseev V.E. Bezgiroskopnaja inercial’naja sistema na osnove akselerometrov[Gyro-free inertial navigation system]. Nano- i mikrosistemnaja tehnika. 2012; 4(141): 26-31. (In Russ.)
[5] Amerbaev V.M., Stempkovskij A.L., Solov’jov R.A. Principy rekursivnyh moduljarnyh vychislenij [Principles of Recursive Modular Arithmetic]. Inform. tehnologii. 2013; 2: 22-27. (In Russ.)
[6] Abramowitz M., Stegun I.A. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th Printing. New York: Dover; 1972.
[7] Inyutin S.A. Moduljarnye vychislenija v sverhbol’shih komp’juternyh diapazonah [Modular calculations in very large scale ranges ].Izv. vuzov. Jelektronika. 2001; 6: 81-87. (In Russ.)
[8] Inyutin S.A. Vychislitel’nye zadachi bol’shoj algoritmicheskoj slozhnosti i moduljarnaja arifmetika [Computational problems with large algorithmic complexity and modular arithmetic ]. Vestnik Tjumenskogo gos. un-ta. 2002; 3: 14-23. (In Russ.)
[9] IPPM RAN. Generator rekursivnyh bazisov [Jelektronnyj resurs]. http://vscripts.ru/2014/recursieve_rns_basis_generator.php
Bibliography link:
Solovyev R.A., Telpukhov D.V. Methodology for basic selection in recursive residue number system // Computational technologies. 2014. V. 19. ¹ 4. P. 99-106
|
