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

UNIT 2: INFORMATION THEORY AND CODING

1. FUNDAMENTALS OF INFORMATION THEORY

1.1. Core Concepts

• Uncertainty: Measured by entropy; higher uncertainty → higher entropy.

• Information: Surprise value of an event; for message \(x_i\) with probability \(p(x_i)\):

  \(I(x_i) = \log_2 \frac{1}{p(x_i)} = -\log_2 p(x_i)\) bits.

• Entropy \(H(X)\): Average information/uncertainty of source \(X\) with \(M\) messages:

  \(H(X) = -\sum_{i=1}^{M} p(x_i) \log_2 p(x_i)\) bits/symbol.

• Axiomatic Properties of \(H(X)\):

  1. Continuity: Small change in probabilities → small change in \(H\).

  2. Symmetry: \(H\) unchanged if probabilities permuted.

  3. Expansibility: Adding zero-probability event doesn’t change \(H\).

  4. Non-negativity: \(H \geq 0\).

  5. Maximum for Equiprobable: \(H \leq \log_2 M\).

• Joint Entropy \(H(X,Y)\): Uncertainty of two sources:

  \(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 of \(Y\) given \(X\):

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

• Marginal Entropy: \(H(X) = -\sum_i p(x_i) \log_2 p(x_i)\).

1.2. Entropy Optimization

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

Let \(p_1, p_2, p_3\) with \(p_1+p_2+p_3=1\).

\(H = - (p_1 \log_2 p_1 + p_2 \log_2 p_2 + p_3 \log_2 p_3)\).

Using Lagrange multiplier \(\lambda\) for constraint:

\(\mathcal{L} = H + \lambda (1 - p_1 - p_2 - p_3)\).

Set \(\frac{\partial \mathcal{L}}{\partial p_i} = 0\) → \(-\log_2 p_i - \frac{1}{\ln 2} - \lambda = 0\) → \(p_i = 2^{-\lambda - 1/\ln 2} = \text{constant}\).

Thus \(p_1 = p_2 = p_3 = \frac{1}{3}\).

\(\boxed{H_{\text{max}} = \log_2 3 \approx 1.585 \text{ bits}}\).

[!TIP] Common Pitfall: Forgetting constraint \(p_i \geq 0\) and \(\sum p_i = 1\).

1.3. Mutual Information

• Definition: \(I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)\). Measures information \(X\) conveys about \(Y\).

• Proof: \(I(X;Y) = H(X) + H(Y) - H(X,Y)\)

  From definitions:

  \(H(X,Y) = H(X) + H(Y|X)\) → \(H(Y|X) = H(X,Y) - H(X)\).

  Substitute: \(I(X;Y) = H(X) - (H(X,Y)-H(X)) = 2H(X) - H(X,Y)\)? Wait, correct:

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

• Properties:

  • Symmetric: \(I(X;Y) = I(Y;X)\).

  • Non-negative: \(I(X;Y) \geq 0\).

  • \(I(X;Y) \leq \min[H(X), H(Y)]\).

• Chain Rule: \(I(X_1,X_2,...,X_n; Y) = \sum_{i=1}^{n} I(X_i; Y | X_1,...,X_{i-1})\).

2. SOURCE CODING TECHNIQUES

2.1. Huffman Coding

• Algorithm (for minimum variance code):

  1. List probabilities in descending order.

  2. Combine two smallest probabilities → new node.

  3. Repeat until single node; assign 0/1 to branches (shorter code to higher prob).

  4. To minimize variance, when probabilities equal, combine those with smallest code lengths first.

• Code Efficiency \(\eta\):

  \(\eta = \frac{H(X)}{L} \times 100\%\), where \(L = \sum p_i l_i\) (average code length).

• Extended Huffman: Group \(r\) symbols together → alphabet size \(M^r\); reduces redundancy for small \(r\).

2.2. Arithmetic Coding

• Principle: Represent entire message as interval \([0,1)\); subdivide based on symbol probabilities.

• Example (for probabilities \(p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1\)):

  Message "BAD":

  Initial range \([0,1)\).

  For 'B': \([0, 0.4)\) → subrange \([0.4 \times 0.3, 0.4 \times 0.6) = [0.12, 0.24)\).

  For 'A': \([0.12, 0.12+0.4\times0.4) = [0.12, 0.28)\).

  For 'D': \([0.12+0.4\times0.4\times0.9, 0.12+0.4\times0.4) = [0.264, 0.28)\).

  Choose any number in \([0.264, 0.28)\), e.g., 0.27 → binary 0.010001... (transmit).

• Decoding: Multiply by 1, compare cumulative probabilities.

2.3. Dictionary-Based Coding

• Lempel-Ziv (LZ77):

  • Sliding window: search buffer (previous data) + look-ahead buffer.

  • Output triple \((\text{offset}, \text{length}, \text{next char})\).

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

• LZ78:

  • Build dictionary dynamically: each new phrase = previous phrase + next symbol.

  • Output pair \((\text{dict index}, \text{next char})\).

  • Example: "ABABABC" → (0,A), (0,B), (1,A), (0,C), etc.

• Adaptive Dictionary: Dictionary updated on-the-fly; no prior knowledge needed.

2.4. Morse Code Analysis

• Symbol durations: dot = 1 unit, dash = 3 units, pause between symbols = 1 unit.

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

• Information content:

  \(I(\text{dot}) = -\log_2 \frac{2}{3} \approx 0.585\) bits,

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

• Average information per symbol:

  \(H = \frac{2}{3} \times 0.585 + \frac{1}{3} \times 1.585 \approx 0.918\) bits/symbol.

