Skip to content

Assignment 3

Student ID: 1W23CF13 Name: TAI Yungche Course: Information Theory

Question 1

The alphabet is X = {A, B, C, •} with probabilities (0.5, 0.2, 0.2, 0.1). First, the cumulative distribution for the symbols is found. F(A) = 0.5 F(B) = 0.5 + 0.2 = 0.7 F(C) = 0.7 + 0.2 = 0.9 F(•) = 0.9 + 0.1 = 1.0 This gives the initial symbol intervals as [0, 0.5) for A, [0.5, 0.7) for B, [0.7, 0.9) for C, and [0.9, 1.0) for the stop symbol •.

The code to decode is "101000101011". The decimal value of this binary fraction is: \(v = 0.101000101011_2 = \frac{1}{2} + \frac{1}{8} + \frac{1}{128} + \frac{1}{512} + \frac{1}{2048} + \frac{1}{4096} = 0.635498046875\)

The sequence can now be decoded symbol by symbol. Starting with the interval [0, 1), the value \(v = 0.635...\) falls into the range for B, which is [0.5, 0.7). So the first symbol is B. The new interval for decoding is [0.5, 0.7).

To find the second symbol, the value is scaled to the new interval: \(v_1 = \frac{v - 0.5}{0.7 - 0.5} = \frac{0.635498... - 0.5}{0.2} = 0.67749...\) This scaled value falls into the range for B, [0.5, 0.7). The second symbol is B. The working interval becomes \([0.5 + (0.2 \times 0.5), 0.5 + (0.2 \times 0.7)) = [0.6, 0.64)\).

For the third symbol, the original value is scaled again: \(v_2 = \frac{v - 0.6}{0.64 - 0.6} = \frac{0.635498... - 0.6}{0.04} = 0.8874...\) This value falls into the range for C, [0.7, 0.9). The third symbol is C. The interval becomes \([0.6 + (0.04 \times 0.7), 0.6 + (0.04 \times 0.9)) = [0.628, 0.636)\).

For the next symbol: \(v_3 = \frac{v - 0.628}{0.636 - 0.628} = \frac{0.635498... - 0.628}{0.008} = 0.9372...\) This value falls into the range for the stop symbol •, [0.9, 1.0). The process terminates here.

The decoded sequence is BBC.

Question 2

The alphabet is X = {A, B, C} with probabilities (0.4, 0.4, 0.2). The symbol intervals are [0, 0.4) for A, [0.4, 0.8) for B, and [0.8, 1.0) for C.

(1)

To encode the sequence "ACAA", the interval [0, 1) is narrowed down. For the first symbol 'A', the new interval is [0, 0.4). For the second symbol 'C', the range is \(0.4 - 0 = 0.4\). The interval becomes \([0 + 0.4 \times 0.8, 0 + 0.4 \times 1.0) = [0.32, 0.4)\). For the third symbol 'A', the range is \(0.4 - 0.32 = 0.08\). The interval becomes \([0.32 + 0.08 \times 0, 0.32 + 0.08 \times 0.4) = [0.32, 0.352)\). For the last symbol 'A', the range is \(0.352 - 0.32 = 0.032\). The final interval is \([0.32 + 0.032 \times 0, 0.32 + 0.032 \times 0.4) = [0.32, 0.3328)\).

A binary string that represents an interval contained within [0.32, 0.3328) must be found. The range has a width of 0.0128. Using a 7-bit code, where the resolution is \(2^{-7} = 0.0078125\), the interval [0.32, 0.3328) corresponds to \([40.96 \times 2^{-7}, 42.5984 \times 2^{-7})\). The integer 41 can be chosen. The 7-bit binary for 41 is 0101001. The interval for this code is \([41/128, 42/128) = [0.3203125, 0.328125)\), which is inside [0.32, 0.3328). So, the encoded bitstream is 0101001.

(2)

To decode the code "010011", the binary string is first converted to its decimal value. \(v = 0.010011_2 = 1 \cdot 2^{-2} + 1 \cdot 2^{-5} + 1 \cdot 2^{-6} = 0.25 + 0.03125 + 0.015625 = 0.296875\). The code represents the interval \([0.296875, 0.296875 + 2^{-6}) = [0.296875, 0.3125)\).

