تحويل فورييه السريع

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 58 صور
الموسوعة الحرة

مثال على بنية خوارزمية تحويل فورييه السريع (FFT)، باستخدام تجزئة إلى تحويلات فورييه السريع بنصف الحجم
تحليل فورييه منفصل لمجموع موجات جيب التمام عند الترددات 10، 20، 30، 40، و50  هرتز
التمثيل الزمني (أعلاه) والتمثيل الترددي (أدناه) لنفس الإشارة، حيث يمكن الحصول على التمثيل السفلي من التمثيل العلوي عن طريق تحويل فورييه.

تحويل فورييه السريع ( FFT ) هو خوارزمية تحسب تحويل فورييه المنفصل (DFT)، أو معكوسه (IDFT)، لتسلسل . يحول تحويل فورييه الإشارة من مجالها الأصلي (غالباً الزمن أو المكان) إلى تمثيل في مجال التردد والعكس صحيح.

يُحسب تحويل فورييه المنفصل (DFT) بتحليل سلسلة من القيم إلى مكونات ذات ترددات مختلفة. [ 1 ] تُعد هذه العملية مفيدة في العديد من المجالات، ولكن حسابها مباشرةً من التعريف غالبًا ما يكون بطيئًا جدًا وغير عملي. يُحسب تحويل فورييه السريع (FFT) هذه التحويلات بسرعة عن طريق تحليل مصفوفة DFT إلى حاصل ضرب عوامل متفرقة (معظمها أصفار). [ 2 ] ونتيجةً لذلك، ينجح في تقليل تعقيد حساب DFT منيا(ن2){\textstyle O(n^{2})}، وهو ما ينشأ إذا طبقنا تعريف DFT ببساطة، علىيا(نسجل⁡ن){\textstyle O(n\log n)}حيث n هو طول المتتالية. قد يكون الفرق في السرعة هائلاً، خاصةً بالنسبة للمتتاليات الطويلة حيث قد يصل n إلى الآلاف أو الملايين.

بما أن تحويل فورييه السريع (FFT) هو مجرد إعادة صياغة جبرية للمصطلحات داخل تحويل فورييه المنفصل (DFT)، فإن كلاً من DFT وFFT يؤديان عمليات متكافئة رياضياً وقابلة للتبادل، بافتراض حساب جميع المصطلحات بدقة لا نهائية. مع ذلك، في حال وجود خطأ التقريب ، فإن العديد من خوارزميات FFT تكون أكثر دقة من تقييم تعريف DFT بشكل مباشر أو غير مباشر. توجد العديد من خوارزميات FFT المختلفة التي تستند إلى نطاق واسع من النظريات المنشورة، بدءاً من حساب الأعداد المركبة البسيط وصولاً إلى نظرية الزمر ونظرية الأعداد . تعتمد أشهر خوارزميات FFT على تحليل العدد n إلى عوامله الأولية ، ولكن توجد خوارزميات FFT أخرى تستخدم عوامل أخرى.يا(نسجل⁡ن){\displaystyle O(n\log n)}التعقيد لجميع قيم n ، بما في ذلك القيم الأولية . تعتمد العديد من خوارزميات تحويل فورييه السريع (FFT) فقط على حقيقة أنهـ-2πأنا/ن{\textstyle e^{-2\pi i/n}}هو جذر أولي من الرتبة n للوحدة ، وبالتالي يمكن تطبيقه على التحويلات المماثلة على أي حقل منتهٍ ، مثل التحويلات العددية . ولأن التحويل العكسي لفورييه المنفصل (DFT) هو نفسه التحويل المنفصل لفورييه المنفصل (DFT)، ولكن بإشارة معاكسة في الأس وعامل 1/ n ، فإنه يمكن تكييف أي خوارزمية تحويل فورييه سريع (FFT) بسهولة معه.

تُستخدم تحويلات فورييه السريعة على نطاق واسع في تطبيقات الهندسة والموسيقى والعلوم والرياضيات. انتشرت الأفكار الأساسية لهذه التحويلات عام 1965، ولكن بعض الخوارزميات وُضعت منذ عام 1805. [ 1 ] في عام 1994، وصف جيلبرت سترانج تحويل فورييه السريع بأنه "أهم خوارزمية عددية في عصرنا"، [ 3 ] [ 4 ] وقد أُدرج ضمن أفضل 10 خوارزميات في القرن العشرين من قِبل مجلة IEEE للحوسبة في العلوم والهندسة . [ 5 ]

تاريخ

كان تطوير الخوارزميات السريعة لتحويل فورييه المنفصل (DFT) مُبشَّرًا به في عمل كارل فريدريش غاوس غير المنشور عام 1805 حول مدارات الكويكبين بالاس وجونو . أراد غاوس استقراء المدارات من خلال رصد عينات؛ [ 6 ] [ 7 ] وكانت طريقته مشابهة جدًا لتلك التي نشرها جيمس كولي وجون توكي عام 1965 ، واللذان يُنسب إليهما عمومًا اختراع خوارزمية تحويل فورييه السريع (FFT) الحديثة. مع أن عمل غاوس سبق حتى نتائج جوزيف فورييه عام 1822، إلا أنه لم يُحلل تعقيد الطريقة ، واستخدم في النهاية طرقًا أخرى لتحقيق الغاية نفسها.

بين عامي 1805 و1965، نُشرت بعض نسخ تحويل فورييه السريع (FFT) من قِبل مؤلفين آخرين. في عام 1932، نشر فرانك ييتس نسخته المسماة خوارزمية التفاعل ، والتي وفرت حسابًا فعالًا لتحويلات هادامارد ووالش . [ 8 ] لا تزال خوارزمية ييتس تُستخدم في مجال التصميم الإحصائي وتحليل التجارب. في عام 1942، نشر جي سي دانييلسون وكورنيليوس لانكزوس نسختهما لحساب تحويل فورييه المنفصل (DFT) لعلم البلورات بالأشعة السينية ، وهو مجال مثّل فيه حساب تحويلات فورييه عقبة كبيرة. [ 9 ] [ 10 ] في حين ركزت العديد من الطرق في الماضي على تقليل العامل الثابت لـيا(ن2){\textstyle O(n^{2})}أدرك دانييلسون ولانكزوس، من خلال الاستفادة من التناظرات في الحسابات، أنه يمكن استخدام الدورية وتطبيق حيلة المضاعفة لمضاعفة [ n ] بجهد يزيد قليلاً عن ضعف الجهد، على الرغم من أنهم، مثل غاوس، لم يجروا التحليل اللازم لاكتشاف أن هذا يؤدي إلىيا(نسجل⁡ن){\textstyle O(n\log n)}القياس. [ 11 ] في عام 1958، نشر آي جيه جود ورقة بحثية تُثبت خوارزمية تحويل فورييه السريع للعوامل الأولية التي تُطبق على تحويلات فورييه المنفصلة ذات الحجمن=ن1ن2{\textstyle n=n_{1}n_{2}}، أينن1{\displaystyle n_{1}}ون2{\displaystyle n_{2}}هي أعداد أولية فيما بينها. [ 12 ]

أعاد جيمس كولي وجون توكي اكتشاف هذه الخوارزميات السابقة بشكل مستقل [ 7 ] ، ونشرا خوارزمية FFT أكثر عمومية في عام 1965 قابلة للتطبيق عندما يكون n عددًا مركبًا وليس بالضرورة قوة للعدد 2، بالإضافة إلى تحليليا(نسجل⁡ن){\textstyle O(n\log n)}[ 13 ] خطرت الفكرة لتوكي خلال اجتماع للجنة الاستشارية العلمية للرئيس كينيدي ، حيث دار نقاش حول إمكانية رصد التجارب النووية التي يجريها الاتحاد السوفيتي عبر نشر أجهزة استشعار حول البلاد من الخارج. ولتحليل بيانات هذه الأجهزة، كان لا بد من استخدام خوارزمية تحويل فورييه السريع (FFT). وخلال نقاشه مع توكي، أدرك ريتشارد غاروِن إمكانية تطبيق الخوارزمية على نطاق واسع، ليس فقط في مسائل الأمن القومي، بل في طيف واسع من المسائل، بما فيها مسألة ذات أهمية مباشرة بالنسبة له، وهي تحديد دورية اتجاهات الدوران في بلورة ثلاثية الأبعاد من الهيليوم-3. [ 14 ] قدّم غاروِن فكرة توكي إلى كولي (وكلاهما كان يعمل في مختبرات واتسون التابعة لشركة IBM ) لتنفيذها. [ 15 ] نشر كولي وتوكي البحث في غضون ستة أشهر فقط. [ 16 ] بما أن توكي لم يكن يعمل في شركة IBM، فقد تم التشكيك في إمكانية الحصول على براءة اختراع للفكرة ودخلت الخوارزمية في المجال العام، الأمر الذي جعل من خلال ثورة الحوسبة في العقد التالي، FFT واحدة من الخوارزميات التي لا غنى عنها في معالجة الإشارات الرقمية .

