Fast Fourier Transform (FFT) Forward, Reverse, 1D and 2D

[Dzandaa]

Hi,

This is a FFT and Complex units I wrote for demonstration purpose.

Included Test for 1D and 2D arrays
Buffers must be exponent of 2

For 1D FTT, there are also some Windows Filters like Hamming, Hanning, etc...
For 2D FTT, image must be square and exponent of 2 for size.

You cant select lower and higher frequencies to change the result.

Tested on Windows 10 and Linux Mint 20.2

B->

[Thaddy]

Why didn't you use the standard fpc supplied uComplex unit?
The ComplexU unit seems to me like a reinvented wheel.

[Dzandaa]

Hi,

@Thaddy:

Why didn't you use the standard fpc supplied uComplex unit?
The ComplexU unit seems to me like a reinvented wheel.

Just for the fun and learning Pascal.

B->

[ackarwow]

Hi @Dzandaa

Good job! Impressive...

[marcov]

Is this correct for non power of 2 samplesizes, and what is the advantage over the standard FFT unit by Nils Haeck ?

[Paolo]

Just for the fun and learning Pascal

+1

[tetrastes]

standard FFT unit by Nils Haeck ?

Where can I find it?

[Dzandaa]

Hi,

Is this correct for non power of 2 samplesizes, and what is the advantage over the standard FFT unit by Nils Haeck ?

@marcov:

Non, it's just for power of 2.

It is the simplest FFT, just to show what an FFT can do with filtering.

Just Need BGRABitmap for 2D FFT and Industrial stuff for both 1D and 2D.

And I don't know the FFT by Nils Haeck.

B->

[Thaddy]

standard FFT unit by Nils Haeck ?

Where can I find it?

Yes, where?
(Interested because I added a very simple fft implementation to a different forum entry last week. The smallest I could come up with and reasonably usable, especially for audio fft's for display use)

[marcov]

Afaik the original site is no longer there (same author as nativejpg). But a bit googling it is easy to find:

https://github.com/neurolabusc/MRIcron/blob/master/niftiview7/FFTs.pas and other fft* files.

I have a slightly different version myself, that was modified once, but I don't know if they are that important.   (my main code typically has 200*2^n samples)

I also spent quite some time in trying to accelerate it with avx, but while all individual routines where several times faster, overall it was not. Probably something frustrates the micro-op cache or so, it will have to wait till I can inline it, e.g. when avx intrinsics become available.

If somebody knows the butterfly diagram for number 20 (specially what to do extra to merge two number 10 diagrams)

[VTwin]

For the record, DMath (and LMath) contain fft routines. I have not used them in years, but they worked well for me at the time. I can not comment on how they compare to this implementation.

https://wiki.lazarus.freepascal.org/DMath