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

UNIT 4: INFORMATION THEORY AND CODING

1. FUNDAMENTALS OF INFORMATION THEORY

1.1 Uncertainty, Self-Information, and Entropy

• Uncertainty quantifies unpredictability of a random variable's outcome.

• Self-Information of an event $$\displaystyle x_i $$ with probability $$\displaystyle p(x_i) $$:

$$i(x_i) = -\log_b p(x_i)$$

Units: bits for $$\displaystyle b=2 $$, nats for $$\displaystyle b=e $$.

• Entropy $H(X)$: average self-information of discrete random variable $X$ with $M$ outcomes:

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

Measures average uncertainty per message.

1.2 Properties of Entropy

1.3 Maximum Entropy Principle (Proof for M=3)

Goal: Maximize $$\displaystyle H(p_1,p_2,p_3) = -\sum_{i=1}^{3} p_i \log p_i $$ subject to $$\displaystyle \sum p_i = 1 $$, $$\displaystyle p_i \geq 0 $$.

Use Lagrange multipliers:

$$\mathcal{L} = -\sum p_i \log p_i + \lambda \left(1 - \sum p_i\right)$$

Set $$\displaystyle \frac{\partial \mathcal{L}}{\partial p_i} = 0 $$:

$$-(\log p_i + 1) - \lambda = 0 \Rightarrow p_i = e^{-(1+\lambda)}$$

All $$\displaystyle p_i $$ equal → $$\displaystyle p_i = 1/3 $$.

Second derivative test confirms maximum.

[!TIP] For $M$ equiprobable messages: $$\displaystyle H_{\max} = \log_2 M $$ bits.

1.4 Joint, Conditional, and Marginal Entropy

• Joint Entropy $H(X,Y)$: uncertainty of pair $(X,Y)$.

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

• Conditional Entropy $H(Y|X)$: average uncertainty of $Y$ given $X$.

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

• Marginal Entropy $H(X)$ from joint: $$\displaystyle H(X) = -\sum_i p(x_i) \log p(x_i) $$.

1.5 Mutual Information

Definition: $I(X;Y)$ = reduction in uncertainty of $X$ due to $Y$.

$$I(X;Y) = \sum_{i,j} p(x_i,y_j) \log \frac{p(x_i,y_j)}{p(x_i)p(y_j)}$$

1.5.1 Proof: $$\displaystyle I(X;Y) = H(X) + H(Y) - H(X,Y) $$

\begin{align*}

I(X;Y) &= \sum p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \

&= \sum p(x,y) \log p(x,y) - \sum p(x,y) \log p(x) - \sum p(x,y) \log p(y) \

&= -H(X,Y) - \left(-\sum_x p(x) \log p(x)\right) - \left(-\sum_y p(y) \log p(y)\right) \

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

\end{align*}

1.5.2 Proof: $$\displaystyle I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) $$

\begin{align*}

H(X) - H(X|Y) &= -\sum_x p(x) \log p(x) + \sum_{x,y} p(x,y) \log p(x|y) \

&= \sum_{x,y} p(x,y) \log \frac{p(x|y)}{p(x)} \

&= \sum_{x,y} p(x,y) \log \frac{p(x,y)/p(y)}{p(x)} \

&= \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} = I(X;Y)

\end{align*}

Similarly, $$\displaystyle H(Y) - H(Y|X) = I(X;Y) $$.

1.6 Source Coding Theorem (Noiseless Coding Theorem)

• Statement: For a discrete memoryless source with entropy $H$, the average code word length $\bar{L}$ per symbol satisfies:

$$H \leq \bar{L} < H + 1$$

for any uniquely decodable code.

• Implication: Entropy is the fundamental limit of lossless compression. Codes approaching $H$ exist (e.g., Huffman, arithmetic).

2. SOURCE CODING TECHNIQUES (LOSSLESS COMPRESSION)

2.1 Huffman Coding

2.1.1 Algorithm and Construction Procedure

1. List probabilities $$\displaystyle p_i $$ in descending order.

2. Combine two smallest probabilities into a node; repeat until one node remains.

3. Assign 0/1 to branches (left/right) from bottom up.

4. Code word = path from root to leaf.

