## Jean-Paul CIPRIA

————— PHYSICS – SPACE – ALGORITHMICS ——-

## Algorithmics 03 – Signal by Fourier Transforms- FFT – 3

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

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.

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

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 ? »  ©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 – 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 – 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.

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.

# References

## Courses

### Wikipedia English Items

• Cooley–Tukey FFT algorithm – Wikipedia.

### C Language Programmation

.

Jean-Paul Cipria
26/06/2015

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.