8.5 Error Control Coding Techniques

8.5 Error Control Coding Techniques

Introduction to Error Control Coding

In digital communication, the transmitted signal is inevitably corrupted by noise, interference, and fading in the channel, leading to errors at the receiver. Error Control Coding (Channel Coding) is a powerful technique that introduces controlled redundancy into the transmitted data to detect and correct these errors, thereby dramatically improving the reliability of the communication link. This involves adding extra bits (parity bits) to the information bits according to specific mathematical rules. This section explores the fundamental concepts of channel coding, from simple parity checks to sophisticated block and convolutional codes, and introduces the algorithms used to decode them.

---

1. Introduction to Channel Coding and Hamming Distance

1.1 The Need for Channel Coding

1. Trade-off: Channel coding introduces redundancy (extra bits), which increases the transmitted data rate for a fixed information rate, effectively consuming more bandwidth. In return, it provides a coding gain – a reduction in the required $E_b/N_0$ to achieve the same Bit Error Rate (BER) as an uncoded system.

2. Shannon's Second Theorem (Noisy Channel Coding Theorem): For a channel of capacity $C$, there exist error-correcting codes that allow information to be transmitted at any rate $R < C$ with an arbitrarily low probability of error. This theorem motivates the search for good codes.

1.2 Basic Terminology

• Information Bits (k): The original message bits to be transmitted.

• Code Bits (n): The total bits transmitted after adding redundancy ($n > k$).

• Code Rate (R): $R = k/n$. It is the fraction of the transmitted bits that carry information. A lower code rate implies more redundancy and stronger error protection.

• Codeword: A specific sequence of $n$ bits generated by the encoder for a given block of $k$ information bits.

• Hamming Weight (w): The number of non-zero bits in a codeword (for binary codes, the number of 1s).

• Hamming Distance (d): The number of bit positions in which two codewords differ.

  • Example: Distance between 10110 and 11001 is 4 (2nd, 3rd, 4th, 5th bits differ).

1.3 Minimum Hamming Distance ($d_{min}$)

1. Definition: The smallest Hamming distance between any pair of valid codewords in a code. $d_{min} = \min_{i \neq j} d(c_i, c_j)$

2. Fundamental Importance: $d_{min}$ determines the error detection and correction capability of a block code.

   • Error Detection Capability: A code can detect up to $(d_{min} - 1)$ errors.

   • Error Correction Capability: A code can correct up to $t$ errors, where: $t = \left\lfloor \frac{d_{min} - 1}{2} \right\rfloor$ ($\lfloor \cdot \rfloor$ denotes the floor function).

   • Simultaneous Detection and Correction: It can correct up to $t$ errors and detect up to $s$ errors provided $s + t < d_{min}$ and $t \le s$.

3. Geometric Interpretation: Valid codewords are points in an n-dimensional space. $d_{min}$ is the minimum separation between any two points. For error correction, we draw a sphere of radius $t$ around each codeword. These spheres must not overlap, which requires $2t + 1 \le d_{min}$.

---

2. Simple Parity Codes

These are the simplest forms of error detection codes.

2.1 Single Parity Check Code

1. Operation: A single parity bit is appended to a block of $k$ information bits to make the total number of 1s in the $n = k+1$ bit codeword either even or odd.

   • Even Parity: Parity bit is chosen so that the total number of 1s is even.

   • Odd Parity: Parity bit is chosen so that the total number of 1s is odd.

2. Encoding Example (Even Parity): Information bits: 1 0 1 1 0. Number of 1s = 3 (odd). Parity bit must be 1 to make total even. Codeword: 1 0 1 1 0 1.

3. Decoding: The receiver counts the number of 1s in the received $n$-bit block. For even parity, if the count is odd, an error is detected.

4. Capabilities:

   • Error Detection: Can detect any odd number of bit errors within the block.

   • Error Correction: None.

   • Limitation: Cannot detect an even number of errors (they preserve parity).

   • $d_{min} = 2$. (One error changes parity, two errors restore it).

2.2 Two-Dimensional Parity Check (Row-Column Parity)

1. Operation: Information bits are arranged in a rectangular array (matrix). A parity bit is calculated for each row (row parity) and for each column (column parity). All row and column parity bits are transmitted along with the data.

2. Capabilities:

   • Can detect all single, double, and triple errors.

   • Can correct any single error (the erroneous bit is at the intersection of the row and column with failed parity).

   • Can detect most patterns of four or more errors.

