من النظرية للـ code العملي
خوارزمية كولي-توكي أنيقة نظريًا، بس إنك تحط الـ FFT (تحويل فورييه السريع) في نظام حقيقي محتاج كذا قرار هندسي الكتاب مبيتكلّمش عنه. إيه أحسن طول للدخل؟ لو الـ signal مش هتساع في block واحد نعمل إيه؟ إزاي تعصر آخر نقطة أداء من الـ hardware؟ الدرس ده بيجاوب على الأسئلة دي بشكل عملي.
نقطة البداية في أي تطبيق عملي تقريبًا واحدة: استخدم طول من قوى الـ 2. خوارزمية الـ radix-2 بتقسم على اتنين في كل مرحلة، فمبتشتغلش صح غير لما N = 2^m. ولو حاولت تعمل FFT لـ signal فيها 1000 نقطة يا إما تعمل padding لحد 1024 يا إما تنقل لخوارزمية mixed-radix — والـ padding غالبًا هو الاختيار الأصح.
أحجام قوى الـ 2: الاختيارات المنتشرة
كل مكتبات الـ FFT الكبيرة متظبطة جامد لأحجام قوى الـ 2. والاختيارات المنتشرة في معالجة الـ signals والصوت:
| N | log₂ N | الضرب (N/2·log₂N) | الاستخدام المعتاد |
|---|---|---|---|
| 256 | 8 | 1,024 | صوت latency قليلة، أنظمة مدمجة |
| 512 | 9 | 2,304 | معالجة الكلام، قنوات OFDM |
| 1024 | 10 | 5,120 | صوت عام، spectral analysis |
| 2048 | 11 | 11,264 | spectrum عالي الدقة، audio codec |
| 4096 | 12 | 24,576 | LTE/5G OFDM، صوت احترافي |
| 8192 | 13 | 53,248 | قياسات علمية، تحليل الاهتزاز |
قيم N الكبيرة بتدّي frequency resolution أنعم (Δf = f_s / N) بس بتزوّد الـ latency والـ memory. والاختيار الصح معتمد على المفاضلة بين الـ resolution والـ latency في التطبيق — مش على طول الـ signal لوحده.
الـ zero-padding: كبّر الحجم، متقصّش
لما الـ block يبقى فيه M sample وM مش قوة لـ 2، بنستخدم الـ zero-padding (الحشو بالأصفار): بتلزق أصفار في آخر الـ block لحد ما طوله يوصل لقوة الـ 2 اللي بعدها. block فيه 700 sample بيبقى 1024 sample لما تلزق 324 صفر.
الـ zero-padding بيعمل interpolation للـ spectrum — بيضيف DFT bins أكتر بين الـ bins الموجودة، فبيدّي منحنى أنعم. بس مبيحسّنش الـ frequency resolution الحقيقية. وsinusoidين قريبين ميتفرّقوش بـ DFT فيه M نقطة هيفضلوا ميتفرّقوش بعد الـ padding لـ 2M. والـ resolution بتحدّدها كمية الـ samples الفعلية اللي معاك، مش حجم الـ FFT.
الـ zero-padding: bins أكتر، نفس الـ resolution. بيانات أكتر = resolution أحسن.ومع إنه مبيحسّنش الـ resolution، الـ zero-padding بيتستخدم في كل حتة. والسبب بسيط: بيخلّيك تستخدم أحجام FFT من قوى الـ 2 السريعة، وبيخلّي تحديد مكان القمم الطيفية أسهل لأنه بيدّيك شبكة bins أكثف.
حيلة الـ FFT للـ signals الحقيقية
لما الـ signal الداخلة x[n] تبقى قيمها حقيقية (وده تقريبًا دايمًا — صوت، sensors، signal اتصالات)، خرج الـ DFT بيبقى عنده تماثل خاص: X[N−k] = X*[k] (الـ conjugate symmetry). ومعنى كده إن الـ bins من 0 لـ N/2 بس هي اللي شايلة معلومات فريدة؛ والباقي صور في المراية.
الـ real FFT بيستغل ده بإنه بيحط signalين حقيقيين كل واحد N/2 نقطة في FFT مركّب واحد N نقطة، وبعدين يفكّهم. والنتيجة الصافية: real FFT فيه N نقطة بيكلّف نص عمليات الـ complex FFT. وكل المكتبات الكبيرة بتدّي دوال real FFT مخصوصة — FFTW، ودالة fft في MATLAB، وrfft في NumPy، وApple Accelerate. استخدم دايمًا rfft أو fftplan REAL لما الدخل يبقى حقيقي — مكسب ببلاش بضعف السرعة.
الـ overlap-add: الـ FFT على الـ signals الطويلة
الـ FFT بيشتغل على blocks طولها ثابت N. بس الـ signals الحقيقية — streams صوت، تسجيلات راديو، بيانات sensors — تقريبًا ملهاش آخر. والتقطيع الساذج لـ blocks منفصلة فيها N نقطة صح للتحليل، بس بيفشل لما تكون عايز تعمل filtering للـ signal بالضرب في الـ frequency domain.
عشان تحسب convolution بين signal لانهائية x[n] وimpulse response محدود h[n] طوله M باستخدام الـ FFT، محتاج طريقة الـ overlap-add (الجمع مع التداخل) أو OLA:
النتيجة هي هي الـ convolution المباشر، بس التكلفة الحسابية O(N log N) لكل block بدل O(N·M) — مكسب ضخم لما M يبقى كبير (زي room impulse response فيه 4096 معامل).
طريقة الـ overlap-save (حفظ التداخل) أو OLS بتوصل لنفس النتيجة بطريقة تانية: blocks الدخل بتتداخل بمقدار M−1 sample، وأول M−1 sample من خرج كل IFFT (اللي فيها آثار الـ circular convolution) بتترمي. والطريقتين بيطلّعوا خرج متطابق لو اتنفّذوا صح — والـ OLS مفضّلة في تنفيذات الـ hardware لأنها بتتجنّب خطوة الجمع.
مكتبات الـ FFT ومسرّعات الـ hardware
إنك تكتب FFT صح وسريع من الصفر شغلانة بحثية. عمليًا، استخدم دايمًا مكتبة متجرّبة:
الـ hardware المخصوص للـ FFT (DSP processors وFPGAs وASICs) بيبني مراحل الـ butterfly في الدواير نفسها عشان يطلّع نتيجة كل مرحلة في clock cycle واحدة — عيلة TI C6000 مثلًا بتنفّذ FFT مركّب فيه 1024 نقطة في أقل من ميكروثانية. ومحطات 5G الحديثة بتعمل مئات الآلاف من عمليات الـ FFT كل ثانية بمسرّعات ASIC.
قبل ما تنادي الـ FFT، اتأكد من: (1) طول الدخل قوة لـ 2 — اعمل padding لو مش كده؛ (2) استخدم rfft لو الدخل حقيقي — نص الشغل؛ (3) طبّق window function لو الـ spectral leakage مشكلة؛ (4) اعمل normalization للخرج لو محتاج amplitudes فيزيائية (اقسم على N)؛ (5) استخدم مكتبة ومتكتبش code بتاعك لأي نظام production.
- استخدم دايمًا حجم FFT من قوى الـ 2 — اعمل zero-padding لحد القوة اللي بعدها لو الـ block أقصر.
- الـ zero-padding بيعمل interpolation للـ spectrum (شبكة bins أكثف) بس مبيحسّنش الـ frequency resolution الحقيقية؛ الـ resolution ماشية ورا طول الـ signal الفعلي.
- الـ real FFT بيستغل الـ conjugate symmetry (X[N−k] = X*[k]) عشان يقسم الحساب على اتنين — استخدم
rfftدايمًا لما الدخل يبقى حقيقي. - الـ overlap-add (OLA) والـ overlap-save (OLS) بيخلّوك تعمل filtering للـ signals الطويلة بكفاءة بـ blocks FFT حجمها ثابت.
- نقطة التقاطع اللي الـ filters المبنية على الـ FFT بتتفوّق فيها على الـ convolution المباشر بتقع عند طول filter M ≈ 30–50 معامل.
- استخدم المكتبات الراسخة (FFTW، MKL، cuFFT، Accelerate) — بتظبط نفسها للـ hardware وأسرع بمراتب من الـ code المكتوب بالإيد.
- مسرّعات الـ hardware (DSP processors، FPGAs، ASICs) بتخلّص FFT فيه 1024 نقطة في أقل من ميكروثانية، وده اللي تطبيقات الـ real time في الاتصالات والصوت محتاجاه.