من النظرية إلى الكود العملي
خوارزمية كولي-توكي أنيقة من الناحية النظرية، لكن نشر FFT في نظام حقيقي يستلزم عدة قرارات هندسية لا يتطرق إليها الكتاب المدرسي. ما طول المدخل الأمثل؟ ماذا لو لم يسع الإشارة في كتلة واحدة؟ كيف تستخرج آخر نسب الأداء من العتاد؟ هذا الدرس يجيب على هذه الأسئلة بشكل عملي.
نقطة البداية في كل تطبيق عملي تكاد تكون موحدة: استخدام طول من قوى العدد 2. خوارزمية Radix-2 تقسم على اثنين في كل مرحلة، لذا تعمل بشكل صحيح فقط عندما N = 2^m. محاولة FFT لإشارة مؤلفة من 1000 نقطة تستلزم إما الحشو حتى 1024 أو التبديل إلى خوارزمية Mixed-Radix — والحشو هو الخيار الأصح في الغالب.
أحجام قوى العدد 2: الاختيارات الشائعة
تُحسَّن كل مكتبات FFT الكبرى بشكل مكثف لأحجام قوى العدد 2. الاختيارات الشائعة في معالجة الإشارات والصوت:
| N | log₂ N | الضربات (N/2·log₂N) | الاستخدام النموذجي |
|---|---|---|---|
| 256 | 8 | 1,024 | صوت منخفض الكمون، أنظمة مضمّنة |
| 512 | 9 | 2,304 | معالجة الكلام، قنوات OFDM |
| 1024 | 10 | 5,120 | صوت عام، تحليل الطيف |
| 2048 | 11 | 11,264 | طيف عالي الدقة، مضغوط صوتي |
| 4096 | 12 | 24,576 | LTE/5G OFDM، صوت احترافي |
| 8192 | 13 | 53,248 | قياسات علمية، تحليل الاهتزاز |
القيم الكبيرة لـ N تُعطي دقة ترددية أدق (Δf = f_s / N) لكنها تزيد الكمون والذاكرة. الاختيار الصحيح يعتمد على المفاضلة بين الدقة والكمون في التطبيق — لا على طول الإشارة وحده.
الحشو بالأصفار: زِد الحجم، لا تقطع
حين تكون كتلة الإشارة مؤلفة من M عينة وM ليست قوة للعدد 2، يُستخدم الحشو بالأصفار: إلحاق أصفار بالكتلة حتى يصل طولها إلى القوة التالية لـ 2. كتلة مكونة من 700 عينة تُصبح 1024 عينة بإلحاق 324 صفراً.
الحشو بالأصفار يُحقق استيفاء الطيف الترددي — يُضيف خانات DFT أكثر بين الخانات الموجودة، مما يمنح منحنى أكثر نعومة. لكنه لا يُحسّن الدقة الترددية الحقيقية. جيبان متقاربان لا يمكن تمييزهما بـ DFT ذي M نقطة سيظلان غير مميزَين بعد الحشو إلى 2M. الدقة تحددها كمية العينات الفعلية التي بحوزتك، لا حجم FFT.
الحشو بالأصفار: خانات أكثر، دقة واحدة. بيانات أكثر = دقة أفضل.ومع أنه لا يُحسّن الدقة، يبقى الحشو بالأصفار مستخدَماً في كل مكان. السبب بسيط: فهو يتيح لك أحجام FFT من قوى العدد 2 السريعة، ويجعل تحديد موقع القمم الطيفية أسهل لأنه يمنحك شبكة خانات أكثف.
خدعة FFT للإشارات الحقيقية
حين تكون الإشارة المدخلة x[n] حقيقية القيمة (كما هو الحال دائمًا تقريبًا — صوت، مستشعرات، إشارة اتصالات)، يمتلك خرج DFT تماثلًا خاصًا: X[N−k] = X*[k] (التماثل المترافق). هذا يعني أن الخانات من 0 إلى N/2 فقط تحمل معلومات فريدة؛ الباقي صور مرايا.
FFT الحقيقي يستغل هذا بتعبئة إشارتين حقيقيتين N/2-نقطة في FFT معقد واحد N-نقطة، ثم فكّ التعبئة. الأثر الصافي: FFT حقيقي N-نقطة يكلف نصف عمليات FFT المعقد. وجميع المكتبات الكبرى تُوفر دوال FFT حقيقية مخصصة — FFTW، ودالة fft في MATLAB، وrfft في NumPy، وApple Accelerate. استخدم دائمًا rfft أو fftplan REAL حين يكون المدخل حقيقيًا — مكسب مجاني بضعف السرعة.
الجمع مع التداخل: FFT على الإشارات الطويلة
تعمل FFT على كتل بطول ثابت N. لكن الإشارات الحقيقية — تدفقات صوتية، تسجيلات راديو، بيانات مستشعرات — لا نهاية لها تقريبًا. التقطيع الساذج إلى كتل N-نقطة منفصلة صحيح للتحليل، لكنه يفشل حين تريد ترشيح الإشارة بضرب التحويل الترددي.
لتحسب التواء إشارة لا نهائية x[n] مع استجابة نبضية محدودة h[n] طولها M باستخدام FFT، تحتاج إلى طريقة الجمع مع التداخل (OLA):
النتيجة مطابقة للالتواء المباشر، لكن التكلفة الحسابية O(N log N) لكل كتلة بدلاً من O(N·M) — مكسب هائل حين يكون M كبيراً (مثل استجابة نبضية لغرفة بـ 4096 معامل).
طريقة حفظ التداخل (OLS) تحقق النتيجة ذاتها بشكل مختلف: كتل المدخل تتداخل بمقدار M−1 عينة، وأول M−1 عينة من خرج كل IFFT (تحتوي آثار الالتواء الدائري) تُهمَل. كلتا الطريقتين تُنتجان خرجاً متطابقاً عند التطبيق الصحيح — OLS مُفضَّلة في التنفيذات العتادية لأنها تتجنب خطوة الجمع.
مكتبات FFT ومسرِّعات العتاد
كتابة FFT صحيح وسريع من الصفر مهمة بحثية. في الممارسة، استخدم دائمًا مكتبة مُختبَرة:
العتاد المخصص لـ FFT (معالجات DSP وFPGA ودوائر ASIC) يبني مراحل الفراشة في الدوائر نفسها ليُخرج نتيجة كل مرحلة في نبضة ساعة واحدة — عائلة TI C6000 مثلاً تُنفّذ FFT معقّداً بـ 1024 نقطة في أقل من ميكروثانية واحدة. ومحطات 5G الحديثة تُجري مئات الآلاف من عمليات FFT كل ثانية بمسرِّعات ASIC.
قبل استدعاء FFT، تحقق من: (1) طول المدخل قوة للعدد 2 — احشُ إن لم يكن كذلك؛ (2) استخدم rfft إن كان المدخل حقيقيًا — نصف العمل؛ (3) طبّق دالة تنبيل إن كان التسرب الطيفي مصدر قلق؛ (4) طبّع الخرج إن كنت بحاجة إلى سعات فيزيائية (قسّم على N)؛ (5) استخدم مكتبة ولا تكتب كوداً خاصاً لأي نظام إنتاجي.
- استخدم دائمًا حجم FFT من قوى العدد 2 — احشُ بالأصفار حتى القوة التالية إن كانت الكتلة أقصر.
- الحشو بالأصفار يستوفي الطيف الترددي (شبكة خانات أكثف) لكنه لا يُحسّن الدقة الترددية الحقيقية؛ فالدقة تتبع طول الإشارة الفعلي.
- FFT الحقيقي يستغل التماثل المترافق (X[N−k] = X*[k]) لتخفيض الحساب إلى النصف — استخدم
rfftدائمًا حين يكون المدخل حقيقيًا. - الجمع مع التداخل (OLA) وحفظ التداخل (OLS) يُتيحان ترشيح الإشارات الطويلة بكفاءة بكتل FFT ذات حجم ثابت.
- نقطة التقاطع التي تتفوق فيها المرشحات القائمة على FFT على الالتواء المباشر تقع عند طول المرشح M ≈ 30–50 معامل.
- استخدم المكتبات الراسخة (FFTW، MKL، cuFFT، Accelerate) — فهي تُضبط ذاتياً للعتاد وأسرع بأوامر مقدار من الكود المكتوب يدويًا.
- المسرّعات العتادية (معالجات DSP، FPGAs، دوائر ASIC) تُنجز FFT ذات 1024 نقطة في أقل من ميكروثانية واحدة، وهو ما تحتاجه تطبيقات الزمن الحقيقي في الاتصالات والصوت.