ليه الـ DFT بطيء — مشكلة الـ O(N²) | DSP-101

حساب تكلفة الـ DFT

الـ discrete Fourier transform (تحويل فورييه المتقطع) أو DFT بيدّينا كل اللي محتاجينه: تحويل دقيق وبيتعكس بين الـ time domain والـ frequency domain، وبيشتغل صح لأي طول N للـ signal. طب فين المشكلة؟ المشكلة هي تكلفة الحساب — بالتحديد عدد عمليات الضرب والجمع اللي الكمبيوتر لازم يعملها عشان يحسب كل قيم الخرج اللي عددها N.

فكّر في التعريف: كل قيمة خرج X[k] محتاجة تجمع N حاصل ضرب مركّب على الشكل x[n]·W_N^{nk}. يعني N عملية ضرب مركّب وN عملية جمع مركّب لكل bin. وبما إن فيه N bin، فالتكلفة الكلية بتتناسب مع 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²) عملية.

نحط أرقام على البطء ده

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

طول الـ signal N	عمليات الـ DFT (≈6N²)	الوقت @ 1 GFLOP/s	real time؟
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 ثانية	مستحيل

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

مثال: تحليل الصوت في الـ real time

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

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

ليه N² بالذات؟ بصّة أعمق

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

الـ DFT كضرب matrix

\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. كضرب matrix، ده matrix كثيفة N×N مضروبة في vector طوله N: O(N²) عملية — إلا لو استغلّينا البنية الخاصة بتاعة W.

الجملة المفتاح هي استغلال بنية W. على عكس matrix عشوائية، الـ DFT matrix ليها بنية قوية جدًا: عناصرها قوى root of unity واحد W_N = e^{−j2π/N}. القيم بتتكرّر بشكل دوري، وعناصر كتير مرتبطة ببعض بقلب إشارة بسيط. وخوارزمية أشطر تقدر تستخدم البنية دي عشان متحسبش نفس النواتج أكتر من مرة — وده بالظبط اللي الـ Fast Fourier Transform بيعمله.

لما الحل ميبقاش إنك تشتري hardware أسرع

رد الفعل الطبيعي: "اشتري hardware أسرع وخلاص." بس نمو الـ O(N²) بيغلب تحسينات الـ hardware. قانون مور بيضاعف سرعة الـ processor تقريبًا كل 18 شهر. بس لو حجم الـ signals كمان بيتضاعف مع زيادة متطلبات التطبيقات، فـ N² معناها إن مضاعفة N بتضرب التكلفة في 4. يعني الـ hardware لازم يتحسّن 4× عشان بس يلحق زيادة 2× في حجم الـ signal — معركة خسرانة.

نمو تربيعي

signal أطول مرتين

مضاعفة N بتضرب تكلفة الـ DFT في 4. signal أطول 10 مرات بتكلّف 100 مرة أكتر. ومفيش تحسين hardware ثابت يقدر يغلب النمو ده لقيم N الكبيرة.

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

الـ OFDM محتاج N كبيرة

الـ OFDM في الجيل الرابع والخامس بيستخدم N = 2,048 لـ 4,096 subcarrier. والـ channel estimation والـ equalization محتاجين تحويلات كتير في كل ملّي ثانية — مستحيل خالص مع الـ DFT المباشر.

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

فضاء k في الرنين المغناطيسي

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

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

deadlines بالميكروثانية

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

الفكرة الأساسية: استغلال الـ periodicity والتناظر

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

الـ periodicity

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

الـ twiddle factors بتتكرّر بدورة 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 factor الفريدة N بس، مش N² — بس الـ DFT المباشر بيحسب N² حاصل ضرب متوزن بـ twiddle factor. ونسبة التكرار هي N.

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

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

لـ N = 1,024 (حجم window صوت منتشر)، الـ 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 بيدخل في خوارزمية كولي-توكي — تقنية الـ divide and conquer اللي بتحقق التسريع ده عن طريق عمليات الـ butterfly، وإعادة استخدام الـ twiddle factors، والتفكيك الـ recursive.

أهم النقط

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