1
$\begingroup$

Is it possible to realize DFT of 6 samples by using 3 DFT2 blocks? For example if had 2 * N samples by one step of decimation in frequency or time is possible to reduce DFT(2N) to 2 * DFT(N). So if we had 2 * DFT(N) blocks we could do it that way. What if we had 3N samples and 3 DFT(N) blocks. In my question N equals 2. How would the structure look and what is formula for X(k) element of spectrum?

The basic problem here is how to find different ways to calculate DFT with given blocks and using only additional sum blocks and multiplying with twiddle factors?

Improve this question
$\endgroup$
  • $\begingroup$ You should define more clearly what you want to do. Also, there's a lot of literature on FFT implementations out there, so what are you basing your question on? $\endgroup$ – Marcus Müller Feb 1 '16 at 11:30
  • $\begingroup$ Ok. This was question from oral exam in DSP course. $\endgroup$ – dumpram Feb 1 '16 at 11:53
  • $\begingroup$ I find it very bad style to ask exam/homework/assignment questions on here without giving the info where they come from, and what background the person asked is expected to have. $\endgroup$ – Marcus Müller Feb 1 '16 at 20:47
  • 1
    $\begingroup$ The structure you came up with is basically equivalent to 3 length-2 DFTs followed by 2 length-3 DFTs. That's what you will always get: if you split $N=N_1\cdot N_2$, you can implement a length-$N$ DFT as $N_1$ length-$N_2$ DFTs followed by $N_2$ length-$N_1$ DFTs. Have a look at this blog post for more details. $\endgroup$ – Matt L. Feb 2 '16 at 8:49
  • $\begingroup$ @MattL. I also consider the edit to not really be part of the question but rather an answer; so I vote to reopen the question, allowing OP to self-answer it, and mark it answered tomorrow. Dumpram, could you still please add a little more background info to the question, and as soon as it is reopened, delete your solution from the question itself and post it as an answer? $\endgroup$ – Marcus Müller Feb 2 '16 at 11:33
5
$\begingroup$

The following is an important paper about FFT algorithms:

Tran-Thong, “Algebraic Formulation of the Fast Fourier Transform,” IEEE Circuits and Systems magazine, vol. 3, no. 2, June 1981, pp. 9-19.

In the above, the author distinguishes 16 basic types of FFT algorithm, characterized by: 1) decimation type (DIT - type T below, or DIF - type F below), 2) input order, 3) output order, and 4) geometry. The author also shows graphs, but they will not be shown here.

Alg.    Input Order Output Order Geometry

T1      bit reverse sequential  in-place
T2      sequential  bit reverse in-place
T3      bit reverse bit reverse same output
T4      sequential  sequential  same output
T5      bit reverse bit reverse same input
T6      sequential  sequential  same input
T7      bit reverse sequential  isogeometric
T8      sequential  bit reverse isogeometric

F1      bit reverse sequential  in-place        
F2      sequential  bit reverse in-place
F3      bit reverse bit reverse same output
F4      sequential  sequential  same output
F5      bit reverse bit reverse same input
F6      sequential  sequential  same input
F7      bit reverse sequential  isogeometric
F8      sequential  bit reverse isogeometric

Although many of the algorithms can be attributed to different authors, as stated in the above paper: "The Cooley-Tukey algorithm and its modifications are DIT algorithms. The Gentleman-Sande algorithms and their modifications are DIF algorithms."

There are many more FFT algorithms other than the ones described above, including higher and mixed radix ones. But they also exhibit similar characteristics. For instance, take a look at the 6 point DIT radix-3/radix-2 graph shown on page 13 in the following reference:

http://www.ece.cmu.edu/~ee791/lectures/L18/FFTstructures.pdf

It is two radix-3 butterflies followed by three radix-2 butterflies. It is bit-reversed input and sequential output.

Of course, given that the FFT can be viewed as a matrix transpose, one can also decompose a 6 point FFT into three radix-2 butterflies, followed by two radix-3 butterflies. You can also have DIT or DIT (or mixed decimation). So you have several options to choose from.

Improve this answer
$\endgroup$
2
$\begingroup$

Ok, I worked out this and i got this for decimation in time:

enter image description here

And here is how structure looks:

enter image description here

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ (comment made after question was edited) Your graph is not an FFT. An FFT relies on minimizing calculations by reusing intermediate results. Compare the total number of operations in your graph to the radix-3/radix-2 FFT shown on p. 13 of the link in my answer, and note the number of unity twiddles in the latter. What you have, in contrast, is a radix-2 stage, followed by a stage of multiply/sum DFT nodes. $\endgroup$ – user14819 Feb 5 '16 at 7:06

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.