نقشهٔ صفحه‌ها · ۱۵ صفحه

نوشته‌شده برای: دانشجویان مهندسی و علوم کامپیوتر

1. 1

   کولی و توکی، ۱۹۶۵: تبدیل فوریهٔ سریع

   • این ارائه مقالهٔ سال ۱۹۶۵ کولی و توکی دربارهٔ محاسبهٔ ماشینی تبدیل فوریه را می‌خواند.
   • این مقاله الگوریتمی را معرفی کرد که امروز تبدیل فوریهٔ سریع (FFT) نامیده می‌شود.
   • آن را مانند یک مهندس می‌خوانیم: هزینه چه بود، ایده چه بود و چرا فراگیر شد؟
2. 2

   مسیر خواندن: هزینه، ایده، روش، نتایج

   • نخست، مسئلهٔ هزینه: چرا تبدیل فوریهٔ گسستهٔ مستقیم پرهزینه است.
   • دوم، ایدهٔ اصلی: شکستن یک تبدیل بلند به چند تبدیل کوتاه‌تر.
   • سوم، روش: نصف کردن پیاپی و عملگر پروانه‌ای.
   • در پایان، نتایج، بده‌بستان‌ها و کاربردهایی که پس از آن آمد.
3. 3

   چرا DFT مستقیم N² عملیات هزینه دارد

   • تبدیل فوریهٔ گسسته N نمونهٔ ورودی را به N مقدار بسامدی خروجی تبدیل می‌کند.
   • هر خروجی جمعی روی همهٔ N ورودی است که با نمایی‌های مختلط وزن‌دهی شده‌اند.
   • N خروجی ضرب در N جمله، از مرتبهٔ N² ضرب و جمع مختلط می‌شود.
   • پس دو برابر شدن طول سیگنال، کار را تقریباً چهار برابر می‌کند.
4. 4

   محدودیت‌های میان‌برهای پیشین

   • میان‌برهای پیشین از تقارن داده‌ها یا چینش‌های ویژهٔ نمونه‌ها بهره می‌گرفتند.
   • این ترفندها در موارد خاص کمک می‌کردند، اما نرخ رشد هزینه را برای N دلخواه تغییر نمی‌دادند.
   • محاسبهٔ دستی و ماشین‌های نخستین به داده‌های کوتاه محدود ماندند.
   • روشی عمومی با رشد بسیار کمتر هنوز در کار نبود.
5. 5

   ایدهٔ کلیدی: شکستن یک تبدیل بلند به چند تبدیل کوتاه

   • ایدهٔ کلیدی: تبدیلی به طول N را می‌توان از تبدیل‌های کوچک‌تر ساخت.
   • نمونه‌ها به دو گروه تقسیم می‌شوند، مثلاً اندیس‌های زوج و اندیس‌های فرد.
   • هر نیمه یک DFT به طول N/2 می‌خواهد که بسیار ارزان‌تر از تبدیلی به طول N است.
   • سپس دو نتیجهٔ جزئی با چند عملیات اضافه با هم ترکیب می‌شوند.
6. 6

   روش: نصف کردن پیاپی وقتی N توانی از دو است

   • وقتی N توانی از دو باشد، شکستن را می‌توان بارها تکرار کرد.
   • هر نصف کردن، اندازهٔ مسئله را کوچک می‌کند تا فقط تبدیل‌های طول ۲ بمانند.
   • این کار log₂ N مرحله پدید می‌آورد.
   • هزینهٔ هر مرحله از مرتبهٔ N عملیات است، پس کل کار حدود N log₂ N می‌شود.
7. 7

   پیاده‌سازی عملگر پروانه‌ای

   • عملگر پروانه‌ای دو مقدار می‌گیرد و دو مقدار تازه می‌سازد.
   • یکی از ورودی‌ها در یک ضریب چرخشی مختلط، یعنی یک ریشهٔ واحد، ضرب می‌شود.
   • مجموع و تفاضل دو جمله، خروجی‌ها را می‌سازند.
   • همین عملیات کوچک همه‌جا تکرار می‌شود و برای همین کدنویسی آن آسان است.
