O metodzie konstrukcji liczb binarnie odwrotnych i jej zastosowaniu w szybkiej transformacji Fouriera

• Autorzy: Jerzy Albrycht , Maciej Wygralak
• Języki publikacji: PL

Abstrakty

Wyliczanie dyskretnych transformat Fouriera bezpośrednio z wzorów analitycznych jest w praktyce (nawet z pomocą maszyny cyfrowej) metodą bardzo uciążliwą i czasochłonną. Wielokrotną redukcję czasu obliczeń komputerowych można uzyskać, korzystając z algorytmów szybkiej transformacji Fouriera - FFT. Celem uzyskania spójności pracy, w rozdziale pierwszym przedstawiono podstawy teoretyczne metod FFT - ze szczególnym uwzględnieniem algorytmu Cooley'a-Tukey'a. Istotnym elementem owego algorytmu jest procedura odwracania porządku wartości bitów reprezentujących pewną liczbę naturalną - wskaźnik tablicy. Znane dotychczas, efektywne rozwiązania powyższego problemu wymagały operowania na pojedynczych bitach słowa maszynowego, bądź korzystały z innych przesłanek teoretycznych. Wszystkie jednak charakteryzowały się relatywnie dużą złożonością metody lub też nastręczały szeregu trudności przy próbach ich implementacji w szerszych klasach języków programowania. Niedogodności tych pozbawiony jest prosty, oryginalny algorytm, oparty na formule (2.3), a przedstawiony w rozdziale drugim niniejszej pracy. Podobnie do metod Singletona, nie odwołuje się on do binarnej struktury liczby. Jest od nich nieco szybszy i znacznie prostszy w swej konstrukcji. Rozdziały trzeci i czwarty zawierają kolejno opis procedury (w języku ALGOL ICL 1900) bazującej na wzorze (2.3) oraz ocenę jej efektywności, jak i nawiązanie do wyników Singletona. (fragment tekstu)

Słowa kluczowe

PL

Funkcje matematyczne; Algorytmy; Matematyka; Transformacja Fouriera

EN

Mathematical functions; Algorithms; Mathematics; Fourier Transform

• Czasopismo: Zeszyty Naukowe. Seria 1 / Akademia Ekonomiczna w Poznaniu
• Rocznik: 1981
• Numer: nr 94 Prace Instytutu Cybernetyki Ekonomicznej
• Strony: 10--16

Twórcy

autor

Jerzy Albrycht

autor

Maciej Wygralak

Bibliografia

• Gentleman W.M., Sande G.: Fast Fourier Transforms for Fun and Profit, AFIPS Conf. Proc. 29, 563-578.
• McCowan D.W.: Finite Fourier Transform Theory and its Appl., Research Depart. Techn. Memorandum, No 8, 1966.
• Otnes R.K., Enochson L., Digital Time Series Analysis, Dumont and Co, Paris 1978, 159-188.
• Singleton R.S.: Algorithm 338, 339, Comm. ACM, vol.11, 1968.
• Singleton R.S.; Algorithm 345, Comm. ACM, vol. 12, 1969.
• Stoer J.: Einfuehrung in die numerische Mathematik I, Springer Verlag 1978, 63-82.