AcademicFFT

A Java class to perform Fourier-related operations on discrete sequences, images, and volumes.

Philippe Thévenaz, Biomedical Imaging Group, Swiss Federal Institute of Technology Lausanne

Figure 1. Top: (898 x 81) grayscale image of a tree core. Middle: log-amplitude of its discrete Fourier transform. Bottom: color-coded phase of its discrete Fourier transform.

General Description

This Java class contains methods to perform forward and backward discrete Fourier transforms and to perform Fourier-based circular convolutions. The data live in dimension one (sequences), two (images), or three (volumes). They are stored as linear arrays of float or double. Complex numbers are viewed either as a (real, imaginary) pair, or as an (amplitude, phase) pair. Optimized methods that handle purely real data are provided, too.

Contrarily to several other Fourier packages currently available, the data manipulated by AcademicFFT are not interleaved. Instead, independent arrays are used to store real, imaginary, amplitude, and phase data. This greatly facilitates interactions with software components dedicated to the further manipulation of Fourier data, typically, those specialized in representation and plotting.

The algorithms deployed by this class are standard versions of the fast Fourier transform (FFT). They include mixed-radix, split-radix, coprime, and Rader decompositions, among others. They are able to handle arbitrary data lengths, memory permitting. Behind the scenes, a stage of planification is first performed to determine which combination of approaches is optimal for the current data length. This planification is performed once only; its outcome is stored for future calls, until the time comes when the class is unloaded from memory. Consequently, the very first call to an instance of an AcademicFFT object is slower than subsequent calls to the same instance.

AcademicFFT is standalone; no external library is required. It is also entirely free. No copyright applies.

I. Download

This distribution is dated May 31, 2014. It includes the complete set of source files, along with the documentation.

• compressed jar file [68,486 bytes]
• source file [622,591 bytes]

II. User Manual

Consider a periodic space-domain sequence. It is convenient to describe it over a single period, starting at the origin, like
(1)    
Then, its discrete Fourier transform is defined as
(2)    
This discrete Fourier transform is periodic, too, of same period. Various researchers have adopted various conventions to retain a single period out of these infinitely many samples. Here, we consider the Fourier representation
(3)    
Then, the inverse discrete Fourier transform is
(4)    

Here are a few basic definitions.

• Imaginary unit:
• Unit impulse:
• Dirac distribution:

Here are a few basic relations featuring the discrete Fourier transform.

• Periodicity:
• Linearity:
• Duality (Fourier of Fourier):
• Duality (Inverse Fourier of inverse Fourier):
• Conjugates:
• Parseval:
• Hermitian symmetry (real data):
• Separate real and imaginary:
• Circular integer translation:
• Circular fractional translation:
• Harmonic modulation:
• Circular spatial convolution:
• Spatial multiplication:
• Reflection:
• Spatial up-sampling:
• Fourier up-sampling:
• Spatial padding: with
• Fourier padding (even length): with
• Fourier padding (odd length): with
• Relation to the discrete-time Fourier transform (even length): with
• Relation to the discrete-time Fourier transform (odd length): with
• Relation to the Fourier series (even length): with
• Relation to the Fourier series (odd length): with

Here are the discrete Fourier transforms of a few particular sequences.

• Constant-valued spatial data:
• Constant-valued Fourier:

III. Conditions of Use

EPFL makes no warranties of any kind on this software and shall in no event be liable for damages of any kind in connection with the use and exploitation of this technology.