Tak, FFT wymaga dużo mniej obliczeń (N*log2N) od tradycyjnego dyskretnego DFT (N*N), ale daje identyczny wynik, jest to ta sama operacja matematyczna, ale obliczana różnymi sposobami.
To uzupełnianie zerami, przesuwanie i sumowanie to jest właśnie motylek. Chciałem tylko wyjaśnić, że
motylek to nie transformata DFT, ale widać jeszcze bardziej pogmatwałem. Może spróbuję tak:
Powiedzmy, że masz sygnał abcdefgh, który poddajesz transformacie przez FFT. Czyli musisz rozdzielic sygnał na powiedzmy 4 dwupunkowe.
Całośc wygląda tak:
1. podział na parzyste i nieparzyste (numery próbek!, nie myl z rozkładem parzysto-nieparzystym, bo to całkiem co innego) otrzymujemy: aceg i bdfh
2. kolejny podział na 4 sygnały: ae cg bf dh
3. 2-punktowa transforamta DFT: ae->DFT->AE, cg->DFT->CG itd.
4. Motylki, czyli synteza widma. Łączenie każdych dwóch widm. Tu pokaże o co chodzi z tymi "zerami"
AE i CG mają się stać jednym widmem, tylko jak to zrobić... trzeba podpatrzyc jak to się robi w dziedzinie czasu.
ae i cg mają połączyc sie w aceg czyli trzeba poddac je interploracji i uzupełnic zerami: a0e0 oraz c0g0. Wciąż nie można ich dodac, jeden z nich należy przesunąc: 0c0g, piąta próbka wynosi 0 i nie musimy się nią martwic. Po tych zabiegach można dodac sygnały: a0e0 + 0c0g = aceg. Udało się, ale trzeba zrobic to samo w dziedzinie częstotliwości. Ale jak? Podpatrzymy jak mają wygląda widma tych sygnałów: a0b0->DFT->ABAB, 0c0g->DFT->? uwaga! sygnał jest przesunięty, żeby Cię nie martwic, musisz uwierzyc mi na słowo że takie przesunięcie sygnału w dziedzinie czasu to to samo co pomnożenie widma przez sinusoidę. Czyli nasze widmo będzie wyglądac tak: 0c0g->DFT->C*sin(90) G*sin(270) C*sin(90) G*sin(270). Tak naprawdę trzaba uwzględnic częśc rzeczywistą i urojoną, gdzie sinusoida jest przesunięta o -90 stopni. Widmo urojone dla tego przypadku będzie wynosiło 0000 gdyż wartości sinusoid dla 0 i 180 stopni też są zerowe. No i doszliśmy do rozwiązania a więc AE i CG dają widmo A+C*sin E+G*sin A+C*sin E+G*sin, pod skróceniu A+C E-G A+C E-G. BF i DH łączymy tak samo.
5. dalsza synteza widma, łączenie 2 widm 4 punktowych. Robi się to tak samo jak wyżej, tylko mnoży się już przez 4 wartości sinusoidy (lub kosinusoidy, jak komu wygodniej:) dla części rzeczywistej i 4 wartości przesuniętej sinusoidy dla wartości urojonych.
6. możemy cieszyc się wynikiem 8punktowego szybkiego przekształcenia Fouriera:)
To jest moje rozumowanie, ale spotkałem się z innymi bardziej zagmatwanymi matematyczne.
Dodam, że gdy kiedyś chciałem od początku napisac algorytm FFT to zatrzymałem się na 16 punktach... potem uznałem wyższośc algorytmu Cooleya-Tukeya. Mój był strasznie chaotyczny i mało uniwersalny, a dalsze zwiększanie ilości próbkek było bezcelowe. Ale to było dawno, jeszcze do końca nie wiedziałem co to FFT
Jeśli chcesz mogę wrzucic sprawdzone algrorytmy dla dowolnej 2^N liczby próbek, mam ściągniętego z neta w C, oraz przerobiony na basica, w 100% dobry, zarówno dla liczb zespolonych, jak i zoptymalizowany dla rzeczywistych.
Miałem kiedyś tą książkę o której piszesz, są tam ciekawe przykłady, ale o ile pamiętam autor pisze jak działa FFT, ale już nie tłumaczy. Dokładnie nie pamiętam, wiem tylko że to była moja pierwsza książka o DSP i bardzo się przydała.
Cóż DFT jako zespół filtrów dla każdego prążka... no, można sobie to tak tłumaczyc na początek, łatwiej zrozumiec podstawowe zastosowanie, ale pamiętaj że DFT to przejście z dziedziny czasu do dziedziny częstotliwości, bez utraty informacji o sygnale.