Mam problem ze zrozumieniem istoty szybkości algorytmu FFT.
Moje wątpliwości opisałem tutaj:
http://matematyka.pl/219308.htm

Proszę o wytłumaczenie, najlepiej w odniesieniu do przykładu dla n=8.

do góry

Am 10.11.2010 14:22, schrieb pbartosz:
> Mam problem ze zrozumieniem istoty szybkości algorytmu FFT.
> Moje wątpliwości opisałem tutaj:
> http://matematyka.pl/219308.htm
>
> Proszę o wytłumaczenie, najlepiej w odniesieniu do przykładu dla n=8.


Tu masz to ładnie opisane:
http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FF
T_algorithm

Waldek

do góry

Użytkownik "pbartosz" <b...@g...com> napisał
>Mam problem ze zrozumieniem istoty szybkości algorytmu FFT.
>Moje wątpliwości opisałem tutaj:
>http://matematyka.pl/219308.htm
>Proszę o wytłumaczenie, najlepiej w odniesieniu do przykładu dla
>n=8.

Normalnie, tzn z najprostszej definicji DFT, jakbys chcial policzyc
wszystkie 8 skladowych, to w kazdej masz 8 skladnikow sumy,
czyli razem 64 skladniki do wyliczenia i zsumowania.

A tak jak opisales - obliczasz osobno skladniki parzyste i
nieparzyste, razem 8. Dodajesz je do siebie odpowiednio. I wlasnie
odwaliles 1/3 roboty. Bo wystarcza jeszcze dwa podobne kroki i masz
transformate policzona.

Bo jak mozesz zauwazyc - te sumy parzyste i nieparzyste ktore
wymieniles, sa znow bardzo podobnym wzorem zapisane,
i mozna je obliczac w analogiczny sposob.

Razem odpowiednio sprytny algorytm liczy to jeszcze zgrabniej i
mnozen jest ciut mniej.

J.

do góry

> Mam problem ze zrozumieniem istoty szybko&#182;ci algorytmu FFT.
> Moje w&#177;tpliwo&#182;ci opisa&#179;em tutaj:
> http://matematyka.pl/219308.htm
>
> Prosz&#234; o wyt&#179;umaczenie, najlepiej w odniesieniu do przyk&#179;adu dla
n=8.

=============

Sądzę , że zarówno Paweł jak i J.F. udzielili Ci wyczerpujących
odpowiedzi/wskazówek. Pozwolę sobie wtrącić swoje "3 grosze".. Jeżeli jesteś
studentem , to z wiadomych powodów (egzamizy/kolokwia) musisz , a nawet
powinieneś zrozumieć na czym to polega. Najważniejszym jest jednak fizyczna
interpretacja transformaty Fouriera. Zarówno w postaci "analogowej" (postać
całkowa) , jak i w postaci "cyfrowej" , skwantowanej kolejnymi próbkami ADC.
Hehe , był tu na grupie kiedyś GENIUSZ , który twierdził , że za pomocą FFT mogę
sobie tylko teoretycznie wzory całkowe "przemielić" , zaś za pomocą DFT można to
zrobić cyfrowo. Baaa , proponował mi nawet podciągnięcie się z DSP , bo spałem
na wykładach... Zakładam , że interpretacja fizyczna DFT jest dla Ciebie
zrozumiała. No więc jeszcze raz... Jeżeli jesteś studentem , "przemiel" temat
w/g wskazówek Pawła i J.F. Jeżeli jesteś młodym , zdobywającym szlify
inżynierem , to nie kombinuj za wiele , tylko skorzystaj z gotowców.. Jeżeli ma
to być zrobione software'owo , skorzystaj z kodów źródłowych , których jest od
cholery w sieci.. Jeżeli ma to być zaszyte w hardware , zarówno Altera jak i
Xilinx dają darmowe core'y. Nie komplikujmy sobie życia !!! Czy ktokolwiek
zastanawia się w jaki sposób kalkulator oblicza wartości funkcji
trygonometrycznych , bądź cyklometrycznych ?? Szereg MacLaurina (??) z jakąś
tam dokładnością ?? Chyba nie LUT (Look-Up-Table) , bo wymagałoby zbyt dużo
pamięci...

