لماذا تحويل DFT بطيء — مشكلة O(N²) | DSP-101

حساب تكلفة تحويل DFT

يمنحنا تحويل فورييه المتقطع (DFT) كل ما نحتاجه: تحويلاً دقيقاً وعكسياً بين مجال الزمن ومجال التردد، ويعمل بشكل صحيح لأي طول N من الإشارة. فما المشكلة إذن؟ المشكلة هي تكلفة الحساب — تحديداً عدد عمليات الضرب والجمع التي يجب على الحاسوب تنفيذها لحساب جميع قيم الخرج البالغة N.

فكّر في التعريف: كل قيمة خرج X[k] تتطلب جمع N حاصل ضرب مركّب من الصورة x[n]·W_N^{nk}. أي N عملية ضرب مركّب وN عملية جمع مركّب لكل bin. وبما أن هناك N من الـ bins، فإن التكلفة الإجمالية تتناسب مع N².

تعريف DFT

X[k] = \sum_{n=0}^{N-1} x[n]\, W_N^{\,kn}, \quad W_N = e^{-j2\pi/N}, \quad k = 0,1,\ldots,N-1

كل من الـ N قيمة خرج X[k] تتطلب N عملية ضرب مركّب (x[n]·W_N^{nk}) وN−1 عملية جمع، حيث W_N = e^{−j2π/N}. المجموع: O(N²) عملية.

وضع أرقام على مقدار البطء

قد تبدو فئات التعقيد المجردة كـ O(N²) غامضة. لنضع أرقاماً ملموسة على المشكلة. يمكن للمعالج الحديث تنفيذ نحو 10⁹ عملية نقطة عائمة في الثانية (1 GFLOP/s). عملية الضرب المركّب الواحدة تتطلب 4 عمليات ضرب حقيقي و2 عملية جمع — حوالي 6 عمليات حقيقية. لـ N قيمة خرج وN عينة دخل، يتطلب DFT المباشر تقريباً 6N² عملية حقيقية.

طول الإشارة N	عمليات DFT (≈6N²)	الزمن @ 1 GFLOP/s	في الوقت الفعلي؟
64	24,576	25 µs	نعم
256	393,216	0.39 ms	نعم
1,024	6,291,456 (~6 مليون)	6.3 ms	هامشي
4,096	100,663,296 (~100 مليون)	100 ms	صعب
1,048,576 (2²⁰)	~6.6 × 10¹²	~6,600 ثانية	مستحيل

للإشارات الصغيرة يكون DFT سريعاً بما يكفي. تأتي الأزمة عند القيم الكبيرة لـ N. معالجة الصوت بجودة CD (44,100 عينة/ثانية) بأحجام نافذة 4,096–8,192 بالكاد قابلة للإدارة. أي تطبيق يتطلب تحويلات كبيرة — تحليل طيفي عالي الدقة، أنظمة OFDM اللاسلكية، معالجة إشارات الرادار، التصوير الطبي — يصطدم بجدار صلب مع DFT المباشر.

مثال: تحليل الصوت في الوقت الفعلي

محلل الطيف الصوتي في الوقت الفعلي عند 48 كيلوهرتز بنافذة N = 8,192 يجب أن يكمل تحويلاً واحداً كل 170 ms (عند 50% تداخل، كل 85 ms). يتطلب DFT المباشر ~4×10⁸ عملية لكل نافذة. عند 1 GFLOP/s هذا يعني 0.4 ثانية — أبطأ بمرتين من الوقت الفعلي حتى قبل أي معالجة أخرى. بدون خوارزمية أسرع، يستحيل تشغيل التطبيق.

N = 8,192: DFT ≈ 4×10⁸ عملية → 400 ms لكل نافذة (الميزانية الزمنية: 85 ms)

لماذا N² تحديداً؟ نظرة أعمق

