آنچه FFT در واقع نشان می دهد

پرسش

یک آکورد روی یک پیانو بازی کنید – مثلاً C و E با هم. گوش شما یک صدا را می شنود. اما این صدا دو فرکانس است: 261.6 هرتز و 329.6 هرتز. cochlea شما به طور فیزیکی آنها را جدا می کند - سلول های مختلف مو در فرکانس های مختلف طنین انداز می کنند و سیگنال های متمایز را به مغز شما ارسال می کنند.

تغییر سریع Fourier همان کار را انجام می دهد، اما با اعداد به جای سلول های مو. به آن یک سیگنال (یک توالی نمونه های دامنه در طول زمان) بدهید و لیستی از فرکانس ها و نقاط قوت آنها را باز می گرداند. پاسخ: ** چه فرکانسی وجود دارد و چه مقدار از هر کدام؟

آنچه در واقع اتفاق می افتد

نمونه سیگنال در طول زمان یک لیست از اعداد است: دامنه در هر نقطه نمونه. ضبط 1 ثانیه در 44،100 هرتز 44،100 عدد است. این اعداد سیگنال را در دامنه **time - دامنه به عنوان تابع زمان توصیف می کنند.

FFT این را به دامنه * فرکانس ** تبدیل می کند - دامنه به عنوان تابع فرکانس. همان اطلاعات، نمایندگی های مختلف مانند تعویض بین مختصات دکارتی و قطبی: هیچ چیز ایجاد نمی شود یا نابود نمی شود، فقط بیان می شود.

هسته ریاضی: هر سیگنال دوره ای را می توان به عنوان خلاصه ای از امواج گناه و cosine در فرکانس های مختلف نوشته شده است. این قضیه چهار بعدی (1807) است. FFT ضریب های این خلاصه را محاسبه می کند - چه مقدار از هر فرکانس در سیگنال است.

چرا "سریع"

روش ساده لوحانه برای محاسبه یک تغییر چهار بعدی نیاز به عملیات N2 برای نمونه های N برای نمونه های 1024، این حدود 1 میلیون عملیات است. الگوریتم Cooley-Tukey (1965) این را به N ·log2 (N) کاهش می دهد - حدود ۱۰۰۰۰ عملیات برای همان ورودی. سرعت 100x برای یک میلیون نمونه، سرعت 500.000x است.

ترفند: تبدیل N-point به دو تغییر نقطه N/2، بازگشتی. این نیاز به N دارد تا قدرت 2 باشد (یا شما با صفر آویزان می شوید). هر تقسیم بندی مشکل را نصف می کند. عملیات "butterfly" ترکیبی از نیمه ها است:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

جایی که W یک نمایی پیچیده است (یک چرخش در هواپیما پیچیده). دو نتیجه فرعی به شما دو امتیاز خروجی می دهد. به همین دلیل است که الگوریتم "سرعت" است - هر محاسبه را دوبار استفاده می کند.

پیاده سازی PinePaper یک کتاب درسی Cooley-Tukey Radix-2 DIT است. 40 خط جاوا اسکریپت ما آن را از ابتدا به جای وارد کردن یک کتابخانه نوشتیم زیرا می خواستیم دانش آموزان بتوانند منبع را بخوانند و هر خط را درک کنند.

آنچه این بارها می گویند

هنگامی که شما یک تجزیه و تحلیل طیف را مشاهده می کنید - میله های پرش به موسیقی - هر نوار نشان دهنده یک سطل فرکانس است. ارتفاع اندازه (قدرت) این فرکانس در سیگنال فعلی است.

• ** موج گناه خالص ** یک بار بلند را با فرکانس و هیچ چیز دیگری تولید می کند.
• ** موج مربع ** میله ها را در پایه و هر گونه آسیب زای عجیب (3rd, 5th, 7th ...) تولید می کند، کاهش به عنوان 1 /n. به همین دلیل است که امواج مربع "buzzy" نامیده می شوند - آنها حاوی انرژی با فرکانس بالا هستند که گناه خالص نیست.
• • صدای سفید ** میله های تقریبا مساوی در همه جا تولید می کند. هر فرکانس با احتمال برابر وجود دارد.
• ** یک صدای انسانی ** تولید یک پایه (زمینی که شما می شنوید) به علاوه فرمرها - قله های برجسته از شکل دستگاه صوتی خود را که سیمل ها را متمایز می کند.

پنجره: چرا لبه ها مهم هستند

یک ضربه وجود دارد. FFT فرض می کند که سیگنال برای همیشه تکرار می شود. اما نمونه ما محدود است - شروع می شود و متوقف می شود. اگر سیگنال در هر دو نقطه پایانی صفر نباشد، برش ناگهانی محتوای با فرکانس مصنوعی ایجاد می کند. این به نام ** نشت چشم انداز.

تعمیر: ضرب سیگنال توسط یک تابع * پنجره ** که به راحتی به صفر در لبه. پنجره های معمولی:

