0
$\begingroup$

I am reading a book (am a programmer so I suck at math) and it states that for a number of $k$-values that are symmetric around 0 (for example $k = -3, -2, -1, 0, 1, 2, 3$), we need to calculate

$$\sum_{j = 0}^{N - 1} x_j e^{-2\pi i kj/N}$$

and the book claims this can be done with FFT.

I know nothing about FFT but Wikipedia tells me that FFT can calculate above sum for $k = 0, ..., N - 1$ in $O(N\log N )$-time.

How does the book then intend to apply FFT to get the values for the $k$ we are interested in here? We want the sum for $k = -3, -2, -1, 0, 1, 2, 3$, but the FFT will calculate them for $k = 0, 1, 2, 3, 4, ..., N - 1$.

$\endgroup$
1
$\begingroup$

There are N possible circular rotations but consistent with what FFTSHIFT in Matlab/Octave provides: Simply map the FFT according to:

For FFT k values before fftshift: 0 to N-1

The samples from 0 to floor((N-1)/2) would map to ceiling((N-1)/2) to N-1

The samples from ceil(N/2) to N-1 would map to -ceiling((N-1)/2) to -1

For example if you have an eight sample FFT (N= 8)

floor((N-1)/2) is floor(7/2) = 3, so the samples from 0 to 3 map to 4 to 7

And the samples from 4 to 7 map to -ceiling(7/2) to -1 or -4 to -1

The samples at index k: 0 1 2 3 4 5 6 7

get mapped to: 4 5 6 7 0 1 2 3

corresponding to the new index -4 -3 -2 -1 0 1 2 3

Similarly when the FFT is odd, for example a nine sample FFT (N= 9)

the samples at index k: 0 1 2 3 4 5 6 7 8

get mapped to: 5 6 7 8 0 1 2 3 4

corresponding to the new index: -4 -3 -2 -1 0 1 2 3 4

$\endgroup$
0
$\begingroup$

The length $N$ discrete Fourier transform (DFT) of a sequence $x[n]$ is given by

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-2\pi j nk/N}\tag{1}$$

where I've used $j=\sqrt{-1}$, as is common in EE/DSP.

It's important to see that $X[k]$ as given by $(1)$ is $N$-periodic in $k$, so you have

$$X[k]=X[k+N]\tag{2}$$

I.e., the values $X[k]$ for negative $k$ or for $k\ge N$ can be obtained by adding or subtracting multiples of $N$ to the index $k$ such that $k$ is in the interval $[0,N-1]$.

Also note that for real-valued $x[n]$ you have the following symmetry:

$$X[k]=X^*[N-k]\tag{3}$$

where $^*$ denotes complex conjugation. So for real-valued $x[n]$, the DFT $X[k]$ for $k<0$ can simply be obtained by conjugating the DFT value for the corresponding positive value of $k$. E.g., $X[-3]=X^*[3]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.