Source/Channel Coding Theorems (Scribe by Eric Chan)

Introduction

Recall the mathematical analog of a communication system. The system encode the source message into codeword, transmit the codeword to form the output sequence, and decode the sequence to reconstruct the message. Two fundamental questions hence are arised: 1) how short can be the codeword, and 2) how much can be the channel transmission rate? Data compression and data transmission form a pair of dual problems. During compression, we remove all the redundancy in the data to form the most compressed version possible, whereas during data transmission, we add redundancy in a controlled fashion to combat errors in the channel. In the lecture, we discussed the two questions separately. Results in short are: R>=H(X); R<=C.

Source Coding Theorem

  Converse for Source Coding Theorem

A source generates n i.i.d. random variables , each with entropy H(X). The encoder Alice encodes this into a string of nR bits  (R is the rate). The decoder Bob decodes the source as the sequence of bits . 

Rearranging the terms gives  , which shows that information will be lost certainly unless .

  Achievability for Source Coding Theorem

In week 2, we have made use of Asymptotic Equipartition Property (AEP) and designed a simple source coding scheme. In the scheme, encoding is a function that maps input to an unbalanced tree. Sequences in typical set are prefixed by a 0 and mapped to the left subtree, while sequences in atypical set are prefixed by a 1 and added to the right subtree. 

This time, we consider random coding, again based on AEP (because we are interested in when n is very large and typical set yields a good relationship to entropy function for analysis). The scheme is as the following.

Encode: For each source sequence  which is in typical set, encoder Alice assigns  bits  i.i.d, uniformly at random. We denote  as the function of the assignment. This assigment is known a priori to both Alice and Bob, and is called the codebook.

Decode: Given a string , decoder Bob examines the codebook to see if there is a unique typical   that generates this . If so, he outputs . Else he declares a decoding error.

This scheme will occur error either (a) when the source sequence is from atypical set and has no encoding defined, or (b) when Bob gets confused by more than one possible he can decode to. This is illustrated in the below figure.

We adopt  and will show that this is enough to appropriate encode the source sequence without significant error of recovering the source sequence.

The probability of error condition (a) is upper bounded by . On the other hand, for condition (b), we do a simple analysis. As , . Taking union bound of this crashing over all elements in the typical set with at most size , the probability of error condition (b) is upper bounded by  . Therefore, the total probability of error is , which becomes a negligible risk of information loss when n is very large. This suggests the achievability of data compression in source coding as long as the rate is greater than .

In conclusion, combining the result in two subsections, we can see a gap for  which lies around . The optimum compression scheme is left to further discussion.

Channel Coding Theorem

  Intuition 

This time, source generates a message  . Alice encodes the message into a string of n symbols . After passing through the discrete memoryless channel (per-symbol transition probabilities given by the conditional distribution p(y|x)), the decoder Bob receives , and decodes the source as .  

Let's consider jointly typical sequences. (Again, we are interested in the typical input sequences with most of the probability. It also makes sense that they should map to typical output sequences with comparable high probability.) For each typical input n-sequence, there are  typical output sequences. (This may due to the noisy channel.) We can consider each set of typical output sequences geometrically as a Hamming ball in the Hamming metric. This is illustrated by the above figure. Though the total number of typical output sequences is , our goal is to uniquely distinguishable input sequences. Thus, it is equivalent to ask how many small Hamming ball can pack into the space of all possible sequences. By dividing the two numbers, the  number of disjoint sets is at most  . Up to this point, we should have gotten the intuition. If we define channel capacity  as the maximum rate that information can be transmitted reliably over a DMC, it should follow something like .