مقدمه
تبدیل فوریه
تبدیل فوریه را در فیزیک و ریاضیات زیاد می‌بینیم و همین باعث می‌شود کاربردهای روزمره‌ی بسیاری هم داشته باشد.
به‌طور خلاصه، تبدیل فوریه یک سیگنال ورودی را می‌گیرد، که اغلب در دامنه‌ی زمان یا دامنه‌ی مکان است، و آن را به دامنه‌ی فرکانس تبدیل می‌کند.
و به‌طور مشخص‌تر، اگر سیگنال ورودی از درهم‌آمیختگی (یعنی «برهم‌نهی») فرکانس‌های مختلف ساخته شده باشد، تبدیل فرکانس‌های منفرد را از هم جدا می‌کند و قدرت نسبی‌شان را نشان می‌دهد.
همین موضوع، تبدیل را به ابزاری اصلی در پردازش سیگنال (مثلاً فیلتر کردن، فشرده‌سازی و غیره) و در بسیاری از کاربردهای علم داده تبدیل می‌کند.
بنابراین شاید کاربردش گسترده‌تر از آن باشد که در نگاه اول تصور می‌کنید، و همین آن را به نمونه‌ای برجسته از کاربردهایی تبدیل می‌کند که در آن‌ها اعداد موهومی خود را ضروری نشان می‌دهند، چرا که خروجی تبدیل فوریه به‌طور کلی یک عدد مختلط است.
تبدیل فوریه صورت‌بندی انتگرالی هم دارد، اما ما در دنیای دیجیتال هستیم، پس به نسخه‌ی گسسته‌ی آن علاقه‌مندیم.
استخراج این تبدیل فراتر از حیطه‌ی این تمرین است، اما تبدیل گسسته رو به جلو (به دامنه‌ی فرکانس) به شکل زیر است:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
در اینجا مجموع روی n انجام می‌شود، N تعداد نمونه‌ها است، k فرکانس، i یکه‌ی موهومی و xₙ یک نمونه‌ی منفرد است.
تبدیل فوریه‌ی سریع
تبدیل فوریه با آنکه بسیار کاربردی است، اگر ساده‌لوحانه پیاده‌سازی شود کمی کند است (O(n²)).
تبدیل فوریه‌ی سریع (FFT) الگوریتمی است که این کار را به‌شدت سریع‌تر می‌کند.
این کار معمولاً با راهبرد تقسیم و غلبه انجام می‌شود که از برخی تقارن‌ها در صورت‌بندی بهره می‌گیرد و در نهایت به پیچیدگی مجانبی O(Nlog(N)) می‌رسد.
این افزایش سرعت، کاربردپذیری و گستره‌ی کاربردهای مناسب برای این تبدیل را به‌شدت بهبود می‌دهد.
دستورالعمل‌ها
دوست شما یک مهندس صدا است که از شما خواسته است به او کمک کنید تا برای نرم‌افزاری اختصاصی که در حال ساخت آن است، یک «تبدیل فوریه» کدنویسی کند.
از آنجا که می‌خواهید این کار را درست انجام دهید، ابتدا «تبدیل فوریه گسسته» را با همان سادگی خام و بی‌پیرایه‌اش پیاده‌سازی می‌کنید.
سپس می‌توان از آن برای آزمودن درستی هدف نهایی‌تان، «تبدیل فوریه سریع»، استفاده کرد.
1. تبدیل فوریه گسسته
تبدیل فوریه گسسته را پیاده‌سازی کنید.
توجه داشته باشید که این الگوریتم پیچیدگی O(n²) دارد، چون برای هر بار گذر از میان همه‌ی n یک k دارید و می‌خواهید یک بردار Xₖ داشته باشید که هم‌طول با بردار سیگنال Xₙ باشد (برای وارون‌پذیری)؛ پس n بار گذر از n نقطه برابر O(n²) است.
2. تبدیل فوریه سریع
تبدیل فوریه سریع را پیاده‌سازی کنید.
منابع زیادی برای یافتن جزئیات بیشتر درباره‌ی ویژگی‌های خاص این الگوریتم وجود دارد، پس می‌توانید با خیال راحت کمی تحقیق کنید.