تعريف

يتركx0،...،xن-1{\displaystyle x_{0},\ldots ,x_{n-1}}لتكن أعدادًا مركبة . يتم تعريف تحويل فورييه المنفصل (DFT) بالصيغة التالية:

Xك=∑م=0ن-1xمهـ-أنا2πكم/نك=0،...،ن-1،{\displaystyle X_{k}=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi km/n}\qquad k=0,\ldots ,n-1,}

أينهـأنا2π/ن{\displaystyle e^{i2\pi /n}}هو جذر أولي من الرتبة n للعدد 1.

يتطلب تقييم هذا التعريف بشكل مباشريا(ن2){\textstyle O(n^{2})}العمليات: يوجد n مخرجًا × k ، ويتطلب كل مخرج مجموع n حدًا. التحويل السريع لفورييه (FFT) هو أي طريقة لحساب نفس النتائج فييا(نسجل⁡ن){\textstyle O(n\log n)}تتطلب جميع خوارزميات تحويل فورييه السريع المعروفة عمليات.يا(نسجل⁡ن){\textstyle O(n\log n)}[ 17 ]​

لتوضيح مدى التوفير الذي توفره تقنية تحويل فورييه السريع (FFT)، ضع في اعتبارك عدد عمليات الضرب والجمع المعقدة لـن=4096{\textstyle n=4096}تتضمن عملية تقييم مجاميع تحويل فورييه المنفصل (DFT) بشكل مباشر نقاط البيانات.ن2{\textstyle n^{2}}عمليات الضرب المعقدة ون(ن-1){\textstyle n(n-1)}عمليات الجمع المعقدة، منهايا(ن){\textstyle O(n)}يمكن توفير العمليات الحسابية عن طريق حذف العمليات البسيطة مثل الضرب في 1، مما يترك حوالي 30 مليون عملية. في المقابل، يمكن لخوارزمية كولي-توكي ذات الأساس 2 ، عندما يكون n قوة للعدد 2، حساب النتيجة نفسها باستخدام 10 عمليات حسابية فقط.(ن/2)سجل2⁡(ن){\textstyle (n/2)\log _{2}(n)}عمليات الضرب المعقدة (مع تجاهل تبسيطات الضرب في 1 وما شابهها) ونسجل2⁡(ن){\textstyle n\log _{2}(n)}عمليات الجمع المعقدة، بإجمالي حوالي 70,000 عملية - أي أقل بأكثر من 400 مرة من التقييم المباشر. عمليًا، عادةً ما يهيمن على الأداء الفعلي للحواسيب الحديثة عوامل أخرى غير سرعة العمليات الحسابية، ويُعد التحليل موضوعًا معقدًا (انظر على سبيل المثال، Frigo & Johnson ، 2005)، [ 18 ] ولكن التحسن الإجمالي منيا(ن2){\textstyle O(n^{2})}ليا(نسجل⁡ن){\textstyle O(n\log n)}بقايا.

الخوارزميات

خوارزمية كولي-توكي

تُعد خوارزمية كولي-توكي الخوارزمية الأكثر استخدامًا في تحويل فورييه السريع (FFT). وهي خوارزمية تعتمد على أسلوب فرق تسد، حيث تقوم بتقسيم تحويل فورييه المنفصل (DFT) لأي حجم مركب بشكل متكرر.ن=ن1ن2{\textstyle n=n_{1}n_{2}}داخلن1{\textstyle n_{1}}سماكات شعاعية أصغر من الحجمن2{\textstyle n_{2}}، جنبا إلى جنب معيا(ن){\displaystyle O(n)}عمليات الضرب بجذور معقدة للوحدة تسمى تقليديًا عوامل التدوير (نقلاً عن جنتلمان وساندي، 1966). [ 19 ]

تم نشر هذه الطريقة (والفكرة العامة لـ FFT) من خلال منشور لكولي وتوكي في عام 1965، [ 13 ] ولكن تم اكتشافه لاحقًا [ 1 ] أن هذين المؤلفين أعادا معًا بشكل مستقل ابتكار خوارزمية معروفة لكارل فريدريش جاوس حوالي عام 1805 [ 20 ] (وأعيد اكتشافها لاحقًا عدة مرات بأشكال محدودة).

يُعدّ تقسيم التحويل إلى جزأين بحجم n /2 في كل خطوة الاستخدامَ الأكثر شيوعًا لخوارزمية كولي-توكي ، ولذلك فهي تقتصر على أحجام قوى العدد 2، ولكن يمكن استخدام أي تحليل بشكل عام (كما كان معروفًا لكل من جاوس وكولي/توكي [ 1 ] ). تُسمى هذه الحالات بحالات الأساس 2 وحالات الأساس المختلط ، على التوالي (وللمتغيرات الأخرى، مثل تحويل فورييه السريع ذي الأساس المنفصل، أسماء خاصة بها أيضًا). على الرغم من أن الفكرة الأساسية تكرارية، إلا أن معظم التطبيقات التقليدية تُعيد ترتيب الخوارزمية لتجنب التكرار الصريح. أيضًا، نظرًا لأن خوارزمية كولي-توكي تُقسّم تحويل فورييه المنفصل إلى تحويلات فورييه منفصلة أصغر، فإنه يُمكن دمجها بشكل تعسفي مع أي خوارزمية أخرى لتحويل فورييه المنفصل، مثل تلك الموضحة أدناه.

خوارزميات تحويل فورييه السريع الأخرى

لن=ن1ن2{\textstyle n=n_{1}n_{2}}مع عدد أولي مشتركن1{\textstyle n_{1}}ون2{\textstyle n_{2}}يمكن استخدام خوارزمية التحليل إلى العوامل الأولية (جود-توماس) (PFA)، القائمة على نظرية الباقي الصينية ، لتحليل تحويل فورييه المنفصل (DFT) بطريقة مشابهة لخوارزمية كولي-توكي، ولكن بدون عوامل التدوير. تُعد خوارزمية رادر-برينر (1976) [ 21 ] تحليلًا مشابهًا لخوارزمية كولي-توكي، ولكن بعوامل تدوير تخيلية بحتة، مما يقلل عمليات الضرب على حساب زيادة عمليات الجمع وانخفاض الاستقرار العددي ؛ وقد تم استبدالها لاحقًا بنسخة كولي-توكي ذات الأساس المنفصل (التي تحقق نفس عدد عمليات الضرب ولكن بعدد أقل من عمليات الجمع ودون التضحية بالدقة). تشمل الخوارزميات التي تُحلل تحويل فورييه المنفصل (DFT) بشكل متكرر إلى عمليات أصغر غير تحويلات فورييه المنفصلة خوارزميتي برون و QFT . (تم اقتراح خوارزميتي رادر-برينر [ 21 ] وQFT لأحجام قوى العدد اثنين، ولكن من الممكن تكييفهما مع أعداد مركبة عامة n . تنطبق خوارزمية برون على أي أحجام مركبة زوجية.) تعتمد خوارزمية برون ، على وجه الخصوص، على تفسير تحويل فورييه السريع (FFT) كتحليل تكراري لكثير الحدودzن-1{\displaystyle z^{n}-1}، هنا إلى كثيرات حدود ذات معاملات حقيقية من الشكلzم-1{\displaystyle z^{m}-1}وz2م+أzم+1{\displaystyle ض^{2م}+az^{م}+1}.

تستغل خوارزمية Winograd FFT وجهة نظر أخرى متعددة الحدود ، [ 22 ] [ 23 ] والتي تقوم بتحليلzن-1{\displaystyle z^{n}-1}إلى كثيرات الحدود الدائرية - والتي غالبًا ما تكون معاملاتها 1 أو  0  أو  -1، وبالتالي تتطلب عددًا قليلًا من عمليات الضرب (إن وجدت)، لذا يمكن استخدام خوارزمية وينوغراد للحصول على تحويلات فورييه السريعة بأقل عدد من عمليات الضرب، وكثيرًا ما تُستخدم لإيجاد خوارزميات فعالة للعوامل الصغيرة. في الواقع، أظهرت خوارزمية وينوغراد أنه يمكن حساب تحويل فورييه المنفصل باستخدام عدد قليل من عمليات الضرب فقط.يا(ن){\displaystyle O(n)}عمليات الضرب غير النسبية، مما أدى إلى حد أدنى مثبت وقابل للتحقيق لعدد عمليات الضرب لأحجام قوى العدد اثنين؛ ويأتي هذا على حساب زيادة كبيرة في عمليات الجمع، وهو خيار لم يعد مناسبًا في المعالجات الحديثة المزودة بمضاعفات مادية . وعلى وجه الخصوص، يستخدم وينوغراد أيضًا خوارزمية PFA بالإضافة إلى خوارزمية رادر لتحويل فورييه السريع للأحجام الأولية .

