Improved magnitude estimation of complex numbers using alpha max and beta min algorithm

• Autorzy: Smyk R. , Czyżak M.

Warianty tytułu

PL

Ulepszony algorytm aproksymacji modułu liczby zespolonej z wykorzystaniem metody alpha max beta min

• Konferencja: XXVI cykl seminarów zorganizowanych przez PTETiS Oddział w Gdańsku ZASTOSOWANIE KOMPUTERÓW W NAUCE I TECHNICE 2016 (XXVI; 2016; Gdańsk)
• Języki publikacji: EN

Abstrakty

EN

The paper presents an improved algorithm for calculating the magnitude of complex numbers. This problem, which is a special case of square rooting, occurs for example, in FFT processors and complex FIR filters. The proposed method of magnitude calculation makes use of the modified alpha max and beta min algorithm. The improved version of the algorithm allows to control the maximum magnitude approximation error by using an adequate number of approximation regions. In this way it is possible to reduce the maximum error to 3.95% for one region, and 0.24% and 0.06% for four and eight regions, respectively. This algorithm in its basic form requires only two multiplications by a constant and one addition which are preceded by the choice of greater of two arguments with respect to their absolute values. The improved version requires one general division to determine the proper approximation region. The algorithm implementation issues are considered in the accompanying paper.

PL

W artykule przedstawiono ulepszony algorytm aproksymacji modułu liczby zespolonej. Wyznaczanie modułu liczby zespolonej wymagane jest przykładowo przy realizacji FFT i filtracji cyfrowej sygnałów zespolonych. Jest to specjalny przypadek obliczania pierwisatka kwadratowego. Wersja ulepszona algorytmu umożliwia pełną kontrolę maksymalnego błędu wyznaczania modułu liczby zespolonej. Możliwe jest to dzięki wyprowadzeniu ogólnej postaci algorytmu dla dowolnej liczby regionów aproksymacji. Umożliwia to redukcję wspomnianego błędu aproksymacji z 3,95% dla jednego regionu, do przykładowo 0,24% dla czterech regionów i 0,06% dla ośmiu regionów aproksymacji. Proponowana metoda bazuje na zmodyfikowanej wersji algorytmu alpha max beta min. Algorytm ten wymaga najpierw porównania wartości bezwzględnych części rzeczywistej i części urojonej liczby zespolonej w celu wyznaczenia większej z nich. Następnie algorytm w wersji podstawowej z jednym regionem aproksymacji konieczne jest wykonanie tylko dwóch mnożeń przez stałą oraz jednego sumowania. W wersji ulepszonej wykonywane jest dodatkowe dzielenie celem wyznaczenia odpowiedniego regionu aproksymacji. Zastosowano tu beziteracyjny algorytm dzielenia. Szczegółowe zagadnienia związane z implementacją układową ulepszonej wersji algorytmu zostały przedstawione w artykule towarzyszącym.

Słowa kluczowe

EN

alpha max beta min algorithm; complex number; magnitude

PL

algorytm alpha max beta min; aproksymacja modułu liczby zespolonej

• Wydawca: Wydział Elektrotechniki i Automatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej
• Rocznik: 2016
• Tom: Nr 51
• Strony: 167--171
• Opis fizyczny: Bibliogr. 11 poz., wykr., tab.

Twórcy

autor

Smyk R.

• Politechnika Gdańska, Wydział Elektrotechniki i Automatyki tel.: [phone]

autor

Czyżak M.

• Politechnika Gdańska, Wydział Elektrotechniki i Automatyki tel.: [phone]

Bibliografia

• 1. Stimson, G.W. Introduction to Airborne Radar, 2 edition ed.; SciTech Publishing, 2014.
• 2. Hassanieh, H.; Shi, L.; Abari, O.; Hamed, E.; Katabi, D. GHz-wide sensing and decoding using the sparse Fourier transform. Proceedings of IEEE International Conference on Computer Communications, INFOCOM 2014, pp. 2256–2264, 2014.
• 3. Filip, A. Linear approximations to 2 2 x y having equiripple error characteristics. IEEE Transactions on Audio and Electroacoustics 1973, 21, pp. 554–556.
• 4. Czyzak, M.; Smyk, R. FPGA realization of an improved alpha max plus beta min algorithm. Poznan University of Technology Academic Journals. Electrical Engineering 2014, 80, pp. 151-160.
• 5. Kosheleva, O. Babylonian method of computing the square root: Justifications based on fuzzy techniques and on computational complexity. 2009 Annual Meeting of the North American Fuzzy Information Processing Society, NAFIPS 2009, pp. 1–6.
• 6. Ercegovac, M. On Digit-by-Digit Methods for Computing Certain Functions. Conference Record of the 41th Asilomar Conference on Signals, Systems and Computers, ACSSC 2007, pp. 338–342.
• 7. Meher, P.; Valls, J.; Juang, T.B.; Sridharan, K.; Maharatna, K. 50 Years of CORDIC: Algorithms, Architectures, and Applications. IEEE Transactions on Circuits and Systems I: Regular Papers 2009, 56, pp. 1893–1907.
• 8. Sutikno, T. An Efficient Implementation of the Non Restoring Square Root Algorithm in Gate Level. International Journal of Computer Theory and Engineering 2011, 3, pp. 1793–8201.
• 9. Smyk R., Czyżak M., Implementation of improved magnitude estimation of complex numbers using alpha max and beta min algorithm, this issue.
• 10. Xilinx, Performance and Resource Utilization for Fast Fourier Transform v9.0, Vivado Design Suite Release 2016.3, 2016
• 11. Xiaohui Li, Blinka E., Very large FFT for TMS320C6678 processors, Texas Instruments, 2015.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.