Synthesis of fast-operating devices for digital signal processing based on the number-theoretic transforms
DOI:
https://doi.org/10.15587/1729-4061.2020.194342Keywords:
autocorrelation function, correlation, convolution, programmable logical integrated circuits, discrete Fourier transformAbstract
The selection of special-form moduli and their corresponding primitive roots have been proposed, which provide for a simplified structure of arithmetic devices using number-theoretic transforms. A method for determining moduli has been developed that ensures a minimum number of arithmetic operations when performing the modulo addition and multiplication operations. The structures of special-form modulo adders have been developed and modeled, which make it possible to perform the addition operation as quickly as possible. The modulo adders for the Fermat, Mersenne, and Golomb numbers have been synthesized and tested, which could be used in the arithmetic units of high-speed correlators and filters.
Real-time correlation and convolution calculation become a rather time-consuming task in the case of long input sequences. To solve this task, it is advisable to apply the so-called fast algorithms. However, this requires the high-performance calculators of convolution and correlation, which often exceed the capabilities of modern computer equipment, Therefore, the proposed procedure for determining the modulus, as well as the designed structural circuits for special-form modulo adders, make it possible to accelerate the computation of correlations and convolutions using number-theoretic transforms.
Since the operation of modulo multiplication is performed using the addition and shift operations, the complexity of calculating the number-theoretic transformations largely depends on the number of unities in the binary representation of the degrees of the primitive root. The operation of multiplication is typically reduced to the multiple addition of numbers, which is why the complexity and speed performance of arithmetic devices for numeric-theoretic transformations is determined by the characteristics of the modulo adders.
The proposed method for designing computing moduli for the digital devices that calculate correlation and convolution, based on rapid theoretical-numerical transformations, provides the simplified hardware and software implementation of these structures, resulting in high-speed processing of signals and imagesReferences
- Ortega Cisneros, S., Rivera D., J., Moreno Villalobos, P., Torres, C., C. A., Hernandez-Hector, H., Raygoza, P., J. J. (2015). An image processor for convolution and correlation of binary images implemented in FPGA. 2015 12th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE). doi: https://doi.org/10.1109/iceee.2015.7357987
- Ito, I. (2013). A Computing Method for Linear Convolution and Linear Correlation in the DCT Domain. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E96.A (7), 1518–1525. doi: https://doi.org/10.1587/transfun.e96.a.1518
- Valencia, F., Khalid, A., O’Sullivan, E., Regazzoni, F. (2017). The design space of the number theoretic transform: A survey. 2017 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS). doi: https://doi.org/10.1109/samos.2017.8344640
- Zhang, J., Li, S. (2009). Data-recovery algorithm and circuit for cyclic convolution based on FNT. IEICE Electronics Express, 6 (14), 1019–1024. doi: https://doi.org/10.1587/elex.6.1019
- Boussakta, S., Hamood, M. T., Rutter, N. (2012). Generalized New Mersenne Number Transforms. IEEE Transactions on Signal Processing, 60 (5), 2640–2647. doi: https://doi.org/10.1109/tsp.2012.2186131
- Campbell, K., Lin, C.-H., Chen, D. (2018). Low-cost hardware architectures for mersenne modulo functional units. 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC). doi: https://doi.org/10.1109/aspdac.2018.8297388
- Toivonen, T., Heikkila, J. (2006). Video filtering with Fermat number theoretic transforms using residue number system. IEEE Transactions on Circuits and Systems for Video Technology, 16 (1), 92–101. doi: https://doi.org/10.1109/tcsvt.2005.858612
- Zhang, J., Li, S. (2009). High Speed Parallel Architecture for Cyclic Convolution Based on FNT. 2009 IEEE Computer Society Annual Symposium on VLSI. doi: https://doi.org/10.1109/isvlsi.2009.10
- Kumar, S., Chang, C.-H. (2017). A Scaling-Assisted Signed Integer Comparator for the Balanced Five-Moduli Set RNS {2n - 1, 2n, 2n + 1, 2n+1 - 1, 2n-1 - 1}. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25 (12), 3521–3533. doi: https://doi.org/10.1109/tvlsi.2017.2748984
- Efstathiou, C., Vergos, H. T., Nikolos, D. (2003). Modulo 2n ±1 adder design using select-prefix blocks. IEEE Transactions on Computers, 52 (11), 1399–1406. doi: https://doi.org/10.1109/tc.2003.1244938
- Golomb, S. W., Reed, I. S., Truong, T. K. (1977). Integer Convolution over Finite Field GF(3‧2n + 1). SIAM Journal on Applied Mathematics, 32 (2), 356–365. doi: https://doi.org/10.1137/0132029
- Chernov, V. M., Korepanov, A. O. (2006). Teoretiko-chislovye preobrazovaniya v zadachah tsifrovoy obrabotki signalov. Samara, 112.
- Baozhou, Z., Ahmed, N., Peltenburg, J., Bertels, K., Al-Ars, Z. (2019). Diminished-1 Fermat Number Transform for Integer Convolutional Neural Networks. 2019 IEEE 4th International Conference on Big Data Analytics (ICBDA). doi: https://doi.org/10.1109/icbda.2019.8713250
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Andrey Ivashko, Igor Liberg, Denis Lunin
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