تُعبّر خوارزمية رادر ، التي تستغل وجود مولد للمجموعة الضربية بتردد عدد أولي n ، عن تحويل فورييه المنفصل (DFT) ذي الحجم الأولي n على شكل التفاف دوري ذي حجم (مركب) n – 1 ، والذي يمكن حسابه بعد ذلك باستخدام زوج من تحويلات فورييه السريعة (FFT) العادية عبر نظرية الالتفاف (على الرغم من أن وينوغراد يستخدم طرق التفاف أخرى) [ 24 ] . وهناك تحويل فورييه سريع آخر ذو حجم أولي يعود إلى لي بلوستين، ويُطلق عليه أحيانًا خوارزمية تشيرب-زد ؛ وهو يُعيد أيضًا التعبير عن تحويل فورييه المنفصل على شكل التفاف، ولكن هذه المرة بنفس الحجم (والذي يمكن إضافة أصفار إليه ليصبح قوة من قوى العدد اثنين وتقييمه باستخدام تحويلات فورييه السريعة من نوع كولي-توكي ذات الأساس 2، على سبيل المثال)، وذلك عبر المتطابقة [ 25 ].

نك=-(ك-ن)22+ن22+ك22.{\displaystyle nk=-{\frac {(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}.}

يهدف تحويل فورييه السريع السداسي (HFFT) إلى حساب تحويل فورييه سريع فعال للبيانات المأخوذة على شكل سداسي باستخدام مخطط عنونة جديد للشبكات السداسية، يسمى عنونة مجموعة المصفوفة (ASA) [ 26 ] .

خوارزميات تحويل فورييه السريع (FFT) المتخصصة في البيانات الحقيقية أو المتناظرة

في العديد من التطبيقات، تكون بيانات الإدخال لتحويل فورييه المنفصل حقيقية تمامًا، وفي هذه الحالة تحقق المخرجات التناظر

Xن-ك=Xك*{\displaystyle X_{nk}=X_{ك}^{*}}

وقد صُممت خوارزميات تحويل فورييه السريع (FFT) الفعالة لهذه الحالة (انظر على سبيل المثال، سورنسن، 1987). [ 27 ] [ 28 ] يتمثل أحد الأساليب في أخذ خوارزمية عادية (مثل كولي-توكي) وإزالة الأجزاء الزائدة من الحساب، مما يوفر ما يقارب النصف من الوقت والذاكرة. بدلاً من ذلك، من الممكن التعبير عن تحويل فورييه المنفصل (DFT) ذي المدخلات الحقيقية بطول زوجي كتحويل فورييه منفصل مركب بنصف الطول (حيث تكون أجزاؤه الحقيقية والخيالية هي العناصر الزوجية/الفردية للبيانات الحقيقية الأصلية)، متبوعًا بـيا(ن){\displaystyle O(n)}عمليات ما بعد المعالجة.

كان يُعتقد سابقًا أن تحويلات فورييه المنفصلة (DFT) ذات المدخلات الحقيقية يُمكن حسابها بكفاءة أكبر باستخدام تحويل هارتلي المنفصل (DHT)، ولكن طُرحت لاحقًا فكرة أنه يُمكن عادةً إيجاد خوارزمية DFT متخصصة ذات مدخلات حقيقية (FFT) تتطلب عمليات أقل من خوارزمية DHT المقابلة (FHT) لنفس عدد المدخلات. [ 27 ] تُعد خوارزمية برون (المذكورة أعلاه) طريقة أخرى طُرحت في البداية للاستفادة من المدخلات الحقيقية، ولكنها لم تحظَ بشعبية واسعة.

توجد تخصصات إضافية لخوارزمية تحويل فورييه السريع (FFT) لحالات البيانات الحقيقية ذات التناظر الزوجي/الفردي ، وفي هذه الحالة يمكن تحقيق توفير إضافي في الوقت والذاكرة بمقدار الضعف تقريبًا، ويصبح تحويل فورييه المنفصل (DFT) هو تحويل جيب التمام / الجيب المنفصل ( DCT / DST ). وبدلًا من تعديل خوارزمية FFT مباشرةً لهذه الحالات، يمكن أيضًا حساب تحويلات DCT/DST من خلال دمج تحويلات FFT للبيانات الحقيقية معيا(ن){\displaystyle O(n)}المعالجة المسبقة واللاحقة.

المشكلات الحسابية

حدود التعقيد وعدد العمليات

مشكلة لم تُحل في علوم الحاسوب
ما هو الحد الأدنى لتعقيد خوارزميات تحويل فورييه السريع؟ هل يمكن أن تكون أسرع منيا(شمالسجل⁡شمال){\displaystyle O(N\log N)}؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

يُعدّ إثبات الحدود الدنيا لتعقيد وعدد العمليات الدقيقة لتحويلات فورييه السريعة سؤالًا أساسيًا ذا أهمية نظرية طويلة الأمد ، ولا تزال العديد من المشكلات مفتوحة. لم يُثبت بشكل قاطع ما إذا كانت تحويلات فورييه المنفصلة تتطلب بالفعلΩ(نسجل⁡ن){\textstyle \Omega (n\log n)}(أي، ترتيب)نسجل⁡ن{\displaystyle n\log n}أو أكبر) من العمليات الحسابية، حتى في حالة قوى العدد اثنين البسيطة ، على الرغم من عدم وجود خوارزميات معروفة ذات تعقيد أقل. وعلى وجه الخصوص، عادةً ما يكون عدد العمليات الحسابية محور هذه الأسئلة، مع أن الأداء الفعلي على أجهزة الكمبيوتر الحديثة يتحدد بعوامل أخرى كثيرة مثل تحسين ذاكرة التخزين المؤقت أو خط أنابيب وحدة المعالجة المركزية .

استنادًا إلى عمل شموئيل وينوغراد (1978)، [ 22 ] ضيقΘ(ن){\displaystyle \Theta (n)}يُعرف الحد الأدنى لعدد عمليات الضرب الحقيقية المطلوبة بواسطة تحويل فورييه السريع (FFT). ويمكن إثبات أن فقط4ن-2سجل22⁡(ن)-2سجل2⁡(ن)-4{\textstyle 4n-2\log _{2}^{2}(n)-2\log _{2}(n)-4}يلزم إجراء عمليات ضرب حقيقية غير نسبية لحساب تحويل فورييه المنفصل بطول قوة العدد اثنينن=2م{\displaystyle n=2^{m}}علاوة على ذلك، توجد خوارزميات صريحة معروفة لتحقيق هذا العدد (هايدمان وبوروس ، 1986؛ [ 29 ] دوهاميل، 1990 [ 30 ] ). مع ذلك، تتطلب هذه الخوارزميات عددًا كبيرًا جدًا من عمليات الجمع لتكون عملية، على الأقل على أجهزة الكمبيوتر الحديثة المزودة بمضاعفات مادية (دوهاميل، 1990؛ [ 30 ] فريجو وجونسون ، 2005). [ 18 ]

لا يُعرف حد أدنى دقيق لعدد عمليات الجمع المطلوبة، على الرغم من إثبات حدود دنيا في ظل بعض الافتراضات التقييدية على الخوارزميات. في عام 1973، أثبت مورغنسترن [ 31 ]Ω(نسجل⁡ن){\displaystyle \Omega (n\log n)}الحد الأدنى لعدد عمليات الجمع للخوارزميات التي تكون فيها الثوابت الضربية ذات مقادير محدودة (وهو ما ينطبق على معظم خوارزميات تحويل فورييه السريع، ولكن ليس جميعها). أثبت بان (1986) [ 32 ]Ω(نسجل⁡ن){\displaystyle \Omega (n\log n)}يُفترض وجود حد أدنى بافتراض حدٍّ لمقياس عدم تزامن خوارزمية تحويل فورييه السريع ، لكن مدى عمومية هذا الافتراض غير واضح. في حالة n من قوى العدد اثنين ، جادل باباديميتريو (1979) [ 33 ] بأن العددنسجل2⁡ن{\textstyle n\log _{2}n}تُعتبر عمليات جمع الأعداد المركبة التي تُحققها خوارزميات كولي-توكي مثالية في ظل افتراضات معينة على الرسم البياني للخوارزمية (تتضمن هذه الافتراضات، من بين أمور أخرى، عدم استغلال أي عناصر محايدة جمعية في جذور الوحدة). (تشير هذه الحجة إلى أن على الأقل2شمالسجل2⁡شمال{\textstyle 2N\log _{2}N}يلزم إجراء عمليات جمع حقيقية، مع العلم أن هذا ليس حدًا دقيقًا نظرًا لوجود عمليات جمع إضافية مطلوبة كجزء من عمليات ضرب الأعداد المركبة. حتى الآن، لم تحقق أي خوارزمية FFT منشورة عددًا أقل مننسجل2⁡ن{\textstyle n\log _{2}n}عمليات جمع الأعداد المركبة (أو ما يعادلها) لقوى العدد اثنين n .

تتمثل المشكلة الثالثة في تقليل العدد الإجمالي لعمليات الضرب والجمع الحقيقية، والذي يُطلق عليه أحيانًا التعقيد الحسابي (مع أن المقصود هنا هو العدد الدقيق وليس التعقيد التقاربي). ومرة ​​أخرى، لم يتم إثبات حد أدنى دقيق. مع ذلك، منذ عام 1968، تم تحقيق أقل عدد منشور لقوى العدد اثنين n لفترة طويلة بواسطة خوارزمية FFT ذات الأساس المنفصل ، والتي تتطلب4نسجل2⁡(ن)-6ن+8{\textstyle 4n\log _{2}(n)-6n+8}عمليات الضرب والجمع الحقيقية لـ n > 1. وقد تم تبسيط ذلك إلى∼349نسجل2⁡ن{\textstyle \sim {\frac {34}{9}}n\log _{2}n}(جونسون وفريجو، 2007؛ [ 17 ] لندي وفان بوسكيرك، 2007 [ 34 ] ). وقد ثبت أن عددًا أكبر قليلًا (ولكنه لا يزال أفضل من طريقة الجذر المنقسم لـ n ≥ 256 ) هو الأمثل بشكل قاطع لـ n ≤ 512 في ظل قيود إضافية على الخوارزميات الممكنة (مخططات تدفق شبيهة بطريقة الجذر المنقسم مع عوامل ضرب ذات معامل وحدة)، وذلك عن طريق اختزالها إلى مسألة إرضاء معيارية للنظريات قابلة للحل بالقوة الغاشمة (هاينال وهاينال، 2011). [ 35 ]

ركزت معظم المحاولات الرامية إلى تقليل تعقيد خوارزميات تحويل فورييه السريع (FFT) أو إثباته على حالة البيانات المركبة العادية، لأنها الأبسط. ومع ذلك، فإن تحويلات فورييه السريع للبيانات المركبة ترتبط ارتباطًا وثيقًا بخوارزميات المشكلات ذات الصلة، مثل تحويلات فورييه السريع للبيانات الحقيقية، وتحويلات جيب التمام المنفصلة ، ​​وتحويلات هارتلي المنفصلة ، ​​وما إلى ذلك، بحيث أن أي تحسين في إحداها سيؤدي فورًا إلى تحسينات في الأخرى (دوهامل وفيترلي، 1990). [ 36 ]

التقريبات

جميع خوارزميات تحويل فورييه السريع (FFT) المذكورة أعلاه تحسب تحويل فورييه المنفصل (DFT) بدقة (أي بإهمال أخطاء الفاصلة العائمة ). مع ذلك، اقتُرحت بعض خوارزميات FFT التي تحسب DFT تقريبًا ، مع هامش خطأ يمكن تقليله إلى أدنى حد ممكن على حساب زيادة العمليات الحسابية. تُضحي هذه الخوارزميات بدقة التقريب مقابل زيادة السرعة أو خصائص أخرى. على سبيل المثال، تُحقق خوارزمية FFT التقريبية التي وضعها إيدلمان وآخرون (1999) [ 37 ] متطلبات اتصال أقل للحوسبة المتوازية باستخدام طريقة الأقطاب المتعددة السريعة . كما أن خوارزمية FFT التقريبية القائمة على الموجات الصغيرة التي وضعها غو وبوروس (1996) [ 38 ] تأخذ المدخلات/المخرجات المتفرقة (تحديد الموقع الزمني/الترددي) في الحسبان بكفاءة أعلى مما هو ممكن مع FFT الدقيق. وهناك خوارزمية أخرى للحساب التقريبي لمجموعة فرعية من مخرجات DFT تعود إلى شينتوف وآخرون (1995). [ 39 ] تعمل خوارزمية إيدلمان بكفاءة متساوية مع البيانات المتفرقة وغير المتفرقة، لأنها تعتمد على انضغاطية (نقص الرتبة) مصفوفة فورييه نفسها بدلاً من انضغاطية (تفرق) البيانات. وعلى العكس، إذا كانت البيانات متفرقة - أي إذا كانت k فقط من أصل n من معاملات فورييه غير صفرية - فيمكن تقليل التعقيد إلىيا(كسجل⁡نسجل⁡ن/ك){\displaystyle O(k\log n\log n/k)}وقد ثبت أن هذا يؤدي إلى تسريع عملي مقارنةً بتحويل فورييه السريع العادي لـ n / k > 32 في مثال ذي n كبير ( n = 222 ) باستخدام خوارزمية تقريبية احتمالية (والتي تقدر أكبر معاملات k إلى عدة منازل عشرية). [ 40 ]

دقة

تُعاني خوارزميات تحويل فورييه السريع (FFT) من أخطاء عند استخدام حسابات الفاصلة العائمة ذات الدقة المحدودة، إلا أن هذه الأخطاء عادةً ما تكون صغيرة جدًا؛ إذ تتمتع معظم خوارزميات FFT، مثل خوارزمية كولي-توكي، بخصائص عددية ممتازة نتيجةً لبنية الجمع الثنائي لهذه الخوارزميات. الحد الأعلى للخطأ النسبي لخوارزمية كولي-توكي هويا(εسجل⁡ن){\textstyle O(\varepsilon \log n)}، مقارنة بيا(εن3/2){\textstyle O(\varepsilon n^{3/2})}بالنسبة لصيغة تحويل فورييه المنفصلة البسيطة، [ 19 ] حيث 𝜀 هي الدقة النسبية للآلة في الفاصلة العائمة. في الواقع، تكون أخطاء الجذر التربيعي المتوسط ​​(rms) أفضل بكثير من هذه الحدود العليا، حيث تبلغ فقطيا(εسجل⁡ن){\textstyle O(\varepsilon {\sqrt {\log n}})}لكولي-توكي ويا(εن){\textstyle O(\varepsilon {\sqrt {n}})}بالنسبة لخوارزمية تحويل فورييه المنفصلة البسيطة (شاتزمان، 1996). [ 41 ] مع ذلك، تتأثر هذه النتائج بشدة بدقة عوامل التدوير المستخدمة في تحويل فورييه السريع (أي قيم الدوال المثلثية )، ومن الشائع أن تكون دقة تطبيقات تحويل فورييه السريع غير الدقيقة أسوأ بكثير، على سبيل المثال إذا استخدمت صيغ تكرارية مثلثية غير دقيقة . بعض خوارزميات تحويل فورييه السريع الأخرى غير خوارزمية كولي-توكي، مثل خوارزمية رادر-برينر، أقل استقرارًا بطبيعتها.

في الحساب ذي النقطة الثابتة ، تكون أخطاء الدقة المحدودة المتراكمة بواسطة خوارزميات تحويل فورييه السريع أسوأ، حيث تنمو أخطاء الجذر التربيعي المتوسط ​​معيا(ن){\textstyle O({\sqrt {n}})}بالنسبة لخوارزمية كولي-توكي (ويلش، 1969). [ 42 ] يتطلب تحقيق هذه الدقة اهتمامًا دقيقًا بالتحجيم لتقليل فقدان الدقة، وتتضمن خوارزميات تحويل فورييه السريع ذات النقطة الثابتة إعادة التحجيم في كل مرحلة وسيطة من مراحل التفكيك مثل كولي-توكي.

للتحقق من صحة تطبيق تحويل فورييه السريع (FFT)، يمكن الحصول على ضمانات صارمة فييا(نسجل⁡ن){\textstyle O(n\log n)}يتم تحديد الوقت من خلال إجراء بسيط يتحقق من الخطية، واستجابة النبضة، وخصائص الإزاحة الزمنية للتحويل على المدخلات العشوائية (إرغون، 1995). [ 43 ]

يمكن الحصول على قيم الترددات المتوسطة من خلال طرق حساب المتوسط ​​المختلفة.

تحويل فورييه متعدد الأبعاد

كما هو مُعرَّف في مقالة DFT متعددة الأبعاد ، فإن DFT متعددة الأبعاد

Xك=∑ن=0شمال-1هـ-2πأناك⋅(ن/شمال)xن{\displaystyle X_{\mathbf {k}}=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }}

يحوّل مصفوفة x n إلى متجه ذي d بُعد من المؤشراتن=(ن1،...،ند){\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}بواسطة مجموعة من عمليات الجمع المتداخلة (علىنج=0...شمالج-1{\textstyle n_{j}=0\ldots N_{j}-1}لكل j )، حيث القسمةن/شمال=(ن1/شمال1،...،ند/شمالد){\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)}يتم تنفيذه عنصرًا تلو الآخر. وبشكل مكافئ، هو عبارة عن تركيب لتسلسل من d مجموعات من تحويلات فورييه المنفصلة أحادية البعد، يتم تنفيذها على طول بُعد واحد في كل مرة (بأي ترتيب).

