informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-182Research ArticleОБРАБОТКА СИГНАЛОВ, ИЗОБРАЖЕНИЙ, РЕЧИ, ТЕКСТА И РАСПОЗНАВАНИЕ ОБРАЗОВSIGNAL, IMAGE, SPEECH, TEXT PROCESSING AND PATTERN RECOGNITIONCORDIC-ТЕХНИКА ДЛЯ ФИКСИРОВАННОГО УГЛА ВРАЩЕНИЯ В ОПЕРАЦИИ УМНОЖЕНИЯ КВАТЕРНИОНОВCORDIC TECHNIQUES FOR FIXED ANGLE OF ROTATION IN MULTIPLYING OPERATION OF QUATERNIONSПетровскийН. А.PetrovskyN. A.

Минск, П. Бровки, 6 

nick@petrovsky.euСтанкевичА. В.StankevichA. V.

Минск, П. Бровки, 6 

stankevich@bsuir.byПетровскийА. А.PetrovskyA. A.

Минск, П. Бровки, 6 

palex@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиBelarus2015121120160485108Copyright © Петровский Н.А., Станкевич А.В., Петровский А.А., 20162016Петровский Н.А., Станкевич А.В., Петровский А.А.Petrovsky N.A., Stankevich A.V., Petrovsky A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/182

Предлагается ряд решений ключевого элемента параунитарного банка фильтров на основе алгебры кватернионов – умножителя кватернионов с использованием CORDIC (Coordinate Rotation Digital Computer)-техники для фиксированного угла вращения, в которых в отличие от известных решений параметры управления 4D-вращением представляются нелинейной функцией числа сдвигов входных операндов операции микровращения. Предложенный подход проектирования умножителя на кватернион-константу позволяет достигать максимальной производительности схемы умножителя при скромном использовании ресурсов, например FPGA.

The article contains a number of solutions for the key element of paraunitary filter banks based on quaternionic algebra (Q-PUBF) – the multiplier of quaternions with usage of CORDIC (Coordinate Rotation Digital Computer) techniques for the fixed angle of rotation where, unlike known solutions, 4D rotation control parameters are represented by nonlinear function of shifts number of input operands of the microrotation operation. Suggested approach of the multiplier designing on a quaternion-constant allows reaching the maximum performance of the multiplier scheme with low use of resources, for example, of FPGA.

