موضوع مقاله: تبدیل فوریه سریع | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تبدیل فوریه سریع | مقدمه: یک تبدیل فوریه سریع تجزیه یک رشته از مقادیر به مؤلفه‌هایی با فرکانس‌های متفاوت است. | ## بخش 1: تبدیل فوریه سریع | این عملیات در بسیاری از رشته‌ها مفید است (ویژگی‌ها و کاربردهای تبدیل فوریه گسسته را مشاهده کنید) اما محاسبه مستقیم آن از تعریف گاهی اوقات در عمل بسیار کند است. تبدیل فوریه سریع یک راه برای محاسبه همان نتایج به‌طور سریع تر است؛ محاسبه تبدیل فوریه گسسته برای n نقطه با استفاده از تعریف عملیات ریاضی نیاز دارد در حالی که تبدیل فوریه سریع می‌تواند همان نتایج را در عملیات، محاسبه نماید. در جایی که n ممکن است در عمل هزاران یا میلیون‌ها باشد، زمان محاسبه در برخی موارد می‌تواند به اندازه چند مرتبه کاهش پیدا کند و بهبود آن در حدود مرتبه‌است. این بهبود عظیم موجب شده تا بسیاری از الگوریتم‌های عملی تبدیل فوریه گسسته را به صورت تبدیل فوریه سریع پیاده‌سازی نمایند؛ بنابراین تبدیل فوریه سریع در محدوده متنوعی از کاربردها از پردازش سیگنال دیجیتال و حل معادلات دیفرانسیل با مشتقات جزئی (پاره‌ای) تا ضرب مقادیر بزرگ صحیح به کار می‌رود. تاریخچه در طول تمامی سده گذشته و به خصوص در طی ۵۰ سال آخر آن صنایع گوناگون و رشته‌های مختلف دانشگاهی را می‌توان ذکر کرد که به واسطه اعمال ایده‌ها و تکنیک‌های گوناگون فوریه به نحو کاملی شکوفا و پررونق شده‌اند. تعریف و سرعت تبدیل فوریه سریع تبدیل فوریه گسسته را محاسبه می‌کند و دقیقاً همان نتایجی را تولید می‌کند که مستقیماً با تعریف تبدیل فوریه گسسته به دست می‌آید تنها تفاوت آن این است که بسیار سریع تر است. اگر اعداد مختلط x۰، ...، xN-1 را در نظر بگیریم تبدیل فوریه گسسته با فرمول زیر تعریف می‌شود: محاسبه مستقیم با این تعریف نیازمند عملیات است در حالی که N خروجی و هر خروجی نیازمند جمع N جمله‌است یک تبدیل فوریه سریع روشی است برای محاسبه همان نتایج در زمان عملیات به‌طور دقیق تر همه الگوریتم‌های شناخته شده تبدیل فوریه سریع نیازمند عملیات هستند (البته از لحاظ فنی O فقط یک باند بالا مشخص می‌کند) درحالی که تاکنون حقیقت ثابت شده‌ای وجود ندارد که پیچیدگی بهتر غیرممکن است. | ## بخش 2: تبدیل فوریه سریع | برای نشان دادن ذخیره یک تبدیل فوریه سریع، می‌توان تعداد ضرب‌ها و جمع‌های مختلط را شمارش نمود. در عمل، کارایی واقعی روی رایانه‌های مدرن با فاکتورهایی غیر از علم حساب می‌باشد و یک موضوع پیچیده‌است اما بهبود کلی از به همچنان باقی است. الگوریتم Cooley–Tukey FFT algorithm رایج‌ترین الگوریتم تبدیل فوریه سریع الگوریتم کولی-توکی است که یک الگوریتم تقسیم و حل است که به صورت بازگشتی یک مسئله تبدیل فوریه گسسته را به سایز مرکب از N = N۱N۲ می‌شکند و به مسئله تبدیل فوریه گسسته با اندازه‌های N۱ و N۲ تبدیل می‌کند که به ضرب ریشه‌های مختلط واحد نیاز دارد و به‌طور سنتی فاکتورهای دست زدن آرام نام دارند. (جنتلمن و سنده، ۱۹۶۶) این روش و ایده عمومی تبدیل فوریه سریع در سال ۱۹۶۵ با انتشارات کولی و توکی معروف شد اما بعدها کشف شد که الگوریتم پیشنهادی این دو نفر قبلاً توسط گاوس در سال ۱۸۰۵ به دست آمده بوده‌است. این الگوریتم در هر مرحله مسئله را به دو تکه با اندازه N/۲ تقسیم می‌کند و بنابراین به اندازه توانی از ۲ محدود است اما می‌توان با فاکتورگیری در حالت کلی مورد استفاده قرار گیرد. یکی از سوالات دیرینه علاقه‌مندان این نظریه اثبات باند کمینه پیچیدگی و شمارش تعداد دقیق عملیات لازم برای تبدیل فوریه سریع است و همچنان این مسئله به صورت باز باقی‌مانده‌است. حتی به صورت دقیق ثابت نشده‌است که تبدیل فوریه گسسته دقیقاً به (یعنی یا بیشتر) مقدار عملیات نیاز دارد؛ حتی برای گزینه‌های ساده با اندازهٔ توانی از ۲. | ## بخش 3: تبدیل فوریه سریع | به‌طور معمول، معمولاً در چنین سوالاتی روی شمارش عملیات‌های ریاضی تمرکز می‌کنیم اگرچه کارایی واقعی روی رایانه‌های امروزی به وسیله بسیاری از فاکتورهای دیگر مانند کش و موازی سازی پردازنده و بهبود آن‌ها استوار است. دقت و تقریب تعداد کمی از الگوریتم‌های تبدیل سریع فوریه که در اینجا مطرح شد برای محاسبه مقدار تقریبی تبدیل فوریه گسسته بود. این الگوریتم‌ها خطاهایی دارند که به‌طور قراردادی کوچک هستند و از افزایش بسیار زیاد محاسبات جلوگیری می‌کنند. به عنوان مثال الگوریتم تبدیل فوریه سریع ادلمن (Edelman) در ۱۹۹۹ موفق شد تا نیازهای ارتباطی برای محاسبات موازی را با کمک روش سریع سازی مالتی پل کمینه نماید. حتی الگوریتم‌های دقیق تبدیل فوریه سریع نیز دارای مقادیری خطا به علت محدود بودن دقت محاسبات ممیز شناور مورد استفاده می‌باشند اما این خطاها عموماً کاملاً کوچک هستند. | ## جمع‌بندی | بیشینه مقدار خطا در خطاهای نسبی برای الگوریتم کولی - توکی است که با میزان خطا برای فرمول تبدیل فوریه گسسته نیوی می‌توان مقایسه نمود.