Chapter 1: Introduction to Information Theory

The first problem we tackle is how to communicate perfectly over imperfect communication channels.

The running example is this. We have some message which is a sequence of bits. We want to write this data to a noisy hard disk that transmits each bit correctly with probability $1-f$ and correctly with probability $f$. This is called the binary symmetric channel (symmetric as the probablity of flipping from $0$ to $1$ is the same as $1$ to $0$).

Suppose $f=0.1$. This is clearly unacceptable. We want a useful disk drive to flip no bits in say 10 years writing $1GB$ a day, which means we want error probability around $10^{-15}$ or smaller. We solve this problem by introducing communication systems to detect and correct the errors.

The flow is such:

• Start with message $s$
• $s$ gets encoded into $t$, which is some intermediate representation we design
• Some noise $n$ gets added to $t$ which represents noise from the imperfect hard disk
• This results in $r=t+n$ which is the received vector
  • The addition is in modulo 2 arithmetic, i.e. $0+1=1$ and $1+1=0$
• Finally we decode using some algorithm to get $\hat{s}$ from $r$

The $R_3$ Repetition Code

A simple communication system is to repeat each bit $3$ times. After noise is added, we decode each bit in the received vector by taking the majority vote. The idea is that when $f$ is small, the probability of multiple bits failing independently becomes small. So the majority vote will correct some errors.

Theorem. The majority vote decoding is optimal (i.e. has the lowest probability of error).

Proof. Since each bit is independent, we just need to consider the optimal decision for one bit. Suppose we received $3$ bits $r_1,r_2,r_3$. The objective is to recover the original bit $s$, which could have been $0$ or $1$. Thus, we want: $$\begin{array}{rl}\hat{s}& =\underset{s\in \{0,1\}}{\mathrm{argmax}}P(S=s|r_1,r_2,r_3)\\ & =\underset{s}{\mathrm{argmax}}\frac{P(r_1,r_2,r_3|s)P(s)}{P(r_1,r_2,r_3)}\\ & =\underset{s}{\mathrm{argmax}}P(r_1,r_2,r_3|s)\end{array}$$ Note that:

• In the first line, $S$ is the random variable representing the unknown true bit
• $s$ is a candidate value that we are choosing (some notation overloading as $s$ is also used to represent the true bit above)
• $P(S=s)$ is treated as a constant, and $P(r_1,r_2,r_3)$ does not affect choice of $s$

Now, if we denote $d$ as the number of bit flips between $r_1,r_2,r_3$ and $s$, we have: $$\begin{array}{r}P(r_1,r_2,r_3|s)=(1-f{)}^{3-d}{f}^d\end{array}$$ Notice that we are computing the probability for this specific received sequence $r_1,r_2,r_3$, hence we do not need to multiply by the number of combinations.

With this formulation, we see that $P(r_1,r_2,r_3|s)$ is maximized when the choice of $s$ minimizes the number of bit flips (if $f<0.5$). This is because a scenario with few bit flips is more likely than a scenario with many bit flips. Hence, the majority vote is optimal as it minimizes the number of bit flips.

Exercise 1.2. Show that the error probability is reduced by the user of $R_3$ by computing the error probability of this code for a binary symmetric channel with noise level $f$.

Solution. The naive error probability is: $$P(r\ne s)=f$$

With $R_3$, the error probability is: $$\begin{array}{rl}P(r_{majority}\ne s)& =P(\text{2 or 3 bit flips})\\ & =f^2(1-f)\times 3+f^3\\ & =3f^2-2f^3\end{array}$$

Now we want to show that when $f<0.5$, $R_3$ has a better error probability: $$\begin{array}{rl}f& <0.5\\ 3f& <1.5\\ 3f-2f^2& <1\\ 3f^2-2f^3& <f\end{array}$$

Hence we showed that $R_3$ has a better error probability.

Even though $R_3$ has a better error probability, the problem is that our rate of information transfer has fallen by a factor of $3$. To improve our error probability, we can continue to increase repetition at the cost of decreased rate.

