http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/dft.html

http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html

If you are interested in the processing time for such algorithms you might read the answers for "Has anyone tried out and measured the final execution times after rearranging the output data in its initial order?".

Normally the amount of mathematical operations is not so important unless you choose an appropriate processor who is able to perform e.g. 3 operations at the same time and who has a specialised architecture e.g. for reverse carry buffers.

Regards, Marc

I assume you know that the number of butterflies is N/2*log_base2(N).

The number of sums and multiplications in a butterfly is given below.

The equations for a Decimation-in-time radix-2 butterfly are

 P = P + WQ

Q = P – WQ

Where P, Q and W are complex. The equations can be written as

PR + j PI = PR + j PI + (WR + j WI)(QR + j QI)

QR + j QI = PR + j PI - (WR + j WI)(QR + j QI)

PR = PR + (WRQR - WIQI)

PI = PI + (WRQI + WIQR)

and

QR = PR - (WRQR - WIQI)

QI = PI - (WRQI + WIQR)

And we have 4 multiplications:

WRQR,

WIQI,

WRQI,

WIQR.

and 6 sums:

WRQR – WIQI              (1)

WRQI + WIQR              (2)

PR + eqn.1

PI + eqn.2

PR – eqn.1

PI – eqn.2