Извините, этот техт доступен только в “Американский Английский”. 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.
THE IMPLEMENTATION OF THE BANK OF DIGITAL FILTERS
WITH REDUCED COMPUTATIONAL COMPLEXITY
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
Ultra-large integrated circuits, called chips, can contain more than 100 thousand logic elements, and therefore the theory of algorithms is considered as a way to effectively organize these elements. Sometimes the choice of algorithm can significantly improve the performance of the chip, without having to increase the size of the chip or to improve its performance. For example, if it is possible to propose an algorithm for calculating some function of digital signal processing, containing only a fifth of the number of operations included in the traditional algorithm for calculating the same function, then using this algorithm, you can implement the same improvement in the characteristics of the chip, which is obtained by increasing five times its size or its speed. However, the developer of the chip should move the algorithm architecture the architecture of the chip, to implement the improvement. An ill-conceived design can negate this advantage by increasing, for example, the complexity of indexing or the input-output flow. The development of optimal designs in the era of large integrated circuits is impossible without the use of fast algorithms. At first glance it may seem that these two directions – fast integrated circuits and fast algorithms – compete with each other. If you can build large enough and fast enough chips, it seems that there is nothing wrong with the fact that inefficient algorithms are used. In some cases, this point of view is not in doubt, but there are certainly cases in which it is possible to express a diametrically opposite point of view. Large digital processors themselves often create the need to develop fast algorithms, as the dimension of the problems solved on them is growing. Whether the processor time of an algorithm designed to solve some problem is proportional to or is irrelevant at n equal to 3 or 4, but at n equal to 1000, it becomes critical. Digital signal processing algorithms use the multiplication of matrices containing complex numbers. When multiplying two matrices of complex numbers in the traditional way, it is required to perform four multiplications and two additions of matrices of real numbers. Using a simple identical transformation of a mathematical expression, it is possible to implement the operation of multiplication of two matrices of complex numbers by three operations of multiplication of matrices of real numbers and five additions of matrices of real numbers. This method reduces the number of arithmetic operations by about 12.5 — 25% vs. traditional method.
Keywords: multirate signal processing, Bank of digital filters, fast algorithm, stability of the algorithm (sensitivity to calculation errors), method 3Ì (method of 3 multiplications), processor performance.
References
1. 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)
2. Vityazev V.V. (1993). Digital frequency selection of signals. Moscow: Radio and communication. 240 p. (in Russian)
3. Solonina A.I., Ulakhovich D.A., Arbuzov S.M. (2003). Fundamentals of digital signal processing: a Course of lectures. St.-Pb.: BHV-Petersburg Publ. 608 p. (in Russian)
4. Azarenkov L.G., Kanatov I.I., Kaplun D.I. (2007). Bank of digital filters. Components and technologies. No. 10, pp. 156-161. (in Russian)
5. Zaitsev A.A. (2003). Methods of Construction of Banks of Digital Filters: Thematic review. Digital signal processing. No. 1, pp. 2-10. (in Russian)
6. Vityazev V.V., Zaitsev A.A. (2005). Basics of multi-rate signal processing. Textbook, Part 1. Ryazan state radio engineering Academy. Ryazan. 124 p. (in Russian)
7. Vityazev V.V., Vityazev S.V. (2007). Methods of synthesis of narrow-band adaptive FIR filter based on multi-speed processing. Digital signal processing. No. 4, pp. 13-16. (in Russian)
8. Gusinskaya E.I., Zaitsev A.A. (2001). Filter Bank Optimization in Subband Coding Problems. Digital signal processing., No. 2, pp. 2-9. (in Russian)
9. 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)
10. Tyrtyshnikov E.E. (2007). Matrix analysis and linear algebra. Moscow: Fizmatgiz. 480 p. (in Russian)
11. Blahut R. (1989). Fast Algorithms for Digital Signal Processing. Moscow: Mir Publ., p. 448. (in Russian)
12. Higham N. (2002). Accuracy and Stability of Numerical Algorithms. Second edition. USA, Philadelphia, SIAM. 710 p.
13. 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, pp.681-687, July 1992.
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