1.1.1: Digital Speech

• Bandwidth: 50-3400 Hz
• Sampling: 8 KHz
• Representation: 8 bit Log PCM (13 bit linear PCM)
• Dynamic range: 42 dB
• Characterization:
  • Spectral components
  • Component description (phonemes)

Digital speech is often presented as a spectrum (frequency/Amplitude) or spectrogram (frequency/time/amplitude)

1.1.2: Digital images/video

• Many proprietary formats, .flv, .avi, .mp4 etc. *Rates go from ~20kbps to 27 Mbps

Images has significant correlation between spectral components. The colors doesnt really matter, and conversion between different color spaces can be done fairly easy. There is significant correlation between neighbouring pixels. This means that we really dont have to treat every pixel for itself, but can instead look on a larger area of pixels. Natural images often exhibit large semi-uniform areas. Images are also non-stationary.

We have different tools for analysis and coding/compression of digital images.

• Analysis:
  • Fourier transform in two dimensions
  • Subband decomposition
• Coding/compression:
  • Block transforms (DCT)
  • Filter banks/Subband decomposition
    • Wavelets
    • General filters
  • Prediction/estimation
    • Motion compensation
  • Quantization
  • Entropy coding

1.2.1: Signal decomposition

Removes redundancy. Correlation between consecutive samples -- Can be removed reversible (without loss of information). This step can also be known as the sampling step usually involfing an A/D convertion.

When dealing with audiovisual content there are two ways we can reduce the size of the files. Alot of the signal contains redundancy, for example big areas of uniformity in an image. This can be removed reversible, without loss of information. Some of the content also contains irrelevancy, for example frequencies above the human hearing range in audio content. This is an irreversible operation.

1.2.2: Signal quantisation

Removes irrelevancy. Non-perceivable information -- Can be removed irreversibly (with loss of information). The quantisation can be described by:

\begin{equation} Q(s)=D(E(s)) \end{equation}

1.2.3: Signal coding

Transmit a perceptually relevant and statistically non redundant signal over the channel to the receiver. Makes the compression efficient.

The source coder output should be:

• Efficient (compression)
• Minimal distortion (fidelity)
• Robust (reconstruction)

2.2.1: Lossless formats

2.2.2: Lossy formats

2.3.1: MPEG

MPEG is a video and audio codec. For signal decomposition, all standards use DCT + quantization. It uses motion compensation as well as lossless entropy coding for motion vectors and quantized DCT samples. The encoder can trade-off between quality and bitrate. The default quantization matrix can be multiplied by a quantization parameter in order to obtain different quantization steps. Small steps gives high quality and bitrate, while large quantization steps git low quality and rate. The resulting bitrate cannot be known accurately from the quantization parameter. This is because the bitrate is dependant on spatial and temporal frame activity and on the GOP structure. In practice, constant bitrate and constant quality cannot be obtained at the same time

2.3.2: What encoder do we choose?

Important question in deciding which codec to use can be:

Technical: Compression ratios Quality improvements 2D, 3D, multiview? Complexity (Power constraints, delay)

Business: Application or service driven Specialised codec? All-rounder? Standardised? Proprietary? Open source?

We once again return to the pyramid earlier, where recieved signal quality cannot be obtained with decreasing time delays, complexity and compression ratio.

Comparison between video standards

2.3.3: Video encoding

2.3.3.1: Frame types

For video compression we use I, P and B frames to compress the raw video.

Intra-frames (I-frames)

are compressed frames from the original video frames and the least compressible. Holds information of a complete image.

Predicted-frames (P-frames)

are predicted frames between two I/P-frames and more compressible than I‑frames. Only holds the changes in the image from the previous frame.

Bidirectionnally predicted frames (B-frames)

can be seen as an interpolation between I and P-frames and get the highest amount of data compression. Holds information about both the preceding and following frames.

A Group of Pictures (GOP) is the sequence of different frames between two I-frames. Intra-coding is coding within a frame. For example for an I-frame we use an intra-coded frame. Inter-coding is between multiple frames, where we can use the original I-frame, and estimate what has moved in the next frame. Often in video two frames are very alike, and it would be wasteful to intra-code every frame.

2.4.1: Objective measures

Image quality can be assesed objectively by SNR or PSNR

$\sigma_e ^2 = \frac{1}{MN}\sum_{M=1}^M\sum_{n=1}^N|u(m,n) - û(m,n)|^2$

$PSNR_{dB} = 10Log_{10}\frac{255^2}{\sigma_e ^2}$

Objective measures has some weaknesses. For example if we have one corrupted line, the PSNR will still be high, while most people would not see this as a good image. A tilt in the image will result in a low PSNR, while it would not be noticable for people.

2.4.2: Subjective measures

Determined based on the judgement of a large number of viewers and after elaborate tests comparing the reference and modified content. Results are summarized using mean opinion scores (MOS).

Some weaknesses of subjective measurements is that the viewing conditions may not be optimal, so that the focus may be on the outer things rather than the content to be tested

4.1.1: Data Compression Theorem

Let $X$ be a random variable over some alphabet $\mathcal A$. Let $\epsilon > 0$ be some arbitrary small number. It then exist some sufficiently large $n$ and a code that maps $x^n$ into binary strings such that the mapping is one-to-one and

$$ \begin{align} E \left[ \frac{1}{n} l(X^n) \right] \leq H(X) + \epsilon \end{align} $$

Let's use a concrete example to show the power of this theorem. Let $X$ be a binary source (zeros and ones) with

$$ \begin{align} P(X=0) = 3/4 \\ P(X=1) = 1/4 \end{align} $$

We compute the entropy of $X$:

p = 3/4
H = -p*np.log2(p) - (1-p)*np.log2(1-p)
print("The entropy is", H, "vs the code rate", L/2)

The theorem now tells us that we can find an $n$ and a code so that the average length of the coded sequences $x^n$ is arbitrarily close to the entropy.

The theorem doesn't tell us how to find these codes, or even how large $n$ should be. In this sense it is an non-constructive theorem. In practice however, getting close enough to $H(X)$ for all practical purposes is well within our reach.

4.1.2: Further properties of the entropy

The Joint Entropy

Given two random variables $X$ and $Y$ we can define their joint entropy as $$ \begin{align} H(X,Y) & = -\sum_m \sum_n \log_2 P(X=x_m,Y=y_n) \log_2 P(X=x_n, Y=y_m) \\ & = -\sum_m \sum_n P(x_m,y_n) \log_2 P(x_m,y_n) \\ & = E_{X,Y}[-\log_2 P(x,y)] \end{align} $$

The Conditional Entropy

Given two random variables $X$ and $Y$ with joint distribution $P(X,Y)$ we can define the conditional entropy $H(Y|X)$ as $$ \begin{align} H(Y|X) & = -\sum_m \sum_n \log_2 P(X=x_m,Y=y_n) \log_2 P(Y=y_m|X=x_n) \\ & = -\sum_m \sum_n P(x_m,y_n) \log_2 P(y_n|x_m) \\ & = E_{X,Y}[-\log_2 P(y|x)] \end{align} $$

The Chain rule for entropy

From probability theory we know that the joint distribution $P(X,Y)$ can be written \begin{equation} P(X,Y) = P(Y|X)P(X) \end{equation}

We can now easily show that

$$ \begin{align} H(X,Y) & = E_{X,Y}[-\log_2 P(x,y)] \\ & = E_{X,Y}[-\log_2 P(y|x)P(x)] \\ & = E_{X,Y}[-\log_2 P(y|x) - \log_2 P(x)] \\ & = E_{X,Y}[-\log_2 P(y|x)] + E_{X,Y}[-\log_2 P(x)] \\ & = H(Y|X) + H(X) \\ & = H(X|Y) + H(Y) \end{align} $$

4.1.3: Huffman codes