[!TIP] Minimum variance variant: when combining nodes, choose the one with smallest number of leaves if probabilities equal.

2.1.2 Code Variance and Code Efficiency

• Average Length: $$\displaystyle \bar{L} = \sum p_i l_i $$

• Code Variance: $$\displaystyle \sigma^2 = \sum p_i (l_i - \bar{L})^2 $$ (measures length spread).

• Efficiency: $$\displaystyle \eta = \frac{H}{\bar{L}} \times 100\% $$

• Redundancy: $1 - \eta$.

2.1.3 Extended Huffman Coding

• Group $r$ source symbols into composite symbols.

• Used when alphabet size not power of 2; reduces variance.

• Example: For 5 symbols, use $$\displaystyle r=2 $$ → 25 composite symbols (some impossible).

2.2 Arithmetic Coding

2.2.1 Principle and Interval Partitioning

• Map message sequence to a fractional interval $[0,1)$.

• Start with $$\displaystyle [L_0, H_0) = [0,1) $$.

• For each symbol $$\displaystyle s_i $$ with cumulative probability $$\displaystyle C(s_i) $$ and range $$\displaystyle p(s_i) $$:

$$L_i = L_{i-1} + (H_{i-1} - L_{i-1}) \cdot C(s_i)$$

$$H_i = L_{i-1} + (H_{i-1} - L_{i-1}) \cdot (C(s_i) + p(s_i))$$

• Final interval uniquely identifies sequence.

2.2.2 Example with Given Probabilities

Let $$\displaystyle P(A)=0.4, P(B)=0.3, P(C)=0.2, P(D)=0.1 $$. Encode "BAD":

1. Initial: $[0,1)$

2. 'B': $$\displaystyle C(B)=0.4 $$, $$\displaystyle p(B)=0.3 $$ → $[0.4, 0.7)$

3. 'A': $$\displaystyle C(A)=0 $$, $$\displaystyle p(A)=0.4 $$ → $$\displaystyle [0.4 + 0.3\cdot0, 0.4 + 0.3\cdot0.4) = [0.4, 0.52) $$

4. 'D': $$\displaystyle C(D)=0.9 $$, $$\displaystyle p(D)=0.1 $$ → $$\displaystyle [0.4 + 0.12\cdot0.9, 0.4 + 0.12\cdot1.0) = [0.508, 0.52) $$

Any number in $[0.508, 0.52)$ (e.g., 0.51) represents "BAD".

[!TIP] Arithmetic coding often outperforms Huffman because it uses fractional bits and doesn't require integer-length codes.

2.3 Lempel-Ziv Coding

2.3.1 LZ77 and LZ78 Algorithms

• LZ77 (Sliding Window):

  • Maintains a window of recent $N$ symbols.

  • Finds longest match in window; outputs $(distance, length)$.

  • Example: "ABABCBABAB" → (0,A), (0,B), (2,2), (0,C), (3,3), ...

• LZ78 (Dictionary-Based):

  • Builds dictionary of phrases.

  • New phrase = previous phrase + next symbol.

  • Outputs (dictionary index, new symbol).

  • Example: "ABABCBABAB" → (0,A), (0,B), (1,A), (0,C), (2,B), ...

2.3.2 Applications and Adaptive Nature

• Applications: ZIP, GIF (LZ78 variant), DEFLATE (LZ77 + Huffman).

• Adaptive: No prior probability needed; builds model on the fly.

• Universal: Works for any source; efficiency approaches entropy for long sequences.

3. CHANNEL MODELS AND CAPACITY

3.1 Binary Symmetric Channel (BSC)

3.1.1 Model Description

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

• Crossover probability $p$: $$\displaystyle P(Y \neq X) = p $$.

• Transition matrix:

$$ \begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix} $$

3.1.2 Capacity Calculation

$$C = \max_{p(x)} I(X;Y) = 1 - H_b(p)$$

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

Achieved when $$\displaystyle p(0)=p(1)=0.5 $$.

3.1.3 Efficiency of Codes for BSC

• Code efficiency $$\displaystyle \eta = \frac{k}{n} $$ for $(n,k)$ block code.

• Reliable communication requires $\eta \leq C$ (Shannon limit).

3.2 Binary Erasure Channel (BEC)

3.2.1 Model Description

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

• Erasure probability $\epsilon$: $$\displaystyle P(Y=e) = \epsilon $$.

• If not erased, $$\displaystyle Y=X $$ with probability $1-\epsilon$.

3.2.2 Capacity Derivation

$$C = (1-\epsilon) \cdot 1 = 1 - \epsilon$$

Because when not erased, $Y$ reveals $X$ perfectly; only $\epsilon$ fraction lost.

[!TIP] BSC capacity symmetric about $$\displaystyle p=0.5 $$; BEC capacity decreases linearly with $\epsilon$.

3.3 Channel Capacity Theorems

3.3.1 Shannon-Hartley Theorem (Bandwidth-Limited)

For AWGN channel with bandwidth $B$ Hz and SNR $S/N$:

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

Assumes infinite-dimensional signaling (continuous amplitude).

3.3.2 Capacity with Infinite Bandwidth (Power-Limited)

As $B \to \infty$, capacity becomes:

$$C = \frac{S}{N_0} \log_2 e \approx 1.44 \frac{S}{N_0}$$

where $$\displaystyle N_0 = N/B $$ (noise spectral density).

Limited by power, not bandwidth.

4. LINEAR BLOCK CODES

4.1 Generator Matrix $G$ and Parity-Check Matrix $H$

• Generator Matrix $$\displaystyle G_{k \times n} $$: maps $k$-bit message $\mathbf{u}$ to codeword $$\displaystyle \mathbf{c} = \mathbf{u} G $$.

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

• Relationship: $$\displaystyle G H^T = 0 $$.

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

4.2 Hamming Codes

4.2.1 Design for Single-Error Correction ($$\displaystyle d_{\min}=3 $$)

• Condition: $$\displaystyle n = 2^m - 1 $$, $$\displaystyle k = n - m $$, $$\displaystyle d_{\min}=3 $$.

• $m$ parity bits; can correct 1 error or detect 2 errors.

• Parity-check matrix $H$: all non-zero $m$-bit columns (each column = binary representation of position 1 to $n$).

4.2.2 Construction for $$\displaystyle k=4 $$ (e.g., (7,4) Hamming)

• $$\displaystyle m=3 $$ → $$\displaystyle n=7 $$, $$\displaystyle k=4 $$.

• $H$ columns = binary numbers 1 to 7:

$$ H = \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} $$

• Syndrome $$\displaystyle \mathbf{s} = \mathbf{r} H^T $$ gives error position (binary value of $\mathbf{s}$).

4.3 Example: (6,3) Block Code from Given Generator Matrix

Given:

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

4.3.1 Listing All Code Vectors

Messages $$\displaystyle \mathbf{u} = (u_1,u_2,u_3) $$ (8 possibilities):

• $$\displaystyle \mathbf{u}=000 $$ → $$\displaystyle \mathbf{c}=000000 $$

• $$\displaystyle \mathbf{u}=001 $$ → $$\displaystyle \mathbf{c}=001111 $$

• $$\displaystyle \mathbf{u}=010 $$ → $$\displaystyle \mathbf{c}=010011 $$

• $$\displaystyle \mathbf{u}=011 $$ → $$\displaystyle \mathbf{c}=011100 $$

• $$\displaystyle \mathbf{u}=100 $$ → $$\displaystyle \mathbf{c}=100110 $$

• $$\displaystyle \mathbf{u}=101 $$ → $$\displaystyle \mathbf{c}=101101 $$

• $$\displaystyle \mathbf{u}=110 $$ → $$\displaystyle \mathbf{c}=110111 $$

