# How do you get FFT for negative $k$ values?

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$$.

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

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]$$.