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

1. Information Theory Fundamentals

Channel Capacity

• Definition: The maximum rate at which information can be reliably transmitted over a communication channel, measured in bits per second (bps) or bits per channel use.

• Shannon’s Channel Capacity Theorem: For a band-limited channel with bandwidth $B$ Hz and signal-to-noise ratio $S/N$, the capacity is given by the Shannon-Hartley theorem:

$$C = B \log_2 \left(1 + \frac{S}{N}\right) \ \text{bps}$$

[!TIP]

Exam Focus: This formula is fundamental. Remember that capacity increases with bandwidth and SNR but is bounded by noise.

• Capacity of Channels with Infinite Bandwidth: As $B \to \infty$, the capacity approaches:

$$C = \frac{S}{N_0} \log_2 e \ \text{bps}$$

where $$\displaystyle N_0 $$ is noise power spectral density. This shows capacity is finite even with infinite bandwidth due to the wideband noise limit.

Binary Erasure Channel (BEC)

• Model: Input $X \in \{0,1\}$, output $Y \in \{0,1,e\}$ where $e$ denotes erasure. Probability of erasure is $$\displaystyle p_e $$; correct transmission probability is $$\displaystyle 1-p_e $$.

• Capacity Derivation:

  Mutual information $$\displaystyle I(X;Y) = H(X) - H(X|Y) $$. For BEC, $$\displaystyle H(X|Y) = p_e H(X) $$ because when $$\displaystyle Y=e $$, $X$ is uniformly uncertain.

  Maximizing over input distribution $P(X)$:

$$C = \max_{P(X)} [H(X) - p_e H(X)] = (1 - p_e) \cdot 1 = 1 - p_e \ \text{bits/channel use}$$

\boxed{C = 1 - p_e}

[!TIP]

Common Pitfall: BEC capacity is independent of input distribution because $H(X|Y)$ is linear in $H(X)$. Always derive from $$\displaystyle I(X;Y) = H(Y) - H(Y|X) $$ for verification.

2. Source Coding

Huffman Coding

• Construction (Minimum Variance):

  1. List symbols with probabilities in descending order.

  2. Combine two lowest-probability nodes into a new node with probability sum.

  3. Assign 0/1 to branches (typically 0 to left, 1 to right).

  4. Repeat until single root node.

  5. Minimum variance: At each step, combine the two lowest probability nodes to minimize weighted path length variance.

• Code Variance: $$\displaystyle \sigma^2 = \sum p_i (l_i - \bar{l})^2 $$, where $$\displaystyle \bar{l} = \sum p_i l_i $$ is average length.

• Efficiency: $$\displaystyle \eta = \frac{H(X)}{\bar{l}} \times 100\% $$, where $H(X)$ is entropy.

• Extended Huffman Coding: Group $r$ source symbols into composite symbols (blocks) before encoding.

  Advantages: Approaches entropy more closely; reduces variance; better for sources with skewed probabilities.

Lempel-Ziv Coding

• LZ77 (Sliding Window): Uses a buffer (dictionary) of recent symbols. Encoder searches buffer for longest match with incoming stream, outputs (offset, length) pair. Adaptive, no prior probability knowledge.

• LZ78 (Dictionary-Based): Builds explicit dictionary of phrases. Each new phrase is previous phrase + next symbol. Outputs dictionary index + new symbol.

• Principle: Exploit repeated sequences dynamically. Dictionary updated on-the-fly.

• Applications: ZIP, GZIP, PNG (LZ77 + Huffman), UNIX compress.

3. Channel Coding

Linear Block Codes

• Generator Matrix $\mathbf{G}$: $k \times n$ matrix; codeword $$\displaystyle \mathbf{c} = \mathbf{u} \mathbf{G} $$, where $\mathbf{u}$ is $k$-bit message.

