Algorytm splotu liniowego ze zredukowaną liczbą operacji mnożenia

• Autorzy: Mąka T. , Tariov A.
• Języki publikacji: PL

Abstrakty

PL

W pracy zaprezentowano uogólnioną metodę wyznaczania splotu liniowego z wykorzystaniem propozycji zawartej w pracy Blahut-a [2]. Metoda to opiera się na zastosowaniu zamiany sumy iloczynów występujących w równaniach splotu (przy założeniu, że rozmiar obydwóch sygnałów jest taki sam) na iloczyny sum. Dzięki takiemu podejściu istnieje możliwość zmniejszenia czasochłonnych operacji mnożenia, kosztem zwiększenia operacji dodawania. Proponowana w pracy metoda umożliwia syntezę algorytmu dla długości sygnałów spełniających warunek N >= 3 oraz realizację operacji splotu w środowisku wykonującym obliczenia równoległe z wykorzystaniem wektoryzacji obliczeń. Na podstawie propozycji i rozważań zawartych w pracy, autorzy opracowali programowy system generacji równań splotu liniowego, który oparto o przedstawioną metodę.

EN

In the paper an algorithm for linear convolution is presented. The algorithm assume that both convolved signals have the same length. The method used to synthesis the algorithm is based on conversion from sum products to product sums. This way the number of multiplication operations (more time consume operation than addition) is dimnished. The reduction of multiplication operations is done by expense of increasing addition operations. Direct realization of linear convolution operation needs N2 multiplication and (N-1)2- addition operations. Exponentially increasing number of multiplications was a reason to search for more effective algorithms. There are many algorithms aim to minimalize these operations [2, 3]. When time of multiplication is greater than time of addition (this situation exists in most cases) the gain can be obtained theoretically. The efficiency won't rely on number of arithmetic operations but complexity of computation control process [4] and data dependencies. Overall time of computations is dependent on implementation type (software or hardware). Therefore dimnishing operations like multiplications shouldn't be more important than clever improvements of data transfer control complexity. From hardware expenditures point of view algorithms with reduced number of operations should be synthesised. Presented generalized method (for any N fulfil the condition N>= 3) is based on suggestion by Blahut [2]. Obtained algorithm bas some more multiplications than a class of "fast" algorithms, but it characterized by simplier data transfers, so it is a certain compromise. For example, when N = 3 proposed algorithm gives reduction from 9 to 6 multiplications in expense of increasing additions form 4 to 13 in comparision with direct realization of convolution. As the result there is 33% gain of multiplications and 325% increasing of additions. When N is rising then gain of multiplications is also rising to the level about 50% and additions increase and stay at level about 250%. Presented algorithm was designed to be used in parallel processing and it can be adopted to hardware implementations using vectorization and bit-serial processing. The fact, that one of signals involved in convolution is often defined as constant, is the reason to use multipliers by set of constants. This can bring the further hardware reduction up. That way a hardware implementation can give more efficiency in the final analysis. Using presented approach, Authors have developed a software tool to generate convolution equations. In future works the system will be used to develop a complete system of automated mapping convolution algorithms into hardware using reprogrammable devices.

Słowa kluczowe

PL

splot liniowy; redukcja operacji arytmetycznych; cyfrowe przetwarzanie sygnałów; wektoryzacja obliczeń

EN

linear convolution; arithmetic reduction; digital signal processing; vectorization calculation

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2004
• Tom: R. 4, nr 7
• Strony: 59--67
• Opis fizyczny: Bibliogr. 9 poz., rys., tab.

Twórcy

autor

Mąka T.

• IAKiT Zakład Telekomunikacji, Politechnika Szczecińska ul. Żołnierska 49, 71-210 Szczecin

autor

Tariov A.

• IAKiT Zakład Telekomunikacji, Politechnika Szczecińska ul. Żołnierska 49, 71-210 Szczecin

Bibliografia

• [1] Agarwal R.C., Cooley J.W., New algorithms for digital convolution, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-vol. AS25(no. 5), pp. 392-410, October 1977.
• [2] Blahut R.E., Fast Algorithms for Digital Signal Processing, Addison-Wesley Publishing Company, Inc., 1985.
• [3] Parhi K.K., VLSI Digital Signal Processing Systems: Design and Implementation, John Wiley & Sons, 1999.
• [4] Tariov A., Algorytmiczne modele i struktury wysokowydajnych procesorów DSP, Wydawnictwo Informa, 2001.
• [5] Selesnick W., Burrus C.S., Extending winograd’s small convolution algorithm to longer lengths, In Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 2.449-2.452, June 1994.
• [6] Nussbaumer H.J., Fast Fourier Transform and Convolution Algorithms, Springer-Verlag, 1982.
• [7] Burrus S., Parks T.W., Potts J.F., DFT/FFT and Convolution Algorithms and Implementation, John Wiley & Sons, 1985.
• [8] Tolimieri R., An M., Lu C., Algorithms for Discrete Fourier Transform and Convolution, Springer-Verlag, New York, 1989.
• [9] Mąka T., Tariov A., Właściwości realizacji bitowo-szeregowych układów dodawania oraz mnożenia dowolnego argumentu i liczby stałej, Materiały VII Krajowej Konferencji Reprogramowalne Układy Cyfrowe - RUC 2004.