Information Theory and Coding (EC-702 (B)) - Unit 1 Short Notes

UNIT 1: Information Theory and Coding

Based on EC-702(B) Nov 2023 Paper Analysis

I. Fundamentals of Information Theory

1.1 Uncertainty, Information, and Entropy

• Uncertainty: Measure of unpredictability of a random variable $X$ with probabilities $$\displaystyle p(x_i) $$.

• Information Content: $$\displaystyle I(x) = -\log_2 p(x) $$ bits. Rarer events carry more information.

• Entropy: Average information per message:

$$H(X) = -\sum_{i=1}^{M} p(x_i) \log_2 p(x_i) \text{ bits}$$

\boxed{H(X) = -\sum p(x) \log_2 p(x)}

[!TIP]

Common Pitfall: Entropy uses $$\displaystyle \log_2 $$ for bits. Natural log gives nats. Always specify base.

1.2 Entropy Maximization

Theorem: For a fixed number of messages $M$, entropy $H(X)$ is maximum when all messages are equiprobable, i.e., $$\displaystyle p(x_i) = 1/M $$.

Proof for $$\displaystyle M=3 $$:

Let $$\displaystyle p_1, p_2, p_3 $$ with $$\displaystyle p_1+p_2+p_3=1 $$. Using Lagrange multipliers or Jensen’s inequality:

$$H = - (p_1 \log p_1 + p_2 \log p_2 + p_3 \log p_3)$$

Since $-\log x$ is convex, by Jensen:

$$H \leq -\log\left(\frac{p_1+p_2+p_3}{3}\right) = \log 3$$

Equality when $$\displaystyle p_1=p_2=p_3=1/3 $$.

\boxed{H_{\max} = \log_2 M}

[!TIP]

Exam Focus: Prove using calculus (set derivative to zero) or Jensen’s inequality. For $$\displaystyle M=3 $$, compute $$\displaystyle H = \log_2 3 \approx 1.585 $$ bits.

1.3 Mutual Information

• Definition: $$\displaystyle I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) $$. Measures information shared between $X$ and $Y$.

• Relationships:

  \begin{align*}

  I(X;Y) &= H(X) + H(Y) - H(X,Y) \

  I(X;Y) &= H(X) - H(X|Y) \

  I(X;Y) &= H(Y) - H(Y|X)

  \end{align*}

  \boxed{I(X;Y) = H(X) + H(Y) - H(X,Y)}

[!TIP]

Key Insight: $$\displaystyle I(X;Y) = H(X) $$ if $Y$ reveals $X$ completely; $$\displaystyle I(X;Y)=0 $$ if $X$ and $Y$ independent.

II. Source Coding (Lossless Compression)

2.1 Huffman Coding

• Algorithm:

  1. List probabilities in descending order.

  2. Combine two smallest probabilities into a new node (sum).

  3. Repeat until one node remains.

  4. Assign binary digits (0/1) to branches from combined nodes.

• Minimum Variance: Always combine the two smallest probabilities at each step. This minimizes both average length and variance among optimal codes.

• Code Efficiency: $$\displaystyle \eta = \frac{H(X)}{\bar{L}} $$, where $$\displaystyle \bar{L} = \sum p_i l_i $$.

Example: Probabilities $\{0.25, 0.25, 0.125, 0.125, 0.125, 0.0625, 0.0625\}$.

• Code lengths: $$\displaystyle l = \{2,2,3,3,3,4,4\} $$.

• $$\displaystyle \bar{L} = 2.625 $$ bits, $$\displaystyle H(X)=2.625 $$ bits → $$\displaystyle \eta = 1 $$ (100%).

[!TIP]

Exam Alert: For dyadic probabilities ($$\displaystyle p_i = 2^{-l_i} $$), Huffman code achieves $$\displaystyle \eta=1 $$. Always verify $\bar{L} \geq H(X)$.

2.2 Arithmetic Coding

• Principle: Represent entire message as a point in interval $[0,1)$. Subdivide interval according to symbol probabilities.

• Encoding Procedure:

  1. Start with $$\displaystyle [Low, High) = [0,1) $$.

  2. For each symbol, update:

     $$\displaystyle Low_{new} = Low_{old} + Range_{old} \cdot C_{low}(x) $$

     $$\displaystyle High_{new} = Low_{old} + Range_{old} \cdot C_{high}(x) $$

     where $$\displaystyle C_{low}(x) $$ is cumulative probability before $x$.

  3. After all symbols, choose any number in final interval.

Example: Alphabet $\{A:0.5, B:0.25, C:0.25\}$, message "BAC".

• After B: $[0.5, 0.75)$

• After A: $[0.5, 0.625)$

• After C: $[0.59375, 0.625)$ → encode as 0.6.

[!TIP]

Advantage: Approaches entropy limit even for non-dyadic probabilities. No need for integer bit lengths.

2.3 Lempel-Ziv (LZ) Coding

• Principle: Dictionary-based adaptive coding. Parse input into longest phrases already in dictionary.

• Procedure:

  1. Initialize dictionary with all single symbols.

  2. Scan input: find longest prefix $P$ in dictionary.

  3. Output pointer (index) to $P$ and next symbol.

  4. Add $P$ + next symbol to dictionary.

• Example: Input "101101010000".

  • "1" (new) → dict: {1}

  • "0" (new) → dict: {1,0}

  • "11" (new) → dict: {1,0,11}

  • "0" in dict, but "01" not → output pointer to "0", add "01".

  • Continue.

[!TIP]

Applications: ZIP, GIF, PNG. Universal – no prior probability knowledge needed.

2.4 Extended Huffman Coding

• Concept: Group $r$ source symbols into composite symbols to create a new alphabet with probabilities $$\displaystyle p_i^r $$. Apply Huffman to new alphabet.

• Purpose: Improve efficiency when original probabilities are not dyadic.

• Example: If single symbols have probabilities not powers of 1/2, grouping can make composite probabilities closer to dyadic.

2.5 Morse Code Analysis

Given:

• Dot duration = 1 unit, dash = 3 units.

• Pause between symbols = 1 unit.

• $$\displaystyle P(\text{dash}) = 1 \cdot P(\text{dot}) \Rightarrow P(\text{dot}) = P(\text{dash}) = 0.5 $$.

Calculations:

1. Information content:

   $$\displaystyle I(\text{dot}) = -\log_2 0.5 = 1 $$ bit,

   $$\displaystyle I(\text{dash}) = 1 $$ bit.

2. Average information per symbol:

   $$\displaystyle H = 0.5 \times 1 + 0.5 \times 1 = 1 $$ bit/symbol.

3. Transmission rate:

   • Time per dot-symbol = $1$ (dot) + $1$ (pause) = $2$ ms.

   • Time per dash-symbol = $3$ + $1$ = $4$ ms.

   • Average time/symbol = $$\displaystyle 0.5 \times 2 + 0.5 \times 4 = 3 $$ ms = $0.003$ s.

   • Rate $$\displaystyle R = \frac{1 \text{ bit}}{0.003 \text{ s}} = 333.33 $$ bits/s.

[!TIP]

Remember: Include pause time in symbol duration. Information content depends only on probability, not duration.

III. Channel Models & Capacity

3.1 Binary Symmetric Channel (BSC)

• Model: Crossover probability $p$.

$$P(Y=0|X=0) = 1-p,\quad P(Y=1|X=0) = p$$

$$P(Y=1|X=1) = 1-p,\quad P(Y=0|X=1) = p$$

• Given: $$\displaystyle p=0.2 $$, input messages $\{000, 001, 011, 111\}$ equiprobable ($$\displaystyle P=0.25 $$ each).

Calculations:

1. Output bit probabilities $p(0)$ and $p(1)$:

   Total input bits = $$\displaystyle 4 \times 3 = 12 $$.

   Count of 0s: in 000→3, 001→2, 011→1, 111→0 → total 6 zeros.

   So $$\displaystyle P(\text{input bit}=0) = 6/12 = 0.5 $$, $$\displaystyle P(\text{input bit}=1)=0.5 $$.

   Since channel is symmetric:

$$P(\text{output bit}=0) = P(\text{input}=0)(1-p) + P(\text{input}=1)p = 0.5 \times 0.8 + 0.5 \times 0.2 = 0.5$$

Similarly $$\displaystyle P(\text{output bit}=1)=0.5 $$.

2. Code efficiency:

   Source entropy $$\displaystyle H = \log_2 4 = 2 $$ bits (4 equiprobable messages).

   Average code length $$\displaystyle \bar{L} = 3 $$ bits (fixed-length code).

$$\eta = \frac{H}{\bar{L}} = \frac{2}{3} \approx 0.6667$$

3. Channel capacity:

$$C = 1 - H(p) = 1 - [-p \log_2 p - (1-p) \log_2 (1-p)]$$

$$\displaystyle H(0.2) = 0.7219 $$ bits → $$\displaystyle C = 0.2781 $$ bits/channel use.

