Entropy and Message Transmission

We discuss another application that sheds light on meaning of entropy, the message transmission problem. In this model, a sender transmits a message to the receiver through a channel. In real world, the channel could be an optical fiber, a wireless channel, a hard disk etc. In the final application, the computer that writes and reads information from the hard disk is both the sender and the receiver.

In real world the channel is not perfect and the message transmitted is distorted by noise. It is natural to ask whether the message can be transmitted accurately under the noise, i.e., whether the receiver can recover the noisy message.

To study the problem, we need a mathematical model for both the channel and the noise. We focus on the simplest binary channel with bits of 0 and 1. The noise causes the bits to flip and is modelled by the distribution on the bit-flips. We study the simplest one that flips each bit independently with some identical probability $p < 0.5$. For a message with length $n$, the number of bit flips follows a Binomial distribution $B(n, p)$. We call such channel a binary symmetric channel.

To protect the message against noise, a naïve way is to send the each bit multiple times. For example, if the sender wants to send a bit 1, it sends $10$ copies of $1$ as $1111111111$. The receiver decides that the bit sent is 1, if the majority of the $10$ bits it receives is 1.

Could it be improved? Repeating each bit may not be the mot efficient way against the noise. In general, if the sender wants to send a message of $k$ bits, it can convert it into a new message of $n$ bits and sends the new one. The receiver considers the $n$ bits received as a whole, and try to recover the $k$-bit message the sender wants to send.

We call the method used by the sender to convert the original message the encoding function, and the one used by the receiver to recover the message the decoding function.

Definition. A $(k, n)$ encoding function $\text{Enc}: \{0, 1\}^k \rightarrow \{0, 1\}^n$ and a $(k, n)$ decoding function $\text{Dec}: \{0, 1\}^n \rightarrow \{0, 1\}^k$, where $n \ge k$.

Since the noise flips the bits randomly, it is impossible to have an encoding function and a decoding function without error (unless $p = 0$). Instead, we aim to control the probability of error within some specified threshold $\delta$. To achieve this, we add redundancy to the message and encode a $k$-bit one into an $n$-bit one. Now, $n - k$ is the amount of redundancy introduced. We would like to make $n - k$ as small as possible. On the other hand, the value of $n-k$ should positively related to $p$. The larger $p$ is, the noisier the channel is and the larger $n - k$ should be.

For fixed $\delta$ and $p$, the Shannon's Theorem says that the smallest possible value of $n - k$ we can achieve is roughly $n\mathbf{H}(p)$. Intuitively, $\mathbf{H}(p)$ is the amount of randomness the noise exerts on each bit. Therefore $1 - \mathbf{H}(p)$ is the maximum amount of information we can transmit by one bit.

Before we proceed, we prove the following lemma.

Lemma 1
For $q \in \mathbb{R}, q \le 1 / 2$ and $n \in \mathbb{N}$, it hold that

Proof.

The first inequality follows from that $\binom{n}{i}$ is increasing for $i \le n / 2$ and that the summation is over at most $(n + 1) /2$ terms. The last one follows from that $\mathbf{H}(x)$ is increasing for $x \le 1 / 2$ and that ${ \lfloor q n \rfloor } / { n } \le { q n } / { n } = q < 1/2$.

$\blacksquare$

Shannon's Theorem
Given a binary symmetric channel with flip probability $p < 1 / 2$ and for any any $\epsilon, \delta > 0$, when $n$ is large enough,

1. if $k \le n (1 - \mathbf{H}(p) - \epsilon)$, there exist $(k, n)$ encoding and decoding functions such that the receiver fails to obtain the correct message with probability at most $2\delta$.
2. $\nexists (k, n)$ encoding and decoding functions with $k \ge n (1 - \mathbf{H}(p) + \epsilon)$ such that the decoding is correctly is at most $\delta$ for a $k$-bit input message chosen uniformly at random.

Proof of 1.

Intuition. When an $n$-bit message $s$ is transmitted through the channel, the number of flipped bits is roughly $np$. As $p < {1} / {2}$, we can find a $\lambda > 0$ such that $p + \lambda < {1} / {2}$. Let $R$ be the received $n$-bit message and define $d(s, R)$ the number of different bits between $s$ and $R$, i.e., the Hamming distance between $s$ and $R$. Given $s$ and $p$, let $\mathfrak{D}(s, p)$ be the distribution of $R$ on $\{0, 1\}^n$.

By Hoeffding's inequality, it holds that

Define the $(p + \lambda)n$ ball centered $s$ as

The the Hoeffding's inequality implies that for large enough $n$, we have

That is, with probability at most $\delta$, the received message fall outside the ball $B_{s, (p + \lambda)n}$. This motivates to decode each message in $B_{s, (p + \lambda)n}$ as the original message the sender wants to send.