• Parity-Check Matrix $\mathbf{H}$: $(n-k) \times n$ matrix; satisfies $$\displaystyle \mathbf{c} \mathbf{H}^T = \mathbf{0} $$. $\mathbf{G}$ and $\mathbf{H}$ related by $$\displaystyle \mathbf{G} \mathbf{H}^T = \mathbf{0} $$.

• Minimum Distance $$\displaystyle d_{\min} $$: Smallest Hamming distance between distinct codewords. Error correction capability: $$\displaystyle t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor $$.

• Example (6,3) Code:

  Given $$\displaystyle G = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} $$, generate all $$\displaystyle 2^3=8 $$ codewords by $\mathbf{u} \mathbf{G}$.

  Compute $$\displaystyle d_{\min} $$ by comparing all pairs. $H$ found from $$\displaystyle \mathbf{G} \mathbf{H}^T = \mathbf{0} $$.

Hamming Codes

• Design: $(n,k)$ with $$\displaystyle n = 2^m - 1 $$, $$\displaystyle k = n - m $$, $$\displaystyle d_{\min}=3 $$. $m$ parity bits.

• Parity-Check Matrix $\mathbf{H}$: Columns are all non-zero $m$-bit binary numbers (each column unique, non-zero).

• Syndrome Decoding: $$\displaystyle \mathbf{s} = \mathbf{r} \mathbf{H}^T $$. If $$\displaystyle \mathbf{s} = \mathbf{0} $$, no error; else $\mathbf{s}$ equals column of $\mathbf{H}$ indicating error position.

• Example for 4-bit message: $$\displaystyle m=3 $$ (since $$\displaystyle 2^3-1=7 \ge 4+3 $$), so $(7,4)$ Hamming code. $H$ has 7 columns of all 3-bit non-zero numbers.

Cyclic Codes

• Properties: Linear + cyclic shift property. If $\mathbf{c}$ is codeword, any cyclic shift is also codeword.

• Generator Polynomial $g(X)$: Degree $n-k$, divides $$\displaystyle X^n + 1 $$. Codeword polynomial $$\displaystyle c(X) = m(X) g(X) $$.

• Encoder Block Diagram: Shift register with feedback based on $g(X)$.

• Syndrome Calculator: Similar shift register; output is $$\displaystyle s(X) = r(X) \bmod g(X) $$.

• Systematic Form: $$\displaystyle \mathbf{G} = [I_k \mid P] $$, $$\displaystyle \mathbf{H} = [P^T \mid I_{n-k}] $$.

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

  • $$\displaystyle g(X) = X^3 + X + 1 $$ divides $$\displaystyle X^7+1 $$.

  • Encoder: 4-stage shift register with feedback from XOR of stages corresponding to terms in $g(X)$.

  • Systematic $\mathbf{G}, \mathbf{H}$ derived from polynomial division.

Convolutional Codes

• Encoder Structure: $k$ input bits, $n$ output bits per time unit. Constraint length $K$: number of input bits affecting current outputs. Code rate $$\displaystyle R = k/n $$.

• (2,1,3) Encoder: $$\displaystyle k=1 $$, $$\displaystyle n=2 $$, $$\displaystyle K=3 $$. Two output generators: $$\displaystyle g_1 = (1,1,1) $$, $$\displaystyle g_2 = (1,0,1) $$. Shift register of 2 memory elements (total $$\displaystyle K-1=2 $$).

• Transform Domain: Output sequences as generating functions: $$\displaystyle G_1(D) = 1 + D + D^2 $$, $$\displaystyle G_2(D) = 1 + D^2 $$.

• Diagrams:

  • State Diagram: $$\displaystyle 2^{K-1} $$ states (here 4 states). Branches labeled with input/output.

  • Tree Diagram: Expands all possible paths from root.

  • Trellis Diagram: Folded tree; states reused over time.

  [!TIP]

  Exam Tip: (2,1,3) is the most common example. Draw its state diagram (4 states: 00, 01, 10, 11) and trellis.

BCH Codes