We will now present one method to find a set of codes for a set of sequences $x^n$ and their probabilities $P(X^n=x^n)$. The method is refered to as Huffman coding and has the nice property that it is optimal in the sense of yielding the lowest average length for any code given any $n$ and $P$. It should be noted though, that increasing $n$ would allow us to find a Huffman code with even lower average length.

The algorithm goes as follows:

1. Find the two symbols with lowest probability (here $X=$4 and 5)

2. Assign a 0 and 1 one to each of the symbols

3. Sum their probabilities and insert a new symbol (4,5) into the sorted table

4. Repeat the procedure with symbols $X=$2 and 3, getting a new symbol (2,3)

5. At the third step we assign 0 to (4,5) and 1 to $X=1$, and get a new symbol ((4,5),1)
6. At the final step we assign 0 to ((4,5),1) and 1 to (2,3)

Pondering

• Is this a prefix code?
  • Yes, symbals can be uniqly identified
• What is the average length of a coded symbol for this code
  • 2.3
• What is the entropy of the source $X$?
  • 2.29
• Create a Huffman code for the alphabet $\{1,2,3,4\}$ with probabilities $P=\{1/2, 1/4, 1/8, 1/8\}$. Compute entropy and average code length.

4.1.4: Bounds on code length

It can be shown (see chapter five in Elements of Information Theory by Cover and Thomas) if you want some proper proofs), that the optimal code lengths for an information source $X$ is

\begin{equation} l_i^{\star} = -\log_2 P(x_i) \end{equation}

if we just could use code words of non-integer length that is. Instead we have to use code words with length

\begin{equation} l_i = \lceil -\log_2 P(x_i) \rceil \end{equation}

(Here $\lceil x \rceil$ rounds x up to the closest integer, eg. $\lceil 2.1 \rceil = 3$).

We can show the following bound on code lengths, $$ \begin{align} & -\log_2 P(x_i) & \leq & l_i & \leq & -\log_2 P(x_i) + 1 \\ \Rightarrow & -P(x_i)\log_2 P(x_i) & \leq & P(x_i)l_i & \leq & -P(x_i)\log_2 P(x_i) + P(x_i) \\ \Rightarrow & \sum_i -P(x_i)\log_2 P(x_i) & \leq & \sum_i P(x_i)l_i & \leq & \sum_i -P(x_i)\log_2 P(x_i) + P(x_i) \\ \Rightarrow & H(X) & \leq & L & \leq & H(X) + 1 \end{align} $$

4.1.5 The Kullback-Leibler divergence (relative entropy)

We will now introduce a very important quantity, both in the field of Information Theory and Statistics. The Kullback-Leibler (or KL) divergence is a measure of how much a distribution differs from a reference distribution, and is defined as

$$ \begin{align} D(P\|Q) & = \sum_{x\in \cal X} P(x)\log_2 \frac{P(x)}{Q(x)} \\ & = E_P \left[\log_2 \frac{P(x)}{Q(x)}\right] \end{align} $$

Some important properties of the KL divergence are

1. We always have that $D(P\|Q) \geq 0$
2. $D(P\|Q) = 0$ iff $P=Q$.
3. It is asymmetric, that is, $D(P\|Q) \neq D(Q\|P)$ in general
4. If $H(P,Q)$ is the cross entropy of $P$ and $Q$, and $H(P)$ is the entropy of $P$ (which is the same as the cross-entropy of P with itself) then $D(P\|Q)=H(P, Q)-H(P)$.

We will quickly prove the first two properties. The third property can easily be proven by finding a suitable example. Before proving (1,2) we need the following inequality

\begin{equation} \log x \leq x - 1~\forall x \end{equation}

Proof

A quick plot is given below in stead of a proper proof.

We can now prove properties 1 and 2 (I will use the natural logarithm in the proof for simplicity. This does not affect the result):

$$ \begin{align} D_e(P\|Q) & = \sum_{x\in\cal X} P(x)\log \frac{P(x)}{Q(x)} \\ & = \sum_{x\in\cal X} -P(x)\log \frac{Q(x)}{P(x)} \\ & \geq \sum_{x\in\cal X} -P(x)\left( \frac{Q(x)}{P(x)}-1\right)\\ & = \sum_{x\in\cal X} \left( P(x)-Q(x)\right)\\ & = 0 \end{align} $$

