Spectral Analysis

Figure 2: A Digital Signal Processing System
In real-world DSP systems, we are often converting a continuous time signal into a discrete one via sampling (as shown in Figure 2). Because input is constantly streaming in, we can’t process all of it at once, especially for real-time applications. That is why we instead process blocks of length LLL
 at a time. This is accomplished by multiplying our sampled signal by a window function w[n]w[n]w[n]
.
All window functions are real, even, and finite. This means they have real and symmetric DTFTs. The most simply window is a box window (a sinc\text{sinc}sinc
 in the frequency domain). When the signal is multiplied by a window, it amounts to a periodic convolution in the frequency domain.
Definition 6
A periodic convolution of the two spectra X(ejΩ)X(e^{j\Omega})X(ejΩ)
 and W(ejΩ)W(e^{j\Omega})W(ejΩ)
 is given by
​V(ejΩ)=12π∫⟨2π⟩X(ejΩ)W(ej(Ω−ω))dωV(e^{j\Omega})=\frac{1}{2\pi}\int_{\langle 2\pi \rangle}X(e^{j\Omega})W(e^{j(\Omega-\omega)})d\omegaV(ejΩ)=2π1​∫⟨2π⟩​X(ejΩ)W(ej(Ω−ω))dω
​
This periodic convolution means our choice of window function has an impact on our ability to resolve frequencies in the frequency domain.
1.If W(ejΩ)W(e^{j\Omega})W(ejΩ)
 has a wide “main lobe” at the DC frequencies, then the spectrum of V(ejΩ)V(e^{j\Omega})V(ejΩ)
 will be blurred
2.If W(ejΩ)W(e^{j\Omega})W(ejΩ)
 has large “side lobes” at non DC frequencies, then spectral leakage occurs because larger frequencies start bleeding into lower ones.
Another factor which impacts our ability to resolve frequencies in frequency domain is the length of the window. Because an L point DFT samples the DTFT at L points, taking a larger window will resolve the DTFT better. If we don’t want to increase the window length (because doing so would increase the latency of our system), we can zero pad after windowing because zero padding has no impact on the DFT besides sampling the DTFT at more finely spaced samples.
Short Time Fourier Transform (STFT)
By looking at the DFT of a signal x[n]x[n]x[n]
, we only get the frequency information across the entire duration of the signal. Likewise, just by looking at x[n]x[n]x[n]
, we get no frequency information and only temporal information. The STFT is a tool to see both at once.
Definition 7
The short-time fourier transform localizes frequencies in time by creating a spectrogram, an image which shows what frequencies are occuring at what time.
​X[n,ω)=∑m=−∞∞x[n+m]w[m]ejωmX[n, \omega) = \sum_{m=-\infty}^{\infty}x[n+m]w[m]e^{j\omega m}X[n,ω)=∑m=−∞∞​x[n+m]w[m]ejωm
​
The result is discrete on the temporal axis and continuous on the frequency axis. Computing the STFT requires a window function w[n]w[n]w[n]
.
Essentially, we slide a window function around x[n]x[n]x[n]
 and compute the DTFT at every time point.
Discrete STFT
Definition 8
The Discrete STFT is the discrete version of the STFT
​X[r,k]=∑m=0L−1x[rR+m]w[m]WNkmX[r, k] = \sum_{m=0}^{L-1}x[rR+m]w[m]W_N^{km}X[r,k]=∑m=0L−1​x[rR+m]w[m]WNkm​
​
Our window is of length LLL
, RRR
 is how much we shift the window around, and N≥LN \ge LN≥L
is the DFT length we are taking.
Just like before, we take our window and slide it around the signal, computing DFTs at every time point. If N>LN > LN>L
, then we are essentially computing a zero-padded DFT. The DSTFT produces a spectrogram which we can display digitally.
Definition 9
The inverse DSTFT is given by
​x[rR+m]wL[m]=1N∑k=0N−1X[n,k]WN−kmx[rR+m]w_L[m] = \frac{1}{N}\sum_{k=0}^{N-1}X[n, k]W_N^{-km}x[rR+m]wL​[m]=N1​∑k=0N−1​X[n,k]WN−km​
​
As long as the window is never 0 and the windows don’t overlap,
​x[n]=x[n−rL]wL[n−rL].x[n] = \frac{x[n-rL]}{w_L[n-rL]}.x[n]=wL​[n−rL]x[n−rL]​.
​
Time-Frequency Uncertainty
When we compute the spectrogram of a signal, we can think of each coefficient as "tiling" the time-frequency plane. If we consider the normal N point DFT, each DFT coefficient is supported by N points in the time domain. Since the DFT samples the DTFT, it divides the range of [0,2π][0, 2\pi][0,2π]
 into NNN
 segments of width 2πN\frac{2\pi}{N}N2π​
. Each coefficient represents a section of this space, leading to a tiling looking like Figure 3 (for a 5 point DFT).
Figure 3: Time-Frequency tiling of a 5 point DFT
Thinking about the DSTFT, each coefficient is computed using LLL
 points of the original signal. Each coefficient still represents intervals of 2πN\frac{2\pi}{N}N2π​
 in the frequency axis, so it will lead to a tiling which looks like Figure 4.
Figure 4: Time-Frequency tiling of the DSTFT
What these tilings show us is that because we have discretized time and frequency, there is some uncertainty regarding which times and frequencies each coefficient represents.
We can formalize this idea by considering a general transform. All transforms are really an inner product with a set of basis functions
​Tx(γ)=⟨x(t),ϕγ(t)⟩=∫−∞∞x(t)ϕγ⋆(t)dt.T_x(\gamma) = \langle x(t), \phi_\gamma(t) \rangle=\int_{-\infty}^{\infty}x(t)\phi_\gamma^\star(t)dt.Tx​(γ)=⟨x(t),ϕγ​(t)⟩=∫−∞∞​x(t)ϕγ⋆​(t)dt.
​
For each γ\gammaγ
, Tx(γ)T_x(\gamma)Tx​(γ)
 is the projection of the signal onto the basis vector ϕγ(t)\phi_\gamma(t)ϕγ​(t)
. We can use Parseval’s relationship to see that
​Tx(γ)=⟨x(t),ϕγ(t)⟩=∫−∞∞x(t)ϕγ⋆(t)dt=12π∫−∞∞X(jΩ)Φγ⋆(jΩ)dΩ=⟨X(jΩ),12πΦλ(jΩ)⟩.\begin{aligned} T_x(\gamma) &= \langle x(t), \phi_\gamma(t) \rangle =\int_{-\infty}^{\infty}x(t)\phi_\gamma^\star(t)dt \\ &= \frac{1}{2\pi}\int_{-\infty}^{\infty}X(j\Omega)\Phi_\gamma^\star(j\Omega)d\Omega \\ &= \langle X(j\Omega), \frac{1}{2\pi}\Phi_\lambda(j\Omega)\rangle.\end{aligned}Tx​(γ)​=⟨x(t),ϕγ​(t)⟩=∫−∞∞​x(t)ϕγ⋆​(t)dt=2π1​∫−∞∞​X(jΩ)Φγ⋆​(jΩ)dΩ=⟨X(jΩ),2π1​Φλ​(jΩ)⟩.​
​
This means that we can think of our transform not only as a projection of the signal onto a new basis, but also as a projection of the spectrum of our signal onto the spectrum of our basis function. Remember that projection essentially asks "How much of a signal can be explained by the basis". We can formalize this by looking at the signal in a statistical sense and treat it as a probability distribution.
​mt=∫−∞∞t∣ψ(t)∣2dtmΩ=∫−∞∞Ω12π∣Ψ(jΩ)∣2dΩσt2=∫−∞∞(t−mt)2∣ψ(t)∣2dtσΩ2=∫−∞∞(Ω−mΩ)212π∣Ψ(jΩ)∣2dΩ\begin{aligned} m_t &= \int_{-\infty}^{\infty}t|\psi(t)|^2dt &\qquad m_\Omega &= \int_{-\infty}^{\infty}\Omega\frac{1}{2\pi}|\Psi(j\Omega)|^2d\Omega\\ \sigma_t^2 &= \int_{-\infty}^{\infty}(t-m_t)^2|\psi(t)|^2dt &\qquad \sigma^2_\Omega &= \int_{-\infty}^{\infty}(\Omega-m_\Omega)^2\frac{1}{2\pi}|\Psi(j\Omega)|^2d\Omega\\\end{aligned}mt​σt2​​=∫−∞∞​t∣ψ(t)∣2dt=∫−∞∞​(t−mt​)2∣ψ(t)∣2dt​mΩ​σΩ2​​=∫−∞∞​Ω2π1​∣Ψ(jΩ)∣2dΩ=∫−∞∞​(Ω−mΩ​)22π1​∣Ψ(jΩ)∣2dΩ​
​
​mtm_tmt​
 and mΩm_\OmegamΩ​
 are the means of the signal and the spectrum. σt2\sigma_t^2σt2​
 and σΩ2\sigma_\Omega^2σΩ2​
 are the variances. Together, they localize where our signal "lives" in the time-frequency spectrum. The uncertainty principle says
​σtσw≥12.\sigma_t\sigma_w \ge \frac{1}{2}.σt​σw​≥21​.
​
This means there is nothing we can do to get completely accurate time resolution and frequency resolution, and any decisions we make will lead to a tradeoff between them.
Wavelets
While the STFT gives us a better picture of a signal than a full-length DFT, one of its shortcomings is that each coefficient is supported by the same amount of time and frequency. Low frequencies don’t change as much as high frequencies do, so a lower frequency needs to be resolved with more time support whereas a fast signal would requires less time support to resolve properly.
Definition 10
The Wavelet transform finds coefficients which tile the time-frequency spectrum with different time and frequency supports using a mother and father wavelet.
​Wf(u,s)=∫−∞∞f(t)1sΨ⋆(t−us)dtWf(u, s) = \int_{-\infty}^{\infty}f(t)\frac{1}{\sqrt{s}}\Psi^\star\left(\frac{t-u}{s}\right)dtWf(u,s)=∫−∞∞​f(t)s​1​Ψ⋆(st−u​)dt
​
The Wavelet transform essentially makes all of the boxes in Figure 4 different sizes.
Definition 11
The mother wavlet is a scaled bandpass filter Ψ(t)\Psi(t)Ψ(t)
 used for the kernel of the wavelet transform. It must have the following properties:
​∫−∞∞∣Ψ(t)∣2dt=1∫−∞∞Ψ(t)dt=0\int_{-\infty}^{\infty}|\Psi(t)|^2dt=1 \qquad \int_{-\infty}^{\infty}\Psi(t)dt = 0∫−∞∞​∣Ψ(t)∣2dt=1∫−∞∞​Ψ(t)dt=0
​
We need an infinite number of functins to fully represent all frequencies properly, but at a certain level, we don’t care about our ability to resolve them better, so we stop scaling and use a low frequency function Φ(t)\Phi(t)Φ(t)
 to "plug" the remaining bandwidth.
Definition 12
The father wavelet is a low frequency function Φ(t)\Phi(t)Φ(t)
used to ``plug'' the remaining bandwidth not covered by the mother wavelet.
Discrete Wavelet Transform
In discrete time, the wavelet transform becomes
​ds,u=∑n=0N−1x[n]Ψs,u[n]as,u=∑n=0N−1x[n]Φs,u[n]d_{s,u}=\sum_{n=0}^{N-1}x[n]\Psi_{s,u}[n] \qquad a_{s,u}=\sum_{n=0}^{N-1}x[n]\Phi_{s,u}[n]ds,u​=∑n=0N−1​x[n]Ψs,u​[n]as,u​=∑n=0N−1​x[n]Φs,u​[n]
​
The ddd
 coefficients are the detailed coefficients and are computed using the mother wavelet. The capture higher frequency information. The aaa
 coefficients are the approximate coefficients computed using the father wavelet. They represent lower frequency information. The time frequency tiling for the DWT looks like Figure 5.
Figure 5: Time Frequency tiling of wavelets
Notice how each wavelet coefficient is supported by a different amount of time and frequency. We can choose different mother and father wavelets to describe our signals depending on how we want to tile the time-frequency plane.
The DFT
Sampling
Last modified 11mo ago