المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

تحويل فوريي السريع

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018)

تحويل فوريي السريع (Fast Fourier Transformation) هي خوارزمية تمكن من حساب قيمة تحويل فوريي المتقطع بسرعة. تعود سرعة هذه الخوارزمية إلى أنها لا تقوم بحساب الأجزاء التي يساوي مجموعها صفرا في تحويل فوريي المتقطع. وتنسب الخوارزمية إلى جيمس كولي James W. Cooley وجون تيوكي John W. Tukey اللذان قاما بنشر الخوارزمية سنة 1965 وذلك بالصيغة المعروفة اليوم، إلا أن العالم الألماني كارل فريدرش غاوس قام بصياغة خوارزمية شبيهة سنة 1805 واستعملها في حساب مجرى المذنبات بالاس وجونو. كما تم تطوير بعض الحالات الخاصة من الخوارزمية قبل اكتشاف توكي لها (من قبل غود سنة 1960).

في الإلكترونيات[عدل]

من التطبيقات العملية المستخدمة كثيرا في الأجهزة الإلكترونية والإتصالات والإذاعة نشير هنا إلى تطبيق عملي لتحليل فورييه السريع، حيث يقوم حاسوب إلكتروني بعملية فصل إشارات الاتصالات المرغوبة عن ترددات مشوشرة ، وهي تستخدم بغرض خفض الضجيج.

تحليل فورييه السريع :

طريقة هامة لخفض الضجيج هي تطبيق تحليل فورييه للإشارات المتراكبة مع تمريرها بمرشح للتردد مفصل لها ثم إعادة تراكبها عن طريق تحويل فورييه. تستخدم الطريقة تحليلا رياضيا ولكن أمكن بواسطة برمجة دوائر إلكترونية لوجيستية التوصل إلى خفض ضجيج أجهزة إلكترونية . ويتم ذلك بواسطة حواسيب رقمية تستطيع أداء ما يسمى تحويل فورييه السريع .

عند استخدام تحليل فورييه تعين جميع التردادت و مطالاتها و أطوارها . يمكن التفريق بين الإشارات المرغوبة وإشارات الضجيج عن طريق معرفة نطاقات أطياف تردداتها . ومن المستحسن معرفة ترددات الضجيج أولا في غياب الإشارات المرغوبة . حينئذ يمكن التأكد من طيف الضجيج (مجموعة ترددات الضجيج ، شكلها ،وتتابعها ، وشدة كل منها ) . وبهذا الطريقة يمكن بعد ذلك فصل طيف ترددات الضجيج من الإشارات المرغوبة .

في المثال العملي التالي سنوضح حالة إشارة مرغوبة "مشوشرة" مما يمكن حدوثها في تقنية الاجهزة الصوتية :

التغير الزمني للإشارة
إشارة مرغوبة يصحبها ضجيج
تحويل للإشاره من تغير زمني إلى تغير ترددي
تحليل تردد إشارة مصحوبة بتردد ضجيج(الرأسي: عدد الترددات، الأفقي:التردد)
← ترشيح →
تحليل ترددات الإشارة المرغوبة
تحليل ترددات الضجيج
أعادة تحويل الإشارة المرشحة من تغير ترددي إلى تغير زمني
الإشارة المرغوبة المرشحة
الضجيج المرشح

| | توضيح تحليل فوريه وإعادة تركيبه بالرسومات المتحركة:

تحويل فورييه من مسار زمني (أحمر) ، إلى مسار ترددي (أزرق). تراكب االترددات (الإشارات) التي يمكن أن يكون منها ترددات ضجيج .

انظر أيضا[عدل]