لفهم مصدر N²، تخيّل ترتيب العملية الحسابية كضرب مصفوفة في متجه. مصفوفة DFT هي W، وهي مصفوفة N×N يساوي عنصرها (k, n) القيمة W_N^{kn}. حساب X = W·x يضرب متجهاً بطول N في مصفوفة N×N — وهذا تقليدياً N² عملية ضرب-تجميع. كل صف في المصفوفة يعطي قيمة خرج واحدة؛ وكل صف يحتوي على N عنصر.

DFT كضرب مصفوفة

\mathbf{X} = \mathbf{W}\,\mathbf{x}, \quad W_{kn} = e^{-j2\pi kn/N}, \quad \mathbf{W} \in \mathbb{C}^{N \times N}

X[k] = Σ W_N^{kn} · x[n] لـ k = 0,…,N−1. بوصفه حاصل ضرب مصفوفة، هذا مصفوفة كثيفة N×N مضروبة في متجه طوله N: O(N²) عملية — ما لم نستغل بنية W الخاصة.

العبارة الرئيسية هي استغلال بنية W. على عكس المصفوفة العشوائية، مصفوفة DFT شديدة البنية: عناصرها هي قوى جذر واحد من الوحدة W_N = e^{−j2π/N}. تتكرر القيم بشكل دوري، والعديد من العناصر مترابطة بانقلاب إشارة بسيط. خوارزمية أذكى يمكنها استخدام هذه البنية لتجنب حساب نفس الحاصلات أكثر من مرة — وهذا بالضبط ما يفعله تحويل فورييه السريع.

عندما لا يكون الحل في شراء أجهزة أسرع

رد الفعل الطبيعي هو: "فقط اشترِ أجهزة أسرع." لكن نمو O(N²) يتفوق على تحسينات الأجهزة. قانون مور يضاعف سرعة المعالج تقريباً كل 18 شهراً. لكن إذا تضاعف حجم الإشارات أيضاً مع تزايد متطلبات التطبيقات، فإن N² يعني أن مضاعفة N ترفع التكلفة أربعة أضعاف. يجب أن تتحسن الأجهزة 4× فقط لمواكبة زيادة 2× في حجم الإشارة — وهي معركة خاسرة.

تحجيم تربيعي

إشارة أطول بضعفين

مضاعفة N ترفع تكلفة DFT 4 مرات. إشارة أطول 10 مرات تكلف 100 مرة أكثر. لا تحسّن جهاز ثابت يمكنه التغلب على هذا النمو للقيم الكبيرة لـ N.

أنظمة لاسلكية

OFDM يتطلب N كبيراً

الجيل الرابع والخامس OFDM يستخدم N = 2,048 إلى 4,096 حاملة فرعية. تقدير القناة والتعادل يتطلبان تحويلات متعددة في كل مللي ثانية — مستحيل تماماً مع DFT المباشر.

التصوير الطبي

فضاء k في التصوير بالرنين

إعادة بناء صورة الرنين المغناطيسي تشمل تحويل DFT ثنائي الأبعاد على شبكة 256×256 أو أكبر. تكلفة DFT المباشر ثنائي الأبعاد تتناسب مع N⁴ — مليارات العمليات لكل شريحة صورة.

الرادار والسونار

مواعيد نهائية بالميكروثانية

معالجة نبضات الرادار يجب أن تنتهي في ميكروثوانٍ لتحديث مسارات الهدف. تأخّر DFT المباشر سيجعل النظام يفوّت كل فرصة للكشف.

الفكرة الرئيسية: استغلال الدورية والتناظر

الطريق إلى خوارزمية أسرع يبدأ بملاحظتين حول عامل الـ twiddle W_N^{kn} = e^{−j2πkn/N}:

الدورية

W_N^{\,kn} = W_N^{\,k(n+N)}

عوامل الـ twiddle تتكرر بدورة N. القيمتان W_N^{kn} وW_N^{k(n+N)} متطابقتان.

التناظر

W_N^{\,k+N/2} = -\,W_N^{\,k}

الإزاحة بنصف الدورة تعني قلب الإشارة. W_N^{k+N/2} تساوي −W_N^k بالضبط.