I To By Było Na Tyle ,

MH


--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

Ooopss !! Waldka Krzoka nie wiem jakim cudem przemianowałem na "Pawła".
Wybacz !! Nie przejmuj się Waldek , ten błąd jest naprawdę mój .... , naprawdę mój..

MH

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

MH wrote:

> Ooopss !! Waldka Krzoka nie wiem jakim cudem przemianowałem na "Pawła".
> Wybacz !! Nie przejmuj się Waldek , ten błąd jest naprawdę mój .... ,
> naprawdę mój..

Nieważne. Możesz za karę poklęczeć na gotowanym grochu.

Waldek

do góry

> MH wrote:
>
> > Ooopss !! Waldka Krzoka nie wiem jakim cudem przemianowa&#179;em na "Paw&#179;a".
> > Wybacz !! Nie przejmuj si&#234; Waldek , ten b&#179;&#177;d jest naprawd&#234;
mój .... ,
> > naprawd&#234; mój..
>
> Niewa&#191;ne. Mo&#191;esz za kar&#234; pokl&#234;cze&#230; na gotowanym grochu.
>
> Waldek
===========

Proszę !! O łagodniejszy wyrok!!

MH

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

W dniu 10.11.2010 22:16, MH pisze:
> Czy ktokolwiek
> zastanawia się w jaki sposób kalkulator oblicza wartości funkcji
> trygonometrycznych , bądź cyklometrycznych ??
Jak mówią na studiach o szeregach to aż żal się nie zastanowić ;)

> Szereg MacLaurina (??) z jakąś tam dokładnością ??
Za wolno zbieżny. Dr wspominał, że są jakieś specyficzne szeregi dające
dużą precyzję dla sin już po zsumowaniu kilku elementów, ele nie
powiedział dokładnie/nie pamiętam jakie.

> Chyba nie LUT (Look-Up-Table) , bo wymagałoby zbyt dużo
> pamięci...
LUT + interpolacja dają już całkiem niezłe efekty przy małej liczbie
punktów (kilkadziesiąt-kilkaset). Chociaż po prawdzie lepiej zrobić
splajna i trzymać kolejne współczynniki wielomianów zamiast wartości
funkcji.

--
Pozdrawiam
Michoo

do góry

On Nov 10, 2:22 pm, pbartosz <b...@g...com> wrote:
> Mam problem ze zrozumieniem istoty szybkości algorytmu FFT.
> Moje wątpliwości opisałem tutaj:http://matematyka.pl/219308.htm
>
> Proszę o wytłumaczenie, najlepiej w odniesieniu do przykładu dla n=8.

n=8 to akurat kiepski przykład. Dla małych wartości szybciej liczy się
DFT metodą "klasyczną" (korelacyjną).

Ładnie opisane jest tu: http://www.dspguide.com/ch12/2.htm
Istotą szybkości jest to, co zostało przedstawione na rysunku 12-4 i
12-5.

do góry

On Thu, 11 Nov 2010 01:48:44 +0100, Michoo wrote:
>W dniu 10.11.2010 22:16, MH pisze:
>> Czy ktokolwiek
>> zastanawia się w jaki sposób kalkulator oblicza wartości funkcji
>> trygonometrycznych , bądź cyklometrycznych ??
>Jak mówią na studiach o szeregach to aż żal się nie zastanowić ;)
>
>> Szereg MacLaurina (??) z jakąś tam dokładnością ??
>Za wolno zbieżny.

Bardzo dobrze zbiezny. Przynajmniej na potrzeby kalkulatora, ktory
moze to liczyc np sekunde.

>> Chyba nie LUT (Look-Up-Table) , bo wymagałoby zbyt dużo
>> pamięci...
>LUT + interpolacja dają już całkiem niezłe efekty przy małej liczbie
>punktów (kilkadziesiąt-kilkaset).

Tablica co 10 stopni, druga co 1 stopien ale tylko do 9, wzor na sume
sinusow.

Ale mozna nieco inaczej http://en.wikipedia.org/wiki/CORDIC
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.


J.

do góry