Skip to main content
1 of 6
Fat32
  • 28.4k
  • 3
  • 24
  • 51

Given a signal $x[n]$ of length N, assume $X[k]$ is its N-point DFT $$X[k] = \sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N}nk}}$$ where $n,k = 0,1,...,N-1$ computed via N-point FFT. And if we wish to compute separateley those even and odd indexed samples of the DFT $X[k]$ we can proceed with the following:

Consider those even indexed samples of $X[k]$ which are denoted as $X_e[k]$ where: \begin{align} X_e[k] = X[2k] &= \sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N}n(2k)}} &\scriptstyle{\text{where 2k computes those even samples of X[k]}}\\ X_e[k] &= \sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N/2}nk}} &\scriptstyle{\text{where the factor 2 is moved into N/2 term}}\\ X_e[k] &= \sum_{n=0}^{\frac{N}{2}-1}{x[n]e^{-j\frac{2\pi}{N/2}nk}} + \sum_{n=\frac{N}{2}}^{N-1}{x[n]e^{-j\frac{2\pi}{N/2}nk}} &\scriptstyle{\text{Divide the sum into two halves}}\\ X_e[k] &= \sum_{n=0}^{\frac{N}{2}-1}{x[n]e^{-j\frac{2\pi}{N/2}nk}} + \sum_{n=0}^{\frac{N}{2}-1}{x[n+\frac{N}{2}]e^{-j\frac{2\pi}{N/2}nk}} &\scriptstyle{\text{where the 2nd sum range is adjusted}}\\ X_e[k] &= \sum_{n=0}^{\frac{N}{2}-1}{ (x[n]+x[n+\frac{N}{2}])e^{-j\frac{2\pi}{N/2}nk}} &\scriptstyle{\text{merge the two sums into one}}\\ \end{align}

The final form suggest that the required even sampled of N-point DFT of signal $x[n]$ can be computed from an N/2 point DFT of a new signal $x_{half}[n]= x[n]+x[n+ N/2]$ which is half the length of $x[n]$.

The signal $x_{half}[n]$ is simply computed by adding the first half of the signal into its second half for N even of course. (if length N of x[n] is not even add a zero to its end to make it even)

In short the following matlab code gives you the desired even samples of X[k]:

Xe = fft ( x[1:N/2] + x[N/2 +1:end], N/2);
Fat32
  • 28.4k
  • 3
  • 24
  • 51