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

UNIT 3: INFORMATION THEORY AND CODING

I. FUNDAMENTALS OF INFORMATION THEORY

A. Core Concepts & Measures

• Uncertainty: The amount of unpredictability in the outcome of a random variable. Higher uncertainty means less prior knowledge.

• Self-Information (Surprisal): Information content of a specific message $$\displaystyle x_i $$ with probability $$\displaystyle p_i $$.

$$I(x_i) = \log_2 \left( \frac{1}{p_i} \right) = -\log_2 p_i \ \text{bits}$$

*Rare events (low $$\displaystyle p_i $$) carry more information.*

• Entropy $H(X)$: Average uncertainty/information of a discrete source $X$ with $M$ messages.

$$H(X) = \mathbb{E}[I(X)] = -\sum_{i=1}^{M} p_i \log_2 p_i \ \text{bits/symbol}$$

*Measures the **minimum average code length** required for lossless compression.*

• Joint Entropy $H(X,Y)$: Uncertainty of two random variables $(X,Y)$.

$$H(X,Y) = -\sum_{i,j} p(x_i, y_j) \log_2 p(x_i, y_j)$$

• Conditional Entropy $H(Y|X)$: Average uncertainty remaining in $Y$ given $X$.

$$H(Y|X) = -\sum_{i,j} p(x_i, y_j) \log_2 p(y_j|x_i) = H(X,Y) - H(X)$$

• Mutual Information $I(X;Y)$: Amount of information shared between $X$ and $Y$. Reduction in uncertainty of one variable due to the other.

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

> [!IMPORTANT] **Key Property**: $$\displaystyle I(X;Y) = I(Y;X) \geq 0 $$. It is zero iff $X$ and $Y$ are independent.

B. Key Proofs & Derivations

[!TIP] Exam Focus: These are 7-mark questions. Show all steps clearly.

1. Proof: Entropy is maximum for equiprobable messages (M=3)

   • Let $X$ have 3 outcomes with probabilities $$\displaystyle p_1, p_2, p_3 $$ where $$\displaystyle p_1+p_2+p_3=1 $$.

   • To maximize $$\displaystyle H(X) = -\sum_{i=1}^{3} p_i \log_2 p_i $$ subject to $$\displaystyle \sum p_i = 1 $$.

   • Use Lagrange multipliers or Jensen's inequality (since $-\log$ is convex).

   • Jensen's Approach:

     For a convex function $$\displaystyle f(u) = -u \log_2 u $$, by Jensen:

$$\frac{1}{3}\sum f(p_i) \geq f\left(\frac{1}{3}\sum p_i\right) = f\left(\frac{1}{3}\right)$$

$$\Rightarrow \sum -p_i \log_2 p_i \geq 3 \cdot \left(-\frac{1}{3}\log_2 \frac{1}{3}\right) = \log_2 3$$

    Equality holds iff $$\displaystyle p_1 = p_2 = p_3 = \frac{1}{3} $$.

\boxed{H_{\text{max}} = \log_2 M \ \text{bits/symbol}}

2. Proof of Mutual Information Identities

   • First Identity: $$\displaystyle I(X;Y) = H(X) + H(Y) - H(X,Y) $$

     \begin{align*}

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

     &= H(X) - [H(X,Y) - H(Y)] \quad \text{(from } H(X,Y)=H(X)+H(Y|X)\text{)} \

     &= H(X) + H(Y) - H(X,Y)

     \end{align*}

   • Second Identity: $$\displaystyle I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) $$

     Direct from definition: $$\displaystyle I(X;Y) = H(X) - H(X|Y) $$.

     Symmetry: $$\displaystyle I(X;Y) = H(Y) - H(Y|X) $$ follows from first identity and $$\displaystyle H(X,Y)=H(Y,X) $$.

   [!CAUTION] Common Pitfall: Do not confuse $H(X,Y)$ with $H(X|Y)$. Joint entropy is for both variables; conditional is for one given the other.

II. SOURCE CODING (DATA COMPRESSION)

A. Variable-Length Codes: Huffman Coding

• Goal: Minimize average code length $$\displaystyle L_{avg} = \sum p_i l_i $$ subject to Kraft's inequality $$\displaystyle \sum 2^{-l_i} \leq 1 $$.

• Algorithm (Min-Variance):

  1. Sort probabilities in descending order.

  2. Combine two smallest probabilities into a new node.

  3. Assign 0/1 to branches (convention: left=0, right=1).

  4. Repeat until single node remains.

  5. For minimum variance: When combining nodes of equal probability, combine the deeper (longer) codewords first.

• Code Efficiency: $$\displaystyle \eta = \frac{H(X)}{L_{avg}} \times 100\% $$

• Code Variance: $$\displaystyle \sigma^2 = \sum p_i (l_i - L_{avg})^2 $$ (measures deviation from average length).

• Code Tree: Binary tree representation. Path from root to leaf gives codeword.

  DiagramSEARCH: Huffman coding tree construction example

B. Advanced Source Coding Techniques

1. Arithmetic Coding

   • Represents entire message as a single fractional number in [0,1).

   • Interval for each symbol $[L, H)$ is subdivided proportional to symbol probabilities.

   • Example (for symbols A:0.5, B:0.3, C:0.2, message "BAC"):

     • Start: [0, 1)

     • B: [0, 0.3) → subdivide: A: [0, 0.15), B: [0.15, 0.24), C: [0.24, 0.3)

     • A: [0.15, 0.24) → subdivide: A: [0.15, 0.195), B: [0.195, 0.213), C: [0.213, 0.24)

     • C: [0.213, 0.24) → final interval. Any number in this interval (e.g., 0.22) encodes "BAC".

   • Advantage: Near-entropy performance, no integer bit constraint.

2. Lempel-Ziv (LZ) Coding (Dictionary-Based)

   • Adaptive, universal compression. No prior probability knowledge needed.

   • LZ77: Uses a sliding window. Encodes as (offset, length) pairs for repeated strings.

   • LZ78: Builds a dictionary of phrases dynamically. Each new phrase = previous phrase + new symbol.

   • Example (LZ78): Input "ABABABC"

     • A → (0, 'A') → dict[1]="A"

     • B → (0, 'B') → dict[2]="B"

     • AB → (1, 'B') → dict[3]="AB"

     • A → (0, 'A') (already in dict)

     • BC → (2, 'C') → dict[4]="BC"

     • Output: (0,A)(0,B)(1,B)(0,A)(2,C)

III. CHANNEL MODELS & CAPACITY

A. Discrete Memoryless Channels (DMC)

1. Binary Symmetric Channel (BSC)

   • Model: Input $X \in \{0,1\}$, Output $Y \in \{0,1\}$.

   • Crossover probability $p$: $$\displaystyle P(Y=1|X=0) = P(Y=0|X=1) = p $$.

   • Channel Efficiency $\eta$: Ratio of achieved rate to capacity.

$$\eta = \frac{R}{C} \ \text{where } R = \frac{H(X)}{T} \ \text{bits/sec}$$

*   **Capacity** $C$: Maximum reliable information rate.

$$C = 1 - H_b(p) \ \text{bits/channel use}$$

    where $$\displaystyle H_b(p) = -p\log_2 p - (1-p)\log_2(1-p) $$ is binary entropy.

2. Binary Erasure Channel (BEC)

   • Model: Input $X \in \{0,1\}$, Output $Y \in \{0,1,\text{e}\}$ where 'e' = erasure.

   • Erasure probability $\epsilon$: $$\displaystyle P(Y=\text{e}|X=0) = P(Y=\text{e}|X=1) = \epsilon $$.

   • Capacity Derivation:

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

     $H(X|Y)$: If $$\displaystyle Y=0 $$ or $1$, $X$ is known (0 entropy). If $$\displaystyle Y=\text{e} $$, $X$ is uniform (entropy $H(X)$).

$$H(X|Y) = \epsilon H(X)$$

$$\Rightarrow I(X;Y) = H(X) - \epsilon H(X) = (1-\epsilon)H(X)$$

    Maximize over input distribution $P(X)$: max $$\displaystyle H(X)=1 $$ (equiprobable).

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

