Table of Contents
Open Table of Contents
Mathematical Conditions for DTFT Existence
The Discrete-Time Fourier Transform (DTFT) exists for a sequence x [ n ] x[n] x [ n ]
Absolutely Summable Sequences
Condition : ∑ n = − ∞ ∞ ∣ x [ n ] ∣ < ∞ \sum_{n=-\infty}^{\infty} |x[n]| < \infty ∑ n = − ∞ ∞ ∣ x [ n ] ∣ < ∞
Mathematical Guarantee : If x [ n ] x[n] x [ n ] X ( e j ω ) = ∑ n = − ∞ ∞ x [ n ] e − j ω n X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} X ( e jω ) = ∑ n = − ∞ ∞ x [ n ] e − jωn
converges uniformly for all ω \omega ω X ( e j ω ) X(e^{j\omega}) X ( e jω ) continuous and bounded .
Examples :
Exponential decay : x [ n ] = a n u [ n ] x[n] = a^n u[n] x [ n ] = a n u [ n ] ∣ a ∣ < 1 |a| < 1 ∣ a ∣ < 1 Finite duration : x [ n ] = 0 x[n] = 0 x [ n ] = 0 ∣ n ∣ > N |n| > N ∣ n ∣ > N
Square Summable Sequences (Finite Energy)
Condition : ∑ n = − ∞ ∞ ∣ x [ n ] ∣ 2 < ∞ \sum_{n=-\infty}^{\infty} |x[n]|^2 < \infty ∑ n = − ∞ ∞ ∣ x [ n ] ∣ 2 < ∞
Convergence : The DTFT exists in the mean-square sense :
lim N → ∞ ∫ − π π ∣ X ( e j ω ) − ∑ n = − N N x [ n ] e − j ω n ∣ 2 d ω = 0 \lim_{N \to \infty} \int_{-\pi}^{\pi} \left|X(e^{j\omega}) - \sum_{n=-N}^{N} x[n] e^{-j\omega n}\right|^2 d\omega = 0 lim N → ∞ ∫ − π π X ( e jω ) − ∑ n = − N N x [ n ] e − jωn 2 d ω = 0
Critical Example : Ideal Low-Pass Filter
h ideal [ n ] = sin ( ω c n ) π n , n ≠ 0 h_{\text{ideal}}[n] = \frac{\sin(\omega_c n)}{\pi n}, \quad n \neq 0 h ideal [ n ] = πn s i n ( ω c n ) , n = 0 h ideal [ 0 ] = ω c π h_{\text{ideal}}[0] = \frac{\omega_c}{\pi} h ideal [ 0 ] = π ω c
Summability Analysis :
∑ n = − ∞ ∞ ∣ h ideal [ n ] ∣ = ∞ \sum_{n=-\infty}^{\infty} |h_{\text{ideal}}[n]| = \infty ∑ n = − ∞ ∞ ∣ h ideal [ n ] ∣ = ∞ ∑ n = − ∞ ∞ ∣ h ideal [ n ] ∣ 2 < ∞ \sum_{n=-\infty}^{\infty} |h_{\text{ideal}}[n]|^2 < \infty ∑ n = − ∞ ∞ ∣ h ideal [ n ] ∣ 2 < ∞
Gibbs Phenomenon: Mathematical Analysis
Definition and Cause
Gibbs Phenomenon occurs when approximating discontinuous functions with finite Fourier series . The overshoot near discontinuities does not diminish as more terms are added.
Mathematical Description : For a jump discontinuity, the maximum overshoot is approximately:
Overshoot ≈ 0.089 × ( Jump Height ) \text{Overshoot} \approx 0.089 \times (\text{Jump Height}) Overshoot ≈ 0.089 × ( Jump Height )
This corresponds to about 8.9% overshoot regardless of the number of terms in the partial sum.
Ideal Low-Pass Filter Example
Frequency Response :
H ( e j ω ) = { 1 ∣ ω ∣ ≤ ω c 0 ω c < ∣ ω ∣ ≤ π H(e^{j\omega}) = \begin{cases}
1 & |\omega| \leq \omega_c \\
0 & \omega_c < |\omega| \leq \pi
\end{cases} H ( e jω ) = { 1 0 ∣ ω ∣ ≤ ω c ω c < ∣ ω ∣ ≤ π Truncated Impulse Response :
h N [ n ] = { sin ( ω c n ) π n ∣ n ∣ ≤ N 0 ∣ n ∣ > N h_N[n] = \begin{cases}
\frac{\sin(\omega_c n)}{\pi n} & |n| \leq N \\
0 & |n| > N
\end{cases} h N [ n ] = { πn s i n ( ω c n ) 0 ∣ n ∣ ≤ N ∣ n ∣ > N Frequency Response of Truncated Filter :
H N ( e j ω ) = ∑ n = − N N h N [ n ] e − j ω n H_N(e^{j\omega}) = \sum_{n=-N}^{N} h_N[n] e^{-j\omega n} H N ( e jω ) = ∑ n = − N N h N [ n ] e − jωn
Gibbs Overshoot : Near ω = ω c \omega = \omega_c ω = ω c max ω ∣ H N ( e j ω ) ∣ ≈ 1.089 \max_{\omega} |H_N(e^{j\omega})| \approx 1.089 max ω ∣ H N ( e jω ) ∣ ≈ 1.089
Key Insight : The height of ripples remains constant as N → ∞ N \to \infty N → ∞ width decreases , ensuring that the integral of the error converges to zero.
1. Linearity Property
Mathematical Statement :
a x 1 [ n ] + b x 2 [ n ] ↔ DTFT a X 1 ( e j ω ) + b X 2 ( e j ω ) ax_1[n] + bx_2[n] \xleftrightarrow{\text{DTFT}} aX_1(e^{j\omega}) + bX_2(e^{j\omega}) a x 1 [ n ] + b x 2 [ n ] DTFT a X 1 ( e jω ) + b X 2 ( e jω )
Proof : Direct from the definition of DTFT:
F { a x 1 [ n ] + b x 2 [ n ] } = ∑ n = − ∞ ∞ ( a x 1 [ n ] + b x 2 [ n ] ) e − j ω n \mathcal{F}\{ax_1[n] + bx_2[n]\} = \sum_{n=-\infty}^{\infty} (ax_1[n] + bx_2[n]) e^{-j\omega n} F { a x 1 [ n ] + b x 2 [ n ]} = ∑ n = − ∞ ∞ ( a x 1 [ n ] + b x 2 [ n ]) e − jωn = a ∑ n = − ∞ ∞ x 1 [ n ] e − j ω n + b ∑ n = − ∞ ∞ x 2 [ n ] e − j ω n = a X 1 ( e j ω ) + b X 2 ( e j ω ) = a\sum_{n=-\infty}^{\infty} x_1[n] e^{-j\omega n} + b\sum_{n=-\infty}^{\infty} x_2[n] e^{-j\omega n} = aX_1(e^{j\omega}) + bX_2(e^{j\omega}) = a ∑ n = − ∞ ∞ x 1 [ n ] e − jωn + b ∑ n = − ∞ ∞ x 2 [ n ] e − jωn = a X 1 ( e jω ) + b X 2 ( e jω )
Applications :
Superposition principle for linear systems
Decomposition of complex signals into simpler components
2. Time Shifting Property
Mathematical Statement :
x [ n − n 0 ] ↔ DTFT e − j ω n 0 X ( e j ω ) x[n - n_0] \xleftrightarrow{\text{DTFT}} e^{-j\omega n_0} X(e^{j\omega}) x [ n − n 0 ] DTFT e − jω n 0 X ( e jω )
Proof :
F { x [ n − n 0 ] } = ∑ n = − ∞ ∞ x [ n − n 0 ] e − j ω n \mathcal{F}\{x[n - n_0]\} = \sum_{n=-\infty}^{\infty} x[n - n_0] e^{-j\omega n} F { x [ n − n 0 ]} = ∑ n = − ∞ ∞ x [ n − n 0 ] e − jωn
Let m = n − n 0 m = n - n_0 m = n − n 0 n = m + n 0 n = m + n_0 n = m + n 0 = ∑ m = − ∞ ∞ x [ m ] e − j ω ( m + n 0 ) = e − j ω n 0 ∑ m = − ∞ ∞ x [ m ] e − j ω m = e − j ω n 0 X ( e j ω ) = \sum_{m=-\infty}^{\infty} x[m] e^{-j\omega (m + n_0)} = e^{-j\omega n_0} \sum_{m=-\infty}^{\infty} x[m] e^{-j\omega m} = e^{-j\omega n_0} X(e^{j\omega}) = ∑ m = − ∞ ∞ x [ m ] e − jω ( m + n 0 ) = e − jω n 0 ∑ m = − ∞ ∞ x [ m ] e − jωm = e − jω n 0 X ( e jω )
Physical Interpretation :
Magnitude : ∣ X ( e j ω ) ∣ |X(e^{j\omega})| ∣ X ( e jω ) ∣ Phase : Adds linear phase − ω n 0 -\omega n_0 − ω n 0 Group Delay : τ g = n 0 \tau_g = n_0 τ g = n 0
3. Frequency Shifting Property (Modulation)
Mathematical Statement :
e j ω 0 n x [ n ] ↔ DTFT X ( e j ( ω − ω 0 ) ) e^{j\omega_0 n} x[n] \xleftrightarrow{\text{DTFT}} X(e^{j(\omega - \omega_0)}) e j ω 0 n x [ n ] DTFT X ( e j ( ω − ω 0 ) )
Proof :
F { e j ω 0 n x [ n ] } = ∑ n = − ∞ ∞ e j ω 0 n x [ n ] e − j ω n \mathcal{F}\{e^{j\omega_0 n} x[n]\} = \sum_{n=-\infty}^{\infty} e^{j\omega_0 n} x[n] e^{-j\omega n} F { e j ω 0 n x [ n ]} = ∑ n = − ∞ ∞ e j ω 0 n x [ n ] e − jωn = ∑ n = − ∞ ∞ x [ n ] e − j ( ω − ω 0 ) n = X ( e j ( ω − ω 0 ) ) = \sum_{n=-\infty}^{\infty} x[n] e^{-j(\omega - \omega_0) n} = X(e^{j(\omega - \omega_0)}) = ∑ n = − ∞ ∞ x [ n ] e − j ( ω − ω 0 ) n = X ( e j ( ω − ω 0 ) )
Applications :
Amplitude Modulation : cos ( ω 0 n ) x [ n ] ↔ 1 2 [ X ( e j ( ω − ω 0 ) ) + X ( e j ( ω + ω 0 ) ) ] \cos(\omega_0 n) x[n] \leftrightarrow \frac{1}{2}[X(e^{j(\omega - \omega_0)}) + X(e^{j(\omega + \omega_0)})] cos ( ω 0 n ) x [ n ] ↔ 2 1 [ X ( e j ( ω − ω 0 ) ) + X ( e j ( ω + ω 0 ) )] Frequency Translation : Shifting spectra for communication systems
4. Conjugate Symmetry Property
For Real Sequences (x [ n ] ∈ R x[n] \in \mathbb{R} x [ n ] ∈ R X ( e j ω ) = X ∗ ( e − j ω ) X(e^{j\omega}) = X^*(e^{-j\omega}) X ( e jω ) = X ∗ ( e − jω )
Component-wise Analysis :
Magnitude : ∣ X ( e j ω ) ∣ = ∣ X ( e − j ω ) ∣ |X(e^{j\omega})| = |X(e^{-j\omega})| ∣ X ( e jω ) ∣ = ∣ X ( e − jω ) ∣ Phase : arg [ X ( e j ω ) ] = − arg [ X ( e − j ω ) ] \arg[X(e^{j\omega})] = -\arg[X(e^{-j\omega})] arg [ X ( e jω )] = − arg [ X ( e − jω )] Real Part : Re [ X ( e j ω ) ] = Re [ X ( e − j ω ) ] \text{Re}[X(e^{j\omega})] = \text{Re}[X(e^{-j\omega})] Re [ X ( e jω )] = Re [ X ( e − jω )] Imaginary Part : Im [ X ( e j ω ) ] = − Im [ X ( e − j ω ) ] \text{Im}[X(e^{j\omega})] = -\text{Im}[X(e^{-j\omega})] Im [ X ( e jω )] = − Im [ X ( e − jω )]
Proof : For real x [ n ] x[n] x [ n ] X ∗ ( e − j ω ) = ( ∑ n = − ∞ ∞ x [ n ] e j ω n ) ∗ = ∑ n = − ∞ ∞ x [ n ] e − j ω n = X ( e j ω ) X^*(e^{-j\omega}) = \left(\sum_{n=-\infty}^{\infty} x[n] e^{j\omega n}\right)^* = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} = X(e^{j\omega}) X ∗ ( e − jω ) = ( ∑ n = − ∞ ∞ x [ n ] e jωn ) ∗ = ∑ n = − ∞ ∞ x [ n ] e − jωn = X ( e jω )
5. Time Reversal Property
Mathematical Statement :
x [ − n ] ↔ DTFT X ( e − j ω ) x[-n] \xleftrightarrow{\text{DTFT}} X(e^{-j\omega}) x [ − n ] DTFT X ( e − jω )
Proof :
F { x [ − n ] } = ∑ n = − ∞ ∞ x [ − n ] e − j ω n \mathcal{F}\{x[-n]\} = \sum_{n=-\infty}^{\infty} x[-n] e^{-j\omega n} F { x [ − n ]} = ∑ n = − ∞ ∞ x [ − n ] e − jωn
Let m = − n m = -n m = − n n = − m n = -m n = − m = ∑ m = − ∞ ∞ x [ m ] e j ω m = X ( e − j ω ) = \sum_{m=-\infty}^{\infty} x[m] e^{j\omega m} = X(e^{-j\omega}) = ∑ m = − ∞ ∞ x [ m ] e jωm = X ( e − jω )
Graphical Interpretation : Time reversal corresponds to frequency reversal .
6. Differentiation in Frequency
Mathematical Statement :
n x [ n ] ↔ DTFT j d d ω X ( e j ω ) n x[n] \xleftrightarrow{\text{DTFT}} j \frac{d}{d\omega} X(e^{j\omega}) n x [ n ] DTFT j d ω d X ( e jω )
Proof : Starting with the DTFT definition:
X ( e j ω ) = ∑ n = − ∞ ∞ x [ n ] e − j ω n X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} X ( e jω ) = ∑ n = − ∞ ∞ x [ n ] e − jωn
Differentiating both sides with respect to ω \omega ω d d ω X ( e j ω ) = ∑ n = − ∞ ∞ x [ n ] d d ω e − j ω n = ∑ n = − ∞ ∞ x [ n ] ( − j n ) e − j ω n \frac{d}{d\omega} X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] \frac{d}{d\omega} e^{-j\omega n} = \sum_{n=-\infty}^{\infty} x[n] (-jn) e^{-j\omega n} d ω d X ( e jω ) = ∑ n = − ∞ ∞ x [ n ] d ω d e − jωn = ∑ n = − ∞ ∞ x [ n ] ( − jn ) e − jωn = − j ∑ n = − ∞ ∞ n x [ n ] e − j ω n = − j F { n x [ n ] } = -j \sum_{n=-\infty}^{\infty} n x[n] e^{-j\omega n} = -j \mathcal{F}\{n x[n]\} = − j ∑ n = − ∞ ∞ n x [ n ] e − jωn = − j F { n x [ n ]}
Therefore: F { n x [ n ] } = j d d ω X ( e j ω ) \mathcal{F}\{n x[n]\} = j \frac{d}{d\omega} X(e^{j\omega}) F { n x [ n ]} = j d ω d X ( e jω )
Applications :
Computing moments of signals
Analyzing signal energy distribution
7. Parseval’s Theorem
Mathematical Statement :
∑ n = − ∞ ∞ ∣ x [ n ] ∣ 2 = 1 2 π ∫ − π π ∣ X ( e j ω ) ∣ 2 d ω \sum_{n=-\infty}^{\infty} |x[n]|^2 = \frac{1}{2\pi} \int_{-\pi}^{\pi} |X(e^{j\omega})|^2 d\omega ∑ n = − ∞ ∞ ∣ x [ n ] ∣ 2 = 2 π 1 ∫ − π π ∣ X ( e jω ) ∣ 2 d ω
Physical Interpretation : Total energy in time domain equals total energy in frequency domain.
Proof : Using the inverse DTFT:
x [ n ] = 1 2 π ∫ − π π X ( e j ω ) e j ω n d ω x[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega}) e^{j\omega n} d\omega x [ n ] = 2 π 1 ∫ − π π X ( e jω ) e jωn d ω
The energy is:
∑ n = − ∞ ∞ ∣ x [ n ] ∣ 2 = ∑ n = − ∞ ∞ x [ n ] x ∗ [ n ] \sum_{n=-\infty}^{\infty} |x[n]|^2 = \sum_{n=-\infty}^{\infty} x[n] x^*[n] ∑ n = − ∞ ∞ ∣ x [ n ] ∣ 2 = ∑ n = − ∞ ∞ x [ n ] x ∗ [ n ] = ∑ n = − ∞ ∞ x [ n ] ( 1 2 π ∫ − π π X ∗ ( e j ω ) e − j ω n d ω ) = \sum_{n=-\infty}^{\infty} x[n] \left(\frac{1}{2\pi} \int_{-\pi}^{\pi} X^*(e^{j\omega}) e^{-j\omega n} d\omega\right) = ∑ n = − ∞ ∞ x [ n ] ( 2 π 1 ∫ − π π X ∗ ( e jω ) e − jωn d ω ) = 1 2 π ∫ − π π X ∗ ( e j ω ) ( ∑ n = − ∞ ∞ x [ n ] e − j ω n ) d ω = \frac{1}{2\pi} \int_{-\pi}^{\pi} X^*(e^{j\omega}) \left(\sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}\right) d\omega = 2 π 1 ∫ − π π X ∗ ( e jω ) ( ∑ n = − ∞ ∞ x [ n ] e − jωn ) d ω = 1 2 π ∫ − π π ∣ X ( e j ω ) ∣ 2 d ω = \frac{1}{2\pi} \int_{-\pi}^{\pi} |X(e^{j\omega})|^2 d\omega = 2 π 1 ∫ − π π ∣ X ( e jω ) ∣ 2 d ω
8. Generalized Parseval’s Theorem (Cross-Correlation)
Mathematical Statement :
∑ n = − ∞ ∞ x 1 [ n ] x 2 ∗ [ n ] = 1 2 π ∫ − π π X 1 ( e j ω ) X 2 ∗ ( e j ω ) d ω \sum_{n=-\infty}^{\infty} x_1[n] x_2^*[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} X_1(e^{j\omega}) X_2^*(e^{j\omega}) d\omega ∑ n = − ∞ ∞ x 1 [ n ] x 2 ∗ [ n ] = 2 π 1 ∫ − π π X 1 ( e jω ) X 2 ∗ ( e jω ) d ω
Applications :
Cross-correlation in frequency domainMatched filtering for signal detectionPower spectral density calculations
9. Convolution Theorem
Mathematical Statement :
x 1 [ n ] ∗ x 2 [ n ] ↔ DTFT X 1 ( e j ω ) ⋅ X 2 ( e j ω ) x_1[n] * x_2[n] \xleftrightarrow{\text{DTFT}} X_1(e^{j\omega}) \cdot X_2(e^{j\omega}) x 1 [ n ] ∗ x 2 [ n ] DTFT X 1 ( e jω ) ⋅ X 2 ( e jω )
Proof :
F { x 1 [ n ] ∗ x 2 [ n ] } = F { ∑ k = − ∞ ∞ x 1 [ k ] x 2 [ n − k ] } \mathcal{F}\{x_1[n] * x_2[n]\} = \mathcal{F}\left\{\sum_{k=-\infty}^{\infty} x_1[k] x_2[n-k]\right\} F { x 1 [ n ] ∗ x 2 [ n ]} = F { ∑ k = − ∞ ∞ x 1 [ k ] x 2 [ n − k ] } = ∑ n = − ∞ ∞ ( ∑ k = − ∞ ∞ x 1 [ k ] x 2 [ n − k ] ) e − j ω n = \sum_{n=-\infty}^{\infty} \left(\sum_{k=-\infty}^{\infty} x_1[k] x_2[n-k]\right) e^{-j\omega n} = ∑ n = − ∞ ∞ ( ∑ k = − ∞ ∞ x 1 [ k ] x 2 [ n − k ] ) e − jωn
Changing the order of summation:
= ∑ k = − ∞ ∞ x 1 [ k ] ∑ n = − ∞ ∞ x 2 [ n − k ] e − j ω n = \sum_{k=-\infty}^{\infty} x_1[k] \sum_{n=-\infty}^{\infty} x_2[n-k] e^{-j\omega n} = ∑ k = − ∞ ∞ x 1 [ k ] ∑ n = − ∞ ∞ x 2 [ n − k ] e − jωn
Using the time-shifting property:
= ∑ k = − ∞ ∞ x 1 [ k ] e − j ω k X 2 ( e j ω ) = X 1 ( e j ω ) X 2 ( e j ω ) = \sum_{k=-\infty}^{\infty} x_1[k] e^{-j\omega k} X_2(e^{j\omega}) = X_1(e^{j\omega}) X_2(e^{j\omega}) = ∑ k = − ∞ ∞ x 1 [ k ] e − jωk X 2 ( e jω ) = X 1 ( e jω ) X 2 ( e jω )
Dual Property :
x 1 [ n ] ⋅ x 2 [ n ] ↔ DTFT 1 2 π X 1 ( e j ω ) ∗ X 2 ( e j ω ) x_1[n] \cdot x_2[n] \xleftrightarrow{\text{DTFT}} \frac{1}{2\pi} X_1(e^{j\omega}) * X_2(e^{j\omega}) x 1 [ n ] ⋅ x 2 [ n ] DTFT 2 π 1 X 1 ( e jω ) ∗ X 2 ( e jω )
10. Filter Design Applications
Method 1 : Spectral Inversion
If h L P [ n ] h_{LP}[n] h L P [ n ] h H P [ n ] = δ [ n ] − h L P [ n ] h_{HP}[n] = \delta[n] - h_{LP}[n] h H P [ n ] = δ [ n ] − h L P [ n ]
Frequency Domain : H H P ( e j ω ) = 1 − H L P ( e j ω ) H_{HP}(e^{j\omega}) = 1 - H_{LP}(e^{j\omega}) H H P ( e jω ) = 1 − H L P ( e jω )
Method 2 : Frequency Shifting
h H P [ n ] = ( − 1 ) n h L P [ n ] = e j π n h L P [ n ] h_{HP}[n] = (-1)^n h_{LP}[n] = e^{j\pi n} h_{LP}[n] h H P [ n ] = ( − 1 ) n h L P [ n ] = e jπn h L P [ n ]
Frequency Domain : H H P ( e j ω ) = H L P ( e j ( ω − π ) ) H_{HP}(e^{j\omega}) = H_{LP}(e^{j(\omega - \pi)}) H H P ( e jω ) = H L P ( e j ( ω − π ) )
This shifts the low-pass response by π \pi π
Band-Pass Filter Design
Method : Combine frequency shifting with low-pass prototype:
h B P [ n ] = 2 h L P [ n ] cos ( ω 0 n ) h_{BP}[n] = 2h_{LP}[n] \cos(\omega_0 n) h BP [ n ] = 2 h L P [ n ] cos ( ω 0 n )
where ω 0 \omega_0 ω 0 center frequency and h L P [ n ] h_{LP}[n] h L P [ n ] ω c \omega_c ω c
Result : Band-pass filter centered at ω 0 \omega_0 ω 0 2 ω c 2\omega_c 2 ω c
Advanced DTFT Concepts and Applications
Mathematical Treatment
For a periodic sequence x [ n ] x[n] x [ n ] N N N x [ n + N ] = x [ n ] for all n x[n + N] = x[n] \text{ for all } n x [ n + N ] = x [ n ] for all n
The DTFT contains impulses (Dirac deltas) at harmonic frequencies:
X ( e j ω ) = 2 π ∑ k = 0 N − 1 X [ k ] δ ( ω − 2 π k N ) X(e^{j\omega}) = 2\pi \sum_{k=0}^{N-1} X[k] \delta(\omega - \frac{2\pi k}{N}) X ( e jω ) = 2 π ∑ k = 0 N − 1 X [ k ] δ ( ω − N 2 πk )
where X [ k ] X[k] X [ k ] Discrete Fourier Series (DFS) coefficients :
X [ k ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j 2 π k n / N X[k] = \frac{1}{N} \sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N} X [ k ] = N 1 ∑ n = 0 N − 1 x [ n ] e − j 2 πkn / N
Connection to DFS and DFT
Discrete Fourier Series : Represents periodic sequences in frequency domain
Discrete Fourier Transform : Computes samples of DTFT for finite-length sequences
Relationship : DFT is samples of DTFT:
X [ k ] = X ( e j ω ) ∣ ω = 2 π k / N X[k] = X(e^{j\omega})\Big|_{\omega = 2\pi k/N} X [ k ] = X ( e jω ) ω = 2 πk / N
Windowing Effects and Spectral Leakage
Rectangular Window Analysis
When analyzing finite-length data, we implicitly multiply by a rectangular window:
x w [ n ] = x [ n ] ⋅ w [ n ] x_w[n] = x[n] \cdot w[n] x w [ n ] = x [ n ] ⋅ w [ n ]
where w [ n ] = 1 w[n] = 1 w [ n ] = 1 0 ≤ n ≤ N − 1 0 \leq n \leq N-1 0 ≤ n ≤ N − 1 w [ n ] = 0 w[n] = 0 w [ n ] = 0
Frequency Domain Effect :
X w ( e j ω ) = 1 2 π X ( e j ω ) ∗ W ( e j ω ) X_w(e^{j\omega}) = \frac{1}{2\pi} X(e^{j\omega}) * W(e^{j\omega}) X w ( e jω ) = 2 π 1 X ( e jω ) ∗ W ( e jω )
Rectangular Window DTFT :
W ( e j ω ) = e − j ω ( N − 1 ) / 2 sin ( ω N / 2 ) sin ( ω / 2 ) W(e^{j\omega}) = e^{-j\omega(N-1)/2} \frac{\sin(\omega N/2)}{\sin(\omega/2)} W ( e jω ) = e − jω ( N − 1 ) /2 s i n ( ω /2 ) s i n ( ω N /2 )
Spectral Leakage Phenomenon
Cause : Windowing spreads spectral energy from discrete frequencies across the frequency spectrum.
Mathematical Description : A pure sinusoid becomes:
cos ( ω 0 n ) → 1 2 π ⋅ sin ( ω N / 2 ) sin ( ω / 2 ) ∗ [ δ ( ω − ω 0 ) + δ ( ω + ω 0 ) ] \cos(\omega_0 n) \rightarrow \frac{1}{2\pi} \cdot \frac{\sin(\omega N/2)}{\sin(\omega/2)} * [\delta(\omega - \omega_0) + \delta(\omega + \omega_0)] cos ( ω 0 n ) → 2 π 1 ⋅ s i n ( ω /2 ) s i n ( ω N /2 ) ∗ [ δ ( ω − ω 0 ) + δ ( ω + ω 0 )]
Mitigation Strategies :
Longer observation windows (reduce main lobe width)Smooth window functions (reduce side lobe levels)Zero-padding (interpolate spectrum)
Sampling Theory and Aliasing
Discrete-Time Sampling of Continuous-Time Signals
Sampling Relationship :
x [ n ] = x c ( n T ) x[n] = x_c(nT) x [ n ] = x c ( n T )
where x c ( t ) x_c(t) x c ( t ) T T T
Frequency Domain Relationship :
X ( e j ω ) = 1 T ∑ k = − ∞ ∞ X c ( j ω − 2 π k T ) X(e^{j\omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left(j\frac{\omega - 2\pi k}{T}\right) X ( e jω ) = T 1 ∑ k = − ∞ ∞ X c ( j T ω − 2 πk )
Nyquist Criterion and Anti-Aliasing
Nyquist Frequency : ω N = π \omega_N = \pi ω N = π f N = 1 2 T f_N = \frac{1}{2T} f N = 2 T 1
Aliasing Condition : If X c ( j Ω ) ≠ 0 X_c(j\Omega) \neq 0 X c ( j Ω ) = 0 ∣ Ω ∣ > π / T |\Omega| > \pi/T ∣Ω∣ > π / T
Anti-Aliasing Filter : Low-pass filter with cutoff at π / T \pi/T π / T
H A A ( j Ω ) = { T ∣ Ω ∣ ≤ π / T 0 ∣ Ω ∣ > π / T H_{AA}(j\Omega) = \begin{cases}
T & |\Omega| \leq \pi/T \\
0 & |\Omega| > \pi/T
\end{cases} H AA ( j Ω ) = { T 0 ∣Ω∣ ≤ π / T ∣Ω∣ > π / T Multirate Signal Processing Fundamentals
Downsampling (Decimation)
Operation : y [ n ] = x [ M n ] y[n] = x[Mn] y [ n ] = x [ M n ] M M M
Frequency Domain :
Y ( e j ω ) = 1 M ∑ k = 0 M − 1 X ( e j ( ω − 2 π k ) / M ) Y(e^{j\omega}) = \frac{1}{M} \sum_{k=0}^{M-1} X(e^{j(\omega - 2\pi k)/M}) Y ( e jω ) = M 1 ∑ k = 0 M − 1 X ( e j ( ω − 2 πk ) / M )
Aliasing : Occurs if X ( e j ω ) ≠ 0 X(e^{j\omega}) \neq 0 X ( e jω ) = 0 ∣ ω ∣ > π / M |\omega| > \pi/M ∣ ω ∣ > π / M
Upsampling (Interpolation)
Operation : Insert ( L − 1 ) (L-1) ( L − 1 )
Frequency Domain :
Y ( e j ω ) = X ( e j ω L ) Y(e^{j\omega}) = X(e^{j\omega L}) Y ( e jω ) = X ( e jω L )
Imaging : Creates replicas at multiples of 2 π / L 2\pi/L 2 π / L
Practical Multirate Systems
Decimation Filter : Anti-aliasing filter before downsampling
Interpolation Filter : Anti-imaging filter after upsampling
Design Specifications :
Passband : [ 0 , π / M ] [0, \pi/M] [ 0 , π / M ] Stopband : [ π / M , π ] [\pi/M, \pi] [ π / M , π ] Transition Band : Balance between filter complexity and performance
Connection to DTFT
The Z-transform is a generalization of the DTFT:
X ( z ) = ∑ n = − ∞ ∞ x [ n ] z − n X(z) = \sum_{n=-\infty}^{\infty} x[n] z^{-n} X ( z ) = ∑ n = − ∞ ∞ x [ n ] z − n
DTFT as Special Case : X ( e j ω ) = X ( z ) ∣ z = e j ω X(e^{j\omega}) = X(z)\Big|_{z = e^{j\omega}} X ( e jω ) = X ( z ) z = e jω
Region of Convergence (ROC)
Absolute Convergence : ∑ n = − ∞ ∞ ∣ x [ n ] r − n ∣ < ∞ \sum_{n=-\infty}^{\infty} |x[n] r^{-n}| < \infty ∑ n = − ∞ ∞ ∣ x [ n ] r − n ∣ < ∞ r r r
DTFT Existence : DTFT exists if and only if unit circle is in ROC
Poles and Zeros Analysis
Rational Z-Transform :
H ( z ) = ∑ k = 0 M b k z − k ∑ k = 0 N a k z − k = B ( z ) A ( z ) H(z) = \frac{\sum_{k=0}^M b_k z^{-k}}{\sum_{k=0}^N a_k z^{-k}} = \frac{B(z)}{A(z)} H ( z ) = ∑ k = 0 N a k z − k ∑ k = 0 M b k z − k = A ( z ) B ( z )
Frequency Response : H ( e j ω ) H(e^{j\omega}) H ( e jω ) H ( z ) H(z) H ( z )
Geometric Interpretation :
Zeros : Points where H ( z ) = 0 H(z) = 0 H ( z ) = 0 Poles : Points where H ( z ) = ∞ H(z) = \infty H ( z ) = ∞ Magnitude : Distance from unit circle to poles/zeros affects ∣ H ( e j ω ) ∣ |H(e^{j\omega})| ∣ H ( e jω ) ∣
This comprehensive framework provides the mathematical foundation for advanced digital signal processing techniques and applications in communications, audio processing, and system analysis.