Further, by Lemma 1, the size of $B_{s, (p + \lambda) n}$ is bounded by

Therefore, the maximum number of non-overlapped balls we can pack into the message space $\{0, 1\}^n$ is

When $n$ is large enough, this is at least $2^{ n (1 - \mathbf{H} ( p ) - \epsilon) }$.

Remark: Hoeffding's inequality is an overkill. Chebyshev's inequality suffices for this proof.

Designing Encoding and Decoding Functions.

This motivates one to design of encoding and decoding function as follows: find a set of messages $s_1, s_2, ..., s_{2^k} \in \{0, 1\}^n$, such that

are disjoint balls, and assign the messages in $\{0, 1\}^k$ to the ones in $\{ s_i \}'s$ one by one. If the sending want to send $i$, it sends $s_i$. On receiving a message $r$, the receiver determines which ball $r$ belongs to. The probability of decoding error is at most $\delta$.

Question to ponder: can we find such a set efficiently, such that

are disjoint?

Finding the Codewords.

It is left to find a set of satisfactory $s_1, s_2, ..., s_{2^k} \in \{0, 1\}^n$. The method we show here does not find a set of non-overlapped balls. Instead it aims to find a set such that

if $s_i$ is transmitted, then the probability received message $r$ falls into the another ball, i.e., $r \in B_{s_{j} , (p + \lambda)n}$ ($j \neq i$), is less than $\delta$.

The property implies that the overlap between $B_{s_{i} , (p + \lambda)n}$ and $\cup_{j \neq i} B_{s_{j} , (p + \lambda)n}$ is less than $\delta$ (measured by probability). To formalize the statement, define the random variable $S$ to be the message sent and $R$ to be the one received. Given that $S = s_i$ is sent, the conditional probability of receiving $R = r$ is

To goal is to prove that it holds for all $i$,

Then , by union bound, it holds that

That is, $s_i$ is transmitted and decoded correctly with probability at least $1 - 2 \delta$.

In what follows, we will prove the following claim:

Claim 1. If we generate $2^{k + 1}$ codewords uniformly at random from $\{0, 1\}^n$, then in expectation

Claim 1 implies that there exits a set of codewords $s_1, s_2, ..., s_{2^{k + 1} }$ with

If we send each $s_i$ with probability $1 / 2^k$, then the expected error probability is already $\delta$. But we can have a stronger result: we can find a set of $2^k$ codewords, such that for each $i$,

W.L.O.G., suppose that $s_1, s_2, ..., s_{2^k}$ are the ones with the smallest $\Pr_{R \sim \mathfrak{D}(s_i, p) } [R \in \cup_{j \neq i} B_{s_{j} , (p + \lambda)n } \mid S = s_i]$ 's, it must be that

Proof of Claim 1. By Lemma 1, for a fixed $r$, the number of strings $s \in \{0, 1\}^n$ such that $d(s, r) < (p + \lambda) n$ is bounded by

If a message $s$ is picked uniformly at random from $\{0, 1\}^n$, the probability such that

By union bound,

As $k \le n(1 - \mathbf{H}(p) - \epsilon)$, when $n$ is sufficient large, it follows

Therefore,

and

$\blacksquare$

Proof of 2.

The difficulty here is to prove that the claim holds for arbitrary $(k, n)$ encoding and decoding functions. The proof relies on an important property:

the decoding function $\text{Dec}$ is a function on $\{0, 1\}^n$

For any $r \in \{0, 1\}^n$, there is a unique output $\text{Dec}(r) \in \{0, 1\}^k$. The decoding function needs to decide the unique message $\{0, 1\}^n$ the sender want to send.

Now, define

The $S_i$'s are non-overlapped and we have,

If $s_i$ is sent, then by Hoeffding inequality, with probability at least $1 - \exp(- 2\lambda^2 n)$, the received message $R$ is likely to fall into a ring centered at $s_i$:

Finally, if the messages $s_1, s_2, ..., s_{2^k}$ are sent uniformly at random, i.e., $i \sim \mathbf{U}[1, 2^k]$, then

Observed that $S_i \subset \text{ring} (s_i) \cup (S_i \cap \text{ring} (s_i) )$, we get

Note that for $r \in S_i \cap \text{ring} (s_i)$, as $p < 1 / 2$, it holds that

We obtain

Conditioning on that $k \ge n (1 - \mathbf{H}(p) + \delta)$,

By choosing sufficient small $\lambda$ and large enough $n$, $\Pr[ R \text{ is decoded correctly}]$ can be arbitrary small.

$\blacksquare$

Reference

[1] M. Mitzenmacher and E. Upfal, Probability and computing: an introduction to randomized algorithms and probabilistic analysis. New York: Cambridge University Press, 2005.