• Introduction: Powerful cyclic codes correcting $t$ errors. Primitive polynomial $p(X)$ of degree $m$ generates field $$\displaystyle GF(2^m) $$. Code length $$\displaystyle n = 2^m - 1 $$.

• Design: Generator polynomial $g(X)$ is LCM of minimal polynomials of $$\displaystyle \alpha, \alpha^2, ..., \alpha^{2t} $$ (roots in $$\displaystyle GF(2^m) $$).

• Encoding: Systematic encoding via polynomial division.

• Decoding: Berlekamp-Massey algorithm or Euclidean algorithm to find error locator polynomial.

• Example: Design a $$\displaystyle t=1 $$ BCH code over $$\displaystyle GF(2^3) $$ ($$\displaystyle n=7 $$). Primitive polynomial $$\displaystyle p(X)=X^3+X+1 $$. Roots $$\displaystyle \alpha, \alpha^2 $$. $$\displaystyle g(X) = \text{LCM}(m_1(X), m_2(X)) = (X^3+X+1)(X^3+X^2+1) = X^6+X^5+X^4+X^3+X^2+X+1 $$? Actually for $$\displaystyle t=1 $$, $g(X)$ has roots $$\displaystyle \alpha, \alpha^2 $$, so minimal polynomials are both degree 3? Wait, check: For $$\displaystyle GF(2^3) $$, $\alpha$ has order 7. Minimal polynomial of $\alpha$ is $$\displaystyle X^3+X+1 $$; of $$\displaystyle \alpha^2 $$ is also $$\displaystyle X^3+X+1 $$? No, $$\displaystyle \alpha^2 $$ has same minimal polynomial if $\alpha$ is primitive. Actually for $$\displaystyle t=1 $$, we need roots $$\displaystyle \alpha, \alpha^2 $$, which are conjugates, so same minimal polynomial. Thus $$\displaystyle g(X) = X^3+X+1 $$? That gives (7,4) code, which is Hamming. For $$\displaystyle t=2 $$, need $$\displaystyle \alpha, \alpha^2, \alpha^3, \alpha^4 $$. Then $g(X)$ degree 6? Standard example: (15,7) BCH with $$\displaystyle t=2 $$. But exam may ask (7,4) as BCH? Actually (7,4) Hamming is a special BCH with $$\displaystyle t=1 $$. So clarify: For $$\displaystyle t=1 $$, BCH = Hamming. For $$\displaystyle t=2 $$, example (15,5) or (15,7). In exam, they might ask design procedure conceptually.

4. Decoding Algorithms

Code Tree

• Representation: Tree where each branch corresponds to an input bit and produces $n$ output bits (for rate $1/n$ convolutional code).

• Branch Labels: $(input/output)$ pairs.

• Path Enumeration: Each root-to-leaf path represents a possible input sequence and corresponding output codeword.

• Use: Visualizes all possible transmitted sequences; basis for Viterbi algorithm.

Viterbi Algorithm

• Principle: Maximum Likelihood (ML) decoding for convolutional codes. Finds path through trellis with minimum Hamming distance (or Euclidean for AWGN) to received sequence.

• Metric Calculation:

  • Hard decision: Hamming distance (additive).

  • Soft decision: Euclidean distance (squared).

• Path Memory & Traceback Depth:

  • Survivor paths: At each time, keep only one path per state (the one with best metric).

  • Traceback depth $D$: Must be $\ge 5K$ for near-ML performance. Typically $D \approx 5K$ to $10K$.

• Applications: Convolutional codes, Turbo codes (as component decoder).

[!TIP]

Exam Focus: Always draw trellis for (2,1,3) code and show Viterbi steps for a short received sequence. Know survivor selection and traceback.

Final Note: This unit is calculation-heavy. Practice derivations (BEC capacity, Huffman variance, generator/parity matrices) and diagram drawing (encoder, trellis, state diagram) from past paper examples.