Podział w FFT

Question

Cześć!

Mam problem z takim zadaniem:

Ile podziałów punktów na grupy zostanie dokonanych w metodzie FFT dla 16 punktów?

Moim zdaniem mogą to być 2 podziały, jednak nie jestem pewien :/

Comments

Nie bardzo rozumiem twoja terminologie wiec nie wiem, czy dobrze odpowiadam. W 16-punktowej FFT masz 4 przebiegi obliczeń motylkowych, każdy na innych parach elementów. Najpierw skok o połowę czyli o 8:

0-8, 1-9, 2-10 ..., 7-15,

potem skok o 4:

0-4, 1-5, 2-6, 3 -7, 8-12, 9-13 ... ,

potem skok o 2

0-2, 1-3, 4-6, 5-7, ...

a na końcu obliczenia parami sąsiadujących elementów

0-1, 2-3, 4-5, 6-7 ...

 

Znazłem fajny dokument:

Algorytm FFT

Answer 1

masz duży problem, bo nad tym algorytmem pracowało 2 osoby na podstawie notatek Gaussa. Tego co wiem to jest gotowy algorytm do którego tylko się podstawia dane tablicowe lub wpisuje się w specjalnie spreparowaną macierz.

Nie wiem skąd masz teorie najprawdopodobniej z Wikipedii (nie musi być prawdziwa). Jedynym słusznym sprawdzeniem twojego algorytmu jest DFT dla pojedynczej wartości.

Algorytm można zdobyć za darmo, jednak jego licencja jest wątpiła, znajduje się w źródłach do programu LameMP3.