Information and Coding Theory (ICT Part 1)

Introduction

What is Information Theory:

Information theory answers two fundamental questions in communication theory: What is the ultimate data compression (answer: the entropy $H$), and what is the ultimate transmission rate of communication (answer: the channel capacity $C$).

Data transmission at the physical layer:

Data Compression:

Data compression is done by the source encoder. Well-defined data sets such as the english alphabet, images, and audio need to be converted into bit strings before being modulated into signal form by the transmitter. Data compression achieves this through lossless (no information is lost) or lossy (information is lost) compression.

Transmitter:

Converts the binary data from the physical layer to a signal.

Erroneous Channel:

The transmission channel is erroneous and can result in bit flipping in the received data.

Channel Encoder:

Modifies the binary data such that the channel decoder can recover error less data; this is done by appending a redundancy code to the data. Error detection can be done using cyclic redundancy codes (CRC) and error correction can be done using stop-and-window.

Adding redundancy codes will occupy the channel transmission rate that could have been utilised by the encoded source data. We want an optimal rate (which depends on the channel) for transmitting the data with error correcting codes.

The entropy of the source gives a lower bound on how much data compression we can apply to make the channel communication optimal.

Hence, compression has two metrics:

1. Compression ratio
2. Resulting transmission speed

Source Encoding

Data Compression

The information at the source can be in any form (even non-binary), but the source encoder should convert it to binary form as binary is well suited to be converted to signal form.

$\Omega:$

$\Omega$ is the alphabet of the source. We assume it to be a finite set (infinite sets are dealt with in a different way). For example $\Omega = \{a_1,a_2, \dots , a_n\}$

Source encoding function:

$C: \Omega \rightarrow \{0,1\}^* = \{w \mid w \text{{w is a finite length binary string}}\}$

$C$ maps a single alphabet ($a_i$) to a binary string

$C^* : \Omega^* \rightarrow \{0,1\}^*$ $C^*$ maps a finite length string with $a_i \in \Omega$.

The (1) requirement for $C$ is that $C$ should be injective. If $C$ is injective then $C$ is non-singular (same for $C^*$).

The (2) requirement for $C$ is that $C(\Omega)$ is a set of codes $\subseteq \{0,1\}^*$.

Assuming a defined $\Omega$ we will interchangebly call $C$ as a code sometimes.

For example, $C^*(a_{i_1},a_{i_2}, \dots , a_{i_n}) = C(a_{i_1} \dots C(a_{i_n}))$ (concatenated)

Example 1:

$\Omega = \{1,2,3,4\}$

$C: \Omega \rightarrow \{0,1\}^*$ defined as:

$1 \rightarrow 0$

$2 \rightarrow 010$

$3 \rightarrow 01$

$4 \rightarrow 10$

Problem: this cannot be decoded correctly, as $C(3).C(1) = 010$, $C(2) = 010$, and $C(1).C(4) = 010$.

Hence, we get to the requirement (3) $C*$ should be injective.

(4) An encoder $C$ is called uniquely decodable if $C^*$ is non-singular.

Now we can fix the problem we faced earlier, but will the decoding be efficient?

Example 2:

Here, we consider the case that $C$ is uniquely decodable.

$\Omega = \{1,2,3,4\}$

$C : \Omega \rightarrow \{0,1\}^*$

$1 \rightarrow 10$

$2 \rightarrow 00$

$3 \rightarrow 11$

$4 \rightarrow 110$

If we get a $11$, we check if we have odd number of following $0$s or even. Even number of $0$s would result in the decoding $32\dots$ and odd number of $0$s would result in the decoding $42\dots$.

Problem: In the worst case, we will have to read the entire string to determine the parity of $0$ bits.

-> One possible fix could be to demarcate the string $010$ as $0,10$ and get a uniquely decodable $C$ without requiring $C^*$ to be non-singular; however, this will occupy a lot of extra bits post encoding which can grow in the size of the length of the string.

Following on this problem, we arrive at the requirment (5) for $C$.

(5) $C$ should be prefix-free. That is, no codeword should be extendable to another codeword

$C$ is prefix-free if for for no $y \in C(\Omega), \exists y' \in C(\Omega)$ such that $yy' \in C(\Omega)$.

Prefix-free $\subseteq$ Uniquely decodable $\subseteq$ Non-Singular $\subset$ Set of all codes;