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

پرسش

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

تغییر سریع 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 خط جاوا اسکریپت. ما آن را از ابتدا به جای وارد کردن یک کتابخانه نوشتیم زیرا می خواستیم دانش آموزان بتوانند منبع را بخوانند و هر خط را درک کنند.

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

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

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

سه اول زیر است: بین آنها کلیک کنید. ارتفاع ها فرمول هستند،, نه یک نقاشی: گناه 1 در اصل است، موج مربع دقیقا 1 /n است در آسیب های عجیب و غریب.

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

یک گرفتن وجود دارد. 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 ساله در جیب شما، میلیاردها بار در روز اجرا می شود.

سعی کنید

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

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

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

ارجاعات

• بریهام، E.O. (1988). * سریع تبدیل و برنامه های آن. سالن پادشاهی.
• Cooley، J.W. و توکل، J.W. (1965). الگوریتمی برای محاسبه ماشین سری چهار نفره پیچیده. * مفاهیم قطع عضو*، 19 (90)، 297-301.
• چهارم، جی. (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. ۲۰۰۳. یک الگوریتم جستجوی صوتی صنعتی. * تایید 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) آزاد کنید.