SU-ENGR76 APR302024 — Jemoka Knowledge Base

Discrete Fourier Transform The matrix operation is computationally intractable as it scales with O(N^{2}). The complexity can be reduced via a Fast-Fourier Transform with O(n\log n) time. We can compute the Fourier representation forward and backwards by inverting the Fourier matrix Source Coding Review Basic Source We can just do Huffman Coding directly. Continuous Real Source We can quantize the continuous source, and then do Huffman Coding. Continuous-Time Source Few strategies to get discrete symbols. sampling: to get discrete points quantization: to turn int continuous source symbols to discrete symbol-set compression: Huffman Coding Lossless Sampling sampling is the task of obtaining discrete time samples of a continuous time signals. Suppose we have a finite-period signal T. We know that we can extend it into a T periodic function model-able by an at-least infinite Fourier Series by an repeated extension. Moreover, assume that the spectrum of the signal can be represented by a finite sequence Fourier Series—essentially, we assume that our signal is a Finite-Bandwidth Signal, and moreover the f_{\min} = 0, and f_{\max} = B < \infty. By making the assumption above, we know that our resulting Fourier series has a frequency bounded by \frac{j}{T} \leq B \implies j \leq BT, meaning, this gives:

\begin{align} &f(x) = b_0 + \sum_{k=1}^{\infty} \left( a_{k} \cos(k \omega x) + b_{k} \sin(k \omega x)\right) \\ \Rightarrow\ & f(x) = b_0 + \sum_{k=1}^{BT} \left( a_{k} \cos(k \omega x) + b_{k} \sin(k \omega x)\right) \end{align}

Now, let us consider what would happen if we tried to sample this signal every S second: at x=0

\begin{equation} y_0 = b_0 + \sum_{j=1}^{BT} a_{j} \sin 0 + b_{j} \cos 0 = b_0 + b_1 + \dots + b_{BT} \end{equation}

at x=S

\begin{equation} y_{S} = b_0 + \sum_{j=1}^{BT} a_{j} \sin \left(2 \pi \frac{j}{T} S \right) + b_{j} \cos \left(2\pi \frac{j}{T} S\right) \end{equation}

… you will note that we have 2BT + 1 unknowns (b_0, b_1, …, b_{BT}, a_{1}…, a_{BT}). This means that we need to at least make 2BT+1 samples. This means that we need to choose our S such that:

\begin{equation} \frac{T}{S} \geq 2BT + 1 \implies S \leq \frac{T}{2BT+1} \approx \frac{T}{2BT} = \frac{1}{2B} \end{equation}

meaning we can reconstruct our whole function as long as our sampling is at least double the Bandwidth of our signal. This is the nyquist limit. We state this more formally in nyquist sampling theorem