مراجع[عدل]

  • Ailon، N. (2014). "An n log n Lower Bound for Fourier Transform Computation in the Well Conditioned Model". arXiv/1403.1307. 
  • Brenner، N.؛ Rader، C. (1976). "A New Principle for Fast Fourier Transformation". IEEE Acoustics, Speech & Signal Processing. 24 (3): 264–266. doi:10.1109/TASSP.1976.1162805. 
  • Brigham، E. O. (2002). "The Fast Fourier Transform". New York: Prentice-Hall 
  • Thomas H. Cormen, Charles E. Leiserson, رونالد ريفست, and Clifford Stein, 2001. مقدمة في الخوارزميات (كتاب), 2nd. ed. MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Especially chapter 30, "Polynomials and the FFT."
  • Duhamel، Pierre (1990). "Algorithms meeting the lower bounds on the multiplicative complexity of length- DFTs and their connection with practical algorithms". IEEE Trans. Acoust. Speech. Sig. Proc. 38 (9): 1504–151. doi:10.1109/29.60070. 
  • P. Duhamel and M. Vetterli, 1990, Fast Fourier transforms: a tutorial review and a state of the art, Signal Processing 19: 259–299.
  • A. Edelman, P. McCorquodale, and S. Toledo, 1999, The Future Fast Fourier Transform?, SIAM J. Sci. Computing 20: 1094–1114.
  • D. F. Elliott, & K. R. Rao, 1982, Fast transforms: Algorithms, analyses, applications. New York: Academic Press.
  • Funda Ergün, 1995, Testing multivariate linear functions: Overcoming the generator bottleneck, Proc. 27th ACM Symposium on the Theory of Computing: 407–416.
  • Frigo، M.؛ Johnson، S. G. (2005). "The Design and Implementation of FFTW3" (PDF). Proceedings of the IEEE. 93: 216–231. doi:10.1109/jproc.2004.840301. 
  • كارل فريدريش غاوس, 1866. "Theoria interpolationis methodo nova tractata," Werke band 3, 265–327. Göttingen: Königliche Gesellschaft der Wissenschaften.
  • Gentleman، W. M.؛ Sande، G. (1966). "Fast Fourier transforms—for fun and profit". Proc. AFIPS. 29: 563–578. doi:10.1145/1464291.1464352. 
  • H. Guo and C. S. Burrus, 1996, Fast approximate Fourier transform via wavelets transform, Proc. SPIE Intl. Soc. Opt. Eng. 2825: 250–259.
  • H. Guo, G. A. Sitton, C. S. Burrus, 1994, The Quick Discrete Fourier Transform, Proc. IEEE Conf. Acoust. Speech and Sig. Processing (ICASSP) 3: 445–448.
  • Steve Haynal and Heidi Haynal, "Generating and Searching Families of FFT Algorithms", Journal on Satisfiability, Boolean Modeling and Computation vol. 7, pp. 145–187 (2011).
  • Heideman، M. T.؛ Johnson، D. H.؛ Burrus، C. S. (1984). "Gauss and the history of the fast Fourier transform". IEEE ASSP Magazine. 1 (4): 14–21. doi:10.1109/MASSP.1984.1162257. 
  • Heideman، Michael T.؛ Burrus، C. Sidney (1986). "On the number of multiplications necessary to compute a length- DFT". IEEE Trans. Acoust. Speech. Sig. Proc. 34 (1): 91–95. doi:10.1109/TASSP.1986.1164785. 
  • Johnson، S. G.؛ Frigo، M. (2007). "A modified split-radix FFT with fewer arithmetic operations" (PDF). IEEE Trans. Signal Processing. 55 (1): 111–119. doi:10.1109/tsp.2006.882087. 
  • T. Lundy and J. Van Buskirk, 2007. "A new matrix approach to real FFTs and convolutions of length 2k," Computing 80 (1): 23–45.
  • Kent, Ray D. and Read, Charles (2002). Acoustic Analysis of Speech. ISBN 0-7693-0112-6. Cites Strang, G. (1994)/May–June). Wavelets. American Scientist, 82, 250–255.
  • Morgenstern، Jacques (1973). "Note on a lower bound of the linear complexity of the fast Fourier transform". J. ACM. 20 (2): 305–306. doi:10.1145/321752.321761. 
  • Mohlenkamp، M. J. (1999). "A fast transform for spherical harmonics" (PDF). J. Fourier Anal. Appl. 5 (2–3): 159–184. doi:10.1007/BF01261607. 
  • Nussbaumer، H. J. (1977). "Digital filtering using polynomial transforms". Electronics Lett. 13 (13): 386–387. doi:10.1049/el:19770280. 
  • V. Pan, 1986, The trade-off between the additive complexity and the asyncronicity of linear and bilinear algorithms, Information Proc. Lett. 22: 11–14.
  • Christos H. Papadimitriou, 1979, Optimality of the fast Fourier transform, J. ACM 26: 95–102.
  • D. Potts, G. Steidl, and M. Tasche, 2001. "Fast Fourier transforms for nonequispaced data: A tutorial", in: J.J. Benedetto and P. Ferreira (Eds.), Modern Sampling Theory: Mathematics and Applications (Birkhauser).
  • Press، WH؛ Teukolsky، SA؛ Vetterling، WT؛ Flannery، BP (2007)، "Chapter 12. Fast Fourier Transform"، Numerical Recipes: The Art of Scientific Computing (الطبعة 3rd)، New York: Cambridge University Press، ISBN 978-0-521-88068-8 
  • Rokhlin، Vladimir؛ Tygert، Mark (2006). "Fast algorithms for spherical harmonic expansions". SIAM J. Sci. Computing. 27 (6): 1903–1928. doi:10.1137/050623073. 
  • Schatzman، James C. (1996). "Accuracy of the discrete Fourier transform and the fast Fourier transform". SIAM J. Sci. Comput. 17: 1150–1166. doi:10.1137/s1064827593247023. 
  • Shentov، O. V.؛ Mitra، S. K.؛ Heute، U.؛ Hossen، A. N. (1995). "Subband DFT. I. Definition, interpretations and extensions". Signal Processing. 41 (3): 261–277. doi:10.1016/0165-1684(94)00103-7. 
  • Sorensen، H. V.؛ Jones، D. L.؛ Heideman، M. T.؛ Burrus، C. S. (1987). "Real-valued fast Fourier transform algorithms". IEEE Trans. Acoust. Speech Sig. Processing. 35 (35): 849–863. doi:10.1109/TASSP.1987.1165220.  See also Sorensen، H.؛ Jones، D.؛ Heideman، M.؛ Burrus، C. (1987). "Corrections to "Real-valued fast Fourier transform algorithms"". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (9): 1353–1353. doi:10.1109/TASSP.1987.1165284. 
  • Welch، Peter D. (1969). "A fixed-point fast Fourier transform error analysis". IEEE Trans. Audio Electroacoustics. 17 (2): 151–157. doi:10.1109/TAU.1969.1162035. 
  • Winograd، S. (1978). "On computing the discrete Fourier transform". Math. Computation. 32 (141): 175–199. JSTOR 2006266. doi:10.1090/S0025-5718-1978-0468306-4. 

وصلات خارجية[عدل]