Calculating the DFT in C++

When you learn about the Fourier transform and what it can show you about a signal, you immediately start thinking about its possible applications. The Fourier transform, however, deals with continuous time signals while, in practice, computers deal with discrete time signals (i.e. a sampled version of the original continuous time signal). When it comes to discrete time signal, you can calculate a discrete Fourier transform to get the frequency content of the signal.

Frequency and time domain representation of a 1 Hz sampled sine wave (sampling frequency is 8 Hz).

Typically, one should use a well known and tested library to perform this calculation for a number of reasons including accuracy and speed. However, it can be useful, for the sake of refreshing or improving one’s coding skills to try and code from scratch the algorithm for calculating the discrete Fourier transform. I decided to go this route to refresh and improve my C++ basic coding skills.

The DFT calculation is often implemented (for the sake of speed and efficiency) through the radix-2 algorithm or other forms of such algorithm. This allows to bring down the computation time to O(N log N) which makes a significant difference with respect to using the definition of the DFT, as N grows larger.

In my simple example, I will implement the definition of the DFT instead, that is, given a sequence of N samples $X$ the following formula is the definition of its DFT:

$$X_{k} = \sum_{n=0}^{N-1}x_{n}e^{-j2\pi k n/N}$$

Along with that, I implemented a lot of auxiliary functions used for printing vectors, saving data and output log information.

Let’s dive into the specifics of the program. The program is made of 2 files dft_main.cpp and dft_module.hpp: dft_main.cpp contains a set of variables that can be edited in order to obtain the desired output.

1. Input signal

As for the input, you can choose to use either a dummy signal (a 1 Hz sinewave) or an external signal which should be contained in a text file and be in the following format:

Header
sample1
sample2
…

Note that you can also have no header, provided that the variable “INPUT_FILE_HAS_HEADER” is set to false. By default it is assumed that the input file has a header. You can choose which input signal to use by changing the value of the variables “USE_EXTERNAL_DATA” and “INPUT_FILE_PATH”.

2. Output signal

If you want the output to be saved to a file, you should provide a path in “OUTPUT_FILE_PATH” and set “SAVE_TO_FILE” equal to true, otherwise the output will be simply printed to the console.

3. Sampling frequency

The sampling frequency can be set in Hz by changing the variable “FS”.

To run the program, simply compile it and then run it. You can use an IDE such as Code::Blocks. Finally, here is the code: