Andrew Thangaraj
Aug-Nov 2020
In engineering, systems process an input and produce an output.
Electrical systems working in discrete time
Input signal: \(x=(x_0,x_1,\ldots,x_{K-1})\)
Output signal: \(y=(y_0,y_1,\ldots,y_{K-1})\)
\(x_n,y_n\): real or complex
Linear, time-invariant (LTI) systems
\(y_n=h_0x_n+h_1x_{n-1}+\cdots+h_Lx_{n-L}\)
\(n=0,1,\ldots,K-1\); assume \(x_i=0\) for \(i<0\)
\(h=(h_0,\ldots,h_L)\): called impulse response
almost all electrical systems use this model
Linear convolution map: \(y\ =\ H_{\text{lin}}\ x\)
\(\begin{bmatrix} y_0\\y_1\\y_2\\\vdots\\y_L\\y_{L+1}\\y_{L+2}\\\vdots\\\vdots\\y_{K-1} \end{bmatrix}=\begin{bmatrix} h_0&0&0&0&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ h_1&h_0&0&0&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ h_2&h_1&h_0&0&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots\\ h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&\cdots&0\\ 0&h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&0\\ \vdots&0&h_L&\cdots&\cdots&h_1&h_0&0&\vdots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&0\\ \cdots&\cdots&\cdots&\cdots&0&h_L&\cdots&\cdots&h_1&h_0 \end{bmatrix}\begin{bmatrix} x_0\\x_1\\x_2\\\vdots\\x_L\\x_{L+1}\\x_{L+2}\\\vdots\\\vdots\\x_{K-1} \end{bmatrix}\)
Circular convolution map: \(y\ =\ H_{\text{circ}}\ x\)
\(\begin{bmatrix} y_0\\y_1\\\vdots\\y_{L-1}\\y_L\\y_{L+1}\\y_{L+2}\\\vdots\\y_{K-2}\\y_{K-1} \end{bmatrix}=\begin{bmatrix} h_0&0&\cdots&\cdots&\cdots&0&h_L&\cdots&h_2&h_1\\ h_1&h_0&0&\cdots&\cdots&\cdots&0&h_L&\cdots&h_2\\ \vdots&\ddots&\ddots&\ddots&\vdots&\vdots&\vdots&\ddots&\ddots&\vdots\\ h_{L-1}&\cdots&h_1&h_0&0&\cdots&\cdots&\cdots&0&h_L\\ h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&\cdots&0\\ 0&h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&0\\ \vdots&0&h_L&\cdots&\cdots&h_1&h_0&0&\vdots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\vdots&0&h_L&\cdots&\cdots&h_1&h_0&0\\ 0&\cdots&\cdots&\cdots&0&h_L&\cdots&\cdots&h_1&h_0 \end{bmatrix}\begin{bmatrix} x_0\\x_1\\\vdots\\x_{L-1}\\x_L\\x_{L+1}\\x_{L+2}\\\vdots\\x_{K-2}\\x_{K-1} \end{bmatrix}\)
LTI systems are represented by the circulant matrix with first column equal to impulse response
What are eigenvectors and eigenvalues of \(H_{\text{circ}}\)?
Let \(\omega=e^{i2\pi/K}=\cos(2\pi/K)+i\sin(2\pi/K)\)
\(\omega^K=1\), \(\omega^{(K-l)k}=\omega^{-lk}\)
Eigenvectors and eigenvalues of \(H_{\text{circ}}\) for \(\{h_0,\ldots,h_L\}\)
\(v_k = (\omega^{0},\omega^{k},\omega^{2k},\cdots,\omega^{(K-1)k})\) for \(k=0,\ldots,K-1\)
\(\lambda_k = h_0w^0+h_1w^{-k}+h_2w^{-2k}+\cdots+h_Lw^{-Lk}\)
Time domain: standard basis
Frequency domain: eigenvector basis of circulant matrices
\(\text{IDFT}_K=\frac{1}{\sqrt{K}}\begin{bmatrix} 1&1&1&\cdots&1\\ 1&\omega&\omega^2&\cdots&w^{K-1}\\ 1&\omega^2&(\omega^2)^2&\cdots&(w^{K-1})^2\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega^{K-1}&(\omega^{K-1})^2&\cdots&(w^{K-1})^{K-1}\\ \end{bmatrix}\)
Discrete Fourier transform of \(x\), \(y\): \(x\), \(y\) in Fourier basis
Denoted \(\hat{x}=(\hat{x}_0,\hat{x}_1,\ldots,\hat{x}_{K-1})\), \(\hat{y}=(\hat{y}_0,\hat{y}_1,\ldots,\hat{y}_{K-1})\)
\(\text{DFT}_K=\frac{1}{\sqrt{K}}\begin{bmatrix} 1&1&1&\cdots&1\\ 1&\omega^{-1}&\omega^{-2}&\cdots&w^{-(K-1)}\\ 1&\omega^{-2}&(\omega^{-2})^2&\cdots&(w^{-(K-1)})^2\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega^{-(K-1)}&(\omega^{-(K-1)})^2&\cdots&(w^{-(K-1)})^{K-1}\\ \end{bmatrix}\)
Input, output, impulse response: \(x\), \(y\), \(h\) in time domain or standard basis
Frequency domain or Fourier basis: \(\hat{x}=\text{DFT}_K\ x\), \(\hat{y}=\text{DFT}_K\ y\), \(\hat{h}=\text{DFT}_K\ h\)
\(\hat{y}_k\ =\ \hat{x}_k\ \hat{h}_k\)