• Information transmission rate:

  Dot duration = 1 ms, pause = 1 ms → symbol duration = 2 ms (average? Actually, each symbol (dot/dash) followed by 1 unit pause, so for dot: 2 units, dash: 4 units. But rate = \(H / \text{avg symbol duration}\).

  Avg duration = \(P(\text{dot}) \times 2 + P(\text{dash}) \times 4 = \frac{2}{3}\times2 + \frac{1}{3}\times4 = \frac{8}{3} \approx 2.667\) units.

  Since 1 unit = 1 ms, avg duration = 2.667 ms.

  \(\boxed{R = \frac{0.918 \text{ bits}}{2.667 \text{ ms}} \approx 344 \text{ bits/s}}\).

3. CHANNEL CAPACITY AND CHANNEL MODELS

3.1. Binary Symmetric Channel (BSC)

• Model: Input \(X \in \{0,1\}\), output \(Y \in \{0,1\}\); crossover probability \(p\):

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

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

• Input probabilities: Given source messages \(x_1=000, x_2=001, x_3=011, x_4=111\) equiprobable → each \(P(x_i)=0.25\).

  Compute \(P(X=0)\): from messages, bits: first bit always 0 for \(x_1,x_2\)? Actually:

  \(x_1=000\), \(x_2=001\), \(x_3=011\), \(x_4=111\).

  Count 0s in first position: \(x_1,x_2\) → 2 out of 4 → \(P(X_1=0)=0.5\). Similarly, second bit: \(x_1,x_2\)? \(x_1=0, x_2=0, x_3=1, x_4=1\) → \(P(X_2=0)=0.5\). Third bit: \(x_1=0, x_2=1, x_3=1, x_4=1\) → \(P(X_3=0)=0.25\). But channel is memoryless, so input distribution per bit? Usually we consider binary input channel, so we need marginal \(P(X=0)\) for the channel input. Since messages are equiprobable, each bit position may have different distribution. But for BSC capacity formula, we optimize over input distribution. For given source, we compute output distribution from channel.

  Actually, the question: "Calculate p(0) and p(1) at the input." Input to channel is bits from source. Since source messages are equiprobable, we compute marginal probability of 0 in the bit stream.

  Total bits: 4 messages × 3 bits = 12 bits.

  Number of 0s: \(x_1\):3, \(x_2\):2, \(x_3\):1, \(x_4\):0 → total 6 zeros.

  So \(P(X=0) = 6/12 = 0.5\), \(P(X=1)=0.5\).

  (Alternatively, per bit position average: first bit: 0.5, second: 0.5, third: 0.25 → overall average 0.5? Weighted: (0.5+0.5+0.25)/3 ≈ 0.417? That’s not correct because each bit position equally likely? Actually, each message equally likely, so each bit position has its own distribution, but for the channel we consider the input distribution that maximizes capacity. Here source is fixed, so the input distribution is determined by source. Since source messages are equiprobable, the input bit distribution is the average over bits:

  \(P(X=0) = \frac{1}{3}[P(X_1=0)+P(X_2=0)+P(X_3=0)] = \frac{1}{3}(0.5+0.5+0.25) = \frac{1.25}{3} \approx 0.4167\).

  But the question likely expects simple: from the 4 messages, count total 0s and 1s. There are 6 zeros and 6 ones? Wait:

  \(x_1=000\) → 3 zeros,

  \(x_2=001\) → 2 zeros, 1 one,

  \(x_3=011\) → 1 zero, 2 ones,

  \(x_4=111\) → 0 zeros, 3 ones.

  Total zeros = 3+2+1+0 = 6, total ones = 0+1+2+3 = 6. So indeed \(P(X=0)=0.5\), \(P(X=1)=0.5\).

  So answer: \(p(0)=0.5\), \(p(1)=0.5\).

• Channel Capacity \(C\):

  \(C = \max_{P(X)} I(X;Y) = 1 - H(p)\) bits/channel use, where \(H(p) = -p \log_2 p - (1-p) \log_2 (1-p)\).

  For \(p=0.2\): \(H(0.2) \approx 0.7219\) bits → \(C \approx 0.2781\) bits/use.

• Code Efficiency (for given source with entropy \(H(X)\) and average code length \(L\)):

  \(\eta = \frac{H(X)}{L} \times 100\%\). But here "code efficiency relative to capacity" might mean \(\frac{R}{C}\) where \(R\) is transmission rate? Actually, for channel coding, efficiency often \(k/n\). But from context: BSC with source messages, we computed source entropy? The source has 4 equiprobable messages → \(H(X) = \log_2 4 = 2\) bits/message. But channel uses 3 bits per message (since each message is 3 bits). So transmission rate \(R = \frac{2 \text{ bits}}{3 \text{ channel uses}} \approx 0.6667\) bits/use. Capacity \(C \approx 0.2781\) bits/use. Then efficiency relative to capacity? Possibly \(\frac{R}{C} > 1\) which is impossible? Wait, capacity is maximum reliable rate. Here \(R > C\), so error is inevitable. But efficiency might be defined as \(\frac{H(X)}{L}\) for source coding, but here we have channel coding? The question: "Calculate the efficiency of the code." Given source messages are encoded into 3-bit codewords (000,001,011,111). This is a channel code? Actually, it's a mapping from 4 messages to 3-bit codewords. So code rate \(k/n = 4/3\)? But \(k\) is message bits? Messages are variable length? Actually each message is 3 bits? No, messages are 4 distinct 3-bit strings. So we have 4 source messages, each represented by 3 bits. So \(k = \log_2 4 = 2\) bits of information per message, but transmitted in 3 channel uses. So rate \(R = 2/3 \approx 0.6667\) bits/channel use. Capacity \(C \approx 0.2781\) bits/use. So \(R > C\), code is not capacity-achieving. Efficiency might be \(R/C \approx 2.4\) or 240%? That seems odd. Alternatively, efficiency could be \(\frac{H(X)}{n}\) where \(n=3\)? That would be \(2/3 \approx 66.67\%\). But typically for channel codes, efficiency = \(k/n\). Here \(k=2\) (since 4 messages), \(n=3\) → efficiency \(= 2/3 \approx 66.7\%\). I think that’s what they want.

  So \(\boxed{\eta = \frac{k}{n} = \frac{2}{3} \approx 66.67\%}\).

3.2. Binary Erasure Channel (BEC)

• Model: Input \(X \in \{0,1\}\), output \(Y \in \{0,1,e\}\) where \(e\) = erasure.

  \(P(Y=e|X=0)=P(Y=e|X=1)=p\), \(P(Y=0|X=0)=1-p\), \(P(Y=1|X=1)=1-p\).

• Capacity Derivation:

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

  \(H(Y|X) = H(p)\) (binary entropy of erasure probability).

  Maximize \(H(Y)\) over \(P(X)\). Let \(P(X=0)=q\), then \(P(Y=0)=q(1-p)\), \(P(Y=1)=(1-q)(1-p)\), \(P(Y=e)=p\).

  \(H(Y) = H_2(q(1-p)) + H_2((1-q)(1-p)) + H_2(p)\)? Actually, three symbols, but \(p\) fixed. Maximize \(H(Y)\) w.r.t. \(q\). Since \(Y\) has two variable probabilities summing to \(1-p\), maximum entropy for two symbols is 1 bit when they are equal. So set \(q(1-p) = (1-q)(1-p)\) → \(q=0.5\). Then \(P(Y=0)=P(Y=1)=0.5(1-p)\), \(P(Y=e)=p\).

  \(H(Y)_{\text{max}} = -2 \times 0.5(1-p) \log_2[0.5(1-p)] - p \log_2 p\)

  \(= (1-p) \log_2 \frac{1}{1-p} - p \log_2 p + (1-p)\)? Simplify:

  \(= (1-p) [1 - \log_2(1-p)] - p \log_2 p\)? Actually:

  \(-2 \times 0.5(1-p) \log_2(0.5(1-p)) = -(1-p)[\log_2 0.5 + \log_2(1-p)] = -(1-p)[-1 + \log_2(1-p)] = (1-p) - (1-p)\log_2(1-p)\).

  So \(H(Y)_{\text{max}} = (1-p) - (1-p)\log_2(1-p) - p \log_2 p\).

  Then \(I(X;Y) = H(Y)_{\text{max}} - H(p) = (1-p) - (1-p)\log_2(1-p) - p \log_2 p - [-p \log_2 p - (1-p)\log_2(1-p)] = 1-p\).

  \(\boxed{C_{\text{BEC}} = 1-p \text{ bits/channel use}}\).

3.3. Channel Capacity Theorem

• Statement: For a channel with bandwidth \(B\) Hz and signal-to-noise ratio \(S/N\), capacity \(C = B \log_2(1 + S/N)\) bits/s (Shannon-Hartley).

  More generally, for a discrete memoryless channel: \(C = \max_{P(X)} I(X;Y)\).

• Infinite Bandwidth Limit: As \(B \to \infty\), noise power \(N = N_0 B\) (white noise). Then

  \(C = B \log_2\left(1 + \frac{S}{N_0 B}\right) \approx B \cdot \frac{S}{N_0 B \ln 2} = \frac{S}{N_0 \ln 2}\) bits/s.

  \(\boxed{C_{\infty} = \frac{S}{N_0 \ln 2} \approx 1.44 \frac{S}{N_0} \text{ bits/s}}\) (constant, independent of \(B\)).

• Interpretation: Infinite bandwidth allows arbitrarily low error rate at finite power, but capacity saturates due to noise.

4. LINEAR BLOCK CODES

4.1. Generator Matrix

• Form: \(G\) is \(k \times n\) matrix; codeword \(\mathbf{c} = \mathbf{u} G\), where \(\mathbf{u}\) is \(k\)-bit message.

• Systematic Form: \(G = [I_k | P]\), where \(I_k\) is \(k \times k\) identity, \(P\) is \(k \times (n-k)\) parity matrix.

  Codeword: \(\mathbf{c} = [\mathbf{u} | \mathbf{u}P]\).

• Non-systematic: No identity submatrix; e.g., \(G = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\).

• Generating All Code Vectors: For \(k=2\), \(n=3\), \(G = [I|P] = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}\):

  \(\mathbf{u}=00 \to \mathbf{c}=000\),

  \(\mathbf{u}=01 \to \mathbf{c}=011\),

  \(\mathbf{u}=10 \to \mathbf{c}=101\),

  \(\mathbf{u}=11 \to \mathbf{c}=110\).

4.2. Hamming Codes

• Parameters: \((n, k, d_{\min}=3)\) with \(n = 2^m - 1\), \(k = n - m\), \(m \geq 2\).

• Design for 4-bit message: \(k=4\) → need \(m\) such that \(2^m - 1 - m \geq 4\). Try \(m=3\): \(n=7\), \(k=4\) → \((7,4)\) Hamming code.

• Parity-Check Matrix \(H\): \(m \times n\) matrix with all non-zero binary \(m\)-tuples as columns. For \(m=3\):

  \(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}\) (columns in order 1 to 7).

• Error Correction: Syndrome \(\mathbf{s} = \mathbf{r} H^T\). If \(\mathbf{s} \neq 0\), its value gives column index of error (single-bit error).

5. CYCLIC CODES

5.1. Algebraic Structure

• Code Polynomials: \(c(X) = c_0 + c_1 X + ... + c_{n-1} X^{n-1}\).

• Generator Polynomial \(g(X)\): Degree \(n-k\), divides \(X^n - 1\).

• Property: \(c(X)\) is valid code polynomial iff \(g(X) | c(X)\).

• Example: \((7,4)\) code with \(g(X)=X^3+X+1\) (degree 3, so \(k=4\)).

5.2. Encoder Implementation

• Block Diagram (for systematic encoding):

  DiagramSEARCH: cyclic encoder shift register systematic

  • Message polynomial \(m(X)\) shifted in, feedback via \(g(X)\).

  • After \(k\) shifts, switch to output \(n-k\) parity bits.

• Systematic Encoding:

  \(c(X) = X^{n-k} m(X) + r(X)\), where \(r(X) = [X^{n-k} m(X)] \bmod g(X)\).

5.3. Syndrome Calculation

• Syndrome \(s(X) = r(X) \bmod g(X)\) (remainder when received polynomial divided by \(g(X)\)).

• Block Diagram:

  DiagramSEARCH: syndrome calculator cyclic code shift register
  • Similar to encoder but without message input; received \(r(X)\) fed, output is syndrome.

• Error Detection: If \(s(X) \neq 0\), error detected.

5.4. Systematic Matrices

• Generator Matrix \(G\): From \(g(X) = g_0 + g_1 X + ... + g_{n-k} X^{n-k}\) (with \(g_0=1\)).

  For \((7,4)\), \(g(X)=1 + X + X^3\) → \(g_0=1, g_1=1, g_2=0, g_3=1\).

  \(G = \begin{bmatrix} 1 & 0 & 0 & 0 & g_0 & g_1 & g_2 \\ 0 & 1 & 0 & 0 & g_1 & g_2 & g_3 \\ 0 & 0 & 1 & 0 & g_2 & g_3 & g_4 \\ 0 & 0 & 0 & 1 & g_3 & g_4 & g_5 \end{bmatrix}\) but careful: for degree 3, \(n-k=3\), so \(P\) is \(4 \times 3\). With \(g(X)=1+X+X^3\), coefficients: \(g_0=1, g_1=1, g_2=0, g_3=1\). Then

  \(G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}\)? Actually, systematic form: first \(k\) columns identity, last \(n-k\) columns are coefficients of \(X^{n-k} m(X) \bmod g(X)\) for each unit message. Standard: \(G = [I | P]\), where \(P\) is \(k \times (n-k)\) matrix with rows corresponding to \(X^{n-k} X^i \bmod g(X)\) for \(i=0,...,k-1\). For \(g(X)=X^3+X+1\), compute:

  \(X^3 \bmod g(X) = X^3 - (X^3+X+1) = -X-1 \equiv X+1 \pmod{2}\)? Actually modulo 2: \(X^3 \equiv X+1 \pmod{g(X)}\).

  So for \(i=0\): \(X^3 \cdot 1 \bmod g(X) = X+1\) → coefficients: \(1,1,0\)? Degree up to 2: \(1 + X\) → \(c_4=1, c_5=1, c_6=0\).

  For \(i=1\): \(X^3 \cdot X = X^4 \bmod g(X)\). \(X^4 = X \cdot X^3 \equiv X(X+1)=X^2+X\). So coefficients: \(0,1,1\)? Actually: \(X^2+X\) → \(c_4=0, c_5=1, c_6=1\).

  For \(i=2\): \(X^3 \cdot X^2 = X^5 \bmod g(X)\). \(X^5 = X^2 \cdot X^3 \equiv X^2(X+1)=X^3+X^2 \equiv (X+1)+X^2 = X^2+X+1\). So \(c_4=1, c_5=1, c_6=1\).

  For \(i=3\): \(X^3 \cdot X^3 = X^6 \bmod g(X)\). \(X^6 = X^3 \cdot X^3 \equiv (X+1)^2 = X^2+1\)? Actually: \(X^6 = (X^3)^2 \equiv (X+1)^2 = X^2+2X+1 \equiv X^2+1 \pmod{2}\). So \(c_4=1, c_5=0, c_6=1\)? Wait, \(X^2+1\) → coefficients: constant=1, X=0, X^2=1 → so for positions 4,5,6 (corresponding to \(X^3, X^4, X^5\)? Actually, in systematic code: \(c(X) = u_0 + u_1 X + u_2 X^2 + u_3 X^3 + p_0 X^4 + p_1 X^5 + p_2 X^6\). So \(p_0, p_1, p_2\) are coefficients of \(X^4, X^5, X^6\)? But in \(X^{n-k} m(X) = X^3 m(X)\), the lowest power is \(X^3\) (since \(m(X)\) starts at \(X^0\)). So after modulo, we get polynomial of degree ≤ 2? Actually \(X^3 m(X)\) has terms from \(X^3\) to \(X^{6}\). Modulo \(g(X)\) (degree 3) gives remainder of degree ≤ 2. So remainder is \(r_0 + r_1 X + r_2 X^2\), which become coefficients for \(X^4, X^5, X^6\)? Wait, systematic form: \(c(X) = X^{n-k} m(X) + r(X)\), with \(\deg(r) < n-k\). Here \(n-k=3\), so \(r(X) = r_0 + r_1 X + r_2 X^2\). Then codeword coefficients:

  \(c_0 = u_0\), \(c_1 = u_1\), \(c_2 = u_2\), \(c_3 = u_3\),

  \(c_4 = r_0\), \(c_5 = r_1\), \(c_6 = r_2\).

  So for \(m(X)=u_0 + u_1 X + u_2 X^2 + u_3 X^3\), compute \(X^3 m(X) \bmod g(X)\).

  For \(u_0=1, u_1=u_2=u_3=0\): \(X^3 \bmod g(X) = X+1\) → \(r_0=1, r_1=1, r_2=0\) → row1 of P: [1,1,0].

  For \(u_1=1\): \(X^4 \bmod g(X) = X^2+X\) → \(r_0=0, r_1=1, r_2=1\) → row2: [0,1,1].

  For \(u_2=1\): \(X^5 \bmod g(X) = X^2+X+1\) → row3: [1,1,1].

  For \(u_3=1\): \(X^6 \bmod g(X) = X^2+1\) → row4: [1,0,1]? Actually \(X^2+1\) → \(r_0=1, r_1=0, r_2=1\).

  So \(P = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}\)? But \(P\) is \(4 \times 3\), yes.

  Then \(G = [I_4 | P] = \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}\).

  But check: for \(g(X)=X^3+X+1\), known systematic generator for \((7,4)\) is \(G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}\)? There are variations depending on ordering. I'll stick to the computed one.

