THEORY EXAMINATION (SEM–IV) 2016-17 INFORMATION THEORY AND CODING

B.Tech Engineering 0 downloads

₹29.00

Course: B.Tech (ECE – 4th Semester)
Subject Code: NEC408
Subject Title: Information Theory and Coding
Exam Type: Theory
Duration: 3 Hours
Maximum Marks: 100

SECTION – A (10 × 2 = 20 Marks)

Short, concept-based questions covering basic principles of communication and coding.

Key Topics:

Communication System Block Diagram – Source → Encoder → Channel → Decoder → Receiver.

Entropy Maximum Condition – Entropy is maximum when all symbols are equiprobable.

Hmax=log⁡2NH_{max} = \log_2 NHmax=log2N

Source efficiency: η=HHmax×100%\eta = \frac{H}{H_{max}} \times 100\%η=HmaxH×100%

Non-Singular Code – Each codeword must be distinct (one-to-one mapping).

Properties of Mutual Information:

I(X;Y)≥0I(X;Y) \geq 0I(X;Y)≥0

I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)

Shannon-Hartley Theorem:

C=Blog⁡2(1+SN)C = B \log_2(1 + \frac{S}{N})C=Blog2(1+NS)

where CCC=capacity, BBB=bandwidth, S/NS/NS/N=signal-to-noise ratio.

Properties of Block Codes: Linearity, fixed block length, error detection and correction.

Hamming Weight: Number of 1’s in a code vector.
Example: C₁ = 0001010 → weight = 2; C₂ = 1010101 → weight = 4.

Convolutional Codes: Continuous stream-based coding vs block-based; defined by generator polynomials.

Zero Memory Information Source: Emits independent symbols →

H(Xn)=nH(X)H(X^n) = nH(X)H(Xn)=nH(X)

(23,12) Golay Code: Called a perfect code because it meets the Hamming bound with equality.

SECTION – B (5 × 10 = 50 Marks)

Numerical and derivation-based questions on entropy, coding algorithms, and information measures.

Key Problems:

(a) Entropy Calculation & Source Extension

Source: S={S1,S2,S3,S4}S = \{S_1, S_2, S_3, S_4\}S={S1,S2,S3,S4}

Probabilities: 4/11,3/11,2/11,2/114/11, 3/11, 2/11, 2/114/11,3/11,2/11,2/11

Compute:

H(S)=−∑pilog⁡2piH(S) = -\sum p_i \log_2 p_iH(S)=−∑pilog2pi

and show H(S2)=2H(S)H(S^2) = 2H(S)H(S2)=2H(S).

(b) Source Coding

Need: Reduce redundancy → improve channel efficiency.

Compact Codes: Codes minimizing average length (e.g., Huffman codes).

External Property of Entropy: Considers both signal and noise contributions to total entropy.

(c) Shannon–Fano Coding Example

Source: S={X1,X2,X3,X4,X5,X6}S = \{X_1,X_2,X_3,X_4,X_5,X_6\}S={X1,X2,X3,X4,X5,X6}
Probabilities: 0.4, 0.2, 0.2, 0.1, 0.08, 0.02

Tasks:

Generate Shannon–Fano code table.

Calculate efficiency:

η=HLavg×100%\eta = \frac{H}{L_{avg}} \times 100\%η=LavgH×100%

Explain differential entropy for continuous signals.

(d) Linear Block Codes

Given parity matrix:

P=[111110101011]P = \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1 \end{bmatrix}P=111011011011

Find code vectors.

Detect & correct error in R = [1011100].

(e) Convolutional Code (4,3,2)

Given input polynomials:

u(1)(D)=1+D2,u(2)(D)=1+D,u(3)(D)=1+Du^{(1)}(D) = 1 + D^2,\quad u^{(2)}(D) = 1 + D,\quad u^{(3)}(D) = 1 + Du(1)(D)=1+D2,u(2)(D)=1+D,u(3)(D)=1+D

Construct codeword using transform-domain approach.

