Fractional Fourier Transform

Definition

While we are already familiar with the Fourier transform, which is defined by the integral of the product of the original function and a kernel function $e^{-2\pi ix\xi}​$:

\[\hat{f}(\xi)=\mathcal{F}[f(x)]=\int_{-\infty}^\infty f(x)e^{-2\pi ix\xi}dx\]

The Fractional Fourier transform has the similar definition:

\[\hat{f}(\xi)=\mathcal{F}^{\alpha}[f(x)]=\int_{-\infty}^\infty K(\xi,x)f(x)dx\]

\[K(\xi,x)=A_\phi \exp[i\pi(x^2\cot\phi-2x\xi\csc\phi+\xi^2\cot\phi)]\]

\[A_\phi=\frac{\exp(-i\pi\ \mathrm{sgn}(\sin\phi)/4+i\phi/2)}{|\sin\phi|^{1/2}}\]

\[\phi=\frac{\alpha\pi}{2}\]

To compute the α-order Fractional Fourier transform of a signal, you can directly compute using frft function:

FractionalTransforms.frftFunction
frft(signal, α)

By entering the signal and the order, we can obtain the Fractional Fourier transform value.

Example

julia> frft([1,2,3], 0.5)
0.2184858049179108 - 0.48050718989735614im
3.1682634817489754 + 0.38301661364477946im
1.3827766087134183 - 1.1551815500981393im
source

Features

The fractional Fourier transform algorithm is $O(N\log N)$ time complexity algorithm.

Relationship with FRST and FRCT

The FRFT can be computed by a smaller transform kernel with the help of the FRCT or the DFRST for the even or odd signal.

Algorithm details

The numerical algorithm can be treated as as follows:

The definition of Fractional Fourier Transform being interpolated using Shannon interpolation, after limit the range, the formulation can be recognized as the convolution of the kernel function and the chirp-modulated function. Then we can use FFT to compute the convolution in $O(N\ \log N)$ time. Finally, process the above output using the chirp modulation.

Acknowledge:

The Fractional Fourier Transform algorithm is taken from Digital computation of the fractional Fourier transform by H.M. Ozaktas; O. Arikan; M.A. Kutay; G. Bozdagt and Jeffrey C. O'Neill for what he has done in DiscreteTFDs.

Value of α

In FractionalTransforms.jl, α is processed as order, while in some books or papers, α would mean angle, which is order*π/2