[!TIP]

Note: Capacity is per channel use (per transmitted bit). Code efficiency here is source coding efficiency, not channel coding.

3.2 Binary Erasure Channel (BEC)

• Model: Erasure probability $\alpha$.

  $$\displaystyle P(Y=X|X) = 1-\alpha $$, $$\displaystyle P(Y=e) = \alpha $$ (erasure).

• Capacity Derivation:

  Mutual information $$\displaystyle I(X;Y) = H(Y) - H(Y|X) $$.

  $$\displaystyle H(Y|X) = H(\alpha) $$ (binary erasure event).

  Maximize $I$ over input distribution $P(X)$.

  For uniform input $$\displaystyle P(X=0)=P(X=1)=0.5 $$:

  $$\displaystyle P(Y=0) = P(Y=1) = \frac{1-\alpha}{2},\ P(Y=e)=\alpha $$.

  Then $$\displaystyle H(Y) = H\left(\frac{1-\alpha}{2}, \frac{1-\alpha}{2}, \alpha\right) $$.

  After simplification:

  \boxed{C = 1 - \alpha \text{ bits/channel use}}

[!TIP]

Intuition: Capacity decreases linearly with erasure probability. When $$\displaystyle \alpha=0 $$, $$\displaystyle C=1 $$; when $$\displaystyle \alpha=1 $$, $$\displaystyle C=0 $$.

3.3 Channel Capacity Theorem (Shannon Limit)

• AWGN Channel: Bandwidth $B$, signal power $P$, noise spectral density $$\displaystyle N_0 $$.

$$C(B) = B \log_2\left(1 + \frac{P}{N_0 B}\right) \text{ bits/s}$$

• Infinite Bandwidth Limit:

$$\lim_{B \to \infty} C(B) = \frac{P}{N_0} \log_2 e \approx 1.44 \frac{P}{N_0} \text{ bits/s}$$

\boxed{C_{\infty} = \frac{P}{N_0} \log_2 e}

[!TIP]

Implication: Increasing bandwidth indefinitely does not increase capacity beyond $$\displaystyle P/N_0 $$ (in nats/s). Trade-off: bandwidth vs. SNR.

IV. Error-Control Coding: Linear Block Codes

4.1 General Linear Block Codes

• Definition: $(n,k)$ code: $k$ information bits → $n$ transmitted bits. Code is subspace of $$\displaystyle \text{GF}(2)^n $$.

• Generator Matrix $G$: $k \times n$ matrix. Code vectors $$\displaystyle \mathbf{c} = \mathbf{m} G $$, $$\displaystyle \mathbf{m} \in \text{GF}(2)^k $$.

• Example: Given

$$G = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}$$

All code vectors (8 total):

$$\displaystyle \mathbf{m}=000 \to 000000 $$

$$\displaystyle \mathbf{m}=001 \to 001111 $$

$$\displaystyle \mathbf{m}=010 \to 010011 $$

$$\displaystyle \mathbf{m}=011 \to 011100 $$

$$\displaystyle \mathbf{m}=100 \to 100110 $$

$$\displaystyle \mathbf{m}=101 \to 101101 $$

$$\displaystyle \mathbf{m}=110 \to 110010 $$

$$\displaystyle \mathbf{m}=111 \to 111001 $$

4.2 Systematic Form

• Systematic $G$: $$\displaystyle G = [I_k \mid P] $$, where $$\displaystyle I_k $$ is $k \times k$ identity, $P$ is $k \times (n-k)$.

• Parity-Check Matrix $H$: $$\displaystyle H = [P^T \mid I_{n-k}] $$, satisfies $$\displaystyle G H^T = 0 $$.

• For above $G$ (already systematic):

$$P = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix},\quad P^T = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix}$$

$$H = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$$

4.3 Hamming Codes

• Design: Single-error-correcting ($$\displaystyle d_{\min}=3 $$). Parameters: $$\displaystyle n = 2^m - 1 $$, $$\displaystyle k = n - m $$.

• Procedure:

  1. Choose $m$ such that $$\displaystyle k = 2^m - m - 1 \geq $$ required message length.

  2. Construct $H$ ($m \times n$) with all non-zero binary $m$-tuples as columns (each column is binary representation of position index).

  3. Obtain $G$ from $H$: $$\displaystyle G = [I_k \mid P] $$ where $$\displaystyle H = [P^T \mid I_m] $$.

