آشنایی با موضوع
تبدیل سریع فوریه (Fast Fourier transform - FFT) نام الگوریتمیست برای انجام تبدیلات مستقیم و معکوس گسستهٔ فوریه به صورتی سریع و بسیار کارآمد. تعداد زیادی الگوریتمهای تبدیل فوریه سریع مجزا وجود دارد که شامل محدوده عظیمی از ریاضیات میشوند: از محاسبات ساده به وسیله اعداد مختلط تا نظریه اعداد. این مقاله چشماندازی است به تکنیکهای موجود و برخی ویژگیهای عمومی آنها. همچنین الگوریتمهای خاص در مقالات دیگری توضیح داده شدهاند. رایجترین الگوریتم تبدیل فوریه سریع الگوریتم کولی-توکی است که یک الگوریتم تقسیم و حل است که به صورت بازگشتی یک مسئله تبدیل فوریه گسسته را به سایز مرکب از N = N۱N۲ میشکند و به مسئله تبدیل فوریه گسسته با اندازههای N۱ و N۲ تبدیل میکند که به O ( n ) {\displaystyle O(n)} O(n) ضرب ریشههای مختلط واحد نیاز دارد و به طور سنتی فاکتورهای دست زدن آرام نام دارند. (جنتلمن و سنده، ۱۹۶۶)
این روش و ایده عمومی تبدیل فوریه سریع در سال ۱۹۶۵ با انتشارات کولی و توکی معروف شد اما بعدها کشف شد که الگوریتم پیشنهادی این دو نفر قبلاً توسط گاوس در سال ۱۸۰۵ به دست آمده بودهاست.
این الگوریتم در هر مرحله مسئله را به دو تکه با اندازه N/۲ تقسیم میکند و بنابراین به اندازه توانی از ۲ محدود است اما میتوان با فاکتورگیری در حالت کلی مورد استفاده قرار گیرد.
دقت و تقریب
تعداد کمی از الگوریتمهای تبدیل سریع فوریه که در اینجا مطرح شد برای محاسبه مقدار تقریبی تبدیل فوریه گسسته بود. این الگوریتمها خطاهایی دارند که به طور قراردادی کوچک هستند و از افزایش بسیار زیاد محاسبات جلوگیری میکنند. چنین الگوریتمهایی سرعت زیاد را با خطای تقریبی بسیار کمی معامله میکنند. به عنوان مثال الگوریتم تبدیل فوریه سریع ادلمن (Edelman) در ۱۹۹۹ موفق شد تا نیازهای ارتباطی برای محاسبات موازی را با کمک روش سریع سازی مالتی پل کمینه نماید.
در این صفحه تعداد 613 مقاله تخصصی درباره تبدیل سریع فوریه که در نشریه های معتبر علمی و پایگاه ساینس دایرکت (Science Direct) منتشر شده، نمایش داده شده است. برخی از این مقالات، پیش تر به زبان فارسی ترجمه شده اند که با مراجعه به هر یک از آنها، می توانید متن کامل مقاله انگلیسی همراه با ترجمه فارسی آن را دریافت فرمایید.
در صورتی که مقاله مورد نظر شما هنوز به فارسی ترجمه نشده باشد، مترجمان با تجربه ما آمادگی دارند آن را در اسرع وقت برای شما ترجمه نمایند.
در صورتی که مقاله مورد نظر شما هنوز به فارسی ترجمه نشده باشد، مترجمان با تجربه ما آمادگی دارند آن را در اسرع وقت برای شما ترجمه نمایند.