• Parity-Check Matrix \(H\): \(H = [-P^T | I_{n-k}]\) for systematic \(G\). Here \(P^T = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix}\), so \(-P^T = P^T\) (mod 2).

  \(H = \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}\).

  Check: \(G H^T = 0\).

5.5. Decoding

• Syndrome Table: List all error patterns \(e(X)\) of weight ≤ \(t\) (error-correcting capability) with their syndromes \(s(X) = e(X) \bmod g(X)\).

• Procedure:

  1. Compute syndrome \(\mathbf{s} = \mathbf{r} H^T\).

  2. If \(\mathbf{s}=0\), assume no error.

  3. Else, find error pattern \(\mathbf{e}\) with syndrome \(\mathbf{s}\) from table (assuming ≤ \(t\) errors).

  4. Correct: \(\mathbf{c} = \mathbf{r} - \mathbf{e}\) (mod 2).

• General Decoder: Syndrome calculator → look-up table → error correction.

6. CONVOLUTIONAL CODES

6.1. Encoder Design

• Parameters \((n, k, m)\):

  \(n\) = output bits per input,

  \(k\) = input bits per time unit,

  \(m\) = memory order (number of shift registers).

  Constraint length \(K = m+1\) (number of bits each output depends on).

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

  \(k=1\), \(n=2\), \(m=3\) → \(K=4\).

  Generator polynomials (in octal): \(g_1=1111_2=17_8\), \(g_2=1101_2=15_8\).

  Encoder: 3 shift registers, input feeds all, outputs modulo-2 sum of taps.

