🎛️ إشارة وطيفها
ركّب إشارة من 3 جيوب (الترددات f₁، f₂، f₃). يحسب تحويل فورييه السريع الطيف — تتطابق القمم تمامًا مع تردداتك. هذا بالضبط ما يفعله Shazam للتعرف على أغنية.
الإشارة في الأعلى هي مجموع 3 جيوب. يستعيد تحويل فورييه السريع القمم الثلاث في الطيف بالأسفل. سحري.
📐 1822: فورييه يطرح السؤال
جوزيف فورييه (1768-1830) يبرهن في كتابه « النظرية التحليلية للحرارة » أنّ كل دالة « معقولة » يمكن كتابتها كمجموع لا نهائي من الجيوب. إنها متسلسلة فورييه. تعميمها المستمر هو تحويل فورييه:
F(ω) = ∫ f(t) · e^(−iωt) dt
F(ω) = السعة العقدية للتردد ω المتضمَّن في f(t)
رقميًا، نشتغل على N عيّنة ونحسب تحويل فورييه المتقطع (DFT — Discrete Fourier Transform):
X[k] = Σ x[n] · e^(−2πi kn / N), k = 0, 1, ..., N−1
الحساب الساذج: N عملية ضرب لكل N عيّنة = O(N²). بالنسبة لـ N = مليون، هذا يعني 10¹² عملية — بضع ساعات حتى على حاسوب حديث. غير مقبول بالنسبة للزمن الحقيقي.
⚡ 1965: كولي وتوكي يكتشفان الحيلة
في عام 1965، جيمس كولي (IBM Research) وجون توكي (برينستون + Bell Labs) ينشران خوارزمية تحسب تحويل فورييه المتقطع في O(N log N). بالنسبة لـ N = مليون، هذا يعني ~20 مليون عملية، أي أسرع بـ 50 000 مرة.
الفكرة المركزية: فرّق تسُد. يمكن التعبير عن تحويل فورييه المتقطع ذي الحجم N كتحويلين متقطعين بحجم N/2 (الأدلّة الزوجية والفردية)، يُجمعان مع N/2 عملية ضرب. بالتراجع:
T(N) = 2·T(N/2) + N → T(N) = O(N log N)
🕰️ قصة إعادة اكتشاف
في الحقيقة، كانت الخوارزمية قد اكتُشفت من قبل كارل فريدريش غاوس عام 1805 لحساب مدارات الكويكبات. لكن غاوس كتبها باللاتينية، في دفتر لم يُنشَر في حياته. لم يُكتشَف إلا عام 1977.
كان كولي وتوكي يجهلان تمامًا هذا التاريخ السابق. مقالهما عام 1965 أطلق الثورة. يروي توكي: كان توكي يقدم المشورة لـ جون كينيدي حول كشف التجارب النووية السوفيتية. كان الكشف الزلزالي يتطلب تحويلات فورييه عملاقة. كتب كولي التنفيذ البرمجي في بضعة أسابيع في IBM.
📊 تحويل فورييه العكسي: إعادة بناء الإشارة
بنفس السرعة التي يحسب بها تحويل فورييه السريع الطيف، يعيد تحويل فورييه العكسي بناء الإشارة انطلاقًا من الطيف. هذا يتيح الحلقة: إشارة ← طيف ← تعديل ← إشارة معدّلة.
التعديلات الممكنة:
- الترشيح (Filtrer): حذف بعض الترددات (المنخفضة = إزالة طنين 50 Hz للتيار الكهربائي؛ المرتفعة = تنعيم الضجيج).
- الضغط (Compresser): الاحتفاظ فقط بالترددات المهمة (أساس MP3 و JPEG).
- المعادلة (Égaliser): تضخيم أو إضعاف بعض النطاقات (معادل الصوت).
- التركيب (Synthétiser): إنشاء صوت غير موجود بمزج ترددات.
🚀 تطبيقات ضخمة لتحويل فورييه السريع
- الصوت: MP3، AAC، Opus، Spotify، YouTube Music. كلها تضغط بالمرور عبر تحويل فورييه السريع لتحديد الترددات غير المسموعة المراد حذفها.
- الصورة والفيديو: JPEG، MPEG، H.264، H.265، AV1 تستعمل DCT (تحويل جيب التمام المتقطع)، وهو نوع من تحويل فورييه السريع.
- Wi-Fi و4G و5G: تستعمل تضمينة OFDM (Orthogonal Frequency Division Multiplexing) تحويل فورييه السريع عند كل استقبال. بدون تحويل فورييه السريع، لا اتصال لاسلكي حديث.
- الرادار: تحليل دوبلر (السرعة) عبر تحويل فورييه السريع للإشارة الراديوية المرتدّة. الأرصاد الجوية، الدفاع، السيارات (ACC، الفرملة الطارئة).
- التصوير بالرنين المغناطيسي (IRM): تكتسب الآلة فضاء فورييه للصورة. تستعمل إعادة البناء تحويل فورييه عكسيًا.
- علم الزلازل: كشف الزلازل، تحديد التجارب النووية الجوفية، تحليل الموجات الأرضية.
- علم الفلك الراديوي: تحلل التلسكوبات الراديوية (FAST في الصين، ALMA في تشيلي) الإشارات عبر تحويل فورييه السريع لرسم خريطة السماء.
- Shazam: يتعرف على أغنية في بضع ثوانٍ بتحليل قمم الطيف. بصمة صوتية رقمية.
- ضرب الأعداد الكبيرة: خوارزمية شونهاجه-شتراسن (1971) تضرب عددين صحيحين من N رقمًا في O(N log N log log N) بالمرور عبر تحويل فورييه السريع. مستعملة في كل حساب بدقة كيفية (RSA، التعمية).
- الحساب العلمي: حل المعادلات التفاضلية الجزئية (بواسون، الحرارة، الموجات)، محاكاة الموائع، توقعات الطقس.
- المالية الكمية: معايرة النماذج، تقييم الخيارات.
- علم الجينوم: محاذاة التسلسلات، الأنماط المتكررة.
🎓 الجمال الرياضي
تحويل فورييه السريع هو النموذج الأصلي لخوارزميات فرّق تسُد الأنيقة. الكود الأساسي يتسع في 20 سطرًا:
function FFT(x):
N = length(x)
if N == 1: return x
pair = FFT(x[0::2])
impair = FFT(x[1::2])
X = array of N
for k = 0 to N/2 − 1:
t = exp(−2πi·k/N) * impair[k]
X[k] = pair[k] + t
X[k + N/2] = pair[k] − t
return X
توجد أيضًا أنواع: تحويل فورييه السريع ثنائي الأبعاد للصور، تحويل فورييه السريع على الأعداد الصحيحة (شونهاجه)، تحويل فورييه السريع غير المتساوي التباعد للإشارات غير المنتظمة، تحويل فورييه السريع المتفرّق (Sparse FFT) للأطياف المتناثرة (الذي يُنفَّذ في O(K log N) حيث K هو عدد القمم، MIT 2012).
📐 الرابط مع برنامجك
- الأعداد العقدية: e^(−2πi/N) هو جذر من الدرجة N للوحدة. برنامج الأعداد العقدية الثانية بكالوريا علوم رياضية (صيغة موافر).
- المجاميع: تحويل فورييه المتقطع هو مجموع مفهرس. برنامج الأولى بكالوريا.
- التراجع: تحويل فورييه السريع تراجعي. خوارزمية « فرّق تسُد ». مفهوم خوارزمي محوري.
- اللوغاريتمات: التعقيد log N. برنامج الثانية بكالوريا علوم رياضية.
- الدورية والترددات: جيب/جيب التمام، الدور، التردد. برنامج حساب المثلثات الأولى بكالوريا.
- الجداء الالتفافي (Convolution): يحوّل تحويل فورييه السريع الجداء الالتفافي (البطيء) إلى ضرب (سريع). مبرهنة الالتفاف. مفهوم أساسي في المعادلات التفاضلية الجزئية والاحتمالات.