Aspekty algorytmiczne redukcji liczby bloków mnożących w układzie do obliczania iloczynu dwóch kwaternionów

• Autorzy: Tariova G. , Tariov A.

Warianty tytułu

EN

Algorithmic aspects of multiplication block number reduction in a two quaternion hardware multiplier

• Języki publikacji: PL

Abstrakty

PL

W pracy został przedstawiony zracjonalizowany algorytm mnożenia dwóch kwaternionów wymagający wykonania mniejszej liczby operacji mnożenia i dodawania, niż dowolny ze znanych autorom "szybkich" algorytmów tego typu. Pozwala to przy implementacji zmniejszyć nakłady obliczeniowe lub zapotrzebowanie na zasoby sprzętowe oraz stworzyć dogodne warunki do efektywnej realizacji operacji mnożenia dwóch kwaternionów w dowolnym sprzętowo-programowym środowisku implementacyjnym.

EN

In the paper the rationalised algorithm for two quaternion product calculating with the reduced number of arithmetic operations (or multipliers and adders - in hardware implementation case) is presented. The computing of quaternion product in the naive way, using the definition, takes 16 multiplications and 12 additions, while the proposed algorithm can compute the same result in only 8 multiplications and 28 additions. This approach allows lowering hardware expenses and creates favorable conditions for effective convolution realisation on the reprogrammable platform. The computational procedure for quaternion multiplication is described in matrix notation. This notation enables adequate representation of the space-time structures of an implemented computational process and directly maps these structures into the hardware realisation space. The proposed structure can be successfully applied to accelerate calculations on FPGA based platforms as well as enhance the efficiency of hardware in general.

Słowa kluczowe

PL

iloczyn kwaternionów; liczby hiperzespolone; algorytmy i układy obliczeniowe

EN

hypercomplex numbers; quaternion product; computation algorithms and units

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 688--690
• Opis fizyczny: Bibliogr. 28 poz., rys., tab., wzory

Twórcy

autor

Tariova G.

autor

Tariov A.