• Transform Domain: Output sequences \(Y_1(X), Y_2(X)\) from input \(U(X)\):

  \(Y_1(X) = U(X) \cdot G_1(X)\), \(Y_2(X) = U(X) \cdot G_2(X)\), where \(G_i(X)\) are generator polynomials.

6.2. Graphical Representations

• Code Tree: Shows all possible output branches for each input at each time. Root → branches labeled by output bits.

• State Diagram: State = contents of shift registers (for \(m=3\), 3 bits → 8 states). Transitions labeled by input/output.

• Trellis Diagram: Time-unfolded state diagram; all paths through states.

6.3. Viterbi Algorithm

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

• Procedure:

  1. Initialize: metric=0 at state 0 at time 0.

  2. For each time step, for each state, compute branch metrics (Hamming distance between received bits and expected output for each incoming branch).

  3. Add to previous state’s metric → path metric.

  4. Add-Compare-Select (ACS): For each state, keep survivor path (minimum metric) and its metric.

  5. After \(L\) steps (traceback depth), trace back from state with minimum metric to get decoded bits.

• Example (for \((2,1,3)\) with received sequence, show path metrics and survivor selection).

7. BCH CODES

7.1. Introduction and Capabilities

• t-error correcting: Can correct up to \(t\) random errors.

• Primitive BCH: Length \(n = 2^m - 1\), designed over \(GF(2^m)\).

• Narrow-sense: Generator polynomial has consecutive powers of primitive element \(\alpha\) as roots: \(\alpha, \alpha^2, ..., \alpha^{2t}\).

7.2. Generator Polynomial Construction

• Steps:

  1. Choose primitive polynomial \(p(X)\) of degree \(m\) to generate \(GF(2^m)\).

  2. Let \(\alpha\) be root of \(p(X)\) in \(GF(2^m)\).

  3. Find minimal polynomials \(m_i(X)\) of \(\alpha^i\) for \(i=1,...,2t\).

  4. \(g(X) = \text{lcm}[m_1(X), m_2(X), ..., m_{2t}(X)]\).

• Example: \(t=1\), \(n=7\) (\(m=3\)), primitive polynomial \(p(X)=X^3+X+1\).

  Roots: \(\alpha, \alpha^2, \alpha^4\) (since \(\alpha^3 = \alpha+1\), etc.).

  Minimal polynomials: \(m_1(X)=X^3+X+1\), \(m_2(X)=X^3+X^2+1\), \(m_3(X)=m_1(X)\)? Actually \(\alpha^4 = \alpha \cdot \alpha^3 = \alpha(\alpha+1) = \alpha^2+\alpha\), its minimal polynomial is same as \(\alpha\)? For \(n=7\), the cyclotomic cosets mod 7: \(\{1,2,4\}\) and \(\{3,6,5\}\)? Actually, \(2^1=2, 2^2=4, 2^3=8≡1 \pmod{7}\) → coset {1,2,4}. \(2^1=2, 2^2=4, 2^3=1\) mod 7? Wait, for \(i=1\): \(1,2,4\); for \(i=3\): \(3,6,5\) (since \(2\cdot3=6, 2\cdot6=12≡5, 2\cdot5=10≡3\)). So minimal polynomials: \(m_1(X)=m_2(X)=m_4(X)\) and \(m_3(X)=m_5(X)=m_6(X)\). For \(t=1\), we need roots \(\alpha, \alpha^2\) → both in same coset → \(g(X)=m_1(X)=X^3+X+1\). This gives \((7,4)\) Hamming code. For true BCH with \(t>1\), e.g., \(t=2\), need roots \(\alpha,\alpha^2,\alpha^3,\alpha^4\) → both cosets → \(g(X)=m_1(X) m_3(X) = (X^3+X+1)(X^3+X^2+1) = X^6+X^5+X^4+X^3+X^2+X+1\) → \((7,1)\) code? Actually degree 6, so \(k=1\). But we want \(t=2\) with \(n=15\) typically.

