Fast fractional Fourier transform

Stepan Martiugin, Sergey Porshnev

Abstract


Fractional Fourier transform (FrFT) is one-parametric family of unitary transformations . FrFT are usually interpreted as rotations in the time-frequency plane. In case  FrFT becomes an ordinary Fourier transform (), in case  we have inversion transform (), for  FrFT corresponds to inverse Fourier Transform (), and for  (or ) we have identity transform (). The family  forms a one-parameter continuous unitary group with additive multiplication . FrFT corresponds to decomposition of a signal into linear combination of chirps (or signals in which the frequency increases (up-chirp) or decreases (down-chirp) with time). FrFTs have found wide application in various signal and image processing tasks, however the problem of improving their fast algorithms remains relevant. In this work we develop fast algorithms for discrete fractional and four-parametric Fourier transforms (FPFT) with minimal computational error. For that, we derive kernels for these transforms using a method of projective decomposition of the discrete Fourier transform operator (DFT). Analysis of computational complexity shows that the complexity of obtained algorithms is comparable to the fast Hartley transform (FHT, ).

 


Full Text:

PDF (Russian)

References


E. U. Condon “Immersion of the Fourier transform in a continuous group of functional transforms”, Proc. Nat. Acad. Sci, 1937, Vol., 12, pp. 158–164.

V. Bargmann “On a Hilbert space of analytic functions and an associated integral transform. Part 1”, Commun. Pure Appl. Math., 1961, 14, pp.187–214.

V. Namias “The fractional order Fourier transform and its application to quatum mechanics”, J. Inst. Math. Appl., 1980, Vol. 25, pp. 241–265.

H. M. Ozaktas. and D. Mendlovic “Fourier transform of fractional order and their optical interpretation”, Opt. Commun., 1993, 110, pp. 163–169.

H. M. Ozaktas, M. A. Kutay, and D. Mendlovic, “Introduction to the fractional Fourier transform and its applications”, Advances in Imaging Electronics and Physics. New York: Academic, 1999, ch. 4.

H. M. Ozaktas, B. Barshan, D. Mendlovic, and L. Onural, “Convolution, filtering, and multiplexing in fractional Fourier domains and their relation to chirp and wavelet transforms,” J. Opt. Soc. Amer. A., vol. 11, pp. 547–559, 1994.

B. W. Dickinson and K. Steiglitz. “Eigenvectors and functions of the discrete Fourier transform” IEEE Transactions on Acoustics, Speech and Signal Processing, vol 30(1), pp. 25-31, 1982.

S. C. Pei and M. H. Yeh, “Improved discrete fractional fourier transform,” Opt. Lett., vol. 22, pp. 1047–1049, 1997.

S. C. Pei, C. C. Tseng, M. H. Yeh, and J. J. Shyu, “Discrete fractional Hartley and Fourier transforms,” IEEE Trans. Circuits Syst. II, vol. 45, pp. 665–675, 1998.

A. Bultheel, and H. Martinez, “Computation of the Fractional Fourier Transform, preprint”.

E. Labunets, V. Labunets, “Fast fractional Fourier transforms”, Proc. of Eusipco-98, Rhodes, Greece, 8–11 Sept. 1998, pp. 1757–1760.

E. Ostheimer, V. Labunets, and S. Martyugin “Fast Infinitesimal Fourier Transform for Signal and Image Processing via Multiparametric and Fractional Fourier Transforms”, Supplementary Proceedings of the 4th International Conference on Analysis of Images, Social Networks and Texts (AIST'2015), pp. 19-27.

L. Chen, D. Zhao “Application of fractional Fourier transform on spatial filtering”, Optik 117, pp. 107–110, 2006

M. F. Erden, M. A. Kutay, H. M. Ozaktas, “Applications of the fractional Fourier transform to filtering, estimation and restoration” Proceedings of the IEEE-EURASIP Workshop on Nonlinear Signal and Image Processing (NSIP’99), Antalya, Turkey, June 20–23, 1999, pp. 481–485.

C. Vijaya, J. S. Bhat, “Signal compression using discrete fractional Fourier transform and set partitioning in hierarchical tree”, Signal Processing 86 (8) pp. 1976–1983, 2006.

A. W. Lohmann, Z. Zalevsky, D. Mendlovic, “Synthesis of pattern recognition filters for fractional Fourier processing”, Optics Communications 128 (4–6) pp. 199–204, 1996.

F. Hong-Yi, F. Yue, “Fractional Fourier transfromation for quantum mechanical wave functions studied by virtue IWOP technique” Commun. Theor. Phys. (Beijing, China) 39 pp 417-420, 2003.

B. Barshan, B. Ayrulu, “Fractional Fourier transform pre-processing for neural networks and its application to object recognition”, Neural Networks 15 (1) (2002) 131–140.

X. WU, R. TAO, D. HONG, Y. WANG, “The FrFT convolutional face: toward robust face recognition using the fractional Fourier transform and convolutional neural networks”, SCIENCE CHINA Information Sciences, Volume 63, Issue 1: 119103 (2020)

F. Şahinuç, A. Koç, “Fractional Fourier Transform Meets Transformer Encoder”, IEEE Signal Processing Letters, Vol 29, pp. 2258–2262, 2022

S. Ervin, D. Igor, S. Ljubisa, “Fractional Fourier Transform as a Signal Processing Tool: An Overview of Recent Developments”, Signal Processing 91 (2011) pp. 1351 – 1369.

H. M. Ozaktas, O. Arıkan, M. A. Kutay, and G. Bozdagi, “Digital computation of the fractional Fourier transform,” IEEE Trans. Signal Processing, vol. 44, pp. 2141–2150, Sept. 1996.

C. Candan “The Discrete Fractional Fourier Transform”, M.S. thesis, Bilkent Univ., Ankara, Turkey, (1998).

F. A. Grunbaum, “The eigenvectors of the discrete Fourier transform: A version of the Hermite functions”, J. Math. Anal. Appl. 88(2) (1982) pp. 355–363.

A. Serbes, L. Durak-Ata, “The discrete fractional Fourier transform based on the DFT matrix”, Signal Processing 91 (2011) 571–581.

M. Bespalov, “Spectral decomposition of the discrete Fourier operator”, Available: http://dha.spb.ru/PDF/DFTSpectrum.pdf.

D. Knuth, “The Art of Computer Programming. Vol. 1: Fundamental Algorithms (3rd ed.)”, p. 139.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162