DFT function implementation in C

Question

I am working on implementation of BFSK implementation on a DSP processor and am currently simulating it on a LINUX machine using C. I am working on the demodulation function and it involves taking a FFT of the incoming data. For simulation purposes, I have a pre-defined function for DFT which is:

void dft(complex_float* in, complex_float* out, int N, int inv)
{
    int i, j;
    float a, f;
    complex_float s, w;
    f = inv ? 1.0/N : 1.0;
    for (i = 0; i < N; i++) {
        s.re = 0;
        s.im = 0;
        for (j = 0; j < N; j++) {
            a = -2*PI*i*j/N;
        if (inv) a = -a;
        w.re = cos(a);
        w.im = sin(a);
        s.re += in[j].re * w.re - in[j].im * w.im;
        s.im += in[j].im * w.re + in[j].re * w.im;
    }
    out[i].re = s.re*f;
    out[i].im = s.im*f;
}

Here the complex_float is a struct defined as follows:

typedef struct {
 float re;
 float im;
} complex_float;

In the dft() function, the parameter N denotes the number of DFT points.

My doubt is that since the algorithm also involves a frequency hopping sequence, while demodulating the signal, I need to check the amplitude of DFT of the signal at different frequency components.

In MATLAB this was quite simple as the FFT function there involves the sampling frequency as well and I could find the power at any frequency point as

powerat_at_freq = floor((freq * fftLength) / Sampling_freq)

But the C function does not involve any frequencies, so how can I determine the magnitude of the DFT at any particular frequency?

Try posting on [DSP stackexchange](http://dsp.stackexchange.com/) — puffadder, Jun 26 '12 at 12:48
Just a nit: your code is not FFT, it is the O(N^2) direct implementation of a DFT. You might want to check out kissfft.sourceforge.net for a C FFT. — Mark Borgerding, Jun 26 '12 at 13:25
@MarkBorgerding : I am using the DFT function just for code testing , the simulation and implementation is some using a separate compiler which uses different function for computing the FFT of a complex signal... — anshu, Jun 26 '12 at 14:22

score 3 · Answer 1 · edited May 23 '17 at 11:48

3

The index in the FFT table for a particular frequency is calculated as follows:

int i = round(f / fT*N)

where f is the wanted frequency, fT is the sampling frequency and N is the number of FFT points. The FFT should be fine-grained enough (i.e. N should be large) to cover all the frequencies. If the precise frequency isn't present in the FFT, the nearest one will be used. More info about FFT indexes versus frequencies:

How do I obtain the frequencies of each value in an FFT?

edited May 23 '17 at 11:48

Community

1
1

answered Jun 26 '12 at 12:49

Ilmo Euro

4,925
1
27
29

I was also thinking on similar lines (its calculated in MATLAB in the same way). However, I am a bit confused as the `fft()` that I am using doesnt consider the sampling frequency being used. – anshu Jun 26 '12 at 13:00
1

Discrete Fourier transforms by itself are completely frequency-agnostic, they use [normalized frequency](http://en.wikipedia.org/wiki/Normalized_frequency) instead. – Ilmo Euro Jun 26 '12 at 13:07

hotpaw2 · Answer 2 · 2013-08-02T16:21:12.400

1

The frequency represented depends on the sample rate of the data fed to it (divided by the length if the FFT). Thus any DFT or FFT can represent any frequency you want just by feeding it the right amount of data at the right sample rate.

edited Aug 02 '13 at 16:21

answered Jun 26 '12 at 17:50

hotpaw2

70,107
14
90
153

score 0 · Answer 3 · answered Jun 26 '12 at 15:44

0

You can refer to the FFTW library which is famous and useful in the applicational area of FFT.

The official website is: http://www.fftw.org/

By the way, the matlab's FFT function is also implemented through the FFTW library.

answered Jun 26 '12 at 15:44

Terence Xie

185
2
16

FFTW is licensed under the GPL with an option to buy from MIT--good to remember depending on what you're doing. – Brett Jun 27 '12 at 03:11

DFT function implementation in C

3 Answers3