تحويل فورييه السريع (FFT)
الشكل 1: يؤدي تراكب التذبذب الأساسي (باللون الأصفر) مع التوافقية الثالثة (باللون الفيروزي) إلى تكوين إشارة تقترب بالفعل من الموجة المستطيلة (باللون الأحمر).
الشكل 2: تؤدي إضافة التوافقية الخامسة إلى تحسين التقريب إلى الموجة المستطيلة.
الشكل 3: الطيف الترددي للإشارة المستطيلة المركبة من التذبذب الأساسي والتوافقيات العليا
الشكل 1: يؤدي تراكب التذبذب الأساسي (باللون الأصفر) مع التوافقية الثالثة (باللون الفيروزي) إلى تكوين إشارة تقترب بالفعل من الموجة المستطيلة (باللون الأحمر).
الشكل 2: تؤدي إضافة التوافقية الخامسة إلى تحسين التقريب إلى الموجة المستطيلة.
الشكل 3: الطيف الترددي للإشارة المستطيلة المركبة من التذبذب الأساسي والتوافقيات العليا
الشكل 1: يؤدي تراكب التذبذب الأساسي (باللون الأصفر) مع التوافقية الثالثة (باللون الفيروزي) إلى تكوين إشارة تقترب بالفعل من الموجة المستطيلة (باللون الأحمر).
الشكل 2: تؤدي إضافة التوافقية الخامسة إلى تحسين التقريب إلى الموجة المستطيلة.
الشكل 3: الطيف الترددي للإشارة المستطيلة المركبة من التذبذب الأساسي والتوافقيات العليا
تحويل فورييه السريع (FFT)
وضع عالم الرياضيات الفرنسي جان باتيست جوزيف فورييه أسس تحليل فورييه، ونشرها عام 1822 في مؤلفه Théorie analytique de la chaleur (النظرية التحليلية للحرارة). وفي معالجة إشارات الرادار، تُحلَّل خصائص الإشارات الصدوية المستقبلة، ومنها السعة والطور. ويمكن، على سبيل المثال، تحديد تردد دوبلر من تغير الطور بين الأصداء المتتالية. ولهذا الغرض، تُحوَّل قيم الإشارة المسجلة زمنيًا إلى المجال الترددي باستخدام تحويل فورييه.
أصبح تحويل فورييه من الأساليب الأساسية في معالجة الإشارات، لأن شكل الموجة في الصدى الراداري يحتوي على معلومات عديدة. ويتيح تحويل فورييه تمثيل هذه المعلومات في المجال الترددي، بحيث يمكن استخدامها في المعالجة الحاسوبية اللاحقة.
تحويل فورييه طريقة رياضية تتيح تحليل الإشارة إلى مكوناتها الترددية. ويمكن وصف هذه المكونات باستخدام دوال الجيب وجيب التمام ذات الترددات والأطوار والسعات المختلفة. وبالنسبة إلى الإشارات المأخوذة عيناتها رقميًا، يُستخدم تحويل فورييه المتقطع (DFT). أما تحويل فورييه السريع (FFT) فهو خوارزمية فعالة للغاية لحساب تحويل فورييه المتقطع.
توضح مجموعة الرسوم المجاورة، باستخدام متسلسلة فورييه، كيف يمكن تقريب إشارة مستطيلة دورية عن طريق تراكب التذبذب الأساسي وتوافقياته الفردية العليا. ومع إضافة المزيد من التوافقيات المناسبة، يتحسن التقريب إلى الشكل المستطيل. ويمكن عرض الطيف الترددي لإشارة ما في جدول يتضمن قيم التردد والسعة. وتُعد هذه البيانات مناسبة جدًا للمعالجة الحاسوبية اللاحقة.
طُوِّرت خوارزميات مختلفة لحساب تحويل فورييه المتقطع بكفاءة، مثل خوارزمية Cooley–Tukey وخوارزمية Sande–Tukey. وفي بعض التطبيقات، تُستخدم أيضًا طريقة إعادة ترتيب البيانات المعروفة باسم Bit-Reversing (عكس ترتيب البتات). ومن التطبيقات الأخرى الالتفاف السريع. ففي هذه الطريقة، لا تُجرى عملية الالتفاف بين إشارتين مباشرةً في المجال الزمني، بل تُحوَّل الإشارتان أولًا إلى المجال الترددي، ثم تُضربان معًا في هذا المجال، وبعد ذلك يُجرى التحويل العكسي إلى المجال الزمني. ويمكن لهذه الطريقة أن تقلل الجهد الحسابي بدرجة كبيرة.
يتطلب الحساب المباشر لتحويل فورييه المتقطع عددًا كبيرًا من العمليات الحسابية عند زيادة عدد العينات. ويُعد تحويل فورييه السريع خوارزمية تتيح حساب تحويل فورييه المتقطع بسرعة وكفاءة أكبر بكثير. ويتحقق ذلك من خلال:
- تقسيم تحويل كبير إلى عمليات حسابية جزئية أصغر،
- إعادة استخدام النتائج الوسيطة المحسوبة سابقًا،
- تقليل العدد الإجمالي للعمليات الحسابية المطلوبة.
عند وجود N من العينات، يزداد الجهد الحسابي للتحويل المباشر لفورييه المتقطع تقريبًا بما يتناسب مع مربع عدد العينات. أما في خوارزميات تحويل فورييه السريع الشائعة، فيزداد الجهد الحسابي تقريبًا بنسبة تتناسب مع N · log2(N). ولذلك، عند معالجة كميات كبيرة بما يكفي من البيانات، قد يحتاج تحويل فورييه السريع إلى أقل من جزء من مئة من زمن الحساب المباشر. وباستخدام تحويل فورييه السريع، يمكن استخراج المكونات الترددية المميزة للأصداء الرادارية. ويمكن تخزين هذه الخصائص باستخدام كمية صغيرة نسبيًا من البيانات، والاستفادة منها في التعرف الآلي على الأهداف للتمييز بين أنواعها المختلفة.
الأسس الرياضية: www.mathepower.com
للمزيد من المعلومات: www.iti.fh-flensburg.de
Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/;
The Design and Implementation of FFTW3, Proceedings of the IEEE 93 (2), 216–231 (2005).
المؤلف: Christian Wolff، الترجمة: حازم كامل