8. 8

   درون یک مرحله: N/2 عملگر پروانه‌ای

   • هر مرحله N/2 عملگر پروانه‌ای را به کار می‌گیرد، یکی برای هر جفت مقدار.
   • جفت‌های درون یک مرحله از یکدیگر مستقل‌اند.
   • اجرای log₂ N مرحله با N/2 عملگر در هر مرحله، شمار کل عملیات را می‌دهد.
   • هر عملگر پروانه‌ای یک ضرب مختلط و دو جمع دارد.
9. 9

   مزایا: عملیات کمتر و محاسبهٔ درجا

   • مزیت اصلی، عملیات بسیار کمتر نسبت به روش مستقیم N² است.
   • خروجی‌های عملگر پروانه‌ای می‌توانند روی ورودی‌هایش نوشته شوند، پس محاسبه درجا انجام می‌شود.
   • محاسبهٔ درجا جز آرایهٔ داده، حافظهٔ اضافهٔ کمی می‌خواهد.
   • هر دو مزیت روی ماشین‌های کم‌حافظهٔ دههٔ ۱۹۶۰ اهمیت داشت.
10. 10

    بده‌بستان حافظه و سرعت

    • محاسبهٔ درجا در حافظه صرفه‌جویی می‌کند، اما خروجی‌ها را به ترتیب درهم و بیت‌وارون باقی می‌گذارد.
    • برای خواندن نتایج به ترتیب طبیعی بسامد، بازچینی لازم است.
    • ضریب‌های چرخشی را می‌توان یک بار حساب و ذخیره کرد یا دوباره حساب کرد؛ بده‌بستانی میان حافظه و سرعت.
    • ساده‌ترین شکل فرض می‌کند N توانی از دو است و این انعطاف را کم می‌کند.
11. 11

    مقاله آزمون‌هایش را چگونه چید

    • مقاله الگوریتم را با اجرای آن روی سیگنال‌های نمونه آزمود.
    • درستی نتایج با تعریف مستقیم DFT بررسی شد.
    • زمان اجرا، در مقایسه با محاسبهٔ مستقیم، کمیت مورد نظر بود.
    • طول‌های آزمون متناسب با ساختار توان دو برگزیده شدند.
12. 12

    آزمون‌ها روی سیگنال‌های نمونه چه نشان دادند

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

    کاربردهای بعدی: طیف‌نگاری، پالایش، تصویربرداری

    • تحلیل طیفی برای داده‌های بسیار بلندتر شدنی شد.
    • پالایش در حوزهٔ بسامد با هزینهٔ کم انجام‌پذیر شد.
    • تصویرها و دیگر داده‌های چندبعدی می‌توانستند از تبدیل سریع در راستای هر محور بهره ببرند.
    • تبدیل‌های ارزان‌تر، روش‌های حوزهٔ بسامد را به ابزاری روزمره در مهندسی بدل کردند.
14. 14

    N² در برابر N log₂ N: افزایش سرعت به زبان عدد

    • در N = 64، تبدیل مستقیم ۴٬۰۹۶ عملیات می‌خواهد و FFT تنها ۳۸۴ عملیات.
    • در N = 1024، این شمارها ۱٬۰۴۸٬۵۷۶ در برابر ۱۰٬۲۴۰ است.
    • در N = 16384، این شمارها ۲۶۸٬۴۳۵٬۴۵۶ در برابر ۲۲۹٬۳۷۶ است.
    • با بزرگ‌تر شدن N این فاصله بیشتر می‌شود، چون N² تندتر از N log₂ N رشد می‌کند.

    جدول: شمار عملیات در DFT مستقیم و FFT. منبع: Computing the DFT, CSE 616 lecture notes (slide 'Significance') · بررسی‌شده در 2026-10-10

15. 15

    چرا یک مقالهٔ ۱۹۶۵ پردازش سیگنال را دگرگون کرد

    • این مقاله هزینهٔ یک عملیات بنیادی را از N² به N log₂ N کاهش داد.
    • ایده عمومی، ساده برای کدنویسی و سازگار با حافظه بود.
    • هزینهٔ کمتر، کاربردهای تازه‌ای برای تحلیل بسامد در سراسر مهندسی گشود.
    • برای دانشجویان نشان می‌دهد بازچینی یک الگوریتم می‌تواند از سخت‌افزار سریع‌تر پیشی بگیرد.