Jean-Paul CIPRIA


Algorithmics 03 – Signal by Fourier Transforms- FFT – 3

Written By: Jean-Paul Cipria - Mai• 10•17


FFT - Only One Partition - ©J.P. Cipria 2017.

FFT – Only One Partition – Execution Times Comparison – ©J.P. Cipria 2017.

How do a Fast Fourier Transform by Cooley and Tukey Algorithms ? Why High Potential with a high level QI don’t understand official physics memorization ? The answer is in the question : nobody ask you to … understand ! Then let’s read the original engineers experts ! Come Back to … 1964.

It is a simple demonstration in thesis annexis. Here is a resume. (Not so clear to read for you. We know it)


Created :2017-05-10 13:08:46. – Modified : 2018-04-14 19:14:44.

Difficult ! Master Level.

Difficult ! Master Level.

26 views on 10/05/17.
37 : 12/05/17

<strong><span style="color: #ff0000;">Expériences En Construction</span></strong>

Experiment in Progress.

How do evaluate number of FFT Calculations Efficiency ?

Cooley and Tukey Number of Calculations Evaluation

If we perform a Fourier Transform from the original document [COOLEY-TUKEY-1964] we take all N decomposition terms A(k) then we multiply each k order term by exponential exp(2.i.\pi.\frac{k.j}{N}) . We get a « frequential » X(j) term.

We changed notation to X(k) time and F(n) frequency signals to match with engineer’s needs and … then we change also sign and recalibrate to \frac{1}{\pi.N}exp(-2.i.\pi.\frac{k.n}{N}) for energy conservation !!!

That’s all folks ?

"What's Up, Doc" Bugs Bunny- ©J.P. Cipria - 15/04/2017

« What’s Up, Doc ? »  ©J.P. Cipria.

Of Course … Not !

Let’s read the original document [COOLEY-TUKEY-1964] : We decompose A signal with k index on any base, for example r_1 as well as the X(j) results we decompose it on any base r_2 so that we have N=r1*r2 . One of a trick is using log_{r_1} or log_{r_2} to symplify equations. After many times, more complicated than difficult, we estimate the r/log(r) ratio when r_1=r_2 . The smallest is it the more efficient for the number of calculations we got.

See one of demonstration [CIPRIA-2017] or the original. The result is :

  • 2 ==> 2
  • 3 (Let’s read e=2.718) ==> 1.88
  • 4 ==> 2
  • 5 ==> 2.15

The more efficient base is 3 as integer or e=2.718 in the continuous domain. Then 3 is the closer integer. The more adapted for calculator is 2. If we use QAM (4), old wireless transmission example (« air interface »), we should perform directly in 4 base more than 2 base !

We traduct C. T . here to avoid some bad interpretation

  • r is the calculation base we search for.
  • RealCalculationNumber=N.log(N).\frac{r}{log(r)}
  • N is a constant then N.log(N)=C^{te} is also a constant for r fixed.
  • RealCalculationNumber=C^{te}.\frac{r}{log(r)}

Key Resume

  • Fast Fourier Transform (FFT).
  • Cooley–Tukey FFT Algorithm (FTTCT).
  • Discrete Fourier Transform (DFT).

Let’s try to find the r right base with Matlab

In the following picture [CIPRIA-2017] we search r as a possible base to made calculations. We need to know if 10 base, 16 hexadecimal base or other is the more efficient to tend from N^2 calculations to a PROPORTIONAL limit to N.log_2(N) .

Cooley Tukey Efficiency - ©J.P. Cipria 2017.

Cooley Tukey Efficiency – r is the search Base the More Efficient Calculations Rate – ©J.P. Cipria 2017.

Why is r = 2.718 = e the best efficiency for a calculation base ?

Cooley and Tukey didn’t answer this question but we need to understand to … anticipate. It is the aim of physics and sciences !

OR, very simple ? 😉 We decompose all X(k) on a e^{-2i\pi.k.n} objects when we do a Fourier Transform. Those objects are perpendicular when k change. This decomposition permits to retreive all F(n) possible in the frequencies domain. Then e^{-2i\pi.k.n} objects form a mathematical base with dimension … ? r=e=2.718. CQFD.

OR, with other words, if you project X(k) on other base than 2.718 then the projections are not perpendicular or and then distances increase. CQFD

OR, the derivative function is nul for an extremum :

  • (\frac{r}{log_2(r})^{\prime}=(1-log(r))/log(r)^2 =0 ==> r=e=2.718 CQFD

Do we Play it with Matlab ?

Let’s try three different algorithms

Let’s try input signal with two frequencies :

  • X(k) = sin(w1*k/N) + sin(w2*k/N)

Let’s try Normal Fourier Transform :

  • F(n)=\sum\limits_{k=0}^{N-1} X(k)*exp(-2i\pi\frac{k.n}{N})

Let’s try Matlab FFT :

  • F(n) =fft(X,N)

Let’s try FFT with Only One Partition :

We just separate in two blocks all the N X(k) samples. Then we do calculation twice with N/2 .

  • F(n)=\sum\limits_{k=0}^{N/2-1}Pair(X)+exp(-2i\pi.n/(N)).Impair(X)+\sum\limits_{k=N/2}^{N-1}Pair(X)-exp(-2i\pi.n/(N)).Impair(X)
  • A simple prove is on Wikipedia English. Students can follow the demonstration on the first order or read Cooley and Tukey [COOLEY-TUKEY-1964]. Don’t try French courses you will not understand anything .

CT Algorithm by One Partition Comparisons

FFT - Only One Partition - ©J.P. Cipria 2017.

FFT – Only One Partition – Execution Times Comparison – ©J.P. Cipria 2017.

We divide calculation in only two parts. A duration for a Fourier transform lasted 3.22 seconds against 1.83 seconds for the FFT with one partition. Then the gain is 1.8. We remark Matlab FFT had  lasted 0.0012 seconds.

Double Partition

FFT - Double-Partition - m11 - ©J.P. Cipria 2017.

FFT – Double-Partition – m11 – ©J.P. Cipria 2017.

We divide calculation in only four parts. A duration for a Fourier transform lasted 3.33 seconds against 0.73 seconds for the FFT with two partition. Then the gain is 4.5. We remark Matlab FFT had  lasted 0.0016 seconds.

Rapidity Comparison ?

Cooley and Tukey runs about two more rapidly than normal Fourier Transform (1.7 to 2 when N increase) when you just divide algorithm in two parts with N/2 .
CQFD by Measurements.

The Matlab function follows a \frac{N^2}{log_2(N)} and not a N.log_2(N) . Then when you evaluate Cooley and Tukey you got 2.N.log_2(N) and not N.log_2(N) written on every French and English courses. Why ? You must multiply by 2 because the efficiency coefficient \frac{2}{log_2(2)} is 2 and not 1. (See first paraph).

That’s all , Folks ? Of Course … Not !

Spectral Repliement ?

FFT - Simple and Double Partition Spectral Repetition - ©J.P. Cipria 2017.

FFT – Simple and Double Partition Spectral Repetition – ©J.P. Cipria 2017.




Wikipedia English Items

  • Cooley–Tukey FFT algorithm – Wikipedia.

C Language Programmation


Jean-Paul Cipria

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Anti-Spam Quiz: