تعريف الـ DFT (تحويل فورييه المتقطع) وتفسيره | DSP-101

معادلة الـ DFT

الـ Discrete Fourier Transform (تحويل فورييه المتقطع) أو DFT هو الأداة الحسابية الأساسية في تحليل الـ spectrum. لو معاك sequence من N sample x[n]، الـ DFT بيطلّع N قيمة مركّبة X[k]، كل واحدة شايلة الـ amplitude والـ phase بتوع مكوّن frequency معيّن. وتعريف الـ DFT هو:

تعريف الـ DFT

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

X[k] هو الـ DFT للـ sequence اللي فيها N نقطة x[n]. وk بيمشي من 0 لـ N−1، وده بيقابل N frequency على مسافات متساوية حوالين دايرة الوحدة. كل bin k بيقابل الـ frequency f_k = k·f_s/N هرتز أو ω_k = 2πk/N راديان/sample.

الـ inverse DFT (IDFT) بيرجّع x[n] بالظبط من X[k]:

الـ inverse DFT (IDFT)

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

معامل التطبيع 1/N بيضمن إن x[n] ترجع بالظبط. والـ DFT والـ IDFT مع بعض بيعملوا زوج تحويل متماثل وبيتعكس على الـ sequences اللي فيها N نقطة.

كل bin شايل إيه؟

X[k] رقم مركّب. مقداره |X[k]| بيدّي الـ amplitude بتاع المكوّن الـ sinusoidal عند الـ frequency k·f_s/N، وزاويته ∠X[k] بتدّي الـ phase بتاعه. وللـ x[n] اللي قيمها حقيقية، الـ DFT عنده conjugate symmetry: X[N−k] = X*[k]، فالـ bins من 0 لـ N/2 بس هي اللي شايلة معلومات مستقلة.

|X[k]| = الـ amplitude عند f = k·f_s/N — ∠X[k] = الـ phase عند الـ frequency دي

تفسير الـ frequency bins

كل bin k في الـ DFT بيقابل frequency فيزيائية معيّنة. لو الـ signal اتاخد منها samples بمعدّل f_s وحجم الـ DFT هو N، يبقى الـ bin k بيقابل الـ frequency f_k = k·f_s/N. والمسافة في الـ frequency بين binين جنب بعض اسمها الـ bin spacing (تباعد الخانات) — وناس كتير بيسمّوه بالتجاوز frequency resolution — وقيمته:

الـ frequency resolution

\Delta f = \frac{f_s}{N}

الـ bin spacing بيساوي الـ sampling rate مقسوم على طول الـ DFT يعني N. وإنك تقسم Δf على اتنين معناه تضاعف N — بس إنك تجمع samples أكتر هو بس اللي بيحسّن الـ frequency resolution الحقيقية. أما إضافة أصفار عشان توصل لـ N أكبر فبتصغّر الـ bin spacing من غير ما تفصل أي حاجة جديدة.

الـ bin 0

مكوّن الـ DC

X[0] = مجموع كل x[n]. ده مستوى الـ DC — متوسط قيمة الـ signal مضروب في N.

الـ bin N/2

الـ Nyquist frequency

لـ N الزوجي، الـ bin N/2 بيقابل الـ Nyquist frequency f_s/2 — أعلى frequency من غير لبس.

الـ bins N/2+1 … N−1

الـ frequencies السالبة

الـ bins دي بتمثّل الـ frequencies السالبة. وفي الـ signals الحقيقية بتعكس الـ bins 1 … N/2−1 بالـ conjugate symmetry.

الـ bin k

f = k·f_s/N هرتز

التحويل العام: اضرب رقم الـ bin في الـ frequency resolution Δf = f_s/N عشان تاخد الـ frequency الفيزيائية بالهرتز.

الـ DFT كعملية matrix

الـ DFT linear transformation. وممكن يتكتب باختصار كضرب matrix في vector: X = W_N x، حيث W_N هي الـ DFT matrix اللي مقاسها N×N. والعنصر (k, n) في W_N هو الـ twiddle factor (عامل التدوير) W_N^kn:

الـ twiddle factor

W_N = e^{-j2\pi/N} \quad \Rightarrow \quad [\mathbf{W}_N]_{k,n} = W_N^{kn} = e^{-j2\pi kn/N}

W_N هو الـ primitive Nth root of unity. واقع على دايرة الوحدة عند زاوية −2π/N. ورفعه لأُس kn بيلفّه للنقطة رقم kn من النقط اللي على مسافات متساوية على دايرة الوحدة.

الـ DFT matrix symmetric وunitary (لحد معامل التطبيع 1/√N). ومعنى كده إن معكوسها هو ببساطة الـ conjugate transpose بتاعها: W_N⁻¹ = (1/N)W_N^*. والمنظور الـ matrix ده بيوضّح إن الـ DFT مجرد تغيير basis — من basis الـ samples الزمنية لـ basis الـ complex exponentials (الـ frequencies).

الـ DFT المباشر بيكلّف O(N²)

إنك تحسب X = W_N x على طول محتاج N عملية ضرب لكل bin خرج وفيه N bin — يعني N² عملية ضرب مركّبة. ولـ N = 1024 ده بيعدّي مليون عملية. والـ FFT بينزّل ده لـ O(N log N) بإنه يستغل التماثلات في الـ twiddle factors.

الطبيعة الدورية للـ DFT

خاصية دقيقة بس مهمة جدًا: الـ DFT بيعامل x[n] من غير ما يقول كأنها signal دورية لانهائية بفترة N. ومن وجهة نظر الـ DFT، الـ sample اللي بعد x[N−1] بتلف وترجع لـ x[0]. والحسابات على indices الـ DFT دايمًا بتتعمل modulo N.

والـ periodicity دي ليها انعكاسات مباشرة على الـ convolution. لو ضربت spectrumين الـ DFT X[k] وH[k] وبعدين عملت IDFT مش هياخدك للـ linear convolution x[n] ∗ h[n] — هياخدك للـ circular convolution (الالتواء الدائري) x[n] ⊛ h[n]، محسوب modulo N. وعشان تستخدم الـ DFT في الـ linear convolution زي الـ filtering، لازم تطوّل الـ sequence بأصفار عشان تتجنّب الـ time aliasing.

الـ circular convolution

y[n] = \mathrm{IDFT}\{X[k]\cdot H[k]\} = \sum_{m=0}^{N-1} x[m]\,h[(n-m)_{\bmod N}]

IDFT{X[k]·H[k]} بيدّي الـ circular convolution مش الـ linear. وعشان تاخد الـ linear convolution من الـ DFT، ضيف أصفار للـ sequenceين الاتنين لحد ما الطول يبقى ≥ L_x + L_h − 1 قبل ما تحسب الـ DFT.

قاعدة الـ zero-padding للـ linear convolution

لو x[n] طولها L_x وh[n] طولها L_h، اختار حجم DFT بحيث N ≥ L_x + L_h − 1. ضيف أصفار للاتنين لحد الطول N، احسب الـ DFT لكل واحد، اضربهم نقطة بنقطة، وبعدين اعمل IDFT. والنتيجة هي الـ linear convolution بالظبط.

الـ frequency resolution والـ zero-padding

الـ bin spacing في الـ DFT هو Δf = f_s/N، وفيه طريقتين تصغّره بيهم — بس واحدة بس فيهم بتحسّن الـ frequency resolution الحقيقية. إنك تجمع samples أكتر بيحسّنها: الـ window الزمنية الأطول بتزوّد فعلًا الـ time-bandwidth product. أما إنك تلزق أصفار في آخر الـ sequence اللي معاك فمبيحسّنهاش. الـ zero-padding (إضافة الأصفار) بيعمل interpolation للـ spectrum — يعني بيحسب الـ DTFT عند نقط أكتر فبيطلّع منحنى أنعم — بس مبيضيفش أي معلومات طيفية جديدة. وsinusoidين قريبين من بعض ميتفرّقوش بـ L sample ميتفصلوش بالـ zero-padding؛ عشان تفصلهم لازم تسجّل بيانات أكتر.

قاعدة عملية: عشان تفرّق بين sinusoidين بينهم Δf هرتز، محتاج على الأقل T = 1/Δf ثانية من البيانات (L ≥ f_s/Δf sample). والـ zero-padding بعد كده بيخلّي الـ spectrum أنعم بس مبيكشفش قمم جديدة.

الدرس الجاي بيستكشف الـ frequency resolution والـ windowing — إزاي شكل window الرصد بيأثّر في الـ spectral leakage وإيه اللي الـ window functions بتعمله عشان تخفّفه.

أهم اللي اتعلّمته

الـ DFT بيحوّل sequence x[n] فيها N نقطة لـ N قيمة طيفية مركّبة X[k] = Σ x[n] e^−j2πkn/N؛ والـ IDFT بيعكسه بمعامل 1/N.
الـ bin k بيقابل الـ frequency f_k = k·f_s/N هرتز؛ والـ bin spacing Δf = f_s/N.
|X[k]| amplitude و∠X[k]| phase عند الـ frequency k·f_s/N؛ وفي الـ signals الحقيقية النص اللي فوق بيعكس اللي تحت بالـ conjugate symmetry.
الـ DFT ضرب matrix X = W_N x، حيث W_N عناصرها W_N^{kn} = e^{−j2πkn/N}؛ والحساب المباشر O(N²).
الـ DFT بيفترض من غير ما يقول إن x[n] دورية بفترة N — الحسابات على الـ indices كلها modulo N.
ضرب spectrumين الـ DFT وبعدين العكس بيدّي circular convolution؛ ضيف أصفار لحد N ≥ L_x + L_h − 1 عشان تاخد linear convolution.
الـ zero-padding بينعّم الـ spectrum بس مبيحسّنش الـ resolution الفعلية — ده محتاج samples زيادة.