Small-Size Algorithms for Quaternion Discrete Fourier Transform
Source abstract
Abstract
The quaternion discrete Fourier transform (QDFT) is a powerful tool in modern digital signal processing, even though until recently this transformation seemed exotic. In recent years, quite a lot of publications have appeared devoted to effective ways to calculate this transformation. In particular, in one of our previous publications, we presented an economical algorithm for calculating one-dimensional QDFT and showed that this algorithm has the lowest computational complexity among all known algorithms of this type. This generalized algorithm is suitable for computing the QDFT of any sequence in which the number of elements is a power of two. However, as it turned out, there are additional possibilities that make it possible to further reduce the computational complexity of the developed algorithm for each specific N. In this article, we provide some examples of the synthesis of such algorithms for short-length input sequences (samples of signals). In particular, algorithms for N ∊ {2, 3, 4, 5, 6, 7, 8} are presented. A parallel implementation of the proposed algorithm allows for saving more than half of the number of required multipliers in each case compared with the parallel implementation of the naive methods of calculation.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Mathematical Analysis and Transform Methods · Algebraic and Geometric Analysis · Image and Signal Denoising Methods
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, Żołnierska 52, 71-210 Szczecin, Poland
References (33)
Show source-provided references
1. Briggs, W.L., and Henson, V.E. (1987). The DFT: An Owners’ Manual for the Discrete Fourier Transform, Society for Industrial and Applied Mathematics.
2. Burrus, S., Parks, T.W., and Potts, J.F. (1985). DFT/FFT and Convolution Algorithms and Implementation, John Wiley & Sons.
3. Tolimieri, R., An, M., and Lu, C. (1989). Algorithms for Discrete Fourier Transform and Convolution, Springer.10.1007/978-1-4757-3854-4 ↗
4. An algorithm for the machine calculation of complex Fourier series10.1090/S0025-5718-1965-0178586-1 ↗
5. Nussbaumer, H.J. (1982). Fast Fourier Transform and Convolution Algorithms, Springer.10.1007/978-3-642-81897-4 ↗
6. Garg, H.K. (1998). Digital Signal Processing Algorithms: Number Theory, Convolution, Fast Fourier Transforms, and Applications, CRC Press.
7. Bi, G., and Zeng, Y. (2004). Transforms and Fast Algorithms for Signal Analysis and Representations, Birkhäuser.10.1007/978-0-8176-8220-0 ↗
8. Quaternions in signal and image processing: A comprehensive and objective overview10.1109/MSP.2023.3278071 ↗
9. García-Retuerta, D., Casado-Vara, R., Martin-del Rey, A., De la Prieta, F., Prieto, J., and Corchado, J.M. (2020, January 4–6). Quaternion Neural Networks: State-of-the-Art and Research Challenges. Proceedings of the Intelligent Data Engineering and Automated Learning—IDEAL, Guimaraes, Portugal.10.1007/978-3-030-62365-4_43 ↗
10. Vince, J. (2011). Quaternions for Computer Graphics, Springer.10.1007/978-0-85729-760-0 ↗
11. An algorithm for quaternion-based 3D rotation10.34768/amcs-2020-0012 ↗
12. On Decoupled Decoding of Quasi-Orthogonal STBCs using Quaternion Algebra10.1109/JSYST.2018.2865216 ↗
13. Pӧppelbaum, J., and Schwung, A. (2024). Time Series Compression using Quaternion Valued Neural Networks and Quaternion Backpropagation. arXiv.
14. Quaternion Analysis Tools for Engineering and Scientific Applications10.2514/1.35632 ↗
15. Hypercomplex signals—A novel extension of the analytic signal to the multidimensional case
16. Schütte, H.-D., and Wenzel, J. (1990, January 1–3). Hypercomplex numbers in digital signal processing. Proceedings of the ISCAS ’90, New Orleans, LA, USA.
17. Alfsmann, D., Göckler, H.G., Sangwine, S.J., and Ell, T.A. (2007, January 3–7). Hypercomplex algebras in digital signal processing: Benefits and drawbacks. Proceedings of the 15th European Signal Processing Conference, Poznań, Poland.
18. Hypercomplex Fourier Transforms of Color Images10.1109/TIP.2006.884955 ↗
19. Sangwine, S., and Ell, T. (1999, January 24–28). Hypercomplex auto- and crosscorrelation of color images. Proceedings of the ICIP 99, Kobe, Japan.
20. Efficient implementation of quaternion Fourier transform, convolution and correlation by 2-D complex FFT10.1109/78.960426 ↗
21. On One-Dimensional Quaternion Fourier Transform10.1088/1742-6596/1341/6/062004 ↗
22. Discrete Double-Sided Quaternionic Fourier Transform and Application
23. Eigenstructure and fractionalization of the quaternion discrete Fourier transform10.1016/j.ijleo.2019.163957 ↗
24. 2-D Left-Side Quaternion Discrete Fourier Transform: Fast Algorithm10.2352/ISSN.2470-1173.2016.15.IPAS-192 ↗
25. Tensor transform-based quaternion Fourier transform algorithm10.1016/j.ins.2015.05.018 ↗
26. Ell, T.A., and Sangwine, S.J. (2000, January 1). Decomposition of 2D hypercomplex Fourier transforms into pairs of complex Fourier transforms. Proceedings of the 2000 10th European Signal Processing Conference, Tampere, Finland.
27. Felsberg, M.M., Bulov, T., Sommer, G., and Chernov, V.M. (2000). Fast Algorithms of Hypercomplex Fourier Transforms. Geometric Computing with Clifford Algebras, Springer.10.1007/978-3-662-04621-0_10 ↗
28. Majorkowska-Mech, D., and Cariow, A. (2023). One-Dimensional Quaternion Discrete Fourier Transform and an Approach to Its Fast Computation. Electronics, 12.10.3390/electronics12244974 ↗
29. A new discrete Fourier transform algorithm using butterfly structure fast convolution10.1109/TASSP.1985.1164684 ↗
30. Steeb, W.H., and Hardy, Y. (2011). Matrix Calculus and Kronecker Product: A Practical Approach to Linear and Multilinear Algebra, World Scientific Publishing Company. [2nd ed.].10.1142/8030 ↗
31. Strategies for the Synthesis of Fast Algorithms for the Computation of the Matrix-vector Products
32. Deshpande, A., and Draper, J. (2010, January 1–4). Squaring units and a comparison with multipliers. Proceedings of the 53rd IEEE International Midwest Symposium on Circuits and Systems (MWSCAS 2010), Seattle, WA, USA.10.1109/MWSCAS.2010.5548763 ↗
33. Cariow, A., Naumowicz, M., and Handkiewicz, A. (2024). Structure and Principles of Operation of a Quaternion VLSI Multiplier. Appl. Sci., 14.10.3390/app14188123 ↗