• $$\displaystyle \mathbf{u}=111 $$ → $$\displaystyle \mathbf{c}=110000 $$? Wait, recalc:

  $$\displaystyle 111 \times G = (1,1,1) \cdot \text{rows} = (1+0+0, 0+1+0, 0+0+1, 1+0+1, 1+1+1, 0+1+1) = (1,1,1,0,1,0) $$?

  Actually:

  First bit: $$\displaystyle 1\cdot1 + 1\cdot0 + 1\cdot0 = 1 $$

  Second: $$\displaystyle 1\cdot0 + 1\cdot1 + 1\cdot0 = 1 $$

  Third: $$\displaystyle 1\cdot0 + 1\cdot0 + 1\cdot1 = 1 $$

  Fourth: $$\displaystyle 1\cdot1 + 1\cdot0 + 1\cdot1 = 0 $$ (mod 2)

  Fifth: $$\displaystyle 1\cdot1 + 1\cdot1 + 1\cdot1 = 1 $$

  Sixth: $$\displaystyle 1\cdot0 + 1\cdot1 + 1\cdot1 = 0 $$

  → $$\displaystyle \mathbf{c}=111010 $$? Let's list systematically:

4.3.2 Minimum Distance and Error Detection/Correction

• Weight of each codeword (number of 1s):

  • 000000: 0

  • 001111: 4

  • 010011: 3

  • 011100: 3

  • 100110: 3

  • 101101: 4

  • 110111: 5

  • 111010: 4

• Minimum distance $$\displaystyle d_{\min} = 3 $$ (smallest non-zero weight).

• Error detection: up to $$\displaystyle d_{\min}-1 = 2 $$ errors.

• Error correction: up to $$\displaystyle t = \lfloor (d_{\min}-1)/2 \rfloor = 1 $$ error.

5. CYCLIC CODES

5.1 Algebraic Structure and Generator Polynomial $g(X)$

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

• Represent codeword as polynomial: $$\displaystyle c(X) = c_0 + c_1 X + \dots + c_{n-1} X^{n-1} $$.

• Generator polynomial $g(X)$: monic polynomial of degree $n-k$ that divides $$\displaystyle X^n + 1 $$.

• All codewords are multiples of $g(X)$: $$\displaystyle c(X) = m(X) g(X) $$, where $\deg m(X) \leq k-1$.

5.2 Encoder Implementation (Shift-Register Based)

• Non-systematic encoder: Feed message polynomial $m(X)$ into linear shift register with feedback based on $g(X)$.

• Output = contents of register after $n$ shifts.

• Systematic encoder: Append parity bits. Often uses division: $$\displaystyle m(X) X^{n-k} = q(X) g(X) + r(X) $$, where $r(X)$ = parity polynomial.

5.3 Syndrome Calculation and Error Detection

• Syndrome $$\displaystyle S(X) = r(X) \bmod g(X) $$ (remainder of received polynomial division by $g(X)$).

• $$\displaystyle S(X)=0 $$ → no detected error (or undetectable error in code space).

• $S(X) \neq 0$ → error detected; can correct if error pattern known.

5.4 Systematic Form of Generator and Parity-Check Matrices

• For cyclic code with $$\displaystyle g(X) = g_0 + g_1 X + \dots + g_{n-k} X^{n-k} $$ (with $$\displaystyle g_{n-k}=1 $$):

  • Systematic $G$:

$$G = \begin{bmatrix} g_{n-k} & g_{n-k-1} & \dots & g_0 & 0 & \dots & 0 \\ 0 & g_{n-k} & \dots & g_1 & g_0 & \dots & 0 \\ \vdots & & \ddots & & & \ddots & \vdots \\ 0 & \dots & 0 & g_{n-k} & \dots & g_0 \end{bmatrix}$$

(Each row is $$\displaystyle X^i g(X) \bmod (X^n+1) $$ shifted).

• Parity-check polynomial $$\displaystyle h(X) = (X^n+1)/g(X) $$.

• Systematic $H$: Derived from $h(X)$ similarly.

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

5.5.1 Encoder Block Diagram

• $$\displaystyle g(X) = X^3 + X + 1 $$ → feedback taps at positions corresponding to coefficients (except leading): $$\displaystyle X^3 $$ term → shift 3, $X$ term → shift 1, constant → direct input.

• Non-systematic encoder: 3-stage shift register with feedback from stage 3 and stage 1 (XOR) to input.

• Systematic encoder: Divide $$\displaystyle m(X)X^3 $$ by $g(X)$; remainder = parity bits.

5.5.2 Syndrome Calculator Design