7.3. Encoding and Decoding

• Systematic Encoding:

  \(c(X) = X^{n-k} m(X) + [X^{n-k} m(X)] \bmod g(X)\).

• Syndrome Computation:

  \(S_j = r(\alpha^j) = \sum_{i=0}^{n-1} r_i \alpha^{ij}\) for \(j=1,...,2t\).

• Berlekamp-Massey Algorithm:

  Find error locator polynomial \(\sigma(X)\) from syndromes.

  Steps: Initialize \(\sigma^{(0)}(X)=1\), \(B(X)=1\), \(L=0\), \(m=-1\). Iterate to compute discrepancy \(\Delta\), update \(\sigma(X)\) and \(L\).

• Error Location: Roots of \(\sigma(X)\) give error positions \(\alpha^{-i}\).

• Example (for \((15,7)\) BCH with \(t=2\)):

  \(m=4\), \(n=15\), \(2t=4\) → roots \(\alpha, \alpha^2, \alpha^3, \alpha^4\).

  Minimal polynomials: \(m_1(X)\) for \(\{1,2,4,8\}\)? Actually \(2^1=2, 2^2=4, 2^3=8, 2^4=16≡1 \pmod{15}\) → coset {1,2,4,8}. \(m_3(X)\) for \(\{3,6,9,12\}\)? \(2\cdot3=6, 2\cdot6=12, 2\cdot12=24≡9, 2\cdot9=18≡3\) → coset {3,6,9,12}. So \(g(X)=m_1(X) m_3(X)\). Compute \(m_1(X)=X^4+X+1\), \(m_3(X)=X^4+X^3+X^2+X+1\)? Then \(g(X)\) degree 8 → \(k=7\). Encoding: multiply message by \(X^8\) mod \(g(X)\). Decoding: compute syndromes \(S_1, S_2, S_3, S_4\), apply Berlekamp-Massey to get \(\sigma(X)\), find roots, correct.

8. ADDITIONAL TOPICS (SHORT NOTES)

8.1. Code Variance

• Definition: Variance of code lengths: \(\sigma^2 = \sum p_i (l_i - L)^2\), where \(L = \sum p_i l_i\).

• Importance: Measures spread of code lengths; lower variance → more uniform lengths, useful for buffering and real-time applications. Huffman coding with minimum variance reduces buffer requirements.

8.2. Performance Metrics

• Source Coding Efficiency: \(\eta = \frac{H(X)}{L} \times 100\%\), where \(L\) is average code length. Ideal: \(\eta = 100\%\) when \(L = H(X)\).

• Channel Coding Efficiency: \(\eta = \frac{k}{n} \times 100\%\), where \(k\) = message bits, \(n\) = codeword length. Must satisfy \(R \leq C\) for reliable communication.

• Transmission Rate vs. Channel Capacity:

  • If \(R < C\): reliable transmission possible with arbitrarily low error (Shannon’s theorem).

  • If \(R > C\): error probability bounded away from zero.

  • Capacity \(C\) is supremum of achievable rates.

[!TIP] Exam Focus:

• Entropy proof (M=3) and mutual info identities are frequently asked.

• Huffman with variance requires careful tree construction.

• Morse code problems: compute info per symbol, avg info, rate given durations.

• BSC/BEC capacity: memorize formulas \(C=1-H(p)\) and \(C=1-p\).

• Cyclic codes: be able to derive systematic \(G\) and \(H\) from \(g(X)\).

• Convolutional codes: draw code tree, state diagram, trellis for \((2,1,3)\); apply Viterbi with path metrics.

• BCH: know steps for generator polynomial and Berlekamp-Massey (conceptually).

• Always box final formulas.