Czasopismo | PRZEGLĄD ELEKTROTECHNICZNY | Rocznik 2017 - zeszyt 1

A Hardware-oriented Algorithm for Complex-valued Constant Matrix-vector Multiplication

:10.15199/48.2017.01.21

nr katalogowy: 103193
:10.15199/48.2017.01.21

In this communication we present a hardware-oriented algorithm for constant matrix-vector product calculating, when the all elements of vector and matrix are complex numbers. The main idea behind our algorithm is to combine the advantages of Winograd’s inner product formula with Gauss's trick for complex number multiplication. The proposed algorithm versus the naïve method of analogous calculations drastically reduces the number of multipliers required for FPGA implementation of complex-valued constant matrix-vector multiplication. If the fully parallel hardware implementation of naïve (schoolbook) method for complex-valued matrix-vector multiplication requires 4MN multipliers, 2M N-inputs adders and 2MN two-input adders, the proposed algorithm requires only 3N(M+1)/2 multipliers and [3M(N+2)+1,5N+2] two-input adders and 3(M+1) N/2-input adders. Streszczenie. W komunikacie został zaprezentowany sprzętowo-zorientowany algorytm mnożenia macierzy stałych przez wektor zmiennych w założeniu, gdy zarówno elementy macierzy jak i elementy wektora są liczbami zespolonymi. Główna idea proponowanego algorytmu polega na łącznym zastosowaniu wzoru Winograda do wyznaczania iloczynu skalarnego oraz formuły Gaussa mnożenia liczb zespolonych. W porównaniu z tradycyjnym sposobem realizacji obliczeń proponowany algorytm pozwala zredukować liczbę układów mnożących niezbędnych do całkowicie równoległej realizacji na platformie FPGA układu wyznaczania iloczynu wektorowo-macierzowego. Jeśli całkowicie równoległa implementacja tradycyjnej metody wyznaczania omawianych iloczynów wymaga 4MN bloków mnożących, 2M N-wejściowych sumatorów oraz 2MN sumatorów dwuwejściowych, to proponowany algorytm wymaga tylko 3N(M+1)/2 błoków mnożenia, [3M(N+2)+1,5N+2] sumatorów dwuwejściowych i 3(M+1) sumatorów N/2-wejściowych. (Sprzętowo-zorientowany algorytm wyznaczania iloczynu macierzy stałych przez wektor zmiennych dla danych zespolonych). Keywords: algorithm design[...]

Bibliografia

[1] B lahut , R. E. Fast algorithms for digital signal processing, Addison-Wesley Publishing company, Inc. 1985
[2] P r a t t , W. K. Digital Image Processing (Second Edition), John Wiley & Sons, New York, 1991.
[3] Fuj imoto, N. Dense matrix-vector multiplication on the CUDA architecture, Parallel Processing Letters, vol. 18, no. 4, 511- 530, 2008.
[4] Qasim, S. M., Telba, A. A. and Al Mazroo, A. Y. FPGA Design and Implementation of Matrix Multiplier Architectures for Image and Signal Processing, IJCSNS International Journal of Computer Science and Network Security, vol.10, no.2, 168-176, 2010.
[5] Fam, A. T. Efficient complex matrix multiplication, IEEE Transactions on Computers, vol. 37, no. 7, 877-879, 1988.
[6] Connolly, F. T. Yagle, A. E. Fast algorithms for complex matrix multiplication using surrogates, IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 37, no. 6, 938 - 939, 1989.
[7] O l l i l a , E. Koivunen, V. Poor, H. V. Complex-valued signal processing — essential models, tools and statistics, Information Theory and Applications Workshop, 6-11 Feb. 2011, 1 - 10.
[8] Guoqiang Li, Liren Liu Complex-valued matrix-vector multiplication using twos complement representation". Optics Communications, vol. 105, no. 3-4, 161-166.
[9] Barazesh B., Michal ina J. and Pi cco A. A VLSI signal processor with complex arithmetic capability. IEEE Transactions on Circuits and Systems, 35(5), 495-505, 1988.
[10] Gus tafsson O., Ohl sson H. and Wanhammar L., Lowcomplexity constant coefficient matrix multiplication using a minimum spanning tree approach, Proceedings of the 6th Nordic Signal Processing Symposium (NORSIG 2004), June 9 - 11, Espoo, Finland, 141-144, 2004.
[11] Boullis N. Tisserand A. Some optimizations of hardware multiplication by constant matrices, IEEE Transactions on Computers, 2005, vol. 54, no 10, 1271 - 1282.
[12] Kinane A. Muresan V. Towards an optimized VLSI design algorithm for the constant matrix multiplication problem. In: Proc. IEEE International Symposium on Circuits and Systems (ISCAS-2006), 5111 - 5114, 2006.
[13] Car iow A., Car iowa G., An algorithm for complex-valued vector-matrix multiplication. Electrical Review, R 88, no 10b, 213-216, 2012.
[14] Car iow A., Car iowa G., A rationalized algorithm for complex-valued inner product calculation, Measurement Automation and Monitoring, no 7, pp. 674-676, 2012.
[15] Winograd S. A new algorithm for inner Product, IEEE Transactions on Computers, vol. C-17, no 7, 693 - 694, 1968.
[16] Knuth D. E., The Art Of Computing Programming, vol. 2, Semi-numerical Algorithms, Addison-Wesley, Reading, MA, USA, Second Ed., 1981.
[17] Regalia P. A. and Mi t ra K. S., Kronecker Products, Unitary Matrices and Signal Processing Applications, SIAM Review., vol. 31, no. 4, pp. 586-613, 1989

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 103193 "A Hardware-oriented Algor..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2017-1 licencja: Osobista Produkt cyfrowy	55.00 zł
PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2017-10 licencja: Osobista Produkt cyfrowy	55.00 zł
PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2017-11 licencja: Osobista Produkt cyfrowy	55.00 zł
PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2017-12 licencja: Osobista Produkt cyfrowy	55.00 zł

Prenumerata

PRZEGLĄD ELEKTROTECHNICZNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

762.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	1002.00 zł brutto 927.78 zł netto 74.22 zł VAT (stawka VAT 8%)

1002.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna	960.00 zł brutto 888.89 zł netto 71.11 zł VAT (stawka VAT 8%)
PRZEGLĄD ELEKTROTECHNICZNY - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

1002.00 zł

Zeszyt

2017-1

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma