ما الذي يُظهره لك في الواقع

المسألة

اعزفوا على البيانو "ك" و "إي" معاً أذنك تسمع صوت واحد ولكن هذا الصوت تواتران زائدان: 261.6 هرتز و 329.6 هرتز. كوخك الجسدي يفصلهم خلايا شعر مختلفة تتردد في ترددات مختلفة ترسل إشارات مميزة إلى دماغك.

الـ "فوريير" السريع يفعل نفس الشيء لكن مع الأرقام بدلاً من خلايا الشعر أعطها إشارة (سلسلة من عينات الضخ عبر الزمن) وتعيد قائمة من الترددات وقوامها. وهو يجيب: ** ما هي الترددات الموجودة، وكم من كل منها؟**

ما يحدث في الواقع

والإشارة التي عينت بمرور الوقت هي قائمة بالأرقام: السعة في كل نقطة من نقاط العينة. تسجيل واحد من الثانية عشرة بـ 100 44 هرتز هو 100 44 شخص وتصف هذه الأرقام الإشارة في مجال ** الوقت** - السعة بوصفها وظيفة وقت.

وتحوّل فرقة العمل هذه إلى مجال الترددات** - السعة كوظيفة من وظائف التردد. نفس المعلومات، تمثيل مختلف مثل التبديل بين الإحداثيات الكارتيزية والأعمدة: لا شيء يُخلق أو يُدمر، فقط يُعاد تفسيره.

The mathematical core: every periodic signal can be written as a sum of sine and cosine waves at different frequencies. هذه نظرية (فوريير) (1807). ويحسب هذا المبلغ معامل هذا المبلغ - أي مدى تردد كل تردد في الإشارة.

لماذا "فاست"

الطريقة الساذجة في حساب التحول الرابع تتطلب N2 العمليات لعينات N. لـ1024 عينة، هذا حوالي مليون عملية The cooley-Tukey algorithm (1965) reduces this to N ·log2(N) — about 10,000 operations for the same input. سرعة 100x. لملايين العينات، السرعة هي 50,000x.

الخدعة: إنقسام نقطة N إلى تحولين من نقطة N/2، على سبيل التصحيح. هذا يتطلب أن تكون (إن) قوّة 2 (أو تمدّد بأصفار) كل جزء يقسم المشكلة "عملية "البترفلي" تجمع بين النصفين:

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

حيث تكون دبلوماً معقداً (دورة في الطائرة المعقدة). نفس الخلاصتين الفرعيتين تعطيانكم نقطتين ناتجتين وهذا هو السبب في أن الخوارزمية هي "الفاسد" - أنها تعيد استخدام كل حساب مرتين.

تنفيذ (بي جي تي إكس) هو دفتر نسيج (كولي توكي) 40 خطاً من (جافاسكريبت) كتبناه من الصفر بدلا من استيراد مكتبة لأننا أردنا للطلاب أن يكونوا قادرين على قراءة المصدر وفهم كل خط.

ما تعنيه تلك البارزات

عندما ترى محلل طيف - الحانات تقفز إلى الموسيقى - كل حانة تمثل سلة تردد. والطول هو حجم هذه الترددات (الثابتة) في الإشارة الحالية.

• ** موجة لامعة صافية** تنتج حانة واحدة طويلة بتواترها ولا شيء آخر.
• ** تُنتج موجة مربعة** قضباناً في الوئام الجوهري وكل وئام غريب (3، 5، 7)، تتناقص إلى 1/n. هذا هو السبب في أن الأمواج المربعة تبدو "الضبابية" تحتوي على طاقة عالية التردد.
• ** تصدر الضوضاء البيضاء** قضبان ذات ارتفاع متساو تقريبا في كل مكان. كل تردد موجود على قدم المساواة.
• ** صوت بشري** ينتج أساسي (اللعبة التي تسمعها) بالإضافة إلى المكوّنات - ذروة صامتة من شكل قصتك الصوتية التي تميز النذور.

لماذا (إدجز ماتر)

هناك صيد إف تي يفترض أن الإشارة تكرر للأبد لكن عينتنا محدودة إنها تبدأ وتتوقف إذا لم تكن الإشارة عند الصفر في كلا النقطتين النهائيتين فإن الإنقطاع المفاجئ يخلق محتوى اصطناعي عالي التردد هذا يُدعى التسرب الغريب**.

The fix: multiply the signal by a window function that tapers smoothly to zero at the edges. النوافذ المشتركة:

• ** Hann** (cosine bell): Good general purpose, loses some frequency resolution
• مثل (هان) لكن لا تصل إلى الصفر عند الحواف، بل إلى حد أفضل
• ** Blackman**: narrower main lobe, better sidelobe suppression, loses more frequency resolution

الخيار دائماً هو تبادل بين قرار التردد (كيف يمكنك تحديد تردد) والتسرب الطيفي (كم تنزف الطاقة إلى صناديق الجيران). لا يوجد نافذة مثالية وهذا نتيجة لمبدأ عدم اليقين - لا يمكن أن يكون لديك معرفة دقيقة تعسفية بكل من الوقت والتواتر في آن واحد.

حيث يعيش FFT

أنت تتفاعل مع نتائج الـ إف تي باستمرار:

• ** MP3 و AAC compression**: تحويل المجال الصوتي إلى النطاق الترددي، ترددات الذكاء دون عتبة السمع، الضغط على ما تبقى. التحول هو الأساس الكامل للضغط الصوتي الضائع.
• ** ضغط JPEG**: تحول النسخة 2D (DCT) 8 x8 كتل من البكسل إلى النطاق الترددي، وهي كمية تحدد المكونات العالية التردد. لهذا يبدو (جي بي جي) القطع الأثرية كقطع.
• ** WiFi and 5G**: OFDM encoding divideds data across many frequency sub-carriers. The FFT converts between time-domain transmission and frequency-domain data symbols.
• ** التصوير بالرنين المغناطيسي**: الإشارة الخام من جهاز تصوير بالرنين المغناطيسي موجودة في الفضاء الترددي. إعادة تشكيل الصورة المكانية حرفياً، كل رنين رنين من الرنين المغناطيسي الذي رأيته هو تحول عكسي لـ(فوريير).
• Shazam: computes the spectrogram (FFT over sliding windows), extracts tops, matches the pattern against a database. فرقة التدخل السريع هي الخطوة الأولى في التعرف على كل أغنية.

خوارزمية عمرها 60 عاماً في جيبك تدير بلايين المرات يومياً.

{widget:function-plot}}

حاول

إفتحي (بي بي جي) و إختاري مولد (سبكتروم) تولد موجة مربعة. انظر إلى القضبان سترى التناسق الغريب يسقط كـ1n اتجهوا إلى منشار - الآن جميع المتجانسات حاضرة، وسقطوا في الساعة 1/n. التحول إلى الضوضاء - طيف مسطح، كل تردد على الأرجح.

غير وظيفة النافذة. شاهدْ كَمْ هان يَسْلسُ الطيفَ بكلفة ذروةِ أوسعِ. تحويل إلى بلاكمان - الذروة الأضيق ولكن الجانب السفلي.

أنت لا تقرأ عن الـ إف تي أنت تُقيسُ الإشاراتَ وتُلاحظُ ما يُظهره التحول هذا هو الفرق بين المعرفة والتفاهم.

المراجع

• Brigham, E.O. (1988). * The Fast Fourier Transform and Its Applications*. قاعة التصوير.
• Coley, J.W. " Tukey, J.W. (1965). Algorithm for the Machine Calculation of Complex Fourier Series. * الرياضيات الحاسوبية*، 19(90)، 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. (فيرمين ديدو).
• Harris, F.J. (1978). On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform. * مقترحات المعهد الدولي للتعليم*، 66 (1)، 51-83.
• Oppenheim, A.V. " Schafer, R.W. (2009). * تجهيز الإشارة في الوقت المحدد* )الطبعة الثالثة(. قاعة التصوير.
• Shannon, C.E. (1949). الاتصال في ظل النواة. * عمليات الامتحانات الأولية*، 37 (1)، 10-21.
• Smith, S.W. (1997). * دليل العلماء والمهندسين لتجهيز الإشارات الرقمية* كاليفورنيا نشر تقني.
• Wang, A., et al. (2003). باحثة صناعية - صناعية * عائدات ISMIR 2003*. (خوارزمية البصمات الصوتية)
• Wallace, G.K. (1991). The JPEG still Picture Compression Standard. * البلاغات المقدمة من اللجنة الاستشارية لشؤون الإدارة والميزانية*، 34 (4)، 30-44.

---

FFT (PG0X) هو تنفيذ نصف قطري رائع مع (هان) و(هامينغ) و(بلاكمان) جربها مجاناً في Pinepaper.studio/editor.*