Problem Set 2
ICT
1. The symbols of the alphabet A = {-5, -3, -1, 0, 1, 3, 5} of a zero-memory source have the probabilities {0.05,
0.1, 0.1, 0.15, 0.05, 0.25, 0.3}. Find the entropy of the source. If the source is quantized based on the following
rule:
𝑄(−5) = 𝑄(−5) = −4
𝑄(−1) = 𝑄(0) = 𝑄(1) = 0
𝑄(3) = 𝑄(5) = 4,
what is the entropy of the quantized source?
2. A random variable 𝑋 is distributed on a set 𝒜 = {𝑎1 , 𝑎2 , … 𝑎𝑛 } with corresponding probabilities
{𝑝1 , 𝑝2 , … 𝑝𝑛 } and another random variable 𝑌 is defined on the same set but distributed uniformly.
Prove that 𝐻(𝑋) ≤ 𝐻(𝑌)
1 1 1 1
3. Construct a Huffman code for a source with 𝑛 outputs with probabilities { , , , … , 𝑛−1 , 𝑛−1 },
2 4 2 2
respectively. Prove that the average code word length of the source is equal to the source entropy.
4. Can the code {01, 100, 101, 1110, 1111, 0011, 0001} be a Huffman code for any source probability
distribution? Give proper justification in favour of your decision.
5. Construct a ternary Huffman code for a source with output alphabet probabilities given by {0.05, 0.1,
0.15, 0.17, 0.18, 0.22, 0.13} using 0, 1, and 2 as code symbols. compute the average code word length,
efficiency, and redundancy of the code?
6. Prove that the capacity of a Bandlimited Additive White Gaussian Noise Channel is
𝑃
𝐶 = 𝑊 log2 (1 + )
𝑁0 𝑊
𝑁0
where 𝑊 is the bandwidth of the channel, 𝑃 is the average transmitted power, and is the power
2
spectral density of the additive white Gaussian noise.
6. Find the capacity of the binary symmetric channel (BSC) shown in Fig. 1.
Fig. 1
7. Prove that for a continuous random variable 𝑋, the differential entropy attains maximum value if the
random variable is Gaussian. The maximum value that it attains is log (√2𝜋𝑒𝜎𝑋2 ), where is the 𝜎𝑋2
variance of the random variable 𝑋.
8. What is the advantage of LZW coding over Huffman coding? Write down the algorithm for LZW
coding. A string is given by, 𝑆 = 𝑎𝑏𝑎𝑏𝑐𝑏𝑎𝑏𝑎𝑏𝑎𝑎𝑎𝑎𝑎𝑎𝑎. Encode the string using LZW coding. Show
the input string, prefix string, output code, table addition, added codeword, and stored format in a coding
table.
9. A source has the symbols 𝐴, 𝐵, 𝐶, and 𝐷 with probabilities 0.4, 0.3, 0.2, and 0.1, respectively. Use
arithmetic coding to encode the string ′𝐵𝐶𝐴𝐵′.
10. With block diagrams describe the function lossy predictive encoding and decoding.
11. Find the minimum distance of the code. Which code word(s) is (are) minimum weight?
12. Listing all code words of the (7, 4) Hamming code, find the minimum distance of the code.
13. The generator matrix of a (6, 3) linear code is
1 0 0 1 1 0
𝐺 = [0 1 0 1 0 1]
0 0 1 0 1 1
This code is extended by adding an overall parity check bit to each codeword so that the weight of each
resulting code word becomes even. Determine the parity check matrix of the extended code. What is
the minimum distance of the extended code?
14. Show the parity check matrix and the generator matrix of a (15,11) Hamming code in the systematic
form.
15. Given that 𝑐 = (1 0 0 1 1 1 0) is a codeword of the (7, 4) Hamming code. Determine the
received codeword 𝑣, error syndrome 𝑠, the decoder’s estimate of the error pattern and estimate of the
codeword when 𝑐 incurs the error patterns
(i) 𝑒1 = (0 0 1 0 0 0 0)
(ii) 𝑒2 = (0 1 0 1 0 0 0)
(iii) 𝑒1 = (1 0 0 0 1 0 1)
16. A (5,2) code is defined by the code words 𝒞 = {00000, 10100, 01111,11011} where the mapping
of information bits to code words is as follows:
00 → 00000
01 → 01111
10 → 10100
11 → 11011.
Check whether the code is linear. Find the generator matrix and the parity check matrix for the code.
17. Show that the (7,4) linear codes generated by
1 0 0 0 1 0 1 1 1 1 1 1 1 1
0 1 0 0 1 1 1 0 1 1 1 0 1 0
𝐺1 = [ ] and 𝐺2 = [ ] are equivalent
0 0 1 0 1 1 0 0 0 1 1 1 0 1
0 0 0 1 0 1 1 0 0 0 1 0 1 1
18. Given the (7,3) linear code with generator matrix
1 1 1 0 1 0 0
𝐺 = [0 1 1 1 0 1 0]. Determine the systematic form of 𝐺. Find the parity check matrix for
1 1 0 1 0 0 1
the code.
1 1 1 0 1 0 0
19. Given the parity check matrix, 𝐻 = [0 1 1 1 0 1 0] of the (7,4) Hamming code,
1 1 0 1 0 0 1
determine the systematic forms for the parity check and generator matrices of the (8, 4) extended
Hamming code.
20. Given that 𝑐 = (0 1 1 0 0 0 1 1) is a codeword of (8, 4) extended Hamming code with
even parity, determine the decoding decisions when 𝑐 incurs errors
(a) 𝑒1 = (0 0 0 0 0 1 0 0)
(b) 𝑒2 = (0 1 0 1 0 0 0 0)
(c) 𝑒3 = (0 0 0 1 1 0 1 0)