Discrete-time Linear Systems and Discrete Fourier Transforms

Recap

• Vector space \(V\) over a scalar field \(F\)
  • \(F\): real field \(\mathbb{R}\) or complex field \(\mathbb{C}\) in this course
• \(m\times n\) matrix A represents a linear map \(T:F^n\to F^m\)
  • dim null \(T\) + dim range \(T\) = dim \(V\)
• Linear equation: \(Ax=b\)
  • Solution (if it exists): \(u+\) null\((A)\)
• Four fundamental subspaces of a matrix
  • Column space, row space, null space, left null space
• Eigenvalue \(\lambda\) and Eigenvector \(v\): \(Tv=\lambda v\)
  • Distinct eigenvalues have independent eigenvectors
  • Basis of eigenvectors results in a diagonal matrix for \(T\)
  • Every linear map has an upper triangular matrix representation

Linear systems

• 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 systems and linear convolution

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}\)

Linear systems and circular convolution

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}\)

• zero-pad input to convert linear into circular convolution

Linear maps represented by circulant matrices

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}\)

Fourier transforms

Time domain: standard basis

• signals \(x=(x_0,\ldots,x_{K-1})\), \(y=(y_0,\ldots,y_{K-1})\)

Frequency domain: eigenvector basis of circulant matrices

• Matrix to convert from Fourier basis to standard basis

\(\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})\)

LTI systems in Fourier domain

• Matrix to convert from standard basis to Fourier basis

\(\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\ =\ \sqrt{K}\ \hat{x}_k\ \hat{h}_k\)

• \(H_{\text{circ}}\) becomes a diagonal matrix in Fourier basis