(f) Mutual Information Example

Given joint probability matrix (page 2, visual table) of 5×4 values for A and B.
Compute:

H(A), H(B), H(A,B), I(A;B)=H(A)+H(B)−H(A,B)H(A),\ H(B),\ H(A,B),\ I(A;B) = H(A) + H(B) - H(A,B)H(A), H(B), H(A,B), I(A;B)=H(A)+H(B)−H(A,B)

Discuss a priori entropy, posteriori entropy, and equivocation.

(g) Huffman Coding Example

Source probabilities: A=1/3,B=1/27,C=1/3,D=1/9,E=1/9,F=1/27,G=1/27A=1/3, B=1/27, C=1/3, D=1/9, E=1/9, F=1/27, G=1/27A=1/3,B=1/27,C=1/3,D=1/9,E=1/9,F=1/27,G=1/27

Construct ternary Huffman code, compute average length & efficiency.

(h) Shannon–Fano–Elias Coding

Source: A=0.25,B=0.25,C=0.2,D=0.15,E=0.15A=0.25, B=0.25, C=0.2, D=0.15, E=0.15A=0.25,B=0.25,C=0.2,D=0.15,E=0.15

Find code length and efficiency.

SECTION – C (2 × 15 = 30 Marks)

Advanced questions focusing on channel capacity, error control codes, and system design.

Q3. Binary Symmetric Channel (BSC)

Given transition matrix and probabilities:

P(Y/X)=[3/41/41/43/4], P(X1)=2/3, P(X2)=1/3P(Y/X) = \begin{bmatrix} 3/4 & 1/4 \\ 1/4 & 3/4 \end{bmatrix},\ P(X_1)=2/3,\ P(X_2)=1/3P(Y/X)=[3/41/41/43/4], P(X1)=2/3, P(X2)=1/3

Find:

H(X)H(X)H(X), H(Y)H(Y)H(Y), H(Y∣X)H(Y|X)H(Y∣X), and Channel Capacity

C=H(Y)−H(Y∣X)C = H(Y) - H(Y|X)C=H(Y)−H(Y∣X)

Also check Kraft–McMillan Inequality to identify instantaneous codes among A, B, C, D (table on page 2).

Q4. Short Notes

(i) BCH & RS Codes – Cyclic error-correcting codes for multi-bit errors.
(ii) Golay Codes – Perfect codes used in deep-space communication.
(iii) Burst vs Random Error Correction – Burst errors occur in clusters; random occur independently.

Also, given a (6,3) linear block code, where:

C4=d1+d2,C5=d1+d3,C6=d2+d3C_4 = d_1 + d_2, \quad C_5 = d_1 + d_3, \quad C_6 = d_2 + d_3C4=d1+d2,C5=d1+d3,C6=d2+d3

Tasks:

Write Generator (G) and Parity-check (H) matrices.

Construct Standard Array Table for decoding.

Q5. Convolutional Codes & Hamming Distance

(a) Define and explain Hamming Distance and Minimum Distance with examples.

(b) For (3,1,2) convolutional code with
g1=110,g2=101,g3=111g_1 = 110, g_2 = 101, g_3 = 111g1=110,g2=101,g3=111:

Draw Encoder Diagram.

Find Generator Matrix.

Encode information sequence (11101) using time-domain approach.

Key Concepts Summary

Concept	Formula / Definition
Entropy	H=−∑pilog⁡2piH = -\sum p_i \log_2 p_iH=−∑pilog2pi
Mutual Information	( I(X;Y) = H(X) - H(X
Channel Capacity	C=Blog⁡2(1+S/N)C = B\log_2(1 + S/N)C=Blog2(1+S/N)
Source Efficiency	η=H/Lavg\eta = H / L_{avg}η=H/Lavg
Hamming Distance	No. of differing bits between two codewords
Linear Block Code	C=uGC = uGC=uG, where ( G = [I_k
Convolutional Code	Output = input convolved with generator polynomials