FFT

تحويل فورييه

يظهر تحويل فورييه كثيرًا في الفيزياء والرياضيات، وهذا يعني أن له استخدامات يومية كثيرة أيضًا.

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

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

وبينما لتحويل فورييه صيغة تكاملية، فإننا رقميون، لذا يهمّنا الإصدار المتقطّع. اشتقاق التحويل خارج نطاق هذا التمرين، لكن التحويل المتقطّع الأمامي (إلى النطاق الترددي) يأخذ الصيغة التالية: Xₖ = Σ xₙ * ℯ^(-2iπk * n/N) هنا يمتدّ الجمع على n، وN هو عدد العينات، وk هو التردد، وi هي الوحدة التخيّلية، وxₙ عيّنة واحدة.

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

رغم فائدة تحويل فورييه البالغة، فإنه إذا نُفّذ تنفيذًا ساذجًا يكون بطيئًا بعض الشيء (O(n²)). وتحويل فورييه السريع (FFT) خوارزمية تُسرّع هذا بدرجة كبيرة. ويُنجَز هذا عادةً من خلال استراتيجية فرِّق تسُد، التي تستغل بعض التناظرات في الصيغة وتؤدي إلى تعقيد O(Nlog(N)) مقارب. هذا التسريع يحسّن كثيرًا الجدوى العملية للتحويل ونطاق التطبيقات المناسبة له.