Exercise 1.3. Find the probability of error of $R_N$, the repetition code with $N$ repetitions for odd $N$

$$\begin{array}{rl}P(\text{Error of }{R}_N)& =P(\text{At least }\frac{N+1}{2}\text{ bits flipped})\\ & =\sum _{n=(N+1)/2}^N\left(\genfrac{}{}{0ex}{}{N}{n}\right)f^n(1-f{)}^{N-n}\end{array}$$

Assuming $f=0.1$, which terms in this sum is biggest? How much bigger than the second largest term?

The largest term is $$\left(\genfrac{}{}{0ex}{}{N}{(N+1)/2}\right)f^{(N+1)/2}(1-f{)}^{(N-1)/2}$$

The second largest term is around $0.1$ times smaller, so the largest term dominates.

Use stirling's approximation to approximate the largest term and find the probability of error.

Using stirling's approximation: $$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{N}{(N+1)/2}\right)& \approx 2^{N\cdot H_2((N+1)/2/N)}\\ & \approx 2^{N\cdot H_2(1/2)}\\ & =2^N\end{array}$$

Hence we have probability of error as: $$\begin{array}{rl}{P}_{error}& \approx 2^N\cdot f^{N/2}\cdot (1-f{)}^{N/2}\\ & =(4f(1-f){)}^{N/2}\end{array}$$

To get error probability less than $10^{-15}$, we write out the inequality and manipulate to find the lower bound for $N$.

Hamming (7, 4) code

Thus far, we have been trying to encode each bit independently. What if we encode blocks of bits together? Can we get more efficient codes?

A block code converts a sequence of source bits $s$, of length $K$, into a transmitted sequence $t$ of length $N$ bits.

• We add some redundancy by making $N>K$. The extra $N-K$ bits (called parity-check bits) are used to store some redundant information of the original $K$ bits.
• This is usually implemented as some linear function of the original $K$ bits
• In the (7,4) Hamming Code, we transmit $N=7$ bits for every $K=4$ source bits

The encoding can be shown with an example. Suppose $s=0011$.

• The first 4 bits of transmitted $t=0011$, i.e. just copy the source sequence
  • $t_1,t_2,t_3,t_4=s_1,s_2,s_3,s_4$
• The next 3 bits are parity-check bits
  • $t_5$ is set such that $s_1+s_2+s_3+t_5$ is even
  • $t_6$ is set such that $s_2+s_3+s_4+t_6$ is even
  • $t_7$ is set such that $s_1+s_3+s_4+t_7$ is even
• For the example of $s=0011$:
  • $t=0011100$

We can see that the Hamming code is a linear code, since the encoding can be written compactly in terms of a matrix-vector multiplication (using modulo-2 arithmetic). Specifically, the transmitted code-vector $t$ may be obtained from source-vector $s$ using a matrix multiplication: $$t=G^{T}s$$

Where $G$ is the generator matrix of the code: $$G^T=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 1& 1& 0\\ 0& 1& 1& 1\\ 1& 0& 1& 1\end{array}\right]$$

The columns of the generator matrix may be viewed as defining four basis vectors in a seven dimensional binary space. The sixteen codewords are obtained by taking all possible linear combinations of these vectors (in modulo-2 arithmetic). This is a useful perspective:

• With 7 dimensions, we have 128 possible vectors, out of which only 2^4 = 16 are valid. This means that if we get an invalid vector, we know that it needs to be corrected.
• The 16 valid vectors are well spread-out in the space (every pair of codewords differs in at least 3 positions), enabling correction

Decoding Hamming Code

Decoding the hamming code follows the same logic as before. Assuming that the channel is a binary symmetric channel and all source vectors are equiprobable, we want to choose a source vector $s$ whose encoding $t(s)$ differs from received $r$ in as few bits as possible. Recall that the theorem we proved earlier shows that we want to maximize $p(r_1,...,r_7|s)$.

Naively, we can enumerate all 16 valid hamming codes (each of length 7), and then compare $t(s)$ against each and find the closest. This is inefficient as our codes get longer.