B. Channel Capacity Theorem

• Shannon's Channel Capacity Theorem: For a DMC with capacity $C$, reliable transmission (arbitrarily low error) is possible for any rate $$\displaystyle R < C $$, and impossible for $$\displaystyle R > C $$.

• Capacity with Infinite Bandwidth:

  • For AWGN channel: $$\displaystyle C = B \log_2(1 + \text{SNR}) $$.

  • As $B \to \infty$, $\text{SNR} \to 0$ but $$\displaystyle B \cdot \log_2(1+\text{SNR}) $$ approaches a limit.

  • Result: $$\displaystyle \lim_{B\to\infty} C = 1.44 \cdot \frac{P}{N_0} \ \text{bits/sec} $$, where $P$ = signal power, $$\displaystyle N_0 $$ = noise spectral density.

  • Interpretation: Even with infinite bandwidth, capacity is finite and linear in $$\displaystyle P/N_0 $$.

IV. LINEAR BLOCK CODES

A. Fundamentals & Matrices

• Parameters: $(n, k)$ code: $k$ info bits → $n$ code bits, rate $$\displaystyle R = k/n $$.

• Generator Matrix $\mathbf{G}$: $k \times n$ matrix. Code vector $$\displaystyle \mathbf{c} = \mathbf{u} \mathbf{G} $$, where $\mathbf{u}$ is info vector.

• Parity-Check Matrix $\mathbf{H}$: $(n-k) \times n$ matrix. Satisfies $$\displaystyle \mathbf{c} \mathbf{H}^T = \mathbf{0} $$ for all valid $\mathbf{c}$.

• Systematic Form: $$\displaystyle \mathbf{G} = [\mathbf{I}_k | \mathbf{P}] $$, then $$\displaystyle \mathbf{H} = [-\mathbf{P}^T | \mathbf{I}_{n-k}] $$ (or $$\displaystyle [\mathbf{P}^T | \mathbf{I}] $$ over GF(2)).

• Code Vector Enumeration: All $$\displaystyle 2^k $$ possible $\mathbf{u}$ give $$\displaystyle 2^k $$ distinct $\mathbf{c}$.

B. Specific Code Designs

1. $(6,3)$ Linear Block Code Example

   Given: $$\displaystyle \mathbf{G} = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} $$ (systematic).

   • Code vectors: $$\displaystyle \mathbf{c} = \mathbf{u} \mathbf{G} $$ for all $\mathbf{u} \in \{000, 001, ..., 111\}$.

   • Results:

     $$\displaystyle \begin{array}{c|c} \mathbf{u} & \mathbf{c} \\ \hline 000 & 000000 \\ 001 & 001111 \\ 010 & 010011 \\ 011 & 011100 \\ 100 & 100110 \\ 101 & 101101 \\ 110 & 110010 \\ 111 & 111001 \end{array} $$

2. Hamming Codes

   • Design Principle: Single-error-correcting ($$\displaystyle t=1 $$) → $$\displaystyle d_{\min} \geq 3 $$.

   • Parity-Check Matrix $\mathbf{H}$: All non-zero columns of length $m$ (where $$\displaystyle n=2^m-1 $$, $$\displaystyle k=n-m $$). Each column is a unique binary number (1 to $n$).

   • Syndrome: $$\displaystyle \mathbf{s} = \mathbf{r} \mathbf{H}^T $$. If $$\displaystyle \mathbf{s} = \mathbf{0} $$ → no error. If $\mathbf{s} \neq \mathbf{0}$ → its value (1 to $n$) indicates error position.

   • Example for $$\displaystyle k=4 $$:

     • $$\displaystyle m=3 $$ (since $$\displaystyle 2^3-1=7 \geq 4+3 $$).

     • $$\displaystyle n = 2^m - 1 = 7 $$, $$\displaystyle k = n-m = 4 $$.

     • $\mathbf{H}$ columns: all non-zero 3-bit numbers: 001, 010, 011, 100, 101, 110, 111.

     \begin{bmatrix}

     1 & 0 & 1 & 0 & 1 & 0 & 1 \

     0 & 1 & 1 & 0 & 0 & 1 & 1 \

     0 & 0 & 0 & 1 & 1 & 1 & 1

     \end{bmatrix}

     • $\mathbf{G}$ derived from $\mathbf{H}$: $$\displaystyle \mathbf{G} = [\mathbf{I}_4 | \mathbf{P}] $$ where $\mathbf{P}$ from $\mathbf{H}$'s non-identity columns.

V. CYCLIC CODES

A. Algebraic Structure

• Definition: A linear block code where any cyclic shift of a code polynomial is also a code polynomial.

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

• Generator Polynomial $g(X)$: A divisor of $$\displaystyle X^n - 1 $$. Degree $$\displaystyle r = n-k $$. All code polynomials are multiples of $g(X)$: $$\displaystyle c(X) = m(X) g(X) $$ where $m(X)$ is message polynomial of degree $$\displaystyle <k $$.

• Cyclic Shift Property: If $c(X)$ is a code polynomial, then $$\displaystyle X \cdot c(X) \mod (X^n - 1) $$ is also a code polynomial.

B. Encoding & Decoding Circuits

• Encoder Block Diagram:

  DiagramCANVAS: Shift register encoder for cyclic code. Input message bits feed into a shift register of length $n-k$ (degree of $g(X)$). Feedback connections from output to input via XOR gates according to the coefficients of $g(X)$. After $k$ message shifts, $n$ code bits are output.

• Syndrome Calculator Block Diagram:

  • Same circuit as encoder but with input disconnected (or set to zero).

  • Received polynomial $r(X)$ is shifted in.

  • After $n$ shifts, register content = syndrome $$\displaystyle s(X) = r(X) \mod g(X) $$.

  DiagramSEARCH: cyclic code syndrome calculator circuit

C. Matrix Forms

Given $$\displaystyle g(X) = X^3 + X + 1 $$ for $(7,4)$ code ($$\displaystyle n=7, k=4, r=3 $$):

1. Systematic Generator Matrix $$\displaystyle \mathbf{G} = [\mathbf{I}_k | \mathbf{P}] $$:

   • $$\displaystyle c(X) = m(X) X^r + p(X) $$ where $$\displaystyle p(X) = m(X) X^r \mod g(X) $$.

   • For $$\displaystyle m(X) = m_0 + m_1 X + m_2 X^2 + m_3 X^3 $$:

     $$\displaystyle m(X) X^3 = m_0 X^3 + m_1 X^4 + m_2 X^5 + m_3 X^6 $$.

     Divide by $$\displaystyle g(X)=X^3+X+1 $$ to get remainder $p(X)$.

   • Result: $$\displaystyle \mathbf{P} = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} $$

   \boxed{\mathbf{G} = \left[ \begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array} \right]}

2. Systematic Parity-Check Matrix $$\displaystyle \mathbf{H} = [\mathbf{P}^T | \mathbf{I}_r] $$:

   \boxed{\mathbf{H} = \left[ \begin{array}{cccc|ccc} 1 & 1 & 1 & 0 & 1 & 0 & 0 \ 0 & 1 & 1 & 1 & 0 & 1 & 0 \ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right]}

D. Decoding Procedure

1. Compute syndrome $$\displaystyle \mathbf{s} = \mathbf{r} \mathbf{H}^T $$.

2. If $$\displaystyle \mathbf{s} = \mathbf{0} $$ → assume no error (or detect if $$\displaystyle d_{\min}>1 $$).

3. If $\mathbf{s} \neq \mathbf{0}$ → look up syndrome table (precomputed mapping $\mathbf{s} \to$ error pattern $\mathbf{e}$).

4. Correct: $$\displaystyle \hat{\mathbf{c}} = \mathbf{r} + \mathbf{e} $$ (mod 2).

5. Extract message bits (first $k$ bits for systematic code).

VI. CONVOLUTIONAL CODES

A. Encoder Structure

• Representation: $(n, k, m)$

  • $n$: output bits per input bit.

  • $k$: input bits per time unit.

  • $m$: constraint length (number of shift register stages).

  • Code rate $$\displaystyle R = k/n $$.