• Compute $$\displaystyle S(X) = r(X) \bmod g(X) $$ using same shift register but with parallel output (syndrome = register contents after feeding $r(X)$).

• Circuit: 3-stage LFSR with feedback taps at $$\displaystyle X^3 $$ and $X$ coefficients.

5.5.3 Derivation of $G$ and $H$ in Systematic Form

• $$\displaystyle g(X) = X^3 + X + 1 $$ → coefficients: $$\displaystyle g_3=1, g_2=0, g_1=1, g_0=1 $$.

• $$\displaystyle X^n+1 = X^7+1 $$; $$\displaystyle h(X) = (X^7+1)/(X^3+X+1) = X^4 + X^2 + X + 1 $$ (by polynomial division).

• Systematic $G$ (4×7):

$$ G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ % X^3 g(X) mod (X^7+1) = X^6 + X^4 + X^3? Actually compute: 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ % X^4 g(X) mod? Better: each row i: X^i g(X) mod (X^7+1) 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} $$

Let's compute properly:

• Row 0: $$\displaystyle g(X) = X^3 + X + 1 $$ → coefficients for $$\displaystyle X^0 $$ to $$\displaystyle X^6 $$: [1,1,0,1,0,0,0]? Wait, $$\displaystyle g(X)=1 + X + X^3 $$. So for systematic form, we want $$\displaystyle [I_4 \mid P] $$.

Actually standard (7,4) Hamming code is cyclic with $$\displaystyle g(X)=X^3+X+1 $$. Systematic $G$:

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

(Parity bits: positions 4,5,6? Actually indices 4,5,6 are parity if systematic means message first).

Verify: $g(X)$ should divide each row polynomial.

Row 0: $$\displaystyle m_0(X)=1 $$, codeword $$\displaystyle c_0(X)=g(X)=X^3+X+1 $$ → polynomial: $$\displaystyle 1 + X + X^3 $$ → coefficients for $$\displaystyle X^0..X^6 $$: [1,1,0,1,0,0,0]? That's not systematic.

For systematic encoding: $$\displaystyle c(X) = m(X)X^3 + r(X) $$ where $$\displaystyle r(X) = m(X)X^3 \bmod g(X) $$.

So $G$ rows correspond to $$\displaystyle X^i X^3 \bmod g(X) $$ plus $$\displaystyle X^i $$ in message part.

Easier: Known systematic generator for this code:

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

Check: first row: $$\displaystyle m_0=1 $$ → codeword: $1000110$? That's $$\displaystyle X^5+X^4+1 $$? Actually polynomial: $$\displaystyle 1 + X^4 + X^5 $$? Not matching $g(X)$.

Let's derive:

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

For $$\displaystyle m(X)=1 $$: $$\displaystyle m(X)X^3 = X^3 $$. Divide by $g(X)$: $$\displaystyle X^3 = 1\cdot g(X) + (X^2+X+1) $$? Because $$\displaystyle g(X)=X^3+X+1 $$, so $$\displaystyle X^3 - (X^3+X+1) = -X-1 = X+1 $$ mod 2? Actually mod 2: $$\displaystyle X^3 = (X^3+X+1) + (X+1) $$ → remainder $X+1$. So parity bits = $X+1$ → coefficients [1,1,0] for $$\displaystyle X^0,X^1,X^2 $$? But systematic means parity at end: codeword = $$\displaystyle m(X)X^3 + r(X) = X^3 + (X+1) = X^3 + X + 1 $$ → polynomial: $$\displaystyle 1 + X + X^3 $$ → bits: position 0:1, pos1:1, pos2:0, pos3:1, pos4:0, pos5:0, pos6:0? That's not systematic (message bits at start).

To get systematic, we want $$\displaystyle c(X) = m_0 + m_1 X + m_2 X^2 + m_3 X^3 + p_0 X^4 + p_1 X^5 + p_2 X^6 $$.

So we need to find $P$ such that $$\displaystyle [I_4 \mid P] $$ rows are multiples of $g(X)$.

Known result: For $$\displaystyle g(X)=X^3+X+1 $$, systematic $G$ is as above. Let's accept standard form.

• Systematic $H$: $$\displaystyle H = [P^T \mid I_3] $$.

  $P = \begin{bmatrix}

  1 & 1 & 0 \

  0 & 1 & 1 \

  1 & 0 & 1 \

  1 & 1 & 1

  \end{bmatrix}$? Actually from $G$ above, $P$ is last 3 columns:

  Columns 4,5,6 (0-indexed? In matrix, columns 4,5,6 are 5th,6th,7th):

  Col4: [1,0,1,1]^T, Col5: [1,1,0,1]^T, Col6: [0,1,1,1]^T.

  So $P = \begin{bmatrix}

  1 & 1 & 0 \

  0 & 1 & 1 \

  1 & 0 & 1 \

  1 & 1 & 1

  \end{bmatrix}$.

  Then $P^T = \begin{bmatrix}

  1 & 0 & 1 & 1 \

  1 & 1 & 0 & 1 \

  0 & 1 & 1 & 1

  \end{bmatrix}$.

  So $H = [P^T \mid I_3] = \begin{bmatrix}

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

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

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

  \end{bmatrix}$.

  Check $$\displaystyle G H^T = 0 $$? Should hold.

6. CONVOLUTIONAL CODES

6.1 Encoder Structure and Constraint Length $K$

• Encoder: $n$ output bits for each $k$ input bits (often $$\displaystyle k=1 $$).

• Constraint length $K$: number of input bits over which output depends.

• Memory $$\displaystyle m = K-1 $$; number of states = $$\displaystyle 2^m $$.

• Generator polynomials $$\displaystyle g^{(j)}(D) $$ for each output $j$, where $D$ = delay operator.

• Example: (2,1,3) code: $$\displaystyle k=1 $$, $$\displaystyle n=2 $$, $$\displaystyle K=3 $$, $$\displaystyle m=2 $$ → 4 states.

6.2 Code Tree, Trellis Diagram, and State Diagram

• State diagram: nodes = states, edges = transitions labeled (input, outputs).

• Code tree: expands indefinitely; shows all possible output sequences.

• Trellis diagram: time-unfolded state diagram; all states at each time step connected by branches.

• Relation: Trellis is a folded version of code tree (merges identical state paths).

6.3 Viterbi Algorithm for Maximum Likelihood Decoding

6.3.1 Path Metric and Branch Metric

• Branch metric $BM$: Hamming distance between received bits and expected branch outputs.

• Path metric $PM(t,s)$: cumulative metric to reach state $s$ at time $t$.

$$PM(t,s) = \min_{s'} [PM(t-1,s') + BM(s' \to s)]$$

6.3.2 Survivor Path Selection

• For each state at time $t$, compute metrics from all incoming transitions.

• Select survivor: path with minimum metric (for hard decision).

• Store survivor path and metric.

• After $L$ steps (traceback depth), trace back from state with minimum final metric.

[!TIP] Complexity: $$\displaystyle O(2^m \cdot 2^k) $$ per step; traceback depth typically $5K$ to $10K$.

6.4 Example: (2,1,3) Convolutional Encoder

6.4.1 Generator Polynomials

• $$\displaystyle g^{(1)}(D) = 1 + D + D^2 $$ (octal 7)

• $$\displaystyle g^{(2)}(D) = 1 + D^2 $$ (octal 5)

• Input $$\displaystyle u_t $$, 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.4.2 State Diagram and Trellis

• States: $$\displaystyle s_t = (u_{t-1}, u_{t-2}) $$ → 4 states: 00, 01, 10, 11.

• State transitions:

  • From $s$ with input $$\displaystyle u_t $$ → next state $$\displaystyle s' = (u_t, u_{t-1}) $$.

  • Outputs $$\displaystyle (v_t^{(1)}, v_t^{(2)}) $$ computed from $$\displaystyle u_t, u_{t-1}, u_{t-2} $$.

• Trellis: for $$\displaystyle t=0 $$ to $T$, show all states at each $t$ with branches labeled (input, output).

7. BCH CODES

7.1 Principles and Design Procedure

• BCH codes: family of t-error correcting cyclic codes over $$\displaystyle GF(2^m) $$.

• Designed to have consecutive powers of primitive element $\alpha$ as roots in $$\displaystyle GF(2^m) $$.

• Design parameters: $(n, k, t)$ with $$\displaystyle n = 2^m - 1 $$, $k \geq n - mt$, $$\displaystyle d_{\min} \geq 2t+1 $$.

7.1.1 Primitive Polynomials and Field Extensions

• Primitive polynomial $p(x)$ of degree $m$: irreducible, generates $$\displaystyle GF(2^m) $$.

• $\alpha$ = root of $p(x)$; powers $$\displaystyle \alpha^1, \alpha^2, \dots, \alpha^{2^m-2} $$ are all non-zero elements.

7.1.2 Determining Generator Polynomial Roots

• Choose distinct powers $$\displaystyle \alpha^b, \alpha^{b+1}, \dots, \alpha^{b+2t-1} $$.

• Minimal polynomial $$\displaystyle m_i(X) $$ of each root.

• Generator polynomial: $$\displaystyle g(X) = \text{lcm}[m_1(X), m_2(X), \dots, m_{2t}(X)] $$.

• Degree of $g(X)$ ≤ $mt$.

7.2 Error Correction Capability

• Can correct up to $t$ errors.

• Syndrome calculation: $$\displaystyle S_j = r(\alpha^j) $$ for $$\displaystyle j=1,\dots,2t $$.

• Use Berlekamp-Massey or Euclidean algorithm to find error locator polynomial $\sigma(X)$.

• Find roots of $\sigma(X)$ → error positions.

• Solve for error magnitudes (for binary BCH, magnitudes = 1).

7.3 Example with Small Parameters: (7,4) BCH Code

• $$\displaystyle m=3 $$ → $$\displaystyle n=7 $$, $$\displaystyle t=1 $$ → $$\displaystyle d_{\min} \geq 3 $$.

• Roots: $$\displaystyle \alpha, \alpha^2 $$ (consecutive powers).

• Minimal polynomials:

  • $$\displaystyle m_1(X) $$ for $\alpha$: since $\alpha$ in $GF(8)$, minimal polynomial degree divides 3. For primitive $\alpha$, $$\displaystyle m_1(X)=X^3+X+1 $$ (if $\alpha$ root of that).

  • $$\displaystyle m_2(X) $$ for $$\displaystyle \alpha^2 $$: same as $$\displaystyle m_1(X) $$ because $$\displaystyle \alpha^2 $$ has same minimal polynomial (since $\alpha$ primitive, cycle length 7, so $$\displaystyle \alpha^2 $$ also generates field).

• So $$\displaystyle g(X) = \text{lcm}(X^3+X+1, X^3+X+1) = X^3+X+1 $$.

• Thus (7,4) BCH with $$\displaystyle t=1 $$ is same as (7,4) Hamming/cyclic code from Section 5.

8. ADVANCED TOPICS AND SHORT NOTES (FROM EXAM)

8.1 Code Tree in Convolutional Codes (Relation to Trellis)

• Code tree: binary tree where each branch at depth $t$ corresponds to input bit and outputs $n$ bits.

• Each node at depth $t$ represents a unique state sequence.

• Trellis: obtained by merging nodes in code tree that correspond to same state at time $t$.

• Advantage: Trellis has finite states ($$\displaystyle 2^m $$) vs. infinite tree; enables Viterbi algorithm.

8.2 Viterbi Algorithm: Detailed Steps and Complexity

Steps:

1. Initialization: Set $$\displaystyle PM(0,0)=0 $$, others = $\infty$.

2. For each time step $$\displaystyle t=1 $$ to $L$:

   • For each state $s$:

     • For each incoming transition from $s'$:

       • Compute $$\displaystyle BM = d_H(\text{received}, \text{expected output}) $$.

       • $$\displaystyle PM_{\text{temp}} = PM(t-1,s') + BM $$.

     • Select $s'$ giving minimum $$\displaystyle PM_{\text{temp}} $$ → survivor.

     • Store $$\displaystyle PM(t,s) = \min PM_{\text{temp}} $$ and survivor pointer.

3. Traceback: After $L$ steps, find state with minimum $PM(L,s)$; trace back through survivor pointers for $D$ steps (traceback depth).

Complexity:

• Per time step: $$\displaystyle 2^m \cdot 2^k $$ branch metrics (for binary input $$\displaystyle k=1 $$, $$\displaystyle 2^m $$ branches).

• Memory: store $PM$ and pointers for $$\displaystyle 2^m $$ states over $L$ steps (or sliding window).

• $D$ typically $5K$ to $10K$ for near-optimal performance.

8.3 Extended Huffman Coding (Handling Non-Power-of-Two Alphabets)

• Problem: Standard Huffman may produce code lengths not powers of 2, causing inefficiency in bit-stuffing.

• Solution: Combine symbols into composite symbols so that number of composites is power of 2.

• Example: 5 symbols → use pairs → 25 composites (some impossible). Huffman on 25 symbols → code lengths closer to integer multiples of $$\displaystyle \log_2 25 $$.

• Reduces variance and improves packing into bytes/words.

8.4 Lempel-Ziv Coding: Parsing and Dictionary Update

• LZ77:

  • Parsing: Scan input; at each position, find longest match in sliding window (size $N$).

  • Output: (offset, length) for match; if no match, output literal.

  • Dictionary: implicit in window; no explicit storage.

• LZ78:

  • Parsing: Start with empty dictionary; read symbols until current string not in dictionary.

  • Output: (index of current string in dictionary, next symbol).

  • Dictionary update: Add new string = current string + next symbol.

  • Example: "ABABCBABAB" →

    (0,A) → dict[1]=A

    (0,B) → dict[2]=B

    (1,A) → dict[3]=AB

    (0,C) → dict[4]=C

    (2,B) → dict[5]=BB? Wait: current string "B" (index 2) + next symbol "B" → "BB"? Actually after "C", next is "B", so current string is "B" (since last was "C", start new). So (2,B) means string "B" (index 2) + "B" → "BB". But input is "ABABCBABAB", after "ABABC", next is "B", so "B" is in dict (index 2), so output (2,B) and add "BB". But next is "A", so start new: (0,A). Then "B": (1,B)? Let's do properly:

    Input: A B A B C B A B A B

    Step1: "A" not in dict → (0,A), add "A" as 1.

    Step2: "B" not in dict → (0,B), add "B" as 2.

    Step3: "A" in dict (1), next "B" → output (1,B), add "AB" as 3.

    Step4: "C" not in dict → (0,C), add "C" as 4.

    Step5: "B" in dict (2), next "A" → output (2,A), add "BA" as 5.

    Step6: "B" in dict (2), next "B" → output (2,B), add "BB" as 6.

    Step7: "A" in dict (1), next "B" → output (1,B) again? But "AB" is in dict (3), so actually after step6, we are at position after "BB"? Let's parse sequentially:

    Actually LZ78 parses into phrases: start empty, read until phrase not in dict.

    Phrase1: "A" → (0,A), dict[1]="A"

    Phrase2: "B" → (0,B), dict[2]="B"

    Phrase3: "AB" → (1,B) because "A" is dict[1], next "B" → add "AB" as 3.

    Phrase4: "C" → (0,C), dict[4]="C"

    Phrase5: "BA" → (2,A) because "B" is dict[2], next "A" → add "BA" as 5.

    Phrase6: "BAB" → (3,B) because "AB" is dict[3], next "B" → add "BAB" as 6.

    So output: (0,A),(0,B),(1,B),(0,C),(2,A),(3,B).

    Dictionary grows adaptively.

8.5 Arithmetic Coding: Implementation Issues and Precision

• Precision: Requires high precision arithmetic to maintain interval boundaries.

  • Use integer arithmetic with renormalization (e.g., E3, MQ coder in JPEG2000).

  • Prevent underflow/overflow by scaling.

• Implementation issues:

  • Model adaptation: probabilities updated on the fly (adaptive arithmetic coding).

  • Underflow: when interval becomes too small; handled by bit output and renormalization.

  • Overflow: use arbitrary precision integers or fixed-point with careful scaling.

  • Speed: table-driven vs. on-the-fly probability updates.

• Example: In DEFLATE, arithmetic coding replaced by Huffman for simplicity, but arithmetic used in JPEG2000 and H.264/AVC (CABAC).