3. Application: Used in early computer memory systems and some simple communication protocols.

---

3. Block Codes

In block codes, the encoder takes a block of $k$ information bits and produces a block of $n$ code bits. The code is defined for specific integers $n$ and $k$, denoted as an $(n, k)$ code.

3.1 Linear Block Codes

1. Definition: A block code is linear if the modulo-2 sum (XOR) of any two valid codewords is also a valid codeword. The all-zero codeword is always a member of a linear code.

2. Advantages: Linear structure simplifies encoding and decoding operations significantly using matrix algebra.

3. Generator Matrix (G):

   • A $k \times n$ binary matrix that defines the code.

   • Encoding is performed via matrix multiplication: $\mathbf{c} = \mathbf{m} \mathbf{G}$ where $\mathbf{m}$ is a $1 \times k$ row vector of information bits and $\mathbf{c}$ is the resulting $1 \times n$ codeword.

   • Systematic Form: The generator matrix can be put in the form $\mathbf{G} = [ \mathbf{I}_k | \mathbf{P} ]$, where $\mathbf{I}_k$ is the $k \times k$ identity matrix and $\mathbf{P}$ is a $k \times (n-k)$ parity submatrix. In this form, the codeword consists of the (n-k)$ parity-check bits: $\mathbf{c} = (\mathbf{m}, \mathbf{m}\mathbf{P})$.

3.2 Systematic Block Codes

1. Definition: A code where the information bits appear unchanged, in a fixed position, within the codeword. The remaining bits are parity bits.

2. Advantage: Easy to extract information bits after decoding. Most practical linear block codes are systematic.

3.3 Parity-Check Matrix (H) and Syndrome Decoding

1. Parity-Check Matrix (H):

   • For a systematic code with $\mathbf{G} = [ \mathbf{I}_k | \mathbf{P} ]$, the corresponding $(n-k) \times n$ parity-check matrix is: $\mathbf{H} = [ \mathbf{P}^T | \mathbf{I}_{n-k} ]$

   • Fundamental Property: For any valid codeword $\mathbf{c}$, $\mathbf{c} \mathbf{H}^T = \mathbf{0}$ (the zero vector).

2. Syndrome:

   • Let $\mathbf{r}$ be the received vector (possibly corrupted): $\mathbf{r} = \mathbf{c} + \mathbf{e}$, where $\mathbf{e}$ is the error vector.

   • The syndrome $\mathbf{s}$ is calculated at the receiver: $\mathbf{s} = \mathbf{r} \mathbf{H}^T$.

   • From the property: $\mathbf{s} = (\mathbf{c} + \mathbf{e}) \mathbf{H}^T = \mathbf{e} \mathbf{H}^T$.

   • Key Insight: The syndrome depends only on the error pattern $\mathbf{e}$, not on the transmitted codeword. A non-zero syndrome indicates an error.

3. Syndrome Decoding:

   • The receiver pre-computes a syndrome lookup table (standard array) mapping each possible syndrome to the most likely error pattern $\hat{\mathbf{e}}$ (the one with the smallest Hamming weight).

   • Upon receiving $\mathbf{r}$, it computes $\mathbf{s}$, looks up $\hat{\mathbf{e}}$, and estimates the codeword: $\hat{\mathbf{c}} = \mathbf{r} + \hat{\mathbf{e}}$.

   • This is a minimum distance decoding rule (maximum likelihood for the BSC).

3.4 Cyclic Codes

1. Definition: A subclass of linear block codes with an additional elegant property: Any cyclic shift of a valid codeword is also a valid codeword.

2. Polynomial Representation:

   • A codeword $(c_{n-1}, c_{n-2}, ..., c_1, c_0)$ is represented by a polynomial of degree less than $n$: $c(X) = c_{n-1}X^{n-1} + c_{n-2}X^{n-2} + ... + c_1X + c_0$

   • A cyclic shift corresponds to multiplying $c(X)$ by $X$ modulo $(X^n - 1)$.

3. Generator Polynomial (g(X)):

   • A cyclic code is uniquely defined by a generator polynomial $g(X)$ of degree $(n-k)$, which is a factor of $(X^n - 1)$.

   • All valid codewords are multiples of $g(X)$.

   • Encoding can be performed using a simple linear feedback shift register (LFSR) circuit.

