تحويل فورييه. الصيام والغاضب

في كثير من الأحيان ، عند تطوير الخوارزميات ، نواجه الحد الأقصى من التعقيد الحسابي ، والذي يبدو أنه من المستحيل التغلب عليه. تحويل فورييه له تعقيد $$$O (n ^ 2)$ ونسخة سريعة ، تم اقتراحها في عام 1805 تقريبًا بواسطة House ¹ (وتم اختراعها عام 1965 بواسطة James Cooley و John Tukey) $$$O (nlog (n))$ . في هذه المقالة ، أود أن أوضح لك أنه يمكنك الحصول على نتائج التحويل في وقت خطي $$$O (n)$ أو حتى تحقيق صعوبة مستمرة $$$O (1)$ تحت ظروف معينة موجودة في مشاكل حقيقية.


عندما واجهت مهمة كتابة برنامج لتحليل وظائف نقل أنظمة الصوت في الوقت الفعلي ، تحولت ، مثل أي شخص آخر ، أولاً إلى تحويل سريع. كان كل شيء على ما يرام ، ولكن مع الحجم الكبير للإطار الزمني ، أصبح تحميل وحدة المعالجة المركزية كبيرًا بشكل غير لائق ويجب القيام بشيء ما. تقرر إيقاف التحول مؤقتًا ودراسته مرة أخرى ، وفي الوقت نفسه البحث عن طرق لحل المشكلة. دعنا نعود إلى التحول الأصلي لجوزيف فورييه ² :

$$

$$f (x) = \ sum \ limit _ {- \ infty} ^ {+ \ infty} c_ke ^ {2 \ pi ikx / T} \\ c_k = \ frac {1} {T} \ int \ limit_0 ^ Tf ( x) e ^ {- 2 \ pi ikx / T} dx$$

سننظر بعناية في ما يجري هنا. كل قيمة الإخراج في مجال التردد $$$c_k$ هو مجموع جميع القيم المدخلة للإشارة $$$f (x)$ مضروبا في $$$e ^ {- 2 \ pi ikx / T}$ . لإجراء عمليات حسابية ، نحتاج إلى استعراض جميع بيانات الإدخال لكل قيمة مخرجات ، أي لتحقيق تلك $$$n ^ 2$ العمليات.

تخلص من n

دعني أذكرك أن المهمة كانت في البداية تحليل البيانات الصوتية في الوقت الفعلي. للقيام بذلك ، يتم تعبئة نافذة الوقت المحددة (أساسًا مخزن مؤقت) من الحجم N بالبيانات بتردد f _d مطابق لتردد أخذ العينات. مع الفترة T ، يتم تحويل بيانات الإدخال من نافذة الوقت إلى نافذة التردد. إذا نظرت إلى الأرقام الحقيقية ، فإن N يختلف من 2 ¹⁴ (16 384) إلى 2 ¹⁶ (65 536) عينات (القيم موروثة من FFT ، حيث يجب أن يكون حجم النافذة قوة لاثنين). الوقت T = 80 مللي ثانية (12.5 مرة في الثانية) ، والذي يسمح لك بمشاهدة التغييرات بشكل مريح للغاية وعدم التحميل الزائد على وحدة المعالجة المركزية ووحدة معالجة الرسومات. تردد أخذ العينات f _{d هو} المعيار وهو 48 كيلو هرتز. دعنا نحسب مقدار البيانات في نافذة الوقت تتغير بين الأبعاد. خلال وقت T ، يدخل المخزن المؤقت $$ عينات. وبالتالي ، يتم تحديث فقط 5 ٪ إلى 23 ٪ من البيانات في النافذة. في أسوأ الحالات ، ستقع 95٪ (وفي أحسن الأحوال 73٪ ، وهي أيضًا كثيرة!) من العينات المعالجة في التحويل مرارًا وتكرارًا ، على الرغم من حقيقة أنها قد تمت معالجتها بالفعل في التكرارات السابقة.

سوف يرفع القارئ اليقظ في تلك اللحظة يده ويقول: "انتظر ، ولكن ماذا عن المعامل $$$e ^ {- 2 \ pi ikx / T}$ ؟ بعد كل شيء ، مع كل تحول جديد ، سيتم تحديد موقع نفس البيانات في المواضع الجديدة للسلسلة ، ونتيجة لذلك توجد معاملات مختلفة؟ " مقابل كل خمسة لرعايتهم ، دعونا نتذكر تفاصيل مهمة في التحول الذي غالباً ما ينسى. في دراسة القيم الوظيفية $$$f (t)$ خلال الفترة الفاصلة من 0 إلى t ، تُعتبر الوظيفة دورية ، مما يسمح لك بتحويل الوظيفة إلى اليسار أو اليمين بدون ألم في الوقت المناسب. نتيجة لذلك ، لدينا كل الحق في عدم إدراج قيمة جديدة في النهاية وحذف القيمة القديمة من البداية ، ولكن لاستبدال البيانات في المخزن المؤقت دوريًا.