Since there is no stop symbol, the unique sequence whose encoding interval contains the interval of the code must be found. The encoding interval for short sequences is considered. The code value 0.296875 lies in [0, 0.4), so the first symbol is 'A'. The interval for "A" is [0, 0.4). For "AB", the interval is \([0 + 0.4 \times 0.4, 0 + 0.4 \times 0.8) = [0.16, 0.32)\). The value is inside this range. For "ABC", the 'C' subinterval of [0.16, 0.32) is taken. The range is 0.16. The interval is \([0.16 + 0.16 \times 0.8, 0.16 + 0.16 \times 1.0) = [0.288, 0.32)\). The code's interval [0.296875, 0.3125) is fully contained inside the interval for "ABC", which is [0.288, 0.32). So, "ABC" is a possible decoded message.

Checking if a longer message is possible, like "ABCA": The interval for "ABCA" is the 'A' subinterval of [0.288, 0.32). The range is 0.032. The interval is \([0.288 + 0.032 \times 0, 0.288 + 0.032 \times 0.4) = [0.288, 0.3008)\). The code's interval [0.296875, 0.3125) is not contained in [0.288, 0.3008), since 0.3125 > 0.3008. This means the message cannot be "ABCA" or any longer sequence. The decoding is unique.

The decoded sequence is ABC.

Question 3

(1)

For this two-state Markov chain, the states are {0, 1}. The transition probabilities are given as \(p(0|0) = 0.4\), \(p(1|0) = 0.6\), \(p(0|1) = 0.25\), and \(p(1|1) = 0.75\).

The transition graph consists of two nodes labeled 0 and 1. There is an edge from node 0 to itself with weight 0.4 and an edge from node 0 to node 1 with weight 0.6. There is an edge from node 1 to node 0 with weight 0.25 and an edge from node 1 to itself with weight 0.75.

The transition matrix \(P\), where \(P_{ij} = p(j|i)\), is: \(P = \begin{pmatrix} 0.4 & 0.6 \\ 0.25 & 0.75 \end{pmatrix}\)

(2)

To compute the stationary distribution \(\pi = (\pi_0, \pi_1)\), the system of linear equations given by \(\pi P = \pi\) must be solved, along with the constraint \(\pi_0 + \pi_1 = 1\). The equation \(\pi P = \pi\) gives: \(0.4 \pi_0 + 0.25 \pi_1 = \pi_0\) \(0.6 \pi_0 + 0.75 \pi_1 = \pi_1\)

From the first equation: \(0.25 \pi_1 = \pi_0 - 0.4 \pi_0 = 0.6 \pi_0\) \(\pi_1 = \frac{0.6}{0.25} \pi_0 = 2.4 \pi_0\)

Substituting this into the constraint \(\pi_0 + \pi_1 = 1\): \(\pi_0 + 2.4 \pi_0 = 1\) \(3.4 \pi_0 = 1\) \(\pi_0 = \frac{1}{3.4} = \frac{5}{17}\)

Then, \(\pi_1\) can be found: \(\pi_1 = 1 - \pi_0 = 1 - \frac{5}{17} = \frac{12}{17}\). The stationary distribution is \(\pi = (\frac{5}{17}, \frac{12}{17})\).

(3)

To compute the entropy rate of the Markov chain, \(H(\mathcal{X})\), the formula \(H(\mathcal{X}) = \sum_i \pi_i H(X_{n+1}|X_n=i)\) is used. First, the conditional entropies for each state are calculated. \(H(X_{n+1}|X_n=0) = H(0.4, 0.6) = - (0.4 \log_2 0.4 + 0.6 \log_2 0.6)\) \(H(X_{n+1}|X_n=0) \approx - (0.4(-1.3219) + 0.6(-0.7370)) = 0.9710\) bits.

\(H(X_{n+1}|X_n=1) = H(0.25, 0.75) = - (0.25 \log_2 0.25 + 0.75 \log_2 0.75)\) \(H(X_{n+1}|X_n=1) \approx - (0.25(-2) + 0.75(-0.4150)) = 0.8113\) bits.

Now, the entropy rate can be computed using the stationary distribution. \(H(\mathcal{X}) = \pi_0 H(X_{n+1}|X_n=0) + \pi_1 H(X_{n+1}|X_n=1)\) \(H(\mathcal{X}) = \frac{5}{17} (0.9710) + \frac{12}{17} (0.8113)\) \(H(\mathcal{X}) \approx 0.2856 + 0.5727 = 0.8583\) bits/symbol.

The entropy rate of the Markov chain is approximately 0.8583 bits per symbol.