A rationalized algorithm for complex-valued inner product calculation

• Autorzy: Cariow A. , Cariowa G.

Warianty tytułu

PL

Zracjonalizowany algorytm wyznaczania zespolonego iloczynu skalarnego

• Języki publikacji: EN

Abstrakty

EN

This paper presents a rationalized algorithm for calculating a complex-valued inner product. The main idea of algorithm synthesis uses the well-known opportunity to calculate the product of two complex numbers with three multiplications and five additions of real numbers. Thus, the proposed algorithmic solution reduces the number of real multiplications and additions compared to the schoolbook implementation, and takes advantage of parallelization of calculation offered by field-programmable gate arrays (FPGAs).

PL

W artykule został przedstawiony równoległy algorytm wyznaczania iloczynu skalarnego dwóch wektorów, których elementami są liczbami zespolonymi. Proponowany algorytm wyróżnia się w stosunku do całkowicie równoległej implementacji metody naiwnej zredukowaną złożonością multiplikatywną. Jeśli metoda naiwna wymaga wykonania 4N mnożeń (układów mnożących podczas implementacji sprzętowej) oraz 2(2N-1) dodawań (sumatorów) liczb rzeczywistych to proponowany algorytm wymaga tylko 3N mnożeń oraz 6N-1 dodawań. W pracy została przedstawiona zracjonalizowana wektorowo-macierzowa procedura obliczeniowa wyznaczania takich iloczynów a także zdefiniowane konstrukcje macierzowe, wchodzące w skład owej procedury. Przy implementacji sprzętowej proponowany algorytm posiada niewątpliwe walory w stosunku do implementacji naiwnego sposobu zrównoleglenia obliczeń wymagającego więcej bloków mnożących. A ponieważ blok mnożący pochłania znacznie więcej zasobów sprzętowych platformy implementacyjnej niż sumator, to redukcja liczby tych bloków przy projektowaniu jednostek obliczeniowych jest sprawą niezwykle aktualną. W przypadku implementacji jednostki do obliczania iloczynu skalarnego w strukturze FPGA proponowane rozwiązanie pozwala zaoszczędzić pewną część umieszczonej w układzie puli bloków mnożących lub też elementów logicznych.

Słowa kluczowe

EN

complex-valued inner product; arithmetic complexity reduction

PL

zespolony iloczyn skalarny; redukcja złożoności obliczeniowej

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 7
• Strony: 674--676
• Opis fizyczny: Bibliogr. 7 poz., rys., tab., wzory

Twórcy

autor

Cariow A.

autor

Cariowa G.

• West Pomeranian University of Technology, Szczecin,

Bibliografia

• [1] Knuth D. E.: The Art Of Computing Programing, Volume 2, Seminumerical Algorithms, Addison-Wesley, Reading, MA, USA, Second Ed., 1981.
• [2] Blahut R. E.: Fast algorithms for digital signal processing, Addison-Wesley Publishing company, Inc. 1985.
• [3] Regalia P. A. and Mitra K. S.: Kronecker Products, Unitary Matrices and Signal Processing Applications, SIAM Review. 1989, v. 31, no. 4, pp. 586-613.
• [4] Ţariov A.: Algorithmic aspects of calculation rationalization in digital signal processing. West Pomeranian University of Technology, Szczecin, 2011 (in Polish).
• [5] Fam A. T.: Efficient complex matrix multiplication, IEEE Transactions on Computers, 1988, v. 37, no. 7, pp. 877-879.
• [6] Connolly F. T., Yagle A. E.: Fast algorithms for complex matrix multiplication using surrogates, IEEE Transactions on Acoustics, Speech and Signal Processing, 1989, v. 37 no. 6, pp. 938-939.
• [7] Li Guoqiang, Liu Liren: Complex-valued matrix-vector multiplication using two’s complement representation. Optics Communications, 1994, v. 105, no. 3-4, pp. 161-166.