ففت وور

الموسوعة الحرة
ففت وور
المطور(ون)ماتيو فريجو وستيفن جي جونسون
الإصدار الأولي24 مارس 1997 ( 1997-03-24 )
إصدار مستقر
3.3.10 [1]  / 15 سبتمبر 2021 ؛ منذ 3 سنوات ( 15 سبتمبر 2021 )
مستودع
  • github.com/FFTW/fftw3
مكتوب فيج ، أوكامل
يكتبالبرمجيات الرقمية
رخصةGPL ، تجاري
موقع إلكترونيwww.fftw.org 

أسرع تحويل فورييه في الغرب ( FFTW ) هي مكتبة برمجيات لحساب تحويلات فورييه المنفصلة (DFTs) طورها ماتيو فريجو وستيفن جي جونسون في معهد ماساتشوستس للتكنولوجيا . [2] [3] [4]

FFTW هو أحد أسرع تطبيقات البرمجيات الحرة لتحويل فورييه السريع (FFT). فهو ينفذ خوارزمية FFT للمصفوفات ذات القيم الحقيقية والمعقدة ذات الحجم والأبعاد التعسفية.

مكتبة

يحول FFTW البيانات بسرعة من خلال دعم مجموعة متنوعة من الخوارزميات واختيار الخوارزمية (تحليل معين للتحويل إلى تحويلات أصغر) التي يقدرها أو يقيسها لتكون مفضلة في الظروف المعينة. إنه يعمل بشكل أفضل على مجموعات من الأحجام ذات العوامل الأولية الصغيرة ، حيث تكون قوى الاثنين هي الأمثل والأعداد الأولية الكبيرة هي أسوأ حالة (ولكن لا تزال O ( n log n )). لتحليل التحويلات ذات الأحجام المركبة إلى تحويلات أصغر، فإنه يختار من بين العديد من المتغيرات لخوارزمية Cooley–Tukey FFT (المقابلة لعوامل مختلفة و/أو أنماط وصول مختلفة للذاكرة)، بينما بالنسبة للأحجام الأولية فإنه يستخدم إما خوارزمية FFT الخاصة بـ Rader أو Bluestein . [2] بمجرد تقسيم التحويل إلى تحويلات فرعية بأحجام صغيرة بدرجة كافية، يستخدم FFTW تحويلات FFT غير ملفوفة مبرمجة بشكل ثابت لهذه الأحجام الصغيرة التي تم إنتاجها (في وقت التجميع ، وليس في وقت التشغيل ) عن طريق إنشاء التعليمات البرمجية ؛ تستخدم هذه الروتينات مجموعة متنوعة من الخوارزميات بما في ذلك متغيرات كولي-توكي، وخوارزمية رادر، وخوارزميات تحويل فورييه السريع للعوامل الأولية . [2]

بالنسبة لعدد كبير بما فيه الكفاية من التحويلات المتكررة، فمن المفيد قياس أداء بعض أو كل الخوارزميات المدعومة على حجم المصفوفة والمنصة المحددة . يمكن تخزين هذه القياسات، التي يشير إليها المؤلفون باسم "الحكمة"، في ملف أو سلسلة لاستخدامها لاحقًا.

تحتوي FFTW على "واجهة خبير" تهدف إلى "الكشف قدر الإمكان عن المرونة في بنية FFTW الأساسية". وهذا يسمح، من بين أمور أخرى، بإجراء تحويلات متعددة الأبعاد وتحويلات متعددة في مكالمة واحدة (على سبيل المثال، حيث يتم تداخل البيانات في الذاكرة).

يدعم FFTW بشكل محدود التحويلات غير المنظمة (باستخدام إصدار واجهة تمرير الرسائل (MPI)). تتسبب إعادة ترتيب البيانات في تكلفة إضافية، والتي من غير السهل تجنبها بالنسبة للتحويلات في المكان ذات الحجم والأبعاد التعسفية. لم يتم توثيق التحويلات التي تكون فيها هذه التكلفة الإضافية كبيرة.

تم ترخيص FFTW بموجب رخصة جنو العمومية . كما تم ترخيصها تجاريًا (بتكلفة تصل إلى 12500 دولار) بواسطة معهد ماساتشوستس للتكنولوجيا [5] ويتم استخدامها في حزمة مصفوفات MATLAB التجارية [6] لحساب تحويلات فورييه السريعة. تمت كتابة FFTW بلغة C ، ولكن توجد واجهات Fortran و Ada ، بالإضافة إلى واجهات لبعض اللغات الأخرى. في حين أن المكتبة نفسها هي C، فإن الكود يتم إنشاؤه في الواقع من برنامج يسمى ' genfft'، والذي تمت كتابته بلغة OCaml . [7]

في عام 1999، فاز برنامج FFTW بجائزة JH Wilkinson للبرمجيات الرقمية .

انظر أيضا

مراجع

  1. ^ "ملاحظات إصدار FFTW" . تم الاسترجاع في 16 سبتمبر 2021 .
  2. ^ abc Frigo M, Johnson SG (فبراير 2005). "تصميم وتنفيذ FFTW3" (PDF) . وقائع معهد مهندسي الكهرباء والإلكترونيات . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. S2CID  6644892. 
  3. ^ Frigo M, Johnson SG (1998). "FFTW: An adaptive software architecture for the FFT". Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181) . المجلد 3. ص 1381-1384. CiteSeerX 10.1.1.47.8661 . doi :10.1109/ICASSP.1998.681704. ISBN  978-0-7803-4428-0. S2CID  12560207.
  4. ^ جونسون إس جي، فريجو إم (سبتمبر 2008). "الفصل 11: تطبيق تحويلات فورييه السريعة في الممارسة العملية". في سي إس بوروس (المحرر). تحويلات فورييه السريعة . هيوستن، تكساس: كونكشنز: جامعة رايس.
  5. ^ "FFTW - أسرع تحويل فورييه في الغرب | مكتب ترخيص التكنولوجيا التابع لمعهد ماساتشوستس للتكنولوجيا". tlo.mit.edu . تم الاسترجاع في 2023-02-07 .
  6. ^ "تحويلات فورييه المحدودة الأسرع في MATLAB". www.mathworks.com . تم الاسترجاع في 2014-03-24 .
  7. ^ "الأسئلة الشائعة حول FFTW"
  • الموقع الرسمي
تم الاسترجاع من "https://en.wikipedia.org/w/index.php?title=FFTW&oldid=1230991906"
Original text
Rate this translation
Your feedback will be used to help improve Google Translate