ReferencesКантор, И.Л. Гиперкомплексные числа / И.Л. Кантор, А.С. Солодовников. – М. : Наука, 1973. – 145 с.Кантор, И.Л. Гиперкомплексные числа / И.Л. Кантор, А.С. Солодовников. – М. : Наука, 1973. – 145 с.Parfieniuk, M. Quaternionic building block for paraunitary filter banks / M. Parfieniuk, A. Petrovsky // Proc. 12th European Signal Processing Conf. (EUSIPCO). – Vienna, Austria, 2004. – P. 1237–1240.Parfieniuk, M. Quaternionic building block for paraunitary filter banks / M. Parfieniuk, A. Petrovsky // Proc. 12th European Signal Processing Conf. (EUSIPCO). – Vienna, Austria, 2004. – P. 1237–1240.Choukroun, D. Novel quaternion kalman filter / D. Choukroun, I. Bar-Itzhack, Y. Oshman // IEEE Trans. Aerosp. Electron. Syst. – 2006. – Vol. 42, № 1. – P. 174–190.Choukroun, D. Novel quaternion kalman filter / D. Choukroun, I. Bar-Itzhack, Y. Oshman // IEEE Trans. Aerosp. Electron. Syst. – 2006. – Vol. 42, № 1. – P. 174–190.Miron, S. Quaternion-music for vector-sensor array processing / S. Miron, N. Le Bihan, J. Mars // IEEE Trans. Signal Process. – 2006. – Vol. 54, № 4. – P. 1218–1229.Miron, S. Quaternion-music for vector-sensor array processing / S. Miron, N. Le Bihan, J. Mars // IEEE Trans. Signal Process. – 2006. – Vol. 54, № 4. – P. 1218–1229.Hsiao, S.F. Parallel singular value decomposition of complex matrices using multidimensional CORDIC algorithms / S.F. Hsiao, J.M. Delosme // IEEE Trans. Signal Process. – 1996. – Vol. 44, № 3. – P. 685–697.Hsiao, S.F. Parallel singular value decomposition of complex matrices using multidimensional CORDIC algorithms / S.F. Hsiao, J.M. Delosme // IEEE Trans. Signal Process. – 1996. – Vol. 44, № 3. – P. 685–697.Sercov, V.V. Digital hypercomplex all-pass filters: A novel filters bank building block / V.V. Sercov, A.A. Petrovsky, D.V. Lushtyk // Proc. 6th Int. Workshop on Systems, Signals and Image Proc. (IWSSIP). – Bratislava, Slovakia, 1999. – P. 181–184.Sercov, V.V. Digital hypercomplex all-pass filters: A novel filters bank building block / V.V. Sercov, A.A. Petrovsky, D.V. Lushtyk // Proc. 6th Int. Workshop on Systems, Signals and Image Proc. (IWSSIP). – Bratislava, Slovakia, 1999. – P. 181–184.Парфенюк, М. Параунитарные банки фильтров на основе алгебры кватернионов: теория и применение / М. Парфенюк, А.А. Петровский // Цифровая обработка сигналов. – 2008. – № 1. – С. 22–36.Парфенюк, М. Параунитарные банки фильтров на основе алгебры кватернионов: теория и применение / М. Парфенюк, А.А. Петровский // Цифровая обработка сигналов. – 2008. – № 1. – С. 22–36.Parfieniuk, M. Inherently lossless structures for eight- and six-channel linear-phase paraunitary filter banks based on quaternion multipliers / M. Parfieniuk, A. Petrovsky // Signal Process. – 2010. – Vol. 90. – P. 1755–1767.Parfieniuk, M. Inherently lossless structures for eight- and six-channel linear-phase paraunitary filter banks based on quaternion multipliers / M. Parfieniuk, A. Petrovsky // Signal Process. – 2010. – Vol. 90. – P. 1755–1767.Alexiadis, D. Estimation of motions in color image sequences using hypercomplex Fourier transforms / D. Alexiadis, G. Sergiadis // IEEE Trans. Image Process. – 2009. – Vol. 18, № 1. – P. 168–187.Alexiadis, D. Estimation of motions in color image sequences using hypercomplex Fourier transforms / D. Alexiadis, G. Sergiadis // IEEE Trans. Image Process. – 2009. – Vol. 18, № 1. – P. 168–187.Karney, C. Quaternions in molecular modeling / C. Karney // J. Molecular Graphics and Modelling. – 2007. – Vol. 25, № 5. – P. 595–604.Karney, C. Quaternions in molecular modeling / C. Karney // J. Molecular Graphics and Modelling. – 2007. – Vol. 25, № 5. – P. 595–604.Vaidyanathan, P.P. Multirate Systems and Filter Banks / P.P. Vaidyanathan. – Englewood Cliffs : Prentice-Hall, 1993. – 911 p.Vaidyanathan, P.P. Multirate Systems and Filter Banks / P.P. Vaidyanathan. – Englewood Cliffs : Prentice-Hall, 1993. – 911 p.Howell, T.D. The complexity of the quaternion product: Tech. Rep. TR 75-245 / T.D. Howell, J.C. Lafon [Электронный ресурс]. – 1975. – Mode of access : http://www.theworld.com/ ~sweetser/quaternions/ps/cornellcstr75-245.pdf. – Date of access : 05.10.2015.Howell, T.D. The complexity of the quaternion product: Tech. Rep. TR 75-245 / T.D. Howell, J.C. Lafon [Электронный ресурс]. – 1975. – Mode of access : http://www.theworld.com/ ~sweetser/quaternions/ps/cornellcstr75-245.pdf. – Date of access : 05.10.2015.Parfieniuk, M. Quaternion multiplier inspired by the lifting implementation of plane rotations / M. Parfieniuk, A. Petrovsky // IEEE Trans. Circuits Syst. I. – 2010. – Vol. 57, № 10. – P. 2708–2717.Parfieniuk, M. Quaternion multiplier inspired by the lifting implementation of plane rotations / M. Parfieniuk, A. Petrovsky // IEEE Trans. Circuits Syst. I. – 2010. – Vol. 57, № 10. – P. 2708–2717.Parfieniuk, M. Rapid Prototyping of Quaternion Multiplier: From Matrix Notation to FPGA-Based Circuits / M. Parfieniuk, N. Petrovsky, A. Petrovsky // Rapid Prototyping Technology: Principles and Functional Requirements. – Vienna : InTech, 2011. – P. 227–246.Parfieniuk, M. Rapid Prototyping of Quaternion Multiplier: From Matrix Notation to FPGA-Based Circuits / M. Parfieniuk, N. Petrovsky, A. Petrovsky // Rapid Prototyping Technology: Principles and Functional Requirements. – Vienna : InTech, 2011. – P. 227–246.50 years of CORDIC: Algorithms, architectures, and applications / P. Meher [et al] // IEEE Trans. Circuits Syst. I. – 2009. – Vol. 56, № 9. – P. 1893–1907.50 years of CORDIC: Algorithms, architectures, and applications / P. Meher [et al] // IEEE Trans. Circuits Syst. I. – 2009. – Vol. 56, № 9. – P. 1893–1907.Volder, J.E. The CORDIC trigonometric computing technique / J. E. Volder // IRE Trans. Electron. Comput. – 1959. – Vol. 8. – P. 330–334.Volder, J.E. The CORDIC trigonometric computing technique / J. E. Volder // IRE Trans. Electron. Comput. – 1959. – Vol. 8. – P. 330–334.Walther, J.S. A unified algorithm for elementary functions / J.S. Walther // Proceedings of the Spring Joint Computer Conf. AFIPS '71 (Spring). – N. Y. : ACM, 1971. – P. 379–385.Walther, J.S. A unified algorithm for elementary functions / J.S. Walther // Proceedings of the Spring Joint Computer Conf. AFIPS '71 (Spring). – N. Y. : ACM, 1971. – P. 379–385.Hsiao, S.-F. Householder CORDIC algorithms / S.-F. Hsiao, J.-M. Delosme // IEEE Trans. Comput. – 1995. – Vol. 44, № 8. – P. 990–1001.Hsiao, S.-F. Householder CORDIC algorithms / S.-F. Hsiao, J.-M. Delosme // IEEE Trans. Comput. – 1995. – Vol. 44, № 8. – P. 990–1001.Гантмахер, Ф.Р. Теория матриц / Ф.Р. Гантмахер; 5-е изд. – М. : Физматлит, 2004. – 560 с.Гантмахер, Ф.Р. Теория матриц / Ф.Р. Гантмахер; 5-е изд. – М. : Физматлит, 2004. – 560 с.Hsiao, S.-F. Redundant constant-factor implementation of multi-dimensional CORDIC and its application to complex SVD / S.-F. Hsiao, C.-Y. Lau, J.-M. Delosme // IEEE Trans. VLSI Syst. – 2000. – Vol. 25, № 2. – P. 155–166.Hsiao, S.-F. Redundant constant-factor implementation of multi-dimensional CORDIC and its application to complex SVD / S.-F. Hsiao, C.-Y. Lau, J.-M. Delosme // IEEE Trans. VLSI Syst. – 2000. – Vol. 25, № 2. – P. 155–166.Петровский, Н.А. Многомерный CORDIC алгоритм кватернионов с «разреженными» итерациями / Н.А. Петровский, М. Парфенюк // Труды 15-й Междунар. конф. «Цифровая обработка сигналов и ее применение» (DSPA'2013). – Т. 2. – М., 2013. – С. 206–210.Петровский, Н.А. Многомерный CORDIC алгоритм кватернионов с «разреженными» итерациями / Н.А. Петровский, М. Парфенюк // Труды 15-й Междунар. конф. «Цифровая обработка сигналов и ее применение» (DSPA'2013). – Т. 2. – М., 2013. – С. 206–210.Петровский, Н.А. 4D-CORDIC арифметика для процессора параунитарного банка фильтров на основе алгебры кватернионов / Н.А. Петровский, М. Парфенюк, А.А. Петровский // Труды 40-й Междунар. науч. конф. «Вопросы оптимизации вычислений» (BOB-XL). – Ялта, 2013. – С. 214–215.Петровский, Н.А. 4D-CORDIC арифметика для процессора параунитарного банка фильтров на основе алгебры кватернионов / Н.А. Петровский, М. Парфенюк, А.А. Петровский // Труды 40-й Междунар. науч. конф. «Вопросы оптимизации вычислений» (BOB-XL). – Ялта, 2013. – С. 214–215.Benes, V.E. Mathematical theory of connecting networks and telephone traffic / V.E. Benes. – N. Y. : Academic Press, 1965. – 319 p.Benes, V.E. Mathematical theory of connecting networks and telephone traffic / V.E. Benes. – N. Y. : Academic Press, 1965. – 319 p.Suzuki, T. Generalized block-lifting factorization of M-channel biorthogonal filter banks for lossy-to-lossless image coding / T. Suzuki, M. Ikehara, T. Nguyen // IEEE Trans. Image Process. – 2012. – Vol. 21, № 7. – P. 3220–3228.Suzuki, T. Generalized block-lifting factorization of M-channel biorthogonal filter banks for lossy-to-lossless image coding / T. Suzuki, M. Ikehara, T. Nguyen // IEEE Trans. Image Process. – 2012. – Vol. 21, № 7. – P. 3220–3228.Wavelet transforms that map integers to integers / A.R. Calderbank [et. al.] // Appl. Comput. Harmon. Anal. – 1998. – Vol. 5, № 3. – P. 332–369.Wavelet transforms that map integers to integers / A.R. Calderbank [et. al.] // Appl. Comput. Harmon. Anal. – 1998. – Vol. 5, № 3. – P. 332–369.Petrovsky, N. Pipelined embedded processor of quaternionic m-band wavelets for image multiresolution analysis / N. Petrovsky, M. Parfieniuk, A. Petrovsky // 2nd Mediterranean Conf. on Embedded Computing (MECO). – Budva, Monternegro, 2013. – P. 196–199.Petrovsky, N. Pipelined embedded processor of quaternionic m-band wavelets for image multiresolution analysis / N. Petrovsky, M. Parfieniuk, A. Petrovsky // 2nd Mediterranean Conf. on Embedded Computing (MECO). – Budva, Monternegro, 2013. – P. 196–199.Оранский, А.М. Аппаратные методы в цифровой вычислительной технике / А.М. Оранский. – Минск : ЕСУ, 1977. – 208 с.Оранский, А.М. Аппаратные методы в цифровой вычислительной технике / А.М. Оранский. – Минск : ЕСУ, 1977. – 208 с.Petrovsky, N.A. The CORDIC-inside-lifting architecture for constant-coefficient hardware quaternion multipliers / N.A. Petrovsky, M. Parfieniuk // Proc. Intern. Conf. on Signals and Electronic Systems (ICSES). – Wroclaw, 2012. – P. 1–6.Petrovsky, N.A. The CORDIC-inside-lifting architecture for constant-coefficient hardware quaternion multipliers / N.A. Petrovsky, M. Parfieniuk // Proc. Intern. Conf. on Signals and Electronic Systems (ICSES). – Wroclaw, 2012. – P. 1–6.Петровский, Н.А. Рекурсивный процессор умножителя кватернионов со структурной CORDIC-лестничной параметризацией / Н.А. Петровский, А.В. Станкевич // Труды Меж- дунар. науч. конф. «Информационные технологии и системы» (ИТС’2013). – Минск : БГУИР, 2013. – C. 196–197.Петровский, Н.А. Рекурсивный процессор умножителя кватернионов со структурной CORDIC-лестничной параметризацией / Н.А. Петровский, А.В. Станкевич // Труды Меж- дунар. науч. конф. «Информационные технологии и системы» (ИТС’2013). – Минск : БГУИР, 2013. – C. 196–197.Meher, P. CORDIC designs for fixed angle of rotation / P. Meher, S. Park // IEEE Trans. VLSI Syst. – 2013. – Vol. 21, № 2. – P. 217–228.Meher, P. CORDIC designs for fixed angle of rotation / P. Meher, S. Park // IEEE Trans. VLSI Syst. – 2013. – Vol. 21, № 2. – P. 217–228.

The authors declare that there are no conflicts of interest present.