1
$\begingroup$

I have an algorithm where I am computing the FFT of a large signal. However, I desire only the even or odd terms of the DFT of the signal, but not both. Currently, I discard these undesired terms. Is there a way by which I may appreciably reduce the runtime complexity when only every other DFT term is desired?

How might I begin to find such an optimization? If it is unclear, I will look for how the larger, encompassing algorithm could be improved, but I'm starting by examining the smallest, most expensive portion before thinking about more fundamental changes to the system.

$\endgroup$
  • $\begingroup$ Can you clarify what you mean by 'odd' or 'even' DFT terms? $\endgroup$ – MBaz May 9 '16 at 16:48
  • $\begingroup$ Very odd question :) Adding to @MBaz, ordering in FFT can be twisted. What kind of gain are you expecting by computing only the half? What is the typical length (exclusively power of two?)? Can you afford online computation, or need FFT on the whole signal? $\endgroup$ – Laurent Duval May 9 '16 at 17:00
  • $\begingroup$ @MBaz @LaurentDuval Thank you for the very prompt responses. By odd or even DFT terms, I wish to indicate the odd or even-ness of the index of the term using the ordering with DC at index zero (even); in particular, the ordering of the typical output of terms given by the built-in fft(v) function in Matlab. I desire this vector decimated by two. I am not experienced in DSP. The signal length is arbitrary, but can be assumed to be a power of two if this is convenient. My interest is academic as intuitively it would seem that it might be computed more cheaply. $\endgroup$ – user20942 May 9 '16 at 21:33
  • $\begingroup$ @Henfre you are right you may compute those samples, in principle, approximately 2 times faster... $\endgroup$ – Fat32 May 9 '16 at 21:52
  • $\begingroup$ @Henfre It looks like you want to do (for example to keep odd indices): S1=fft(s);S=S1(1:2:end) ? You can accomplish that (as Fat32 implies) simply by adjusting your sampling rate and FFT size to locate the DFT bins exactly where you want them. $\endgroup$ – MBaz May 9 '16 at 22:00
2
$\begingroup$

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 $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{term 2k computes 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{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 2 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{adjust the 2nd sum range}}\\ 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 2 sums}}\\ \end{align}

The final form suggest that the required even samples 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]$ whose length is half that of $x[n]$

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

In short the following matlab code gives you the desired even samples of X[k] without computing a full N point DFT (via FFT) of x[n]:

Xe = fft ( x(1:N/2) + x(N/2 + 1 : end), N/2);

Note that because of the addition of those half length signals efficiency will degrade from a simple N/2 point FFT.

The case for the odd indexed samples proceeds similary but results in a more complex form which I would like to summarize in the following Matlab script:

% Let x[n] be the signal of length N
xc = x .* exp(-j*2*pi*[0:N-1]/N) ; % Multiply x[n] with a complex phase term
Xo = fft (xc(1:N/2) + xc(N/2 + 1, N), N/2); % odd indexed samples of X[k]

Due to a complex multiplication before the FFT, in this case of computing odd indices performance is further reduced but still preferable over a direct N point FFT.

The following Matlab excerpt demonstrates both even and odd samples (with odds requiring only half the complex multiplication wrt the above line)

N = 1024;
x = randn(1,N);
X = fft(x,N);       % original DFT of X

Xe = fft( x(1:N/2) + x(N/2 + 1: N) , N/2);                          % Even   samples only from N/2 point FFT
Xo = fft( ( x(1:N/2) - x(N/2+1:N) ).*exp(-j*pi*[0:2:N-2]/N) , N/2); % Odd samples only from N/2 point FFT

figure,stem( abs ( Xe - X(1:2:N)) ); title('Xe - X(1:2:N)');
figure,stem( abs ( Xo - X(2:2:N)) ); title('Xo - X(2:2:N)');

Note the absolute value of the difference. It is neither zero (down to roundoff error), nor too big. But for the purpose of particular computation this "practical" error shall be considered carefully.

$\endgroup$
  • 1
    $\begingroup$ A surprising result (at least to me), but seems correct! $\endgroup$ – MBaz May 9 '16 at 22:48
  • 1
    $\begingroup$ Nice answer! You should update to NTFS. ;-) $\endgroup$ – Peter K. May 10 '16 at 1:46

Your Answer

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