4. Examples:

   • Cyclic Redundancy Check (CRC) Codes: Powerful error-detection codes widely used in data storage and networking (Ethernet, USB, ZIP). Defined by their generator polynomial.

   • BCH Codes and Reed-Solomon Codes: Important cyclic codes with strong algebraic structure and excellent correction capabilities. Reed-Solomon codes are particularly effective against burst errors (used in CDs, DVDs, QR codes).

---

4. Convolutional Codes

Unlike block codes, convolutional codes have memory. The encoder outputs $n$ bits for each incoming $k$ bits, but these output bits depend on the current and previous input bits.

4.1 Encoding

1. Encoder Structure: Implemented using one or more shift registers and modulo-2 adders (XOR gates).

2. Parameters:

   • Constraint Length (K): The number of shift register stages + 1 (i.e., the number of input bits that influence the output). It defines the memory of the encoder.

   • Code Rate (R): $R = k/n$. Most common are $R = 1/2$ or $1/3$ ($k=1$).

3. Operation: For each new block of $k$ input bits, the encoder:

   • Shifts them into the shift register.

   • Performs modulo-2 additions on specific taps of the register(s) to produce $n$ output bits.

   • The output is a continuous stream.

4. Generator Sequences (Polynomials): The connections from the shift register stages to the adders are defined by generator polynomials (in binary form). For a rate 1/2 code, there are two generators, $g_1$ and $g_2$.

4.2 Graphical Representations

These tools are essential for understanding and decoding convolutional codes.

4.2.1 Code Tree

• Represents all possible encoder output sequences as a function of time.

• Branches: Represent possible input bits (e.g., 0 = upper branch, 1 = lower branch). Each branch is labeled with the corresponding $n$ output bits.

• Nodes: Represent the state of the encoder (the contents of the shift register).

• Limitation: The tree grows exponentially with the input length, making it impractical for visualizing long sequences.

4.2.2 Trellis Diagram

• A collapsed version of the code tree. It merges identical states at the same time step, revealing the repetitive structure of the encoder.

• Trellis Section: A snapshot of possible state transitions from time $t$ to time $t+1$.

• Path: A sequence of connected branches through the trellis represents one possible transmitted sequence.

• This is the most important representation for decoding algorithms like the Viterbi algorithm.

4.2.3 State Diagram

• A finite-state machine representation showing all possible states of the encoder and the transitions between them.

• States: Represent the content of the shift register.

• Edges: Labeled as input bit / output bits, showing the transition caused by an input and the resulting output.

• Useful for analyzing code properties but not directly used for decoding long sequences.

4.3 The Viterbi Algorithm - An Introduction to Decoding

1. Objective: To find the most likely transmitted sequence (the path through the trellis) given the received noisy sequence. This is Maximum Likelihood Sequence Estimation (MLSE).

2. Core Idea (Dynamic Programming):

   • Instead of comparing the received sequence with all possible transmitted sequences (exponentially complex), the Viterbi algorithm works recursively through the trellis.

   • At each node (state) and time, it keeps track of only the one most likely path (the survivor path) leading to that state.

   • Less likely paths are pruned away. This is the principle of optimality: the best path to a future state must begin with the best path to a current state.

3. Key Steps (for Hard-Decision Decoding): a. Branch Metric Calculation: For each branch in a trellis section, compute the Hamming distance between the $n$ received bits and the $n$ bits labeling that branch. b. Path Metric Accumulation (Add): For each state at time $t+1$, for each incoming branch, add the branch metric to the path metric of the state at time $t$ from which it originated. c. Comparison and Selection (Compare-Select): For each state at time $t+1$, compare the accumulated metrics of all incoming paths. Select the path with the smallest metric (the survivor). Discard the others. d. Traceback: After processing the entire received sequence (or a sufficiently long window), trace back along the survivor path of the state with the smallest final metric to retrieve the most likely sequence of transmitted bits.

4. Significance: The Viterbi algorithm provides an efficient, optimal way to decode convolutional codes. Its complexity is linear in the sequence length but exponential in the constraint length $K$.

Conclusion: Error control coding is a cornerstone of reliable digital communication. Simple parity codes provide basic error detection, while structured linear and cyclic block codes offer a balance of performance and complexity for error correction. Convolutional codes, with their memory and elegant trellis structure, enable powerful decoding via the Viterbi algorithm. These techniques, used individually or in combination (like Turbo codes and LDPC codes), are what allow modern communication systems (from deep-space probes to 5G cellular networks) to approach the theoretical limits of performance set by Shannon's theorems.