تبدیل فوریه سریع FAST Fourier transform – FFT

تبدیل سریع فوریه (Fast Fourier transform – FFT)

نام الگوریتمی است  برای انجام تبدیلات  به صورتی سریع و بسیار کارآمد. تعداد زیادی الگوریتم‌های تبدیل فوریه  سریع مجزا وجود دارد که شامل محدوده عظیمی از ریاضیات می‌شوند

بدیل فوریه سریع تبدیل فوریه گسسته را محاسبه می‌کند و دقیقاً همان نتایجی را تولید می‌کند که مستقیماً با تعریف تبدیل فوریه گسسته به دست می‌آید تنها تفاوت آن این است که بسیار سریع تر است

اگر اعداد مختلط  x_۰، ….، x_N-۱ را در نظر بگیریم تبدیل فوریه گسسته با فرمول زیر تعریف می‌شود:

بر مبنای سری فوریه، می‌توان نشان داد که هر سیگنال پریودیک را می‌توان به صورت مجموع سیگنال‌های سینوسی و کسینوسی بیان کرد. به هر کدام از این سیگنال‌های سینوسی، یک مؤلفه گفته می‌شود. هر مؤلفه، یک فرکانس و دامنه دارد. بنابراین، اگر برای یک سیگنال یا موج در حوزه زمان، سری فوریه آن را محاسبه کنیم، می‌توان مؤلفه‌های آن را در نمودار دیگری که محور افقی آن فرکانس مؤلفه‌ها و محور عمودی آن، دامنه مؤلفه‌ها هستند نمایش داد. این نمایش را، نمایش حوزه فرکانس سیگنال می‌گویند.

پیاده سازی FFT تبدیل فوریه سریع در Fpga

تبدیل فوریه سریعFFT به زبان C++