تُقدّم هذه النظرة التركيبية مباشرةً أبسط خوارزمية تحويل فورييه المنفصل متعدد الأبعاد وأكثرها شيوعًا، والمعروفة بخوارزمية الصف والعمود (بعد الحالة ثنائية الأبعاد، أدناه). أي، يتم ببساطة إجراء سلسلة من d تحويلات فورييه سريعة أحادية البعد (باستخدام أي من الخوارزميات المذكورة أعلاه): أولًا ، يتم التحويل على طول البعد n1 ، ثم على طول البعد n2 ، وهكذا (في الواقع، أي ترتيب يُجدي). من السهل إثبات أن هذه الطريقة تتمتع بالخصائص المعتادة .يا(نسجل⁡ن){\textstyle O(n\log n)}التعقيد، حيثن=ن1⋅ن2⋯ند{\textstyle n=n_{1}\cdot n_{2}\cdots n_{d}}يمثل العدد الإجمالي لنقاط البيانات التي تم تحويلها. على وجه الخصوص، هناك n / n 1 تحويلًا بحجم n 1 ، وهكذا، لذا فإن تعقيد سلسلة تحويلات فورييه السريعة (FFT) هو:

نن1يا(ن1سجل⁡ن1)+⋯+ننديا(ندسجل⁡ند)=يا(ن[سجل⁡ن1+⋯+سجل⁡ند])=يا(نسجل⁡ن).{\displaystyle {\begin{aligned}&{\frac {n}{n_{1}}}O(n_{1}\log n_{1})+\cdots +{\frac {n}{n_{d}}}O(n_{d}\log n_{d})\\[6pt]={}&O\left(n\left[\log n_{1}+\cdots +\log n_{d}\right]\right)=O(n\log n).\end{aligned}}}

