NOWY TEMAT
elektroda NewsGroups Forum Index - Elektronika Polska - Jak działa algorytm FFT dla n=8? Wyjaśnienie szybkości i istoty obliczeń
pbartosz
Guest
Guest
Wed Nov 10, 2010 3:22 pm
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.
Waldemar Krzok
Guest
Guest
Wed Nov 10, 2010 3:22 pm
Am 10.11.2010 14:22, schrieb pbartosz:
Quote:
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.
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_FFT_algorithm
Waldek
J.F.
Guest
Guest
Wed Nov 10, 2010 3:44 pm
Użytkownik "pbartosz" <bartoszpop@gmail.com> napisał
Quote:
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.
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.
MH
Guest
Guest
Wed Nov 10, 2010 10:16 pm
Quote:
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.
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.
=============
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
MH
Guest
Guest
Wed Nov 10, 2010 10:49 pm
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
Waldemar Krzok
Guest
Guest
Wed Nov 10, 2010 11:00 pm
MH wrote:
Quote:
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..
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
MH
Guest
Guest
Wed Nov 10, 2010 11:50 pm
Quote:
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
===========
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
===========
Proszę !! O łagodniejszy wyrok!!
MH
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
Michoo
Guest
Guest
Thu Nov 11, 2010 1:48 am
W dniu 10.11.2010 22:16, MH pisze:
Quote:
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ć
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ć
Quote:
Szereg MacLaurina (??) z jakąś tam dokładnością ??
Za wolno zbieżny. Dr wspominał, że są jakieś specyficzne szeregi dające
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.
Quote:
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
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
J.F.
Guest
Guest
Thu Nov 11, 2010 10:00 am
On Thu, 11 Nov 2010 01:48:44 +0100, Michoo wrote:
Quote:
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.
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.
Quote:
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).
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.
shg
Guest
Guest
Thu Nov 11, 2010 10:27 am
On Nov 10, 2:22 pm, pbartosz <bartosz...@gmail.com> wrote:
Quote:
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.
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.
mk
Guest
Guest
Fri Nov 12, 2010 9:03 pm
W dniu 2010-11-11 10:00, J.F. pisze:
Quote:
Ale mozna nieco inaczej http://en.wikipedia.org/wiki/CORDIC
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
http://www.jacques-laporte.org/TheSecretOfTheAlgorithms.htm
pzdr
mk
J.F.
Guest
Guest
Sat Nov 13, 2010 8:38 pm
On Fri, 12 Nov 2010 21:03:09 +0100, mk wrote:
Quote:
W dniu 2010-11-11 10:00, J.F. pisze:
Ale mozna nieco inaczej http://en.wikipedia.org/wiki/CORDIC
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
Ale mozna nieco inaczej http://en.wikipedia.org/wiki/CORDIC
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
A ja bym taki pewny nie byl. Zuzycie pamieci spore, jak na kalkulator
ktory jej prawie nie ma, zalet nie widac, bo arytmometr dziesietny,
a McLaureen liczy to w 5-6 krokach.
J.
Michoo
Guest
Guest
Sun Nov 14, 2010 12:00 am
W dniu 13.11.2010 20:38, J.F. pisze:
Quote:
On Fri, 12 Nov 2010 21:03:09 +0100, mk wrote:
W dniu 2010-11-11 10:00, J.F. pisze:
Ale mozna nieco inaczej http://en.wikipedia.org/wiki/CORDIC
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
A ja bym taki pewny nie byl. Zuzycie pamieci spore, jak na kalkulator
ktory jej prawie nie ma,
Tablice można wykonać w krzemie - nie wpływają wtedy na ilość dostępnej
W dniu 2010-11-11 10:00, J.F. pisze:
Ale mozna nieco inaczej http://en.wikipedia.org/wiki/CORDIC
Nie obiecuje ze kalkulatory akurat tak licza.
W sumie to McLaurenem prosciej.
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
A ja bym taki pewny nie byl. Zuzycie pamieci spore, jak na kalkulator
ktory jej prawie nie ma,
Tablice można wykonać w krzemie - nie wpływają wtedy na ilość dostępnej
pamięci.
Quote:
zalet nie widac, bo arytmometr dziesietny,
a McLaureen liczy to w 5-6 krokach.
Mam kalkulator TI - ogólnie fajny, ale tak jak
a McLaureen liczy to w 5-6 krokach.
Mam kalkulator TI - ogólnie fajny, ale tak jak
logarytmy/pierwiastki/potęgi liczy dość sprawnie (~700ms) to już funkcje
trygonometryczne to około 2 sekundy - mocno mnie irytowało zwłaszcza
przy fizyce.
Casio kumpla logarytmy liczył koło 1.5sec ale sin/cos w ~0.5sec.
--
Pozdrawiam
Michoo
J.F.
Guest
Guest
Sun Nov 14, 2010 9:26 am
On Sun, 14 Nov 2010 00:00:16 +0100, Michoo wrote:
Quote:
W dniu 13.11.2010 20:38, J.F. pisze:
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
A ja bym taki pewny nie byl. Zuzycie pamieci spore, jak na kalkulator
ktory jej prawie nie ma,
Tablice można wykonać w krzemie - nie wpływają wtedy na ilość dostępnej
pamięci.
W kalkulatorze można śmiało strzelać, że CORDIC (najmniejsze zużycie
zasobów hardwarowych, choć szybkość nie najlepsza, ale niezła, mniej
więcej jeden bit dokładności w jednym kroku algorytmu).
A ja bym taki pewny nie byl. Zuzycie pamieci spore, jak na kalkulator
ktory jej prawie nie ma,
Tablice można wykonać w krzemie - nie wpływają wtedy na ilość dostępnej
pamięci.
No ale trzeba je wykonac. okolo 30 wspolczynnikow to sporo jak na
kalkulator, ktory poza tym ma w ROM tylko liczbe pi :-)
Quote:
zalet nie widac, bo arytmometr dziesietny,
a McLaureen liczy to w 5-6 krokach.
Mam kalkulator TI - ogólnie fajny, ale tak jak
logarytmy/pierwiastki/potęgi liczy dość sprawnie (~700ms) to już funkcje
trygonometryczne to około 2 sekundy - mocno mnie irytowało zwłaszcza
przy fizyce.
Casio kumpla logarytmy liczył koło 1.5sec ale sin/cos w ~0.5sec.
a McLaureen liczy to w 5-6 krokach.
Mam kalkulator TI - ogólnie fajny, ale tak jak
logarytmy/pierwiastki/potęgi liczy dość sprawnie (~700ms) to już funkcje
trygonometryczne to około 2 sekundy - mocno mnie irytowało zwłaszcza
przy fizyce.
Casio kumpla logarytmy liczył koło 1.5sec ale sin/cos w ~0.5sec.
Niestety - nie dojdziemy ktory jak liczy :-)
J.
elektroda NewsGroups Forum Index - Elektronika Polska - Jak działa algorytm FFT dla n=8? Wyjaśnienie szybkości i istoty obliczeń