من أجل الوضوح ، يمكنك الكتابة في شكل جدول عن كيفية تغيير المخزن المؤقت:

ر = 0	و (0)	و (1)	و (2)	و (3)	و (4)	و (5)	و (6)	و (7)	و (8)	و (9)
ر = 1	و (10)	و (1)	و (2)	و (3)	و (4)	و (5)	و (6)	و (7)	و (8)	و (9)
ر = 2	و (10)	و (11)	و (2)	و (3)	و (4)	و (5)	و (6)	و (7)	و (8)	و (9)
ر = 3	و (10)	و (11)	و (12)	و (3)	و (4)	و (5)	و (6)	و (7)	و (8)	و (9)
ر = 4	و (10)	و (11)	و (12)	و (13)	و (4)	و (5)	و (6)	و (7)	و (8)	و (9)

يمكنك كتابة كيف يتغير التحول في الوقت من t ₁ إلى t ₂ :

$$

$$F_t = F_ {t-1} + \ Delta F \\ \ Delta F: \ Delta c_k = \ frac {1} {T} \ int \ limit_ {t_1} ^ {t_2} (f_t (x) - f_ { t-1} (x)) e ^ {- 2 \ pi ikx / T} dx$$

القيمة $$$F_ {t-1} (x)$ هو نتيجة التحويل السابق ، وتعقيد الحساب $$$\ Delta f (x)$ لا يعتمد على حجم نافذة الوقت ، وبالتالي ، فهو ثابت. نتيجة لذلك ، سيكون تعقيد التحويل $$$O (n)$ ^* لأن كل ما تبقى بالنسبة لنا هو الذهاب من خلال نافذة التردد مرة واحدة وتطبيق التغييرات على عينات T التي تغيرت على مدار الوقت. وأود أيضا أن ألفت انتباهكم إلى حقيقة أن الاحتمالات $$$e ^ {- 2 \ pi ikx / T}$ يمكن حسابها مقدمًا ، مما يعطي ربحًا إضافيًا في الإنتاجية ، وتبقى عمليتان فقط في الدورة: طرح الأرقام الحقيقية وضرب الرقم الحقيقي برقم معقد ، في الواقع العملي ، تكون كلتا العمليتين بسيطة ورخيصة.

لإكمال الصورة ، يبقى فقط للإشارة إلى الحالة الأولية ، ولكن هنا كل شيء بسيط:

$$

$$F_0 (x) = 0$$

* - بالطبع ، سيظل التعقيد النهائي للتحول كله كذلك $$$O (n ^ 2)$ ، ولكن سيتم تنفيذه تدريجياً ، على التكرار n ، بينما يتم تحديث المخزن المؤقت. $$$O (n)$ - هذا هو تعقيد تحديث البيانات ، ولكن هذا هو بالضبط ما نحتاجه (عند استخدام FFT ، تعقيد كل تحويل $$$O (nlog (n))$ )

ولكن ماذا لو كنت حفر أعمق. أو تخلص من الثانية ن

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

الآن دعنا نحلل مجموعة البيانات الناتجة ، بالنظر إلى ظروف المشكلة. لدينا مجموعة من الأعداد المركبة ، يصف كل منها سعة وطور التذبذبات بتردد معين. يمكن تحديد التردد بالصيغة: $$$f [j] = j \ frac {fd} {N}$ ل $$$j <\ frac {N} {2}$ . لنقم بتقييم خطوة نافذة التردد على بياناتنا: $$$\ Delta f = \ frac {fd} {N}$ ل N = 2 ¹⁴ : 2.93 هرتز (و 2 ¹⁶ : 0.73 هرتز). وبالتالي ، في المدى من 1 كيلو هرتز إلى 2 كيلو هرتز نحصل على 341 نتيجة. حاول بشكل مستقل تقييم مقدار البيانات التي ستكون في النطاق من 8 كيلو هرتز إلى 16 كيلو هرتز لـ N = 65536. هل هناك الكثير ، أليس كذلك؟ الكثير! هل نحتاج إلى الكثير من البيانات؟ بالطبع ، في مشاكل عرض خصائص تردد أنظمة الصوت ، الجواب هو لا. ومن ناحية أخرى ، للتحليل في المنطقة ذات التردد المنخفض ، هناك خطوة صغيرة مفيدة للغاية. لا تنس أنه لا يزال هناك جدول زمني قبل أن هذه المجلدات ( $$$\ frac {N} {2}$ ) قم بالتحويل إلى نموذج يمكن قراءته من قبل الإنسان (حساب أو تجانس أو تجانس) وعرضها على الشاشة. وعلى الترددات العالية ، وحتى مع وجود شاشة 4K وعرض الرسم البياني في وضع ملء الشاشة مع محور التردد اللوغاريتمي ، سيتحول حجم الخطوة بسرعة إلى أقل بكثير من 1 بكسل.