The better way is syndrome decoding. A syndrome is defined as the pattern of violations of the parity bits. In other words, it is the vector of "unhappy" parity bits.

Syndome example. Suppose we transmit t = 1000101 and noise flips the second bit, giving us r = 1100101. The syndrome would be z = 110, because the first two parity checks are unhappy and the third is happy.

The syndrome decoding task is thus to find the unique bit that lies inside all the unhappy circles and outside the happy circles. If we can find such a bit, flipping it would account for the observed syndrome.

Matrix Version of Hamming Decoding

We can describe the decoding operation in terms of matrices. Let us define: $$P=\left[\begin{array}{cccc}1& 1& 1& 0\\ 0& 1& 1& 1\\ 1& 0& 1& 1\end{array}\right]\in R^{3\times 4}$$

Let $H=\left[\begin{array}{cc}-P& I_3\end{array}\right]$. Then the syndrome vector is: $$z=Hr$$

Since the $-P$ part computes the expected parity bit and subtracts it from the actual received parity bits (from the identity part). But because in modulo-2 arithmetic, $-1\equiv 1$, so: $$H=\left[\begin{array}{cc}P& I_3\end{array}\right]=\left[\begin{array}{ccccccc}1& 1& 1& 0& 1& 0& 0\\ 0& 1& 1& 1& 0& 1& 0\\ 1& 0& 1& 1& 0& 0& 1\end{array}\right]$$

It should be clear that for valid transmitted vectors of the form $t=G^{T}s$, $Ht$ will be the zero vector / syndrome.

Exercise 1.4. Prove that this is so.

We want to show that $H{G}^{T}s$ is the zero vector for all $s$. Consider $H{G}^T$. We have: $$H{G}^T=\left[\begin{array}{cc}P& I_3\end{array}\right]\left[\begin{array}{c}{I}_4\\ P\end{array}\right]$$

For compatible matrix blocks (i.e. $P\cdot I_4$ is defined etc.), we have: $$H{G}^T=P+P=0\in R^{3\times 4}$$

Hence $H{G}^{T}s$ will always be the zero vector.

We close this section of hamming decoding by noting that the received vector is obtained by: $$r=G^{T}s+n$$

And the syndrome vector is: $$z=Hr=H{G}^{T}s+Hn=Hn$$

Hence, the syndrome decoding problem is to find the most probably noise vector that satisfies $z=Hn$. Such a decoding algorithm is called maximum likelihood decoder.

Exercise 1.5 Refer to the (7,4) Hamming code. Decode these received strings: r = 1101011

We have z = 011, so flip $r_4$, $\hat{s}$=1100

r = 0110110

We have z = 111, so flip $r_3$, $\hat{s}$=0100

r = 0100111

We have z = 001, so flip $r_7$, $\hat{s}$=0100

r = 1111111 We have z = 000, so flip nothing, $\hat{s}$=1111

Exercise 1.6. Calculate the probability of block error $p_B$ of the 7, 4 hamming code as a function of the noise level $f$ and show that to leading order it goes as $21f^2$.

The block error is the probability that one or more of the decoded bits in one block fail to match the corresponding source bits.

Assuming that whenever 2 or more bits are flipped in a block of 7 bits, we get a block decoding error, we can derive this as a binomial distribution. $$\begin{array}{rl}{p}_B& =P(\text{At least 2 bits flipped})\\ & =1-P(\text{0 bits flipped})-P(\text{1 bit flipped})\\ & =1-(1-f{)}^7-7f(1-f{)}^6\end{array}$$

Recall Taylor's expansion: $$(1-f{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(-f{)}^k$$

So for $p_B$: $$\begin{array}{rl}{p}_B& =1-(1-f{)}^7-7f(1-f{)}^6\\ & =1-(1-7f+21f^2+...)-7f(1-6f+...)\\ & =21f^2+O(f^3)\end{array}$$

The leading term is $21f^2$.

Show that to leading order the probability of bit error $p_b$ goes as $9f^2$.