# EECE 451 Digital Signal Processing
These are my notes for the POSTECH course EECE 451 Digital Signal Processing. It is a combination of both lecture notes as well as stuff I learnt from googling to clarify terms used in the notes or the homework.

Some things which are missing are certain matrix expressions due to the tediousness of formatting them, as well as diagrams.

In addition, there are links to webpages I found useful to understanding the content

## 1. Discrete time(DT) signals and systems
### Obtaining a DT signal
Sampling a continuous time signal $x(t)$ every $t = nT$ to obtain a DT signal $x[n]$

This is equivalent to convolving a continous time signal with a delta function train, ie $h[m] = \sum_{k = 0}^\infty \delta[m-nk]$

### Basic operations
1. Flipping
$x[n] \rightarrow x[-n]$

2. Scaling
$x[n] \rightarrow x[2n]$
:::danger
Note: Samples can be lost when scaling a signal!
:::

3. Shifting
$x[n] \rightarrow x[n+1]$

#### Even/Odd signals
- An even signal is a signal that fulfills $x[n] = x[-n]$. An example of an even signal is a discrete cosine wave.
- An odd signal is a signal that fulfills $x[n] = -x[-n]$. An example of an odd signal is a discrete sine wave
- Every signal can be decomposed into even and odd parts:
- $Ev(x[n]) = \frac{1}{2}(x[n]+x[-n])$
- $Od(x[n]) = \frac{1}{2}(x[n]-x[-n])$

### Periodicity
- A DT signal $x[n]$ is periodic with period $N$ if $N$ is the smallest positive integer such that $x[n+N] = x[n]$ for all integer n
- Time shifts remain periodic
- Sums of periodic functions are periodic. For 2 functions $x_1[n], x_2[n]$ with periods $N_1, N_2$, $x_1[n] + x_2[n]$ has period lcm$(N_1, N_2)$