The if part of property 2 is trivially true since \begin{equation} \log\frac{P(x)}{Q(x)} = \log 1 = 0 \end{equation} if $P(x) = Q(x)$ for all $x$. The only if part can be seen from the inequality, which is only tight ($\log x = x - 1$) for $x=1$.

4.1.6: The Mutual information

The last informastion theoretic quantity we will discuss is the mutual information. It is a quantity used with joint distributions $P(X,Y)$ and is defined as

$$ \begin{align} I(X;Y) & = \sum_{i,j} P(x_i,y_j) \log_2 \frac{P(x_i,y_j)}{P(x_i)P(y_j)} \\ & = D(P(X,Y)\|P(X)P(Y)) \\ & = E\left[\log_2 \frac{P(x_i,y_j)}{P(x_i)P(y_j)}\right] \end{align} $$

Let us list some properties of the mutual information before further discussion

$$ \begin{align} I(X;Y) & = H(X) - H(X|Y) \\ I(X;Y) & = H(Y) - H(Y|X) \\ I(X;Y) & = H(X) + H(Y) - H(X,Y) \\ I(X;Y) & = I(Y;X) \\ I(X;X) & = H(X) \\ \end{align} $$

4.1.7: The Data Processing Inequality

We now give an application of the mutual information. The Data Processing inequality say that no amount of data processing can improve the inference based on the data.

Before we state the inequality, we need to define a Markov chain. Let $X_1$, $X_2$, ... be a series of random variable that are observed in that order. Let

\begin{equation} P(x_k|x_{k-1},x_{k-2}\ldots) \end{equation}

be the probability of $X_k = x_k$ given all the previous observations. If we can write

\begin{equation} P(x_k|x_{k-1},x_{k-2}\ldots) = P(x_k|x_{k-1}) \end{equation}

for all $k$, then $X_1$, $X_2$, ... is a Markov chain.

Now consider the Markov chain $X \rightarrow Y \rightarrow Z$, where $X$ is the original or "raw" data that is unobserved, $Y$ is the observed version of $X$ and $Z$ is some processed version of $Y$, $Z = g(Y)$.

Examples:

• $X$ is a communication signal (zeros and ones) and $Y$ is $X$ plus some additiver noise
• $X$ is a label from the set {Cat, Dog, Horse, Capybara}, and $Y$ is a blurry image of the animal

The Data Processing Inequality now states: If we have a Markov chain $X\rightarrow Y\rightarrow Z$, then $I(X;Y) \geq I(X;Z)$.

Again - this means that no amount of processing of the data $Y$ can increase the information gained about $X$.

4.1.8: The Entropy rate

The concept of entropy is not limited to iid. random variables, but can also be defined for stochastic processes. Let $X_1,X_2,X_3,\ldots$ be a stochastic process. Since such a process can be arbitrarily long, we define the entropy rate as

\begin{equation} H({\cal X}) = \lim_{n\rightarrow\infty} \frac{1}{n}H(X_1,X_2,\ldots,X_n) \end{equation}

if the limit exists. Examples:

If iid. random variables $X_i$ we have

$$ \begin{align} H({\cal X}) & = \lim_{n\rightarrow\infty} \frac{1}{n} H(X_1,X_2,\ldots,X_n) \\ &= \lim_{n\rightarrow\infty} \frac{1}{n} \sum_{i=1}^n H(X_i) \\ & = H(X_1) \end{align} $$

We are now read to consdider coding of arbitrarily long sequences.

4.1.9 Differential Entropy

Let $X$ by a continuous random variable (r.v.) with probability density function (pdf) $f_X(x)$. Then the differential entropy is defined as: \begin{equation} h(X) = -\int_\Omega f_X(x)\log f_X(x) dx \end{equation}

The definition of the differential entropy can be motivated from the discrete entropy as follows:

Let

$$ \begin{equation} p_i = \int_{i\Delta}^{(i+1)\Delta} f_X(x) dx = f_X(x_i)\Delta \end{equation} $$ define a discrete rv. $X^\Delta$, and write the discrete entropy as

$$ \begin{align} H(X^\Delta) & = -\sum_i p_i \log p_i \\ & = -\sum_i f_X(x_i)\Delta\log (f_X(x_i)\Delta) \\ & = -\sum_i \Delta f_X(x_i)\log f_X(x_i) -\sum_i f_X(x_i)\Delta\log\Delta \\ & = -\sum_i \Delta f_X(x_i)\log f_X(x_i) - \log\Delta \\ & \approx -\int_\Omega f_X(x)\log f_X(x) dx -\log \Delta \end{align} $$

We see that as $\Delta\rightarrow 0 \Rightarrow -\log\Delta\rightarrow\infty$. It makes sense in a way, as the information corresponding to an specific outcome $X=x$ from a continuous rv. has zero probability, and hence has infinite information.

This is the reason we refer to $h(X)$ as the differential information - it is the difference in information from different continuous rvs.

We can define the joint and conditional entropies in the same way as for discrete rvs.

$$ \begin{align} h(X,Y) & = -\int_{\Omega_X\times\Omega_Y} f_{X,Y}(x,y)\log f_{X,Y}(x,y) dxdy \\ & = E_{X,Y}\left[ -\log f_{X,Y}(X,Y) \right] \\ h(X|Y) & = -\int_{\Omega_X\times\Omega_Y} f_{X,Y}(x,y)\log f_{X|Y}(x|y) dxdy \\ & = E_{X|Y}\left[ -\log f_{X|Y}(X|Y) \right] \\ \end{align} $$

We can also define the continuous versions of the Kullback-Leibler divergence and the Mutual Information:

$$ \begin{align} D(X\|Y) &= E_{X,Y}\left[ \log\frac{f_Y(Y)}{f_X(X)} \right] \\ I(X;Y) &= E_{X,Y}\left[ \log\frac{f_{X,Y}(X,Y)}{f_X(X)f_Y(Y)} \right] \end{align} $$

Because of the linearity of the integral, all the relationships between entropy, joint entropy, conditional entrop$y$ and mutual information hold as well.

Example 1:

The differential entropy of a zero-mean normal distribution $$ \begin{equation} f_X(x) = (2\pi\sigma^2)^{-\frac{1}{2}} e^{-\frac{1}{2}\frac{x^2}{\sigma^2}} \end{equation} $$ Using the definition of the differential entropy we have $$ \begin{align} h(X) &= -\int_{-\infty}^{\infty} f_X(x)\log f_X(x) dx \\ &= -\int_{-\infty}^{\infty} f_X(x) \log \left( (2\pi\sigma^2)^{-\frac{1}{2}} e^{-\frac{1}{2}\frac{x^2}{\sigma^2}} \right)dx \\ &= -\int_{-\infty}^{\infty} f_X(x) \left( -\frac{1}{2} \log (2\pi\sigma^2) -\frac{1}{2}\frac{x^2}{\sigma^2} \right)\\ &= \frac{1}{2} \log (2\pi\sigma^2) -\int_{-\infty}^{\infty} f_X(x) \left( -\frac{1}{2}\frac{x^2}{\sigma^2} \right) dx \\ & = \frac{1}{2} \log (2\pi\sigma^2) + \frac{1}{2} \\ & = \frac{1}{2} \log (2\pi\sigma^2) + \frac{1}{2}\log e \\ & = \frac{1}{2} \log (2e\pi\sigma^2) \end{align} $$

Example 2:

We can discuss this independently of the underlying distribution. Let $X$ ba an rv. with mean $E_X[X] = \mu$ and pdf. $f_X(X)$, and let $Y = X - \mu$ be an rv. with $E_Y[Y] = 0$ and pdf. $f_Y(Y) = f_X(Y+\mu)$. Then

