Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
ANALYSIS OF FAST ALGORITHM OF MATRIX-VECTOR MULTIPLICATION FOR THE BANK OF DIGITAL FILTERS
Vitaly B. Kreyndelin, Moscow Technical University of Communications and Informatics, Moscow, Russia, vitkrend@gmail.com
Elena D. Grigorieva, Moscow Technical University of Communications and Informatics, Moscow, Russia, ed.grigorieva@yandex.ru
Abstract
Algorithms of implementation of vector-matrix multiplication are presented, which are intended for application in banks (sets) of digital filters. These algorithms provide significant savings in computational costs over traditional algorithms. At the same time, reduction of computational complexity of algorithms is achieved without any performance loss of banks (sets) of digital filters. As the basis for the construction of algorithms proposed in the article, the previously known Winograd method of multiplication of real matrices and vectors and two versions of the method of type 3M for multiplication of complex matrices and vectors are used. Methods of combining these known methods of multiplying matrices and vectors for building digital filter banks (sets) are considered. The analysis of computing complexity of such ways which showed a possibility of reduction of computing complexity in comparison with a traditional algorithm of realization of bank (set) of digital filters approximately in 2.66 times – at realization on the processor without hardware multiplier is carried out; and by 1.33 times – at realization on the processor with the hardware multiplier. These indicators are markedly higher than those of known algorithms. Analysis of sensitivity of algorithms proposed in this article to rounding errors arising by digital signal processing was carried out. Based on this analysis, an algorithm is selected that has a computational complexity smaller than that of a traditional algorithm, but its sensitivity to rounding errors is the same as that of a traditional algorithm. Recommendations are given on its practical application in the development of a bank (set) of digital filters.
Keywords: multirate signal processing, Bank (set) of digital filters, fast algorithm, sensitivity to calculation errors, 3M method, Winograd method.
References
1. Zaitsev A. A. (2003). Methods of Construction of Banks of Digital Filters: Thematic review. Digital signal processing. No. 1. P. 2-10. (in Russian)
2. Vityazev V.V. (2016). Filter banks in broadband data transmission systems. Digital signal processing. No. 2. P. 44-52. (in Russian)
3. Vityazev V.V., Harin A.V. (2017). Estimation of computational efficiency of methods of development of bank of filres-demodulators. Proceedings of II Russian scientific-technical conference ‘Actual problems of modern science and manufactoring’, 15-17 November, 2017, Razyan. P. 113-123. (in Russian)
4. Vityazev V.V. (2017). Multirate signal processing. Moscow: Goryachaya-linia – Telecom. 336 p. (in Russian)
5. Kreyndelin V.B., Smirnov A.E., Ben Rejeb T.B.K. (2016). Efficiency of signal processing methods in high-order MU-MIMO systems. T-Comm. Vol.10, No.12. P. 24-30. (in Russian)
6. Kreyndelin V.B., Reznev A.A. (2013). Quasi-optimal code properties in space-time coding communication systems. T-Comm. Vol.7. No.10. P. 59-60. (in Russian)
7. Kreyndelin V.B., Grigorieva E.D. (2019). The Implementation of the Bank of Digital Filters with Reduced Computational Complexity. T-Comm. Vol.13. No.7. P.4 8-53. (in Russian)
8. Higham N. (2002). Accuracy and Stability of Numerical Algorithms. Second edition. USA, Philadelphia, SIAM. 710 p.
9. Tyrtyshnikov E.E. (2007). Matrix analysis and linear algebra. Moscow: Fizmatgiz. 480 p. (in Russian)
10. Higham N. (1992). Stability of a Method for Multiplying Complex Matrices with Three Real Matrix Multiplications. SIAM J. Matrix Anal. Appl. Vol.13. No.3. P. 681-687, July 1992.
11. Blahut R. (1989). Fast Algorithms for Digital Signal Processing. Moscow: Mir Publ. 448 p. (in Russian)
12. Bakulin M.G., .Kreyndelin V.B, Pankratov D.Y. (2018). Technologies in radiocommunication systems on the road to 5G. Moscow: Goryachaya linia – Telecom. 280 p. (in Russian)
13. Ivanova V.G., Tyazhev A.I. (2017). Digital Signal Processing and Signal Processors: Tutorial. 2-nd ed. Samara: PGUTI. 252 p. (in Russian)
14. Kreyndelin, V.B., Smirnov A.E. (2016). Decreasing of computational complexity of demodulation algorithms in multi-antenna systems due to application of fast algorithms. Telecommunications and Radio Engineering. Vol. 75, issue: 19. P. 1757-1773.
15. Verzhbitsky V.M. (2002). Basis of numeric methods. Moscow: Vyshaya shkola. 840 p. (in Russian)
16. Seber G.A.F. (2008). Matrix Handbook for Statisticians. New Jersey, USA: John Wiley & Sons. 593 p.
17. Fackler P.L. (2005). Notes of Matrix Calculus. North Carolina State University, September 27, 2005. 14 p.
18. Kreyndelin V.B. and Grigorieva E.D. (2020). Analysis of Fast Algorithm of Matrix-Vector Multiplication for the Bank of Digital Filters. 2020 Systems of Signal Synchronization, Generating and Processing in Telecommunications (SYNCHROINFO), Svetlogorsk, Russia, 2020, pp. 1-5, doi: 10.1109/SYNCHROINFO49631.2020.9166081.
Information about authors:
Vitaly B. Kreyndelin, Moscow Technical University of Communications and Informatics, chief of the Department of electric circuit theory, Moscow, Russia
Elena D. Grigorieva, Moscow Technical University of Communications and Informatics, member of the Department of electric circuit theory, Moscow, Russia