في بُعدين، يمكن اعتبار x k بمثابةن1×ن2{\displaystyle n_{1}\times n_{2}}المصفوفة ، وتتوافق هذه الخوارزمية مع إجراء تحويل فورييه السريع (FFT) لجميع الصفوف (أو الأعمدة)، ثم تجميع الصفوف (أو الأعمدة) المحولة الناتجة معًا كمصفوفة أخرى.ن1×ن2{\displaystyle n_{1}\times n_{2}}ثم إجراء تحويل فورييه السريع على كل عمود (أو صف) من هذه المصفوفة الثانية، وبالمثل تجميع النتائج في مصفوفة النتائج النهائية.

في الأبعاد التي تزيد عن بعدين، غالبًا ما يكون من المفيد لتحسين موضع البيانات في الذاكرة المؤقتة تجميع الأبعاد بشكل متكرر. على سبيل المثال، قد تُجري خوارزمية تحويل فورييه السريع ثلاثية الأبعاد أولًا تحويلات فورييه السريع ثنائية الأبعاد لكل شريحة مستوية لكل قيمة ثابتة لـ n1 ، ثم تُجري تحويلات فورييه السريع أحادية البعد على طول اتجاه n1 . وبشكل أعم، تتكون الخوارزمية المثلى تقاربًا والتي لا تعتمد على الذاكرة المؤقتة من تقسيم الأبعاد بشكل متكرر إلى مجموعتين .(ن1،...،ند/2){\textstyle (n_{1},\ldots ,n_{d/2})}و(ند/2+1،...،ند){\textstyle (n_{d/2+1},\ldots ,n_{d})}التي تُحوَّل بشكل متكرر (مع التقريب إذا لم يكن d زوجيًا) (انظر فريجو وجونسون، 2005). [ 18 ] ومع ذلك، يظل هذا تباينًا مباشرًا لخوارزمية الصف-العمود التي لا تتطلب في النهاية سوى خوارزمية تحويل فورييه السريع أحادية البعد كحالة أساسية، ولا تزاليا(نسجل⁡ن){\displaystyle O(n\log n)}التعقيد. هناك اختلاف آخر يتمثل في إجراء عمليات تبديل المصفوفات بين تحويل الأبعاد اللاحقة، بحيث تعمل التحويلات على البيانات المتجاورة؛ وهذا مهم بشكل خاص لحالات الذاكرة خارج الذاكرة الرئيسية والذاكرة الموزعة حيث يكون الوصول إلى البيانات غير المتجاورة مستهلكًا للوقت بشكل كبير.

توجد خوارزميات أخرى لتحويل فورييه السريع متعدد الأبعاد تختلف عن خوارزمية الصف والعمود، على الرغم من أن جميعها تمتلكيا(نسجل⁡ن){\textstyle O(n\log n)}التعقيد. ربما تكون أبسط خوارزمية تحويل فورييه السريع غير القائمة على الصفوف والأعمدة هي خوارزمية تحويل فورييه السريع ذات الأساس المتجهي ، وهي تعميم لخوارزمية كولي-توكي العادية حيث يتم تقسيم أبعاد التحويل على متجه.ر=(ر1،ر2،...،رد){\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}عدد الجذور في كل خطوة. (قد يكون لهذا فوائد تخزين مؤقت أيضًا). أبسط حالة لنظام الجذر المتجهي هي عندما تكون جميع الجذور متساوية (على سبيل المثال، يقسم نظام الجذر المتجهي 2 جميع الأبعاد على اثنين)، ولكن هذا ليس ضروريًا. نظام الجذر المتجهي مع جذر واحد فقط غير الوحدة في كل مرة، أير=(1،...،1،ر،1،...،1){\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}هي في الأساس خوارزمية صف-عمود. تشمل الطرق الأخرى الأكثر تعقيدًا خوارزميات التحويل متعدد الحدود التي وضعها نوسباومر (1977) [ 44 ] ، والتي تنظر إلى التحويل من منظور الالتفافات وحاصل ضرب متعددات الحدود. انظر دوهامل وفيترلي (1990) [ 36 ] لمزيد من المعلومات والمراجع.

تعميمات أخرى

أنيا(ن5/2سجل⁡ن){\textstyle O(n^{5/2}\log n)}وصف موهلينكامب [ 45 ] تعميمًا للتوافقيات الكروية على الكرة S2 ذات n2 عقدة ، إلى جانب خوارزمية يُفترض (ولكن لم يتم إثباتها) أنهايا(ن2سجل2⁡(ن)){\textstyle O(n^{2}\log ^{2}(n))}التعقيد؛ كما يوفر موهلينكامب تطبيقًا في مكتبة libftsh. [ 46 ] خوارزمية توافقية كروية معيا(ن2سجل⁡ن){\textstyle O(n^{2}\log n)}تم وصف التعقيد بواسطة روخلين وتيجرت. [ 47 ]

تُشابه خوارزمية الطي السريع خوارزمية تحويل فورييه السريع (FFT)، إلا أنها تعمل على سلسلة من أشكال الموجات المُصنّفة بدلاً من سلسلة من القيم العددية الحقيقية أو المركبة. الدوران (الذي يُمثّل في خوارزمية تحويل فورييه السريع الضرب في مُتجه طوري مُركب) هو إزاحة دائرية لشكل الموجة المُكوّنة [ 48 ] .

نشرت مجموعات بحثية مختلفة خوارزميات تحويل فورييه السريع (FFT) للبيانات غير المتساوية التباعد، كما ورد في مراجعة بوتس وآخرون (2001). [ 49 ] لا تحسب هذه الخوارزميات تحويل فورييه المنفصل (DFT) بدقة (المُعرَّف فقط للبيانات المتساوية التباعد)، بل تُجري تقريبًا له ( تحويل فورييه المنفصل غير المنتظم ، أو NDFT، والذي غالبًا ما يُحسب بشكل تقريبي فقط). وبشكل عام، توجد طرق أخرى متنوعة لتقدير الطيف .

التطبيقات

تُستخدم تقنية تحويل فورييه السريع (FFT) في التسجيل الرقمي، وأخذ العينات، والتوليف الإضافي ، وبرامج تصحيح النغمات . [ 50 ]

تكمن أهمية تحويل فورييه السريع (FFT) في أنه جعل العمل في مجال التردد ممكنًا حسابيًا بنفس قدر العمل في المجال الزمني أو المكاني. ومن أهم تطبيقات تحويل فورييه السريع ما يلي: [ 16 ] [ 51 ]

الاتصالات السلكية واللاسلكية

في معايير الاتصالات اللاسلكية الحديثة، يُعدّ تحويل فورييه السريع (FFT) عنصرًا أساسيًا لمعالجة الإشارات. ويُستخدم تحديدًا في أنظمة الإرسال بتقسيم التردد المتعامد (OFDM)، مثل شبكات الجيل الرابع LTE وشبكات الجيل الخامس NR . [ 53 ] تتيح كفاءة تحويل فورييه السريع نقل البيانات بسرعة عالية من خلال تقسيم إشارة النطاق العريض إلى عدة موجات حاملة فرعية متعامدة متقاربة. [ 54 ] تُعدّ هذه التقنية ضرورية للحدّ من التداخل وتحسين استهلاك الطاقة في الأجهزة المحمولة. [ 54 ]

البدائل

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