• Zachodniopomorski Uniwersytet Technologiczny, Wydział Informatyki, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Kantor I. and Solodovnikov A.: Hypercomplex numbers, Sprin-ger-Verlag, New York, 1989.
• [2] Bülow T. and Sommer G.: Hypercomplex signals - a novel extension of the analytic signal to the multidimensional case, IEEE Trans. Sign. Proc., vol. SP-49, no 11, pp. 2844–2852, Nov. 2001.
• [3] Schütte H. D. and Wenzel J.: Hypercomplex numbers in digital signal processing, in Proc. ISCAS’90, New Orleans, 1990, pp. 1557-1560.
• [4] Alfsmann D.: On families of 2N-dimensional hypercomplex algebras suitable for digital signal processing, in Proc. European Signal Processing Conf. (EUSIPCO 2006), Florence, Italy, 2006.
• [5] Alfsmann D., H. Göckler G., Sangwine S. J. and Ell T. A.: Hypercomplex Algebras in Digital Signal Processing: Benefits and Drawbacks (Tutorial). Proc. EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Poznań, Poland, 2007, pp. 1322-1326.
• [6] Moxey C. E., Sangwine S. J. and Ell T. A.: Hypercomplex correlation techniques for vector images, IEEE Trans. Signal Processing, vol. 51, pp. 1941-1953, July 2003.
• [7] Ueda K., Takahashi S.I.: Digital filters with hypercomplex coefficients, in Proc. IEEE Int. Symp. Circuits Syst., May 1993, vol. 1, pp. 479-482.
• [8] Deavours C. A.: The quaternion calculus, The American Mathematical Monthly, vol. 80, pp. 995-1008, 1973.
• [9] Pei S. C., Chang J. H. and Ding J. J.: Commutative reduced biquaternions and their Fourier transform for signal and image processing applications, IEEE Trans. on Signal Processing, vol. 52, no 7, pp. 2012-2031, 2004.
• [10] Pei Soo-Chang, Ding Jian-Jiun and Chang Ja-Han: Efficient Implementation of Quaternion Fourier Transform, Convolution, and Correlation by 2-D Complex FFT. IEEE Transactions On Signal Processing, vol. 49, no 11, November 2001, pp. 2783-2797.
• [11] Pei S. C., Ding J. J., Chang J. H.: Color pattern recognition by quaternion correlation, in Proc. IEEE Int. Conf. Image Process., 2000, pp. 847-849.
• [12] Sangwine S. J., Le Bihan N.: Hypercomplex analytic signals: extension of the analytic signal concept to complex signals, Proc. EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Poznań, Poland, 2007, Poznań, pp. 621-624.
• [13] Sangwine S.: Fourier transforms of color images using quaternion or hypercomplex, numbers, in Electronics Letters, 10 Oct. 1996, vol. 32, pp. 1979-1980.
• [14] Sangwine S. J. and Ell T. A.: Hypercomplex auto- and cross-correlation of color images, in Proc. ICIP, 1999, pp. 319-323.
• [15] Sangwine S. J.: Colour image edge detector based on quaternion convolution, Electron. Lett., vol. 34, no 10, pp. 969-971, May 1998.
• [16] Toyoshima H.: Computationally efficient implementation of hypercomplex digital filters, in Proc. IEEE Int. Conference on Acoustics, Speech, and Signal Processing (ICASSP’98), Seattle, USA, 1998, vol. 3, pp. 1761-1764.
• [17] Ell T.: Quaternion-Fourier transforms for analysis of two-dimensional linear time-invariant partial differential systems, in Decision and Control, 1993. Proceedings of the 32nd IEEE Conference on, 15-17 Dec. 1993, pp. 1830–1841.
• [18] Miron S., Le Bihan N., and Mars J.: High resolution vector-sensor array processing based on biquaternions, in Proc IEEE Conf. ICASSP, Toulouse, France, 2006.
• [19] Witten B. and Shragge J.: Quaternion-based Signal Processing. Proceedings of the New Orleans 2006 Annual Meeting, pp. 2862-2865.
• [20] Bayro-Corrochano Eduardo: The Theory and Use of the Quaternion Wavelet Transform, Journal of Mathematical Imaging and Vision, 2006, Volume 24, Issue 1, pp. 19-35.
• [21] Bayro-Corrochano Eduardo: Multi-resolution image analysis using the quaternion wavelet transform, Numerical Algorithms, Volume 39, Numbers 1-3, July, 2005, pp. 35-55.
• [22] Hitzer E.: Foundations of Multidimensional Wavelet Theory: The Quaternion Fourier Transform and its Generalizations, Preprints of Meeting of the Japan Society for Industrial and Applied Mathematics, Tsukuba University, 16-18 Sep. 2006, Tsukuba, Japan, pp. 66-67.
• [23] Dimitrov V. S., Cooklev T. V. and Donevsky B. D.: On the multiplication of reduced biquaternions and applications, Infor. Process. Letters, 1992, vol. 43, no 3, pp. 161-164.
• [24] De Groote H. F.: On the complexity of quaternion multiplication, Infor. Process.Lett. 1975, vol. 43, no 6, pp. 161-164.
• [25] Howell T. D., Jean-Claude Lafon: The complexity of the quaternion product, TR 75-245, Cornell Univ., http://citeseer.nj.nec.com/ howell75 complexity.html, June 1975.
• [26] Maкаров О. М.: Алгоритм умножения двух кватернионов. Журнал вычислительной математики и математической физики. 1977, т. 17, № 6 стр. 1574-1575.
• [27] Росошек С. K., Литвин A. И., Черняева Н. E.: Быстрый алгоритм произведения двух гиперкомплексных чисел. Известия томского государственного университета „Математика, Кибернетика, Информатика”, 2000, № 269, стр. 66-68.
• [28] Ţariov A.: Strategie racjonalizacji obliczeń przy wyznaczaniu iloczynów macierzowo-wektorowych. Metody Informatyki stosowanej, Nr 1, 2008, str. 147-158.