Example for $$\displaystyle k=4 $$:
$$\displaystyle m=3 $$, $$\displaystyle n=7 $$. Columns of $H$: all non-zero 3-bit vectors:

$$H = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}$$

(Columns correspond to positions 1–7 in binary: 001,010,011,100,101,110,111).

Then $G$ systematic:

$$G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$$

[!TIP]

Check: $$\displaystyle d_{\min}=3 $$ because any two columns of $H$ are linearly independent.

4.4 BCH Codes

• Primitive Polynomial: Generates $$\displaystyle \text{GF}(2^m) $$. Let $\alpha$ be primitive element.

• Generator Polynomial $g(X)$: LCM of minimal polynomials of $$\displaystyle \alpha^b, \alpha^{b+1}, \dots, \alpha^{b+\delta-2} $$, where $$\displaystyle \delta = 2t+1 $$ for $t$-error correction.

• Parameters: $$\displaystyle n = 2^m - 1 $$, $\deg g(X) \leq m t$, $$\displaystyle k = n - \deg g(X) $$.

Example: $$\displaystyle n=15 $$ ($$\displaystyle m=4 $$), $$\displaystyle t=2 $$ ($$\displaystyle \delta=5 $$), $$\displaystyle b=1 $$.

• Primitive polynomial: $$\displaystyle p(X)=X^4+X+1 $$.

• Roots: $$\displaystyle \alpha, \alpha^2, \alpha^3, \alpha^4 $$.

• Minimal polynomials:

  $$\displaystyle m_1(X) $$: roots $$\displaystyle \alpha, \alpha^2, \alpha^4, \alpha^8 $$ (degree 4)

  $$\displaystyle m_3(X) $$: roots $$\displaystyle \alpha^3, \alpha^6, \alpha^{12}, \alpha^9 $$ (degree 4)

• $$\displaystyle g(X) = \text{LCM}(m_1(X), m_3(X)) = m_1(X) m_3(X) $$ (since distinct), degree 8.

• So $(15,7)$ BCH code with $$\displaystyle d_{\min} \geq 5 $$.

[!TIP]

BCH vs Hamming: Hamming is BCH with $$\displaystyle t=1 $$. BCH can correct multiple errors.

V. Error-Control Coding: Cyclic Codes

5.1 Properties

• Cyclic Shift: If $$\displaystyle \mathbf{c} = (c_0,\dots,c_{n-1}) $$ is a codeword, then $$\displaystyle (c_{n-1}, c_0,\dots,c_{n-2}) $$ is also a codeword.

• Polynomial Representation: $$\displaystyle \mathbf{c} \leftrightarrow c(X) = c_0 + c_1 X + \dots + c_{n-1} X^{n-1} $$.

  Cyclic property $\iff$ $c(X)$ divisible by generator polynomial $g(X)$, where $$\displaystyle g(X) \mid (X^n + 1) $$.

5.2 Generator Polynomial

• Example: $(7,4)$ code with $$\displaystyle g(X) = X^3 + X + 1 $$.

  Check: $$\displaystyle X^7 + 1 = (X+1)(X^3+X+1)(X^3+X^2+1) $$ over $\text{GF}(2)$.

  $$\displaystyle \deg g = 3 $$, so $$\displaystyle k = n - \deg g = 4 $$.

5.3 Encoder Implementation

Operation:

• Non-systematic: Input stream fed directly; output is last stage.

• Systematic: Shift in $k$ information bits, then $n-k$ zeros; the parity bits appear in the last $n-k$ shifts.

5.4 Syndrome Calculator

5.5 Systematic Encoding (Matrix Derivation)

For $$\displaystyle g(X)=X^3+X+1 $$, $$\displaystyle n=7 $$, $$\displaystyle k=4 $$.

Method: Want $$\displaystyle c(X) = m(X) + X^k p(X) $$ with $$\displaystyle \deg p < n-k=3 $$, and $c(X) \equiv 0 \pmod{g(X)}$.

So $$\displaystyle m(X) + X^4 p(X) \equiv 0 \pmod{g(X)} \Rightarrow p(X) \equiv m(X) X^{-4} \pmod{g(X)} $$.

Since $$\displaystyle X^7 \equiv 1 \pmod{g(X)} $$, $$\displaystyle X^{-4} \equiv X^3 \equiv X+1 $$.

Thus $p(X) \equiv m(X)(X+1) \pmod{g(X)}$.

Let $$\displaystyle m(X) = m_0 + m_1 X + m_2 X^2 + m_3 X^3 $$. Compute:
$$\displaystyle p(X) = (X+1)m(X) \bmod g(X) $$

