Introduction to Coding Problem and Part of Problem Set 1(Scribe: WANG Limin)

I. Introduction to Coding Problem

The main problem of information theory can be described as follows: Imagine a stream of source data, say in the form of bits (0 or 1), is being transmitted over a communication channel.  In the source,  we want to encode the source message to make it more efficient and robust for transmission. Meanwhile, receiver will hope to decode the message and get meaning of the message(sometimes we may not recover the source message totally due to the noise in the channel).

See the next figure for an example, our source send a message denoted as  where the alphabet is , then the encoder encodes the message as codeword  where the alphabet is , finally the decoder receives the codeword and recovers the message as  where the alphabet is . Encoder is usually a function that assigns a codeword to each source message and decoder attempts to correct any errors in transmission and then recovers the original message. Usually the random variable  form a first order Markov Chain, i.e. 

Ideally, we wish to decode correctly and get the source message, i.e. .  However, in fact there is always noise during the transmission (e.g. bit 0 has probability p to be turned into 1 and vice-versa) and we can not guarantee the receiver recovers the message totally correct. In information theory, we usually consider the error probability  less than some threshold ,i.e. . In addition to robustness, we need to take the efficiency into account and want the length of our code is smaller than the source message, i.e.. We usually define the rate . When , the error  may converge to  and the rate  can reach to best rate , see the next figure for illustration.

There is a common sense that encoding source information, by adding additional information, sometimes referred to as redundancy, that can be used to detect and perhaps correct errors in transmission. The more redundancy that we add to the original source code. the more reliably we can detect and correct errors, but the less efficient we become at transmitting the source data. Thus, we need to keep a balance between efficiency and robustness.

II. Part of Problem Set 1

A certain fair coin is tossed n times. Each time it is tossed, the result is independent of the previous toss. This is an example of an i.i.d. binary random variable.

Q1: (Worst-case "compression") 

(a) If the coin described above is tossed n times, how many distinct length-n sequences of coin tosses are possible?

 The answer is 

(b) Given N possible outcomes of a random variable, how many bits (elements from {0,1}) are required to assign a unique length-N bit-sequence to each possible outcome?

The answer is  ,see the next figure for an example, we have 8 possible out comes and we need 3 bit to assign a unique length-3 bit sequence to each possible outcome. Generally, for a full binary tree with N leaves, the height is 

(c) Describe a method based on binary trees, to assign a length-N bit-sequence to an outcome, based on a binary tree, and a corresponding method to reconstruct the coin-toss sequence from the bit-sequence.

Code: if coin is tossed head, the output bit is 0; if coin is tossed tail the output bit is 1.

Decode: if the bit is 0, the tossed result is head; if the bit is 1, the tossed result is tail.

Since the coin is fair, i.e the probability of head is 0.5, we can use a full binary tree for our coding and decoding scheme, see the next figure for a example. If we coin is head, we then go left and the bit is 0. If coin is tail, we then go right and the bit is 1. The same process is for decoding.

(d) If the encoding alphabet is ternary (eg: {0,1,2}) instead of binary, how does your answer to (b) change? How about your answer to (c), if ternary trees are allowed? What if you were tossing a six-sided dice instead of a coin? How do your answers change? What is the time-complexity of your assignment schemes?

The answer is  for problem (b).  We can think of ternary trees with N leaves, then the average of tree height is , see the next figure for a example with 9 leaves, we only need 2 ternary bits. 

Coding idea:

Step1: We can according the coding scheme of problem (d) to map the tossed result into a n-length bit, the time complex is , e.g. HTHHT coded as 01001.

Step2: We need translate the binary code into ternary code, the time complexity is , e.g. (01001)₂=(100)₃

Thus the total time complexity is .

Decoding idea:

The reverse order of coding scheme and the time complexity is .

Note: n is the length of bit sequence.

If I toss a six-sided dice, the answer is similar to a coin.

A second coin is biased with probability p, i.e., it comes up Heads with probability p and Tails with probability 1-p. Each time it is tossed, the result is independent of the previous toss. This is an example of an i.i.d. binary random variable, also called a Bernoulli(p) random variable.

Q2: (Average-case compression)

(b) What is the probability of observing a particular coin-toss sequence with Heads?

The answer is 

(c) What is the size of the type-class T(k,n) of all coin-toss sequences with exactly k Heads? What is therefore the probability of observing the type-class T(k,n)?

The size of the type-class T(k,n) is  and thus the probability of observing the type class T(k,n) is 

The other questions are in the next scribe and thanks for your reading.