تبدیل سریع فوریه

تبدیل سریع فوریه تابلوی مونا لیزا
تبدیل سریع فوریه (Fast Fourier transform - FFT) نام الگوریتمی‌ست برای انجام تبدیلات مستقیم و معکوس گسسته فوریه به صورتی سریع و بسیار کارآمد. تعداد زیادی الگوریتم‌های تبدیل فوریه سریع مجزا وجود دارد که شامل محدوده عظیمی از ریاضیات می‌شوند: از محاسبات ساده به وسیله اعداد مختلط تا نظریه اعداد. این مقاله چشم‌اندازی است به تکنیک‌های موجود و برخی ویژگی‌های عمومی آن‌ها. همچنین الگوریتم‌های خاص در مقالات دیگری توضیح داده شده‌اند.
یک تبدیل فوریه سریع تجزیه یک رشته از مقادیر به مولفه‌هایی با فرکانس‌های متفاوت است. این عملیات در بسیاری از رشته‌ها مفید است (ویژگی‌ها و کاربردهای تبدیل فوریه گسسته را مشاهده کنید) اما محاسبه مستقیم آن از تعریف گاهی اوقات در عمل بسیار کند است. تبدیل فوریه سریع یک راه برای محاسبه همان نتایج به طور سریع‌تر است؛ محاسبه تبدیل فوریه گسسته برای n نقطه با استفاده از تعریف عملیات ریاضی نیاز دارد در حالی که تبدیل فوریه سریع می‌تواند همان نتایج را در عملیات، محاسبه نماید.
مقایسه تبدیل سریع فوریه و تبدیل فوریه گسسته
این تفاوت در سرعت می‌تواند بسیار چشمگیر باشد، مخصوصا برای مجموعه داده‌های بزرگ. در جایی که n ممکن است در عمل هزاران یا میلیون‌ها باشد، زمان محاسبه در برخی موارد می‌تواند به اندازه چند مرتبه کاهش پیدا کند و بهبود آن در حدود مرتبه‌است. این بهبود عظیم موجب شده تا بسیاری از الگوریتم‌های عملی تبدیل فوریه گسسته را به صورت تبدیل فوریه سریع پیاده‌سازی نمایند؛ بنابراین تبدیل فوریه سریع در محدوده متنوعی از کاربردها از پردازش سیگنال دیجیتال و حل معادلات دیفرانسیل با مشتقات جزئی (پاره‌ای) تا ضرب مقادیر بزرگ صحیح به کار می‌رود.
از تبدیل فوریه سریع به عنوان «مهم‌ترین الگوریتم عددی عصر زندگی ما» یاد می‌شود.
تاریخچه
در طول تمامی سده گذشته و به خصوص در طی ۵۰ سال آخر آن صنایع گوناگون و رشته‌های مختلف دانشگاهی را می‌توان ذکر کرد که به واسطه اعمال ایده‌ها و تکنیک‌های گوناگون فوریه به نحو کاملی شکوفا و پررونق شده‌اند.
تعریف و سرعت
تبدیل فوریه سریع تبدیل فوریه گسسته را محاسبه می‌کند و دقیقا همان نتایجی را تولید می‌کند که مستقیما با تعریف تبدیل فوریه گسسته به دست می‌آید تنها تفاوت آن این است که بسیار سریع‌تر است
اگر اعداد مختلط x ۰ ، …. ، x N-1 را در نظر بگیریم تبدیل فوریه گسسته با فرمول زیر تعریف می‌شود:
X_k = \sum_{n=0^{N-1 x_n e^{-{i 2\pi k \frac{n{N
\qquad
k = 0,\dots,N-1.
f_j = \sum_{k=0^{n-1 x_k e^{-{2\pi i \over n jk
\qquad
j = 0,\dots,n-1.
\begin{array{l
\begin{pmatrix
f_0 \\
f_1 \\
f_2 \\
\vdots \\
f_{n-1
\end{pmatrix
\begin{pmatrix
1 - 1 - 1 - \cdots - 1\\
1 - w - w^2 - \cdots - w^{n-1\\
1 - w^2 - w^4 - \cdots - w^{2(n-1)\\
\vdots - \vdots - \vdots - \ddots - \vdots -\\
1 - w^{n-1 - w^{2(n-1) - \cdots - w^{(n-1)^2
\end{pmatrix
\end{array
\begin{pmatrix
x_0 \\
x_1 \\
x_2 \\
\vdots \\
x_{n-1
\end{pmatrix
w = e^{-\frac{2 \pi i{n
محاسبه مستقیم با این تعریف نیازمند عملیات است در حالی که N خروجی و هر خروجی نیازمند جمع N جمله‌است یک تبدیل فوریه سریع روشی است برای محاسبه همان نتایج در زمان عملیات به طور دقیق‌تر همه الگوریتم‌های شناخته شده تبدیل فوریه سریع نیازمند عملیات هستند (البته از لحاظ فنی O فقط یک باند بالا مشخص می‌کند) درحالی که تاکنون حقیقت ثابت شده‌ای وجود ندارد که پیچیدگی بهتر غیرممکن است.
برای نشان دادن ذخیره یک تبدیل فوریه سریع، می‌توان تعداد ضرب‌ها و جمع‌های مختلط را شمارش نمود. در عمل، کارایی واقعی روی رایانه‌های مدرن با فاکتورهایی غیر از علم حساب می‌باشد و یک موضوع پیچیده‌است اما بهبود کلی از به همچنان باقی است.
الگوریتم
Cooley–Tukey FFT algorithm رایج‌ترین الگوریتم تبدیل فوریه سریع الگوریتم کولی-توکی است که یک الگوریتم تقسیم و حل است که به صورت بازگشتی یک مسئله تبدیل فوریه گسسته را به سایز مرکب از N = N ۱ N ۲ می‌شکند و به مسئله تبدیل فوریه گسسته با اندازه‌های N۱ و N۲ تبدیل می‌کند که به ضرب ریشه‌های مختلط واحد نیاز دارد و به طور سنتی فاکتورهای دست زدن آرام نام دارند. (جنتلمن و سنده، ۱۹۶۶)
این روش و ایده عمومی تبدیل فوریه سریع در سال ۱۹۶۵ با انتشارات کولی و توکی معروف شد اما بعدها کشف شد که الگوریتم پیشنهادی این دو نفر قبلا توسط گاوس در سال ۱۸۰۵ به دست آمده بوده‌است.
این الگوریتم در هر مرحله مسئله را به دو تکه با اندازه N/۲ تقسیم می‌کند و بنابراین به اندازه توانی از ۲ محدود است اما می‌توان با فاکتورگیری در حالت کلی مورد استفاده قرار گیرد.
چگونگی سرعت بخشی در تبدیل فوریه سریع
مسائل محاسباتی
باند پیچیدگی و شمارش عملیات‌ها
میزان کمینه پیچیدگی الگوریتم‌های تبدیل سریع فوریه چقدر است؟ آیا می‌توانند سریع‌تر از باشند؟
یکی از سوالات دیرینه علاقه‌مندان این نظریه اثبات باند کمینه پیچیدگی و شمارش تعداد دقیق عملیات لازم برای تبدیل فوریه سریع است و همچنان این مسئله به صورت باز باقی‌مانده‌است. حتی به صورت دقیق ثابت نشده‌است که تبدیل فوریه گسسته دقیقا به (یعنی یا بیشتر) مقدار عملیات نیاز دارد؛ حتی برای گزینه‌های ساده با اندازه توانی از ۲. در حالی که هیچ الگوریتمی با پیچیدگی کمتر نیز شناخته نشده‌است. به طور معمول، معمولا در چنین سوالاتی روی شمارش عملیات‌های ریاضی تمرکز می‌کنیم اگرچه کارایی واقعی روی رایانه‌های امروزی به وسیله بسیاری از فاکتورهای دیگر مانند کش و موازی سازی پردازنده و بهبود آنها استوار است.
دقت و تقریب
تعداد کمی از الگوریتم‌های تبدیل سریع فوریه که در اینجا مطرح شد برای محاسبه مقدار تقریبی تبدیل فوریه گسسته بود. این الگوریتم‌ها خطاهایی دارند که به طور قراردادی کوچک هستند و از افزایش بسیار زیاد محاسبات جلوگیری می‌کنند. چنین الگوریتم‌هایی سرعت زیاد را با خطای تقریبی بسیار کمی معامله می‌کنند. به عنوان مثال الگوریتم تبدیل فوریه سریع ادلمن (Edelman) در ۱۹۹۹ موفق شد تا نیازهای ارتباطی برای محاسبات موازی را با کمک روش سریع سازی مالتی پل کمینه نماید.
حتی الگوریتم‌های دقیق تبدیل فوریه سریع نیز دارای مقادیری خطا به علت محدود بودن دقت محاسبات ممیز شناور مورد استفاده می‌باشند اما این خطاها عموما کاملا کوچک هستند. بیشینه مقدار خطا در خطاهای نسبی برای الگوریتم کولی - توکی است که با میزان خطا برای فرمول تبدیل فوریه گسسته نیوی می‌توان مقایسه نمود. بدین ترتیب که  دقت نسبی ماشین محاسبه گر در محاسبات ممیز شناور است.
پیاده‌سازی
پیاده‌سازی با جاوا
یک نمونه پیاده‌سازی الگوریتم تبدیل فوریه سریع به زبان جاوا در زیر آمده‌است که ورودی تابع FFT یک آرایه از اعداد double با اندازه توانی از ۲ است:
// FFT.java
public class FFT {
public static Complex fft(double input) {
int inputLength = input.length;
if (inputLength == 1) {
// returning an array with just one member
return new Complex { new Complex(input0, 0) ;
double evens = new double ;
double odds = new double ;
for (int i = 0; i
= 2) -- (j> m)) {
j = j - m; m = m>> 2;
j = j + m;
Mmax = 2;
while (n> Mmax) {
Theta = -TwoPi / Mmax; Wpi = Sin(Theta);
Wtmp = Sin(Theta / 2); Wpr = Wtmp * Wtmp * 2;
Istp = Mmax * 2; Wr = 1; Wi = 0; m = 1;
while (m <Mmax) {
i = m; m = m + 2; Tmpr = Wr; Tmpi = Wi;
Wr = Wr - Tmpr * Wpr - Tmpi * Wpi;
Wi = Wi + Tmpr * Wpi - Tmpi * Wpr;
while (i <n) {
j = i + Mmax;
Tmpr = Wr * Tmvlj - Wi * Tmvlj+1;
Tmpi = Wi * Tmvlj + Wr * Tmvlj+1;
Tmvlj = Tmvli - Tmpr; Tmvlj+1 = Tmvli+1 - Tmpi;
Tmvli = Tmvli + Tmpr; Tmvli+1 = Tmvli+1 + Tmpi;
i = i + Istp;
Mmax = Istp;
for (i = 1; i <Nft; i++) {
j = i * 2; FTvli = Sqrt(Sqr(Tmvlj) + Sqr(Tmvlj+1));
delete Tmvl;
فاکتورهای اولیه الگوریتم تبدیل سریع فوریه Prime-factor FFT algorithm
الگوریتم تبدیل سریع فوریه براون
الگوریتم تبدیل سریع فوریه ریدر
الگوریتم تبدیل سریع فوریه بلوستین
روش همپوشانی جمع
تبدیل سریع فوریه در غرب
سری زمانی