EC-702-B Information Theory and Coding - Nov 2023 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aDefine uncertainty, information and entropy. Show that the entropy is maximum when all the message are equiprobable. Assume $M = 3$.
   How to answer

   • Define uncertainty, self-information and entropy with formulas
   • Entropy expression for M=3
   • Use Lagrange multiplier / differentiation to show maximum at equiprobable case
   • Conclude H_max = log M
2. 7 Marks
   bThe international Morse code uses a sequence of dots and dashes to transmit letters of the English alphabet. The dash is represented by a current pulse that has a duration of 3 units and the dot has a duration of 1 unit. The probability of occurrence of a dash is 1 of the probability of occurrence of a dot.

   1. i)Calculate the information content of a dot and a dash.
   2. ii)Calculate the average information in the dot-dash code.
   3. iii)Assume that the dot lasts 1 m sec, which is the same time interval as the pause between symbols. Find the average rate of information transmission.
   How to answer

   • Find P(dot) and P(dash) from given ratio
   • Calculate self-information I = -log2 P for dot and dash
   • Calculate average information / entropy H
   • Calculate average duration and information rate
3. 7 Marks
   aShow that $I(X; Y) = H(X) + H(Y) - H(X, Y)$.
   How to answer

   • Define joint, marginal and conditional entropies
   • Define mutual information I(X;Y)
   • Expand using definitions to get H(X)+H(Y)-H(X,Y)
   • Conclude proof
4. 7 Marks
   bExplain general form of a decoder for cyclic codes with error correction procedure.
   How to answer

   • Define cyclic codes and syndrome concept
   • Describe general decoder block diagram
   • Explain error correction steps: syndrome calculation, error pattern detection, correction
   • Mention Meggitt decoder if applicable
5. 7 Marks
   aConstruct the Huffman code with minimum code variance for the following probabilities and also determine the code variance and code efficiency: {0.25, 0.25, 0.125, 0.125, 0.125, 0.0625, 0.0625}.
   How to answer

   • Sort probabilities and construct Huffman tree with minimum variance
   • Assign codes and find code lengths
   • Calculate average length, entropy, efficiency and variance
   • Present code table
6. 7 Marks
   bDiscuss about arithmetic coding with suitable example.
   How to answer

   • Define arithmetic coding principle
   • Explain interval subdivision with example
   • Show encoding and decoding steps
   • Mention advantages over Huffman
7. 7 Marks
   aA BSC has the error probability $p = 0.2$ and the input to the channel consists of 4 equiprobable messages $x_1 = 000$; $x_2 = 001$; $x_3 = 011$; $x_4 = 111$. Calculate:

   1. i)p (0) and p (1) at the input
   2. ii)Efficiency of the code
   3. iii)Channel capacity
   How to answer

   • Find P(0), P(1) at input from 4 equiprobable 3-bit messages
   • Calculate source entropy and code efficiency
   • Calculate BSC capacity C = 1 - H(p) with p=0.2
   • Present numerical results
8. 7 Marks
   bFrom channel capacity theorem, find the capacity of a channel with infinite bandwidth and explain.
   How to answer

   • State Shannon channel capacity theorem C = B log2(1+S/N)
   • Take limit as B -> infinity
   • Derive C_infinity = (S/N0) log2 e
   • Explain physical meaning
9. 7 Marks
   aDiscuss the Binary Erasure Channel (BEC) and also derive channel capacity equation for BEC.
   How to answer

   • Define BEC with erasure probability
   • Draw channel transition diagram
   • Derive mutual information and maximize to get C = 1 - alpha
   • Interpret result
10. 7 Marks
    bThe generator matrix for a (6, 3) block code is given below. Find all code vectors of this code. $$G = \begin{bmatrix} 1 & 0 & 0 & : & 1 & 1 & 0 \\ 0 & 1 & 0 & : & 0 & 1 & 1 \\ 0 & 0 & 1 & : & 1 & 1 & 1 \end{bmatrix}$$
    How to answer

    • Interpret 3x6 generator matrix in systematic form
    • Generate all 8 combinations of 3 message bits
    • Compute code vectors C = mG
    • List all 8 codewords
11. 7 Marks
    aDesign (n, k) hamming code with a minimum distance of $d_{min} = 3$ and message length of 4 bits.
    How to answer

    • Determine r for k=4, d_min=3 using Hamming bound 2^r >= n+1
    • Get (7,4) Hamming code parameters
    • Construct parity check and generator matrices
    • Explain error correction capability
12. 7 Marks
    bA (7, 4) cyclic code has a generator polynomial: $g(X) = X^3 + X + 1$.

    1. i)Draw the block diagram of encoder and syndrome calculator.
    2. ii)Find generator and parity check matrices in systematic form.
    How to answer

    • Draw encoder and syndrome calculator using g(X)=X^3+X+1
    • Derive systematic generator and parity check matrices
    • Show shift-register implementation
    • List codewords if needed
13. 7 Marks
    aExplain the working of (2,1,3) Convolutional encoder using transform domain approach.
    How to answer

    • Describe (2,1,3) encoder structure with constraint length
    • Explain transform domain / D-transform representation
    • Give generator polynomials and output equations
    • Show example encoding
14. 7 Marks
    bExplain BCH codes in details with taking a suitable example.
    How to answer

    • Define BCH codes and parameters
    • Explain generator polynomial construction using GF
    • Give suitable example e.g., primitive BCH
    • Mention error correction capability
15. 14 Marks
    Write a short notes on any two:

    1. i)Lempel-Ziv Coding
    2. ii)Code Tree
    3. iii)Viterbi Algorithm
    4. iv)Extended Huffman Coding
    How to answer

    • Select any two topics from list
    • Define principle and encoding/decoding steps for each
    • Give example / diagram / algorithm flow
    • Mention applications