• Transform Domain Approach:

  • Encoder outputs are linear combinations of current and past inputs.

  • Represented by generator polynomials $$\displaystyle \mathbf{G}(D) = [g_1(D), g_2(D), ..., g_n(D)] $$ where $D$ is delay operator.

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

    • $$\displaystyle k=1 $$, $$\displaystyle n=2 $$, $$\displaystyle m=3 $$ (3 shift registers).

    • Output 1: $$\displaystyle u_t \oplus u_{t-1} \oplus u_{t-2} $$ → $$\displaystyle g_1(D) = 1 + D + D^2 $$.

    • Output 2: $$\displaystyle u_t \oplus u_{t-2} $$ → $$\displaystyle g_2(D) = 1 + D^2 $$.

    \boxed{\mathbf{G}(D) = \left[ 1+D+D^2 \quad , \quad 1+D^2 \right]}

B. Decoding Algorithms

1. Viterbi Algorithm (Maximum Likelihood Sequence Estimation - MLSE)

   • Principle: Find the most likely path through the trellis (sequence of states) given received sequence.

   • Metrics:

     • Branch Metric: Hamming distance between received bits and expected bits for that branch.

     • Path Metric: Cumulative sum of branch metrics along a path.

   • Procedure:

     1. Initialize: Start at state 0 with metric 0.

     2. For each time step, compute add-compare-select (ACS):

        • For each state, consider all incoming branches.

        • Add branch metric to survivor path metric from previous state.

        • Select the path with maximum metric (or minimum Hamming distance) as the survivor.

     3. Store survivor path and metric for each state.

     4. After receiving all bits, trace back from state with best metric (usually after traceback depth $$\displaystyle = 5m $$ to $7m$).

   • Output: Most likely transmitted information sequence.

VII. BCH CODES

A. Theory & Construction

• Principles:

  • t-error-correcting capability.

  • Designed distance $$\displaystyle \delta = 2t+1 $$.

  • Generator polynomial $g(X)$: LCM of minimal polynomials of $$\displaystyle \alpha, \alpha^2, ..., \alpha^{\delta-1} $$ where $\alpha$ is a primitive element in $$\displaystyle GF(2^m) $$.

  • Parameters: $$\displaystyle n = 2^m - 1 $$ (or divisor thereof), $k \geq n - m t$, $$\displaystyle d_{\min} \geq \delta $$.

• Construction Steps:

  1. Choose $m$ (determines $$\displaystyle n=2^m-1 $$).

  2. Choose $t$ (error-correcting capability).

  3. Find minimal polynomials $$\displaystyle M_i(X) $$ for $$\displaystyle \alpha^i $$, $$\displaystyle i=1,2,...,2t $$.

  4. $$\displaystyle g(X) = \text{LCM}[M_1(X), M_2(X), ..., M_{2t}(X)] $$.

  5. $$\displaystyle k = n - \deg(g(X)) $$.

B. Example-Based Design

• Example: Design a t=1, n=7 BCH code over $GF(2)$.

  1. $$\displaystyle n=7 = 2^3-1 $$ → $$\displaystyle m=3 $$. Field: $$\displaystyle GF(2^3) $$ with primitive polynomial $$\displaystyle p(X)=X^3+X+1 $$. Root $\alpha$.

  2. $$\displaystyle t=1 $$ → $$\displaystyle \delta=3 $$ → need minimal polynomials for $\alpha$ and $$\displaystyle \alpha^2 $$.

  3. Minimal Polynomials:

     • $$\displaystyle M_1(X) $$: roots $$\displaystyle \alpha, \alpha^2, \alpha^4 $$ → $$\displaystyle M_1(X) = (X-\alpha)(X-\alpha^2)(X-\alpha^4) = X^3 + X + 1 $$.

     • $$\displaystyle M_2(X) $$: roots $$\displaystyle \alpha^2, \alpha^4, \alpha $$ (same set!) → $$\displaystyle M_2(X) = X^3 + X + 1 $$.

     • Actually, for $$\displaystyle GF(2^3) $$, $$\displaystyle \alpha, \alpha^2, \alpha^4 $$ are conjugates; $$\displaystyle \alpha^3, \alpha^5, \alpha^6 $$ are another set.

     • For $$\displaystyle \delta=3 $$, we need $$\displaystyle M_1(X) $$ and $$\displaystyle M_2(X) $$. Since $$\displaystyle \alpha^2 $$ is in same cyclotomic class as $\alpha$, $$\displaystyle M_1(X)=M_2(X) $$.

  4. $$\displaystyle g(X) = \text{LCM}[M_1(X), M_2(X)] = M_1(X) = X^3 + X + 1 $$.

  5. $$\displaystyle \deg(g)=3 $$ → $$\displaystyle k = n - 3 = 4 $$.

  6. Result: This is exactly the $(7,4)$ Hamming code (special case of BCH with $$\displaystyle t=1 $$).

  \boxed{g(X) = X^3 + X + 1, \quad (n,k) = (7,4), \quad t=1}

VIII. PRACTICAL APPLICATIONS & SHORT NOTES

A. Information Theory Applications (From Exam)

1. Morse Code Information Content:

   • Dot: duration 1 unit, Dash: duration 3 units.

   • Given: $$\displaystyle P(\text{dash}) = \frac{1}{2} P(\text{dot}) $$, and $$\displaystyle P(\text{dot}) + P(\text{dash}) = 1 $$.

   • Solve: $$\displaystyle P_d + \frac{1}{2}P_d = 1 \Rightarrow P_d = \frac{2}{3} $$, $$\displaystyle P_D = \frac{1}{3} $$.

   • Information content:

     $$\displaystyle I(\text{dot}) = -\log_2(2/3) = \log_2(3/2) \approx 0.585 $$ bits.

     $$\displaystyle I(\text{dash}) = -\log_2(1/3) = \log_2 3 \approx 1.585 $$ bits.

   \boxed{I_{\text{dot}} = \log_2 \frac{3}{2} \ \text{bits}, \quad I_{\text{dash}} = \log_2 3 \ \text{bits}}

   • Average Information (Entropy of symbol source):

     $$\displaystyle H = P_d I_d + P_D I_D = \frac{2}{3}\log_2\frac{3}{2} + \frac{1}{3}\log_2 3 = \frac{2}{3}(\log_2 3 - 1) + \frac{1}{3}\log_2 3 = \log_2 3 - \frac{2}{3} \approx 1.585 - 0.667 = 0.918 $$ bits/symbol.

   • Average Rate:

     • Dot duration = 1 ms, pause between symbols = 1 ms → total time per symbol = 2 ms for dot, 4 ms for dash? (Clarify: "dot lasts 1 m sec, which is the same time interval as the pause between symbols" → each symbol (dot or dash) is followed by a pause of 1 ms. So dot: 1 ms signal + 1 ms pause = 2 ms; dash: 3 ms signal + 1 ms pause = 4 ms).

     • Average time per symbol: $$\displaystyle T_{avg} = P_d \cdot 2 + P_D \cdot 4 = \frac{2}{3}\cdot 2 + \frac{1}{3}\cdot 4 = \frac{4}{3} + \frac{4}{3} = \frac{8}{3} $$ ms.

     • Information rate $$\displaystyle R = \frac{H}{T_{avg}} = \frac{0.918 \ \text{bits}}{8/3 \ \text{ms}} = 0.918 \times \frac{3}{8} \times 1000 \approx 344.25 $$ bits/sec.

     \boxed{R \approx 344 \ \text{bits/sec}}

B. Coding Scheme Comparisons & Applications

[!TIP] Short Notes from Exam: Be ready to write concise (1-page) notes on:

• Lempel-Ziv Coding: Dictionary-based, adaptive, used in ZIP/GZIP.

• Code Tree: Huffman tree representation, path = codeword.

• Viterbi Algorithm: MLSE for convolutional codes, trellis-based, ACS operation.

• Extended Huffman Coding: Allows codeword lengths to be non-integer via compound Huffman or package merging. Improves efficiency closer to entropy.

SUMMARY OF CRITICAL FORMULAS