$$ \begin{align} h(Y) & = -\int_{-\infty}^\infty f_Y(y)\log f_Y(y) dy \\ & = -\int_{-\infty}^\infty f_X(y+\mu)\log f_X(y+\mu) dy \\ & = -\int_{-\infty}^\infty f_X(x)\log f_X(x) dx,~x = y + \mu \\ & = h(X) \end{align} $$

In other words, the entropies of rvs. $X$ and $Y = X - \mu$ is always the same.

4.1.10: Run-length Coding

4.1.11: Arithmetic coding

4.1.12: Lempel-Ziv (LZW) coding

Lempel-Ziv (LZ) codes are widely used for universallossless compression. Due to flexible adaptation mechanisms, these are in principle applicable for compression of any kind of digital data.

Properties of different entropy-coding methods:

4.2.1: Rate-distortion pair

Definition: A rate distortion pair (R,D) is achievable if there exists a sequence of $(2^{nR},n)$-rate distortion codes $(f_n,g_n)$ so that

$$ \begin{equation} \lim_{n\rightarrow\infty} E_X \left[ d(X^n,g_n(f_n(X^n))) \right] \leq D \end{equation} $$

4.2.1: Rate-distortion region

Definition: The rate distortion region is the closure of of the set of achievable rate distortion pairs $(R,D)$.

4.2.3: Rate distortion function

Definition: The rate distortion function is the infimum over all $R$ contained in the rate distortion region for a given distortion $D$.

This definition of the rate distortion function, though intuitive, is highly abstract and not constructive. We will now give a more concrete definition of the rate distortion function $R(D)$, but first we need to discuss the joint distribution of $X$ and $\hat X$, $f_{X,\hat X}(X,\hat X)$. Let us look at a simple uniform quantizer as shown below:

We see that the mapping from $X$ to $\hat X = Q(X)$ is a simple deterministic mapping. In that sense $f_{\hat X|X}(\hat X|X)$ may not seem very interesting as it is one for $\hat X = Q(X)$ and zero otherwise. But just by that property it does actually specify the quantizer completely! In that sense, specifying different $f_{\hat X|X}(\hat X|X)$ can in principle determine underlying quantizers.

Definition: The rate distortion function $R(D)$ for an iid. discrete source $X$ and a bounded distortion measure $d(x,\hat x)$ is defined as $$ \begin{equation} R(D) = \min_{P(\hat X| X):\sum_{x,\hat x} P(x)P(\hat x|x) d(x,\hat x)\leq D} I(X;\hat X) \end{equation} $$

Definition: The rate distortion function $R(D)$ extended to continuous alphabets and a squared error distortion measure is defined as

$$ \begin{equation} R(D) = \min_{f_{\hat X|X}(\hat X| X): E \left[ \|X - \hat X \| \right]\leq D} I(X;\hat X) \end{equation} $$

The rate distortion theorem states that $R(D)$ as defined above in fact is the rate distortion function as defined using the rate distortion region. The proof is outside of the scope of this course however.

4.2.4: Examples

def H(p):
    return -p*np.log2(p) - (1-p)*np.log2(1-p)

def R(D,p):
    R = H(p) - H(D)
    R[ p < D] = 0
    return R

p = 1/2
D = np.linspace(1e-12,1-1e-12,100)

fig, ax = plt.subplots()
ax.plot(D,R(D,p),label="p={}".format(p))
ax.grid()
ax.set_xlabel("Distortion D")
ax.set_ylabel("Rate R")
ax.legend()

sigmasq = 1.0
D = np.linspace(1e-6, 2*sigmasq,10000)
R = np.maximum(0.5*np.log(sigmasq/D),0)

fig, ax = plt.subplots()
ax.plot(D,R)
ax.grid()
ax.set_xlabel("Distortion D")
ax.set_ylabel("Rate R")

5.1.1: Training

5.1.2: Deep Naural Networks

5.1.3: Convolutional Neural Networks

5.1.4: Recurrent neural networks

5.3.1: Tranformer networks