### Special signals
Delta function
$$\delta[n] = \Biggl \{ \begin{matrix}1 \text{ if n = 0} \\ 0 \text{ otherwise} \end{matrix}$$

Step function
$$u[n] = \Biggl \{ \begin{matrix}1 \text{ if n } \ge \text{0} \\ 0 \text{ otherwise} \end{matrix}$$

Connection between step and delta functions
$u[n]= \delta[n] + \delta[n-1] + ... = \displaystyle \sum_{k=0}^{\infty}\delta[n-k]=\sum_{k=-\infty}^{n}\delta[k]$
$\Rightarrow \delta[n] = u[n]-u[n-1]$
:::info
This is the discrete equivalent of $\frac{d}{dt}u(t) = \delta (t)$
:::

### Representation property
$$x[n] = \displaystyle \sum_{k=-\infty}^{\infty} x[k] \delta[n-k]$$

### Sampling property
Swapping the representation property around gives the sampling property
$$\displaystyle \sum_{k=-\infty}^{\infty} x[k] \delta[n-k] = x[n]$$

### DT sinusoids
Unlike continuous time sinusoids, DT sinusoids cannot have an infinite number of frequencies

For two sinusoids $e^{j\omega n}$ and $e^{j(\omega + 2\pi)n}$,

$$e^{j(\omega + 2\pi)n} = e^{j2\pi n} \cdot e^{j\omega n} = e^{j\omega n}$$

This implies that a DT sinusoid can only have a frequency range of $2\pi$

### Signal power
The energy over the interval $n_1 \le n \le n_2$ is given by
$$\sum_{n=n1}^{n_2} |x[n]|^2$$

A signal with finite energy has $P_{\infty} = 0$ and is sometimes called an "energy type" signal

Any signal with $0 < P_{\infty} < \infty$ has $E_{\infty} = \infty$ and is sometimes called a "power type" signal

### Correlation
For energy type signals the cross correlaton between $x[n]$ and $y[n]$ with lag $l$ is given by
$$r_{xy}[l] ≜ \sum_{n=-\infty}^\infty x[n]y^*[n-l] = \sum_{n=-\infty}^\infty x[n+l]y^*[n]$$

Essentially the cross correlation measures how much 2 signals match each other

The autocorrelation is the correlation of a signal with itself, $r_{xx}$

The maximum autocorrelation is always $r_{xx}[0] = E_x$, and thus the normalised autocorrelation is defined as $\frac{r_{xx}[l]}{r_{xx}[0]}$

Also, the autocorrelation of a periodic signal with period $N$ will take it's maximum value of $E_x$ when $l$ is an integer multiple of $N$

The squared euclidian distance is
$$\sum_{n=-\infty}^{\infty}|x[n] - Ay[n-l]|^2 = E_x + |A|^2E_y - 2\text{Re}(\text{Ar}^*_{xy}[l])$$

and it's minimum occurs at $A = \frac{r_{xy}[l]}{E_y}$

For power type signals, the time average cross correlation function is
$$\bar{r}_{xy}[l] ≜ \lim_{M\rightarrow \infty}\frac{\sum_{n=-\infty}^\infty x[n]y^*[n-l]}{2M+1} = \lim_{M\rightarrow \infty}\frac{\sum_{n=-\infty}^\infty x[n+l]y^*[n]}{2M+1}$$

## 2. Discrete time systems

$x[n] \rightarrow y[n] = f(x[n])$

- x[n] is the input signal
- y[n] is the output signal
- f is a system

#### RECAP - LTI systems

**Linearity**

- If $x_1[n] \rightarrow y_1[n]$ and $x_2[n] \rightarrow y_2[n]$, then $ax_1[n] + bx_2[n] \rightarrow ay_1[n] + by_2[n]$

A linear system satisfies the superposition property

**Time invariant**

$$x[n] \rightarrow y[n] \Rightarrow x[n-n_0] \rightarrow y[n-n_0] \space \forall n_0 \in \mathbb{Z}$$

Behaviour does not depend on what time it is

An implication of this property is that periodicity is conserved in time invariant systems

**Response**

Completely characterised by impulse response

#### Discrete time convolution

Any signal $x[n]$ can be expressed as a linear combination of impulse functions and time shifts, ie:

$$ x[n] = \sum_{k=-\infty}^{\infty} x[k]\delta [n-k] $$

where $x[k]$ is the value of $x[n$] at some time time $k$

Let $h[n]$ be the impulse response to the input $\delta[n]$ implying that $h[n-k]$ is the response to $\delta [n-k]$

$$ x[n] = \sum_{k=-\infty}^{\infty} x[k]\delta [n-k] \rightarrow y[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k] $$

$y[n]$ is defined as the convolution sum:

:::warning

$$x[n]*h[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k]$$

:::

The convolution sum can be expressed in matrix form [link](https://en.wikipedia.org/wiki/Toeplitz_matrix#Discrete_convolution)
**Properties of convolution**

Associative

$$x[n] * (h_1[n] * h_2[n]) = (x[n] * h_1[n]) * h_2[n]$$

Distributive

$$x[n] * (h_1[n] + h_2[n]) = x[n] *h_1[n] + x[n] * h_2[n]$$

### Difference equation representation of LTI systems

A linear constant-coefficient difference equation(LCCDE) defines the relationship between an input sequence $x[n]$ and output $y[n]$. A causal LTI system can be described by a LCCDE

$$\sum_{k=0}^{K}a_ky[n-k] = \sum_{m=0}^{M}b_my[n-m]$$

#### Other properties

**Causality**

A DT-LTI system is causal iff for all $k \in \mathbb{Z}$, $x[n] = 0$ for $n<k$ implies $y[n] = 0$ for $n<k$

**Stability**

A system is stable if the output is bounded whenever the input is bounded.

**Eigenfunctions**

Complex exponentials are eigenfunctions of discrete time systems. Proof can be easily shown from the convolution definition.

## 3. Discrete time fourier transform
Discrete time fourier transform(DTFT)
:::warning
$$X(e^{j\omega}) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}$$
:::

Inverse discrete time fourier transform (IDTFT)
:::warning
$$x[n] = \frac{1}{2\pi}\int_{-\pi}^{\pi} X(e^{j\omega})e^{j\omega n} \space d\omega$$
:::

#### Properties of the DTFT
Periodicity
$$X(e^{j(\omega+2m\pi)}) = X(e^{j\omega})$$

Conjugate symmetry
If $x[n] = x^*[n]$ then $X(e^{j\omega}) = X^*(e^{-j\omega})$

Linearity
$$x[n] = ax_1[n] + bx_2[n] \Rightarrow aX_1(e^{j\omega}) + bX_2(e^{j\omega})$$

Time delay
$$y[n] = x[n-n_d] \Rightarrow Y(e^{j\omega}) = e^{-j\omega n_d}X(e^{j\omega})$$

Frequency shift
$$y[n] = e^{j\omega_c n}x[n] \Rightarrow Y(e^{j\omega}) = X(e^{j(\omega - \omega_c)})$$

DFT maps convolution to multiplication
$$x[n] * h[n] = X(e^{j\omega})H(e^{j\omega})$$

#### DTFT filter design
- Designing a filter is essentially designing the impulse response of a system
- It is much easier to make a filter in the frequency domain compared to the time domain

**Ideal Low pass filter**
Time domain impulse response
:::warning
$$h_{LP}[n] = \frac{sin(\omega_c n)}{\pi n}$$
http://mathworld.wolfram.com/SincFunction.html
:::

Frequency domain impulse response
:::warning
$$H_{LP}(e^{j\omega}) = \Biggl \{ \begin{matrix}1 \text{ if } \omega_c \le |\omega| \\
0 \text{ if } \omega \lt |\omega| \le \pi
\end{matrix}$$
:::

**Ideal High pass filter**
Time domain impulse response
:::warning
$$h_{HP}[n] = \delta[n] - \frac{sin(\omega_c n)}{\pi n}$$
:::

Frequency domain impulse response
:::warning
$$H_{HP}(e^{j\omega}) = \Biggl \{ \begin{matrix}0 \text{ if } \omega_c \le |\omega| \\
1 \text{ if } \omega \lt |\omega| \le \pi
\end{matrix}$$
:::

**Ideal Band pass filter**
Time domain impulse response
:::warning
$$h_{BP}[n] = 2\cos(\frac{1}{2}(\omega_{c_1} + \omega _{c_2})n)\frac{sin(0.5(\omega_{c_2} - \omega_{c_1}) n)}{\pi n}$$
Band pass filter is a frequency shifted version of the low pass filter
:::

Frequency domain impulse response
:::warning
$$H_{BP}(e^{j\omega}) = \Biggl \{ \begin{matrix}0 \text{ if } |\omega| \le \omega_{c_1} \\
1 \text{ if } \omega_{c_1} \lt |\omega| \le \omega_{c_2}\\
0 \text{ if } \omega_{c_2} \lt |\omega| \le \pi
\end{matrix}$$
:::

Ideal filter implementation
- Ideal filters cannot be implemented due to the infinite nature of the sinc function
- One way is to truncate the filter using a finite length "window" with length L

$$w[n] = \Biggl \{ \begin{matrix}0 \text{ if } n \lt 0 \\
1 \text{ if } 0 \lt n \le L\\
0 \text{ if } n \gt L
\end{matrix}$$

## 4. Z-Transform
- Generalising the DTFT into the complex plane.
- Is the discrete time version of the Laplace Transform
:::warning
$$ X(z) = \sum_{n=-\infty}^{\infty}x[n]z^{-n}$$
:::
- z is a complex number in polar form: $Re^{j\omega}$
- if R = 1, then the Z-Transform is equivalent to the DTFT

Example: $x[n] = [1,2,3,4|,5] \Rightarrow X(z) = z^3 + 2z^2 + 3z + 4 + \frac{5}{z}$

### Existence of Z-transform
- The Z-transform only exists when the power series $X(z)$ converges
- The set of values for which this is true is known as the region of convergence(ROC)
:::danger
The ROC must be specified when the Z-transform is used - identical Z transforms can have different ROCs

Eg. $a^nu[n]$ and $-a^nu[n]$ have the same Z-transform $\frac{1}{1-az^{-1}}$ but the ROC is $|z| > |a|$ for the former but $|z| < |a|$ for the latter
:::

#### Properties of the ROC
1. If $x[n]$ has finite supports, then the ROC is the entire z plane except $z=0$ and/or $z = \infty$
2. If $x[n]$ has infinite left-sided supports, then $X(z)$ exists in the ROC such that $|z| \lt |p|_{max}$
3. If $x[n]$ has infinite right-sided supports, then $X(z)$ exists in the ROC such that $|z| \gt |p|_{max}$

### Properties of the Z-transform
**Superposition**
If $y[n]= ax_1[n] + bx_2[n]$, then
$$Y(z) = aX_1(z) + bX_2(z)$$

**Differential**
If $y[n] = nx[n]$, then
$$Y(z) = -z\frac{dX(z)}{dz}$$

**Scaling**
If $y[n] = a^nx[n]$, then
$$Y(z) = X(\frac{z}{a})$$

**Exponential**
If $y[n] = e^{j\omega n}x[n]$, then,
$$Y(z) = X(ze^{-j\omega})$$

**Time shift**
If $y[n] = x[n-n_d]$, then
$$Y(z) = z^{-n_d}X(z)$$

**Convolution**
If $y[n] = x_1[n] * x_2[n]$, then
$$Y(z) = X_1(z)X_2(z)$$

**Time reversal**
If $y[n] = x[-n]$, then
$$Y(z) = X(\frac{1}{z})$$

### Causality
The transfer function of a system can be expressed as
$$H(z) = \frac{Y(z)}{X(z)}$$
If the maximum degree of $X(z)$ is greater than the maximum degree of $Y(z)$ then the system is causal

### Stability
- An LTI system is stable if the ROC includes the unit circle
- A causal LTI system is stable if all poles of $H(z)$ lie within the unit cricle

### Inverse Z transform
Definition
:::warning
$$x[n] = \frac{1}{j2\pi}∮ X(z)z^{n-1} dz$$
:::

Methods to solve the inverse Z transform
1. Finite length sequence
2. Long division
3. Solve the difference equation
4. Partial Fractions

#### Initial value theorem
$$x[0] = \lim_{z\rightarrow \infty} X(z)$$

#### Final value theorem
$$x[\infty] = \lim_{z\rightarrow 1}(z-1)X(z)$$

### Deconvolution filter
Given a system $y[n] \rightarrow x[n]$, with impulse response $h[n]$, we are looking for the filter $g[n]$ such that $H(z)G(z) = 1 \Rightarrow h[n] * g[n] = \delta[n]$

### Digital filter types
Given $$H(z) = \frac{A(z)}{B(z)}$$

#### Direct Form I
- Implementing $A(z)$ first followed by $\frac{1}{B(z)}$

#### Direct Form II
- Implementing $\frac{1}{B(z)}$ first followed by $A(z)$.

## 5. Discrete Fourier Transform
Representing the continuous DTFT using a finite set of frequencies
:::warning
$$X[k] = X(e^{j\omega})|_{\omega = \frac{2\pi k}{N}} = \sum_{n = -\infty}^{\infty} x[n]e^{j\frac{2\pi k}{N}n}$$
:::

$W_N^{kn}$ is used to simplify the above equation, where $W_N = e^{-j\frac{2\pi}{N}}$

:::warning
$$X[k] = \sum_{n = -\infty}^{\infty} x[n]W_N^{kn}$$
:::

IDFT
:::warning
$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] W_N^{-kn}$$
:::

:::danger
$\frac{1}{N}$ is the normalisation constant and can vary for both DFT and IDFT. For more information see https://dsp.stackexchange.com/questions/11376/why-are-magnitudes-normalised-during-synthesis-idft-not-analysis-dft
:::

The DFT can be represnted as a system of equations $X = W\text{x}$ where $W$ is the fourier matrix, $X$ is the DFT of $\text{x}$

:::warning
$$X= \begin{bmatrix} W_N^0 & W_N^0 & ... & W_N^0 \\
W_N^0 & W_N^1 & ... & W_N^{N-1} \\
W_N^0 & W_N^2 & ... & W_N^{2(N-1)} \\
W_N^0 & W_N^3 & ... & W_N^{3(N-1)} \\
... & ... & ... & ... \\
W_N^0 & W_N^{N-1} & ... & W_N^{(N-1)(N-1)} \\
\end{bmatrix} \text{x}$$
:::

### Sampling theorem
**Nyquist sampling theorem**
A signal with finite bandwidth $B$ can be reconstructed perfectly if the sampling rate is at least twice the bandwidth of the signal.
$$f_s \ge 2B$$

If the sampling rate is lower than the Nyquist rate, then aliasing of the signal will occur.

### Circular Convolution
When a periodic signal is convolved with another periodic signal the result is also periodic. It is useful to describe a circular convolution to represent this property
:::warning
$$x[n]\circledast h[n] = \sum_{m = 0}^{N-1} x[m]h[(n-m) \pmod n]$$
:::

### Obtaining linear convolution from circular convolution
Given two finite inputs $x[n]$ and $h[n]$ of length $M$ and $N$,
1. Pad zeros on both $x[n]$ and $h[n]$ until both inputs are of length $M+N-1$
2. Perform circular convolution, which will yield the linear convolution result.

## 6. Fast Fourier Transform
The FFT is an algorithm that reduces the computational complexity of the DFT from $O(n^2)$ to $O(n \text{ log } n)$

The DFT sum can be broken down into even and odd components $$X[k] = \sum_{r=0}^{N/2-1} x[2r]W^{2rk}_{N} + \sum_{r=0}^{N/2-1} x[2r+1]W^{(2r+1)k}_{N}$$

where the first term are the even terms of the summation and the second term are the odd terms of the summation.

This can be simplified to the following:
:::warning
$$X[k] = \sum_{r=0}^{N/2-1} x[2r]W^{rk}_{N/2} + W_N^k \sum_{r=0}^{N/2-1} x[2r+1]W^{rk}_{N/2}$$

or

$$X[k] = G[k] + W_N^k H[k]$$
:::

The even and odd terms can be further decomposed similarly until only a 2 point DFT remains, which is computed directly.

The FFT can be interpreted as a sparse decomposition of $\textbf{F}_N$:
:::warning
$$\textbf{F}_N = \begin{bmatrix}\textbf{I}_{N/2} & \textbf{D}_{N/2} \\ \textbf{I}_{N/2} & -\textbf{D}_{N/2} \end{bmatrix} \begin{bmatrix}\textbf{W}_{N/2} & \textbf{0}_{N/2} \\ \textbf{0}_{N/2} & \textbf{W}_{N/2} \end{bmatrix} \begin{bmatrix} \textbf{x}_{even} \\ \textbf{x}_{odd} \end{bmatrix}$$
:::

where $\textbf{D}_{N/2} = \text{diag}(1, W_N, ... , W_N^{N/2-1} )$

## 7. Changing sampling rates
### Downsampling
Sampling a discrete signal $x[n]$ to take every $M$th sample.

For example, if a signal $h[n]$ is downsampled by a factor of 3, then it is equivalent to multiplying $h[n]$ by the sequence $[1, 0, 0, 1, 0, 0, 1, ....]$ then discarding the zeros. The above sequence is equivalent to $\frac{1}{3}\sum_{k=0}^{k=2}e^{-j\frac{2\pi kn}{3}}$, therefore the downsampled signal is $\frac{1}{3}\sum_{k=0}^{k=2}e^{-j\frac{2\pi kn}{3}}h[n]$. In the frequency domain, this translates to $\frac{1}{3}\sum_{k=0}^{k=2}H(ze^{-j\frac{2\pi kn}{3}})$

#### Frequency domain effects
$X_d(e^{j\omega})$ is scaled by a factor of $1/M$ in amplitude, stretched by a factor of $M$ in frequency, and has replicas of the spectrum every $2\pi$ with period $\frac{2\pi}{M}$

To prevent aliasing in the frequency domain the signal is passed through a low pass filter with gain 1 and cutoff of $\frac{\pi}{M}$ before downsampling. This is called decimation.

The order of filtering and downsampling does not matter, ie the following two systems are equal. This is the interchangeable property.



### Upsampling
Adding $L$ zeros in between each sample. The upsampled signal is passed through a interpolation filter with gain $L$ and cutoff $\frac{\pi}{L}$ to fill in the zeros.

#### Frequency domain effects
Scales spectrum by $L$ in amplitude, and compresses spectrum by $\frac{1}{L}$ in frequency.

#### Common interpolation filters
- Zero order hold - holds sample value for one sample interval
- Linear interpolation - connects samples with a straight line
- Truncated sinc

### Non integer sampling
Combining both up and downsampling to obtain non integer sampling rates.

### Polyphase representation (multirate signal processing)
Polyphase representation is a more efficient way of performing non integer sampling.

Decompsing an impulse response into the sum of $M$ sub-impulse responses
:::warning
$$h[n] = \sum_{k=0}^{M-1}h_k[n-k]$$
:::

$k^{th}$ polyphase element is defined as
:::warning
$$e_k[n] = h_k[nM]$$
:::
and can be obtained by downsampling $h_k[n]$. The inverse operation can be implemented by upsampling $e_k$
:::warning
$$H(z) = \sum_{k=0}^{M-1}z^{-k}E_k(z^M)$$
:::

#### Multirate filter banks
- Use filter banks to operate on a signal differently in different frequency bands
- Reduce rate after filtering to save computation
- Downsampling side is the analysis side, upsampling side is the synthesis side

## 8. Spectral analysis with DFT
### Windowed signals
Taking a block of signal samples and multiplying by a window duration $L$ for $0 \ge n \ge L-1$.
:::warning
$$v[n] = x[n]w[n]$$
:::

This implies that the DTFT of the windowed block of signals is the perodic convolution between $X(e^{j\omega})$ and $W(e^{j\omega})$

:::warning
$$V(e^{j\omega}) = \frac{1}{2\pi}\int_{-\pi}^{\pi} X(e^{j\omega})X(e^{j(\omega-\theta)})d\theta$$
:::

This limits the spectral resolution - main lobes of the DTFT of the window

And also produce spectral leaage from the side lobe of the DTFT of the window.

The two are tradeoff between the time-frequency uncertainty principle. $\sigma_t \sigma_\omega \ge \frac{1}{2}$

#### Common window functions
[Wiki](https://en.wikipedia.org/wiki/Window_function)
- Rectangular boxcar fourier
- Triangular
- Bartlett
- Hann
- Hanning
- Hamming

### Frequency analysis with DFT
We can zero pad a windowed block of signals $v[n]$ in preparation for taking an $N$-point DFT. This zero padding has no effect on the DTFT of $v[n]$.

To obtain samples at more closely spaced frequencies, we can zero pad $v[n]$ to longer block lengths.

### Time dependent Fourier Transform
Also known as short-time Fourier Trasform(STFT)
:::warning
$$X[n,\omega) = \sum_{m=-\infty}^{\infty}x[n+m]w[m]e^{-j\omega m}$$
:::

Simply slide a window and compute DTFT.

The discrete STFT is given as
:::warning
$$X[r,k] = \sum_{m=0}^{L-1}x[rR+m]w[m]e^{-j\frac{2\pi k m}{N}}$$

$L$ - window length
$R$ - jump of samples
$N$ - DFT length
:::

## 9. Application to Digital Communications
### Frequency selective channel
The channel between transmitter and deceiver is not just a delay and scaling, and can reasonably be assumed to be causal and FIR.
:::warning
$$h(\tau) = \sum_k \alpha_k e^{j\phi_k \delta(t-\tau_k)}$$
:::

The received signal can be described as
$$y[n] = \sum_{l=0}^{L-1} h[l]s[n-l] + v[n]$$

where $L$ is the number of effective ISI(intersymbol interference) channel taps and $v[n]$ is uncorrelated and Gaussian noise

### Channel estimation
The channel can be determined by sending pilot signals before the data transmission.


#### Least squares (LS)
Suppose that $\{t[n]\}_{n=0}^{N_t-1}$ is a known training sequence at both the Tx and Rx

Then, the least squares problem is
:::warning
$$\{ \hat h[0], .... \hat h[L-1] \} = \text{arg min} \sum_{n=L}^{N_t - 1} \lVert y[n] - \sum_{l=0}^{L} h[l]t[n-l] \rVert^2_2 $$

where $\lVert x \rVert _2 = \sqrt{\sum \lvert x_i \rvert^2}$ denotes the 2-norm of $x \Rightarrow \lVert x \rVert ^2_2 = \sum \lvert x_i \rvert ^2$
:::

with solution
$$\hat h = (T^H T)^{-1}T^H y$$

Least squares solution is vulnerable to the noise boost effect. (esp. when noise is not IID)

#### ML (maximum likelihood)
Consider the conditional distribution
$$f_{y|Th(y)} = \frac{1}{\text{det} (\pi C)} e^{-(y-\text{Th})^H C^{-1}(y - Th)}$$

where $C = \text{E}[\mathbb{vv}^H]$ is the noise covariance matrix

The ML channel estimator solves
$$\text{arg max} \ln f_{y|Th(y)}$$ or equivalently, $$\text{arg min} \lVert y - Th \rVert ^2_2$$

The LS is equivalent to ML when the noise is IID

### Time domain ISI suppression
- Maximum likelihood sequence detection(MLSD)
- uses markov property
- implemented effectively with Viterbi algorithm

- Linear equalizer
- Decision feedback equalizer
- takes linear equalizer + subtract tentative estimate of symbol
- Direct equalzation(without explicit channel estimation)

#### Linear equalizer
An equalizer is a filter that removes frequency selective distortion

1. DTFT method - finding $f[n]$ such that $f[n] * h[n] = \delta [n]$.
- The filter needs to be implemented in a real form.
- If the channel is FIR, the equalizer should be IIR
- Can overcome this by truncating the length of $f[n]$ with a reasonable number of taps

2. Least squares method using the channel estimate.
- minimising the square error with the estimated channel
$$J_f[n_d] = \lVert e_{n_d} -\hat Hf_{n_d} \rVert_2^2= \sum_{n=0}^{L_f + L}\lvert \delta[n-n_d] - \sum_{l=0}^{L_f}f[l]\hat h[n-l] \rvert^2$$

- The squared error can be further minimized by choosing $n_d$ such that $J_f$ is minimised.

### Frequency domain equalization
$$y[n] = \sum_{l=0}^{L} h[l]x[n-l]$$

- Transform linear convolution into circular convolution
- Decompose channel matrix using DFT
$$ y = H_c s = F^H \Lambda Fs$$

where $F$ is the normalized DFT matrix and $\Lambda = \text{diag}(Fh_1)$

To find $s$, the inverse operation can be taken.

## 10. Image signal processing
3 components:
1. A transform
2. A quantizer
3. A entropy coder

### Transforms
The transform throws away correlations. Pixels are usually highly correlated as a result of smooth surfaces

Eg. For a 2 point DFT transform,
$$X[0] = x[0] + x[1]$$ and $$X[1] = x[0] - x[1]$$

If $x[0]$ is similar to $x[1]$, then $X[1] \approx 0$. This allows for compression since we only have to transmit one number, without any significant cost in image quality.

#### Discrete Cosine Transform
- 4 different [variations](https://en.wikipedia.org/wiki/Discrete_cosine_transform#DCT-I) of DCT

DCT II
:::warning
$$C_x[k] = \sum_{n=0}^{N-1}2x[n] \cos (\frac{\pi}{2N}k(2n+1))$$

$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1}w[k] C_x[k] \cos (\frac{\pi}{2N}k(2n+1))$$

where $0 \le n,k < N$
:::

#### Relation between DCT and DFT
For a sequence $y[n] = x[n] + x[2N - n -1]$,
$$Y[k] = e^{j\frac{\pi}{2N}k}C_x[k]$$

The DCT allows for better compression as most of it's energy is located near zero, unlike the symmetric DFT. As a result, there are less significant values which have to be stored.

### Quantizer
Mapping inputs in a given range to the same output.
$$x_q = \text{round}(\frac{x}{Q})$$

More compression at the cost of larger distortion

### Entropy encoder
For a random variable $X$ with pdf $p(x)$
:::warning
$$H(X) = E(\log \frac{1}{p(X)}) = \sum_x p(x) \log \frac{1}{p(x)}$$
:::

A code $C: X \rightarrow \{0,1\}^l$ is an injective function which maps letters in $X$ to binary code words. Letting $C(x)$ and $l_C(x)$ denote the codeword and its length for an alphabet $x \in X$. The expected length $L$ of a coding scheme C is defined as
$$ L = \sum_x l_C(x)p(x)$$

If $L = H(x)$, then the coding is the most efficient possible.