Tag Archives: dsp

A roman inspiration for the Discrete Fourier Transform

CAesAR

Divide et impera (in english, divide and rule): that was one of the main foundations of the political, military and economic strategy of the expansionist Roman Empire. The roman ambition was too big to be achieved without division. They realized that the sum of necessary efforts to perform each part of a divided task may be less than one needed to perform the same task without dividing it.

Playing with algebraic notation without any mathematical or conceptual formalism: if a task that demands an effort T to be performed could be divided in n subtasks, each one with its respective T_i performing efforts, it is intuitive to consider that T_1+T_2+...+T_n=T. Instead, the roman experience establishes the opposite: T_1+T_2+...+T_n<T!

In mathematics and computer science, this “roman insight” is called Divide and Conquer Algorithm: a logical maneuver that breaks a big problem in many little others to (among other benefits) reduce its overall computational complexity. There are many applications of it, but my preferred is the Cooley-Tukey algorithm to process a DFT (Discrete Fourier Transform), most known as the Fast Fourier Transform. A really simple subtlety (breaking the problem into subproblems recursively) makes the problem much easier.

A classical result is to compute the DFT of a sequence with N=2^n elements, N^2 complex multiplications are needed by the original DFT algorithm. If we the Cooley-Tukey algorithm instead, only N \log_2 N multiplications have to be done. Don’t you see big difference? Imagine that you have to process a tiny signal with 1024 samples:

  • Original DFT algorithm: 2^{20} complex multiplications
  • Cooley-Tukey algorithm: 10 \cdot 2^{10}

In this example the FFT, also called as 2-radix FFT (because the sequence is broken recursively in 2 others) is 102.4 faster than the original. If N increases, the difference will be much more than this. What would be the Digital Signal Processing without such subtleties? So, let us divide to conquer.

Ave Cooley and ave Tukey!

Advertisements