Discrete Fourier Transform in Calc

Last week I started implementing a FOURIER() formula for LibreOffice Calc that computes Discrete Fourier Transform [DFT] of a real/complex data sequence. This is a long-time wanted feature in Calc. I’d like to thank Collabora Productivity for a fully funded hack week and lots of encouragement that enabled me to work on this feature.

The implementation is still a work in progress and current syntax of the formula is :

FOURIER(Array, GroupedByColumn, Inverse, Polar)

First argument is the data array range, but there are some restrictions on its shape. If the array is grouped by columns(rows), you need to indicate that by setting the second argument GroupedByColumns = TRUE(FALSE). In this case the array can contain 1 or 2 columns(rows), where the first column(row) contains the real part of input series and second column(row) if present contains the imaginary part of the input series. If there is only 1 column(row), the input series is treated as purely real. If the number of rows(columns) is not a power of 2, zeroes are appended to the input series internally to make the series length equal to the next nearest power of 2.

The third argument “Inverse” is a boolean flag to indicate whether an inverse DFT needs to be computed. This argument is optional and the default value is FALSE.

The fourth argument Polar is a boolean flag to indicate whether the final output needs to be in polar coordinates. This argument is optional and the default value is FALSE.

The result of this formula consists of two columns – first column contains the real parts (or the magnitudes if Polar=TRUE) and second column contains the imaginary parts (or the phases if Polar=TRUE).

Below is a screenshot of a sample usage of FOURIER() formula.

 

fourier-trimmed

The data x[n] column was generated by the formula “=10*COS(2*PI()*COS(2*PI()*A2:A257/128))” (a typical frequency modulation example). Here I wanted to get an Phase-Magnitude spectrum and plot it, so I used “=FOURIER(B2:B257,1,0,1)” (Note that the Polar argument is set to 1).

Implementation

I made a choice to implement a radix-2 decimation-in-time Fast Fourier Transform algorithm from scratch. Of course this would mean the data length should be an even power of 2. But like Gnumeric, my implementation pads zeroes to the data sequence to round the length to the next power of 2. This is something to improve upon in the future. The current implementation is not yet merged to LibreOffice core repository, but is in review @ gerrit. A Fourier analysis tool user-interface is also in the works too.

Advertisements

2 thoughts on “Discrete Fourier Transform in Calc

  1. Pingback: Doing #science using advanced #freesw such as #libreoffice https://… | Dr. Roy Schestowitz (罗伊)
  2. Pingback: QA Report: February 2019 - LibreOffice QA Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s