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$.

The naive way to solve this is to try to enumerate for each source bit possible scenarios and compute the probabilities. But that is very tedious.

The observation is to consider the subset of cases under a block error where exactly two bits are corrupted. This is the leading case because the probability of 3 or more bits being corrupted becomes increasingly unlikely.

Now when two bits are corrupted, exactly 3 bits will be in error if we follow optimal decoding.

• Suppose bits $i,j$ are corrupted. Since the syndrome follows $z=Hn$, and $n_i=n_j=1$, then this corresponds to an operation where we add the $i^{th}$ and $j^{th}$ columns of H together $$z=H_i+H_j$$
• The decoder flips the single bit that explains the syndrome $z$, since this has the highest likelihood. In other words, the bit flipped would be the column $k$ where $H_k+z=0$
• We can show that $k\ne i\ne j$, which tells us that exactly 3 bits will be in error

It is furthermore possible to show that these 3 bits in error are uniformly distributed amongst the 7 possible positions in the code (but not shown here). Since the probability of a block error goes as $21f^2$, and each block error has a leading explanation that $\frac{3}{7}$ bits are in error, so the probability of any bit being in error is $$\frac{3}{7}\times 21f^2=9f^2$$

Exercise 1.7 Find some noise vectors that give the all zero syndrome (i.e. noise vectors that leave all the parity checks unviolated). How many such noise vectors are there?

We use the formula $Hn=z$. If $z=0$, then $Hn=0$.

In other words, we are finding the number of elements in the null space of $H$. Using the fundamental theorem of linear maps: $$\text{rank}(H)+dim(\text{nullspace}(H))=dim(V)$$

Since $\text{rank}(H)=3$ (the 3 row vectors in $H$ are linearly independent) and $dim(V)=7$ (as each vector has 7 elements), $dim(\text{nullspace}(H))=7-3=4$.

The number of elements in the null space is thus $2^4=16$, because each element can be either 0 or 1. We remove the all zero solution as it is not a valid noise vector, leaving us with 15 non-zero noise vectors that leave us with the all zero syndrome.

Exercise 1.8 I asserted above that block decoding error will results whenever two or more bits are flipped in a single block. Show that this is indeed so. [In principle, there may be error patterns that, after decoding, lead only to corruption of parity bits, with all source bits correct]

We need to show that when two or more bits are flipped in a single block, there will always be at least one source bit that is still corrupted (after decoding).

We need to consider the formula: $$Hn=z$$

We saw earlier that we can interpret this matrix-vector multiplication as adding up columns in $H$ (which is $3\times 7$) corresponding to the positions in $n$ which have value 1. Hence: $$z=H_i+H_j+...\text{where }i,j,...\text{ are the noise positions}$$

The optimal bit to be flipped is the columns $x$ s.t. $H_x=z$.

In case where two bits are flipped, we can show that $H_x\ne H_i\ne H_j$. This is because if $H_x=H_i$, then $H_j=0$ which is a contradiction. This means that three bits will be flipped under optimal decoding.

It suffices to show that the three bits flipped cannot all be parity bits. Recall that we had setup the generator $G$ to put the source bits in the first 4 positions and the parity bits in the last 3 positions. The corresponding "parity check" matrix $H$ is like 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]$$

In order to flip all 3 parity bits, we need $H_i+H_j=H_k$ such that $[1,0,0{]}^T+[0,1,0{]}^T=[0,0,1{]}^T$ (or some other combination), which is not possible as they are linearly independent. Hence for the two-bit case, at least one source bit is corrupted.

In the case where three bits are flipped, we can again show that $H_x\ne H_i\ne H_j\ne H_k$. This is because if $H_x=H_i$, then $H_j+H_k=0$, which contradicts since $H_j\ne H_k$. This means that total of 4 bits will be flipped. Since there are only 3 parity bits, at least one source bit must be flipped.

If at least four bits are flipped, then it may be possible for a corrupted position to be flipped back (into a correct state). This will leave us with at least 3 corrupted bits. Hence we just need to show (in the four-bit case) that the 3 corrupted bits remaining cannot all be parity bits.

Suppose $H_x=H_i$ (i.e. position $i$ was corrupted but flipped back), and $H_j+H_k+H_l=0$. Clearly, $j,k,l$ cannot all correspond to parity bits, because they are linearly independent and cannot add up to $0$. So we are done.

Exercise 1.10 A (7, 4) Hamming code can correct any one error; might there be a (14, 8) code that can correct any two errors? Does the answer to this question depend on whether the code is linear or non-linear?

In the (14, 8) code, we have 8 source bits and 6 parity check bits.

First try to understand why (7, 4) works.

• $H$ is $3\times 7$, because there are 3 parity checks
• So we have $2^3=8$ syndromes, $7$ if we subtract the all zero syndrome
• We can correct any one error because 1-bit errors map exactly to the $7$ non-zero syndromes

With (14, 8):

• $H$ is $6\times 14$, because there are 6 parity checks
• So $2^6=64$ possible syndromes, $63$ non-zero syndromes
• 1-bit errors map to $14$ possible non-zero syndromes, so we still have $63-14=49$ syndromes to use
• 2-bit errors map to potentially $\left(\genfrac{}{}{0ex}{}{14}{2}\right)=91$ syndromes
• There are insufficient syndromes to correct for all possible 2-bit errors

So no, a (14, 8) hamming code cannot possibly correct any two errors.