DSP#2
0. Key ideas
DSP #1 was about performing fourier analysis for the continous time signal. Now, time for discrete time signals.
1. DTFT
DTFT evaluates discrete-time aperiodic signals.
Compared to CTFT :
-
CTFT is for continuous-time aperiodic signal. It has a frequency range \((-\infty, \infty)\). Any frequency can exist.
\[X(\omega) = \int_{-\infty}^{\infty} x(t)e^{-j\omega_0t}dt\] -
DTFT has frequency range \(2\pi\). Thus DTFT is periodic, which means that there can only be a limited value of frequency that can exist. However, frequency values are still continous within the \(2\pi\) range.
2. z-transform
z-transform is a more general version of DTFT. DTFT don’t always exist/converge, since it cannot be computed for signals that are not stable. However, z-transform can.
Let $z^n$ be an eigenfunction of a discrete-time LTI system. (\(e^{jwn}\) is that of a continuous-time LTI system)
\[x[n] = z^n\] \[y[n] = \sum_{k=-\infty}^{\infty}h[k]x[n-k] = H(z)z^n\]$H(z)$ is called a transfer function and is a complex number.
Z-transform is :
\[X(z) = \sum_{n=-\infty}^{\infty} x[n]z^{-n}\]This equals to DTFT when \(z=e^{j\omega}\), meaning that DTFT is when z value is on a unit circle in the z-plane. This is also the reason why DTFT is \(2\pi\) periodic.
The benefit of z-transform is that it can be used to evaluate systems that are not stable (ex. feedback loop).
Properties of z-transform
\[x[k] \Leftrightarrow X(z)\]Time reversal
\[x[-k] \Leftrightarrow X(\frac{1}{z})\]Time shift
\[x[k-k_0] \Leftrightarrow z^{-k_0}X(z)\]Exponential sequence
\[\alpha^k x[k] \Leftrightarrow X(\frac{z}{\alpha})\]z-domain differentiation
\[kx[k] \Leftrightarrow -z\frac{d}{dz}X(z)\]Region of convergence (ROC)
If \(z=re^{j\omega}\), then z-tranform looks like DTFT applied to \(x[n]r^{-n}\).
\[X(z) = X(re^{j\omega}) = \sum_{n=-\infty}^{\infty} (x[n]r^{-n})e^{-jwn} = DTFT(x[n]r^{-n})\]Thus, we can say that z-tranform converges if
\[\sum_{n=-\infty}^{\infty} \lvert x[n]r^{-n} \rvert < \infty\]If ROC includes the unit circle, we say the system is stable.
Poles and zeros
\[X(z) = \frac{N(z)}{D(z)}\]\(N(z) = 0\) are zeros, \(D(z) = \infty\) are poles.
3. DFT
More appropriate name is discrete fourier series. DFT analyzes finite and periodic digital input signal x. The resulting frequency domain is discrete (unlike DTFT).
Compare DTFT with DFT.
\[X(\omega) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}\] \[X[k] = \sum_{n=0}^{N-1} x[n]e^{-jk\frac{2\pi}{N}n}\]These two are almost equivalent, when \(\omega = \frac{2\pi k}{N}\). Also, unlike DTFT, input x[n] is finite/periodic.
In other words, we can interprete DFT as DTFT sampled in the frequency domain at \(\omega = \frac{2\pi k}{N}\) interval.
DFT can be computed via matrix multiplication:
A faster algorithm of DFT is FFT.