Reduction yields:

\begin{align*}

p_0 &= m_0 + m_2 + m_3 \

p_1 &= m_0 + m_1 + m_2 \

p_2 &= m_1 + m_2 + m_3

\end{align*}

Generator Matrix $G$ (systematic):

$$G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$$

Parity-Check Matrix $H$:

$$H = [P^T \mid I_3] = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$$

[!TIP]

Verification: $$\displaystyle G H^T = 0 $$. Syndrome $$\displaystyle s = r H^T $$.

VI. Convolutional Codes

6.1 Encoder Structure

• Parameters $(n,k,K)$:

  $n$: output bits per input symbol

  $k$: input bits per symbol (usually 1)

  $K$: constraint length (number of input bits affecting output)

• Example: $(2,1,3)$ code.

  • $$\displaystyle k=1 $$: single input bit $$\displaystyle u_t $$.

  • $$\displaystyle K=3 $$: output depends on $$\displaystyle u_t $$ and previous $$\displaystyle K-1=2 $$ bits.

  • Memory: 2 shift registers.

• Connection Polynomials:

  $$\displaystyle g_1(X) = 1 + X + X^2 $$

  $$\displaystyle g_2(X) = 1 + X^2 $$

  Outputs:

  $$\displaystyle v_t^{(1)} = u_t \oplus u_{t-1} \oplus u_{t-2} $$

  $$\displaystyle v_t^{(2)} = u_t \oplus u_{t-2} $$

6.2 Code Tree, Trellis, State Diagram

• State: Content of memory registers. For $(2,1,3)$, states = binary pairs $$\displaystyle (u_{t-1}, u_{t-2}) $$ → 4 states: $00, 01, 10, 11$.

• Code Tree: Shows all possible output sequences from start. Each branch labeled with input bit and output pair.

• Trellis: Unfolds tree over time; states reused. Shows transitions between states with input/output labels.

• State Diagram: Nodes = states, edges = transitions labeled $u/v$.

Example State Diagram for $(2,1,3)$:

From state $$\displaystyle S_{t-1}=(a,b) $$:

• Input 0: next state $(0,a)$, output $$\displaystyle g_1(0,a,b), g_2(0,a,b) $$.

• Input 1: next state $(1,a)$, output $$\displaystyle g_1(1,a,b), g_2(1,a,b) $$.

6.3 Viterbi Algorithm

• Principle: Maximum likelihood sequence decoding. Find path through trellis with minimum Hamming distance to received sequence.

• Procedure:

  1. Compute branch metrics (Hamming distance) for each transition at time $t$.

  2. Add to path metrics from previous states.

  3. For each state at time $t$, select survivor (path with smallest metric).

  4. Store survivor and its metric.

  5. After $N$ steps, trace back from state with smallest metric.

Example Decoding Trace:

Received: $$\displaystyle \mathbf{r} = (11, 10, 00, 11) $$

Initialize: metric(0, state 0) = 0, others = ∞.

At each time, compute metrics, select survivors. After 4 steps, trace back.

[!TIP]

Complexity: $$\displaystyle 2^k $$ states, $$\displaystyle 2^k $$ branches per time step. Survivor memory: store path metrics and pointers.

VII. Additional Topics (Short Notes)

7.1 Code Tree

• Represents all possible codewords from a convolutional encoder as a tree.

• Each node branches into $$\displaystyle 2^k $$ sub-nodes (for $k$ input bits).

• Branch labeled with output bits.

• Used for visualizing encoding and ML decoding (Viterbi is optimized trellis).

7.2 Viterbi Algorithm

• As above. Optimal ML decoding for convolutional codes.

• Path Metric: Cumulative Hamming distance.

• Survivor Selection: Keep one path per state.

• Traceback: Decode by following pointers back from final state.

7.3 Extended Huffman Coding

• Group $r$ source symbols into composite symbols.

• New alphabet size reduces, probabilities become $$\displaystyle p_i^r $$.

• Apply Huffman to new probabilities.

• Improves efficiency when original $$\displaystyle p_i $$ are not dyadic.

7.4 Lempel-Ziv Coding

• Dictionary-based, adaptive.

• No need for known probabilities.

• Used in file compression (ZIP, GIF).

• Parsing: longest previously seen phrase + new symbol.

END OF UNIT 1 NOTES
Aligns with EC-702(B) Nov 2023 paper. Focus on definitions, derivations, and numerical examples.