Fast Fourier Transform (FFT) یا “تبدیل فوریه سریع” یعنی چه؟

Fast Fourier Transform (FFT) یا تبدیل فوریه سریع، یک الگوریتم بسیار مهم و پرکاربرد در پردازش سیگنال، پردازش تصویر، و بسیاری از زمینه‌های علمی و مهندسی است. در واقع، FFT یک روش بهینه برای محاسبه تبدیل فوریه گسسته (DFT) و معکوس آن (IDFT) است.

برای اینکه FFT را به خوبی درک کنیم، ابتدا باید مفهوم تبدیل فوریه و سپس تبدیل فوریه گسسته (DFT) را بدانیم.

1. مفهوم تبدیل فوریه (Fourier Transform)

تصور کنید که شما یک سیگنال پیچیده دارید، مثلاً یک قطعه موسیقی. گوش انسان این سیگنال را به صورت ترکیبی از صداهای مختلف (با فرکانس‌ها و شدت‌های متفاوت) درک می‌کند. تبدیل فوریه دقیقاً همین کار را به صورت ریاضی انجام می‌دهد.

تبدیل فوریه یک سیگنال را از “حوزه زمان” (Time Domain) به “حوزه فرکانس” (Frequency Domain) تبدیل می‌کند.

• حوزه زمان: در این حوزه، ما سیگنال را به صورت تغییرات دامنه آن (مثلاً ولتاژ یا فشار هوا) بر حسب زمان مشاهده می‌کنیم. نموداری که سیگنال صوتی را در طول زمان نشان می‌دهد، یک سیگنال در حوزه زمان است.
• حوزه فرکانس: در این حوزه، سیگنال به اجزای فرکانسی تشکیل‌دهنده‌اش تجزیه می‌شود. یعنی، تبدیل فوریه به ما می‌گوید که سیگنال اصلی از چه فرکانس‌هایی (مثلاً 100 هرتز، 1 کیلوهرتز، 5 کیلوهرتز) و با چه شدت‌هایی تشکیل شده است. نمودار در حوزه فرکانس معمولاً یک طیف فرکانسی را نشان می‌دهد که در آن محور افقی فرکانس و محور عمودی دامنه (یا توان) آن فرکانس را نشان می‌دهد.

به زبان ساده، تبدیل فوریه یک سیگنال را به مجموعه‌ای از موج‌های سینوسی ساده با فرکانس‌ها و دامنه‌های مختلف تجزیه می‌کند.

فرمول کلی تبدیل فوریه پیوسته (برای سیگنال‌های آنالوگ):

که x(t) سیگنال در حوزه زمان و X(ω) سیگنال در حوزه فرکانس (طیف فرکانسی) است.

2. تبدیل فوریه گسسته (DFT)

در دنیای دیجیتال، ما با سیگنال‌های پیوسته سروکار نداریم، بلکه با نمونه‌های گسسته (sampled) از یک سیگنال سروکار داریم. به عنوان مثال، وقتی یک میکروفون صدا را ضبط می‌کند، در فواصل زمانی مشخصی از سیگنال نمونه‌برداری می‌کند. برای کار با این سیگنال‌های گسسته، به تبدیل فوریه گسسته (DFT) نیاز داریم.

DFT، همانند تبدیل فوریه پیوسته، یک سیگنال گسسته در حوزه زمان را به یک سیگنال گسسته در حوزه فرکانس تبدیل می‌کند.

فرمول DFT:

که:

• xn​: $n$-اُمین نمونه از سیگنال ورودی در حوزه زمان (که مجموعاً $N$ نمونه داریم).
• Xk​: $k$-اُمین مؤلفه فرکانسی در حوزه فرکانس.
• $N$: تعداد کل نمونه‌های سیگنال.
• $k$: اندیس فرکانس (از 0 تا $N-1$).

محاسبه مستقیم DFT با استفاده از این فرمول، نیاز به N2 عملیات ضرب و جمع (که هر کدام پیچیده هستند) دارد. برای سیگنال‌های طولانی (با N بالا)، این عملیات می‌تواند بسیار زمان‌بر و پرهزینه باشد.

3. تبدیل فوریه سریع (FFT)

اینجاست که FFT وارد عمل می‌شود!

FFT (Fast Fourier Transform) یک الگوریتم کارآمد برای محاسبه DFT است که تعداد عملیات محاسباتی را به طور چشمگیری کاهش می‌دهد.

به جای N2 عملیات، FFT نیاز به تقریباً Nlog2​(N) عملیات دارد. این کاهش در سرعت محاسبات، به خصوص برای مقادیر بزرگ N (مثلاً هزاران یا میلیون‌ها نمونه)، بسیار چشمگیر است و باعث می‌شود که DFT از نظر عملی قابل استفاده باشد.

چگونه FFT سرعت را افزایش می‌دهد؟

الگوریتم‌های FFT مختلفی وجود دارد، اما محبوب‌ترین آنها بر اساس ایده “تقسیم و حل” (Divide and Conquer) کار می‌کنند. به عنوان مثال، الگوریتم Cooley-Tukey (که رایج‌ترین الگوریتم FFT است) با تقسیم کردن یک DFT بزرگ به چندین DFT کوچک‌تر و سپس ترکیب نتایج آنها، محاسبات را بهینه می‌کند. این فرآیند بازگشتی است و تا زمانی که به DFTهای دو نقطه‌ای (که به راحتی قابل محاسبه هستند) برسیم، ادامه پیدا می‌کند.

