تبدیل سریع فوریه (Fast Fourier transform - FFT) نام الگوریتمی‌ست برای انجام تبدیلات مستقیم و معکوس گسستهٔ فوریه به صورتی سریع و بسیار کارآمد. تعداد زیادی الگوریتم‌های تبدیل فوریه سریع مجزا وجود دارد که شامل محدوده عظیمی از ریاضیات می‌شوند: از محاسبات ساده به وسیله اعداد مختلط تا نظریه اعداد.این مقاله یک چشم اندازی است به تکنیک‌های موجود و برخی ویژگی‌های عمومی آنها. همچنین الگوریتم‌های خاص در مقالات دیگری توضیح داده شده‌اند.
یک تبدیل فوریه سریع تجزیه یک رشته از مقادیر به مولفه‌هایی با فرکانس‌های متفاوت است. این عملیات در بسیاری از رشته‌ها مفید است (ویژگی‌ها و کاربردهای تبدیل فوریه گسسته را مشاهده کنید.) اما محاسبه مستقیم آن از تعریف گاهی اوقات در عمل بسیار کند است. تبدیل فوریه سریع یک راه برای محاسبه همان نتایج به طور سریع تر است؛ محاسبه تبدیل فوریه گسسته برای n نقطه با استفاده از تعریف O(n^2) عملیات ریاضی نیاز دارد در حالی که تبدیل فوریع سریع می‌تواند همان نتایج را در O(n\log^n) عملیات، محاسبه نماید.
مقایسه تبدیل سریع فوریه و تبدیل فوریه گسسته
این تفاوت در سرعت می‌تواند بسیار چشمگیر باشد، مخصوصا برای مجموعه داده‌های بزرگ. در جایی که n ممکن است در عمل هزاران یا میلیون‌ها باشد، زمان محاسبه در برخی موارد می‌تواند به اندازه چند مرتبه کاهش پیدا کند و بهبود آن در حدود n / \log^n مرتبه‌است. این بهبود عظیم موجب شده تا بسیاری از الگوریتم‌های عملی تبدیل فوریه گسسته را به صورت تبدیل فوریه سریع پیاده سازی نمایند. بنابراین تبدیل فوریه سریع در محدوده متنوعی از کاربردها از پردازش سیگنال دیجیتال و حل معادلات دیفرانسیل با مشتقات جزئی(پاره‌ای) تا ضرب مقادیر بزرگ صحیح به کار می‌رود.
از تبدیل فوریه سریع به عنوان «مهمترین الگوریتم عددی عصر زندگی ما» یاد می‌شود.
محتویات
۱ تاریخچه
۲ تعریف و سرعت
۳ الگوریتم
۴ مسائل محاسباتی
۴.۱ باند پیچیدگی و شمارش عملیات‌ها
۴.۲ دقت و تقریب
۵ پیاده سازی
۵.۱ پیاده سازی با جاوا
۵.۲ پیاده سازی با C++
۶ جستارهای وابسته
۷ منابع
۸ پیوند به بیرون
تاریخچه
در طول تمامی سده گذشته و به خصوص در طی ۵۰ سال آخر آن صنایع گوناگون و رشته‌های مختلف دانشگاهی را می‌توان ذکر کرد که به واسطه اعمال ایده‌ها و تکنیک‌های گوناگون فوریه به نحو کاملی شکوفا و پررونق شده‌اند.
تعریف و سرعت
تبدیل فوریه سریع تبدیل فوریه گسسته را محاسبه می‌کند و دقیقاً همان نتایجی را تولید می‌کند که مستقیماً با تعریف تبدیل فوریه گسسته به دست می‌آید تنها تفاوت آن این است که بسیار سریع تر است
اگر اعداد مختلط x۰، ....، xN-۱ را در نظر بگیریم تبدیل فوریه گسسته با فرمول زیر تعریف می‌شود:
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}}
محاسبه مستقیم با این تعریف نیازمند O(n^2) عملیات است در حالی که N خروجی X_k و هر خروجی نیازمند جمع N جمله‌است یک تبدیل فوریه سریع روشی است برای محاسبه همان نتایج در زمان O(n \log^n) عملیات به طور دقیق تر همه الگوریتم‌های شناخته شده تبدیل فوریه سریع نیازمند O(n \log^n) عملیات هستند (البته از لحاظ فنی O فقط یک باند بالا مشخص می‌کند) درحالی که تاکنون حقیقت ثابت شده‌ای وجود ندارد که پیچیدگی بهتر غیر ممکن است.
برای نشان دادن ذخیره یک تبدیل فوریه سریع، می‌توان تعداد ضرب‌ها و جمعهای مختلط را شمارش نمود. در عمل، کارایی واقعی روی رایانه‌های مدرن با فاکتورهایی غیر از علم حساب می‌باشد و یک موضوع پیچیده‌است اما بهبود کلی از O(n^2) به O(n \log^n) همچنان باقی است.
الگوریتم
Cooley–Tukey FFT algorithm رایج‌ترین الگوریتم تبدیل فوریه سریع الگوریتم کولی-توکی است که یک الگوریتم تقسیم و حل است که به صورت بازگشتی یک مسئله تبدیل فوریه گسسته را به سایز مرکب از N = N۱N۲ می‌شکند و به مسئله تبدیل فوریه گسسته با اندازه‌های N۱ و N۲ تبدیل می‌کند که به O(n) ضرب ریشه‌های مختلط واحد نیاز دارد و به طور سنتی فاکتورهای دست زدن آرام نام دارند. (جنتلمن و سنده، ۱۹۶۶)
این روش و ایده عمومی تبدیل فوریه سریع در سال ۱۹۶۵ با انتشارات کولی و توکی معروف شد اما بعدها کشف شد که الگوریتم پیشنهادی این دو نفر قبلاً توسط گاوس در سال ۱۸۰۵ به دست آمده بوده‌است.
این الگوریتم در هر مرحله مسئله را به دو تکه با اندازه N/۲ تقسیم می‌کند و بنابراین به اندازه توانی از ۲ محدود است اما می‌توان با فاکتورگیری در حالت کلی مورد استفاده قرار گیرد.
چگونگی سرعت بخشی در تبدیل فوریه سریع
مسائل محاسباتی
باند پیچیدگی و شمارش عملیات‌ها
میزان کمینه پیچیدگی الگوریتم‌های تبدیل سریع فوریه چقدر است؟ آیا می‌توانند سریع‌تر از \theta(n \log^n) باشند؟
یکی از سوالات دیرینه علاقه‌مندان این نظریه اثبات باند کمینه پیچیدگی و شمارش تعداد دقیق عملیات لازم برای تبدیل فوریه سریع است و همچنان این مسئله به صورت باز باقی‌مانده‌است. حتی به صورت دقیق ثابت نشده‌است که تبدیل فوریه گسسته دقیقاً به \Omega(N \log^n) (یعنی N \log^n یا بیشتر ) مقدار عملیات نیاز دارد؛ حتی برای گزینه‌های ساده با اندازهٔ توانی از ۲. در حالی که هیچ الگوریتمی با پیچیدگی کمتر نیز شناخته نشده‌است. به طور معمول، معمولاً در چنین سوالاتی روی شمارش عملیات‌های ریاضی تمرکز می‌کنیم اگرچه کارایی واقعی روی رایانه‌های امروزی به وسیله بسیاری از فاکتورهای دیگر مانند کش و موازی سازی پردازنده و بهبود آنها استوار است.
دقت و تقریب
تعداد کمی از الگوریتم‌های تبدیل سریع فوریه که در اینجا مطرح شد برای محاسبه مقدار تفریبی تبدیل فوریه گسسته بود. این الگوریتم‌ها خطاهایی دارند که به طور قراردادی کوچک هستند و از افزایش بسیار زیاد محاسبات جلوگیری می‌کنند. چنین الگوریتم‌هایی سرعت زیاد را با خطای تقریبی بسیار کمی معامله می‌کنند. به عنوان مثال الگوریتم تبدیل فوریه سریع ادلمن (Edelman) در ۱۹۹۹ موفق شد تا نیازهای ارتباطی برای محاسبات موازی را با کمک روش سریع سازی مالتی پل کمینه نماید.
حتی الگوریتم‌های دقیق تبدیل فوریه سریع نیز دارای مقادیری خطا به علت محدود بودن دقت محاسبات ممیز شناور مورد استفاده می‌باشند اما این خطاها عموماً کاملاً کوچک هستند. بیشینه مقدار خطا در خطاهای نسبی برای الگوریتم کولی - توکی O(\epsilon \log^n) است که با O(\epsilon n^{\frac{3}{2}}) میزان خطا برای فرمول تبدیل فوریه گسسته نیوی می‌توان مقایسه نمود. بدین ترتیب که ε دقت نسبی ماشین محاسبه گر در محاسبات ممیز شناور است.
پیاده سازی
پیاده سازی با جاوا
یک نمونهٔ پیاده‌سازی الگوریتم تبدیل فوریهٔ سریع به زبان جاوا در زیر آمده‌است که ورودی تابع 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(input[0], 0) };
}
double[] evens = new double[inputLength / 2];
double[] odds = new double[inputLength / 2];
for (int i = 0; i <inputLength; i++) {
if (i % 2 == 0)
evens[i / 2] = input[i];
else
odds[i / 2] = input[i];
}
Complex[] evensFFT = fft(evens);
Complex[] oddsFFT = fft(odds);
double wSize = 2 * Math.PI / inputLength;
Complex[] result = new Complex[inputLength];
int inputLengthHalf = inputLength / 2;
for (int k = 0; k <inputLengthHalf; k++) {
Complex temp = Complex.mul(
new Complex(Math.cos(wSize * k), Math.sin(wSize * k)),
oddsFFT[k]);
result[k] = Complex.add(evensFFT[k], temp);
result[k + inputLengthHalf] = Complex.sub(evensFFT[k], temp);
}
return result;
}
}
// Complex.java
class Complex {
private double real;
private double imaginary;
public Complex(double real, double imaginary) {
this.real = real;
this.imaginary = imaginary;
}
@Override
public String toString() {
return String.format("%.3f %.3f", real, imaginary);
}
public double getReal() {
return real;
}
public double getImaginary() {
return imaginary;
}
public static Complex add(Complex a, Complex b) {
return new Complex(a.real + b.real, a.imaginary + b.imaginary);
}
public static Complex sub(Complex a, Complex b) {
return new Complex(a.real - b.real, a.imaginary - b.imaginary);
}
public static Complex mul(Complex a, Complex b) {
return new Complex(a.real * b.real - a.imaginary * b.imaginary,
a.real * b.imaginary + a.imaginary * b.real);
}
}
پیاده سازی با C++
const double TwoPi = 6.283185307179586;
void FFTAnalysis(double *AVal, double *FTvl, int Nvl, int Nft) {
int i, j, n, m, Mmax, Istp;
double Tmpr, Tmpi, Wtmp, Theta;
double Wpr, Wpi, Wr, Wi;
double *Tmvl;
n = Nvl * 2; Tmvl = new double[n+1];
for (i = 0; i <Nvl; i++) {
j = i * 2; Tmvl[j] = 0; Tmvl[j+1] = AVal[i];
}
i = 1; j = 1;
while (i <n) {
if (j> i) {
Tmpr = Tmvl[i]; Tmvl[i] = Tmvl[j]; Tmvl[j] = Tmpr;
Tmpr = Tmvl[i+1]; Tmvl[i+1] = Tmvl[j+1]; Tmvl[j+1] = Tmpr;
}
i = i + 2; m = Nvl;
while ((m>= 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 * Tmvl[j] - Wi * Tmvl[j+1];
Tmpi = Wi * Tmvl[j] + Wr * Tmvl[j+1];
Tmvl[j] = Tmvl[i] - Tmpr; Tmvl[j+1] = Tmvl[i+1] - Tmpi;
Tmvl[i] = Tmvl[i] + Tmpr; Tmvl[i+1] = Tmvl[i+1] + Tmpi;
i = i + Istp;
}
}
Mmax = Istp;
}
for (i = 1; i <Nft; i++) {
j = i * 2; FTvl[i] = Sqrt(Sqr(Tmvl[j]) + Sqr(Tmvl[j+1]));
}
delete []Tmvl;
}