Skip to content

Fast implementation of the multi-dimensional fractional Fourier transform in Python

License

Notifications You must be signed in to change notification settings

siddharth-maddali/frft

Repository files navigation

frft: Multi-dimensional fractional Fourier transform in Python

CHANGELOG

May 24 2022

Created GPU implementation with PyTorch. To use the GPU module like the CPU module, the following changes need to be made.
- Module import: python import frft_gpu as frft - Conversion of the input array from fftshifted numpy array to fftshifted PyTorch array. See tutorial for details.

Measured the runtimes in the tutorial more accurately.

Introduction

The fractional Fourier transform (FRFT) is a valuable signal processing tool used in optics, physics, and radar engineering. It generalizes the familiar Fourier transform into real/reciprocal phase space as a partial rotation between these two spaces. Signal information represented in the fractional Fourier space can sometimes be far more illuminating than the Fourier transform.

Numerical convention

The definition of the one-dimensional FRFT for a parameter $\alpha \in \mathbb{R}$ can be found in Wikipedia. In our convention, $\alpha = 1$ indicates a quarter of the cycle of repetition, corresponding to a phase space 'rotation' of $\pi/2$ or $90^\circ$. Thus, the periodicity in $\alpha$ is $4$.

Implementation

The code uses Numpy's native fftn routine and therefore can be used for transforms of any dimensionality. This implementation follows the theory described in Ozaktas et al. \cite{Ozaktas1996}. It computes the FRFT as the chirp-modulated signal convolved with a chirp function, followed by a final chirp modulation. The chirp function (i.e., a parabolic phase) resides as an array within the namespace of the imported module. It is recalculated whenever the dimensions of the input array change. 1-D, 2-D and 3-D example data is provided as an HDF5 file data.hdf5.

Caveats

  1. Currently does not preserve signal norm. This has to be done manually. Will soon add a normalization parameter, similar to norm="ortho" in numpy.fftn.
  2. Currently selective transforms along user-defined dimensions are not implemented; transforms along all dimensions of the input array by default.

Tutorial

Here is a basic tutorial.

In these tutorials, the FRFT will be simulated in the range $\alpha \in [0, 2]$. This corresponds to the original signal ($\alpha = 0$) through to its Fourier transform ($\alpha = 1$), and ending with the inverted signal ($\alpha = 2$).

Acknowledgements

  • Dr. Ishwor Poudyal (Argonne National Laboratory) for generating the example data.

References

(Ozaktas, Arikan et al., 1996) H.M. Ozaktas, O. Arikan, M.A. Kutay and G. Bozdagt, Digital computation of the fractional Fourier transform, IEEE Transactions on signal processing, vol. 44, number 9, pp. 2141--2150, 1996.