Is there a way to extract amplitude information but over 4 phases of the same frequency. That is, if the frequency is known could I extract amplitude peaks (between given values)in the time domain in lots of four, then separate them into "bins" or "arrays" ready for four individual FFTs?

  • $\begingroup$ From what I get out of your question, is it the overlap-add method that you are looking for? $\endgroup$ – DSP Novice Apr 1 at 11:49
  • $\begingroup$ Can you partition a signal in the time domain on whole sets of cycles and do DFTs on each? Absolutely. Is that what you are asking? $\endgroup$ – Cedron Dawg Apr 1 at 11:57

This would be trivial to do as simple decimation where each block increments its samples by $n+4$ with each block starting at sample 0,1,2,3 respectively. This is common with polyphase filter implementation and similar techniques to reduce the overall clock rate requirement for the processing (parallel processing).

For more details on both of those approaches see these posts:

How to implement Polyphase filter?

4-phase FIR LPF in MATLAB

Why does this parallel IIR filter have such a weird form?

Another straightforward and interesting approach specific to DFT processing is to use the Decimation In Time binning that is inherent in the (DIT) FFT algorithm itself.

See the block diagram below for further detail on how an 8 point DFT can be binned in time into 4 2 point DFTs, and specifically how to combine the resulting DFT outputs for any size data block.

FFT Implementation

Expanding this to any general block length of radix 4 length (a length that is a multiple of $2^4$ so that it can be divided into 4 identical blocks. For blocks not in increments of $2^4$ simply pad with zeros to get to this length), the input sequence is binned by two decimation in time operations each with a factor of 2, best demonstrated by example:

Consider a sequence $x[n]$ numbered 0, 1, 2, 3, 4, 5, 6, 7, ...

After one decimation in time by 2 we divide this into two groups, noted here as Group one and Group two:

Group one (even samples): 0, 2, 4, 6, 8, 10 ....

Group two (odd samples): 1, 3, 5, 7, 9, 11 ...

Each of these is then decimated by 2 to form each of the four separate sample blocks, as follows:

Group $x_1[n]$ (even samples of Group 1): 0, 4, 8, 12, ...

Group $x_2[n]$ (odd samples of Group 1): 2, 6, 8, 10, ...

Group $x_3[n]$ (even samples of Group 2): 1, 5, 7, 11, ...

Group $x_4[n]$ (odd samples of Group 2): 3, 7, 11, 13, ...

The reason for binning in this fashion is for the efficient recombining of the DFT results for each block using 2 point DFT "butterflies" as shown in the graphic above and further detailed below.

The four DFT results are combined to be equal to the DFT of the whole sequence as follows:

Given each $N/4$ length DFT result of the four groups as $X_1[k]$, $X_2[k]$, $X_3[k]$, and $X_4[k]$, where k is the integers from $0$ to $N/4-1$ representing the $N/4$ samples in each group:

Combine $X_1$ with $X_2$ to form a $N/2$ length DFT of the combined result. $k$ is incremented from $0$ to $N/2-1$ and due to the cyclical nature of the DFT, $X_1[N/4]=X_1[0]$, $X_1[N/4+1]=X_1[1]$ etc
$$X_{1,2}[k] = X_1[k]+ W_{N/2}^{k/2} X_2[k]$$

Similarly combine $X_3$ with $X_4$ to form a $N/2$ length DFT of the combined result.

$$X_{3,4}[k] = X_3[k]+ W_{N/2}^{k/2} X_4[k]$$

Finally combine the two resulting $N/2$ length DFT's to have the full $N$ length DFT result, here k is incremented from $0$ to $N-1$:

$$X[k] = X_{1,2}[k]+ W_{N}^{k} X_{3,4}[k]$$

The notation above $W_n^k$ are the "roots of unity", coined as "Twiddle Factors" by W.M Gentleman and G. Sande in their 1966 paper "Fast Fourier Transform - for fun and profit". The twiddle factors are simply convenient shorthand for the exponential expression below and represent phase rotations:

$$ W_N^k = e^{j2\pi/N}$$

Below shows a graphic example for N = 8

twiddle factors

| improve this answer | |

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.