Szybki algorytm splotu kołowego dla N = 2^m

• Autorzy: Gliszczyński M. , Tariov A.

Warianty tytułu

EN

Fast circular convolution algorithm for N = 2^m

• Języki publikacji: PL

Abstrakty

PL

W pracy został przedstawiony szybki algorytm liczenia splotu kołowego N-elementowych wektorów danych ze zredukowaną liczbą operacji arytmetycznych (lub układów mnożących i sumatorów, jeśli chodzi o implementację sprzętową) w przypadku, gdy N=2^m, m - liczba całkowita. Pozwala to przy implementacji zmniejszyć nakłady obliczeniowe lub zapotrzebowanie na zasoby sprzętowe oraz stworzyć dogodne warunki do efektywnej realizacji operacji splotu kołowego w dowolnym sprzętowo-programowym środowisku implementacyjnym.

EN

In the work the fast algorithm for 2n-point circular convolution calculating with the reduced number of arithmetic operations (or multipliers and adders - in hardware implementation case) is presented. Computational procedure for describing the algorithm, based on the successful decomposition of the circulant matrix of arbitrary order is shown. This approach allows to lower hardware expenses and to create favorable conditions for effective convolution realization in the reprogrammable platform. Computational procedure for circular convolution realization can be described by means of matrix algebra notation. Matrix algebra offers not only a formalism for describing the algorithm, but it enables the derivation by pure algebraic manipulations of an algorithm that is well suited to be implemented in vector and matrix digital signal processors with various levels of parallelism. In addition, the mentioned procedures can be directly used for easy implementation in matrix-oriented languages like Matlab.

Słowa kluczowe

PL

szybkie algorytmy; splot kołowy; notacja macierzowa

EN

fast algorithms; circular convolution; matrix notation

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 8
• Strony: 566--568
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wzory

Twórcy

autor

Gliszczyński M.

autor

Tariov A.

• Widział Informatyki, Zachodniopomorski Uniwersytet Technologiczny,

Bibliografia

• [1] T. P. Zieliński, Cyfrowe przetwarzanie sygnałów: od teorii do zastosowań, WKŁ, Warszawa 2007.
• [2] E. E. Dagman., G. A. Kukharev. Szybkie dyskretne transformaty ortogonalne, Wydawnictwo Nauka, 1983.
• [3] A. Ţariov, Modele algorytmiczne i struktury wysokowydajnych procesorów cyfrowej obróbki sygnałów, Szczecin, Informa, 2001.
• [4] R. E. Blahut, Fast algorithms for digital signal processing, Addison-Wesley Publishing company, Inc. 1985.
• [5] R. C. Agarwal, J. W. Cooley, New algorithms for digital convolution. IEEE Transactions on Acoustics, speech, and Signal processing, vol ASSP-vol. AS25 (no 5), pp. 392-410, October 1977.
• [6] H. J. Nussbaumer., Fast Fourier Transform and Convolution Algorithms, Springer-Verlag, 1982.
• [7] C. S. Burrus, T. W. Parks, J. F. Potts, DFT/FFT and Convolution Algorithms and Implementation, John Willey & Sons, 1985.
• [8] R. Tolimieri M. An, C. Lu, Algotithms for Discrete Fourier Transform and Convolution, Springer-Verlag, 1989.
• [9] I. S. Reed, T. K. Truong, The Use of Finite Fields to Compute Convolutions, IEEE Trans. on Information Theory: IT-21, March 1975, pp. 208-213.
• [10] J. H. McClellan, C. M. Rader, Number Theory in Digital Signal Processing, Prentice-Hall, Inc. Englewood Cliffs, New Jersey, 1979.
• [11] W. Selesnik, C. S. Burrus, Extending Winograd’s Small Convolution Algorithm to Longer Lengths, In Proceedings of the IEEE International Symposium on Circuits and Systems, June 1994, pp. 2.449-2.452.
• [12] R. Stasiński, Extending sizes of effective convolution algorithms, Electronic letters, 1990, vol. 26, no 19, pp. 1602-1604.
• [13] A. Tariov, Strategie racjonalizacji obliczeń przy wyznaczaniu iloczynów macierzowo-wektorowych. Metody Informatyki stosowanej, Nr 1, 2008, str. 147-158.