في الحالات التي تظهر فيها معلومات التردد لفترة وجيزة في الإشارة أو تتغير عمومًا بمرور الوقت، قد تكون البدائل مثل تحويل فورييه قصير المدى ، أو تحويلات المويجات المنفصلة ، ​​أو تحويل هيلبرت المنفصل أكثر ملاءمة. [ 55 ] [ 56 ] تسمح هذه التحويلات بتحليل التردد الموضعي من خلال التقاط كل من معلومات التردد والزمن.

مجالات البحث

تحويل فورييه السريع الكبير
مع تزايد حجم البيانات الضخمة في مجالات مثل علم الفلك، برزت الحاجة إلى تحويلات فورييه سريعة (FFT) بحجم 512 ألف نقطة لإجراء بعض حسابات التداخل الضوئي. تتطلب البيانات التي تجمعها مشاريع مثل WMAP و LIGO تحويلات فورييه سريعة لعشرات المليارات من النقاط. ولأن هذا الحجم لا يتسع في الذاكرة الرئيسية، تُعدّ تحويلات فورييه السريعة خارج الذاكرة مجالًا بحثيًا نشطًا. [ 57 ]
تحويلات فورييه السريعة التقريبية
في تطبيقات مثل التصوير بالرنين المغناطيسي، من الضروري حساب تحويلات فورييه المنفصلة (DFT) لنقاط الشبكة و/أو الترددات غير المنتظمة التباعد. يمكن للأساليب القائمة على الأقطاب المتعددة حساب كميات تقريبية مع زيادة في وقت التشغيل. [ 58 ]
تحويلات فورييه السريعة الجماعية
يمكن أيضًا شرح وتفسير تحويل فورييه السريع (FFT) باستخدام نظرية تمثيل الزمر ، مما يسمح بمزيد من التعميم. للدالة على أي زمرة متراصة، بما في ذلك الزمر غير الدورية، توسيع بدلالة أساس من عناصر المصفوفة غير القابلة للاختزال. ولا يزال إيجاد خوارزمية فعالة لإجراء هذا التغيير في الأساس مجالًا بحثيًا نشطًا. وتشمل التطبيقات توسيع التوافقيات الكروية بكفاءة ، وتحليل بعض عمليات ماركوف ، والروبوتات، وغيرها. [ 59 ]
تحويل فورييه الكمي
تتضمن خوارزمية شور السريعة لتحليل الأعداد الصحيحة إلى عواملها الأولية على الحاسوب الكمومي روتينًا فرعيًا لحساب تحويل فورييه المنفصل (DFT) لمتجه ثنائي. يُنفذ هذا كسلسلة من البوابات الكمومية أحادية أو ثنائية البت، والمعروفة الآن باسم تحويل فورييه الكمومي السريع (FFT)، وهو في جوهره تحويل فورييه السريع لكولي-توكي مُجسدًا كتحليل خاص لمصفوفة فورييه. ويجري حاليًا استكشاف امتدادات لهذه الأفكار. [ 60 ]

مرجع لغوي

لغةأسلوب الأمرالمتطلبات الأساسية
Rstats::fft(x)لا أحد
سكيلابfft(x)لا أحد
MATLAB ، Octavefft(x)لا أحد
بايثونfft.fft(x)numpy أو scipy
ماثيماتيكافورييه[x]لا أحد
لغة C / لغة C++fftw_execute(plan)FTW
فورترانfftw_one(plan,in,out)FTW
جولياfft(A [,dims])FTW
الصدأfft.process(&mut x);rustfft
هاسكلdft xتحويل فورييه السريع

انظر أيضاً

الخوارزميات المتعلقة بتحويل فورييه السريع:

تطبيقات تحويل فورييه السريع (FFT):

  • FFTW – مكتبة برمجية مجانية طورها ماتيو فريجو وستيفن جي. جونسون في معهد ماساتشوستس للتكنولوجيا
  • FFTReal – تطبيق مُحسَّن للغاية ونظيف وموجز يدعم القيم العددية أو متجه SIMD في فئة C++ من تطوير ديمتري بولديريف، مُستضاف على GitHub https://github.com/mewza/realfft/
  • ALGLIB – مكتبة C++ وC# مرخصة بموجب ترخيص مزدوج/GPL (تدعم لغات أخرى أيضًا)، مع تطبيق FFT حقيقي/معقد
  • FFTPACK – مكتبة أخرى لـ FFT بلغة فورتران (متاحة للجميع)
  • خاص بالبنية المعمارية:
  • تتوفر العديد من التطبيقات الأخرى، [ 62 ] لوحدات المعالجة المركزية ووحدات معالجة الرسومات، مثل PocketFFT للغة C++

روابط أخرى:

مراجع

  1. 1 2 3 4 هايدمان، مايكل ت.؛ جونسون، دون هـ.؛ بوروس، تشارلز سيدني (1984). "غاوس وتاريخ تحويل فورييه السريع" ( ملف PDF) . مجلة IEEE ASSP . 1 (4): 14-21 . Bibcode : 1984IASSP...1...14H . CiteSeerX 10.1.1.309.181 . doi : 10.1109/MASSP.1984.1162257 . S2CID 10032502. مؤرشف (ملف PDF) من الأصل بتاريخ 19-03-2013.  
  2. ↑ فان لون، تشارلز (1992). الأطر الحسابية لتحويل فورييه السريع . SIAM .
  3. ↑ سترانج، جيلبرت (مايو-يونيو 1994). "الموجات الصغيرة". العالم الأمريكي . 82 (3): 250-255 . رمز Bibcode : 1994AmSci..82..250S . JSTOR 29775194 . 
  4. ↑ كينت، ريموند د.؛ ريد، تشارلز (2002). التحليل الصوتي للكلام ( الطبعة الثانية). سينغولار/تومسون ليرنينج. ص 61. ISBN   978-0-7693-0112-9.
  5. ↑ دونغارا، جاك؛ سوليفان، فرانسيس (يناير 2000). "مقدمة المحررين الضيوف لأفضل 10 خوارزميات". الحوسبة في العلوم والهندسة . 2 (1): 22-23 . Bibcode : 2000CSE.....2a..22D . doi : 10.1109/MCISE.2000.814652 . ISSN 1521-9615 . 
  6. ^ غاوس، كارل فريدريش (1866). "Theoria interpolationismetho novatractata" [ نظرية تتعلق بطريقة جديدة للاستيفاء ] . نشلس (مخطوطة غير منشورة). Werke (باللغة اللاتينية والألمانية). المجلد. 3. غوتنغن، ألمانيا: Königlichen Gesellschaft der Wissenschaften zu Göttingen. ص 265 – 303.  
  7. 1 2 هايدمان، مايكل ت.؛ جونسون، دون هـ.؛ بوروس، تشارلز سيدني (1985-09-01). "غاوس وتاريخ تحويل فورييه السريع". أرشيف تاريخ العلوم الدقيقة . 34 (3): 265-277 . CiteSeerX 10.1.1.309.181 . doi : 10.1007/BF00348431 . ISSN 0003-9519 . S2CID 122847826 .   
  8. ↑ ييتس، فرانك (1937). "تصميم وتحليل التجارب العاملية". النشرة الفنية رقم 35 الصادرة عن مكتب الكومنولث للتربة . 142 (3585): 90-92 . Bibcode : 1938Natur.142...90F . doi : 10.1038/142090a0 . S2CID 23501205 . 
  9. ↑ دانييلسون، جوردون سي .؛ لانكزوس، كورنيليوس (1942). "بعض التحسينات في تحليل فورييه العملي وتطبيقها على تشتت الأشعة السينية من السوائل". مجلة معهد فرانكلين . 233 (4): 365-380 . doi : 10.1016/S0016-0032(42)90767-1 .
  10. ↑ لانكزوس، كورنيليوس (1956). التحليل التطبيقي . برنتيس هول .
  11. ↑ كولي، جيمس و .؛ لويس، بيتر أ. و.؛ ويلش، بيتر د. (يونيو 1967). "ملاحظات تاريخية حول تحويل فورييه السريع". معاملات IEEE في الصوتيات والإلكترونيات الصوتية . 15 (2): 76-79 . Bibcode : 1967ITAuE..15...76C . CiteSeerX 10.1.1.467.7209 . doi : 10.1109/TAU.1967.1161903 . ISSN 0018-9278 .  
  12. ↑ جود، آي جيه (يوليو 1958). "خوارزمية التفاعل والتحليل العملي لفورييه" . مجلة الجمعية الإحصائية الملكية، السلسلة ب (المنهجية) . 20 (2): 361-372 . doi : 10.1111/j.2517-6161.1958.tb00300.x .
  13. 1 2 كولي، جيمس و .؛ توكي، جون و. (1965). "خوارزمية للحساب الآلي لمتسلسلات فورييه المعقدة" . رياضيات الحساب . 19 (90): 297-301 . doi : 10.1090/S0025-5718-1965-0178586-1 . ISSN 0025-5718 . 
  14. ↑ كولي، جيمس و. (1987). "إعادة اكتشاف خوارزمية تحويل فورييه السريع" (ملف PDF) . مجلة ميكروكيميكا أكتا . المجلد الثالث. فيينا، النمسا. الصفحات 33-45 . مؤرشف (ملف PDF) من الأصل بتاريخ 20 أغسطس 2016.  {{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
  15. ↑ غاروِن، ريتشارد (يونيو 1969). "تحويل فورييه السريع كمثال على صعوبة انتشار استخدام تقنية جديدة" (ملف PDF) . معاملات IEEE في الصوتيات والإلكترونيات الصوتية . AU-17 (2): 68-72 . مؤرشف (ملف PDF) من الأصل بتاريخ 17-05-2006.
  16. روكمور ، دانيال ن . (يناير 2000). "تحويل فورييه السريع: خوارزمية يمكن لجميع أفراد الأسرة استخدامها". الحوسبة في العلوم والهندسة . 2 (1): 60-64 . رمز Bibcode : 2000CSE.....2a..60R . CiteSeerX 10.1.1.17.228 . doi : 10.1109/5992.814659 . ISSN 1521-9615 . S2CID 14978667 .   
  17. 1 2 فريجو، ماتيو؛ جونسون، ستيفن ج. (يناير 2007) [19-12-2006]. "تحويل فورييه سريع معدل ذو أساس منقسم مع عمليات حسابية أقل". معاملات IEEE في معالجة الإشارات . 55 (1): 111-119 . Bibcode : 2007ITSP...55..111J . CiteSeerX 10.1.1.582.5497 . doi : 10.1109/tsp.2006.882087 . S2CID 14772428 .  
  18. 1 2 3 فريجو، ماتيو؛ جونسون، ستيفن ج. (2005). "تصميم وتنفيذ FFTW3" (ملف PDF) . وقائع معهد مهندسي الكهرباء والإلكترونيات . 93 (2): 216-231 . رمز Bibcode : 2005IEEEP..93..216F . CiteSeerX 10.1.1.66.3097 . doi : 10.1109/jproc.2004.840301 . S2CID 6644892. مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 2005-02-07 .  
  19. 1 2 جنتلمان، دبليو. مورفن؛ ساندي، جي. (1966). "تحويلات فورييه السريعة - للمتعة والربح" . وقائع AFIPS . 29 : 563-578 . doi : 10.1145/1464291.1464352 . S2CID 207170956 . 
  20. ^ غاوس، كارل فريدريش (1866) [1805]. نظرية الاستيفاء طريقة المسالك الجديدة . Werke (باللغة اللاتينية والألمانية). المجلد. 3. غوتنغن، ألمانيا: Königliche Gesellschaft der Wissenschaften. ص 265 – 327.  
  21. 1 2 برينر، نورمان م.؛ رادر، تشارلز م. (1976). "مبدأ جديد لتحويل فورييه السريع". معاملات IEEE في الصوتيات والكلام ومعالجة الإشارات . 24 (3): 264-266 . Bibcode : 1976ITASS..24..264R . doi : 10.1109/TASSP.1976.1162805 .
  22. وينوغراد ، شموئيل ( 1978). " حول حساب تحويل فورييه المنفصل" . رياضيات الحساب . 32 (141): 175-199 . doi : 10.1090/S0025-5718-1978-0468306-4 . JSTOR 2006266. PMC 430186. PMID 16592303 .   
  23. ↑ وينوغراد، شموئيل (1979). "حول التعقيد الضربي لتحويل فورييه المنفصل" . التقدم في الرياضيات . 32 (2): 83-117 . doi : 10.1016/0001-8708(79)90037-9 .
  24. ↑ رادر، سي إم (1968). "تحويلات فورييه المنفصلة عندما يكون عدد عينات البيانات عددًا أوليًا" . وقائع معهد مهندسي الكهرباء والإلكترونيات . 56 (6): 1107-1108 . doi : 10.1109/PROC.1968.6477 . ISSN 0018-9219 . 
  25. ↑ بلوستين، ل. (ديسمبر 1970). "نهج الترشيح الخطي لحساب تحويل فورييه المنفصل" . معاملات IEEE في الصوتيات والإلكترونيات الصوتية . 18 (4): 451-455 . doi : 10.1109/TAU.1970.1162132 . ISSN 0018-9278 . 
  26. ↑ ويلسون، جوزيف ن. (2011-04-01). "عنونة مجموعة المصفوفات: تقنية تمكينية للمعالجة الفعالة للصور المأخوذة عينات منها سداسية الشكل" . مجلة التصوير الإلكتروني . 20 (2): 023012. doi : 10.1117/1.3589306 . ISSN 1017-9909 . 
  27. 1 2 سورنسن، هنريك ف.؛ جونز، دوغلاس ل .؛ هايدمان، مايكل ت.؛ بوروس، تشارلز سيدني (1987). "خوارزميات تحويل فورييه السريع ذات القيم الحقيقية". معاملات IEEE في الصوتيات والكلام ومعالجة الإشارات . 35 (6): 849-863 . Bibcode : 1987ITASS..35..849S . CiteSeerX 10.1.1.205.4523 . doi : 10.1109/TASSP.1987.1165220 . 
  28. ↑ سورنسن، هنريك ف.؛ جونز، دوغلاس ل .؛ هايدمان، مايكل ت.؛ بوروس، تشارلز سيدني (1987). "تصحيحات لـ "خوارزميات تحويل فورييه السريع ذات القيم الحقيقية"". IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (9): 1353. Bibcode : 1987ITASS..35R1353S . doi : 10.1109/TASSP.1987.1165284 .
  29. ↑ هايدمان، مايكل ت.؛ بوروس، تشارلز سيدني (1986). "حول عدد عمليات الضرب اللازمة لحساب تحويل فورييه المنفصل بطول 2^ n ". معاملات IEEE في الصوتيات والكلام ومعالجة الإشارات . 34 (1): 91-95 . Bibcode : 1986ITASS..34...91H . doi : 10.1109/TASSP.1986.1164785 .
  30. 1 2 دوهاميل، بيير (1990). "الخوارزميات التي تحقق الحدود الدنيا للتعقيد المضاعف لتحويلات فورييه المنفصلة ذات الطول 2n وعلاقتها بالخوارزميات العملية". معاملات IEEE في الصوتيات والكلام ومعالجة الإشارات . 38 (9): 1504-1511 . doi : 10.1109/29.60070 .
  31. ↑ مورغنسترن، جاك (1973). "ملاحظة حول الحد الأدنى للتعقيد الخطي لتحويل فورييه السريع" . مجلة ACM . 20 (2): 305-306 . doi : 10.1145/321752.321761 . S2CID 2790142 . 
  32. ↑ بان، فيكتور يا. (2 يناير 1986). "المفاضلة بين التعقيد الجمعي وعدم التزامن في الخوارزميات الخطية والثنائية الخطية" . رسائل معالجة المعلومات . 22 (1): 11-14 . doi : 10.1016/0020-0190(86)90035-9 . تاريخ الاسترجاع: 31 أكتوبر 2017 .
  33. ↑ باباديميتريو، كريستوس هـ. (1979). "أمثلية تحويل فورييه السريع" . مجلة ACM . 26 (1): 95-102 . doi : 10.1145/322108.322118 . S2CID 850634 . 
  34. ↑ لندي، توماس جيه؛ فان بوسكيرك، جيمس (2007). "نهج مصفوفي جديد لتحويلات فورييه السريعة الحقيقية والالتفافات ذات الطول 2k " . الحوسبة . 80 (1): 23-45 . doi : 10.1007/s00607-007-0222-6 . S2CID 27296044 . 
  35. ↑ هاينال، ستيف؛ هاينال، هايدي (2011). "توليد عائلات خوارزميات تحويل فورييه السريع والبحث عنها" (ملف PDF) . مجلة الإرضاء، والنمذجة المنطقية، والحساب . 7 (4): 145-187 . arXiv : 1103.5740 . Bibcode : 2011arXiv1103.5740H . doi : 10.3233/SAT190084 . S2CID 173109. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 26 أبريل 2012. 
  36. 1 2 دوهاميل، بيير؛ فيترلي، مارتن (1990). "تحويلات فورييه السريعة: مراجعة تعليمية وأحدث التقنيات" . معالجة الإشارات . 19 (4): 259-299 . Bibcode : 1990SigPr..19..259D . doi : 10.1016/0165-1684(90)90158-U .
  37. ↑ إيدلمان، آلان؛ ماكوركوديل، بيتر؛ توليدو، سيفان (1999). "مستقبل تحويل فورييه السريع؟" (ملف PDF) . مجلة SIAM للحوسبة العلمية . 20 (3): 1094-1114 . CiteSeerX 10.1.1.54.9339 . doi : 10.1137/S1064827597316266 . مؤرشف (ملف PDF) من الأصل بتاريخ 2017-07-05. 
  38. ↑ غو، هايتاو؛ بوروس، تشارلز سيدني (1996). "تحويل فورييه التقريبي السريع باستخدام تحويل المويجات". في: أونزر، مايكل أ.؛ الدروبي، أكرم؛ لاين، أندرو ف. (محررون). تطبيقات المويجات في معالجة الإشارات والصور IV . وقائع SPIE . المجلد 2825. الصفحات 250-259 . Bibcode : 1996SPIE.2825..250G . CiteSeerX 10.1.1.54.3984 . doi : 10.1117/12.255236 . S2CID 120514955 .    
  39. ^ شينتوف، أوجنجان ف؛ ميترا، سانجيت ك.؛ هيوت، أولريش. حسين، عبد ن. (1995). “النطاق الفرعي DFT. I. التعريف والتفسيرات والإضافات”. معالجة الإشارات . 41 (3): 261–277 . دوى : 10.1016/0165-1684(94)00103-7 .
  40. ↑ حسنية، هيثم؛ إنديك، بيوتر ؛ كاتابي، دينا؛ برايس، إريك (يناير 2012). "خوارزمية بسيطة وعملية لتحويل فورييه المتناثر" (ملف PDF) . ندوة ACM-SIAM حول الخوارزميات المنفصلة . مؤرشف (ملف PDF) من الأصل بتاريخ 4 مارس 2012.(ملاحظة: انظر أيضًا صفحة الويب الخاصة بـ sFFT .)
  41. ↑ شاتزمان، جيمس سي. (1996). "دقة تحويل فورييه المنفصل وتحويل فورييه السريع" . مجلة SIAM للحوسبة العلمية . 17 (5): 1150-1166 . Bibcode : 1996SJSC...17.1150S . CiteSeerX 10.1.1.495.9184 . doi : 10.1137/s1064827593247023 . 
  42. ↑ ويلش، بيتر د. (1969). "تحليل خطأ تحويل فورييه السريع ذي النقطة الثابتة". معاملات IEEE في الصوتيات والإلكترونيات الصوتية . 17 (2): 151-157 . Bibcode : 1969ITAuE..17..151W . doi : 10.1109/TAU.1969.1162035 .
  43. ↑ إرغون، فوندا (1995). "اختبار الدوال الخطية متعددة المتغيرات". وقائع الندوة السنوية السابعة والعشرين لجمعية الحوسبة الآلية (ACM) حول نظرية الحوسبة - STOC '95 . كيوتو، اليابان. الصفحات 407-416 . doi : 10.1145/225058.225167 . ISBN  978-0897917186. S2CID 15512806 . {{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
  44. ↑ نوسباومر، هنري ج. (1977). "الترشيح الرقمي باستخدام التحويلات متعددة الحدود". رسائل الإلكترونيات . 13 (13): 386-387 . Bibcode : 1977ElL....13..386N . doi : 10.1049/el:19770280 .
  45. ↑ موهلينكامب، مارتن ج. (1999). "تحويل سريع للتوافقيات الكروية" (ملف PDF) . مجلة تحليل فورييه وتطبيقاته . 5 ( 2-3 ): 159-184 . Bibcode : 1999JFAA....5..159M . CiteSeerX 10.1.1.135.9830 . doi : 10.1007 /BF01261607 . S2CID 119482349. مؤرشف (PDF) من الأصل بتاريخ 2017-05-06 . تم الاطلاع عليه بتاريخ 2018-01-11 .  
  46. ↑ "مكتبة libftsh" . مؤرشفة من الأصل بتاريخ 23-06-2010 . تم الاطلاع عليها بتاريخ 09-01-2007 .
  47. ↑ روخلين، فلاديمير؛ تايجرت، مارك (2006). "خوارزميات سريعة لتوسيعات التوافقيات الكروية" (ملف PDF) . مجلة SIAM للحوسبة العلمية . 27 (6): 1903-1928 . رمز Bibcode : 2006SJSC...27.1903R . CiteSeerX 10.1.1.125.7415 . doi : 10.1137/050623073 . مؤرشف (ملف PDF) من الأصل بتاريخ 17 ديسمبر 2014. تاريخ الاسترجاع : 18 سبتمبر 2014 . 
  48. ↑ ستيلين، د. هـ. (1969). "خوارزمية طي سريعة للكشف عن سلاسل النبضات الدورية" . وقائع معهد مهندسي الكهرباء والإلكترونيات . 57 (4): 724-725 . doi : 10.1109/PROC.1969.7051 . ISSN 0018-9219 . 
  49. ↑ بوتس، دانيال؛ ستيدل، غابرييل ؛ تاش، مانفريد (2001). "تحويلات فورييه السريعة للبيانات غير المتساوية المسافات: دليل تعليمي" (ملف PDF) . في بينيديتو، جيه جيه؛ فيريرا، بي. (محرران). نظرية أخذ العينات الحديثة: الرياضيات والتطبيقات . بيركهاوزر . مؤرشف (ملف PDF) من الأصل بتاريخ 26-09-2007.
  50. ↑ بورغيس، ريتشارد جيمس (2014). تاريخ إنتاج الموسيقى . مطبعة جامعة أكسفورد. ISBN 978-0199357178تم الاطلاع عليه بتاريخ 1 أغسطس 2019 .
  51. ↑ تشو، إليانور؛ جورج، آلان (11-11-1999). "الفصل 16". داخل الصندوق الأسود لتحويل فورييه السريع: خوارزميات تحويل فورييه السريع التسلسلية والمتوازية . مطبعة سي آر سي . الصفحات 153-168 . ISBN  978-1-42004996-1.
  52. ↑ فرنانديز دي كوسيو دياز، خورخي؛ فرنانديز دي كوسيو، خورخي (2012-08-08). "حساب توزيع مركز كتلة الذروة النظائرية باستخدام تحويل فورييه". الكيمياء التحليلية . 84 (16): 7052-7056 . doi : 10.1021/ac301296a . ISSN 0003-2700 . PMID 22873736 .  
  53. ↑ "تحويل فورييه السريع وتطبيقاته"، مجلة معالجة الإشارات IEEE.
  54. 1 2 أنور، ك.، وآخرون. "FFT المزدوج لمعايير LTE"، IEEE Xplore.
  55. ↑ كيجيفسكي-كوريا، ت.؛ كريم، أ. (أكتوبر 2006). "فعالية تحويلات هيلبرت والمويجات في تحليل الزمن والتردد" . مجلة الهندسة الميكانيكية . 132 (10): 1037-1049 . doi : 10.1061/(ASCE)0733-9399(2006)132:10(1037) . ISSN 0733-9399 . 
  56. ↑ ستيرن، ريتشارد م. (2020). "ملاحظات حول تحويلات فورييه قصيرة المدى" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 2025-02-08 . تم الاطلاع عليه بتاريخ 2025-02-08 .
  57. ↑ كورمن، توماس هـ.؛ نيكول، ديفيد م. (1998). "إجراء تحويلات فورييه السريعة خارج الذاكرة الرئيسية على أنظمة الأقراص المتوازية". الحوسبة المتوازية . 24 (1): 5-20 . CiteSeerX 10.1.1.44.8212 . doi : 10.1016/S0167-8191(97)00114-2 . S2CID 14996854 .  
  58. ↑ دوت، ألوك؛ روخلين، فلاديمير (1993-11-01). "تحويلات فورييه السريعة للبيانات غير المتساوية المسافات". مجلة SIAM للحوسبة العلمية . 14 (6): 1368-1393 . Bibcode : 1993SJSC...14.1368D . doi : 10.1137/0914081 . ISSN 1064-8275 . 
  59. ↑ روكمور، دانيال ن. (2004). "التقدم الحديث والتطبيقات في تحويلات فورييه السريعة للمجموعات". في: بيرنز، جيم (محرر). الجبر الحسابي غير التبادلي وتطبيقاته . سلسلة علوم الناتو الثانية: الرياضيات والفيزياء والكيمياء. المجلد 136. سبرينغر هولندا. الصفحات 227-254 . CiteSeerX 10.1.1.324.4700 . doi : 10.1007/1-4020-2307-3_9 . ISBN    978-1-4020-1982-1. S2CID 1412268 . 
  60. ↑ ريو، أساكا؛ كازوميتسو، ساكاي؛ ريوكو، ياهاغي (2020). "دائرة كمومية لتحويل فورييه السريع" . معالجة المعلومات الكمومية . 19 (277): 277. arXiv : 1911.03055 . Bibcode : 2020QuIP...19..277A . doi : 10.1007/s11128-020-02776-5 . S2CID 207847474 . 
  61. ↑ "مكتبات أداء Arm" . Arm . 2020. تم الاسترجاع في 16-12-2020 .
  62. ↑ "قائمة كاملة بمكتبات تحويل فورييه السريع (FFT) للغة C/C++" . مجتمع VCV . 2020-04-05 . تم الاطلاع عليه بتاريخ 2021-03-03 .

للمزيد من القراءة