مثال: مقایسه سرعت DFT و FFT

اگر $N=1024$ (تعداد نمونه‌ها):

• DFT: 10242=1,048,576 عملیات
• FFT: 1024×log2​(1024)=1024×10=10,240 عملیات

همانطور که می‌بینید، FFT ده‌ها تا صدها برابر سریع‌تر از DFT مستقیم است.

4. خروجی FFT

خروجی FFT یک سری از اعداد مختلط است. هر عدد مختلط شامل یک قسمت حقیقی و یک قسمت موهومی است. برای به دست آوردن اطلاعات مفید مانند دامنه (شدت) هر فرکانس، باید قدر مطلق (magnitude) این اعداد مختلط را محاسبه کنیم:

این دامنه، نشان‌دهنده میزان حضور آن فرکانس خاص در سیگنال اصلی است.

5. کاربردهای FFT:

FFT در بسیاری از زمینه‌ها کاربردهای گسترده‌ای دارد، از جمله:

• پردازش سیگنال‌های صوتی:
  • تجزیه و تحلیل طیف فرکانسی موسیقی و گفتار.
  • فیلتر کردن نویز (با شناسایی فرکانس نویز و حذف آن).
  • فشرده‌سازی صدا (مثل MP3) با حذف فرکانس‌های کمتر شنیده شده.
  • تشخیص الگوهای صوتی و گفتاری.
  • اکولایزرها (مانند تراشه MSGEQ7 که به آن اشاره کردید، در واقع یک نسخه سخت‌افزاری ساده از تحلیل فرکانسی است، اما DFT/FFT تجزیه بسیار دقیق‌تر و جزئی‌تری ارائه می‌دهد).
• پردازش تصویر:
  • فیلتر کردن تصاویر (مثلاً شارپ کردن یا تار کردن تصاویر).
  • فشرده‌سازی تصاویر (مثل JPEG) با تبدیل تصویر به حوزه فرکانس و حذف فرکانس‌های بالا که جزئیات کمتر مهم را تشکیل می‌دهند.
  • تشخیص لبه‌ها و ویژگی‌ها.
• تحلیل ارتعاشات و ماشین‌آلات:
  • تشخیص عیوب در موتورها، بلبرینگ‌ها و سایر ماشین‌آلات با تحلیل طیف فرکانسی ارتعاشات آنها.
• مخابرات:
  • مدولاسیون و دمدولاسیون سیگنال‌ها.
  • طراحی فیلترها.
• علوم پزشکی:
  • آنالیز سیگنال‌های مغزی (EEG) و قلبی (ECG).
• نجوم:
  • تحلیل سیگنال‌های رادیویی از فضا.

6. محدودیت‌ها و ملاحظات FFT:

• پنجره‌بندی (Windowing): FFT فرض می‌کند که سیگنال ورودی تناوبی است و دقیقا در انتهای پنجره زمانی تکرار می‌شود. اگر سیگنال ورودی این خاصیت را نداشته باشد، “پراکندگی طیفی” (Spectral Leakage) رخ می‌دهد که باعث می‌شود فرکانس‌های موجود در سیگنال به درستی نمایش داده نشوند. برای کاهش این اثر، از توابع پنجره‌ای (مانند Hanning, Hamming, Blackman) استفاده می‌شود که به تدریج سیگنال را در ابتدا و انتهای پنجره به صفر می‌رسانند.
• رزولوشن فرکانسی: رزولوشن فرکانسی (دقت در تشخیص فرکانس‌های نزدیک به هم) به تعداد نمونه‌های N و فرکانس نمونه‌برداری (Sampling Frequency) بستگی دارد. هرچه N بیشتر باشد، رزولوشن فرکانسی بالاتر است.
• فرکانس نایکوئیست (Nyquist Frequency): برای جلوگیری از پدیده “آلیاسینگ” (Aliasing) که در آن فرکانس‌های بالا به اشتباه به عنوان فرکانس‌های پایین‌تر ظاهر می‌شوند، فرکانس نمونه‌برداری باید حداقل دو برابر بالاترین فرکانس موجود در سیگنال باشد (قضیه نایکوئیست).
• قدرت 2 بودن N: بسیاری از الگوریتم‌های FFT بهینه‌تر عمل می‌کنند اگر تعداد نمونه‌های N توانی از 2 باشد (مثلاً 256, 512, 1024, 2048). اگر N توانی از 2 نباشد، می‌توان از روش‌هایی مانند “پدینگ صفر” (Zero Padding) استفاده کرد که به انتهای سیگنال صفر اضافه می‌شود تا طول آن به یک توان از 2 برسد.

جمع‌بندی:

FFT یک ابزار ریاضی قدرتمند است که به ما امکان می‌دهد سیگنال‌ها را از حوزه زمان به حوزه فرکانس تبدیل کرده و ساختار فرکانسی آنها را درک کنیم. این قابلیت در تحلیل، فیلتر کردن، فشرده‌سازی و بسیاری از کاربردهای دیگر در دنیای دیجیتال و مهندسی ضروری است. در مقایسه با MSGEQ7 که یک تحلیلگر باند-پاس آنالوگ ساده است، FFT یک تحلیل دقیق و جزئی از تمام فرکانس‌های موجود در سیگنال ارائه می‌دهد و انعطاف‌پذیری بسیار بیشتری دارد.