Authors V.M. Amerbaev, R.A. Solovyev, D.V. Telpukhov, P.S. Poperechny, V.S. Rukhlov, A.N. Sсhelokov, A.S. Mihmel
Month, Year 06, 2015 @en
Index UDC 004.3'1
Abstract One of the key operations in digital signal processing (DSP) is the dot product operation used in the construction of convolutions and FIR filters. In the positional representation, this operation has been well studied and many effective implementations of microelectronic devices have been developed. However, for large dimensions of vector elements performance of positional devices significantly decreases. In this paper we propose to use residue number system (RNS) to perform this operation. RNS has internal parallelism that helps to avoid significant delay growth when dimensions of vector elements increase. As opposed to traditional parallelization for residue channels of RNS, we use another level of parallelism, the so-called complex numbers intramodular parallelism based on the Gauss"s theorem on isomorphism. The paper describes the method of implementing of dot product calculation for vectors of complex integers using RNS arithmetic over a Galois field. We present an approach related to the use of modular decomposition in intramodular channels for complex numbers based on the Gauss"s theorem on isomorphism. A device calculating dot product by the proposed method was implemented. Detailed description of the device is presented, as well as the results of its comparison to similar devices built in binary basis using modern ASIC and FPGA CADs.

Download PDF

Keywords Complex integer; residue number system; dot product (scalar product); finite field; convolution.
References 1. Abdelgawad A., Bayoumi M. High Speed and Area-Efficient Multiply Accumulate (MAC) Unit for Digital Signal Processing Applications, IEEE International Symposium on Circuits and Systems, 2007, pp. 3199-3202.
2. Preethy A.P. and Radhakrishnan D. A 36-bit Balanced Moduli MAC Architecture, 42nd Midwest Symp. on Circuits and Systems (MWSCAS99), Las Cruces, NM., Aug. 1999, Vol. 1, pp. 380-383.
3. Amerbaev V.M., Solov'ev R.A., Tel'pukhov D.V., Shchelokov A.N. Issledovanie effektivnosti modulyarnykh vychislitel'nykh struktur pri proektirovanii apparatnykh odnotaktnykh umnozhiteley [A survey on efficiency of modular computing structures for single-cycle hard-ware multiplier design], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 248-254.
4. Amerbaev V.M., Stempkovskiy A.L., Solov'ev R.A. Parallel'nye vychisleniya v kol'tse gaussovykh chisel nad polem Galua GF(P) [Parallel computations in the ring of Gaussian integers over Galois field GF(P)], Vserossiyskaya nauchno-tekhnicheskaya konfe-rentsiya "Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES)". Sbornik trudov [All-Russian scientific-technical conference "problems of development of perspective
micro- and nanoelectronic systems (MES)". Proceedings of], 2012, No. 1, pp. 517-520.
5. Dugdale M. VLSI implementation of residue adders based on binary adders, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. 1992.
6. Amerbaev V.M., Solovyev R.A., Telpukhov D.V. Hardware Implementation of Fir Filter based on Number-Theoretic Fast Fourier Transform in Residue Number System, Open Sciences Journal, 2014, pp. 1-6.
7. Amerbaev V.M., Tel'pukhov D.V., Konstantinov A.V. Bivalentnyy defekt modulyarnykh kodov. Vybor tekhnologicheskikh moduley, ponizhayushchikh bivalentnyy defekt [Bivalent defect modular codes. The choice of process modules, lowering bivalent defect], Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES) [Problems of development of perspec-
tive micro- and nanoelectronic systems (MES)], 2008, pp. 462.
8. Amerbaev V.M., Solov'ev R.A., Tel'pukhov D.V. Realizatsiya biblioteki modul'nykh arifmeticheskikh operatsiy na osnove algoritmov minimizatsii logicheskikh funktsiy [Library implementation of modular arithmetic operations, based on logic functions minimization algorithms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 221-225.
9. Amerbaev V.M., Solov'ev R.A., Tel'pukhov D.V. Metod vychisleniya tsiklicheskoy svertki na baze BPF s ispol'zovaniem chisel Prota [Method for computing the cyclic convolution based on FFT using Proth numbers], Informatsionnye tekhnologii [Information technologies], 2014, No. 10, pp. 22-27.
10. Solov'ev R.A., Tel'pukhov D.V. Apparatnaya realizatsiya operatsii nakhozhdeniya ostatka tselochislennogo deleniya dlya vkhodnykh dannykh bol'shoy razryadnosti v modulyarnoy arifmetike [Hardware implementation of the operation of finding the remainder of integer division to input data high-capacity in modular arithmetic], Izvestiya vysshikh uchebnykh zavedeniy. Elektronika [Izvestiya of Higher Educational Institutions. Electronics], 2013, No. 4, pp. 75-83.
11. Solov'ev R.A., Tel'pukhov D. V., Amerbaev V.M., Balaka E.S. Postroenie obratnykh preobrazovateley modulyarnoy arifmetiki s korrektsiey oshibok na baze poliadicheskogo koda [Build inverters modular arithmetic error correction on the basis politicheskogo code], Neyrokomp'yutery: razrabotka, primenenie [Neurocomputers: Development, Application], 2014, No. 9, pp. 30-35.
12. Amerbaev V.M., Pak I.T. Parallel'nye vychisleniya v kompleksnoy ploskosti [Parallel computations in the complex plane]. Alma-Ata.: Izd-vo «Nauka», 1984, 183 p.
13. Vinogradov I.M. Osnovy teorii chisel [Fundamentals of the theory of numbers]. Moscow-Leningrad: Gostekhizdat, 1952, 180 p.
14. Omondi A. and Premkumar B. Residue Number System: Theory and Implementation, Imperial College Press. 2007. ISBN 978-1-86094-866-4.
15. Solov'ev R.A. Generator Verilog dlya indeksnykh umnozhiteley po modulyu [Generator Verilog for index modulo multipliers]: vscripts. 2012. Available at: (accessed 16 February 2015).
16. Piestrak S.J. Design of residue generators and multioperand modular adders using carry-save adders, IEEE Trans. Comput., 1994, Vol. 423, No. 1, pp. 68-77.
17. Balaka E.S., Tel'pukhov D.V. Printsipy postroeniya spetsializirovannogo vychislitelya dlya zadach matrichnoy algebry s primeneniem parallel'noy arifmetiki [Principles of construction of a specialized computer tasks for matrix algebra with application of parallel arithmetic], Neyrokomp'yutery: razrabotka, primenenie [Neurocomputers: Development, Application],
2010, No. 9, pp. 46-49.
18. Amerbaev V.M., Tel'pukhov D.V. Obratnyy preobrazovatel' modulyarnoy arifmetiki s ispol'zovaniem netochnogo ranga dlya zadach TsOS [Return Converter modular arithmetic using inaccurate rank for DSP tasks], Izvestiya vysshikh uchebnykh zavedeniy. Elektronika [Izvestiya of Higher Educational Institutions. Electronics], 2013, No. 1 (99), pp. 41-46.
19. Amerbaev V.M., Balaka E.S., Konstantinov A.V., Tel'pukhov D.V. Metody postroeniya pryamykh preobrazovateley modulyarnoy logarifmetiki, orientirovannykh na TsOS [Methods of construction of direct converters of modular logarithmica-oriented DSP], Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES) [Problems of development of perspective micro - and nanoelectronic systems (MES)], 2010, pp. 374.
20. Poperechnyy P.S. Matlab Residue Library: vscripts. 2014. Available at: (accessed 16 February 2015).

Comments are closed.