من خلال التجربة ، يمكنك معرفة أنه يكفي الحصول على 48 نقطة فقط لكل أوكتاف ، ولكي نحصل على بيانات أكثر سلاسة وأكثر متوسطًا ، أقترح التوقف عند 96. في نطاق تردد الصوت من 20 هرتز إلى 20 كيلو هرتز ، يسهل حساب 10 أوكتافات فقط: 20 ، 40 ، 80 ، 160 ، 320 ، 640 ، 1280 ، 2560 ، 5120 ، 10240 ، 20480 ، يمكن تقسيم كل منها إلى عدد معين من النطاقات الفرعية (لا تنس أن القسم يجب أن يتم هندسيًا وليس حسابيًا) ، وبالتالي ، فإن إجراء التحويل هو فقط أكثر من 960 ترددات للحصول عليها Performan أنه في 16 ... 65 مرات أصغر من النسخة الأصلية.

وبالتالي ، من خلال الجمع بين كلا النهجين ، نحصل على التعقيد المستمر لخوارزمية تحديث البيانات $$$O (1)$ .

العسل التربيع وملعقة من القطران

الآن يمكننا أن نقول ذلك بأمان من التعقيد $$$O (n ^ 2)$ وصلنا إلى التعقيد $$$O (1)$ باستخدام اثنين من الخارقة الحياة البسيطة:

• بعد تحليل المشكلة ، لاحظنا أن البيانات يتم إضافتها تدريجيًا ، وأن فترة التحديث الكامل لإطار الوقت أعلى بكثير من فترة التحولات واستمرت في حساب الفرق في تحويل فورييه.
• انتقل من الخطوة الحسابية في نافذة التردد إلى الحد فقط حسب القيم المحددة ، والتي يمكن أن تقلل بشكل كبير عدد التحويلات.

ولكن ، بطبيعة الحال ، فإن الحياة ستكون حقا خرافة ، إن لم يكن واحدة ولكن. سمح لنا تطبيق هذين النهجين بإفراغ وحدة المعالجة المركزية حقًا بحيث نتصور أنه يحسب تحويل فورييه ويعرض النتائج على الشاشة حتى مع $$$N = 2 ^ {20}$ كان صعبا. لكن العقوبة لم تبق في انتظارها عندما تكون إشاراتك في الواقع غير دورية (وهذا أمر ضروري للحصول على نتائج التحويل الصحيحة) ولا يمكن تحديد حجم النافذة المناسب ، يصبح من الضروري استخدام وظائف النافذة المختلفة ، التي لم تعد تسمح لك باستخدام الخطوة الأولى بالكامل. وقد أظهرت الممارسة أن استخدام وظائف النافذة أمر بالغ الأهمية في دراسة الإشارات بتردد أقل من $$$0،1f_d$ . في الترددات العالية ، يخفف عدد الفترات التي تقع في نافذة الوقت بشكل كبير من التشوهات الناشئة عن وجود فجوة من الدرجة الأولى (بين f (0) و f (N-1)) في الوظيفة الأصلية.

في النهاية ، رفضت أيضًا الخطوة الثانية وعدت إلى FFT ، لأن المكسب في هذه المهمة كانت صغيرة بالفعل.

في الختام

يمكن تطبيق الطريقة الأولى إذا كانت بياناتك ذات طبيعة دورية واضحة وتحتاج إلى تحليل مع مرور الوقت باستخدام نافذة زمنية كبيرة ، والتي ، على ما أذكر ، لا يجب أن تكون على درجة 2 ، أي أي رقم طبيعي.
ينطبق الأسلوب الثاني (حتى مع مراعاة وظائف النافذة) إذا تم تحليل مجموعة معينة فقط من الترددات في البيانات.

للأسف ، بالنسبة لي في هذه المشكلة ، ظل هذا مجرد القليل من التسلية الرياضية ، لكنني آمل أن يلهمك ذلك لدراسة الخوارزميات الأخرى في أيام العطلات من حيث التغييرات في بيانات الإدخال مع مرور الوقت :)

الأدب

1. Cooley - Tukey FFT خوارزمية
2. E.A. Vlasova Rows. دار نشر MSTU سميت باسم N.E.Bauman. موسكو 2002

الصورة مأخوذة من المانجا بواسطة ميشيو شيبويا. "الرياضيات المثيرة. تحليل فورييه