• ** Hann ** (یک زنگ مرغ): هدف کلی خوب، از دست دادن برخی از رزولوشن فرکانس
• ** در حالی که شبیه به هانن است اما در لبه ها به صفر نمی رسد، کمی بهتر سرکوب جانبی
• • Blackman **: لوب اصلی باریک تر، سرکوب بهتر جانبی، از دست دادن رزولوشن فرکانس بیشتر

انتخاب همیشه یک معامله بین حل فرکانس است (هرچند شما دقیقا می توانید یک فرکانس را شناسایی کنید) و نشت طیفی (چه مقدار خونریزی انرژی در سطل های مجاور). هیچ پنجره کامل وجود ندارد. این یک نتیجه از اصل عدم اطمینان است - شما نمی توانید به طور خودسرانه دانش دقیق از هر دو زمان و فرکانس به طور همزمان داشته باشید.

جایی که زندگی FFT

شما به طور مداوم با نتایج FFT تعامل دارید:

• *MP3 و فشرده سازی AAC **: تبدیل صدا به دامنه فرکانس، دور زدن فرکانس زیر آستانه شنوایی، فشرده آنچه باقی مانده است. این تبدیل کل پایه فشرده سازی صوتی از دست دادن است.
• ** فشرده سازی JPEG - نسخه 2D (DCT) 8×8 بلوک پیکسل را به دامنه فرکانس تبدیل می کند، اجزای فرکانس بالا را تعیین می کند. به همین دلیل است که مصنوعات JPEG به عنوان بلوک ها ظاهر می شوند.
• **WiFi و 5G **: رمزگذاری OFDM داده ها را در بسیاری از زیرمجموعه های فرکانس تقسیم می کند. FFT بین انتقال زمان-domain و نمادهای داده های دامنه فرکانسی تبدیل می شود.
• ** تصویربرداری MRI **: سیگنال خام از اسکنر MRI در فضای فرکانسی است. FFT معکوس تصویر فضایی را بازسازی می کند. به معنای واقعی کلمه: هر MRIی که تا به حال دیده اید، یک دگرگونی چهارگانه است.
• **Shazam ** محاسبه طیفogram (FFT بیش از پنجره های کشویی)، استخراج قله ها، مطابقت الگوی در برابر یک پایگاه داده. FFT اولین گام در شناخت هر آهنگ است.

یک الگوریتم 60 ساله در جیب شما، میلیاردها بار در روز اجرا می شود.

{{-plot}}

سعی کنید

PinePaper را باز کنید، ژنراتور تجزیه و تحلیل طیف را انتخاب کنید. یک موج مربع را تولید کنید. به میله ها نگاه کنید - شما می بینید که هارمونیک های عجیب و غریب به عنوان 1 /n سقوط می کنند. سوئیچ به یک دندان دیده شده - در حال حاضر همه هارمونیک ها وجود دارد، سقوط به عنوان 1 /n. سوئیچ به سر و صدا - طیف مسطح، هر فرکانس به همان اندازه ممکن است.

تغییر عملکرد پنجره نگاه کنید که چگونه هانن طیف را با هزینه های قله های گسترده تر هموار می کند. سوئیچ به Blackman - قله های باریک اما حاشیه پایین تر.

شما در مورد FFT نمی خوانید. شما سیگنال ها را اندازه گیری می کنید و مشاهده می کنید که چه چیزی نشان می دهد. این تفاوت بین شناخت و درک است.

ارجاعات

• بریهام، E.O. (1988) * سریع تبدیل و برنامه های آن سالن پادشاهی.
• Cooley، J.W. & Tukey، J.W. (1965). الگوریتمی برای محاسبه ماشین سری چهار نفره پیچیده * مفاهیم قطع عضو*، 19 (90)، 297-301.
• 4ier, J. (1822) Théorie مقعدی de la chaleur پاریس: شرکت Didot.
• هریس، F.J. (1978) در استفاده از ویندوز برای تجزیه و تحلیل هارمونی با تغییر چهار بعدی گسسته * نظارت بر IEEE *، 66 (1)، 51-83.
• Oppenheim، A.V. & Schafer، R.W. (2009) پردازش سیگنال زمان دفع شده * (3rd ed) سالن پادشاهی.
• شانون، C.E. (1949) ارتباطات در حضور نویز * نظارت بر IRE *، 37 (1)، 10-21.
• اسمیت، S.W. (1997) راهنمای دانشمند و مهندس برای پردازش سیگنال دیجیتال انتشارات فنی کالیفرنیا.
• وانگ، A.، et al. (2003) یک الگوریتم جستجوی صوتی صنعتی * تایید ISMIR 2003 ( الگوریتم اثر انگشت صوتی Shutteram)
• والاس، G.K. (1991) استاندارد JPEG Still Picture Compression • ارتباطات ACM *، 34 (4)، 30-44.

---

*PinePaper’s FFT یک پیاده سازی Cooley-Tukey Radix-2 با Hann، Hamming و Blackman پنجره سازی است، به علاوه فیلترهای کمپوست و با کیفیت بالا. سعی کنید آن را در [pinepaper.studio/editor] (/editor) آزاد کنید