هاتان الخاصيتان تعنيان أنه في الحساب الكامل N²، تُحسب كثير من الحاصلات أكثر من مرة. إذا استطعنا إعادة تنظيم الحساب بذكاء بحيث يُقيَّم كل حاصل فريد مرة واحدة فقط، يمكننا تقليل إجمالي العمل بشكل جذري. عدد قيم عامل الـ twiddle الفريدة هو N فقط، لا N² — لكن DFT المباشر يحسب N² حاصل ضرب مرجّح بعامل twiddle. نسبة التكرار هي N.

إزالة هذا التكرار هي الفكرة الجوهرية لتحويل فورييه السريع. بتقسيم DFT بشكل متكرر — أولاً إلى تحويلات فرعية للعينات ذات الإندكس الزوجي وتلك ذات الإندكس الفردي، ثم تكرار التقسيم — تخفّض الخوارزمية عدد عمليات الضرب المركّب من N² إلى (N/2)·log₂ N. وهذا الثنائي هو الاصطلاح الذي تقوم عليه كل أرقام التسريع في هذه الدورة: نحسب عمليات الضرب المركّب، فيكون التسريع هو النسبة N² ÷ (N/2)·log₂ N = 2N / log₂ N. عند N = 4,096 هذا تخفيض بعامل 683، وعند N = 1,048,576 يصل التخفيض إلى 100,000 تقريباً. الفرق بين "مستحيل في الوقت الفعلي" و"سريع بشكل تافه" على الأجهزة العادية.

مقارنة ملموسة

لـ N = 1,024 (حجم نافذة صوتية شائع)، يتطلب DFT المباشر N² = 1,048,576 عملية ضرب مركّب. أما الـ FFT فلا يحتاج سوى (N/2)·log₂ N = 5,120 — تسريع بمقدار 205×. وعند N = 4,096 يصبح التسريع 683×، وعند N = 1,048,576 يصل إلى ~100,000×. هذا ليس تحسيناً هندسياً؛ بل خوارزمية مختلفة جذرياً.

DFT المباشر: O(N²) → FFT: O(N log₂ N) — نفس النتيجة الرياضية، عمليات أقل بكثير

الدرس 6.2 يتعمق في خوارزمية كولي-توكي — تقنية الفصل والغزو التي تحقق هذا التسريع من خلال عمليات الفراشة، وإعادة استخدام عوامل الـ twiddle، والتحليل المتكرر.

أهم النقاط

يحسب DFT المباشر N قيمة خرج، كل منها يتطلب N عملية ضرب — تكلفة إجمالية O(N²) تنمو تربيعياً مع طول الإشارة.
لـ N = 1,024 يتطلب DFT المباشر ~6 مليون عملية؛ لـ N = 2²⁰ يتطلب ~6.6 تريليون — تتجاوز بكثير ميزانيات الوقت الفعلي.
لا يمكن لتحسينات الأجهزة التغلب على نمو O(N²): مضاعفة طول الإشارة يربّع العملية الحسابية، فالمعالجات الأسرع تؤخر الاختناق فحسب.
التطبيقات الحقيقية — OFDM اللاسلكي، التصوير الطبي، الرادار — تتطلب تحويلات على آلاف إلى ملايين النقاط في ظل قيود زمنية صارمة، مما يجعل DFT المباشر غير عملي تماماً.
مصفوفة DFT ليست مصفوفة عشوائية؛ عناصرها هي قوى جذر واحد من الوحدة W_N = e^{−j2π/N}، مما يخلق تكراراً هائلاً في الحساب المباشر.
عامل الـ twiddle W_N^{kn} دوري (بدورة N في k وn) ولديه تناظر W_N^{k+N/2} = −W_N^k — خصائص يمكن لخوارزمية ذكية استغلالها لإعادة استخدام النتائج الوسيطة.
إزالة تكرار عامل الـ twiddle يخفض عدد العمليات من N² إلى (N/2)·log₂ N — تحويل فورييه السريع، الذي يُستكشف في الدرس 6.2.